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 short_cones;
  39         bool verbose;
  40
  41         pool<pair<Cell*, int>> imported_cells_cache;
  42
  43         EquivSimpleWorker(const vector<Cell*> &equiv_cells, SigMap &sigmap, dict<SigBit, Cell*> &bit2driver, int max_seq, bool short_cones, bool verbose, bool model_undef) :
  44                         module(equiv_cells.front()->module), equiv_cells(equiv_cells), equiv_cell(nullptr),
  45                         sigmap(sigmap), bit2driver(bit2driver), satgen(ez.get(), &sigmap), max_seq(max_seq), short_cones(short_cones), verbose(verbose)
  46         {
  47                 satgen.model_undef = model_undef;
  48         }
  49
  50         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)
  51         {
  52                 if (cells_cone.count(cell))
  53                         return false;
  54
  55                 cells_cone.insert(cell);
  56
  57                 if (cells_stop.count(cell))
  58                         return true;
  59
  60                 for (auto &conn : cell->connections())
  61                         if (yosys_celltypes.cell_input(cell->type, conn.first))
  62                                 for (auto bit : sigmap(conn.second)) {
  63                                         if (cell->type.in(ID($dff), ID($_DFF_P_), ID($_DFF_N_), ID($ff), ID($_FF_))) {
  64                                                 if (!conn.first.in(ID::CLK, ID::C))
  65                                                         next_seed.insert(bit);
  66                                         } else
  67                                                 find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, input_bits, bit);
  68                                 }
  69                 return false;
  70         }
  71
  72         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)
  73         {
  74                 if (bits_cone.count(bit))
  75                         return;
  76
  77                 bits_cone.insert(bit);
  78
  79                 if (bits_stop.count(bit)) {
  80                         if (input_bits != nullptr) input_bits->insert(bit);
  81                         return;
  82                 }
  83
  84                 if (!bit2driver.count(bit))
  85                         return;
  86
  87                 if (find_input_cone(next_seed, cells_cone, bits_cone, cells_stop, bits_stop, input_bits, bit2driver.at(bit)))
  88                         if (input_bits != nullptr) input_bits->insert(bit);
  89         }
  90
  91         bool run_cell()
  92         {
  93                 SigBit bit_a = sigmap(equiv_cell->getPort(ID::A)).as_bit();
  94                 SigBit bit_b = sigmap(equiv_cell->getPort(ID::B)).as_bit();
  95                 int ez_context = ez->frozen_literal();
  96
  97                 if (satgen.model_undef)
  98                 {
  99                         int ez_a = satgen.importSigBit(bit_a, max_seq+1);
 100                         int ez_b = satgen.importDefSigBit(bit_b, max_seq+1);
 101                         int ez_undef_a = satgen.importUndefSigBit(bit_a, max_seq+1);
 102
 103                         ez->assume(ez->XOR(ez_a, ez_b), ez_context);
 104                         ez->assume(ez->NOT(ez_undef_a), ez_context);
 105                 }
 106                 else
 107                 {
 108                         int ez_a = satgen.importSigBit(bit_a, max_seq+1);
 109                         int ez_b = satgen.importSigBit(bit_b, max_seq+1);
 110                         ez->assume(ez->XOR(ez_a, ez_b), ez_context);
 111                 }
 112
 113                 pool<SigBit> seed_a = { bit_a };
 114                 pool<SigBit> seed_b = { bit_b };
 115
 116                 if (verbose) {
 117                         log("  Trying to prove $equiv cell %s:\n", log_id(equiv_cell));
 118                         log("    A = %s, B = %s, Y = %s\n", log_signal(bit_a), log_signal(bit_b), log_signal(equiv_cell->getPort(ID::Y)));
 119                 } else {
 120                         log("  Trying to prove $equiv for %s:", log_signal(equiv_cell->getPort(ID::Y)));
 121                 }
 122
 123                 int step = max_seq;
 124                 while (1)
 125                 {
 126                         pool<Cell*> no_stop_cells;
 127                         pool<SigBit> no_stop_bits;
 128
 129                         pool<Cell*> full_cells_cone_a, full_cells_cone_b;
 130                         pool<SigBit> full_bits_cone_a, full_bits_cone_b;
 131
 132                         pool<SigBit> next_seed_a, next_seed_b;
 133
 134                         for (auto bit_a : seed_a)
 135                                 find_input_cone(next_seed_a, full_cells_cone_a, full_bits_cone_a, no_stop_cells, no_stop_bits, nullptr, bit_a);
 136                         next_seed_a.clear();
 137
 138                         for (auto bit_b : seed_b)
 139                                 find_input_cone(next_seed_b, full_cells_cone_b, full_bits_cone_b, no_stop_cells, no_stop_bits, nullptr, bit_b);
 140                         next_seed_b.clear();
 141
 142                         pool<Cell*> short_cells_cone_a, short_cells_cone_b;
 143                         pool<SigBit> short_bits_cone_a, short_bits_cone_b;
 144                         pool<SigBit> input_bits;
 145
 146                         if (short_cones)
 147                         {
 148                                 for (auto bit_a : seed_a)
 149                                         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);
 150                                 next_seed_a.swap(seed_a);
 151
 152                                 for (auto bit_b : seed_b)
 153                                         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);
 154                                 next_seed_b.swap(seed_b);
 155                         }
 156                         else
 157                         {
 158                                 short_cells_cone_a = full_cells_cone_a;
 159                                 short_bits_cone_a = full_bits_cone_a;
 160                                 next_seed_a.swap(seed_a);
 161
 162                                 short_cells_cone_b = full_cells_cone_b;
 163                                 short_bits_cone_b = full_bits_cone_b;
 164                                 next_seed_b.swap(seed_b);
 165                         }
 166
 167                         pool<Cell*> problem_cells;
 168                         problem_cells.insert(short_cells_cone_a.begin(), short_cells_cone_a.end());
 169                         problem_cells.insert(short_cells_cone_b.begin(), short_cells_cone_b.end());
 170
 171                         if (verbose)
 172                         {
 173                                 log("    Adding %d new cells to the problem (%d A, %d B, %d shared).\n",
 174                                                 GetSize(problem_cells), GetSize(short_cells_cone_a), GetSize(short_cells_cone_b),
 175                                                 (GetSize(short_cells_cone_a) + GetSize(short_cells_cone_b)) - GetSize(problem_cells));
 176                         #if 0
 177                                 for (auto cell : short_cells_cone_a)
 178                                         log("      A-side cell: %s\n", log_id(cell));
 179
 180                                 for (auto cell : short_cells_cone_b)
 181                                         log("      B-side cell: %s\n", log_id(cell));
 182                         #endif
 183                         }
 184
 185                         for (auto cell : problem_cells) {
 186                                 auto key = pair<Cell*, int>(cell, step+1);
 187                                 if (!imported_cells_cache.count(key) && !satgen.importCell(cell, step+1))
 188                                         log_cmd_error("No SAT model available for cell %s (%s).\n", log_id(cell), log_id(cell->type));
 189                                 imported_cells_cache.insert(key);
 190                         }
 191
 192                         if (satgen.model_undef) {
 193                                 for (auto bit : input_bits)
 194                                         ez->assume(ez->NOT(satgen.importUndefSigBit(bit, step+1)));
 195                         }
 196
 197                         if (verbose)
 198                                 log("    Problem size at t=%d: %d literals, %d clauses\n", step, ez->numCnfVariables(), ez->numCnfClauses());
 199
 200                         if (!ez->solve(ez_context)) {
 201                                 log(verbose ? "    Proved equivalence! Marking $equiv cell as proven.\n" : " success!\n");
 202                                 equiv_cell->setPort(ID::B, equiv_cell->getPort(ID::A));
 203                                 ez->assume(ez->NOT(ez_context));
 204                                 return true;
 205                         }
 206
 207                         if (verbose)
 208                                 log("    Failed to prove equivalence with sequence length %d.\n", max_seq - step);
 209
 210                         if (--step < 0) {
 211                                 if (verbose)
 212                                         log("    Reached sequence limit.\n");
 213                                 break;
 214                         }
 215
 216                         if (seed_a.empty() && seed_b.empty()) {
 217                                 if (verbose)
 218                                         log("    No nets to continue in previous time step.\n");
 219                                 break;
 220                         }
 221
 222                         if (seed_a.empty()) {
 223                                 if (verbose)
 224                                         log("    No nets on A-side to continue in previous time step.\n");
 225                                 break;
 226                         }
 227
 228                         if (seed_b.empty()) {
 229                                 if (verbose)
 230                                         log("    No nets on B-side to continue in previous time step.\n");
 231                                 break;
 232                         }
 233
 234                         if (verbose) {
 235                         #if 0
 236                                 log("    Continuing analysis in previous time step with the following nets:\n");
 237                                 for (auto bit : seed_a)
 238                                         log("      A: %s\n", log_signal(bit));
 239                                 for (auto bit : seed_b)
 240                                         log("      B: %s\n", log_signal(bit));
 241                         #else
 242                                 log("    Continuing analysis in previous time step with %d A- and %d B-nets.\n", GetSize(seed_a), GetSize(seed_b));
 243                         #endif
 244                         }
 245                 }
 246
 247                 if (!verbose)
 248                         log(" failed.\n");
 249
 250                 ez->assume(ez->NOT(ez_context));
 251                 return false;
 252         }
 253
 254         int run()
 255         {
 256                 if (GetSize(equiv_cells) > 1) {
 257                         SigSpec sig;
 258                         for (auto c : equiv_cells)
 259                                 sig.append(sigmap(c->getPort(ID::Y)));
 260                         log(" Grouping SAT models for %s:\n", log_signal(sig));
 261                 }
 262
 263                 int counter = 0;
 264                 for (auto c : equiv_cells) {
 265                         equiv_cell = c;
 266                         if (run_cell())
 267                                 counter++;
 268                 }
 269                 return counter;
 270         }
 271
 272 };
 273
 274 struct EquivSimplePass : public Pass {
 275         EquivSimplePass() : Pass("equiv_simple", "try proving simple $equiv instances") { }
 276         void help() YS_OVERRIDE
 277         {
 278                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 279                 log("\n");
 280                 log("    equiv_simple [options] [selection]\n");
 281                 log("\n");
 282                 log("This command tries to prove $equiv cells using a simple direct SAT approach.\n");
 283                 log("\n");
 284                 log("    -v\n");
 285                 log("        verbose output\n");
 286                 log("\n");
 287                 log("    -undef\n");
 288                 log("        enable modelling of undef states\n");
 289                 log("\n");
 290                 log("    -short\n");
 291                 log("        create shorter input cones that stop at shared nodes. This yields\n");
 292                 log("        simpler SAT problems but sometimes fails to prove equivalence.\n");
 293                 log("\n");
 294                 log("    -nogroup\n");
 295                 log("        disabling grouping of $equiv cells by output wire\n");
 296                 log("\n");
 297                 log("    -seq <N>\n");
 298                 log("        the max. number of time steps to be considered (default = 1)\n");
 299                 log("\n");
 300         }
 301         void execute(std::vector<std::string> args, Design *design) YS_OVERRIDE
 302         {
 303                 bool verbose = false, short_cones = false, model_undef = false, nogroup = false;
 304                 int success_counter = 0;
 305                 int max_seq = 1;
 306
 307                 log_header(design, "Executing EQUIV_SIMPLE pass.\n");
 308
 309                 size_t argidx;
 310                 for (argidx = 1; argidx < args.size(); argidx++) {
 311                         if (args[argidx] == "-v") {
 312                                 verbose = true;
 313                                 continue;
 314                         }
 315                         if (args[argidx] == "-short") {
 316                                 short_cones = true;
 317                                 continue;
 318                         }
 319                         if (args[argidx] == "-undef") {
 320                                 model_undef = true;
 321                                 continue;
 322                         }
 323                         if (args[argidx] == "-nogroup") {
 324                                 nogroup = true;
 325                                 continue;
 326                         }
 327                         if (args[argidx] == "-seq" && argidx+1 < args.size()) {
 328                                 max_seq = atoi(args[++argidx].c_str());
 329                                 continue;
 330                         }
 331                         break;
 332                 }
 333                 extra_args(args, argidx, design);
 334
 335                 CellTypes ct;
 336                 ct.setup_internals();
 337                 ct.setup_stdcells();
 338
 339                 for (auto module : design->selected_modules())
 340                 {
 341                         SigMap sigmap(module);
 342                         dict<SigBit, Cell*> bit2driver;
 343                         dict<SigBit, dict<SigBit, Cell*>> unproven_equiv_cells;
 344                         int unproven_cells_counter = 0;
 345
 346                         for (auto cell : module->selected_cells())
 347                                 if (cell->type == ID($equiv) && cell->getPort(ID::A) != cell->getPort(ID::B)) {
 348                                         auto bit = sigmap(cell->getPort(ID::Y).as_bit());
 349                                         auto bit_group = bit;
 350                                         if (!nogroup && bit_group.wire)
 351                                                 bit_group.offset = 0;
 352                                         unproven_equiv_cells[bit_group][bit] = cell;
 353                                         unproven_cells_counter++;
 354                                 }
 355
 356                         if (unproven_equiv_cells.empty())
 357                                 continue;
 358
 359                         log("Found %d unproven $equiv cells (%d groups) in %s:\n",
 360                                         unproven_cells_counter, GetSize(unproven_equiv_cells), log_id(module));
 361
 362                         for (auto cell : module->cells()) {
 363                                 if (!ct.cell_known(cell->type) && !cell->type.in(ID($dff), ID($_DFF_P_), ID($_DFF_N_), ID($ff), ID($_FF_)))
 364                                         continue;
 365                                 for (auto &conn : cell->connections())
 366                                         if (yosys_celltypes.cell_output(cell->type, conn.first))
 367                                                 for (auto bit : sigmap(conn.second))
 368                                                         bit2driver[bit] = cell;
 369                         }
 370
 371                         unproven_equiv_cells.sort();
 372                         for (auto it : unproven_equiv_cells)
 373                         {
 374                                 it.second.sort();
 375
 376                                 vector<Cell*> cells;
 377                                 for (auto it2 : it.second)
 378                                         cells.push_back(it2.second);
 379
 380                                 EquivSimpleWorker worker(cells, sigmap, bit2driver, max_seq, short_cones, verbose, model_undef);
 381                                 success_counter += worker.run();
 382                         }
 383                 }
 384
 385                 log("Proved %d previously unproven $equiv cells.\n", success_counter);
 386         }
 387 } EquivSimplePass;
 388
 389 PRIVATE_NAMESPACE_END