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