From 5febbe3620d361b3fe2f5300a985da2a593cccfb Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Mon, 19 Jan 2015 15:08:44 +0100 Subject: [PATCH] Added equiv_simple --- passes/sat/Makefile.inc | 1 + passes/sat/equiv_simple.cc | 187 +++++++++++++++++++++++++++++++++++++ 2 files changed, 188 insertions(+) create mode 100644 passes/sat/equiv_simple.cc diff --git a/passes/sat/Makefile.inc b/passes/sat/Makefile.inc index 18bd6561e..d3c323c4b 100644 --- a/passes/sat/Makefile.inc +++ b/passes/sat/Makefile.inc @@ -5,5 +5,6 @@ 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_simple.cc b/passes/sat/equiv_simple.cc new file mode 100644 index 000000000..ffc1e3f5b --- /dev/null +++ b/passes/sat/equiv_simple.cc @@ -0,0 +1,187 @@ +/* + * 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; + + EquivSimpleWorker(Cell *equiv_cell, SigMap &sigmap, dict &bit2driver) : + module(equiv_cell->module), equiv_cell(equiv_cell), sigmap(sigmap), + bit2driver(bit2driver), satgen(&ez, &sigmap) + { + } + + void find_input_cone(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)) + find_input_cone(cells_cone, bits_cone, cells_stop, bits_stop, bit); + } + + void find_input_cone(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(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(); + + 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"))); + + 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; + + find_input_cone(full_cells_cone_a, full_bits_cone_a, no_stop_cells, no_stop_bits, bit_a); + find_input_cone(full_cells_cone_b, full_bits_cone_b, no_stop_cells, no_stop_bits, bit_b); + + pool short_cells_cone_a, short_cells_cone_b; + pool short_bits_cone_a, short_bits_cone_b; + + find_input_cone(short_cells_cone_a, short_bits_cone_a, full_cells_cone_b, full_bits_cone_b, bit_a); + find_input_cone(short_cells_cone_b, short_bits_cone_b, full_cells_cone_a, full_bits_cone_a, bit_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()); + for (auto cell : problem_cells) satgen.importCell(cell); + + int ez_a = satgen.importSigBit(bit_a); + int ez_b = satgen.importSigBit(bit_b); + ez.assume(ez.XOR(ez_a, ez_b)); + + log(" Created SAT problem from %d cells.\n", GetSize(problem_cells)); + + 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.\n"); + 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"); + } + virtual void execute(std::vector args, Design *design) + { + int success_counter = 0; + + log_header("Executing EQUIV_SIMPLE 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); + + 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->selected_cells()) { + if (!ct.cell_known(cell->type)) + continue; + for (auto &conn : cell->connections()) + if (ct.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); + if (worker.run()) + success_counter++; + } + } + + log("Successfully proved %d previously unproven $equiv cells.\n", success_counter); + } +} EquivSimplePass; + +PRIVATE_NAMESPACE_END -- 2.30.2