From 297a0962ea399fcfa80656af2bc887c5725f5b82 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 19 Jul 2014 15:33:55 +0200 Subject: [PATCH] Added SAT-based write-port sharing to memory_share --- passes/memory/memory_share.cc | 180 ++++++++++++++++++++++++++++++++++ tests/memories/shared_ports.v | 25 +++++ 2 files changed, 205 insertions(+) create mode 100644 tests/memories/shared_ports.v diff --git a/passes/memory/memory_share.cc b/passes/memory/memory_share.cc index 4af0ebdca..20ff16dea 100644 --- a/passes/memory/memory_share.cc +++ b/passes/memory/memory_share.cc @@ -18,7 +18,9 @@ */ #include "kernel/rtlil.h" +#include "kernel/satgen.h" #include "kernel/sigtools.h" +#include "kernel/modwalker.h" #include "kernel/register.h" #include "kernel/log.h" #include @@ -37,6 +39,8 @@ struct MemoryShareWorker RTLIL::Design *design; RTLIL::Module *module; SigMap sigmap, sigmap_xmux; + ModWalker modwalker; + CellTypes cone_ct; std::map> sig_to_mux; std::map>, RTLIL::SigBit> conditions_logic_cache; @@ -470,6 +474,167 @@ struct MemoryShareWorker } + // -------------------------------------------------------- + // Consolidate write ports using sat-based resource sharing + // -------------------------------------------------------- + + void consolidate_wr_using_sat(std::string memid, std::vector &wr_ports) + { + if (wr_ports.size() <= 1) + return; + + ezDefaultSAT ez; + SatGen satgen(&ez, &modwalker.sigmap); + + // find list of considered ports and port pairs + + std::set considered_ports; + std::set considered_port_pairs; + + for (int i = 0; i < int(wr_ports.size()); i++) { + std::vector bits = modwalker.sigmap(wr_ports[i]->connections.at("\\EN")); + for (auto bit : bits) + if (bit == RTLIL::State::S1) + goto port_is_always_active; + if (modwalker.has_drivers(bits)) + considered_ports.insert(i); + port_is_always_active:; + } + + log("Consolidating write ports of memory %s using sat-based resource sharing:\n", log_id(memid)); + + bool cache_clk_enable = false; + bool cache_clk_polarity = false; + RTLIL::SigSpec cache_clk; + + for (int i = 0; i < int(wr_ports.size()); i++) + { + RTLIL::Cell *cell = wr_ports.at(i); + + if (cell->parameters.at("\\CLK_ENABLE").as_bool() != cache_clk_enable || + (cache_clk_enable && (sigmap(cell->connections.at("\\CLK")) != cache_clk || + cell->parameters.at("\\CLK_POLARITY").as_bool() != cache_clk_polarity))) + { + cache_clk_enable = cell->parameters.at("\\CLK_ENABLE").as_bool(); + cache_clk_polarity = cell->parameters.at("\\CLK_POLARITY").as_bool(); + cache_clk = sigmap(cell->connections.at("\\CLK")); + } + else if (i > 0 && considered_ports.count(i-1) && considered_ports.count(i)) + considered_port_pairs.insert(i); + + if (cache_clk_enable) + log(" Port %d (%s) on %s %s: %s\n", i, log_id(cell), + cache_clk_polarity ? "posedge" : "negedge", log_signal(cache_clk), + considered_ports.count(i) ? "considered" : "not considered"); + else + log(" Port %d (%s) unclocked: %s\n", i, log_id(cell), + considered_ports.count(i) ? "considered" : "not considered"); + } + + if (considered_port_pairs.size() < 1) { + log(" No two subsequent ports in same clock domain considered -> nothing to consolidate.\n"); + return; + } + + // create SAT representation of common input cone of all considered EN signals + + std::set sat_cells; + std::set bits_queue; + std::map port_to_sat_variable; + + for (int i = 0; i < int(wr_ports.size()); i++) + if (considered_port_pairs.count(i) || considered_port_pairs.count(i+1)) + { + RTLIL::SigSpec sig = modwalker.sigmap(wr_ports[i]->connections.at("\\EN")); + port_to_sat_variable[i] = ez.expression(ez.OpOr, satgen.importSigSpec(sig)); + + std::vector bits = sig; + bits_queue.insert(bits.begin(), bits.end()); + } + + while (!bits_queue.empty()) + { + std::set portbits; + modwalker.get_drivers(portbits, bits_queue); + bits_queue.clear(); + + for (auto &pbit : portbits) + if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) { + std::set &cell_inputs = modwalker.cell_inputs[pbit.cell]; + bits_queue.insert(cell_inputs.begin(), cell_inputs.end()); + sat_cells.insert(pbit.cell); + } + } + + log(" Common input cone for all EN signals: %d cells.\n", int(sat_cells.size())); + + for (auto cell : sat_cells) + satgen.importCell(cell); + + log(" Size of unconstrained SAT problem: %d variables, %d clauses\n", ez.numCnfVariables(), ez.numCnfClauses()); + + // merge subsequent ports if possible + + for (int i = 0; i < int(wr_ports.size()); i++) + { + if (!considered_port_pairs.count(i)) + continue; + + if (ez.solve(port_to_sat_variable.at(i-1), port_to_sat_variable.at(i))) { + log(" According to SAT solver sharing of port %d with port %d is not possible.\n", i-1, i); + continue; + } + + log(" Merging port %d into port %d.\n", i-1, i); + port_to_sat_variable.at(i) = ez.OR(port_to_sat_variable.at(i-1), port_to_sat_variable.at(i)); + + RTLIL::SigSpec last_addr = wr_ports[i-1]->connections.at("\\ADDR"); + RTLIL::SigSpec last_data = wr_ports[i-1]->connections.at("\\DATA"); + std::vector last_en = modwalker.sigmap(wr_ports[i-1]->connections.at("\\EN")); + + RTLIL::SigSpec this_addr = wr_ports[i]->connections.at("\\ADDR"); + RTLIL::SigSpec this_data = wr_ports[i]->connections.at("\\DATA"); + std::vector this_en = modwalker.sigmap(wr_ports[i]->connections.at("\\EN")); + + RTLIL::SigBit this_en_active = module->ReduceOr(NEW_ID, this_en); + + wr_ports[i]->connections.at("\\ADDR") = module->Mux(NEW_ID, last_addr, this_addr, this_en_active); + wr_ports[i]->connections.at("\\DATA") = module->Mux(NEW_ID, last_data, this_data, this_en_active); + + std::map, int> groups_en; + RTLIL::SigSpec grouped_last_en, grouped_this_en, en; + RTLIL::Wire *grouped_en = module->new_wire(0, NEW_ID); + + for (int j = 0; j < int(this_en.size()); j++) { + std::pair key(last_en[j], this_en[j]); + if (!groups_en.count(key)) { + grouped_last_en.append_bit(last_en[j]); + grouped_this_en.append_bit(this_en[j]); + groups_en[key] = grouped_en->width; + grouped_en->width++; + } + en.append(RTLIL::SigSpec(grouped_en, 1, groups_en[key])); + } + + module->addMux(NEW_ID, grouped_last_en, grouped_this_en, this_en_active, grouped_en); + wr_ports[i]->connections.at("\\EN") = en; + + module->cells.erase(wr_ports[i-1]->name); + delete wr_ports[i-1]; + wr_ports[i-1] = NULL; + } + + // Clean up `wr_ports': remove all NULL entries + + std::vector wr_ports_with_nulls; + wr_ports_with_nulls.swap(wr_ports); + + for (auto cell : wr_ports_with_nulls) + if (cell != NULL) + wr_ports.push_back(cell); + } + + // ------------- // Setup and run // ------------- @@ -515,6 +680,21 @@ struct MemoryShareWorker translate_rd_feedback_to_en(it.first, it.second.first, it.second.second); consolidate_wr_by_addr(it.first, it.second.second); } + + cone_ct.setup_internals(); + cone_ct.cell_types.erase("$mul"); + cone_ct.cell_types.erase("$mod"); + cone_ct.cell_types.erase("$div"); + cone_ct.cell_types.erase("$pow"); + cone_ct.cell_types.erase("$shl"); + cone_ct.cell_types.erase("$shr"); + cone_ct.cell_types.erase("$sshl"); + cone_ct.cell_types.erase("$sshr"); + + modwalker.setup(design, module, &cone_ct); + + for (auto &it : memindex) + consolidate_wr_using_sat(it.first, it.second.second); } }; diff --git a/tests/memories/shared_ports.v b/tests/memories/shared_ports.v new file mode 100644 index 000000000..94bad53e2 --- /dev/null +++ b/tests/memories/shared_ports.v @@ -0,0 +1,25 @@ +// expect-wr-ports 1 +// expect-rd-ports 1 + +module test( + input clk, + input wr_en1, wr_en2, wr_en3, + input [3:0] wr_addr1, wr_addr2, wr_addr3, + input [15:0] wr_data, + input [3:0] rd_addr, + output reg [31:0] rd_data +); + +reg [31:0] mem [0:15]; + +always @(posedge clk) begin + if (wr_en1) + mem[wr_addr1][15:0] <= wr_data; + else if (wr_en2) + mem[wr_addr2][23:8] <= wr_data; + else if (wr_en3) + mem[wr_addr3][31:16] <= wr_data; + rd_data <= mem[rd_addr]; +end + +endmodule -- 2.30.2