From fa310c98f82ce9637034ca2b1de7b04b5d5772d0 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Fri, 11 Aug 2017 00:40:31 -0700 Subject: recover_reduce_core: Initial commit Conflicts: passes/techmap/Makefile.inc --- passes/techmap/Makefile.inc | 1 + passes/techmap/recover_reduce_core.cpp | 109 +++++++++++++++++++++++++++++++++ 2 files changed, 110 insertions(+) create mode 100644 passes/techmap/recover_reduce_core.cpp (limited to 'passes') diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc index ce67b711d..51ed356fe 100644 --- a/passes/techmap/Makefile.inc +++ b/passes/techmap/Makefile.inc @@ -17,6 +17,7 @@ OBJS += passes/techmap/iopadmap.o OBJS += passes/techmap/hilomap.o OBJS += passes/techmap/extract.o OBJS += passes/techmap/extract_fa.o +OBJS += passes/techmap/recover_reduce_core.o OBJS += passes/techmap/alumacc.o OBJS += passes/techmap/dff2dffe.o OBJS += passes/techmap/dffinit.o diff --git a/passes/techmap/recover_reduce_core.cpp b/passes/techmap/recover_reduce_core.cpp new file mode 100644 index 000000000..e6b9ec879 --- /dev/null +++ b/passes/techmap/recover_reduce_core.cpp @@ -0,0 +1,109 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2017 Robert Ou + * + * 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 RecoverReduceCorePass : public Pass { + enum GateType { + And, + Or, + Xor + }; + + RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" recover_reduce_core\n"); + log("\n"); + log("converts gate chains into $reduce_*\n"); + log("\n"); + log("This performs the core step of the recover_reduce command. This step recognizes\n"); + log("chains of gates found by the previous steps and converts these chains into one\n"); + log("logical cell.\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + (void)args; + + for (auto module : design->selected_modules()) + { + SigMap sigmap(module); + + // Index all of the nets in the module + dict sig_to_driver; + dict> sig_to_sink; + for (auto cell : module->selected_cells()) + { + for (auto &conn : cell->connections()) + { + if (cell->output(conn.first)) + for (auto bit : sigmap(conn.second)) + sig_to_driver[bit] = cell; + + if (cell->input(conn.first)) + { + for (auto bit : sigmap(conn.second)) + { + if (sig_to_sink.count(bit) == 0) + sig_to_sink[bit] = pool(); + sig_to_sink[bit].insert(cell); + } + } + } + } + + // Need to check if any wires connect to module ports + pool port_sigs; + for (auto wire : module->selected_wires()) + if (wire->port_input || wire->port_output) + for (auto bit : sigmap(wire)) + port_sigs.insert(bit); + + // Actual logic starts here + pool consumed_cells; + for (auto cell : module->selected_cells()) + { + if (consumed_cells.count(cell)) + continue; + + GateType gt; + + if (cell->type == "$_AND_") + gt = GateType::And; + else if (cell->type == "$_OR_") + gt = GateType::Or; + else if (cell->type == "$_XOR_") + gt = GateType::Xor; + else + continue; + + log("Working on cell %s...\n", cell->name.c_str()); + } + } + } +} RecoverReduceCorePass; + +PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 8b7dc792ee8301af10dcd83798128c1f0f5c43c3 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Fri, 11 Aug 2017 01:48:22 -0700 Subject: recover_reduce_core: Finish implementing the core function --- passes/techmap/recover_reduce_core.cpp | 110 +++++++++++++++++++++++++++++++++ 1 file changed, 110 insertions(+) (limited to 'passes') diff --git a/passes/techmap/recover_reduce_core.cpp b/passes/techmap/recover_reduce_core.cpp index e6b9ec879..dbd61b366 100644 --- a/passes/techmap/recover_reduce_core.cpp +++ b/passes/techmap/recover_reduce_core.cpp @@ -101,7 +101,117 @@ struct RecoverReduceCorePass : public Pass { continue; log("Working on cell %s...\n", cell->name.c_str()); + + // Go all the way to the sink + Cell* head_cell = cell; + Cell* x = cell; + while (true) + { + if (!((x->type == "$_AND_" && gt == GateType::And) || + (x->type == "$_OR_" && gt == GateType::Or) || + (x->type == "$_XOR_" && gt == GateType::Xor))) + break; + + head_cell = x; + + auto y = sigmap(x->getPort("\\Y")); + log_assert(y.size() == 1); + + // Should only continue if there is one fanout back into a cell (not to a port) + if (sig_to_sink[y[0]].size() != 1) + break; + + x = *sig_to_sink[y[0]].begin(); + } + + log(" Head cell is %s\n", head_cell->name.c_str()); + + pool cur_supercell; + std::deque bfs_queue = {head_cell}; + while (bfs_queue.size()) + { + Cell* x = bfs_queue.front(); + bfs_queue.pop_front(); + + cur_supercell.insert(x); + + auto a = sigmap(x->getPort("\\A")); + log_assert(a.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1) + { + Cell* cell_a = sig_to_driver[a[0]]; + if (((cell_a->type == "$_AND_" && gt == GateType::And) || + (cell_a->type == "$_OR_" && gt == GateType::Or) || + (cell_a->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_a); + } + } + + auto b = sigmap(x->getPort("\\B")); + log_assert(b.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1) + { + Cell* cell_b = sig_to_driver[b[0]]; + if (((cell_b->type == "$_AND_" && gt == GateType::And) || + (cell_b->type == "$_OR_" && gt == GateType::Or) || + (cell_b->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_b); + } + } + } + + log(" Cells:\n"); + for (auto x : cur_supercell) + log(" %s\n", x->name.c_str()); + + if (cur_supercell.size() > 1) + { + // Worth it to create reduce cell + log(" Creating $reduce_* cell!\n"); + + pool input_pool; + pool input_pool_intermed; + for (auto x : cur_supercell) + { + input_pool.insert(sigmap(x->getPort("\\A"))[0]); + input_pool.insert(sigmap(x->getPort("\\B"))[0]); + input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]); + } + SigSpec input; + for (auto b : input_pool) + if (input_pool_intermed.count(b) == 0) + input.append_bit(b); + + SigBit output = sigmap(head_cell->getPort("\\Y")[0]); + + auto new_reduce_cell = module->addCell(NEW_ID, + gt == GateType::And ? "$reduce_and" : + gt == GateType::Or ? "$reduce_or" : + gt == GateType::Xor ? "$reduce_xor" : ""); + new_reduce_cell->setParam("\\A_SIGNED", 0); + new_reduce_cell->setParam("\\A_WIDTH", input.size()); + new_reduce_cell->setParam("\\Y_WIDTH", 1); + new_reduce_cell->setPort("\\A", input); + new_reduce_cell->setPort("\\Y", output); + + for (auto x : cur_supercell) + consumed_cells.insert(x); + } } + + // Remove every cell that we've used up + for (auto cell : consumed_cells) + module->remove(cell); } } } RecoverReduceCorePass; -- cgit v1.2.3 From 99dad40ed056e33173be4cb24b476ae0ab28edc7 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Fri, 11 Aug 2017 02:00:33 -0700 Subject: recover_reduce: Add driver script for the $reduce_* recover feature Conflicts: passes/techmap/Makefile.inc --- passes/techmap/Makefile.inc | 1 + passes/techmap/recover_reduce.cpp | 100 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 101 insertions(+) create mode 100644 passes/techmap/recover_reduce.cpp (limited to 'passes') diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc index 51ed356fe..7561369b9 100644 --- a/passes/techmap/Makefile.inc +++ b/passes/techmap/Makefile.inc @@ -17,6 +17,7 @@ OBJS += passes/techmap/iopadmap.o OBJS += passes/techmap/hilomap.o OBJS += passes/techmap/extract.o OBJS += passes/techmap/extract_fa.o +OBJS += passes/techmap/recover_reduce.o OBJS += passes/techmap/recover_reduce_core.o OBJS += passes/techmap/alumacc.o OBJS += passes/techmap/dff2dffe.o diff --git a/passes/techmap/recover_reduce.cpp b/passes/techmap/recover_reduce.cpp new file mode 100644 index 000000000..21ebac532 --- /dev/null +++ b/passes/techmap/recover_reduce.cpp @@ -0,0 +1,100 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2017 Robert Ou + * + * 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" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct RecoverReducePass : public ScriptPass +{ + RecoverReducePass() : ScriptPass("recover_reduce", "recovers $reduce_* from gates") {} + virtual void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" recover_reduce [options]\n"); + log("\n"); + log("recovers $reduce_* from gates\n"); + log("\n"); + log("Reconstructs $reduce_* elements (e.g. larger gates) given a netlist of gates."); + log("This pass is intended to be used as part of a circuit reverse-engineering workflow.\n"); + log("\n"); + log("\n"); + log("The following commands are executed by this command:\n"); + help_script(); + log("\n"); + } + + bool one_pass, no_final_abc; + + virtual void clear_flags() YS_OVERRIDE + { + one_pass = false; + no_final_abc = false; + } + + virtual void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE + { + clear_flags(); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-one_pass") { + one_pass = true; + continue; + } + if (args[argidx] == "-no_final_abc") { + no_final_abc = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + log_header(design, "Executing recover_reduce.\n"); + log_push(); + + run_script(design, "", ""); + + log_pop(); + } + + virtual void script() YS_OVERRIDE + { + if (!one_pass) + { + // Certain structures such as counters seem to work better if we extract only AND + // and then run a general extract pass. + // XXX: Why is that? Does this work in general? + run("abc -g AND"); + run("recover_reduce_core"); + } + run("abc -g AND,OR,XOR"); + run("recover_reduce_core"); + + if (!no_final_abc) + run("abc"); + + run("clean"); + } +} RecoverReducePass; + +PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 8a5887464c4c8dc9b1f3ecd987d7be9bca51b8f8 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Sun, 27 Aug 2017 02:01:32 -0700 Subject: recover_reduce: Rename recover_reduce_core to recover_reduce Clifford has commented on PR #387 stating that he does not like the driver script and would prefer to only have the core script with appropriate notes in the documentation. Also rename to .cc (rather than .cpp) for consistency. --- passes/techmap/Makefile.inc | 1 - passes/techmap/recover_reduce.cc | 219 +++++++++++++++++++++++++++++++++ passes/techmap/recover_reduce.cpp | 100 --------------- passes/techmap/recover_reduce_core.cpp | 219 --------------------------------- 4 files changed, 219 insertions(+), 320 deletions(-) create mode 100644 passes/techmap/recover_reduce.cc delete mode 100644 passes/techmap/recover_reduce.cpp delete mode 100644 passes/techmap/recover_reduce_core.cpp (limited to 'passes') diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc index 7561369b9..c2b918f00 100644 --- a/passes/techmap/Makefile.inc +++ b/passes/techmap/Makefile.inc @@ -18,7 +18,6 @@ OBJS += passes/techmap/hilomap.o OBJS += passes/techmap/extract.o OBJS += passes/techmap/extract_fa.o OBJS += passes/techmap/recover_reduce.o -OBJS += passes/techmap/recover_reduce_core.o OBJS += passes/techmap/alumacc.o OBJS += passes/techmap/dff2dffe.o OBJS += passes/techmap/dffinit.o diff --git a/passes/techmap/recover_reduce.cc b/passes/techmap/recover_reduce.cc new file mode 100644 index 000000000..dbd61b366 --- /dev/null +++ b/passes/techmap/recover_reduce.cc @@ -0,0 +1,219 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2017 Robert Ou + * + * 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 RecoverReduceCorePass : public Pass { + enum GateType { + And, + Or, + Xor + }; + + RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" recover_reduce_core\n"); + log("\n"); + log("converts gate chains into $reduce_*\n"); + log("\n"); + log("This performs the core step of the recover_reduce command. This step recognizes\n"); + log("chains of gates found by the previous steps and converts these chains into one\n"); + log("logical cell.\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + (void)args; + + for (auto module : design->selected_modules()) + { + SigMap sigmap(module); + + // Index all of the nets in the module + dict sig_to_driver; + dict> sig_to_sink; + for (auto cell : module->selected_cells()) + { + for (auto &conn : cell->connections()) + { + if (cell->output(conn.first)) + for (auto bit : sigmap(conn.second)) + sig_to_driver[bit] = cell; + + if (cell->input(conn.first)) + { + for (auto bit : sigmap(conn.second)) + { + if (sig_to_sink.count(bit) == 0) + sig_to_sink[bit] = pool(); + sig_to_sink[bit].insert(cell); + } + } + } + } + + // Need to check if any wires connect to module ports + pool port_sigs; + for (auto wire : module->selected_wires()) + if (wire->port_input || wire->port_output) + for (auto bit : sigmap(wire)) + port_sigs.insert(bit); + + // Actual logic starts here + pool consumed_cells; + for (auto cell : module->selected_cells()) + { + if (consumed_cells.count(cell)) + continue; + + GateType gt; + + if (cell->type == "$_AND_") + gt = GateType::And; + else if (cell->type == "$_OR_") + gt = GateType::Or; + else if (cell->type == "$_XOR_") + gt = GateType::Xor; + else + continue; + + log("Working on cell %s...\n", cell->name.c_str()); + + // Go all the way to the sink + Cell* head_cell = cell; + Cell* x = cell; + while (true) + { + if (!((x->type == "$_AND_" && gt == GateType::And) || + (x->type == "$_OR_" && gt == GateType::Or) || + (x->type == "$_XOR_" && gt == GateType::Xor))) + break; + + head_cell = x; + + auto y = sigmap(x->getPort("\\Y")); + log_assert(y.size() == 1); + + // Should only continue if there is one fanout back into a cell (not to a port) + if (sig_to_sink[y[0]].size() != 1) + break; + + x = *sig_to_sink[y[0]].begin(); + } + + log(" Head cell is %s\n", head_cell->name.c_str()); + + pool cur_supercell; + std::deque bfs_queue = {head_cell}; + while (bfs_queue.size()) + { + Cell* x = bfs_queue.front(); + bfs_queue.pop_front(); + + cur_supercell.insert(x); + + auto a = sigmap(x->getPort("\\A")); + log_assert(a.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1) + { + Cell* cell_a = sig_to_driver[a[0]]; + if (((cell_a->type == "$_AND_" && gt == GateType::And) || + (cell_a->type == "$_OR_" && gt == GateType::Or) || + (cell_a->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_a); + } + } + + auto b = sigmap(x->getPort("\\B")); + log_assert(b.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1) + { + Cell* cell_b = sig_to_driver[b[0]]; + if (((cell_b->type == "$_AND_" && gt == GateType::And) || + (cell_b->type == "$_OR_" && gt == GateType::Or) || + (cell_b->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_b); + } + } + } + + log(" Cells:\n"); + for (auto x : cur_supercell) + log(" %s\n", x->name.c_str()); + + if (cur_supercell.size() > 1) + { + // Worth it to create reduce cell + log(" Creating $reduce_* cell!\n"); + + pool input_pool; + pool input_pool_intermed; + for (auto x : cur_supercell) + { + input_pool.insert(sigmap(x->getPort("\\A"))[0]); + input_pool.insert(sigmap(x->getPort("\\B"))[0]); + input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]); + } + SigSpec input; + for (auto b : input_pool) + if (input_pool_intermed.count(b) == 0) + input.append_bit(b); + + SigBit output = sigmap(head_cell->getPort("\\Y")[0]); + + auto new_reduce_cell = module->addCell(NEW_ID, + gt == GateType::And ? "$reduce_and" : + gt == GateType::Or ? "$reduce_or" : + gt == GateType::Xor ? "$reduce_xor" : ""); + new_reduce_cell->setParam("\\A_SIGNED", 0); + new_reduce_cell->setParam("\\A_WIDTH", input.size()); + new_reduce_cell->setParam("\\Y_WIDTH", 1); + new_reduce_cell->setPort("\\A", input); + new_reduce_cell->setPort("\\Y", output); + + for (auto x : cur_supercell) + consumed_cells.insert(x); + } + } + + // Remove every cell that we've used up + for (auto cell : consumed_cells) + module->remove(cell); + } + } +} RecoverReduceCorePass; + +PRIVATE_NAMESPACE_END diff --git a/passes/techmap/recover_reduce.cpp b/passes/techmap/recover_reduce.cpp deleted file mode 100644 index 21ebac532..000000000 --- a/passes/techmap/recover_reduce.cpp +++ /dev/null @@ -1,100 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2017 Robert Ou - * - * 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" - -USING_YOSYS_NAMESPACE -PRIVATE_NAMESPACE_BEGIN - -struct RecoverReducePass : public ScriptPass -{ - RecoverReducePass() : ScriptPass("recover_reduce", "recovers $reduce_* from gates") {} - virtual void help() YS_OVERRIDE - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" recover_reduce [options]\n"); - log("\n"); - log("recovers $reduce_* from gates\n"); - log("\n"); - log("Reconstructs $reduce_* elements (e.g. larger gates) given a netlist of gates."); - log("This pass is intended to be used as part of a circuit reverse-engineering workflow.\n"); - log("\n"); - log("\n"); - log("The following commands are executed by this command:\n"); - help_script(); - log("\n"); - } - - bool one_pass, no_final_abc; - - virtual void clear_flags() YS_OVERRIDE - { - one_pass = false; - no_final_abc = false; - } - - virtual void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE - { - clear_flags(); - - size_t argidx; - for (argidx = 1; argidx < args.size(); argidx++) - { - if (args[argidx] == "-one_pass") { - one_pass = true; - continue; - } - if (args[argidx] == "-no_final_abc") { - no_final_abc = true; - continue; - } - break; - } - extra_args(args, argidx, design); - - log_header(design, "Executing recover_reduce.\n"); - log_push(); - - run_script(design, "", ""); - - log_pop(); - } - - virtual void script() YS_OVERRIDE - { - if (!one_pass) - { - // Certain structures such as counters seem to work better if we extract only AND - // and then run a general extract pass. - // XXX: Why is that? Does this work in general? - run("abc -g AND"); - run("recover_reduce_core"); - } - run("abc -g AND,OR,XOR"); - run("recover_reduce_core"); - - if (!no_final_abc) - run("abc"); - - run("clean"); - } -} RecoverReducePass; - -PRIVATE_NAMESPACE_END diff --git a/passes/techmap/recover_reduce_core.cpp b/passes/techmap/recover_reduce_core.cpp deleted file mode 100644 index dbd61b366..000000000 --- a/passes/techmap/recover_reduce_core.cpp +++ /dev/null @@ -1,219 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2017 Robert Ou - * - * 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 RecoverReduceCorePass : public Pass { - enum GateType { - And, - Or, - Xor - }; - - RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" recover_reduce_core\n"); - log("\n"); - log("converts gate chains into $reduce_*\n"); - log("\n"); - log("This performs the core step of the recover_reduce command. This step recognizes\n"); - log("chains of gates found by the previous steps and converts these chains into one\n"); - log("logical cell.\n"); - log("\n"); - } - virtual void execute(std::vector args, RTLIL::Design *design) - { - (void)args; - - for (auto module : design->selected_modules()) - { - SigMap sigmap(module); - - // Index all of the nets in the module - dict sig_to_driver; - dict> sig_to_sink; - for (auto cell : module->selected_cells()) - { - for (auto &conn : cell->connections()) - { - if (cell->output(conn.first)) - for (auto bit : sigmap(conn.second)) - sig_to_driver[bit] = cell; - - if (cell->input(conn.first)) - { - for (auto bit : sigmap(conn.second)) - { - if (sig_to_sink.count(bit) == 0) - sig_to_sink[bit] = pool(); - sig_to_sink[bit].insert(cell); - } - } - } - } - - // Need to check if any wires connect to module ports - pool port_sigs; - for (auto wire : module->selected_wires()) - if (wire->port_input || wire->port_output) - for (auto bit : sigmap(wire)) - port_sigs.insert(bit); - - // Actual logic starts here - pool consumed_cells; - for (auto cell : module->selected_cells()) - { - if (consumed_cells.count(cell)) - continue; - - GateType gt; - - if (cell->type == "$_AND_") - gt = GateType::And; - else if (cell->type == "$_OR_") - gt = GateType::Or; - else if (cell->type == "$_XOR_") - gt = GateType::Xor; - else - continue; - - log("Working on cell %s...\n", cell->name.c_str()); - - // Go all the way to the sink - Cell* head_cell = cell; - Cell* x = cell; - while (true) - { - if (!((x->type == "$_AND_" && gt == GateType::And) || - (x->type == "$_OR_" && gt == GateType::Or) || - (x->type == "$_XOR_" && gt == GateType::Xor))) - break; - - head_cell = x; - - auto y = sigmap(x->getPort("\\Y")); - log_assert(y.size() == 1); - - // Should only continue if there is one fanout back into a cell (not to a port) - if (sig_to_sink[y[0]].size() != 1) - break; - - x = *sig_to_sink[y[0]].begin(); - } - - log(" Head cell is %s\n", head_cell->name.c_str()); - - pool cur_supercell; - std::deque bfs_queue = {head_cell}; - while (bfs_queue.size()) - { - Cell* x = bfs_queue.front(); - bfs_queue.pop_front(); - - cur_supercell.insert(x); - - auto a = sigmap(x->getPort("\\A")); - log_assert(a.size() == 1); - // Must have only one sink - // XXX: Check that it is indeed this node? - if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1) - { - Cell* cell_a = sig_to_driver[a[0]]; - if (((cell_a->type == "$_AND_" && gt == GateType::And) || - (cell_a->type == "$_OR_" && gt == GateType::Or) || - (cell_a->type == "$_XOR_" && gt == GateType::Xor))) - { - // The cell here is the correct type, and it's definitely driving only - // this current cell. - bfs_queue.push_back(cell_a); - } - } - - auto b = sigmap(x->getPort("\\B")); - log_assert(b.size() == 1); - // Must have only one sink - // XXX: Check that it is indeed this node? - if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1) - { - Cell* cell_b = sig_to_driver[b[0]]; - if (((cell_b->type == "$_AND_" && gt == GateType::And) || - (cell_b->type == "$_OR_" && gt == GateType::Or) || - (cell_b->type == "$_XOR_" && gt == GateType::Xor))) - { - // The cell here is the correct type, and it's definitely driving only - // this current cell. - bfs_queue.push_back(cell_b); - } - } - } - - log(" Cells:\n"); - for (auto x : cur_supercell) - log(" %s\n", x->name.c_str()); - - if (cur_supercell.size() > 1) - { - // Worth it to create reduce cell - log(" Creating $reduce_* cell!\n"); - - pool input_pool; - pool input_pool_intermed; - for (auto x : cur_supercell) - { - input_pool.insert(sigmap(x->getPort("\\A"))[0]); - input_pool.insert(sigmap(x->getPort("\\B"))[0]); - input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]); - } - SigSpec input; - for (auto b : input_pool) - if (input_pool_intermed.count(b) == 0) - input.append_bit(b); - - SigBit output = sigmap(head_cell->getPort("\\Y")[0]); - - auto new_reduce_cell = module->addCell(NEW_ID, - gt == GateType::And ? "$reduce_and" : - gt == GateType::Or ? "$reduce_or" : - gt == GateType::Xor ? "$reduce_xor" : ""); - new_reduce_cell->setParam("\\A_SIGNED", 0); - new_reduce_cell->setParam("\\A_WIDTH", input.size()); - new_reduce_cell->setParam("\\Y_WIDTH", 1); - new_reduce_cell->setPort("\\A", input); - new_reduce_cell->setPort("\\Y", output); - - for (auto x : cur_supercell) - consumed_cells.insert(x); - } - } - - // Remove every cell that we've used up - for (auto cell : consumed_cells) - module->remove(cell); - } - } -} RecoverReduceCorePass; - -PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 74d0f17fd4b26eeece7133cf2425d3c4e0e35976 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Sun, 27 Aug 2017 02:12:41 -0700 Subject: recover_reduce: Reindent using tabs --- passes/techmap/recover_reduce.cc | 380 +++++++++++++++++++-------------------- 1 file changed, 190 insertions(+), 190 deletions(-) (limited to 'passes') diff --git a/passes/techmap/recover_reduce.cc b/passes/techmap/recover_reduce.cc index dbd61b366..873b8ab26 100644 --- a/passes/techmap/recover_reduce.cc +++ b/passes/techmap/recover_reduce.cc @@ -24,196 +24,196 @@ USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN struct RecoverReduceCorePass : public Pass { - enum GateType { - And, - Or, - Xor - }; - - RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" recover_reduce_core\n"); - log("\n"); - log("converts gate chains into $reduce_*\n"); - log("\n"); - log("This performs the core step of the recover_reduce command. This step recognizes\n"); - log("chains of gates found by the previous steps and converts these chains into one\n"); - log("logical cell.\n"); - log("\n"); - } - virtual void execute(std::vector args, RTLIL::Design *design) - { - (void)args; - - for (auto module : design->selected_modules()) - { - SigMap sigmap(module); - - // Index all of the nets in the module - dict sig_to_driver; - dict> sig_to_sink; - for (auto cell : module->selected_cells()) - { - for (auto &conn : cell->connections()) - { - if (cell->output(conn.first)) - for (auto bit : sigmap(conn.second)) - sig_to_driver[bit] = cell; - - if (cell->input(conn.first)) - { - for (auto bit : sigmap(conn.second)) - { - if (sig_to_sink.count(bit) == 0) - sig_to_sink[bit] = pool(); - sig_to_sink[bit].insert(cell); - } - } - } - } - - // Need to check if any wires connect to module ports - pool port_sigs; - for (auto wire : module->selected_wires()) - if (wire->port_input || wire->port_output) - for (auto bit : sigmap(wire)) - port_sigs.insert(bit); - - // Actual logic starts here - pool consumed_cells; - for (auto cell : module->selected_cells()) - { - if (consumed_cells.count(cell)) - continue; - - GateType gt; - - if (cell->type == "$_AND_") - gt = GateType::And; - else if (cell->type == "$_OR_") - gt = GateType::Or; - else if (cell->type == "$_XOR_") - gt = GateType::Xor; - else - continue; - - log("Working on cell %s...\n", cell->name.c_str()); - - // Go all the way to the sink - Cell* head_cell = cell; - Cell* x = cell; - while (true) - { - if (!((x->type == "$_AND_" && gt == GateType::And) || - (x->type == "$_OR_" && gt == GateType::Or) || - (x->type == "$_XOR_" && gt == GateType::Xor))) - break; - - head_cell = x; - - auto y = sigmap(x->getPort("\\Y")); - log_assert(y.size() == 1); - - // Should only continue if there is one fanout back into a cell (not to a port) - if (sig_to_sink[y[0]].size() != 1) - break; - - x = *sig_to_sink[y[0]].begin(); - } - - log(" Head cell is %s\n", head_cell->name.c_str()); - - pool cur_supercell; - std::deque bfs_queue = {head_cell}; - while (bfs_queue.size()) - { - Cell* x = bfs_queue.front(); - bfs_queue.pop_front(); - - cur_supercell.insert(x); - - auto a = sigmap(x->getPort("\\A")); - log_assert(a.size() == 1); - // Must have only one sink - // XXX: Check that it is indeed this node? - if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1) - { - Cell* cell_a = sig_to_driver[a[0]]; - if (((cell_a->type == "$_AND_" && gt == GateType::And) || - (cell_a->type == "$_OR_" && gt == GateType::Or) || - (cell_a->type == "$_XOR_" && gt == GateType::Xor))) - { - // The cell here is the correct type, and it's definitely driving only - // this current cell. - bfs_queue.push_back(cell_a); - } - } - - auto b = sigmap(x->getPort("\\B")); - log_assert(b.size() == 1); - // Must have only one sink - // XXX: Check that it is indeed this node? - if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1) - { - Cell* cell_b = sig_to_driver[b[0]]; - if (((cell_b->type == "$_AND_" && gt == GateType::And) || - (cell_b->type == "$_OR_" && gt == GateType::Or) || - (cell_b->type == "$_XOR_" && gt == GateType::Xor))) - { - // The cell here is the correct type, and it's definitely driving only - // this current cell. - bfs_queue.push_back(cell_b); - } - } - } - - log(" Cells:\n"); - for (auto x : cur_supercell) - log(" %s\n", x->name.c_str()); - - if (cur_supercell.size() > 1) - { - // Worth it to create reduce cell - log(" Creating $reduce_* cell!\n"); - - pool input_pool; - pool input_pool_intermed; - for (auto x : cur_supercell) - { - input_pool.insert(sigmap(x->getPort("\\A"))[0]); - input_pool.insert(sigmap(x->getPort("\\B"))[0]); - input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]); - } - SigSpec input; - for (auto b : input_pool) - if (input_pool_intermed.count(b) == 0) - input.append_bit(b); - - SigBit output = sigmap(head_cell->getPort("\\Y")[0]); - - auto new_reduce_cell = module->addCell(NEW_ID, - gt == GateType::And ? "$reduce_and" : - gt == GateType::Or ? "$reduce_or" : - gt == GateType::Xor ? "$reduce_xor" : ""); - new_reduce_cell->setParam("\\A_SIGNED", 0); - new_reduce_cell->setParam("\\A_WIDTH", input.size()); - new_reduce_cell->setParam("\\Y_WIDTH", 1); - new_reduce_cell->setPort("\\A", input); - new_reduce_cell->setPort("\\Y", output); - - for (auto x : cur_supercell) - consumed_cells.insert(x); - } - } - - // Remove every cell that we've used up - for (auto cell : consumed_cells) - module->remove(cell); - } - } + enum GateType { + And, + Or, + Xor + }; + + RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" recover_reduce_core\n"); + log("\n"); + log("converts gate chains into $reduce_*\n"); + log("\n"); + log("This performs the core step of the recover_reduce command. This step recognizes\n"); + log("chains of gates found by the previous steps and converts these chains into one\n"); + log("logical cell.\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + (void)args; + + for (auto module : design->selected_modules()) + { + SigMap sigmap(module); + + // Index all of the nets in the module + dict sig_to_driver; + dict> sig_to_sink; + for (auto cell : module->selected_cells()) + { + for (auto &conn : cell->connections()) + { + if (cell->output(conn.first)) + for (auto bit : sigmap(conn.second)) + sig_to_driver[bit] = cell; + + if (cell->input(conn.first)) + { + for (auto bit : sigmap(conn.second)) + { + if (sig_to_sink.count(bit) == 0) + sig_to_sink[bit] = pool(); + sig_to_sink[bit].insert(cell); + } + } + } + } + + // Need to check if any wires connect to module ports + pool port_sigs; + for (auto wire : module->selected_wires()) + if (wire->port_input || wire->port_output) + for (auto bit : sigmap(wire)) + port_sigs.insert(bit); + + // Actual logic starts here + pool consumed_cells; + for (auto cell : module->selected_cells()) + { + if (consumed_cells.count(cell)) + continue; + + GateType gt; + + if (cell->type == "$_AND_") + gt = GateType::And; + else if (cell->type == "$_OR_") + gt = GateType::Or; + else if (cell->type == "$_XOR_") + gt = GateType::Xor; + else + continue; + + log("Working on cell %s...\n", cell->name.c_str()); + + // Go all the way to the sink + Cell* head_cell = cell; + Cell* x = cell; + while (true) + { + if (!((x->type == "$_AND_" && gt == GateType::And) || + (x->type == "$_OR_" && gt == GateType::Or) || + (x->type == "$_XOR_" && gt == GateType::Xor))) + break; + + head_cell = x; + + auto y = sigmap(x->getPort("\\Y")); + log_assert(y.size() == 1); + + // Should only continue if there is one fanout back into a cell (not to a port) + if (sig_to_sink[y[0]].size() != 1) + break; + + x = *sig_to_sink[y[0]].begin(); + } + + log(" Head cell is %s\n", head_cell->name.c_str()); + + pool cur_supercell; + std::deque bfs_queue = {head_cell}; + while (bfs_queue.size()) + { + Cell* x = bfs_queue.front(); + bfs_queue.pop_front(); + + cur_supercell.insert(x); + + auto a = sigmap(x->getPort("\\A")); + log_assert(a.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1) + { + Cell* cell_a = sig_to_driver[a[0]]; + if (((cell_a->type == "$_AND_" && gt == GateType::And) || + (cell_a->type == "$_OR_" && gt == GateType::Or) || + (cell_a->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_a); + } + } + + auto b = sigmap(x->getPort("\\B")); + log_assert(b.size() == 1); + // Must have only one sink + // XXX: Check that it is indeed this node? + if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1) + { + Cell* cell_b = sig_to_driver[b[0]]; + if (((cell_b->type == "$_AND_" && gt == GateType::And) || + (cell_b->type == "$_OR_" && gt == GateType::Or) || + (cell_b->type == "$_XOR_" && gt == GateType::Xor))) + { + // The cell here is the correct type, and it's definitely driving only + // this current cell. + bfs_queue.push_back(cell_b); + } + } + } + + log(" Cells:\n"); + for (auto x : cur_supercell) + log(" %s\n", x->name.c_str()); + + if (cur_supercell.size() > 1) + { + // Worth it to create reduce cell + log(" Creating $reduce_* cell!\n"); + + pool input_pool; + pool input_pool_intermed; + for (auto x : cur_supercell) + { + input_pool.insert(sigmap(x->getPort("\\A"))[0]); + input_pool.insert(sigmap(x->getPort("\\B"))[0]); + input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]); + } + SigSpec input; + for (auto b : input_pool) + if (input_pool_intermed.count(b) == 0) + input.append_bit(b); + + SigBit output = sigmap(head_cell->getPort("\\Y")[0]); + + auto new_reduce_cell = module->addCell(NEW_ID, + gt == GateType::And ? "$reduce_and" : + gt == GateType::Or ? "$reduce_or" : + gt == GateType::Xor ? "$reduce_xor" : ""); + new_reduce_cell->setParam("\\A_SIGNED", 0); + new_reduce_cell->setParam("\\A_WIDTH", input.size()); + new_reduce_cell->setParam("\\Y_WIDTH", 1); + new_reduce_cell->setPort("\\A", input); + new_reduce_cell->setPort("\\Y", output); + + for (auto x : cur_supercell) + consumed_cells.insert(x); + } + } + + // Remove every cell that we've used up + for (auto cell : consumed_cells) + module->remove(cell); + } + } } RecoverReduceCorePass; PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 849b8857752170812261261934d8571ecff09295 Mon Sep 17 00:00:00 2001 From: Robert Ou Date: Sun, 27 Aug 2017 02:19:19 -0700 Subject: recover_reduce: Update documentation The documentation now describes the commands performed in the deleted recover_reduce script. --- passes/techmap/recover_reduce.cc | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) (limited to 'passes') diff --git a/passes/techmap/recover_reduce.cc b/passes/techmap/recover_reduce.cc index 873b8ab26..bcc31e182 100644 --- a/passes/techmap/recover_reduce.cc +++ b/passes/techmap/recover_reduce.cc @@ -23,25 +23,28 @@ USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN -struct RecoverReduceCorePass : public Pass { +struct RecoverReducePass : public Pass { enum GateType { And, Or, Xor }; - RecoverReduceCorePass() : Pass("recover_reduce_core", "converts gate chains into $reduce_*") { } + RecoverReducePass() : Pass("recover_reduce", "converts gate chains into $reduce_* cells") { } virtual void help() { // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| log("\n"); - log(" recover_reduce_core\n"); + log(" recover_reduce\n"); log("\n"); - log("converts gate chains into $reduce_*\n"); + log("converts gate chains into $reduce_* cells\n"); log("\n"); - log("This performs the core step of the recover_reduce command. This step recognizes\n"); - log("chains of gates found by the previous steps and converts these chains into one\n"); - log("logical cell.\n"); + log("This command finds chains of $_AND_, $_OR_, and $_XOR_ cells and replaces them\n"); + log("with their corresponding $reduce_* cells. Because this command only operates on\n"); + log("these cell types, it is recommended to map the design to only these cell types\n"); + log("using the `abc -g` command. Note that, in some cases, it may be more effective\n"); + log("to map the design to only $_AND_ cells, run recover_reduce, map the remaining\n"); + log("parts of the design to AND/OR/XOR cells, and run recover_reduce a second time.\n"); log("\n"); } virtual void execute(std::vector args, RTLIL::Design *design) @@ -214,6 +217,6 @@ struct RecoverReduceCorePass : public Pass { module->remove(cell); } } -} RecoverReduceCorePass; +} RecoverReducePass; PRIVATE_NAMESPACE_END -- cgit v1.2.3