passes/opt/opt_merge.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/register.h"
  21 #include "kernel/sigtools.h"
  22 #include "kernel/log.h"
  23 #include "kernel/celltypes.h"
  24 #include "libs/sha1/sha1.h"
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <set>
  28
  29 #define USE_CELL_HASH_CACHE
  30
  31 USING_YOSYS_NAMESPACE
  32 PRIVATE_NAMESPACE_BEGIN
  33
  34 struct OptMergeWorker
  35 {
  36         RTLIL::Design *design;
  37         RTLIL::Module *module;
  38         SigMap assign_map;
  39         SigMap dff_init_map;
  40         bool mode_share_all;
  41
  42         CellTypes ct;
  43         int total_count;
  44 #ifdef USE_CELL_HASH_CACHE
  45         dict<const RTLIL::Cell*, std::string> cell_hash_cache;
  46 #endif
  47
  48         static void sort_pmux_conn(dict<RTLIL::IdString, RTLIL::SigSpec> &conn)
  49         {
  50                 SigSpec sig_s = conn.at("\\S");
  51                 SigSpec sig_b = conn.at("\\B");
  52
  53                 int s_width = GetSize(sig_s);
  54                 int width = GetSize(sig_b) / s_width;
  55
  56                 vector<pair<SigBit, SigSpec>> sb_pairs;
  57                 for (int i = 0; i < s_width; i++)
  58                         sb_pairs.push_back(pair<SigBit, SigSpec>(sig_s[i], sig_b.extract(i*width, width)));
  59
  60                 std::sort(sb_pairs.begin(), sb_pairs.end());
  61
  62                 conn["\\S"] = SigSpec();
  63                 conn["\\B"] = SigSpec();
  64
  65                 for (auto &it : sb_pairs) {
  66                         conn["\\S"].append(it.first);
  67                         conn["\\B"].append(it.second);
  68                 }
  69         }
  70
  71 #ifdef USE_CELL_HASH_CACHE
  72         std::string int_to_hash_string(unsigned int v)
  73         {
  74                 if (v == 0)
  75                         return "0";
  76                 std::string str = "";
  77                 while (v > 0) {
  78                         str += 'a' + (v & 15);
  79                         v = v >> 4;
  80                 }
  81                 return str;
  82         }
  83
  84         std::string hash_cell_parameters_and_connections(const RTLIL::Cell *cell)
  85         {
  86                 if (cell_hash_cache.count(cell) > 0)
  87                         return cell_hash_cache[cell];
  88
  89                 std::string hash_string = cell->type.str() + "\n";
  90
  91                 for (auto &it : cell->parameters)
  92                         hash_string += "P " + it.first.str() + "=" + it.second.as_string() + "\n";
  93
  94                 const dict<RTLIL::IdString, RTLIL::SigSpec> *conn = &cell->connections();
  95                 dict<RTLIL::IdString, RTLIL::SigSpec> alt_conn;
  96
  97                 if (cell->type == "$and" || cell->type == "$or" || cell->type == "$xor" || cell->type == "$xnor" || cell->type == "$add" || cell->type == "$mul" ||
  98                                 cell->type == "$logic_and" || cell->type == "$logic_or" || cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_") {
  99                         alt_conn = *conn;
 100                         if (assign_map(alt_conn.at("\\A")) < assign_map(alt_conn.at("\\B"))) {
 101                                 alt_conn["\\A"] = conn->at("\\B");
 102                                 alt_conn["\\B"] = conn->at("\\A");
 103                         }
 104                         conn = &alt_conn;
 105                 } else
 106                 if (cell->type == "$reduce_xor" || cell->type == "$reduce_xnor") {
 107                         alt_conn = *conn;
 108                         assign_map.apply(alt_conn.at("\\A"));
 109                         alt_conn.at("\\A").sort();
 110                         conn = &alt_conn;
 111                 } else
 112                 if (cell->type == "$reduce_and" || cell->type == "$reduce_or" || cell->type == "$reduce_bool") {
 113                         alt_conn = *conn;
 114                         assign_map.apply(alt_conn.at("\\A"));
 115                         alt_conn.at("\\A").sort_and_unify();
 116                         conn = &alt_conn;
 117                 } else
 118                 if (cell->type == "$pmux") {
 119                         alt_conn = *conn;
 120                         assign_map.apply(alt_conn.at("\\A"));
 121                         assign_map.apply(alt_conn.at("\\B"));
 122                         assign_map.apply(alt_conn.at("\\S"));
 123                         sort_pmux_conn(alt_conn);
 124                         conn = &alt_conn;
 125                 }
 126
 127                 vector<string> hash_conn_strings;
 128
 129                 for (auto &it : *conn) {
 130                         if (cell->output(it.first))
 131                                 continue;
 132                         RTLIL::SigSpec sig = it.second;
 133                         assign_map.apply(sig);
 134                         string s = "C " + it.first.str() + "=";
 135                         for (auto &chunk : sig.chunks()) {
 136                                 if (chunk.wire)
 137                                         s += "{" + chunk.wire->name.str() + " " +
 138                                                         int_to_hash_string(chunk.offset) + " " +
 139                                                         int_to_hash_string(chunk.width) + "}";
 140                                 else
 141                                         s += RTLIL::Const(chunk.data).as_string();
 142                         }
 143                         hash_conn_strings.push_back(s + "\n");
 144                 }
 145
 146                 std::sort(hash_conn_strings.begin(), hash_conn_strings.end());
 147
 148                 for (auto it : hash_conn_strings)
 149                         hash_string += it;
 150
 151                 cell_hash_cache[cell] = sha1(hash_string);
 152                 return cell_hash_cache[cell];
 153         }
 154 #endif
 155
 156         bool compare_cell_parameters_and_connections(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2, bool &lt)
 157         {
 158 #ifdef USE_CELL_HASH_CACHE
 159                 std::string hash1 = hash_cell_parameters_and_connections(cell1);
 160                 std::string hash2 = hash_cell_parameters_and_connections(cell2);
 161
 162                 if (hash1 != hash2) {
 163                         lt = hash1 < hash2;
 164                         return true;
 165                 }
 166 #endif
 167
 168                 if (cell1->parameters != cell2->parameters) {
 169                         std::map<RTLIL::IdString, RTLIL::Const> p1(cell1->parameters.begin(), cell1->parameters.end());
 170                         std::map<RTLIL::IdString, RTLIL::Const> p2(cell2->parameters.begin(), cell2->parameters.end());
 171                         lt = p1 < p2;
 172                         return true;
 173                 }
 174
 175                 dict<RTLIL::IdString, RTLIL::SigSpec> conn1 = cell1->connections();
 176                 dict<RTLIL::IdString, RTLIL::SigSpec> conn2 = cell2->connections();
 177
 178                 for (auto &it : conn1) {
 179                         if (cell1->output(it.first))
 180                                 it.second = RTLIL::SigSpec();
 181                         else
 182                                 assign_map.apply(it.second);
 183                 }
 184
 185                 for (auto &it : conn2) {
 186                         if (cell2->output(it.first))
 187                                 it.second = RTLIL::SigSpec();
 188                         else
 189                                 assign_map.apply(it.second);
 190                 }
 191
 192                 if (cell1->type == "$and" || cell1->type == "$or" || cell1->type == "$xor" || cell1->type == "$xnor" || cell1->type == "$add" || cell1->type == "$mul" ||
 193                                 cell1->type == "$logic_and" || cell1->type == "$logic_or" || cell1->type == "$_AND_" || cell1->type == "$_OR_" || cell1->type == "$_XOR_") {
 194                         if (conn1.at("\\A") < conn1.at("\\B")) {
 195                                 RTLIL::SigSpec tmp = conn1["\\A"];
 196                                 conn1["\\A"] = conn1["\\B"];
 197                                 conn1["\\B"] = tmp;
 198                         }
 199                         if (conn2.at("\\A") < conn2.at("\\B")) {
 200                                 RTLIL::SigSpec tmp = conn2["\\A"];
 201                                 conn2["\\A"] = conn2["\\B"];
 202                                 conn2["\\B"] = tmp;
 203                         }
 204                 } else
 205                 if (cell1->type == "$reduce_xor" || cell1->type == "$reduce_xnor") {
 206                         conn1["\\A"].sort();
 207                         conn2["\\A"].sort();
 208                 } else
 209                 if (cell1->type == "$reduce_and" || cell1->type == "$reduce_or" || cell1->type == "$reduce_bool") {
 210                         conn1["\\A"].sort_and_unify();
 211                         conn2["\\A"].sort_and_unify();
 212                 } else
 213                 if (cell1->type == "$pmux") {
 214                         sort_pmux_conn(conn1);
 215                         sort_pmux_conn(conn2);
 216                 }
 217
 218                 if (conn1 != conn2) {
 219                         std::map<RTLIL::IdString, RTLIL::SigSpec> c1(conn1.begin(), conn1.end());
 220                         std::map<RTLIL::IdString, RTLIL::SigSpec> c2(conn2.begin(), conn2.end());
 221                         lt = c1 < c2;
 222                         return true;
 223                 }
 224
 225                 if (cell1->type.substr(0, 1) == "$" && conn1.count("\\Q") != 0) {
 226                         std::vector<RTLIL::SigBit> q1 = dff_init_map(cell1->getPort("\\Q")).to_sigbit_vector();
 227                         std::vector<RTLIL::SigBit> q2 = dff_init_map(cell2->getPort("\\Q")).to_sigbit_vector();
 228                         for (size_t i = 0; i < q1.size(); i++)
 229                                 if ((q1.at(i).wire == NULL || q2.at(i).wire == NULL) && q1.at(i) != q2.at(i)) {
 230                                         lt = q1.at(i) < q2.at(i);
 231                                         return true;
 232                                 }
 233                 }
 234
 235                 return false;
 236         }
 237
 238         bool compare_cells(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2)
 239         {
 240                 if (cell1->type != cell2->type)
 241                         return cell1->type < cell2->type;
 242
 243                 if ((!mode_share_all && !ct.cell_known(cell1->type)) || !cell1->known())
 244                         return cell1 < cell2;
 245
 246                 if (cell1->has_keep_attr() || cell2->has_keep_attr())
 247                         return cell1 < cell2;
 248
 249                 bool lt;
 250                 if (compare_cell_parameters_and_connections(cell1, cell2, lt))
 251                         return lt;
 252
 253                 return false;
 254         }
 255
 256         struct CompareCells {
 257                 OptMergeWorker *that;
 258                 CompareCells(OptMergeWorker *that) : that(that) {}
 259                 bool operator()(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) const {
 260                         return that->compare_cells(cell1, cell2);
 261                 }
 262         };
 263
 264         OptMergeWorker(RTLIL::Design *design, RTLIL::Module *module, bool mode_nomux, bool mode_share_all) :
 265                 design(design), module(module), assign_map(module), mode_share_all(mode_share_all)
 266         {
 267                 total_count = 0;
 268                 ct.setup_internals();
 269                 ct.setup_internals_mem();
 270                 ct.setup_stdcells();
 271                 ct.setup_stdcells_mem();
 272
 273                 if (mode_nomux) {
 274                         ct.cell_types.erase("$mux");
 275                         ct.cell_types.erase("$pmux");
 276                 }
 277
 278                 ct.cell_types.erase("$tribuf");
 279                 ct.cell_types.erase("$_TBUF_");
 280                 ct.cell_types.erase("$anyseq");
 281                 ct.cell_types.erase("$anyconst");
 282                 ct.cell_types.erase("$allseq");
 283                 ct.cell_types.erase("$allconst");
 284
 285                 log("Finding identical cells in module `%s'.\n", module->name.c_str());
 286                 assign_map.set(module);
 287
 288                 dff_init_map.set(module);
 289                 for (auto &it : module->wires_)
 290                         if (it.second->attributes.count("\\init") != 0) {
 291                                 Const initval = it.second->attributes.at("\\init");
 292                                 for (int i = 0; i < GetSize(initval) && i < GetSize(it.second); i++)
 293                                         if (initval[i] == State::S0 || initval[i] == State::S1)
 294                                                 dff_init_map.add(SigBit(it.second, i), initval[i]);
 295                         }
 296
 297                 bool did_something = true;
 298                 while (did_something)
 299                 {
 300 #ifdef USE_CELL_HASH_CACHE
 301                         cell_hash_cache.clear();
 302 #endif
 303                         std::vector<RTLIL::Cell*> cells;
 304                         cells.reserve(module->cells_.size());
 305                         for (auto &it : module->cells_) {
 306                                 if (!design->selected(module, it.second))
 307                                         continue;
 308                                 if (ct.cell_known(it.second->type) || (mode_share_all && it.second->known()))
 309                                         cells.push_back(it.second);
 310                         }
 311
 312                         did_something = false;
 313                         std::map<RTLIL::Cell*, RTLIL::Cell*, CompareCells> sharemap(CompareCells(this));
 314                         for (auto cell : cells)
 315                         {
 316                                 if (sharemap.count(cell) > 0) {
 317                                         did_something = true;
 318                                         log_debug("  Cell `%s' is identical to cell `%s'.\n", cell->name.c_str(), sharemap[cell]->name.c_str());
 319                                         for (auto &it : cell->connections()) {
 320                                                 if (cell->output(it.first)) {
 321                                                         RTLIL::SigSpec other_sig = sharemap[cell]->getPort(it.first);
 322                                                         log_debug("    Redirecting output %s: %s = %s\n", it.first.c_str(),
 323                                                                         log_signal(it.second), log_signal(other_sig));
 324                                                         module->connect(RTLIL::SigSig(it.second, other_sig));
 325                                                         assign_map.add(it.second, other_sig);
 326                                                 }
 327                                         }
 328                                         log_debug("    Removing %s cell `%s' from module `%s'.\n", cell->type.c_str(), cell->name.c_str(), module->name.c_str());
 329 #ifdef USE_CELL_HASH_CACHE
 330                                         cell_hash_cache.erase(cell);
 331 #endif
 332                                         module->remove(cell);
 333                                         total_count++;
 334                                 } else {
 335                                         sharemap[cell] = cell;
 336                                 }
 337                         }
 338                 }
 339
 340                 log_suppressed();
 341         }
 342 };
 343
 344 struct OptMergePass : public Pass {
 345         OptMergePass() : Pass("opt_merge", "consolidate identical cells") { }
 346         void help() YS_OVERRIDE
 347         {
 348                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 349                 log("\n");
 350                 log("    opt_merge [options] [selection]\n");
 351                 log("\n");
 352                 log("This pass identifies cells with identical type and input signals. Such cells\n");
 353                 log("are then merged to one cell.\n");
 354                 log("\n");
 355                 log("    -nomux\n");
 356                 log("        Do not merge MUX cells.\n");
 357                 log("\n");
 358                 log("    -share_all\n");
 359                 log("        Operate on all cell types, not just built-in types.\n");
 360                 log("\n");
 361         }
 362         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 363         {
 364                 log_header(design, "Executing OPT_MERGE pass (detect identical cells).\n");
 365
 366                 bool mode_nomux = false;
 367                 bool mode_share_all = false;
 368
 369                 size_t argidx;
 370                 for (argidx = 1; argidx < args.size(); argidx++) {
 371                         std::string arg = args[argidx];
 372                         if (arg == "-nomux") {
 373                                 mode_nomux = true;
 374                                 continue;
 375                         }
 376                         if (arg == "-share_all") {
 377                                 mode_share_all = true;
 378                                 continue;
 379                         }
 380                         break;
 381                 }
 382                 extra_args(args, argidx, design);
 383
 384                 int total_count = 0;
 385                 for (auto module : design->selected_modules()) {
 386                         OptMergeWorker worker(design, module, mode_nomux, mode_share_all);
 387                         total_count += worker.total_count;
 388                 }
 389
 390                 if (total_count)
 391                         design->scratchpad_set_bool("opt.did_something", true);
 392                 log("Removed a total of %d cells.\n", total_count);
 393         }
 394 } OptMergePass;
 395
 396 PRIVATE_NAMESPACE_END