diff options
Diffstat (limited to 'passes/opt/opt_lut.cc')
| -rw-r--r-- | passes/opt/opt_lut.cc | 595 |
1 files changed, 595 insertions, 0 deletions
diff --git a/passes/opt/opt_lut.cc b/passes/opt/opt_lut.cc new file mode 100644 index 000000000..c4f278706 --- /dev/null +++ b/passes/opt/opt_lut.cc @@ -0,0 +1,595 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2018 whitequark <whitequark@whitequark.org> + * + * 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" +#include "kernel/modtools.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct OptLutWorker +{ + dict<IdString, dict<int, IdString>> &dlogic; + RTLIL::Module *module; + ModIndex index; + SigMap sigmap; + + pool<RTLIL::Cell*> luts; + dict<RTLIL::Cell*, int> luts_arity; + dict<RTLIL::Cell*, pool<RTLIL::Cell*>> luts_dlogics; + dict<RTLIL::Cell*, pool<int>> luts_dlogic_inputs; + + int eliminated_count = 0, combined_count = 0; + + bool evaluate_lut(RTLIL::Cell *lut, dict<SigBit, bool> inputs) + { + SigSpec lut_input = sigmap(lut->getPort(ID::A)); + int lut_width = lut->getParam(ID(WIDTH)).as_int(); + Const lut_table = lut->getParam(ID(LUT)); + int lut_index = 0; + + for (int i = 0; i < lut_width; i++) + { + SigBit input = sigmap(lut_input[i]); + if (inputs.count(input)) + { + lut_index |= inputs[input] << i; + } + else + { + lut_index |= SigSpec(lut_input[i]).as_bool() << i; + } + } + + return lut_table.extract(lut_index).as_bool(); + } + + void show_stats_by_arity() + { + dict<int, int> arity_counts; + dict<IdString, int> dlogic_counts; + int max_arity = 0; + + for (auto lut_arity : luts_arity) + { + max_arity = max(max_arity, lut_arity.second); + arity_counts[lut_arity.second]++; + } + + for (auto &lut_dlogics : luts_dlogics) + { + for (auto &lut_dlogic : lut_dlogics.second) + { + dlogic_counts[lut_dlogic->type]++; + } + } + + log("Number of LUTs: %8d\n", GetSize(luts)); + for (int arity = 1; arity <= max_arity; arity++) + { + if (arity_counts[arity]) + log(" %d-LUT %16d\n", arity, arity_counts[arity]); + } + for (auto &dlogic_count : dlogic_counts) + { + log(" with %-12s %4d\n", dlogic_count.first.c_str(), dlogic_count.second); + } + } + + OptLutWorker(dict<IdString, dict<int, IdString>> &dlogic, RTLIL::Module *module, int limit) : + dlogic(dlogic), module(module), index(module), sigmap(module) + { + log("Discovering LUTs.\n"); + for (auto cell : module->selected_cells()) + { + if (cell->type == ID($lut)) + { + if (cell->has_keep_attr()) + continue; + SigBit lut_output = cell->getPort(ID::Y); + if (lut_output.wire->get_bool_attribute(ID::keep)) + continue; + + int lut_width = cell->getParam(ID(WIDTH)).as_int(); + SigSpec lut_input = cell->getPort(ID::A); + int lut_arity = 0; + + log_debug("Found $lut\\WIDTH=%d cell %s.%s.\n", lut_width, log_id(module), log_id(cell)); + luts.insert(cell); + + // First, find all dedicated logic we're connected to. This results in an overapproximation + // of such connections. + pool<RTLIL::Cell*> lut_all_dlogics; + for (int i = 0; i < lut_width; i++) + { + SigBit bit = lut_input[i]; + for (auto &port : index.query_ports(bit)) + { + if (dlogic.count(port.cell->type)) + { + auto &dlogic_map = dlogic[port.cell->type]; + if (dlogic_map.count(i)) + { + if (port.port == dlogic_map[i]) + { + lut_all_dlogics.insert(port.cell); + } + } + } + } + } + + // Second, make sure that the connection to dedicated logic is legal. If it is not legal, + // it means one of the two things: + // * The connection is spurious. I.e. this is dedicated logic that will be packed + // with some other LUT, and it just happens to be connected to this LUT as well. + // * The connection is illegal. + // In either of these cases, we don't need to concern ourselves with preserving the connection + // between this LUT and this dedicated logic cell. + pool<RTLIL::Cell*> lut_legal_dlogics; + pool<int> lut_dlogic_inputs; + for (auto lut_dlogic : lut_all_dlogics) + { + auto &dlogic_map = dlogic[lut_dlogic->type]; + bool legal = true; + for (auto &dlogic_conn : dlogic_map) + { + if (lut_width <= dlogic_conn.first) + { + log_debug(" LUT has illegal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic)); + log_debug(" LUT input A[%d] not present.\n", dlogic_conn.first); + legal = false; + break; + } + if (sigmap(lut_input[dlogic_conn.first]) != sigmap(lut_dlogic->getPort(dlogic_conn.second))) + { + log_debug(" LUT has illegal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic)); + log_debug(" LUT input A[%d] (wire %s) not connected to %s port %s (wire %s).\n", dlogic_conn.first, log_signal(lut_input[dlogic_conn.first]), lut_dlogic->type.c_str(), dlogic_conn.second.c_str(), log_signal(lut_dlogic->getPort(dlogic_conn.second))); + legal = false; + break; + } + } + + if (legal) + { + log_debug(" LUT has legal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic)); + lut_legal_dlogics.insert(lut_dlogic); + for (auto &dlogic_conn : dlogic_map) + lut_dlogic_inputs.insert(dlogic_conn.first); + } + } + + // Third, determine LUT arity. An n-wide LUT that has k constant inputs and m inputs shared with dedicated + // logic implements an (n-k-m)-ary function. + for (int i = 0; i < lut_width; i++) + { + SigBit bit = lut_input[i]; + if (bit.wire || lut_dlogic_inputs.count(i)) + lut_arity++; + } + + log_debug(" Cell implements a %d-LUT.\n", lut_arity); + luts_arity[cell] = lut_arity; + luts_dlogics[cell] = lut_legal_dlogics; + luts_dlogic_inputs[cell] = lut_dlogic_inputs; + } + } + show_stats_by_arity(); + + log("\n"); + log("Eliminating LUTs.\n"); + pool<RTLIL::Cell*> worklist = luts; + while (worklist.size()) + { + if (limit == 0) + { + log("Limit reached.\n"); + break; + } + + auto lut = worklist.pop(); + SigSpec lut_input = sigmap(lut->getPort(ID::A)); + pool<int> &lut_dlogic_inputs = luts_dlogic_inputs[lut]; + + vector<SigBit> lut_inputs; + for (auto &bit : lut_input) + { + if (bit.wire) + lut_inputs.push_back(sigmap(bit)); + } + + bool const0_match = true; + bool const1_match = true; + vector<bool> input_matches; + for (size_t i = 0; i < lut_inputs.size(); i++) + input_matches.push_back(true); + + for (int eval = 0; eval < 1 << lut_inputs.size(); eval++) + { + dict<SigBit, bool> eval_inputs; + for (size_t i = 0; i < lut_inputs.size(); i++) + eval_inputs[lut_inputs[i]] = (eval >> i) & 1; + bool value = evaluate_lut(lut, eval_inputs); + if (value != 0) + const0_match = false; + if (value != 1) + const1_match = false; + for (size_t i = 0; i < lut_inputs.size(); i++) + { + if (value != eval_inputs[lut_inputs[i]]) + input_matches[i] = false; + } + } + + int input_match = -1; + for (size_t i = 0; i < lut_inputs.size(); i++) + if (input_matches[i]) + input_match = i; + + if (const0_match || const1_match || input_match != -1) + { + log_debug("Found redundant cell %s.%s.\n", log_id(module), log_id(lut)); + + SigBit value; + if (const0_match) + { + log_debug(" Cell evaluates constant 0.\n"); + value = State::S0; + } + if (const1_match) + { + log_debug(" Cell evaluates constant 1.\n"); + value = State::S1; + } + if (input_match != -1) { + log_debug(" Cell evaluates signal %s.\n", log_signal(lut_inputs[input_match])); + value = lut_inputs[input_match]; + } + + if (lut_dlogic_inputs.size()) + log_debug(" Not eliminating cell (connected to dedicated logic).\n"); + else + { + SigSpec lut_output = lut->getPort(ID::Y); + for (auto &port : index.query_ports(lut_output)) + { + if (port.cell != lut && luts.count(port.cell)) + worklist.insert(port.cell); + } + + module->connect(lut_output, value); + sigmap.add(lut_output, value); + + module->remove(lut); + luts.erase(lut); + luts_arity.erase(lut); + luts_dlogics.erase(lut); + luts_dlogic_inputs.erase(lut); + + eliminated_count++; + if (limit > 0) + limit--; + } + } + } + show_stats_by_arity(); + + log("\n"); + log("Combining LUTs.\n"); + worklist = luts; + while (worklist.size()) + { + if (limit == 0) + { + log("Limit reached.\n"); + break; + } + + auto lutA = worklist.pop(); + SigSpec lutA_input = sigmap(lutA->getPort(ID::A)); + SigSpec lutA_output = sigmap(lutA->getPort(ID::Y)[0]); + int lutA_width = lutA->getParam(ID(WIDTH)).as_int(); + int lutA_arity = luts_arity[lutA]; + pool<int> &lutA_dlogic_inputs = luts_dlogic_inputs[lutA]; + + auto lutA_output_ports = index.query_ports(lutA->getPort(ID::Y)); + if (lutA_output_ports.size() != 2) + continue; + + for (auto &port : lutA_output_ports) + { + if (port.cell == lutA) + continue; + + if (luts.count(port.cell)) + { + auto lutB = port.cell; + SigSpec lutB_input = sigmap(lutB->getPort(ID::A)); + SigSpec lutB_output = sigmap(lutB->getPort(ID::Y)[0]); + int lutB_width = lutB->getParam(ID(WIDTH)).as_int(); + int lutB_arity = luts_arity[lutB]; + pool<int> &lutB_dlogic_inputs = luts_dlogic_inputs[lutB]; + + log_debug("Found %s.%s (cell A) feeding %s.%s (cell B).\n", log_id(module), log_id(lutA), log_id(module), log_id(lutB)); + + if (index.query_is_output(lutA->getPort(ID::Y))) + { + log_debug(" Not combining LUTs (cascade connection feeds module output).\n"); + continue; + } + + pool<SigBit> lutA_inputs; + pool<SigBit> lutB_inputs; + for (auto &bit : lutA_input) + { + if (bit.wire) + lutA_inputs.insert(sigmap(bit)); + } + for (auto &bit : lutB_input) + { + if (bit.wire) + lutB_inputs.insert(sigmap(bit)); + } + + pool<SigBit> common_inputs; + for (auto &bit : lutA_inputs) + { + if (lutB_inputs.count(bit)) + common_inputs.insert(bit); + } + + int lutM_arity = lutA_arity + lutB_arity - 1 - common_inputs.size(); + if (lutA_dlogic_inputs.size()) + log_debug(" Cell A is a %d-LUT with %d dedicated connections. ", lutA_arity, GetSize(lutA_dlogic_inputs)); + else + log_debug(" Cell A is a %d-LUT. ", lutA_arity); + if (lutB_dlogic_inputs.size()) + log_debug("Cell B is a %d-LUT with %d dedicated connections.\n", lutB_arity, GetSize(lutB_dlogic_inputs)); + else + log_debug("Cell B is a %d-LUT.\n", lutB_arity); + log_debug(" Cells share %d input(s) and can be merged into one %d-LUT.\n", GetSize(common_inputs), lutM_arity); + + const int COMBINE_A = 1, COMBINE_B = 2, COMBINE_EITHER = COMBINE_A | COMBINE_B; + int combine_mask = 0; + if (lutM_arity > lutA_width) + log_debug(" Not combining LUTs into cell A (combined LUT wider than cell A).\n"); + else if (lutB_dlogic_inputs.size() > 0) + log_debug(" Not combining LUTs into cell A (cell B is connected to dedicated logic).\n"); + else if (lutB->get_bool_attribute(ID(lut_keep))) + log_debug(" Not combining LUTs into cell A (cell B has attribute \\lut_keep).\n"); + else + combine_mask |= COMBINE_A; + if (lutM_arity > lutB_width) + log_debug(" Not combining LUTs into cell B (combined LUT wider than cell B).\n"); + else if (lutA_dlogic_inputs.size() > 0) + log_debug(" Not combining LUTs into cell B (cell A is connected to dedicated logic).\n"); + else if (lutA->get_bool_attribute(ID(lut_keep))) + log_debug(" Not combining LUTs into cell B (cell A has attribute \\lut_keep).\n"); + else + combine_mask |= COMBINE_B; + + int combine = combine_mask; + if (combine == COMBINE_EITHER) + { + log_debug(" Can combine into either cell.\n"); + if (lutA_arity == 1) + { + log_debug(" Cell A is a buffer or inverter, combining into cell B.\n"); + combine = COMBINE_B; + } + else if (lutB_arity == 1) + { + log_debug(" Cell B is a buffer or inverter, combining into cell A.\n"); + combine = COMBINE_A; + } + else + { + log_debug(" Arbitrarily combining into cell A.\n"); + combine = COMBINE_A; + } + } + + RTLIL::Cell *lutM, *lutR; + pool<SigBit> lutM_inputs, lutR_inputs; + pool<int> lutM_dlogic_inputs; + if (combine == COMBINE_A) + { + log_debug(" Combining LUTs into cell A.\n"); + lutM = lutA; + lutM_inputs = lutA_inputs; + lutM_dlogic_inputs = lutA_dlogic_inputs; + lutR = lutB; + lutR_inputs = lutB_inputs; + } + else if (combine == COMBINE_B) + { + log_debug(" Combining LUTs into cell B.\n"); + lutM = lutB; + lutM_inputs = lutB_inputs; + lutM_dlogic_inputs = lutB_dlogic_inputs; + lutR = lutA; + lutR_inputs = lutA_inputs; + } + else + { + log_debug(" Cannot combine LUTs.\n"); + continue; + } + + pool<SigBit> lutR_unique; + for (auto &bit : lutR_inputs) + { + if (!common_inputs.count(bit) && bit != lutA_output) + lutR_unique.insert(bit); + } + + int lutM_width = lutM->getParam(ID(WIDTH)).as_int(); + SigSpec lutM_input = sigmap(lutM->getPort(ID::A)); + std::vector<SigBit> lutM_new_inputs; + for (int i = 0; i < lutM_width; i++) + { + bool input_unused = false; + if (sigmap(lutM_input[i]) == lutA_output) + input_unused = true; + if (!lutM_input[i].wire && !lutM_dlogic_inputs.count(i)) + input_unused = true; + + if (input_unused && lutR_unique.size()) + { + SigBit new_input = lutR_unique.pop(); + log_debug(" Connecting input %d as %s.\n", i, log_signal(new_input)); + lutM_new_inputs.push_back(new_input); + } + else if (sigmap(lutM_input[i]) == lutA_output) + { + log_debug(" Disconnecting cascade input %d.\n", i); + lutM_new_inputs.push_back(SigBit()); + } + else + { + log_debug(" Leaving input %d as %s.\n", i, log_signal(lutM_input[i])); + lutM_new_inputs.push_back(lutM_input[i]); + } + } + log_assert(lutR_unique.size() == 0); + + RTLIL::Const lutM_new_table(State::Sx, 1 << lutM_width); + for (int eval = 0; eval < 1 << lutM_width; eval++) + { + dict<SigBit, bool> eval_inputs; + for (size_t i = 0; i < lutM_new_inputs.size(); i++) + { + eval_inputs[lutM_new_inputs[i]] = (eval >> i) & 1; + } + eval_inputs[lutA_output] = evaluate_lut(lutA, eval_inputs); + lutM_new_table[eval] = (RTLIL::State) evaluate_lut(lutB, eval_inputs); + } + + log_debug(" Cell A truth table: %s.\n", lutA->getParam(ID(LUT)).as_string().c_str()); + log_debug(" Cell B truth table: %s.\n", lutB->getParam(ID(LUT)).as_string().c_str()); + log_debug(" Merged truth table: %s.\n", lutM_new_table.as_string().c_str()); + + lutM->setParam(ID(LUT), lutM_new_table); + lutM->setPort(ID::A, lutM_new_inputs); + lutM->setPort(ID::Y, lutB_output); + + luts_arity[lutM] = lutM_arity; + luts.erase(lutR); + luts_arity.erase(lutR); + lutR->module->remove(lutR); + + worklist.insert(lutM); + worklist.erase(lutR); + + combined_count++; + if (limit > 0) + limit--; + } + } + } + show_stats_by_arity(); + } +}; + +static void split(std::vector<std::string> &tokens, const std::string &text, char sep) +{ + size_t start = 0, end = 0; + while ((end = text.find(sep, start)) != std::string::npos) { + tokens.push_back(text.substr(start, end - start)); + start = end + 1; + } + tokens.push_back(text.substr(start)); +} + +struct OptLutPass : public Pass { + OptLutPass() : Pass("opt_lut", "optimize LUT cells") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" opt_lut [options] [selection]\n"); + log("\n"); + log("This pass combines cascaded $lut cells with unused inputs.\n"); + log("\n"); + log(" -dlogic <type>:<cell-port>=<LUT-input>[:<cell-port>=<LUT-input>...]\n"); + log(" preserve connections to dedicated logic cell <type> that has ports\n"); + log(" <cell-port> connected to LUT inputs <LUT-input>. this includes\n"); + log(" the case where both LUT and dedicated logic input are connected to\n"); + log(" the same constant.\n"); + log("\n"); + log(" -limit N\n"); + log(" only perform the first N combines, then stop. useful for debugging.\n"); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing OPT_LUT pass (optimize LUTs).\n"); + + dict<IdString, dict<int, IdString>> dlogic; + int limit = -1; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-dlogic" && argidx+1 < args.size()) + { + std::vector<std::string> tokens; + split(tokens, args[++argidx], ':'); + if (tokens.size() < 2) + log_cmd_error("The -dlogic option requires at least one connection.\n"); + IdString type = "\\" + tokens[0]; + for (auto it = tokens.begin() + 1; it != tokens.end(); ++it) { + std::vector<std::string> conn_tokens; + split(conn_tokens, *it, '='); + if (conn_tokens.size() != 2) + log_cmd_error("Invalid format of -dlogic signal mapping.\n"); + IdString logic_port = "\\" + conn_tokens[0]; + int lut_input = atoi(conn_tokens[1].c_str()); + dlogic[type][lut_input] = logic_port; + } + continue; + } + if (args[argidx] == "-limit" && argidx + 1 < args.size()) + { + limit = atoi(args[++argidx].c_str()); + continue; + } + break; + } + extra_args(args, argidx, design); + + int eliminated_count = 0, combined_count = 0; + for (auto module : design->selected_modules()) + { + OptLutWorker worker(dlogic, module, limit - eliminated_count - combined_count); + eliminated_count += worker.eliminated_count; + combined_count += worker.combined_count; + } + if (eliminated_count) + design->scratchpad_set_bool("opt.did_something", true); + if (combined_count) + design->scratchpad_set_bool("opt.did_something", true); + log("\n"); + log("Eliminated %d LUTs.\n", eliminated_count); + log("Combined %d LUTs.\n", combined_count); + } +} OptLutPass; + +PRIVATE_NAMESPACE_END |