From 616ace2d9299eee2006650ed3f13e9241664ad20 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Marcelina=20Ko=C5=9Bcielnicka?= Date: Thu, 12 Aug 2021 03:31:56 +0200 Subject: [PATCH] Add new opt_mem_priority pass. --- passes/memory/memory.cc | 6 +- passes/opt/Makefile.inc | 1 + passes/opt/opt_mem_priority.cc | 109 ++++++++++++++++++ tests/opt/opt_mem_priority.ys | 205 +++++++++++++++++++++++++++++++++ 4 files changed, 319 insertions(+), 2 deletions(-) create mode 100644 passes/opt/opt_mem_priority.cc create mode 100644 tests/opt/opt_mem_priority.ys diff --git a/passes/memory/memory.cc b/passes/memory/memory.cc index 29e140ba9..a4751cb61 100644 --- a/passes/memory/memory.cc +++ b/passes/memory/memory.cc @@ -36,9 +36,10 @@ struct MemoryPass : public Pass { log("This pass calls all the other memory_* passes in a useful order:\n"); log("\n"); log(" opt_mem\n"); + log(" opt_mem_priority\n"); + log(" opt_mem_feedback\n"); log(" memory_dff (skipped if called with -nordff or -memx)\n"); log(" opt_clean\n"); - log(" opt_mem_feedback\n"); log(" memory_share\n"); log(" memory_memx (when called with -memx)\n"); log(" opt_clean\n"); @@ -84,10 +85,11 @@ struct MemoryPass : public Pass { extra_args(args, argidx, design); Pass::call(design, "opt_mem"); + Pass::call(design, "opt_mem_priority"); + Pass::call(design, "opt_mem_feedback"); if (!flag_nordff) Pass::call(design, "memory_dff"); Pass::call(design, "opt_clean"); - Pass::call(design, "opt_mem_feedback"); Pass::call(design, "memory_share"); if (flag_memx) Pass::call(design, "memory_memx"); diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc index b0192235b..d8eb2f0b9 100644 --- a/passes/opt/Makefile.inc +++ b/passes/opt/Makefile.inc @@ -3,6 +3,7 @@ OBJS += passes/opt/opt.o OBJS += passes/opt/opt_merge.o OBJS += passes/opt/opt_mem.o OBJS += passes/opt/opt_mem_feedback.o +OBJS += passes/opt/opt_mem_priority.o OBJS += passes/opt/opt_muxtree.o OBJS += passes/opt/opt_reduce.o OBJS += passes/opt/opt_dff.o diff --git a/passes/opt/opt_mem_priority.cc b/passes/opt/opt_mem_priority.cc new file mode 100644 index 000000000..49ece570b --- /dev/null +++ b/passes/opt/opt_mem_priority.cc @@ -0,0 +1,109 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2021 Marcelina Kościelnicka + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/yosys.h" +#include "kernel/modtools.h" +#include "kernel/qcsat.h" +#include "kernel/mem.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct OptMemPriorityPass : public Pass { + OptMemPriorityPass() : Pass("opt_mem_priority", "remove priority relations between write ports that can never collide") { } + void help() override + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" opt_mem_priority [selection]\n"); + log("\n"); + log("This pass detects cases where one memory write port has priority over another\n"); + log("even though they can never collide with each other — ie. there can never be\n"); + log("a situation where a given memory bit is written by both ports at the same\n"); + log("time, for example because of always-different addresses, or mutually exclusive\n"); + log("enable signals. In such cases, the priority relation is removed.\n"); + log("\n"); + } + void execute(std::vector args, RTLIL::Design *design) override { + log_header(design, "Executing OPT_MEM_PRIORITY pass (removing unnecessary memory write priority relations).\n"); + extra_args(args, 1, design); + + ModWalker modwalker(design); + + int total_count = 0; + for (auto module : design->selected_modules()) { + modwalker.setup(module); + for (auto &mem : Mem::get_selected_memories(module)) { + bool mem_changed = false; + QuickConeSat qcsat(modwalker); + for (int i = 0; i < GetSize(mem.wr_ports); i++) { + auto &wport1 = mem.wr_ports[i]; + for (int j = 0; j < GetSize(mem.wr_ports); j++) { + auto &wport2 = mem.wr_ports[j]; + if (!wport1.priority_mask[j]) + continue; + // No mixed width support — we could do it, but + // that would complicate code and wouldn't help + // anything since we run this pass before + // wide ports are created in normal flow. + if (wport1.wide_log2 != wport2.wide_log2) + continue; + // Two ports with priority, let's go. + pool> checked; + SigSpec addr1 = wport1.addr; + SigSpec addr2 = wport2.addr; + int abits = std::max(GetSize(addr1), GetSize(addr2)); + addr1.extend_u0(abits); + addr2.extend_u0(abits); + int addr_eq = qcsat.ez->vec_eq(qcsat.importSig(addr1), qcsat.importSig(addr2)); + bool ok = true; + for (int k = 0; k < GetSize(wport1.data); k++) { + SigBit wen1 = wport1.en[k]; + SigBit wen2 = wport2.en[k]; + if (checked.count({wen1, wen2})) + continue; + int wen1_sat = qcsat.importSigBit(wen1); + int wen2_sat = qcsat.importSigBit(wen2); + qcsat.prepare(); + if (qcsat.ez->solve(wen1_sat, wen2_sat, addr_eq)) { + ok = false; + break; + } + checked.insert({wen1, wen2}); + } + if (ok) { + total_count++; + mem_changed = true; + wport1.priority_mask[j] = false; + } + } + } + if (mem_changed) + mem.emit(); + } + } + + if (total_count) + design->scratchpad_set_bool("opt.did_something", true); + log("Performed a total of %d transformations.\n", total_count); + } +} OptMemPriorityPass; + +PRIVATE_NAMESPACE_END + diff --git a/tests/opt/opt_mem_priority.ys b/tests/opt/opt_mem_priority.ys new file mode 100644 index 000000000..c1261ddf7 --- /dev/null +++ b/tests/opt/opt_mem_priority.ys @@ -0,0 +1,205 @@ +# Bad case: independent write ports. + +read_verilog << EOT + +module top( + input [3:0] wa1, wa2, ra, wd1, wd2, + input clk, we1, we2, + output [3:0] rd); + +reg [3:0] mem[0:15]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) + mem[wa1] <= wd1; + if (we2) + mem[wa2] <= wd2; +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=4'b0100 %i + + +design -reset + +# Good case: write ports with definitely different addresses. + +read_verilog << EOT + +module top( + input [3:0] wa, ra, wd1, wd2, + input clk, we1, we2, + output [3:0] rd); + +reg [3:0] mem[0:15]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) + mem[wa] <= wd1; + if (we2) + mem[wa ^ 1] <= wd2; +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=4'b0000 %i + + +design -reset + +# Bad case 2: the above, but broken. + +read_verilog << EOT + +module top( + input [3:0] wa, ra, wd1, wd2, + input clk, we1, we2, + output [3:0] rd); + +reg [3:0] mem[0:15]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) + mem[wa] <= wd1; + if (we2) + mem[wa | 1] <= wd2; +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=4'b0100 %i + + +design -reset + +# Good case 2: write ports with disjoint bit enables. + +read_verilog << EOT + +module top( + input [3:0] wa1, wa2, ra, + input [1:0] wd1, wd2, + input clk, we1, we2, + output [3:0] rd); + +reg [3:0] mem[0:15]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) + mem[wa1][1:0] <= wd1; + if (we2) + mem[wa2][3:2] <= wd2; +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=4'b0000 %i + + +design -reset + +# Good case 3: write ports with soft priority logic already + +read_verilog << EOT + +module top( + input [3:0] wa1, wa2, ra, wd1, wd2, + input clk, we1, we2, + output [3:0] rd); + +reg [3:0] mem[0:15]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) + mem[wa1] <= wd1; + if (we2 && wa1 != wa2) + mem[wa2] <= wd2; +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=4'b0000 %i + + +design -reset + +# Good case 4: two wide write ports + +read_verilog << EOT + +module top( + input [5:0] wa1, wa2, + input [7:0] ra, + input [31:0] wd1, wd2, + input clk, we1, we2, + output [7:0] rd); + +reg [7:0] mem[0:255]; +assign rd = mem[ra]; + +always @(posedge clk) begin + if (we1) begin + mem[{wa1, 2'b00}] <= wd1[7:0]; + mem[{wa1, 2'b01}] <= wd1[15:8]; + mem[{wa1, 2'b10}] <= wd1[23:16]; + mem[{wa1, 2'b11}] <= wd1[31:24]; + end + if (we2) begin + mem[{wa2, 2'b00}] <= wd2[7:0]; + mem[{wa2, 2'b01}] <= wd2[15:8]; + mem[{wa2, 2'b10}] <= wd2[23:16]; + mem[{wa2, 2'b11}] <= wd2[31:24]; + end +end + +endmodule + +EOT + +hierarchy -auto-top +proc +opt +memory -nomap +select -assert-count 1 t:$mem_v2 +select -assert-count 1 t:$mem_v2 r:WR_PRIORITY_MASK=64'h0804020100000000 %i -- 2.30.2