diff options
Diffstat (limited to 'passes/equiv')
| -rw-r--r-- | passes/equiv/Makefile.inc | 5 | ||||
| -rw-r--r-- | passes/equiv/equiv_make.cc | 248 | ||||
| -rw-r--r-- | passes/equiv/equiv_simple.cc | 253 | ||||
| -rw-r--r-- | passes/equiv/equiv_status.cc | 94 |
4 files changed, 600 insertions, 0 deletions
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 <clifford@clifford.at> + * + * 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<IdString> 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<std::string> 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 <clifford@clifford.at> + * + * 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<SigBit, Cell*> &bit2driver; + + ezDefaultSAT ez; + SatGen satgen; + int max_seq; + + EquivSimpleWorker(Cell *equiv_cell, SigMap &sigmap, dict<SigBit, Cell*> &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<SigBit> &next_seed, pool<Cell*> &cells_cone, pool<SigBit> &bits_cone, const pool<Cell*> &cells_stop, const pool<SigBit> &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<SigBit> &next_seed, pool<Cell*> &cells_cone, pool<SigBit> &bits_cone, const pool<Cell*> &cells_stop, const pool<SigBit> &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<SigBit> seed_a = { bit_a }; + pool<SigBit> 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<Cell*> no_stop_cells; + pool<SigBit> no_stop_bits; + + pool<Cell*> full_cells_cone_a, full_cells_cone_b; + pool<SigBit> full_bits_cone_a, full_bits_cone_b; + + pool<SigBit> 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<Cell*> short_cells_cone_a, short_cells_cone_b; + pool<SigBit> 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<Cell*> 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>\n"); + log(" the max. number of time steps to be considered (default = 1)\n"); + log("\n"); + } + virtual void execute(std::vector<std::string> 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<Cell*> 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<SigBit, Cell*> 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 <clifford@clifford.at> + * + * 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<std::string> 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<Cell*> 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 |