azonenberg · Aug 1, 2017 · Aug 4, 2017 · Aug 5, 2017 · Aug 6, 2017 · Aug 6, 2017
Showing with 419 additions and 28 deletions.

+9 −0 passes/techmap/Makefile.inc

+91 −28 passes/techmap/extract_fa.cc

+100 −0 passes/techmap/recover_reduce.cpp

+219 −0 passes/techmap/recover_reduce_core.cpp
diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc
@@ -16,6 +16,15 @@ ifneq ($(SMALL),1)
 OBJS += passes/techmap/iopadmap.o
 OBJS += passes/techmap/hilomap.o
 OBJS += passes/techmap/extract.o
+OBJS += passes/techmap/recover_adder.o
+$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap.lib))
+$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap.v))
+$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap_gates.v))
+OBJS += passes/techmap/recover_adder_core.o
+OBJS += passes/techmap/recover_reduce.o
+OBJS += passes/techmap/recover_reduce_core.o
+OBJS += passes/techmap/recover_tff.o
+$(eval $(call add_share_file,share/untechmap,passes/techmap/tff_untechmap.v))
 OBJS += passes/techmap/extract_fa.o
 OBJS += passes/techmap/extract_counter.o
 OBJS += passes/techmap/extract_reduce.o

diff --git a/passes/techmap/extract_fa.cc b/passes/techmap/extract_fa.cc
@@ -326,6 +326,8 @@ struct ExtractFaWorker
 				log("\n");
 			}
 
+			dict<int, tuple<SigBit, SigBit, Cell*>> facache;
+
 			for (auto &it : func3_maj_info)
 			{
 				int func = it.first;
@@ -357,33 +359,64 @@ struct ExtractFaWorker
 					log(" %s", log_signal(bit));
 				log("\n");
 
-				Cell *cell = module->addCell(NEW_ID, "$fa");
-				cell->setParam("\\WIDTH", 1);
+				int fakey = 0;
+				if (f3i.inv_a) fakey |= 1;
+				if (f3i.inv_b) fakey |= 2;
+				if (f3i.inv_c) fakey |= 4;
+
+				int fakey_inv = fakey ^ 7;
+				bool invert_xy = false;
+				SigBit X, Y;
+
+				if (facache.count(fakey))
+				{
+					auto &fa = facache.at(fakey);
+					X = get<0>(fa);
+					Y = get<1>(fa);
+					log("      Reusing $fa cell %s.\n", log_id(get<2>(fa)));
+				}
+				else
+				if (facache.count(fakey_inv))
+				{
+					auto &fa = facache.at(fakey_inv);
+					invert_xy = true;
+					X = get<0>(fa);
+					Y = get<1>(fa);
+					log("      Reusing $fa cell %s.\n", log_id(get<2>(fa)));
+				}
+				else
+				{
+					Cell *cell = module->addCell(NEW_ID, "$fa");
+					cell->setParam("\\WIDTH", 1);
+
+					log("      Created $fa cell %s.\n", log_id(cell));
 
-				log("      Created $fa cell %s.\n", log_id(cell));
+					cell->setPort("\\A", f3i.inv_a ? module->NotGate(NEW_ID, A) : A);
+					cell->setPort("\\B", f3i.inv_b ? module->NotGate(NEW_ID, B) : B);
+					cell->setPort("\\C", f3i.inv_c ? module->NotGate(NEW_ID, C) : C);
 
-				cell->setPort("\\A", f3i.inv_a ? module->NotGate(NEW_ID, A) : A);
-				cell->setPort("\\B", f3i.inv_b ? module->NotGate(NEW_ID, B) : B);
-				cell->setPort("\\C", f3i.inv_c ? module->NotGate(NEW_ID, C) : C);
+					X = module->addWire(NEW_ID);
+					Y = module->addWire(NEW_ID);
 
-				SigBit X = module->addWire(NEW_ID);
-				SigBit Y = module->addWire(NEW_ID);
+					cell->setPort("\\X", X);
+					cell->setPort("\\Y", Y);
 
-				cell->setPort("\\X", X);
-				cell->setPort("\\Y", Y);
+					facache[fakey] = make_tuple(X, Y, cell);
+				}
 
 				if (func3.at(key).count(xor3_func)) {
+					SigBit YY = invert_xy ? module->NotGate(NEW_ID, Y) : Y;
 					for (auto bit : func3.at(key).at(xor3_func))
-						assign_new_driver(bit, Y);
+						assign_new_driver(bit, YY);
 				}
 
 				if (func3.at(key).count(xnor3_func)) {
-					SigBit YN = module->NotGate(NEW_ID, Y);
+					SigBit YY = invert_xy ? Y : module->NotGate(NEW_ID, Y);
 					for (auto bit : func3.at(key).at(xnor3_func))
-						assign_new_driver(bit, YN);
+						assign_new_driver(bit, YY);
 				}
 
-				SigBit XX = f3i.inv_y ? module->NotGate(NEW_ID, X) : X;
+				SigBit XX = invert_xy != f3i.inv_y ? module->NotGate(NEW_ID, X) : X;
 
 				for (auto bit : func3.at(key).at(func))
 					assign_new_driver(bit, XX);
@@ -408,6 +441,8 @@ struct ExtractFaWorker
 				log("\n");
 			}
 
+			dict<int, tuple<SigBit, SigBit, Cell*>> facache;
+
 			for (auto &it : func2_and_info)
 			{
 				int func = it.first;
@@ -431,33 +466,61 @@ struct ExtractFaWorker
 					log(" %s", log_signal(bit));
 				log("\n");
 
-				Cell *cell = module->addCell(NEW_ID, "$fa");
-				cell->setParam("\\WIDTH", 1);
+				int fakey = 0;
+				if (f2i.inv_a) fakey |= 1;
+				if (f2i.inv_b) fakey |= 2;
 
-				log("      Created $fa cell %s.\n", log_id(cell));
+				int fakey_inv = fakey ^ 3;
+				bool invert_xy = false;
+				SigBit X, Y;
 
-				cell->setPort("\\A", f2i.inv_a ? module->NotGate(NEW_ID, A) : A);
-				cell->setPort("\\B", f2i.inv_b ? module->NotGate(NEW_ID, B) : B);
-				cell->setPort("\\C", State::S0);
+				if (facache.count(fakey))
+				{
+					auto &fa = facache.at(fakey);
+					X = get<0>(fa);
+					Y = get<1>(fa);
+					log("      Reusing $fa cell %s.\n", log_id(get<2>(fa)));
+				}
+				else
+				if (facache.count(fakey_inv))
+				{
+					auto &fa = facache.at(fakey_inv);
+					invert_xy = true;
+					X = get<0>(fa);
+					Y = get<1>(fa);
+					log("      Reusing $fa cell %s.\n", log_id(get<2>(fa)));
+				}
+				else
+				{
+					Cell *cell = module->addCell(NEW_ID, "$fa");
+					cell->setParam("\\WIDTH", 1);
+
+					log("      Created $fa cell %s.\n", log_id(cell));
 
-				SigBit X = module->addWire(NEW_ID);
-				SigBit Y = module->addWire(NEW_ID);
+					cell->setPort("\\A", f2i.inv_a ? module->NotGate(NEW_ID, A) : A);
+					cell->setPort("\\B", f2i.inv_b ? module->NotGate(NEW_ID, B) : B);
+					cell->setPort("\\C", State::S0);
 
-				cell->setPort("\\X", X);
-				cell->setPort("\\Y", Y);
+					X = module->addWire(NEW_ID);
+					Y = module->addWire(NEW_ID);
+
+					cell->setPort("\\X", X);
+					cell->setPort("\\Y", Y);
+				}
 
 				if (func2.at(key).count(xor2_func)) {
+					SigBit YY = invert_xy ? module->NotGate(NEW_ID, Y) : Y;
 					for (auto bit : func2.at(key).at(xor2_func))
-						assign_new_driver(bit, Y);
+						assign_new_driver(bit, YY);
 				}
 
 				if (func2.at(key).count(xnor2_func)) {
-					SigBit YN = module->NotGate(NEW_ID, Y);
+					SigBit YY = invert_xy ? Y : module->NotGate(NEW_ID, Y);
 					for (auto bit : func2.at(key).at(xnor2_func))
-						assign_new_driver(bit, YN);
+						assign_new_driver(bit, YY);
 				}
 
-				SigBit XX = f2i.inv_y ? module->NotGate(NEW_ID, X) : X;
+				SigBit XX = invert_xy != f2i.inv_y ? module->NotGate(NEW_ID, X) : X;
 
 				for (auto bit : func2.at(key).at(func))
 					assign_new_driver(bit, XX);

diff --git a/passes/techmap/recover_reduce.cpp b/passes/techmap/recover_reduce.cpp
@@ -0,0 +1,100 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2017 Robert Ou <rqou@robertou.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"
+
+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<std::string> 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
@@ -0,0 +1,219 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2017 Robert Ou <rqou@robertou.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 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<std::string> args, RTLIL::Design *design)
+    {
+        (void)args;
+
+        for (auto module : design->selected_modules())
+        {
+            SigMap sigmap(module);
+
+            // Index all of the nets in the module
+            dict<SigBit, Cell*> sig_to_driver;
+            dict<SigBit, pool<Cell*>> 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<Cell*>();
+                            sig_to_sink[bit].insert(cell);
+                        }
+                    }
+                }
+            }
+
+            // Need to check if any wires connect to module ports
+            pool<SigBit> 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<Cell*> 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<Cell*> cur_supercell;
+                std::deque<Cell*> 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<SigBit> input_pool;
+                    pool<SigBit> 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