passes/equiv/equiv_simple.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   5  *
   6  *  Permission to use, copy, modify, and/or distribute this software for any
   7  *  purpose with or without fee is hereby granted, provided that the above
   8  *  copyright notice and this permission notice appear in all copies.
   9  *
  10  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  */
  19
  20 #include "kernel/yosys.h"
  21 #include "kernel/satgen.h"
  22
  23 USING_YOSYS_NAMESPACE
  24 PRIVATE_NAMESPACE_BEGIN
  25
  26 struct EquivSimpleWorker
  27 {
  28         Module *module;
  29         const vector<Cell*> &equiv_cells;
  30         Cell *equiv_cell;
  31
  32         SigMap &sigmap;
  33         dict<SigBit, Cell*> &bit2driver;
  34
  35         ezSatPtr ez;
  36         SatGen satgen;
  37         int max_seq;
  38         bool verbose;
  39
  40         pool<pair<Cell*, int>> imported_cells_cache;
  41
  42         EquivSimpleWorker(const vector<Cell*> &equiv_cells, SigMap &sigmap, dict<SigBit, Cell*> &bit2driver, int max_seq, bool verbose, bool model_undef) :
  43                         module(equiv_cells.front()->module), equiv_cells(equiv_cells), equiv_cell(nullptr),
  44                         sigmap(sigmap), bit2driver(bit2driver), satgen(ez.get(), &sigmap), max_seq(max_seq), verbose(verbose)
  45         {
  46                 satgen.model_undef = model_undef;
  47         }
  48
  49         bool 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, pool<SigBit> *input_bits, Cell *cell)
  50         {
  51                 if (cells_cone.count(cell))
  52                         return false;
  53
  54                 cells_cone.insert(cell);
  55
  56                 if (cells_stop.count(cell))
  57                         return true;
  58
  59                 for (auto &conn : cell->connections())
  60                         if (yosys_celltypes.cell_input(cell->type, conn.first))
  61                                 for (auto bit : sigmap(conn.second)) {
  62                                         if (cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_")) {
  63                                                 if (!conn.first.in("\\CLK", "\\C"))
  64                                                         next_seed.insert(bit);
  65                                         } else
  66                                                 find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, input_bits, bit);
  67                                 }
  68                 return false;
  69         }
  70
  71         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, pool<SigBit> *input_bits, SigBit bit)
  72         {
  73                 if (bits_cone.count(bit))
  74                         return;
  75
  76                 bits_cone.insert(bit);
  77
  78                 if (bits_stop.count(bit)) {
  79                         if (input_bits != nullptr) input_bits->insert(bit);
  80                         return;
  81                 }
  82
  83                 if (!bit2driver.count(bit))
  84                         return;
  85
  86                 if (find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, input_bits, bit2driver.at(bit)))
  87                         if (input_bits != nullptr) input_bits->insert(bit);
  88         }
  89
  90         bool run_cell()
  91         {
  92                 SigBit bit_a = sigmap(equiv_cell->getPort("\\A")).as_bit();
  93                 SigBit bit_b = sigmap(equiv_cell->getPort("\\B")).as_bit();
  94                 int ez_context = ez->frozen_literal();
  95
  96                 if (satgen.model_undef)
  97                 {
  98                         int ez_a = satgen.importSigBit(bit_a, max_seq+1);
  99                         int ez_b = satgen.importDefSigBit(bit_b, max_seq+1);
 100                         int ez_undef_a = satgen.importUndefSigBit(bit_a, max_seq+1);
 101
 102                         ez->assume(ez->XOR(ez_a, ez_b), ez_context);
 103                         ez->assume(ez->NOT(ez_undef_a), ez_context);
 104                 }
 105                 else
 106                 {
 107                         int ez_a = satgen.importSigBit(bit_a, max_seq+1);
 108                         int ez_b = satgen.importSigBit(bit_b, max_seq+1);
 109                         ez->assume(ez->XOR(ez_a, ez_b), ez_context);
 110                 }
 111
 112                 pool<SigBit> seed_a = { bit_a };
 113                 pool<SigBit> seed_b = { bit_b };
 114
 115                 if (verbose) {
 116                         log("  Trying to prove $equiv cell %s:\n", log_id(equiv_cell));
 117                         log("    A = %s, B = %s, Y = %s\n", log_signal(bit_a), log_signal(bit_b), log_signal(equiv_cell->getPort("\\Y")));
 118                 } else {
 119                         log("  Trying to prove $equiv for %s:", log_signal(equiv_cell->getPort("\\Y")));
 120                 }
 121
 122                 int step = max_seq;
 123                 while (1)
 124                 {
 125                         pool<Cell*> no_stop_cells;
 126                         pool<SigBit> no_stop_bits;
 127
 128                         pool<Cell*> full_cells_cone_a, full_cells_cone_b;
 129                         pool<SigBit> full_bits_cone_a, full_bits_cone_b;
 130
 131                         pool<SigBit> next_seed_a, next_seed_b;
 132
 133                         for (auto bit_a : seed_a)
 134                                 find_input_cone(next_seed_a, full_cells_cone_a, full_bits_cone_a, no_stop_cells, no_stop_bits, nullptr, bit_a);
 135                         next_seed_a.clear();
 136
 137                         for (auto bit_b : seed_b)
 138                                 find_input_cone(next_seed_b, full_cells_cone_b, full_bits_cone_b, no_stop_cells, no_stop_bits, nullptr, bit_b);
 139                         next_seed_b.clear();
 140
 141                         pool<Cell*> short_cells_cone_a, short_cells_cone_b;
 142                         pool<SigBit> short_bits_cone_a, short_bits_cone_b;
 143                         pool<SigBit> input_bits;
 144
 145                         for (auto bit_a : seed_a)
 146                                 find_input_cone(next_seed_a, short_cells_cone_a, short_bits_cone_a, full_cells_cone_b, full_bits_cone_b, &input_bits, bit_a);
 147                         next_seed_a.swap(seed_a);
 148
 149                         for (auto bit_b : seed_b)
 150                                 find_input_cone(next_seed_b, short_cells_cone_b, short_bits_cone_b, full_cells_cone_a, full_bits_cone_a, &input_bits, bit_b);
 151                         next_seed_b.swap(seed_b);
 152
 153                         pool<Cell*> problem_cells;
 154                         problem_cells.insert(short_cells_cone_a.begin(), short_cells_cone_a.end());
 155                         problem_cells.insert(short_cells_cone_b.begin(), short_cells_cone_b.end());
 156
 157                         if (verbose)
 158                                 log("    Adding %d new cells to the problem (%d A, %d B, %d shared).\n",
 159                                                 GetSize(problem_cells), GetSize(short_cells_cone_a), GetSize(short_cells_cone_b),
 160                                                 (GetSize(short_cells_cone_a) + GetSize(short_cells_cone_b)) - GetSize(problem_cells));
 161
 162                         for (auto cell : problem_cells) {
 163                                 auto key = pair<Cell*, int>(cell, step+1);
 164                                 if (!imported_cells_cache.count(key) && !satgen.importCell(cell, step+1))
 165                                         log_cmd_error("No SAT model available for cell %s (%s).\n", log_id(cell), log_id(cell->type));
 166                                 imported_cells_cache.insert(key);
 167                         }
 168
 169                         if (satgen.model_undef) {
 170                                 for (auto bit : input_bits)
 171                                         ez->assume(ez->NOT(satgen.importUndefSigBit(bit, step+1)));
 172                         }
 173
 174                         if (verbose)
 175                                 log("    Problem size at t=%d: %d literals, %d clauses\n", step, ez->numCnfVariables(), ez->numCnfClauses());
 176
 177                         if (!ez->solve(ez_context)) {
 178                                 log(verbose ? "    Proved equivalence! Marking $equiv cell as proven.\n" : " success!\n");
 179                                 equiv_cell->setPort("\\B", equiv_cell->getPort("\\A"));
 180                                 ez->assume(ez->NOT(ez_context));
 181                                 return true;
 182                         }
 183
 184                         if (verbose)
 185                                 log("    Failed to prove equivalence with sequence length %d.\n", max_seq - step);
 186
 187                         if (--step < 0) {
 188                                 if (verbose)
 189                                         log("    Reached sequence limit.\n");
 190                                 break;
 191                         }
 192
 193                         if (seed_a.empty() && seed_b.empty()) {
 194                                 if (verbose)
 195                                         log("    No nets to continue in previous time step.\n");
 196                                 break;
 197                         }
 198
 199                         if (seed_a.empty()) {
 200                                 if (verbose)
 201                                         log("    No nets on A-side to continue in previous time step.\n");
 202                                 break;
 203                         }
 204
 205                         if (seed_b.empty()) {
 206                                 if (verbose)
 207                                         log("    No nets on B-side to continue in previous time step.\n");
 208                                 break;
 209                         }
 210
 211                         if (verbose) {
 212                         #if 0
 213                                 log("    Continuing analysis in previous time step with the following nets:\n");
 214                                 for (auto bit : seed_a)
 215                                         log("      A: %s\n", log_signal(bit));
 216                                 for (auto bit : seed_b)
 217                                         log("      B: %s\n", log_signal(bit));
 218                         #else
 219                                 log("    Continuing analysis in previous time step with %d A- and %d B-nets.\n", GetSize(seed_a), GetSize(seed_b));
 220                         #endif
 221                         }
 222                 }
 223
 224                 if (!verbose)
 225                         log(" failed.\n");
 226
 227                 ez->assume(ez->NOT(ez_context));
 228                 return false;
 229         }
 230
 231         int run()
 232         {
 233                 if (GetSize(equiv_cells) > 1) {
 234                         SigSpec sig;
 235                         for (auto c : equiv_cells)
 236                                 sig.append(sigmap(c->getPort("\\Y")));
 237                         log(" Grouping SAT models for %s:\n", log_signal(sig));
 238                 }
 239
 240                 int counter = 0;
 241                 for (auto c : equiv_cells) {
 242                         equiv_cell = c;
 243                         if (run_cell())
 244                                 counter++;
 245                 }
 246                 return counter;
 247         }
 248
 249 };
 250
 251 struct EquivSimplePass : public Pass {
 252         EquivSimplePass() : Pass("equiv_simple", "try proving simple $equiv instances") { }
 253         virtual void help()
 254         {
 255                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 256                 log("\n");
 257                 log("    equiv_simple [options] [selection]\n");
 258                 log("\n");
 259                 log("This command tries to prove $equiv cells using a simple direct SAT approach.\n");
 260                 log("\n");
 261                 log("    -v\n");
 262                 log("        verbose output\n");
 263                 log("\n");
 264                 log("    -undef\n");
 265                 log("        enable modelling of undef states\n");
 266                 log("\n");
 267                 log("    -nogroup\n");
 268                 log("        disabling grouping of $equiv cells by output wire\n");
 269                 log("\n");
 270                 log("    -seq <N>\n");
 271                 log("        the max. number of time steps to be considered (default = 1)\n");
 272                 log("\n");
 273         }
 274         virtual void execute(std::vector<std::string> args, Design *design)
 275         {
 276                 bool verbose = false, model_undef = false, nogroup = false;
 277                 int success_counter = 0;
 278                 int max_seq = 1;
 279
 280                 log_header("Executing EQUIV_SIMPLE pass.\n");
 281
 282                 size_t argidx;
 283                 for (argidx = 1; argidx < args.size(); argidx++) {
 284                         if (args[argidx] == "-v") {
 285                                 verbose = true;
 286                                 continue;
 287                         }
 288                         if (args[argidx] == "-undef") {
 289                                 model_undef = true;
 290                                 continue;
 291                         }
 292                         if (args[argidx] == "-nogroup") {
 293                                 nogroup = true;
 294                                 continue;
 295                         }
 296                         if (args[argidx] == "-seq" && argidx+1 < args.size()) {
 297                                 max_seq = atoi(args[++argidx].c_str());
 298                                 continue;
 299                         }
 300                         break;
 301                 }
 302                 extra_args(args, argidx, design);
 303
 304                 CellTypes ct;
 305                 ct.setup_internals();
 306                 ct.setup_stdcells();
 307
 308                 for (auto module : design->selected_modules())
 309                 {
 310                         SigMap sigmap(module);
 311                         dict<SigBit, Cell*> bit2driver;
 312                         dict<SigBit, dict<SigBit, Cell*>> unproven_equiv_cells;
 313                         int unproven_cells_counter = 0;
 314
 315                         for (auto cell : module->selected_cells())
 316                                 if (cell->type == "$equiv" && cell->getPort("\\A") != cell->getPort("\\B")) {
 317                                         auto bit = sigmap(cell->getPort("\\Y").as_bit());
 318                                         auto bit_group = bit;
 319                                         if (!nogroup && bit_group.wire)
 320                                                 bit_group.offset = 0;
 321                                         unproven_equiv_cells[bit_group][bit] = cell;
 322                                         unproven_cells_counter++;
 323                                 }
 324
 325                         if (unproven_equiv_cells.empty())
 326                                 continue;
 327
 328                         log("Found %d unproven $equiv cells (%d groups) in %s:\n",
 329                                         unproven_cells_counter, GetSize(unproven_equiv_cells), log_id(module));
 330
 331                         for (auto cell : module->cells()) {
 332                                 if (!ct.cell_known(cell->type) && !cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_"))
 333                                         continue;
 334                                 for (auto &conn : cell->connections())
 335                                         if (yosys_celltypes.cell_output(cell->type, conn.first))
 336                                                 for (auto bit : sigmap(conn.second))
 337                                                         bit2driver[bit] = cell;
 338                         }
 339
 340                         unproven_equiv_cells.sort();
 341                         for (auto it : unproven_equiv_cells)
 342                         {
 343                                 it.second.sort();
 344
 345                                 vector<Cell*> cells;
 346                                 for (auto it2 : it.second)
 347                                         cells.push_back(it2.second);
 348
 349                                 EquivSimpleWorker worker(cells, sigmap, bit2driver, max_seq, verbose, model_undef);
 350                                 success_counter += worker.run();
 351                         }
 352                 }
 353
 354                 log("Proved %d previously unproven $equiv cells.\n", success_counter);
 355         }
 356 } EquivSimplePass;
 357
 358 PRIVATE_NAMESPACE_END