From 0a225f8b273bfd036efa89f660114d4ab9cb190f Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 22 Jan 2015 12:03:15 +0100 Subject: Moved equiv stuff to passes/equiv/ --- passes/equiv/Makefile.inc | 5 + passes/equiv/equiv_make.cc | 248 ++++++++++++++++++++++++++++++++++++++++++ passes/equiv/equiv_simple.cc | 253 +++++++++++++++++++++++++++++++++++++++++++ passes/equiv/equiv_status.cc | 94 ++++++++++++++++ passes/sat/Makefile.inc | 3 - passes/sat/equiv_make.cc | 248 ------------------------------------------ passes/sat/equiv_simple.cc | 253 ------------------------------------------- passes/sat/equiv_status.cc | 94 ---------------- 8 files changed, 600 insertions(+), 598 deletions(-) create mode 100644 passes/equiv/Makefile.inc create mode 100644 passes/equiv/equiv_make.cc create mode 100644 passes/equiv/equiv_simple.cc create mode 100644 passes/equiv/equiv_status.cc delete mode 100644 passes/sat/equiv_make.cc delete mode 100644 passes/sat/equiv_simple.cc delete mode 100644 passes/sat/equiv_status.cc (limited to 'passes') diff --git a/passes/equiv/Makefile.inc b/passes/equiv/Makefile.inc new file mode 100644 index 00000000..16abcd96 --- /dev/null +++ b/passes/equiv/Makefile.inc @@ -0,0 +1,5 @@ + +OBJS += passes/equiv/equiv_make.o +OBJS += passes/equiv/equiv_simple.o +OBJS += passes/equiv/equiv_status.o + diff --git a/passes/equiv/equiv_make.cc b/passes/equiv/equiv_make.cc new file mode 100644 index 00000000..07374cfc --- /dev/null +++ b/passes/equiv/equiv_make.cc @@ -0,0 +1,248 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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/celltypes.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct EquivMakeWorker +{ + Module *gold_mod, *gate_mod, *equiv_mod; + pool wire_names, cell_names; + CellTypes ct; + + void copy_to_equiv() + { + Module *gold_clone = gold_mod->clone(); + Module *gate_clone = gate_mod->clone(); + + for (auto it : gold_clone->wires().to_vector()) { if (it->name[0] == '\\') wire_names.insert(it->name); gold_clone->rename(it, it->name.str() + "_gold"); } + for (auto it : gold_clone->cells().to_vector()) { if (it->name[0] == '\\') cell_names.insert(it->name); gold_clone->rename(it, it->name.str() + "_gold"); } + for (auto it : gate_clone->wires().to_vector()) { if (it->name[0] == '\\') wire_names.insert(it->name); gate_clone->rename(it, it->name.str() + "_gate"); } + for (auto it : gate_clone->cells().to_vector()) { if (it->name[0] == '\\') cell_names.insert(it->name); gate_clone->rename(it, it->name.str() + "_gate"); } + + gold_clone->cloneInto(equiv_mod); + gate_clone->cloneInto(equiv_mod); + delete gold_clone; + delete gate_clone; + } + + void find_same_wires() + { + SigMap assign_map(equiv_mod); + SigMap rd_signal_map; + + // list of cells without added $equiv cells + auto cells_list = equiv_mod->cells().to_vector(); + + for (auto id : wire_names) + { + IdString gold_id = id.str() + "_gold"; + IdString gate_id = id.str() + "_gate"; + + Wire *gold_wire = equiv_mod->wire(gold_id); + Wire *gate_wire = equiv_mod->wire(gate_id); + + if (gold_wire == nullptr || gate_wire == nullptr || gold_wire->width != gate_wire->width) { + if (gold_wire && gold_wire->port_id) + log_error("Can't match gold port `%s' to a gate port.\n", log_id(gold_wire)); + if (gate_wire && gate_wire->port_id) + log_error("Can't match gate port `%s' to a gold port.\n", log_id(gate_wire)); + continue; + } + + log("Presumably equivalent wires: %s (%s), %s (%s) -> %s\n", + log_id(gold_wire), log_signal(assign_map(gold_wire)), + log_id(gate_wire), log_signal(assign_map(gate_wire)), log_id(id)); + + if (gold_wire->port_output || gate_wire->port_output) + { + Wire *wire = equiv_mod->addWire(id, gold_wire->width); + wire->port_output = true; + gold_wire->port_input = false; + gate_wire->port_input = false; + gold_wire->port_output = false; + gate_wire->port_output = false; + + for (int i = 0; i < wire->width; i++) + equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i)); + + rd_signal_map.add(assign_map(gold_wire), wire); + rd_signal_map.add(assign_map(gate_wire), wire); + } + else + if (gold_wire->port_input || gate_wire->port_input) + { + Wire *wire = equiv_mod->addWire(id, gold_wire->width); + wire->port_input = true; + gold_wire->port_input = false; + gate_wire->port_input = false; + equiv_mod->connect(gold_wire, wire); + equiv_mod->connect(gate_wire, wire); + } + else + { + Wire *wire = equiv_mod->addWire(id, gold_wire->width); + + for (int i = 0; i < wire->width; i++) + equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i)); + + rd_signal_map.add(assign_map(gold_wire), wire); + rd_signal_map.add(assign_map(gate_wire), wire); + } + } + + for (auto c : cells_list) + for (auto &conn : c->connections()) + if (ct.cell_input(c->type, conn.first)) { + SigSpec old_sig = assign_map(conn.second); + SigSpec new_sig = rd_signal_map(old_sig); + if (old_sig != new_sig) { + log("Changing input %s of cell %s (%s): %s -> %s\n", + log_id(conn.first), log_id(c), log_id(c->type), + log_signal(old_sig), log_signal(new_sig)); + c->setPort(conn.first, new_sig); + } + } + + equiv_mod->fixup_ports(); + } + + void find_same_cells() + { + SigMap assign_map(equiv_mod); + + for (auto id : cell_names) + { + IdString gold_id = id.str() + "_gold"; + IdString gate_id = id.str() + "_gate"; + + Cell *gold_cell = equiv_mod->cell(gold_id); + Cell *gate_cell = equiv_mod->cell(gate_id); + + if (gold_cell == nullptr || gate_cell == nullptr || gold_cell->type != gate_cell->type || !ct.cell_known(gold_cell->type) || + gold_cell->parameters != gate_cell->parameters || GetSize(gold_cell->connections()) != GetSize(gate_cell->connections())) + try_next_cell_name: + continue; + + for (auto gold_conn : gold_cell->connections()) + if (!gate_cell->connections().count(gold_conn.first)) + goto try_next_cell_name; + + log("Presumably equivalent cells: %s %s (%s) -> %s\n", + log_id(gold_cell), log_id(gate_cell), log_id(gold_cell->type), log_id(id)); + + for (auto gold_conn : gold_cell->connections()) + { + SigSpec gold_sig = assign_map(gold_conn.second); + SigSpec gate_sig = assign_map(gate_cell->getPort(gold_conn.first)); + + if (ct.cell_output(gold_cell->type, gold_conn.first)) { + equiv_mod->connect(gate_sig, gold_sig); + continue; + } + + for (int i = 0; i < GetSize(gold_sig); i++) + if (gold_sig[i] != gate_sig[i]) { + Wire *w = equiv_mod->addWire(NEW_ID); + equiv_mod->addEquiv(NEW_ID, gold_sig[i], gate_sig[i], w); + gold_sig[i] = w; + } + + gold_cell->setPort(gold_conn.first, gold_sig); + } + + equiv_mod->remove(gate_cell); + equiv_mod->rename(gold_cell, id); + } + } + + void run() + { + copy_to_equiv(); + find_same_wires(); + find_same_cells(); + } +}; + +struct EquivMakePass : public Pass { + EquivMakePass() : Pass("equiv_make", "prepare a circuit for equivalence checking") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" equiv_make [options] gold_module gate_module equiv_module\n"); + log("\n"); + log("This creates a module annotated with $equiv cells from two presumably\n"); + log("equivalent modules. Use commands such as 'equiv_simple' and 'equiv_status'\n"); + log("to work with the created equivalent checking module.\n"); + log("\n"); + log("Note: The circuit created by this command is not a miter (with something like\n"); + log("a trigger output), but instead uses $equiv cells to encode the equivalence\n"); + log("checking problem. Use 'miter -equiv' if you want to create a miter circuit.\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + EquivMakeWorker worker; + worker.ct.setup(design); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + // if (args[argidx] == "-foo" && argidx+1 < args.size()) { + // log("foo> %s\n", args[++argidx].c_str()); + // continue; + // } + break; + } + + if (argidx+3 != args.size()) + log_cmd_error("Invalid number of arguments.\n"); + + worker.gold_mod = design->module(RTLIL::escape_id(args[argidx])); + worker.gate_mod = design->module(RTLIL::escape_id(args[argidx+1])); + worker.equiv_mod = design->module(RTLIL::escape_id(args[argidx+2])); + + if (worker.gold_mod == nullptr) + log_cmd_error("Can't find gold module %s.\n", args[argidx].c_str()); + + if (worker.gate_mod == nullptr) + log_cmd_error("Can't find gate module %s.\n", args[argidx+1].c_str()); + + if (worker.equiv_mod != nullptr) + log_cmd_error("Equiv module %s already exists.\n", args[argidx+2].c_str()); + + if (worker.gold_mod->has_memories() || worker.gold_mod->has_processes()) + log_cmd_error("Gold module contains memories or procresses. Run 'memory' or 'proc' respectively.\n"); + + if (worker.gate_mod->has_memories() || worker.gate_mod->has_processes()) + log_cmd_error("Gate module contains memories or procresses. Run 'memory' or 'proc' respectively.\n"); + + log_header("Executing EQUIV_MAKE pass (creating equiv checking module).\n"); + + worker.equiv_mod = design->addModule(RTLIL::escape_id(args[argidx+2])); + worker.run(); + } +} EquivMakePass; + +PRIVATE_NAMESPACE_END diff --git a/passes/equiv/equiv_simple.cc b/passes/equiv/equiv_simple.cc new file mode 100644 index 00000000..b87f4ed7 --- /dev/null +++ b/passes/equiv/equiv_simple.cc @@ -0,0 +1,253 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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/satgen.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct EquivSimpleWorker +{ + Module *module; + Cell *equiv_cell; + + SigMap &sigmap; + dict &bit2driver; + + ezDefaultSAT ez; + SatGen satgen; + int max_seq; + + EquivSimpleWorker(Cell *equiv_cell, SigMap &sigmap, dict &bit2driver, int max_seq) : + module(equiv_cell->module), equiv_cell(equiv_cell), sigmap(sigmap), + bit2driver(bit2driver), satgen(&ez, &sigmap), max_seq(max_seq) + { + } + + void find_input_cone(pool &next_seed, pool &cells_cone, pool &bits_cone, const pool &cells_stop, const pool &bits_stop, Cell *cell) + { + if (cells_cone.count(cell)) + return; + + cells_cone.insert(cell); + + if (cells_stop.count(cell)) + return; + + for (auto &conn : cell->connections()) + if (yosys_celltypes.cell_input(cell->type, conn.first)) + for (auto bit : sigmap(conn.second)) { + if (cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_")) { + if (!conn.first.in("\\CLK", "\\C")) + next_seed.insert(bit); + } else + find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, bit); + } + } + + void find_input_cone(pool &next_seed, pool &cells_cone, pool &bits_cone, const pool &cells_stop, const pool &bits_stop, SigBit bit) + { + if (bits_cone.count(bit)) + return; + + bits_cone.insert(bit); + + if (bits_stop.count(bit)) + return; + + if (!bit2driver.count(bit)) + return; + + find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, bit2driver.at(bit)); + } + + bool run() + { + SigBit bit_a = sigmap(equiv_cell->getPort("\\A")).to_single_sigbit(); + SigBit bit_b = sigmap(equiv_cell->getPort("\\B")).to_single_sigbit(); + + int ez_a = satgen.importSigBit(bit_a, max_seq+1); + int ez_b = satgen.importSigBit(bit_b, max_seq+1); + ez.assume(ez.XOR(ez_a, ez_b)); + + pool seed_a = { bit_a }; + pool seed_b = { bit_b }; + + log(" Trying to prove $equiv cell %s:\n", log_id(equiv_cell)); + log(" A = %s, B = %s, Y = %s\n", log_signal(bit_a), log_signal(bit_b), log_signal(equiv_cell->getPort("\\Y"))); + + int step = max_seq; + while (1) + { + pool no_stop_cells; + pool no_stop_bits; + + pool full_cells_cone_a, full_cells_cone_b; + pool full_bits_cone_a, full_bits_cone_b; + + pool next_seed_a, next_seed_b; + + for (auto bit_a : seed_a) + find_input_cone(next_seed_a, full_cells_cone_a, full_bits_cone_a, no_stop_cells, no_stop_bits, bit_a); + next_seed_a.clear(); + + for (auto bit_b : seed_b) + find_input_cone(next_seed_b, full_cells_cone_b, full_bits_cone_b, no_stop_cells, no_stop_bits, bit_b); + next_seed_b.clear(); + + pool short_cells_cone_a, short_cells_cone_b; + pool short_bits_cone_a, short_bits_cone_b; + + for (auto bit_a : seed_a) + find_input_cone(next_seed_a, short_cells_cone_a, short_bits_cone_a, full_cells_cone_b, full_bits_cone_b, bit_a); + next_seed_a.swap(seed_a); + + for (auto bit_b : seed_b) + find_input_cone(next_seed_b, short_cells_cone_b, short_bits_cone_b, full_cells_cone_a, full_bits_cone_a, bit_b); + next_seed_b.swap(seed_b); + + pool problem_cells; + problem_cells.insert(short_cells_cone_a.begin(), short_cells_cone_a.end()); + problem_cells.insert(short_cells_cone_b.begin(), short_cells_cone_b.end()); + + log(" Adding %d new cells to the problem (%d A, %d B, %d shared).\n", + GetSize(problem_cells), GetSize(short_cells_cone_a), GetSize(short_cells_cone_b), + (GetSize(short_cells_cone_a) + GetSize(short_cells_cone_b)) - GetSize(problem_cells)); + + for (auto cell : problem_cells) + satgen.importCell(cell, step+1); + + log(" Problem size at t=%d: %d literals, %d clauses\n", step, ez.numCnfVariables(), ez.numCnfClauses()); + + if (!ez.solve()) { + log(" Proved equivalence! Marking $equiv cell as proven.\n"); + equiv_cell->setPort("\\B", equiv_cell->getPort("\\A")); + return true; + } + + log(" Failed to prove equivalence with sequence length %d.\n", max_seq - step); + + if (--step < 0) { + log(" Reached sequence limit.\n"); + break; + } + + if (seed_a.empty() && seed_b.empty()) { + log(" No nets to continue in previous time step.\n"); + break; + } + + if (seed_a.empty()) { + log(" No nets on A-side to continue in previous time step.\n"); + break; + } + + if (seed_b.empty()) { + log(" No nets on B-side to continue in previous time step.\n"); + break; + } + + #if 0 + log(" Continuing analysis in previous time step with the following nets:\n"); + for (auto bit : seed_a) + log(" A: %s\n", log_signal(bit)); + for (auto bit : seed_b) + log(" B: %s\n", log_signal(bit)); + #else + log(" Continuing analysis in previous time step with %d A- and %d B-nets.\n", GetSize(seed_a), GetSize(seed_b)); + #endif + } + + return false; + } +}; + +struct EquivSimplePass : public Pass { + EquivSimplePass() : Pass("equiv_simple", "try proving simple $equiv instances") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" equiv_simple [options] [selection]\n"); + log("\n"); + log("This command tries to prove $equiv cells using a simple direct SAT approach.\n"); + log("\n"); + log(" -seq \n"); + log(" the max. number of time steps to be considered (default = 1)\n"); + log("\n"); + } + virtual void execute(std::vector args, Design *design) + { + int success_counter = 0; + int max_seq = 1; + + log_header("Executing EQUIV_SIMPLE pass.\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-seq" && argidx+1 < args.size()) { + max_seq = atoi(args[++argidx].c_str()); + continue; + } + break; + } + extra_args(args, argidx, design); + + CellTypes ct; + ct.setup_internals(); + ct.setup_stdcells(); + + for (auto module : design->selected_modules()) + { + vector unproven_equiv_cells; + + for (auto cell : module->selected_cells()) + if (cell->type == "$equiv" && cell->getPort("\\A") != cell->getPort("\\B")) + unproven_equiv_cells.push_back(cell); + + if (unproven_equiv_cells.empty()) + continue; + + log("Found %d unproven $equiv cells in %s:\n", GetSize(unproven_equiv_cells), log_id(module)); + + SigMap sigmap(module); + dict bit2driver; + + for (auto cell : module->cells()) { + if (!ct.cell_known(cell->type) && !cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_")) + continue; + for (auto &conn : cell->connections()) + if (yosys_celltypes.cell_output(cell->type, conn.first)) + for (auto bit : sigmap(conn.second)) + bit2driver[bit] = cell; + } + + for (auto cell : unproven_equiv_cells) { + EquivSimpleWorker worker(cell, sigmap, bit2driver, max_seq); + if (worker.run()) + success_counter++; + } + } + + log("Proved %d previously unproven $equiv cells.\n", success_counter); + } +} EquivSimplePass; + +PRIVATE_NAMESPACE_END diff --git a/passes/equiv/equiv_status.cc b/passes/equiv/equiv_status.cc new file mode 100644 index 00000000..bcd09cd9 --- /dev/null +++ b/passes/equiv/equiv_status.cc @@ -0,0 +1,94 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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 EquivStatusPass : public Pass { + EquivStatusPass() : Pass("equiv_status", "print status of equivalent checking module") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" equiv_status [options] [selection]\n"); + log("\n"); + log("This command prints status information for all selected $equiv cells.\n"); + log("\n"); + log(" -assert\n"); + log(" produce an error if any unproven $equiv cell is found\n"); + log("\n"); + } + virtual void execute(std::vector args, Design *design) + { + bool assert_mode = false; + int unproven_count = 0; + + log_header("Executing EQUIV_STATUS pass.\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-assert") { + assert_mode = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + for (auto module : design->selected_modules()) + { + vector unproven_equiv_cells; + int proven_equiv_cells = 0; + + for (auto cell : module->selected_cells()) + if (cell->type == "$equiv") { + if (cell->getPort("\\A") != cell->getPort("\\B")) + unproven_equiv_cells.push_back(cell); + else + proven_equiv_cells++; + } + + if (unproven_equiv_cells.empty() && !proven_equiv_cells) { + log("No $equiv cells found in %s.\n", log_id(module)); + continue; + } + + log("Found %d $equiv cells found in %s:\n", GetSize(unproven_equiv_cells) + proven_equiv_cells, log_id(module)); + log(" Of those cells %d are proven and %d are unproven.\n", proven_equiv_cells, GetSize(unproven_equiv_cells)); + if (unproven_equiv_cells.empty()) { + log(" Equivalence successfully proven!\n"); + } else { + for (auto cell : unproven_equiv_cells) + log(" Unproven $equiv %s: %s %s\n", log_id(cell), log_signal(cell->getPort("\\A")), log_signal(cell->getPort("\\B"))); + } + + unproven_count += GetSize(unproven_equiv_cells); + } + + if (unproven_count != 0) { + log("Found a total of %d unproven $equiv cells.\n", unproven_count); + if (assert_mode && unproven_count != 0) + log_error("Found %d unproven $equiv cells in 'equiv_status -assert'.\n", unproven_count); + } + } +} EquivStatusPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/sat/Makefile.inc b/passes/sat/Makefile.inc index d3c323c4..4fa6bf0d 100644 --- a/passes/sat/Makefile.inc +++ b/passes/sat/Makefile.inc @@ -4,7 +4,4 @@ OBJS += passes/sat/freduce.o OBJS += passes/sat/eval.o OBJS += passes/sat/miter.o OBJS += passes/sat/expose.o -OBJS += passes/sat/equiv_make.o -OBJS += passes/sat/equiv_simple.o -OBJS += passes/sat/equiv_status.o diff --git a/passes/sat/equiv_make.cc b/passes/sat/equiv_make.cc deleted file mode 100644 index 07374cfc..00000000 --- a/passes/sat/equiv_make.cc +++ /dev/null @@ -1,248 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2012 Clifford Wolf - * - * 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/celltypes.h" - -USING_YOSYS_NAMESPACE -PRIVATE_NAMESPACE_BEGIN - -struct EquivMakeWorker -{ - Module *gold_mod, *gate_mod, *equiv_mod; - pool wire_names, cell_names; - CellTypes ct; - - void copy_to_equiv() - { - Module *gold_clone = gold_mod->clone(); - Module *gate_clone = gate_mod->clone(); - - for (auto it : gold_clone->wires().to_vector()) { if (it->name[0] == '\\') wire_names.insert(it->name); gold_clone->rename(it, it->name.str() + "_gold"); } - for (auto it : gold_clone->cells().to_vector()) { if (it->name[0] == '\\') cell_names.insert(it->name); gold_clone->rename(it, it->name.str() + "_gold"); } - for (auto it : gate_clone->wires().to_vector()) { if (it->name[0] == '\\') wire_names.insert(it->name); gate_clone->rename(it, it->name.str() + "_gate"); } - for (auto it : gate_clone->cells().to_vector()) { if (it->name[0] == '\\') cell_names.insert(it->name); gate_clone->rename(it, it->name.str() + "_gate"); } - - gold_clone->cloneInto(equiv_mod); - gate_clone->cloneInto(equiv_mod); - delete gold_clone; - delete gate_clone; - } - - void find_same_wires() - { - SigMap assign_map(equiv_mod); - SigMap rd_signal_map; - - // list of cells without added $equiv cells - auto cells_list = equiv_mod->cells().to_vector(); - - for (auto id : wire_names) - { - IdString gold_id = id.str() + "_gold"; - IdString gate_id = id.str() + "_gate"; - - Wire *gold_wire = equiv_mod->wire(gold_id); - Wire *gate_wire = equiv_mod->wire(gate_id); - - if (gold_wire == nullptr || gate_wire == nullptr || gold_wire->width != gate_wire->width) { - if (gold_wire && gold_wire->port_id) - log_error("Can't match gold port `%s' to a gate port.\n", log_id(gold_wire)); - if (gate_wire && gate_wire->port_id) - log_error("Can't match gate port `%s' to a gold port.\n", log_id(gate_wire)); - continue; - } - - log("Presumably equivalent wires: %s (%s), %s (%s) -> %s\n", - log_id(gold_wire), log_signal(assign_map(gold_wire)), - log_id(gate_wire), log_signal(assign_map(gate_wire)), log_id(id)); - - if (gold_wire->port_output || gate_wire->port_output) - { - Wire *wire = equiv_mod->addWire(id, gold_wire->width); - wire->port_output = true; - gold_wire->port_input = false; - gate_wire->port_input = false; - gold_wire->port_output = false; - gate_wire->port_output = false; - - for (int i = 0; i < wire->width; i++) - equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i)); - - rd_signal_map.add(assign_map(gold_wire), wire); - rd_signal_map.add(assign_map(gate_wire), wire); - } - else - if (gold_wire->port_input || gate_wire->port_input) - { - Wire *wire = equiv_mod->addWire(id, gold_wire->width); - wire->port_input = true; - gold_wire->port_input = false; - gate_wire->port_input = false; - equiv_mod->connect(gold_wire, wire); - equiv_mod->connect(gate_wire, wire); - } - else - { - Wire *wire = equiv_mod->addWire(id, gold_wire->width); - - for (int i = 0; i < wire->width; i++) - equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i)); - - rd_signal_map.add(assign_map(gold_wire), wire); - rd_signal_map.add(assign_map(gate_wire), wire); - } - } - - for (auto c : cells_list) - for (auto &conn : c->connections()) - if (ct.cell_input(c->type, conn.first)) { - SigSpec old_sig = assign_map(conn.second); - SigSpec new_sig = rd_signal_map(old_sig); - if (old_sig != new_sig) { - log("Changing input %s of cell %s (%s): %s -> %s\n", - log_id(conn.first), log_id(c), log_id(c->type), - log_signal(old_sig), log_signal(new_sig)); - c->setPort(conn.first, new_sig); - } - } - - equiv_mod->fixup_ports(); - } - - void find_same_cells() - { - SigMap assign_map(equiv_mod); - - for (auto id : cell_names) - { - IdString gold_id = id.str() + "_gold"; - IdString gate_id = id.str() + "_gate"; - - Cell *gold_cell = equiv_mod->cell(gold_id); - Cell *gate_cell = equiv_mod->cell(gate_id); - - if (gold_cell == nullptr || gate_cell == nullptr || gold_cell->type != gate_cell->type || !ct.cell_known(gold_cell->type) || - gold_cell->parameters != gate_cell->parameters || GetSize(gold_cell->connections()) != GetSize(gate_cell->connections())) - try_next_cell_name: - continue; - - for (auto gold_conn : gold_cell->connections()) - if (!gate_cell->connections().count(gold_conn.first)) - goto try_next_cell_name; - - log("Presumably equivalent cells: %s %s (%s) -> %s\n", - log_id(gold_cell), log_id(gate_cell), log_id(gold_cell->type), log_id(id)); - - for (auto gold_conn : gold_cell->connections()) - { - SigSpec gold_sig = assign_map(gold_conn.second); - SigSpec gate_sig = assign_map(gate_cell->getPort(gold_conn.first)); - - if (ct.cell_output(gold_cell->type, gold_conn.first)) { - equiv_mod->connect(gate_sig, gold_sig); - continue; - } - - for (int i = 0; i < GetSize(gold_sig); i++) - if (gold_sig[i] != gate_sig[i]) { - Wire *w = equiv_mod->addWire(NEW_ID); - equiv_mod->addEquiv(NEW_ID, gold_sig[i], gate_sig[i], w); - gold_sig[i] = w; - } - - gold_cell->setPort(gold_conn.first, gold_sig); - } - - equiv_mod->remove(gate_cell); - equiv_mod->rename(gold_cell, id); - } - } - - void run() - { - copy_to_equiv(); - find_same_wires(); - find_same_cells(); - } -}; - -struct EquivMakePass : public Pass { - EquivMakePass() : Pass("equiv_make", "prepare a circuit for equivalence checking") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" equiv_make [options] gold_module gate_module equiv_module\n"); - log("\n"); - log("This creates a module annotated with $equiv cells from two presumably\n"); - log("equivalent modules. Use commands such as 'equiv_simple' and 'equiv_status'\n"); - log("to work with the created equivalent checking module.\n"); - log("\n"); - log("Note: The circuit created by this command is not a miter (with something like\n"); - log("a trigger output), but instead uses $equiv cells to encode the equivalence\n"); - log("checking problem. Use 'miter -equiv' if you want to create a miter circuit.\n"); - log("\n"); - } - virtual void execute(std::vector args, RTLIL::Design *design) - { - EquivMakeWorker worker; - worker.ct.setup(design); - - size_t argidx; - for (argidx = 1; argidx < args.size(); argidx++) - { - // if (args[argidx] == "-foo" && argidx+1 < args.size()) { - // log("foo> %s\n", args[++argidx].c_str()); - // continue; - // } - break; - } - - if (argidx+3 != args.size()) - log_cmd_error("Invalid number of arguments.\n"); - - worker.gold_mod = design->module(RTLIL::escape_id(args[argidx])); - worker.gate_mod = design->module(RTLIL::escape_id(args[argidx+1])); - worker.equiv_mod = design->module(RTLIL::escape_id(args[argidx+2])); - - if (worker.gold_mod == nullptr) - log_cmd_error("Can't find gold module %s.\n", args[argidx].c_str()); - - if (worker.gate_mod == nullptr) - log_cmd_error("Can't find gate module %s.\n", args[argidx+1].c_str()); - - if (worker.equiv_mod != nullptr) - log_cmd_error("Equiv module %s already exists.\n", args[argidx+2].c_str()); - - if (worker.gold_mod->has_memories() || worker.gold_mod->has_processes()) - log_cmd_error("Gold module contains memories or procresses. Run 'memory' or 'proc' respectively.\n"); - - if (worker.gate_mod->has_memories() || worker.gate_mod->has_processes()) - log_cmd_error("Gate module contains memories or procresses. Run 'memory' or 'proc' respectively.\n"); - - log_header("Executing EQUIV_MAKE pass (creating equiv checking module).\n"); - - worker.equiv_mod = design->addModule(RTLIL::escape_id(args[argidx+2])); - worker.run(); - } -} EquivMakePass; - -PRIVATE_NAMESPACE_END diff --git a/passes/sat/equiv_simple.cc b/passes/sat/equiv_simple.cc deleted file mode 100644 index b87f4ed7..00000000 --- a/passes/sat/equiv_simple.cc +++ /dev/null @@ -1,253 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2012 Clifford Wolf - * - * 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/satgen.h" - -USING_YOSYS_NAMESPACE -PRIVATE_NAMESPACE_BEGIN - -struct EquivSimpleWorker -{ - Module *module; - Cell *equiv_cell; - - SigMap &sigmap; - dict &bit2driver; - - ezDefaultSAT ez; - SatGen satgen; - int max_seq; - - EquivSimpleWorker(Cell *equiv_cell, SigMap &sigmap, dict &bit2driver, int max_seq) : - module(equiv_cell->module), equiv_cell(equiv_cell), sigmap(sigmap), - bit2driver(bit2driver), satgen(&ez, &sigmap), max_seq(max_seq) - { - } - - void find_input_cone(pool &next_seed, pool &cells_cone, pool &bits_cone, const pool &cells_stop, const pool &bits_stop, Cell *cell) - { - if (cells_cone.count(cell)) - return; - - cells_cone.insert(cell); - - if (cells_stop.count(cell)) - return; - - for (auto &conn : cell->connections()) - if (yosys_celltypes.cell_input(cell->type, conn.first)) - for (auto bit : sigmap(conn.second)) { - if (cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_")) { - if (!conn.first.in("\\CLK", "\\C")) - next_seed.insert(bit); - } else - find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, bit); - } - } - - void find_input_cone(pool &next_seed, pool &cells_cone, pool &bits_cone, const pool &cells_stop, const pool &bits_stop, SigBit bit) - { - if (bits_cone.count(bit)) - return; - - bits_cone.insert(bit); - - if (bits_stop.count(bit)) - return; - - if (!bit2driver.count(bit)) - return; - - find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, bit2driver.at(bit)); - } - - bool run() - { - SigBit bit_a = sigmap(equiv_cell->getPort("\\A")).to_single_sigbit(); - SigBit bit_b = sigmap(equiv_cell->getPort("\\B")).to_single_sigbit(); - - int ez_a = satgen.importSigBit(bit_a, max_seq+1); - int ez_b = satgen.importSigBit(bit_b, max_seq+1); - ez.assume(ez.XOR(ez_a, ez_b)); - - pool seed_a = { bit_a }; - pool seed_b = { bit_b }; - - log(" Trying to prove $equiv cell %s:\n", log_id(equiv_cell)); - log(" A = %s, B = %s, Y = %s\n", log_signal(bit_a), log_signal(bit_b), log_signal(equiv_cell->getPort("\\Y"))); - - int step = max_seq; - while (1) - { - pool no_stop_cells; - pool no_stop_bits; - - pool full_cells_cone_a, full_cells_cone_b; - pool full_bits_cone_a, full_bits_cone_b; - - pool next_seed_a, next_seed_b; - - for (auto bit_a : seed_a) - find_input_cone(next_seed_a, full_cells_cone_a, full_bits_cone_a, no_stop_cells, no_stop_bits, bit_a); - next_seed_a.clear(); - - for (auto bit_b : seed_b) - find_input_cone(next_seed_b, full_cells_cone_b, full_bits_cone_b, no_stop_cells, no_stop_bits, bit_b); - next_seed_b.clear(); - - pool short_cells_cone_a, short_cells_cone_b; - pool short_bits_cone_a, short_bits_cone_b; - - for (auto bit_a : seed_a) - find_input_cone(next_seed_a, short_cells_cone_a, short_bits_cone_a, full_cells_cone_b, full_bits_cone_b, bit_a); - next_seed_a.swap(seed_a); - - for (auto bit_b : seed_b) - find_input_cone(next_seed_b, short_cells_cone_b, short_bits_cone_b, full_cells_cone_a, full_bits_cone_a, bit_b); - next_seed_b.swap(seed_b); - - pool problem_cells; - problem_cells.insert(short_cells_cone_a.begin(), short_cells_cone_a.end()); - problem_cells.insert(short_cells_cone_b.begin(), short_cells_cone_b.end()); - - log(" Adding %d new cells to the problem (%d A, %d B, %d shared).\n", - GetSize(problem_cells), GetSize(short_cells_cone_a), GetSize(short_cells_cone_b), - (GetSize(short_cells_cone_a) + GetSize(short_cells_cone_b)) - GetSize(problem_cells)); - - for (auto cell : problem_cells) - satgen.importCell(cell, step+1); - - log(" Problem size at t=%d: %d literals, %d clauses\n", step, ez.numCnfVariables(), ez.numCnfClauses()); - - if (!ez.solve()) { - log(" Proved equivalence! Marking $equiv cell as proven.\n"); - equiv_cell->setPort("\\B", equiv_cell->getPort("\\A")); - return true; - } - - log(" Failed to prove equivalence with sequence length %d.\n", max_seq - step); - - if (--step < 0) { - log(" Reached sequence limit.\n"); - break; - } - - if (seed_a.empty() && seed_b.empty()) { - log(" No nets to continue in previous time step.\n"); - break; - } - - if (seed_a.empty()) { - log(" No nets on A-side to continue in previous time step.\n"); - break; - } - - if (seed_b.empty()) { - log(" No nets on B-side to continue in previous time step.\n"); - break; - } - - #if 0 - log(" Continuing analysis in previous time step with the following nets:\n"); - for (auto bit : seed_a) - log(" A: %s\n", log_signal(bit)); - for (auto bit : seed_b) - log(" B: %s\n", log_signal(bit)); - #else - log(" Continuing analysis in previous time step with %d A- and %d B-nets.\n", GetSize(seed_a), GetSize(seed_b)); - #endif - } - - return false; - } -}; - -struct EquivSimplePass : public Pass { - EquivSimplePass() : Pass("equiv_simple", "try proving simple $equiv instances") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" equiv_simple [options] [selection]\n"); - log("\n"); - log("This command tries to prove $equiv cells using a simple direct SAT approach.\n"); - log("\n"); - log(" -seq \n"); - log(" the max. number of time steps to be considered (default = 1)\n"); - log("\n"); - } - virtual void execute(std::vector args, Design *design) - { - int success_counter = 0; - int max_seq = 1; - - log_header("Executing EQUIV_SIMPLE pass.\n"); - - size_t argidx; - for (argidx = 1; argidx < args.size(); argidx++) { - if (args[argidx] == "-seq" && argidx+1 < args.size()) { - max_seq = atoi(args[++argidx].c_str()); - continue; - } - break; - } - extra_args(args, argidx, design); - - CellTypes ct; - ct.setup_internals(); - ct.setup_stdcells(); - - for (auto module : design->selected_modules()) - { - vector unproven_equiv_cells; - - for (auto cell : module->selected_cells()) - if (cell->type == "$equiv" && cell->getPort("\\A") != cell->getPort("\\B")) - unproven_equiv_cells.push_back(cell); - - if (unproven_equiv_cells.empty()) - continue; - - log("Found %d unproven $equiv cells in %s:\n", GetSize(unproven_equiv_cells), log_id(module)); - - SigMap sigmap(module); - dict bit2driver; - - for (auto cell : module->cells()) { - if (!ct.cell_known(cell->type) && !cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_")) - continue; - for (auto &conn : cell->connections()) - if (yosys_celltypes.cell_output(cell->type, conn.first)) - for (auto bit : sigmap(conn.second)) - bit2driver[bit] = cell; - } - - for (auto cell : unproven_equiv_cells) { - EquivSimpleWorker worker(cell, sigmap, bit2driver, max_seq); - if (worker.run()) - success_counter++; - } - } - - log("Proved %d previously unproven $equiv cells.\n", success_counter); - } -} EquivSimplePass; - -PRIVATE_NAMESPACE_END diff --git a/passes/sat/equiv_status.cc b/passes/sat/equiv_status.cc deleted file mode 100644 index bcd09cd9..00000000 --- a/passes/sat/equiv_status.cc +++ /dev/null @@ -1,94 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2012 Clifford Wolf - * - * 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 EquivStatusPass : public Pass { - EquivStatusPass() : Pass("equiv_status", "print status of equivalent checking module") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" equiv_status [options] [selection]\n"); - log("\n"); - log("This command prints status information for all selected $equiv cells.\n"); - log("\n"); - log(" -assert\n"); - log(" produce an error if any unproven $equiv cell is found\n"); - log("\n"); - } - virtual void execute(std::vector args, Design *design) - { - bool assert_mode = false; - int unproven_count = 0; - - log_header("Executing EQUIV_STATUS pass.\n"); - - size_t argidx; - for (argidx = 1; argidx < args.size(); argidx++) { - if (args[argidx] == "-assert") { - assert_mode = true; - continue; - } - break; - } - extra_args(args, argidx, design); - - for (auto module : design->selected_modules()) - { - vector unproven_equiv_cells; - int proven_equiv_cells = 0; - - for (auto cell : module->selected_cells()) - if (cell->type == "$equiv") { - if (cell->getPort("\\A") != cell->getPort("\\B")) - unproven_equiv_cells.push_back(cell); - else - proven_equiv_cells++; - } - - if (unproven_equiv_cells.empty() && !proven_equiv_cells) { - log("No $equiv cells found in %s.\n", log_id(module)); - continue; - } - - log("Found %d $equiv cells found in %s:\n", GetSize(unproven_equiv_cells) + proven_equiv_cells, log_id(module)); - log(" Of those cells %d are proven and %d are unproven.\n", proven_equiv_cells, GetSize(unproven_equiv_cells)); - if (unproven_equiv_cells.empty()) { - log(" Equivalence successfully proven!\n"); - } else { - for (auto cell : unproven_equiv_cells) - log(" Unproven $equiv %s: %s %s\n", log_id(cell), log_signal(cell->getPort("\\A")), log_signal(cell->getPort("\\B"))); - } - - unproven_count += GetSize(unproven_equiv_cells); - } - - if (unproven_count != 0) { - log("Found a total of %d unproven $equiv cells.\n", unproven_count); - if (assert_mode && unproven_count != 0) - log_error("Found %d unproven $equiv cells in 'equiv_status -assert'.\n", unproven_count); - } - } -} EquivStatusPass; - -PRIVATE_NAMESPACE_END -- cgit v1.2.3