passes/equiv/equiv_struct.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
  23 USING_YOSYS_NAMESPACE
  24 PRIVATE_NAMESPACE_BEGIN
  25
  26 struct EquivStructWorker
  27 {
  28         Module *module;
  29         SigMap sigmap;
  30         SigMap equiv_bits;
  31         bool mode_icells;
  32         int merge_count;
  33
  34         dict<IdString, pool<IdString>> cells_by_type;
  35
  36         void handle_cell_pair(Cell *cell_a, Cell *cell_b)
  37         {
  38                 if (cell_a->parameters != cell_b->parameters)
  39                         return;
  40
  41                 bool merge_this_cells = false;
  42                 bool found_diff_inputs = false;
  43                 vector<SigSpec> inputs_a, inputs_b;
  44
  45                 for (auto &port_a : cell_a->connections())
  46                 {
  47                         SigSpec bits_a = equiv_bits(port_a.second);
  48                         SigSpec bits_b = equiv_bits(cell_b->getPort(port_a.first));
  49
  50                         if (GetSize(bits_a) != GetSize(bits_b))
  51                                 return;
  52
  53                         if (cell_a->output(port_a.first)) {
  54                                 for (int i = 0; i < GetSize(bits_a); i++)
  55                                         if (bits_a[i] == bits_b[i])
  56                                                 merge_this_cells = true;
  57                         } else {
  58                                 SigSpec diff_bits_a, diff_bits_b;
  59                                 for (int i = 0; i < GetSize(bits_a); i++)
  60                                         if (bits_a[i] != bits_b[i]) {
  61                                                 diff_bits_a.append(bits_a[i]);
  62                                                 diff_bits_b.append(bits_b[i]);
  63                                         }
  64                                 if (!diff_bits_a.empty()) {
  65                                         inputs_a.push_back(diff_bits_a);
  66                                         inputs_b.push_back(diff_bits_b);
  67                                         found_diff_inputs = true;
  68                                 }
  69                         }
  70                 }
  71
  72                 if (!found_diff_inputs)
  73                         merge_this_cells = true;
  74
  75                 if (merge_this_cells)
  76                 {
  77                         SigMap merged_map;
  78
  79                         log("      Merging cells %s and %s.\n", log_id(cell_a),  log_id(cell_b));
  80                         merge_count++;
  81
  82                         for (int i = 0; i < GetSize(inputs_a); i++) {
  83                                 SigSpec &sig_a = inputs_a[i], &sig_b = inputs_b[i];
  84                                 SigSpec sig_y = module->addWire(NEW_ID, GetSize(sig_a));
  85                                 log("        A: %s, B: %s, Y: %s\n", log_signal(sig_a),  log_signal(sig_b), log_signal(sig_y));
  86                                 module->addEquiv(NEW_ID, sig_a, sig_b, sig_y);
  87                                 merged_map.add(sig_a, sig_y);
  88                                 merged_map.add(sig_b, sig_y);
  89                         }
  90
  91                         std::vector<IdString> outport_names, inport_names;
  92
  93                         for (auto &port_a : cell_a->connections())
  94                                 if (cell_a->output(port_a.first))
  95                                         outport_names.push_back(port_a.first);
  96                                 else
  97                                         inport_names.push_back(port_a.first);
  98
  99                         for (auto &pn : inport_names)
 100                                 cell_a->setPort(pn, merged_map(equiv_bits(cell_a->getPort(pn))));
 101
 102                         for (auto &pn : outport_names) {
 103                                 SigSpec sig_a = cell_a->getPort(pn);
 104                                 SigSpec sig_b = cell_b->getPort(pn);
 105                                 module->connect(sig_b, sig_a);
 106                                 sigmap.add(sig_b, sig_a);
 107                                 equiv_bits.add(sig_b, sig_a);
 108                         }
 109
 110                         module->remove(cell_b);
 111                 }
 112         }
 113
 114         EquivStructWorker(Module *module, bool mode_icells) :
 115                         module(module), sigmap(module), equiv_bits(module), mode_icells(mode_icells), merge_count(0)
 116         {
 117                 log("  Starting new iteration.\n");
 118
 119                 for (auto cell : module->selected_cells())
 120                         if (cell->type == "$equiv") {
 121                                 equiv_bits.add(sigmap(cell->getPort("\\A")), sigmap(cell->getPort("\\B")));
 122                                 cells_by_type[cell->type].insert(cell->name);
 123                         } else
 124                         if (module->design->selected(module, cell)) {
 125                                 if (mode_icells || module->design->module(cell->type))
 126                                         cells_by_type[cell->type].insert(cell->name);
 127                         }
 128
 129                 for (auto &it : cells_by_type)
 130                 {
 131                         if (it.second.size() <= 1)
 132                                 continue;
 133
 134                         log("    Merging %s cells..\n", log_id(it.first));
 135
 136                         // FIXME: O(n^2)
 137                         for (auto cell_name_a : it.second)
 138                         for (auto cell_name_b : it.second)
 139                                 if (cell_name_a < cell_name_b) {
 140                                         Cell *cell_a = module->cell(cell_name_a);
 141                                         Cell *cell_b = module->cell(cell_name_b);
 142                                         if (cell_a && cell_b)
 143                                                 handle_cell_pair(cell_a, cell_b);
 144                                 }
 145                 }
 146         }
 147 };
 148
 149 struct EquivStructPass : public Pass {
 150         EquivStructPass() : Pass("equiv_struct", "structural equivalence checking") { }
 151         virtual void help()
 152         {
 153                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 154                 log("\n");
 155                 log("    equiv_struct [options] [selection]\n");
 156                 log("\n");
 157                 log("This command adds additional $equiv cells based on the assumption that the\n");
 158                 log("gold and gate circuit are structurally equivalent. Note that this can introduce\n");
 159                 log("bad $equiv cells in cases where the netlists are not structurally equivalent,\n");
 160                 log("for example when analyzing circuits with cells with commutative inputs. This\n");
 161                 log("command will also de-duplicate gates.\n");
 162                 log("\n");
 163                 log("    -icells\n");
 164                 log("        by default, the internal RTL and gate cell types are ignored. add\n");
 165                 log("        this option to also process those cell types with this command.\n");
 166                 log("\n");
 167         }
 168         virtual void execute(std::vector<std::string> args, Design *design)
 169         {
 170                 bool mode_icells = false;
 171
 172                 log_header("Executing EQUIV_STRUCT pass.\n");
 173
 174                 size_t argidx;
 175                 for (argidx = 1; argidx < args.size(); argidx++) {
 176                         if (args[argidx] == "-icells") {
 177                                 mode_icells = true;
 178                                 continue;
 179                         }
 180                         break;
 181                 }
 182                 extra_args(args, argidx, design);
 183
 184                 for (auto module : design->selected_modules()) {
 185                         log("Running equiv_struct on module %s:", log_id(module));
 186                         while (1) {
 187                                 EquivStructWorker worker(module, mode_icells);
 188                                 if (worker.merge_count == 0)
 189                                         break;
 190                         }
 191                 }
 192         }
 193 } EquivStructPass;
 194
 195 PRIVATE_NAMESPACE_END