From 83450a94898321a239f67f92e05fb9a246f4dd6d Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 12:15:13 -0700 Subject: Move muxpack from passes/techmap to passes/opt --- passes/opt/muxpack.cc | 256 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 256 insertions(+) create mode 100644 passes/opt/muxpack.cc (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc new file mode 100644 index 000000000..9668b0d43 --- /dev/null +++ b/passes/opt/muxpack.cc @@ -0,0 +1,256 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * 2019 Eddie Hung + * + * 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/sigtools.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct MuxpackWorker +{ + Module *module; + SigMap sigmap; + + int mux_count, pmux_count; + + pool remove_cells; + + dict sig_chain_next; + dict sig_chain_prev; + pool sigbit_with_non_chain_users; + pool chain_start_cells; + + void make_sig_chain_next_prev() + { + for (auto wire : module->wires()) + { + if (wire->port_output || wire->get_bool_attribute("\\keep")) { + for (auto bit : sigmap(wire)) { + sigbit_with_non_chain_users.insert(bit); + } + } + } + + for (auto cell : module->cells()) + { + if (cell->type.in("$mux") && !cell->get_bool_attribute("\\keep")) + { + SigSpec a_sig = sigmap(cell->getPort("\\A")); + SigSpec b_sig = sigmap(cell->getPort("\\B")); + SigSpec y_sig = sigmap(cell->getPort("\\Y")); + + if (sig_chain_next.count(a_sig)) + for (auto a_bit : a_sig.bits()) + sigbit_with_non_chain_users.insert(a_bit); + else + sig_chain_next[a_sig] = cell; + + if (sig_chain_next.count(b_sig)) + for (auto b_bit : b_sig.bits()) + sigbit_with_non_chain_users.insert(b_bit); + else + sig_chain_next[b_sig] = cell; + + sig_chain_prev[y_sig] = cell; + continue; + } + + for (auto conn : cell->connections()) + if (cell->input(conn.first)) + for (auto bit : sigmap(conn.second)) + sigbit_with_non_chain_users.insert(bit); + } + } + + void find_chain_start_cells() + { + for (auto it : sig_chain_next) + { + SigSpec next_sig; + + for (auto bit : it.first.bits()) + if (sigbit_with_non_chain_users.count(bit)) + goto start_cell; + + next_sig = it.second->getPort("\\A"); + if (sig_chain_prev.count(next_sig) == 0) { + next_sig = it.second->getPort("\\B"); + if (sig_chain_prev.count(next_sig) == 0) + next_sig = SigSpec(); + } + + if (!next_sig.empty()) + { + Cell *c1 = sig_chain_prev.at(next_sig); + Cell *c2 = it.second; + + if (c1->type != c2->type) + goto start_cell; + + if (c1->parameters != c2->parameters) + goto start_cell; + + continue; + } + + start_cell: + chain_start_cells.insert(it.second); + } + } + + vector create_chain(Cell *start_cell) + { + vector chain; + + Cell *c = start_cell; + while (c != nullptr) + { + chain.push_back(c); + + SigSpec y_sig = sigmap(c->getPort("\\Y")); + + if (sig_chain_next.count(y_sig) == 0) + break; + + c = sig_chain_next.at(y_sig); + if (chain_start_cells.count(c) != 0) + break; + } + + return chain; + } + + void process_chain(vector &chain) + { + if (GetSize(chain) < 2) + return; + + int cursor = 0; + while (cursor < GetSize(chain)) + { + int cases = GetSize(chain) - cursor; + + Cell *first_cell = chain[cursor]; + dict taps_dict; + + if (cases < 2) { + cursor++; + continue; + } + + Cell *last_cell = chain[cursor+cases-1]; + + log("Converting %s.%s ... %s.%s to a pmux with %d cases.\n", + log_id(module), log_id(first_cell), log_id(module), log_id(last_cell), cases); + + mux_count += cases; + pmux_count += 1; + + first_cell->type = "$pmux"; + SigSpec b_sig = first_cell->getPort("\\B"); + SigSpec s_sig = first_cell->getPort("\\S"); + + for (int i = 1; i < cases; i++) { + Cell* prev_cell = chain[cursor+i-1]; + Cell* cursor_cell = chain[cursor+i]; + if (sigmap(prev_cell->getPort("\\Y")) == sigmap(cursor_cell->getPort("\\A"))) { + b_sig.append(cursor_cell->getPort("\\B")); + s_sig.append(cursor_cell->getPort("\\S")); + } + else { + b_sig.append(cursor_cell->getPort("\\A")); + s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S"))); + } + remove_cells.insert(cursor_cell); + } + + first_cell->setPort("\\B", b_sig); + first_cell->setPort("\\S", s_sig); + first_cell->setParam("\\S_WIDTH", GetSize(s_sig)); + first_cell->setPort("\\Y", last_cell->getPort("\\Y")); + + cursor += cases; + } + } + + void cleanup() + { + for (auto cell : remove_cells) + module->remove(cell); + + remove_cells.clear(); + sig_chain_next.clear(); + sig_chain_prev.clear(); + chain_start_cells.clear(); + } + + MuxpackWorker(Module *module) : + module(module), sigmap(module), mux_count(0), pmux_count(0) + { + make_sig_chain_next_prev(); + find_chain_start_cells(); + + for (auto c : chain_start_cells) { + vector chain = create_chain(c); + process_chain(chain); + } + + cleanup(); + } +}; + +struct MuxpackPass : public Pass { + MuxpackPass() : Pass("muxpack", "$mux cell cascades to $pmux") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" muxpack [selection]\n"); + log("\n"); + log("This pass converts cascaded chains of $mux cells (e.g. those created by if-else\n"); + log("constructs) into $pmux cells.\n"); + log("\n"); + } + void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing MUXPACK pass ($mux cell cascades to $pmux).\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + break; + } + extra_args(args, argidx, design); + + int mux_count = 0; + int pmux_count = 0; + + for (auto module : design->selected_modules()) { + MuxpackWorker worker(module); + mux_count += worker.mux_count; + pmux_count += worker.pmux_count; + } + + log("Converted %d (p)mux cells into %d pmux cells.\n", mux_count, pmux_count); + } +} MuxpackPass; + +PRIVATE_NAMESPACE_END -- cgit v1.2.3 From d2172c6846f710e9a362708e3308dd302110deb2 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 12:44:50 -0700 Subject: Non chain user check using next_sig --- passes/opt/muxpack.cc | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 9668b0d43..963083107 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -84,19 +84,17 @@ struct MuxpackWorker { for (auto it : sig_chain_next) { - SigSpec next_sig; - - for (auto bit : it.first.bits()) - if (sigbit_with_non_chain_users.count(bit)) - goto start_cell; - - next_sig = it.second->getPort("\\A"); + SigSpec next_sig = it.second->getPort("\\A"); if (sig_chain_prev.count(next_sig) == 0) { next_sig = it.second->getPort("\\B"); if (sig_chain_prev.count(next_sig) == 0) next_sig = SigSpec(); } + for (auto bit : next_sig.bits()) + if (sigbit_with_non_chain_users.count(bit)) + goto start_cell; + if (!next_sig.empty()) { Cell *c1 = sig_chain_prev.at(next_sig); -- cgit v1.2.3 From 978fda94f684185a7d583a3865b7a68459344e46 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 12:46:42 -0700 Subject: Fix spacing --- passes/opt/muxpack.cc | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 963083107..cb13a45b0 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -43,9 +43,8 @@ struct MuxpackWorker for (auto wire : module->wires()) { if (wire->port_output || wire->get_bool_attribute("\\keep")) { - for (auto bit : sigmap(wire)) { + for (auto bit : sigmap(wire)) sigbit_with_non_chain_users.insert(bit); - } } } @@ -58,8 +57,8 @@ struct MuxpackWorker SigSpec y_sig = sigmap(cell->getPort("\\Y")); if (sig_chain_next.count(a_sig)) - for (auto a_bit : a_sig.bits()) - sigbit_with_non_chain_users.insert(a_bit); + for (auto a_bit : a_sig.bits()) + sigbit_with_non_chain_users.insert(a_bit); else sig_chain_next[a_sig] = cell; @@ -70,7 +69,7 @@ struct MuxpackWorker sig_chain_next[b_sig] = cell; sig_chain_prev[y_sig] = cell; - continue; + continue; } for (auto conn : cell->connections()) @@ -182,7 +181,7 @@ struct MuxpackWorker first_cell->setPort("\\B", b_sig); first_cell->setPort("\\S", s_sig); - first_cell->setParam("\\S_WIDTH", GetSize(s_sig)); + first_cell->setParam("\\S_WIDTH", GetSize(s_sig)); first_cell->setPort("\\Y", last_cell->getPort("\\Y")); cursor += cases; -- cgit v1.2.3 From dc7b8c4b942f9d9bc61a87a81291244d0b73843b Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 12:56:34 -0700 Subject: More cleanup --- passes/opt/muxpack.cc | 35 ++++++++++++++++++++--------------- 1 file changed, 20 insertions(+), 15 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index cb13a45b0..ae4b67db2 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -37,6 +37,7 @@ struct MuxpackWorker dict sig_chain_prev; pool sigbit_with_non_chain_users; pool chain_start_cells; + pool candidate_cells; void make_sig_chain_next_prev() { @@ -59,14 +60,18 @@ struct MuxpackWorker if (sig_chain_next.count(a_sig)) for (auto a_bit : a_sig.bits()) sigbit_with_non_chain_users.insert(a_bit); - else + else { sig_chain_next[a_sig] = cell; + candidate_cells.insert(cell); + } if (sig_chain_next.count(b_sig)) for (auto b_bit : b_sig.bits()) sigbit_with_non_chain_users.insert(b_bit); - else + else { sig_chain_next[b_sig] = cell; + candidate_cells.insert(cell); + } sig_chain_prev[y_sig] = cell; continue; @@ -81,35 +86,34 @@ struct MuxpackWorker void find_chain_start_cells() { - for (auto it : sig_chain_next) + for (auto cell : candidate_cells) { - SigSpec next_sig = it.second->getPort("\\A"); + SigSpec next_sig = cell->getPort("\\A"); if (sig_chain_prev.count(next_sig) == 0) { - next_sig = it.second->getPort("\\B"); + next_sig = cell->getPort("\\B"); if (sig_chain_prev.count(next_sig) == 0) - next_sig = SigSpec(); - } - - for (auto bit : next_sig.bits()) - if (sigbit_with_non_chain_users.count(bit)) goto start_cell; + } - if (!next_sig.empty()) { + for (auto bit : next_sig.bits()) + if (sigbit_with_non_chain_users.count(bit)) + goto start_cell; + Cell *c1 = sig_chain_prev.at(next_sig); - Cell *c2 = it.second; + Cell *c2 = cell; if (c1->type != c2->type) goto start_cell; if (c1->parameters != c2->parameters) goto start_cell; - - continue; } + continue; + start_cell: - chain_start_cells.insert(it.second); + chain_start_cells.insert(cell); } } @@ -197,6 +201,7 @@ struct MuxpackWorker sig_chain_next.clear(); sig_chain_prev.clear(); chain_start_cells.clear(); + candidate_cells.clear(); } MuxpackWorker(Module *module) : -- cgit v1.2.3 From ccdf989025e57da7dfd5ab609676ebe3cfb2c2d6 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 13:51:22 -0700 Subject: Support cascading $pmux.A with $mux.A and $mux.B --- passes/opt/muxpack.cc | 42 +++++++++++++++++++++++++----------------- 1 file changed, 25 insertions(+), 17 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index ae4b67db2..f9e5c8f09 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -51,10 +51,12 @@ struct MuxpackWorker for (auto cell : module->cells()) { - if (cell->type.in("$mux") && !cell->get_bool_attribute("\\keep")) + if (cell->type.in("$mux", "$pmux") && !cell->get_bool_attribute("\\keep")) { SigSpec a_sig = sigmap(cell->getPort("\\A")); - SigSpec b_sig = sigmap(cell->getPort("\\B")); + SigSpec b_sig; + if (cell->type == "$mux") + b_sig = sigmap(cell->getPort("\\B")); SigSpec y_sig = sigmap(cell->getPort("\\Y")); if (sig_chain_next.count(a_sig)) @@ -65,12 +67,14 @@ struct MuxpackWorker candidate_cells.insert(cell); } - if (sig_chain_next.count(b_sig)) - for (auto b_bit : b_sig.bits()) - sigbit_with_non_chain_users.insert(b_bit); - else { - sig_chain_next[b_sig] = cell; - candidate_cells.insert(cell); + if (!b_sig.empty()) { + if (sig_chain_next.count(b_sig)) + for (auto b_bit : b_sig.bits()) + sigbit_with_non_chain_users.insert(b_bit); + else { + sig_chain_next[b_sig] = cell; + candidate_cells.insert(cell); + } } sig_chain_prev[y_sig] = cell; @@ -88,10 +92,16 @@ struct MuxpackWorker { for (auto cell : candidate_cells) { + log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); + SigSpec next_sig = cell->getPort("\\A"); if (sig_chain_prev.count(next_sig) == 0) { - next_sig = cell->getPort("\\B"); - if (sig_chain_prev.count(next_sig) == 0) + if (cell->type == "$mux") { + next_sig = cell->getPort("\\B"); + if (sig_chain_prev.count(next_sig) == 0) + goto start_cell; + } + else goto start_cell; } @@ -103,10 +113,7 @@ struct MuxpackWorker Cell *c1 = sig_chain_prev.at(next_sig); Cell *c2 = cell; - if (c1->type != c2->type) - goto start_cell; - - if (c1->parameters != c2->parameters) + if (c1->getParam("\\WIDTH") != c2->getParam("\\WIDTH")) goto start_cell; } @@ -220,15 +227,16 @@ struct MuxpackWorker }; struct MuxpackPass : public Pass { - MuxpackPass() : Pass("muxpack", "$mux cell cascades to $pmux") { } + MuxpackPass() : Pass("muxpack", "$mux/$pmux cascades to $pmux") { } void help() YS_OVERRIDE { // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| log("\n"); log(" muxpack [selection]\n"); log("\n"); - log("This pass converts cascaded chains of $mux cells (e.g. those created by if-else\n"); - log("constructs) into $pmux cells.\n"); + log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n"); + log("constructs) and $mux cells (e.g. those created by if-else constructs) into \n"); + log("into $pmux cells.\n"); log("\n"); } void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE -- cgit v1.2.3 From 5c277c6325b78bfe18cf294b63ea69ff272e69c5 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 6 Jun 2019 14:21:34 -0700 Subject: Fix and test for balanced case --- passes/opt/muxpack.cc | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index f9e5c8f09..8c4db4e4d 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -94,23 +94,27 @@ struct MuxpackWorker { log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); - SigSpec next_sig = cell->getPort("\\A"); - if (sig_chain_prev.count(next_sig) == 0) { - if (cell->type == "$mux") { - next_sig = cell->getPort("\\B"); - if (sig_chain_prev.count(next_sig) == 0) - goto start_cell; - } - else + SigSpec a_sig = cell->getPort("\\A"); + if (cell->type == "$mux") { + SigSpec b_sig = cell->getPort("\\B"); + if (sig_chain_prev.count(a_sig) + sig_chain_prev.count(b_sig) != 1) + goto start_cell; + + if (!sig_chain_prev.count(a_sig)) + a_sig = b_sig; + } + else if (cell->type == "$pmux") { + if (!sig_chain_prev.count(a_sig)) goto start_cell; } + else log_abort(); { - for (auto bit : next_sig.bits()) + for (auto bit : a_sig.bits()) if (sigbit_with_non_chain_users.count(bit)) goto start_cell; - Cell *c1 = sig_chain_prev.at(next_sig); + Cell *c1 = sig_chain_prev.at(a_sig); Cell *c2 = cell; if (c1->getParam("\\WIDTH") != c2->getParam("\\WIDTH")) -- cgit v1.2.3 From 5ab59cd59ee90abc4b6991486854dbe4c3f4d0a4 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 7 Jun 2019 11:36:19 -0700 Subject: Resolve @cliffordwolf comment on sigmap --- passes/opt/muxpack.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 8c4db4e4d..b060389e3 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -94,9 +94,9 @@ struct MuxpackWorker { log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); - SigSpec a_sig = cell->getPort("\\A"); + SigSpec a_sig = sigmap(cell->getPort("\\A")); if (cell->type == "$mux") { - SigSpec b_sig = cell->getPort("\\B"); + SigSpec b_sig = sigmap(cell->getPort("\\B")); if (sig_chain_prev.count(a_sig) + sig_chain_prev.count(b_sig) != 1) goto start_cell; -- cgit v1.2.3 From 887df8914c64220b9f306b7d21f199fa247224fd Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 7 Jun 2019 11:37:52 -0700 Subject: Resolve @cliffordwolf comment on redundant check --- passes/opt/muxpack.cc | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index b060389e3..15a646e2e 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -109,17 +109,9 @@ struct MuxpackWorker } else log_abort(); - { - for (auto bit : a_sig.bits()) - if (sigbit_with_non_chain_users.count(bit)) - goto start_cell; - - Cell *c1 = sig_chain_prev.at(a_sig); - Cell *c2 = cell; - - if (c1->getParam("\\WIDTH") != c2->getParam("\\WIDTH")) + for (auto bit : a_sig.bits()) + if (sigbit_with_non_chain_users.count(bit)) goto start_cell; - } continue; -- cgit v1.2.3 From 9b408838f191bb0390b6edff55770cab8e8ca15d Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 7 Jun 2019 14:18:17 -0700 Subject: Add ExclusiveDatabase to check exclusive $eq/$logic_not cell results --- passes/opt/muxpack.cc | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 64 insertions(+), 1 deletion(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 15a646e2e..0cf9e0e30 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -24,6 +24,58 @@ USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN +struct ExclusiveDatabase +{ + Module *module; + const SigMap &sigmap; + + dict sig_cmp_prev; + dict> sig_exclusive; + + ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap) + { + SigSpec a_port, b_port, y_port; + for (auto cell : module->cells()) { + if (cell->type == "$eq") { + a_port = sigmap(cell->getPort("\\A")); + b_port = sigmap(cell->getPort("\\B")); + if (!b_port.is_fully_const()) { + if (!a_port.is_fully_const()) + continue; + std::swap(a_port, b_port); + } + y_port = sigmap(cell->getPort("\\Y")); + } + else if (cell->type == "$logic_not") { + a_port = sigmap(cell->getPort("\\A")); + b_port = Const(RTLIL::S0, GetSize(a_port)); + y_port = sigmap(cell->getPort("\\Y")); + } + else continue; + + auto r = sig_exclusive[a_port].insert(b_port.as_const()); + if (!r.second) + continue; + sig_cmp_prev[y_port] = a_port; + } + } + + bool query(const SigSpec& sig1, const SigSpec& sig2) const + { + auto it = sig_cmp_prev.find(sig1); + if (it == sig_cmp_prev.end()) + return false; + + auto jt = sig_cmp_prev.find(sig2); + if (jt == sig_cmp_prev.end()) + return false; + + log("query = %s %s\n", log_signal(it->second), log_signal(jt->second)); + return it->second == jt->second; + } +}; + + struct MuxpackWorker { Module *module; @@ -39,6 +91,8 @@ struct MuxpackWorker pool chain_start_cells; pool candidate_cells; + ExclusiveDatabase excl_db; + void make_sig_chain_next_prev() { for (auto wire : module->wires()) @@ -90,6 +144,7 @@ struct MuxpackWorker void find_chain_start_cells() { + Cell* first_cell = nullptr; for (auto cell : candidate_cells) { log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); @@ -102,6 +157,13 @@ struct MuxpackWorker if (!sig_chain_prev.count(a_sig)) a_sig = b_sig; + + if (first_cell) { + SigSpec s_sig = sigmap(cell->getPort("\\S")); + SigSpec prev_s_sig = sigmap(first_cell->getPort("\\S")); + if (!excl_db.query(prev_s_sig, s_sig)) + goto start_cell; + } } else if (cell->type == "$pmux") { if (!sig_chain_prev.count(a_sig)) @@ -117,6 +179,7 @@ struct MuxpackWorker start_cell: chain_start_cells.insert(cell); + first_cell = cell; } } @@ -208,7 +271,7 @@ struct MuxpackWorker } MuxpackWorker(Module *module) : - module(module), sigmap(module), mux_count(0), pmux_count(0) + module(module), sigmap(module), mux_count(0), pmux_count(0), excl_db(module, sigmap) { make_sig_chain_next_prev(); find_chain_start_cells(); -- cgit v1.2.3 From ba52d9b4716b287b0a469597b748f9859e897329 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 7 Jun 2019 15:34:16 -0700 Subject: Extend ExclusiveDatabase to query SigSpec-s (for $pmux) --- passes/opt/muxpack.cc | 46 +++++++++++++++++++++++++++------------------- 1 file changed, 27 insertions(+), 19 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 0cf9e0e30..4b02df394 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -29,7 +29,7 @@ struct ExclusiveDatabase Module *module; const SigMap &sigmap; - dict sig_cmp_prev; + dict sig_cmp_prev; dict> sig_exclusive; ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap) @@ -62,16 +62,23 @@ struct ExclusiveDatabase bool query(const SigSpec& sig1, const SigSpec& sig2) const { - auto it = sig_cmp_prev.find(sig1); - if (it == sig_cmp_prev.end()) - return false; - - auto jt = sig_cmp_prev.find(sig2); - if (jt == sig_cmp_prev.end()) - return false; + // FIXME: O(N) + for (auto bit1 : sig1.bits()) { + auto it = sig_cmp_prev.find(bit1); + if (it == sig_cmp_prev.end()) + return false; + + for (auto bit2 : sig2.bits()) { + auto jt = sig_cmp_prev.find(bit2); + if (jt == sig_cmp_prev.end()) + return false; + + if (it->second != jt->second) + return false; + } + } - log("query = %s %s\n", log_signal(it->second), log_signal(jt->second)); - return it->second == jt->second; + return true; } }; @@ -144,7 +151,6 @@ struct MuxpackWorker void find_chain_start_cells() { - Cell* first_cell = nullptr; for (auto cell : candidate_cells) { log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); @@ -157,13 +163,6 @@ struct MuxpackWorker if (!sig_chain_prev.count(a_sig)) a_sig = b_sig; - - if (first_cell) { - SigSpec s_sig = sigmap(cell->getPort("\\S")); - SigSpec prev_s_sig = sigmap(first_cell->getPort("\\S")); - if (!excl_db.query(prev_s_sig, s_sig)) - goto start_cell; - } } else if (cell->type == "$pmux") { if (!sig_chain_prev.count(a_sig)) @@ -175,11 +174,19 @@ struct MuxpackWorker if (sigbit_with_non_chain_users.count(bit)) goto start_cell; + { + Cell *prev_cell = sig_chain_prev.at(a_sig); + log_assert(prev_cell); + SigSpec s_sig = sigmap(cell->getPort("\\S")); + SigSpec next_s_sig = sigmap(prev_cell->getPort("\\S")); + if (!excl_db.query(s_sig, next_s_sig)) + goto start_cell; + } + continue; start_cell: chain_start_cells.insert(cell); - first_cell = cell; } } @@ -243,6 +250,7 @@ struct MuxpackWorker s_sig.append(cursor_cell->getPort("\\S")); } else { + log_assert(cursor_cell->type == "$mux"); b_sig.append(cursor_cell->getPort("\\A")); s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S"))); } -- cgit v1.2.3 From f705f6a0b5d19d38cf41ba5f782847de54110463 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 7 Jun 2019 15:39:12 -0700 Subject: Comment O(N) -> O(N^2) --- passes/opt/muxpack.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 4b02df394..f01d5474d 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -62,7 +62,7 @@ struct ExclusiveDatabase bool query(const SigSpec& sig1, const SigSpec& sig2) const { - // FIXME: O(N) + // FIXME: O(N^2) for (auto bit1 : sig1.bits()) { auto it = sig_cmp_prev.find(bit1); if (it == sig_cmp_prev.end()) -- cgit v1.2.3 From 5b999ae68decef5646ef0ccac53463f22fe18d8f Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 10 Jun 2019 10:32:19 -0700 Subject: Elaborate muxpack doc --- passes/opt/muxpack.cc | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index f01d5474d..b6f3313bf 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -302,8 +302,12 @@ struct MuxpackPass : public Pass { log(" muxpack [selection]\n"); log("\n"); log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n"); - log("constructs) and $mux cells (e.g. those created by if-else constructs) into \n"); - log("into $pmux cells.\n"); + log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n"); + log("$pmux cells.\n"); + log("\n"); + log("This optimisation is conservative --- it will only pack $mux or $pmux cells with\n"); + log("other such cells if it can be certain that the select lines are mutually\n"); + log("exclusive.\n"); log("\n"); } void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE -- cgit v1.2.3 From 641b86d25f5baa898bf5fca3d1a8f2fd4f5954e6 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 21 Jun 2019 11:45:31 -0700 Subject: Fix up ExclusiveDatabase with @cliffordwolf's help --- passes/opt/muxpack.cc | 69 +++++++++++++++++++++++++-------------------------- 1 file changed, 34 insertions(+), 35 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index b6f3313bf..ae4f7ba9c 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -29,54 +29,53 @@ struct ExclusiveDatabase Module *module; const SigMap &sigmap; - dict sig_cmp_prev; - dict> sig_exclusive; + dict> sig_cmp_prev; ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap) { - SigSpec a_port, b_port, y_port; + SigSpec const_sig, nonconst_sig, y_port; for (auto cell : module->cells()) { if (cell->type == "$eq") { - a_port = sigmap(cell->getPort("\\A")); - b_port = sigmap(cell->getPort("\\B")); - if (!b_port.is_fully_const()) { - if (!a_port.is_fully_const()) + nonconst_sig = sigmap(cell->getPort("\\A")); + const_sig = sigmap(cell->getPort("\\B")); + if (!const_sig.is_fully_const()) { + if (!nonconst_sig.is_fully_const()) continue; - std::swap(a_port, b_port); + std::swap(nonconst_sig, const_sig); } y_port = sigmap(cell->getPort("\\Y")); } else if (cell->type == "$logic_not") { - a_port = sigmap(cell->getPort("\\A")); - b_port = Const(RTLIL::S0, GetSize(a_port)); + nonconst_sig = sigmap(cell->getPort("\\A")); + const_sig = Const(RTLIL::S0, GetSize(nonconst_sig)); y_port = sigmap(cell->getPort("\\Y")); } else continue; - auto r = sig_exclusive[a_port].insert(b_port.as_const()); - if (!r.second) - continue; - sig_cmp_prev[y_port] = a_port; - } - } + log_assert(!nonconst_sig.empty()); + log_assert(!const_sig.empty()); + sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const()); + } + } - bool query(const SigSpec& sig1, const SigSpec& sig2) const - { - // FIXME: O(N^2) - for (auto bit1 : sig1.bits()) { - auto it = sig_cmp_prev.find(bit1); - if (it == sig_cmp_prev.end()) - return false; - - for (auto bit2 : sig2.bits()) { - auto jt = sig_cmp_prev.find(bit2); - if (jt == sig_cmp_prev.end()) - return false; - - if (it->second != jt->second) - return false; - } - } + bool query(const SigSpec &sig) const + { + SigSpec nonconst_sig; + pool const_values; + + for (auto bit : sig.bits()) { + auto it = sig_cmp_prev.find(bit); + if (it == sig_cmp_prev.end()) + return false; + + if (nonconst_sig.empty()) + nonconst_sig = it->second.first; + else if (nonconst_sig != it->second.first) + return false; + + if (!const_values.insert(it->second.second).second) + return false; + } return true; } @@ -178,8 +177,8 @@ struct MuxpackWorker Cell *prev_cell = sig_chain_prev.at(a_sig); log_assert(prev_cell); SigSpec s_sig = sigmap(cell->getPort("\\S")); - SigSpec next_s_sig = sigmap(prev_cell->getPort("\\S")); - if (!excl_db.query(s_sig, next_s_sig)) + s_sig.append(sigmap(prev_cell->getPort("\\S"))); + if (!excl_db.query(s_sig)) goto start_cell; } -- cgit v1.2.3 From d89d663c92853fcd7f9d75b392ec4133ba2f1d89 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 21 Jun 2019 11:52:28 -0700 Subject: Add doc --- passes/opt/muxpack.cc | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index ae4f7ba9c..c8b226c78 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -304,9 +304,9 @@ struct MuxpackPass : public Pass { log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n"); log("$pmux cells.\n"); log("\n"); - log("This optimisation is conservative --- it will only pack $mux or $pmux cells with\n"); - log("other such cells if it can be certain that the select lines are mutually\n"); - log("exclusive.\n"); + log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n"); + log("whose select lines are driven by '$eq' cells with other such cells if it can be\n"); + log("certain that their select inputs are mutually exclusive.\n"); log("\n"); } void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE -- cgit v1.2.3 From 15535112b7b4caa1da75274397c5a3ba885a7349 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 21 Jun 2019 11:52:51 -0700 Subject: Fix spacing --- passes/opt/muxpack.cc | 48 ++++++++++++++++++++++++------------------------ 1 file changed, 24 insertions(+), 24 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index c8b226c78..4468e8734 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -52,30 +52,30 @@ struct ExclusiveDatabase } else continue; - log_assert(!nonconst_sig.empty()); - log_assert(!const_sig.empty()); - sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const()); - } - } - - bool query(const SigSpec &sig) const - { - SigSpec nonconst_sig; - pool const_values; - - for (auto bit : sig.bits()) { - auto it = sig_cmp_prev.find(bit); - if (it == sig_cmp_prev.end()) - return false; - - if (nonconst_sig.empty()) - nonconst_sig = it->second.first; - else if (nonconst_sig != it->second.first) - return false; - - if (!const_values.insert(it->second.second).second) - return false; - } + log_assert(!nonconst_sig.empty()); + log_assert(!const_sig.empty()); + sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const()); + } + } + + bool query(const SigSpec &sig) const + { + SigSpec nonconst_sig; + pool const_values; + + for (auto bit : sig.bits()) { + auto it = sig_cmp_prev.find(bit); + if (it == sig_cmp_prev.end()) + return false; + + if (nonconst_sig.empty()) + nonconst_sig = it->second.first; + else if (nonconst_sig != it->second.first) + return false; + + if (!const_values.insert(it->second.second).second) + return false; + } return true; } -- cgit v1.2.3 From 545cfbbe0dcc36f18dce6429498f4d87112879e2 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 21 Jun 2019 12:31:14 -0700 Subject: Cope with $reduce_or common in case --- passes/opt/muxpack.cc | 42 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 37 insertions(+), 5 deletions(-) (limited to 'passes/opt/muxpack.cc') diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc index 4468e8734..6697d6ca1 100644 --- a/passes/opt/muxpack.cc +++ b/passes/opt/muxpack.cc @@ -29,11 +29,13 @@ struct ExclusiveDatabase Module *module; const SigMap &sigmap; - dict> sig_cmp_prev; + dict>> sig_cmp_prev; ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap) { - SigSpec const_sig, nonconst_sig, y_port; + SigSpec const_sig, nonconst_sig; + SigBit y_port; + pool reduce_or; for (auto cell : module->cells()) { if (cell->type == "$eq") { nonconst_sig = sigmap(cell->getPort("\\A")); @@ -50,11 +52,40 @@ struct ExclusiveDatabase const_sig = Const(RTLIL::S0, GetSize(nonconst_sig)); y_port = sigmap(cell->getPort("\\Y")); } + else if (cell->type == "$reduce_or") { + reduce_or.insert(cell); + continue; + } else continue; log_assert(!nonconst_sig.empty()); log_assert(!const_sig.empty()); - sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const()); + sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::vector{const_sig.as_const()}); + } + + for (auto cell : reduce_or) { + nonconst_sig = SigSpec(); + std::vector values; + SigSpec a_port = sigmap(cell->getPort("\\A")); + for (auto bit : a_port) { + auto it = sig_cmp_prev.find(bit); + if (it == sig_cmp_prev.end()) { + nonconst_sig = SigSpec(); + break; + } + if (nonconst_sig.empty()) + nonconst_sig = it->second.first; + else if (nonconst_sig != it->second.first) { + nonconst_sig = SigSpec(); + break; + } + for (auto value : it->second.second) + values.push_back(value); + } + if (nonconst_sig.empty()) + continue; + y_port = sigmap(cell->getPort("\\Y")); + sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::move(values)); } } @@ -73,8 +104,9 @@ struct ExclusiveDatabase else if (nonconst_sig != it->second.first) return false; - if (!const_values.insert(it->second.second).second) - return false; + for (auto value : it->second.second) + if (!const_values.insert(value).second) + return false; } return true; -- cgit v1.2.3