diff options
Diffstat (limited to 'passes/opt')
-rw-r--r-- | passes/opt/Makefile.inc | 1 | ||||
-rw-r--r-- | passes/opt/muxpack.cc | 368 | ||||
-rw-r--r-- | passes/opt/opt.cc | 8 | ||||
-rw-r--r-- | passes/opt/opt_clean.cc | 6 | ||||
-rw-r--r-- | passes/opt/opt_rmdff.cc | 109 | ||||
-rw-r--r-- | passes/opt/pmux2shiftx.cc | 14 |
6 files changed, 489 insertions, 17 deletions
diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc index 337fee9e4..ea3646330 100644 --- a/passes/opt/Makefile.inc +++ b/passes/opt/Makefile.inc @@ -14,5 +14,6 @@ OBJS += passes/opt/opt_demorgan.o OBJS += passes/opt/rmports.o OBJS += passes/opt/opt_lut.o OBJS += passes/opt/pmux2shiftx.o +OBJS += passes/opt/muxpack.o endif diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc new file mode 100644 index 000000000..6697d6ca1 --- /dev/null +++ b/passes/opt/muxpack.cc @@ -0,0 +1,368 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * 2019 Eddie Hung <eddie@fpgeh.com> + * + * 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 ExclusiveDatabase +{ + Module *module; + const SigMap &sigmap; + + dict<SigBit, std::pair<SigSpec,std::vector<Const>>> sig_cmp_prev; + + ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap) + { + SigSpec const_sig, nonconst_sig; + SigBit y_port; + pool<Cell*> reduce_or; + for (auto cell : module->cells()) { + if (cell->type == "$eq") { + 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(nonconst_sig, const_sig); + } + y_port = sigmap(cell->getPort("\\Y")); + } + else if (cell->type == "$logic_not") { + nonconst_sig = sigmap(cell->getPort("\\A")); + 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,std::vector<Const>{const_sig.as_const()}); + } + + for (auto cell : reduce_or) { + nonconst_sig = SigSpec(); + std::vector<Const> 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)); + } + } + + bool query(const SigSpec &sig) const + { + SigSpec nonconst_sig; + pool<Const> 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; + + for (auto value : it->second.second) + if (!const_values.insert(value).second) + return false; + } + + return true; + } +}; + + +struct MuxpackWorker +{ + Module *module; + SigMap sigmap; + + int mux_count, pmux_count; + + pool<Cell*> remove_cells; + + dict<SigSpec, Cell*> sig_chain_next; + dict<SigSpec, Cell*> sig_chain_prev; + pool<SigBit> sigbit_with_non_chain_users; + pool<Cell*> chain_start_cells; + pool<Cell*> candidate_cells; + + ExclusiveDatabase excl_db; + + 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", "$pmux") && !cell->get_bool_attribute("\\keep")) + { + SigSpec a_sig = sigmap(cell->getPort("\\A")); + 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)) + for (auto a_bit : a_sig.bits()) + sigbit_with_non_chain_users.insert(a_bit); + else { + sig_chain_next[a_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; + 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 cell : candidate_cells) + { + log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type)); + + SigSpec a_sig = sigmap(cell->getPort("\\A")); + if (cell->type == "$mux") { + SigSpec b_sig = sigmap(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 : a_sig.bits()) + 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")); + s_sig.append(sigmap(prev_cell->getPort("\\S"))); + if (!excl_db.query(s_sig)) + goto start_cell; + } + + continue; + + start_cell: + chain_start_cells.insert(cell); + } + } + + vector<Cell*> create_chain(Cell *start_cell) + { + vector<Cell*> 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<Cell*> &chain) + { + if (GetSize(chain) < 2) + return; + + int cursor = 0; + while (cursor < GetSize(chain)) + { + int cases = GetSize(chain) - cursor; + + Cell *first_cell = chain[cursor]; + dict<int, SigBit> 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 { + log_assert(cursor_cell->type == "$mux"); + 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(); + candidate_cells.clear(); + } + + MuxpackWorker(Module *module) : + module(module), sigmap(module), mux_count(0), pmux_count(0), excl_db(module, sigmap) + { + make_sig_chain_next_prev(); + find_chain_start_cells(); + + for (auto c : chain_start_cells) { + vector<Cell*> chain = create_chain(c); + process_chain(chain); + } + + cleanup(); + } +}; + +struct MuxpackPass : public Pass { + 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 $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("$pmux cells.\n"); + log("\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<std::string> 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 diff --git a/passes/opt/opt.cc b/passes/opt/opt.cc index a4aca2fee..e9a43e0f3 100644 --- a/passes/opt/opt.cc +++ b/passes/opt/opt.cc @@ -44,7 +44,7 @@ struct OptPass : public Pass { log(" opt_muxtree\n"); log(" opt_reduce [-fine] [-full]\n"); log(" opt_merge [-share_all]\n"); - log(" opt_rmdff [-keepdc]\n"); + log(" opt_rmdff [-keepdc] [-sat]\n"); log(" opt_clean [-purge]\n"); log(" opt_expr [-mux_undef] [-mux_bool] [-undriven] [-clkinv] [-fine] [-full] [-keepdc]\n"); log(" while <changed design>\n"); @@ -54,7 +54,7 @@ struct OptPass : public Pass { log(" do\n"); log(" opt_expr [-mux_undef] [-mux_bool] [-undriven] [-clkinv] [-fine] [-full] [-keepdc]\n"); log(" opt_merge [-share_all]\n"); - log(" opt_rmdff [-keepdc]\n"); + log(" opt_rmdff [-keepdc] [-sat]\n"); log(" opt_clean [-purge]\n"); log(" while <changed design in opt_rmdff>\n"); log("\n"); @@ -112,6 +112,10 @@ struct OptPass : public Pass { opt_rmdff_args += " -keepdc"; continue; } + if (args[argidx] == "-sat") { + opt_rmdff_args += " -sat"; + continue; + } if (args[argidx] == "-share_all") { opt_merge_args += " -share_all"; continue; diff --git a/passes/opt/opt_clean.cc b/passes/opt/opt_clean.cc index cfb0f788a..a8a8e0bc7 100644 --- a/passes/opt/opt_clean.cc +++ b/passes/opt/opt_clean.cc @@ -326,8 +326,8 @@ bool rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbos if (wire->port_id != 0 || wire->get_bool_attribute("\\keep") || !initval.is_fully_undef()) { // do not delete anything with "keep" or module ports or initialized wires } else - if (!purge_mode && check_public_name(wire->name)) { - // do not get rid of public names unless in purge mode + if (!purge_mode && check_public_name(wire->name) && (raw_used_signals.check_any(s1) || used_signals.check_any(s2) || s1 != s2)) { + // do not get rid of public names unless in purge mode or if the wire is entirely unused, not even aliased } else if (!raw_used_signals.check_any(s1)) { // delete wires that aren't used by anything directly @@ -480,7 +480,7 @@ void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose, bool std::vector<RTLIL::Cell*> delcells; for (auto cell : module->cells()) - if (cell->type.in("$pos", "$_BUF_")) { + if (cell->type.in("$pos", "$_BUF_") && !cell->has_keep_attr()) { bool is_signed = cell->type == "$pos" && cell->getParam("\\A_SIGNED").as_bool(); RTLIL::SigSpec a = cell->getPort("\\A"); RTLIL::SigSpec y = cell->getPort("\\Y"); diff --git a/passes/opt/opt_rmdff.cc b/passes/opt/opt_rmdff.cc index eeb992a3e..be6ac2d30 100644 --- a/passes/opt/opt_rmdff.cc +++ b/passes/opt/opt_rmdff.cc @@ -17,19 +17,24 @@ * */ +#include "kernel/log.h" #include "kernel/register.h" +#include "kernel/rtlil.h" +#include "kernel/satgen.h" #include "kernel/sigtools.h" -#include "kernel/log.h" -#include <stdlib.h> #include <stdio.h> +#include <stdlib.h> USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN SigMap assign_map, dff_init_map; SigSet<RTLIL::Cell*> mux_drivers; +dict<SigBit, RTLIL::Cell*> bit2driver; dict<SigBit, pool<SigBit>> init_attributes; + bool keepdc; +bool sat; void remove_init_attr(SigSpec sig) { @@ -452,12 +457,84 @@ bool handle_dff(RTLIL::Module *mod, RTLIL::Cell *dff) dff->unsetPort("\\E"); } + if (sat && has_init && (!sig_r.size() || val_init == val_rv)) + { + bool removed_sigbits = false; + + ezSatPtr ez; + SatGen satgen(ez.get(), &assign_map); + pool<Cell*> sat_cells; + + std::function<void(Cell*)> sat_import_cell = [&](Cell *c) { + if (!sat_cells.insert(c).second) + return; + if (!satgen.importCell(c)) + return; + for (auto &conn : c->connections()) { + if (!c->input(conn.first)) + continue; + for (auto bit : assign_map(conn.second)) + if (bit2driver.count(bit)) + sat_import_cell(bit2driver.at(bit)); + } + }; + + // For each register bit, try to prove that it cannot change from the initial value. If so, remove it + for (int position = 0; position < GetSize(sig_d); position += 1) { + RTLIL::SigBit q_sigbit = sig_q[position]; + RTLIL::SigBit d_sigbit = sig_d[position]; + + if ((!q_sigbit.wire) || (!d_sigbit.wire)) + continue; + + if (!bit2driver.count(d_sigbit)) + continue; + + sat_import_cell(bit2driver.at(d_sigbit)); + + RTLIL::State sigbit_init_val = val_init[position]; + if (sigbit_init_val != State::S0 && sigbit_init_val != State::S1) + continue; + + int init_sat_pi = satgen.importSigSpec(sigbit_init_val).front(); + int q_sat_pi = satgen.importSigBit(q_sigbit); + int d_sat_pi = satgen.importSigBit(d_sigbit); + + // Try to find out whether the register bit can change under some circumstances + bool counter_example_found = ez->solve(ez->IFF(q_sat_pi, init_sat_pi), ez->NOT(ez->IFF(d_sat_pi, init_sat_pi))); + + // If the register bit cannot change, we can replace it with a constant + if (!counter_example_found) + { + log("Setting constant %d-bit at position %d on %s (%s) from module %s.\n", sigbit_init_val ? 1 : 0, + position, log_id(dff), log_id(dff->type), log_id(mod)); + + SigSpec tmp = dff->getPort("\\D"); + tmp[position] = sigbit_init_val; + dff->setPort("\\D", tmp); + + removed_sigbits = true; + } + } + + if (removed_sigbits) { + handle_dff(mod, dff); + return true; + } + } + + return false; delete_dff: log("Removing %s (%s) from module %s.\n", log_id(dff), log_id(dff->type), log_id(mod)); remove_init_attr(dff->getPort("\\Q")); mod->remove(dff); + + for (auto &entry : bit2driver) + if (entry.second == dff) + bit2driver.erase(entry.first); + return true; } @@ -467,11 +544,15 @@ struct OptRmdffPass : public Pass { { // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| log("\n"); - log(" opt_rmdff [-keepdc] [selection]\n"); + log(" opt_rmdff [-keepdc] [-sat] [selection]\n"); log("\n"); log("This pass identifies flip-flops with constant inputs and replaces them with\n"); log("a constant driver.\n"); log("\n"); + log(" -sat\n"); + log(" additionally invoke SAT solver to detect and remove flip-flops (with \n"); + log(" non-constant inputs) that can also be replaced with a constant driver\n"); + log("\n"); } void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE { @@ -479,6 +560,7 @@ struct OptRmdffPass : public Pass { log_header(design, "Executing OPT_RMDFF pass (remove dff with constant values).\n"); keepdc = false; + sat = false; size_t argidx; for (argidx = 1; argidx < args.size(); argidx++) { @@ -486,18 +568,22 @@ struct OptRmdffPass : public Pass { keepdc = true; continue; } + if (args[argidx] == "-sat") { + sat = true; + continue; + } break; } extra_args(args, argidx, design); - for (auto module : design->selected_modules()) - { + for (auto module : design->selected_modules()) { pool<SigBit> driven_bits; dict<SigBit, State> init_bits; assign_map.set(module); dff_init_map.set(module); mux_drivers.clear(); + bit2driver.clear(); init_attributes.clear(); for (auto wire : module->wires()) @@ -522,17 +608,21 @@ struct OptRmdffPass : public Pass { driven_bits.insert(bit); } } - mux_drivers.clear(); std::vector<RTLIL::IdString> dff_list; std::vector<RTLIL::IdString> dffsr_list; std::vector<RTLIL::IdString> dlatch_list; for (auto cell : module->cells()) { - for (auto &conn : cell->connections()) - if (cell->output(conn.first) || !cell->known()) - for (auto bit : assign_map(conn.second)) + for (auto &conn : cell->connections()) { + bool is_output = cell->output(conn.first); + if (is_output || !cell->known()) + for (auto bit : assign_map(conn.second)) { + if (is_output) + bit2driver[bit] = cell; driven_bits.insert(bit); + } + } if (cell->type == "$mux" || cell->type == "$pmux") { if (cell->getPort("\\A").size() == cell->getPort("\\B").size()) @@ -604,6 +694,7 @@ struct OptRmdffPass : public Pass { assign_map.clear(); mux_drivers.clear(); + bit2driver.clear(); init_attributes.clear(); if (total_count || total_initdrv) diff --git a/passes/opt/pmux2shiftx.cc b/passes/opt/pmux2shiftx.cc index 29870f510..65d8b8f32 100644 --- a/passes/opt/pmux2shiftx.cc +++ b/passes/opt/pmux2shiftx.cc @@ -221,6 +221,9 @@ struct Pmux2ShiftxPass : public Pass { log(" select strategy for one-hot encoded control signals\n"); log(" default: pmux\n"); log("\n"); + log(" -norange\n"); + log(" disable $sub inference for \"range decoders\"\n"); + log("\n"); } void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE { @@ -230,6 +233,7 @@ struct Pmux2ShiftxPass : public Pass { bool optimize_onehot = true; bool verbose = false; bool verbose_onehot = false; + bool norange = false; log_header(design, "Executing PMUX2SHIFTX pass.\n"); @@ -270,6 +274,10 @@ struct Pmux2ShiftxPass : public Pass { verbose_onehot = true; continue; } + if (args[argidx] == "-norange") { + norange = true; + continue; + } break; } extra_args(args, argidx, design); @@ -559,7 +567,7 @@ struct Pmux2ShiftxPass : public Pass { int this_inv_delta = this_maxval - this_minval; bool this_inv = false; - if (this_delta != this_inv_delta) + if (!norange && this_delta != this_inv_delta) this_inv = this_inv_delta < this_delta; else if (this_maxval != this_inv_maxval) this_inv = this_inv_maxval < this_maxval; @@ -574,7 +582,7 @@ struct Pmux2ShiftxPass : public Pass { if (best_src_col < 0) this_is_better = true; - else if (this_delta != best_delta) + else if (!norange && this_delta != best_delta) this_is_better = this_delta < best_delta; else if (this_maxval != best_maxval) this_is_better = this_maxval < best_maxval; @@ -656,7 +664,7 @@ struct Pmux2ShiftxPass : public Pass { // check density percentages Const offset(State::S0, GetSize(sig)); - if (absolute_density < min_density && range_density >= min_density) + if (!norange && absolute_density < min_density && range_density >= min_density) { offset = Const(min_choice, GetSize(sig)); log(" offset: %s\n", log_signal(offset)); |