passes/equiv/equiv_make.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/sigtools.h"
  22 #include "kernel/celltypes.h"
  23
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct EquivMakeWorker
  28 {
  29         Module *gold_mod, *gate_mod, *equiv_mod;
  30         pool<IdString> wire_names, cell_names;
  31         CellTypes ct;
  32
  33         bool inames;
  34         vector<string> blacklists;
  35         vector<string> encfiles;
  36
  37         pool<IdString> blacklist_names;
  38         dict<IdString, dict<Const, Const>> encdata;
  39
  40         pool<SigBit> undriven_bits;
  41         SigMap assign_map;
  42
  43         dict<SigBit, pool<Cell*>> bit2driven; // map: bit <--> and its driven cells
  44
  45         CellTypes comb_ct;
  46
  47         EquivMakeWorker()
  48         {
  49                 comb_ct.setup_internals();
  50                 comb_ct.setup_stdcells();
  51         }
  52
  53         void read_blacklists()
  54         {
  55                 for (auto fn : blacklists)
  56                 {
  57                         std::ifstream f(fn);
  58                         if (f.fail())
  59                                 log_cmd_error("Can't open blacklist file '%s'!\n", fn.c_str());
  60
  61                         string line, token;
  62                         while (std::getline(f, line)) {
  63                                 while (1) {
  64                                         token = next_token(line);
  65                                         if (token.empty())
  66                                                 break;
  67                                         blacklist_names.insert(RTLIL::escape_id(token));
  68                                 }
  69                         }
  70                 }
  71         }
  72
  73         void read_encfiles()
  74         {
  75                 for (auto fn : encfiles)
  76                 {
  77                         std::ifstream f(fn);
  78                         if (f.fail())
  79                                 log_cmd_error("Can't open encfile '%s'!\n", fn.c_str());
  80
  81                         dict<Const, Const> *ed = nullptr;
  82                         string line, token;
  83                         while (std::getline(f, line))
  84                         {
  85                                 token = next_token(line);
  86                                 if (token.empty() || token[0] == '#')
  87                                         continue;
  88
  89                                 if (token == ".fsm") {
  90                                         IdString modname = RTLIL::escape_id(next_token(line));
  91                                         IdString signame = RTLIL::escape_id(next_token(line));
  92                                         if (encdata.count(signame))
  93                                                 log_cmd_error("Re-definition of signal '%s' in encfile '%s'!\n", signame.c_str(), fn.c_str());
  94                                         encdata[signame] = dict<Const, Const>();
  95                                         ed = &encdata[signame];
  96                                         continue;
  97                                 }
  98
  99                                 if (token == ".map") {
 100                                         Const gold_bits = Const::from_string(next_token(line));
 101                                         Const gate_bits = Const::from_string(next_token(line));
 102                                         (*ed)[gold_bits] = gate_bits;
 103                                         continue;
 104                                 }
 105
 106                                 log_cmd_error("Syntax error in encfile '%s'!\n", fn.c_str());
 107                         }
 108                 }
 109         }
 110
 111         void copy_to_equiv()
 112         {
 113                 Module *gold_clone = gold_mod->clone();
 114                 Module *gate_clone = gate_mod->clone();
 115
 116                 for (auto it : gold_clone->wires().to_vector()) {
 117                         if ((it->name[0] == '\\' || inames) && blacklist_names.count(it->name) == 0)
 118                                 wire_names.insert(it->name);
 119                         gold_clone->rename(it, it->name.str() + "_gold");
 120                 }
 121
 122                 for (auto it : gold_clone->cells().to_vector()) {
 123                         if ((it->name[0] == '\\' || inames) && blacklist_names.count(it->name) == 0)
 124                                 cell_names.insert(it->name);
 125                         gold_clone->rename(it, it->name.str() + "_gold");
 126                 }
 127
 128                 for (auto it : gate_clone->wires().to_vector()) {
 129                         if ((it->name[0] == '\\' || inames) && blacklist_names.count(it->name) == 0)
 130                                 wire_names.insert(it->name);
 131                         gate_clone->rename(it, it->name.str() + "_gate");
 132                 }
 133
 134                 for (auto it : gate_clone->cells().to_vector()) {
 135                         if ((it->name[0] == '\\' || inames) && blacklist_names.count(it->name) == 0)
 136                                 cell_names.insert(it->name);
 137                         gate_clone->rename(it, it->name.str() + "_gate");
 138                 }
 139
 140                 gold_clone->cloneInto(equiv_mod);
 141                 gate_clone->cloneInto(equiv_mod);
 142                 delete gold_clone;
 143                 delete gate_clone;
 144         }
 145
 146         void find_same_wires()
 147         {
 148                 SigMap assign_map(equiv_mod);
 149                 SigMap rd_signal_map;
 150
 151                 // list of cells without added $equiv cells
 152                 auto cells_list = equiv_mod->cells().to_vector();
 153
 154                 for (auto id : wire_names)
 155                 {
 156                         IdString gold_id = id.str() + "_gold";
 157                         IdString gate_id = id.str() + "_gate";
 158
 159                         Wire *gold_wire = equiv_mod->wire(gold_id);
 160                         Wire *gate_wire = equiv_mod->wire(gate_id);
 161
 162                         if (encdata.count(id))
 163                         {
 164                                 log("Creating encoder/decoder for signal %s.\n", log_id(id));
 165
 166                                 Wire *dec_wire = equiv_mod->addWire(id.str() + "_decoded", gold_wire->width);
 167                                 Wire *enc_wire = equiv_mod->addWire(id.str() + "_encoded", gate_wire->width);
 168
 169                                 SigSpec dec_a, dec_b, dec_s;
 170                                 SigSpec enc_a, enc_b, enc_s;
 171
 172                                 dec_a = SigSpec(State::Sx, dec_wire->width);
 173                                 enc_a = SigSpec(State::Sx, enc_wire->width);
 174
 175                                 for (auto &it : encdata.at(id))
 176                                 {
 177                                         SigSpec dec_sig = gate_wire, dec_pat = it.second;
 178                                         SigSpec enc_sig = dec_wire, enc_pat = it.first;
 179
 180                                         if (GetSize(dec_sig) != GetSize(dec_pat))
 181                                                 log_error("Invalid pattern %s for signal %s of size %d!\n",
 182                                                                 log_signal(dec_pat), log_signal(dec_sig), GetSize(dec_sig));
 183
 184                                         if (GetSize(enc_sig) != GetSize(enc_pat))
 185                                                 log_error("Invalid pattern %s for signal %s of size %d!\n",
 186                                                                 log_signal(enc_pat), log_signal(enc_sig), GetSize(enc_sig));
 187
 188                                         SigSpec reduced_dec_sig, reduced_dec_pat;
 189                                         for (int i = 0; i < GetSize(dec_sig); i++)
 190                                                 if (dec_pat[i] == State::S0 || dec_pat[i] == State::S1) {
 191                                                         reduced_dec_sig.append(dec_sig[i]);
 192                                                         reduced_dec_pat.append(dec_pat[i]);
 193                                                 }
 194
 195                                         SigSpec reduced_enc_sig, reduced_enc_pat;
 196                                         for (int i = 0; i < GetSize(enc_sig); i++)
 197                                                 if (enc_pat[i] == State::S0 || enc_pat[i] == State::S1) {
 198                                                         reduced_enc_sig.append(enc_sig[i]);
 199                                                         reduced_enc_pat.append(enc_pat[i]);
 200                                                 }
 201
 202                                         SigSpec dec_result = it.first;
 203                                         for (auto &bit : dec_result)
 204                                                 if (bit != State::S1) bit = State::S0;
 205
 206                                         SigSpec enc_result = it.second;
 207                                         for (auto &bit : enc_result)
 208                                                 if (bit != State::S1) bit = State::S0;
 209
 210                                         SigSpec dec_eq = equiv_mod->addWire(NEW_ID);
 211                                         SigSpec enc_eq = equiv_mod->addWire(NEW_ID);
 212
 213                                         equiv_mod->addEq(NEW_ID, reduced_dec_sig, reduced_dec_pat, dec_eq);
 214                                         cells_list.push_back(equiv_mod->addEq(NEW_ID, reduced_enc_sig, reduced_enc_pat, enc_eq));
 215
 216                                         dec_s.append(dec_eq);
 217                                         enc_s.append(enc_eq);
 218                                         dec_b.append(dec_result);
 219                                         enc_b.append(enc_result);
 220                                 }
 221
 222                                 equiv_mod->addPmux(NEW_ID, dec_a, dec_b, dec_s, dec_wire);
 223                                 equiv_mod->addPmux(NEW_ID, enc_a, enc_b, enc_s, enc_wire);
 224
 225                                 rd_signal_map.add(assign_map(gate_wire), enc_wire);
 226                                 gate_wire = dec_wire;
 227                         }
 228
 229                         if (gold_wire == nullptr || gate_wire == nullptr || gold_wire->width != gate_wire->width) {
 230                                 if (gold_wire && gold_wire->port_id)
 231                                         log_error("Can't match gold port `%s' to a gate port.\n", log_id(gold_wire));
 232                                 if (gate_wire && gate_wire->port_id)
 233                                         log_error("Can't match gate port `%s' to a gold port.\n", log_id(gate_wire));
 234                                 continue;
 235                         }
 236
 237                         log("Presumably equivalent wires: %s (%s), %s (%s) -> %s\n",
 238                                         log_id(gold_wire), log_signal(assign_map(gold_wire)),
 239                                         log_id(gate_wire), log_signal(assign_map(gate_wire)), log_id(id));
 240
 241                         if (gold_wire->port_output || gate_wire->port_output)
 242                         {
 243                                 Wire *wire = equiv_mod->addWire(id, gold_wire->width);
 244                                 wire->port_output = true;
 245                                 gold_wire->port_input = false;
 246                                 gate_wire->port_input = false;
 247                                 gold_wire->port_output = false;
 248                                 gate_wire->port_output = false;
 249
 250                                 for (int i = 0; i < wire->width; i++)
 251                                         equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i));
 252
 253                                 rd_signal_map.add(assign_map(gold_wire), wire);
 254                                 rd_signal_map.add(assign_map(gate_wire), wire);
 255                         }
 256                         else
 257                         if (gold_wire->port_input || gate_wire->port_input)
 258                         {
 259                                 Wire *wire = equiv_mod->addWire(id, gold_wire->width);
 260                                 wire->port_input = true;
 261                                 gold_wire->port_input = false;
 262                                 gate_wire->port_input = false;
 263                                 equiv_mod->connect(gold_wire, wire);
 264                                 equiv_mod->connect(gate_wire, wire);
 265                         }
 266                         else
 267                         {
 268                                 Wire *wire = equiv_mod->addWire(id, gold_wire->width);
 269                                 SigSpec rdmap_gold, rdmap_gate, rdmap_equiv;
 270
 271                                 for (int i = 0; i < wire->width; i++) {
 272                                         if (undriven_bits.count(assign_map(SigBit(gold_wire, i)))) {
 273                                                 log("  Skipping signal bit %s [%d]: undriven on gold side.\n", id2cstr(gold_wire->name), i);
 274                                                 continue;
 275                                         }
 276                                         if (undriven_bits.count(assign_map(SigBit(gate_wire, i)))) {
 277                                                 log("  Skipping signal bit %s [%d]: undriven on gate side.\n", id2cstr(gate_wire->name), i);
 278                                                 continue;
 279                                         }
 280                                         equiv_mod->addEquiv(NEW_ID, SigSpec(gold_wire, i), SigSpec(gate_wire, i), SigSpec(wire, i));
 281                                         rdmap_gold.append(SigBit(gold_wire, i));
 282                                         rdmap_gate.append(SigBit(gate_wire, i));
 283                                         rdmap_equiv.append(SigBit(wire, i));
 284                                 }
 285
 286                                 rd_signal_map.add(rdmap_gold, rdmap_equiv);
 287                                 rd_signal_map.add(rdmap_gate, rdmap_equiv);
 288                         }
 289                 }
 290
 291                 init_bit2driven();
 292
 293                 pool<Cell*> visited_cells;
 294                 for (auto c : cells_list)
 295                 for (auto &conn : c->connections())
 296                         if (!ct.cell_output(c->type, conn.first)) {
 297                                 SigSpec old_sig = assign_map(conn.second);
 298                                 SigSpec new_sig = rd_signal_map(old_sig);
 299
 300                                 if(old_sig != new_sig) {
 301                                         SigSpec tmp_sig = old_sig;
 302                                         for (int i = 0; i < GetSize(old_sig); i++) {
 303                                                 SigBit old_bit = old_sig[i], new_bit = new_sig[i];
 304
 305                                                 visited_cells.clear();
 306                                                 if (check_signal_in_fanout(visited_cells, old_bit, new_bit))
 307                                                         continue;
 308
 309                                                 log("Changing input %s of cell %s (%s): %s -> %s\n",
 310                                                                 log_id(conn.first), log_id(c), log_id(c->type),
 311                                                                 log_signal(old_bit), log_signal(new_bit));
 312
 313                                                 tmp_sig[i] = new_bit;
 314                                         }
 315                                         c->setPort(conn.first, tmp_sig);
 316                                 }
 317                         }
 318
 319                 equiv_mod->fixup_ports();
 320         }
 321
 322         void find_same_cells()
 323         {
 324                 SigMap assign_map(equiv_mod);
 325
 326                 for (auto id : cell_names)
 327                 {
 328                         IdString gold_id = id.str() + "_gold";
 329                         IdString gate_id = id.str() + "_gate";
 330
 331                         Cell *gold_cell = equiv_mod->cell(gold_id);
 332                         Cell *gate_cell = equiv_mod->cell(gate_id);
 333
 334                         if (gold_cell == nullptr || gate_cell == nullptr || gold_cell->type != gate_cell->type || !ct.cell_known(gold_cell->type) ||
 335                                         gold_cell->parameters != gate_cell->parameters || GetSize(gold_cell->connections()) != GetSize(gate_cell->connections()))
 336                 try_next_cell_name:
 337                                 continue;
 338
 339                         for (auto gold_conn : gold_cell->connections())
 340                                 if (!gate_cell->connections().count(gold_conn.first))
 341                                         goto try_next_cell_name;
 342
 343                         log("Presumably equivalent cells: %s %s (%s) -> %s\n",
 344                                         log_id(gold_cell), log_id(gate_cell), log_id(gold_cell->type), log_id(id));
 345
 346                         for (auto gold_conn : gold_cell->connections())
 347                         {
 348                                 SigSpec gold_sig = assign_map(gold_conn.second);
 349                                 SigSpec gate_sig = assign_map(gate_cell->getPort(gold_conn.first));
 350
 351                                 if (ct.cell_output(gold_cell->type, gold_conn.first)) {
 352                                         equiv_mod->connect(gate_sig, gold_sig);
 353                                         continue;
 354                                 }
 355
 356                                 for (int i = 0; i < GetSize(gold_sig); i++)
 357                                         if (gold_sig[i] != gate_sig[i]) {
 358                                                 Wire *w = equiv_mod->addWire(NEW_ID);
 359                                                 equiv_mod->addEquiv(NEW_ID, gold_sig[i], gate_sig[i], w);
 360                                                 gold_sig[i] = w;
 361                                         }
 362
 363                                 gold_cell->setPort(gold_conn.first, gold_sig);
 364                         }
 365
 366                         equiv_mod->remove(gate_cell);
 367                         equiv_mod->rename(gold_cell, id);
 368                 }
 369         }
 370
 371         void find_undriven_nets(bool mark)
 372         {
 373                 undriven_bits.clear();
 374                 assign_map.set(equiv_mod);
 375
 376                 for (auto wire : equiv_mod->wires()) {
 377                         for (auto bit : assign_map(wire))
 378                                 if (bit.wire)
 379                                         undriven_bits.insert(bit);
 380                 }
 381
 382                 for (auto wire : equiv_mod->wires()) {
 383                         if (wire->port_input)
 384                                 for (auto bit : assign_map(wire))
 385                                         undriven_bits.erase(bit);
 386                 }
 387
 388                 for (auto cell : equiv_mod->cells()) {
 389                         for (auto &conn : cell->connections())
 390                                 if (!ct.cell_known(cell->type) || ct.cell_output(cell->type, conn.first))
 391                                         for (auto bit : assign_map(conn.second))
 392                                                 undriven_bits.erase(bit);
 393                 }
 394
 395                 if (mark) {
 396                         SigSpec undriven_sig(undriven_bits);
 397                         undriven_sig.sort_and_unify();
 398
 399                         for (auto chunk : undriven_sig.chunks()) {
 400                                 log("Setting undriven nets to undef: %s\n", log_signal(chunk));
 401                                 equiv_mod->connect(chunk, SigSpec(State::Sx, chunk.width));
 402                         }
 403                 }
 404         }
 405
 406         void init_bit2driven()
 407         {
 408                 for (auto cell : equiv_mod->cells()) {
 409                         if (!ct.cell_known(cell->type) && !cell->type.in("$dff", "$_DFF_P_", "$_DFF_N_", "$ff", "$_FF_"))
 410                                 continue;
 411                         for (auto &conn : cell->connections())
 412                         {
 413                                 if (yosys_celltypes.cell_input(cell->type, conn.first))
 414                                         for (auto bit : assign_map(conn.second))
 415                                         {
 416                                                 bit2driven[bit].insert(cell);
 417                                         }
 418                         }
 419                 }
 420         }
 421
 422         bool check_signal_in_fanout(pool<Cell*> & visited_cells, SigBit source_bit, SigBit target_bit)
 423         {
 424                 if (source_bit == target_bit)
 425                         return true;
 426
 427                 if (bit2driven.count(source_bit) == 0)
 428                         return false;
 429
 430                 auto driven_cells = bit2driven.at(source_bit);
 431                 for (auto driven_cell: driven_cells)
 432                 {
 433                         bool is_comb = comb_ct.cell_known(driven_cell->type);
 434                         if (!is_comb)
 435                                 continue;
 436
 437                         if (visited_cells.count(driven_cell) > 0)
 438                                 continue;
 439                         visited_cells.insert(driven_cell);
 440
 441                         for (auto &conn: driven_cell->connections())
 442                         {
 443                                 if (yosys_celltypes.cell_input(driven_cell->type, conn.first))
 444                                         continue;
 445
 446                                 for (auto bit: conn.second) {
 447                                         bool is_in_fanout = check_signal_in_fanout(visited_cells, bit, target_bit);
 448                                         if (is_in_fanout == true)
 449                                                 return true;
 450                                 }
 451                         }
 452                 }
 453
 454                 return false;
 455         }
 456
 457         void run()
 458         {
 459                 copy_to_equiv();
 460                 find_undriven_nets(false);
 461                 find_same_wires();
 462                 find_same_cells();
 463                 find_undriven_nets(true);
 464         }
 465 };
 466
 467 struct EquivMakePass : public Pass {
 468         EquivMakePass() : Pass("equiv_make", "prepare a circuit for equivalence checking") { }
 469         void help() YS_OVERRIDE
 470         {
 471                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 472                 log("\n");
 473                 log("    equiv_make [options] gold_module gate_module equiv_module\n");
 474                 log("\n");
 475                 log("This creates a module annotated with $equiv cells from two presumably\n");
 476                 log("equivalent modules. Use commands such as 'equiv_simple' and 'equiv_status'\n");
 477                 log("to work with the created equivalent checking module.\n");
 478                 log("\n");
 479                 log("    -inames\n");
 480                 log("        Also match cells and wires with $... names.\n");
 481                 log("\n");
 482                 log("    -blacklist <file>\n");
 483                 log("        Do not match cells or signals that match the names in the file.\n");
 484                 log("\n");
 485                 log("    -encfile <file>\n");
 486                 log("        Match FSM encodings using the description from the file.\n");
 487                 log("        See 'help fsm_recode' for details.\n");
 488                 log("\n");
 489                 log("Note: The circuit created by this command is not a miter (with something like\n");
 490                 log("a trigger output), but instead uses $equiv cells to encode the equivalence\n");
 491                 log("checking problem. Use 'miter -equiv' if you want to create a miter circuit.\n");
 492                 log("\n");
 493         }
 494         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 495         {
 496                 EquivMakeWorker worker;
 497                 worker.ct.setup(design);
 498                 worker.inames = false;
 499
 500                 size_t argidx;
 501                 for (argidx = 1; argidx < args.size(); argidx++)
 502                 {
 503                         if (args[argidx] == "-inames") {
 504                                 worker.inames = true;
 505                                 continue;
 506                         }
 507                         if (args[argidx] == "-blacklist" && argidx+1 < args.size()) {
 508                                 worker.blacklists.push_back(args[++argidx]);
 509                                 continue;
 510                         }
 511                         if (args[argidx] == "-encfile" && argidx+1 < args.size()) {
 512                                 worker.encfiles.push_back(args[++argidx]);
 513                                 continue;
 514                         }
 515                         break;
 516                 }
 517
 518                 if (argidx+3 != args.size())
 519                         log_cmd_error("Invalid number of arguments.\n");
 520
 521                 worker.gold_mod = design->module(RTLIL::escape_id(args[argidx]));
 522                 worker.gate_mod = design->module(RTLIL::escape_id(args[argidx+1]));
 523                 worker.equiv_mod = design->module(RTLIL::escape_id(args[argidx+2]));
 524
 525                 if (worker.gold_mod == nullptr)
 526                         log_cmd_error("Can't find gold module %s.\n", args[argidx].c_str());
 527
 528                 if (worker.gate_mod == nullptr)
 529                         log_cmd_error("Can't find gate module %s.\n", args[argidx+1].c_str());
 530
 531                 if (worker.equiv_mod != nullptr)
 532                         log_cmd_error("Equiv module %s already exists.\n", args[argidx+2].c_str());
 533
 534                 if (worker.gold_mod->has_memories() || worker.gold_mod->has_processes())
 535                         log_cmd_error("Gold module contains memories or processes. Run 'memory' or 'proc' respectively.\n");
 536
 537                 if (worker.gate_mod->has_memories() || worker.gate_mod->has_processes())
 538                         log_cmd_error("Gate module contains memories or processes. Run 'memory' or 'proc' respectively.\n");
 539
 540                 worker.read_blacklists();
 541                 worker.read_encfiles();
 542
 543                 log_header(design, "Executing EQUIV_MAKE pass (creating equiv checking module).\n");
 544
 545                 worker.equiv_mod = design->addModule(RTLIL::escape_id(args[argidx+2]));
 546                 worker.run();
 547         }
 548 } EquivMakePass;
 549
 550 PRIVATE_NAMESPACE_END