passes/opt/opt_reduce.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 <stdlib.h>
  25 #include <stdio.h>
  26 #include <set>
  27
  28 USING_YOSYS_NAMESPACE
  29 PRIVATE_NAMESPACE_BEGIN
  30
  31 struct OptReduceWorker
  32 {
  33         RTLIL::Design *design;
  34         RTLIL::Module *module;
  35         SigMap assign_map;
  36
  37         int total_count;
  38         bool did_something;
  39
  40         void opt_reduce(pool<RTLIL::Cell*> &cells, SigSet<RTLIL::Cell*> &drivers, RTLIL::Cell *cell)
  41         {
  42                 if (cells.count(cell) == 0)
  43                         return;
  44                 cells.erase(cell);
  45
  46                 RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
  47                 pool<RTLIL::SigBit> new_sig_a_bits;
  48
  49                 for (auto &bit : sig_a.to_sigbit_set())
  50                 {
  51                         if (bit == RTLIL::State::S0) {
  52                                 if (cell->type == "$reduce_and") {
  53                                         new_sig_a_bits.clear();
  54                                         new_sig_a_bits.insert(RTLIL::State::S0);
  55                                         break;
  56                                 }
  57                                 continue;
  58                         }
  59                         if (bit == RTLIL::State::S1) {
  60                                 if (cell->type == "$reduce_or") {
  61                                         new_sig_a_bits.clear();
  62                                         new_sig_a_bits.insert(RTLIL::State::S1);
  63                                         break;
  64                                 }
  65                                 continue;
  66                         }
  67                         if (bit.wire == NULL) {
  68                                 new_sig_a_bits.insert(bit);
  69                                 continue;
  70                         }
  71
  72                         bool imported_children = false;
  73                         for (auto child_cell : drivers.find(bit)) {
  74                                 if (child_cell->type == cell->type) {
  75                                         opt_reduce(cells, drivers, child_cell);
  76                                         if (child_cell->getPort("\\Y")[0] == bit) {
  77                                                 pool<RTLIL::SigBit> child_sig_a_bits = assign_map(child_cell->getPort("\\A")).to_sigbit_pool();
  78                                                 new_sig_a_bits.insert(child_sig_a_bits.begin(), child_sig_a_bits.end());
  79                                         } else
  80                                                 new_sig_a_bits.insert(RTLIL::State::S0);
  81                                         imported_children = true;
  82                                 }
  83                         }
  84                         if (!imported_children)
  85                                 new_sig_a_bits.insert(bit);
  86                 }
  87
  88                 RTLIL::SigSpec new_sig_a(new_sig_a_bits);
  89
  90                 if (new_sig_a != sig_a || sig_a.size() != cell->getPort("\\A").size()) {
  91                         log("    New input vector for %s cell %s: %s\n", cell->type.c_str(), cell->name.c_str(), log_signal(new_sig_a));
  92                         did_something = true;
  93                         total_count++;
  94                 }
  95
  96                 cell->setPort("\\A", new_sig_a);
  97                 cell->parameters["\\A_WIDTH"] = RTLIL::Const(new_sig_a.size());
  98                 return;
  99         }
 100
 101         void opt_mux(RTLIL::Cell *cell)
 102         {
 103                 RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
 104                 RTLIL::SigSpec sig_b = assign_map(cell->getPort("\\B"));
 105                 RTLIL::SigSpec sig_s = assign_map(cell->getPort("\\S"));
 106
 107                 RTLIL::SigSpec new_sig_b, new_sig_s;
 108                 pool<RTLIL::SigSpec> handled_sig;
 109
 110                 handled_sig.insert(sig_a);
 111                 for (int i = 0; i < sig_s.size(); i++)
 112                 {
 113                         RTLIL::SigSpec this_b = sig_b.extract(i*sig_a.size(), sig_a.size());
 114                         if (handled_sig.count(this_b) > 0)
 115                                 continue;
 116
 117                         RTLIL::SigSpec this_s = sig_s.extract(i, 1);
 118                         for (int j = i+1; j < sig_s.size(); j++) {
 119                                 RTLIL::SigSpec that_b = sig_b.extract(j*sig_a.size(), sig_a.size());
 120                                 if (this_b == that_b)
 121                                         this_s.append(sig_s.extract(j, 1));
 122                         }
 123
 124                         if (this_s.size() > 1)
 125                         {
 126                                 RTLIL::Cell *reduce_or_cell = module->addCell(NEW_ID, "$reduce_or");
 127                                 reduce_or_cell->setPort("\\A", this_s);
 128                                 reduce_or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0);
 129                                 reduce_or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(this_s.size());
 130                                 reduce_or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
 131
 132                                 RTLIL::Wire *reduce_or_wire = module->addWire(NEW_ID);
 133                                 this_s = RTLIL::SigSpec(reduce_or_wire);
 134                                 reduce_or_cell->setPort("\\Y", this_s);
 135                         }
 136
 137                         new_sig_b.append(this_b);
 138                         new_sig_s.append(this_s);
 139                         handled_sig.insert(this_b);
 140                 }
 141
 142                 if (new_sig_s.size() != sig_s.size()) {
 143                         log("    New ctrl vector for %s cell %s: %s\n", cell->type.c_str(), cell->name.c_str(), log_signal(new_sig_s));
 144                         did_something = true;
 145                         total_count++;
 146                 }
 147
 148                 if (new_sig_s.size() == 0)
 149                 {
 150                         module->connect(RTLIL::SigSig(cell->getPort("\\Y"), cell->getPort("\\A")));
 151                         assign_map.add(cell->getPort("\\Y"), cell->getPort("\\A"));
 152                         module->remove(cell);
 153                 }
 154                 else
 155                 {
 156                         cell->setPort("\\B", new_sig_b);
 157                         cell->setPort("\\S", new_sig_s);
 158                         if (new_sig_s.size() > 1) {
 159                                 cell->parameters["\\S_WIDTH"] = RTLIL::Const(new_sig_s.size());
 160                         } else {
 161                                 cell->type = "$mux";
 162                                 cell->parameters.erase("\\S_WIDTH");
 163                         }
 164                 }
 165         }
 166
 167         void opt_mux_bits(RTLIL::Cell *cell)
 168         {
 169                 std::vector<RTLIL::SigBit> sig_a = assign_map(cell->getPort("\\A")).to_sigbit_vector();
 170                 std::vector<RTLIL::SigBit> sig_b = assign_map(cell->getPort("\\B")).to_sigbit_vector();
 171                 std::vector<RTLIL::SigBit> sig_y = assign_map(cell->getPort("\\Y")).to_sigbit_vector();
 172
 173                 std::vector<RTLIL::SigBit> new_sig_y;
 174                 RTLIL::SigSig old_sig_conn;
 175
 176                 std::vector<std::vector<RTLIL::SigBit>> consolidated_in_tuples;
 177                 std::map<std::vector<RTLIL::SigBit>, RTLIL::SigBit> consolidated_in_tuples_map;
 178
 179                 for (int i = 0; i < int(sig_y.size()); i++)
 180                 {
 181                         std::vector<RTLIL::SigBit> in_tuple;
 182                         bool all_tuple_bits_same = true;
 183
 184                         in_tuple.push_back(sig_a.at(i));
 185                         for (int j = i; j < int(sig_b.size()); j += int(sig_a.size())) {
 186                                 if (sig_b.at(j) != sig_a.at(i))
 187                                         all_tuple_bits_same = false;
 188                                 in_tuple.push_back(sig_b.at(j));
 189                         }
 190
 191                         if (all_tuple_bits_same)
 192                         {
 193                                 old_sig_conn.first.append_bit(sig_y.at(i));
 194                                 old_sig_conn.second.append_bit(sig_a.at(i));
 195                         }
 196                         else if (consolidated_in_tuples_map.count(in_tuple))
 197                         {
 198                                 old_sig_conn.first.append_bit(sig_y.at(i));
 199                                 old_sig_conn.second.append_bit(consolidated_in_tuples_map.at(in_tuple));
 200                         }
 201                         else
 202                         {
 203                                 consolidated_in_tuples_map[in_tuple] = sig_y.at(i);
 204                                 consolidated_in_tuples.push_back(in_tuple);
 205                                 new_sig_y.push_back(sig_y.at(i));
 206                         }
 207                 }
 208
 209                 if (new_sig_y.size() != sig_y.size())
 210                 {
 211                         log("    Consolidated identical input bits for %s cell %s:\n", cell->type.c_str(), cell->name.c_str());
 212                         log("      Old ports: A=%s, B=%s, Y=%s\n", log_signal(cell->getPort("\\A")),
 213                                         log_signal(cell->getPort("\\B")), log_signal(cell->getPort("\\Y")));
 214
 215                         cell->setPort("\\A", RTLIL::SigSpec());
 216                         for (auto &in_tuple : consolidated_in_tuples) {
 217                                 RTLIL::SigSpec new_a = cell->getPort("\\A");
 218                                 new_a.append(in_tuple.at(0));
 219                                 cell->setPort("\\A", new_a);
 220                         }
 221
 222                         cell->setPort("\\B", RTLIL::SigSpec());
 223                         for (int i = 1; i <= cell->getPort("\\S").size(); i++)
 224                                 for (auto &in_tuple : consolidated_in_tuples) {
 225                                         RTLIL::SigSpec new_b = cell->getPort("\\B");
 226                                         new_b.append(in_tuple.at(i));
 227                                         cell->setPort("\\B", new_b);
 228                                 }
 229
 230                         cell->parameters["\\WIDTH"] = RTLIL::Const(new_sig_y.size());
 231                         cell->setPort("\\Y", new_sig_y);
 232
 233                         log("      New ports: A=%s, B=%s, Y=%s\n", log_signal(cell->getPort("\\A")),
 234                                         log_signal(cell->getPort("\\B")), log_signal(cell->getPort("\\Y")));
 235                         log("      New connections: %s = %s\n", log_signal(old_sig_conn.first), log_signal(old_sig_conn.second));
 236
 237                         module->connect(old_sig_conn);
 238                         module->check();
 239
 240                         did_something = true;
 241                         total_count++;
 242                 }
 243         }
 244
 245         OptReduceWorker(RTLIL::Design *design, RTLIL::Module *module, bool do_fine) :
 246                         design(design), module(module), assign_map(module)
 247         {
 248                 log("  Optimizing cells in module %s.\n", module->name.c_str());
 249
 250                 total_count = 0;
 251                 did_something = true;
 252
 253                 SigPool mem_wren_sigs;
 254                 for (auto &cell_it : module->cells_) {
 255                         RTLIL::Cell *cell = cell_it.second;
 256                         if (cell->type == "$mem")
 257                                 mem_wren_sigs.add(assign_map(cell->getPort("\\WR_EN")));
 258                         if (cell->type == "$memwr")
 259                                 mem_wren_sigs.add(assign_map(cell->getPort("\\EN")));
 260                 }
 261                 for (auto &cell_it : module->cells_) {
 262                         RTLIL::Cell *cell = cell_it.second;
 263                         if (cell->type == "$dff" && mem_wren_sigs.check_any(assign_map(cell->getPort("\\Q"))))
 264                                 mem_wren_sigs.add(assign_map(cell->getPort("\\D")));
 265                 }
 266
 267                 bool keep_expanding_mem_wren_sigs = true;
 268                 while (keep_expanding_mem_wren_sigs) {
 269                         keep_expanding_mem_wren_sigs = false;
 270                         for (auto &cell_it : module->cells_) {
 271                                 RTLIL::Cell *cell = cell_it.second;
 272                                 if (cell->type == "$mux" && mem_wren_sigs.check_any(assign_map(cell->getPort("\\Y")))) {
 273                                         if (!mem_wren_sigs.check_all(assign_map(cell->getPort("\\A"))) ||
 274                                                         !mem_wren_sigs.check_all(assign_map(cell->getPort("\\B"))))
 275                                                 keep_expanding_mem_wren_sigs = true;
 276                                         mem_wren_sigs.add(assign_map(cell->getPort("\\A")));
 277                                         mem_wren_sigs.add(assign_map(cell->getPort("\\B")));
 278                                 }
 279                         }
 280                 }
 281
 282                 while (did_something)
 283                 {
 284                         did_something = false;
 285
 286                         // merge trees of reduce_* cells to one single cell and unify input vectors
 287                         // (only handle reduce_and and reduce_or for various reasons)
 288
 289                         const char *type_list[] = { "$reduce_or", "$reduce_and" };
 290                         for (auto type : type_list)
 291                         {
 292                                 SigSet<RTLIL::Cell*> drivers;
 293                                 pool<RTLIL::Cell*> cells;
 294
 295                                 for (auto &cell_it : module->cells_) {
 296                                         RTLIL::Cell *cell = cell_it.second;
 297                                         if (cell->type != type || !design->selected(module, cell))
 298                                                 continue;
 299                                         drivers.insert(assign_map(cell->getPort("\\Y")), cell);
 300                                         cells.insert(cell);
 301                                 }
 302
 303                                 while (cells.size() > 0) {
 304                                         RTLIL::Cell *cell = *cells.begin();
 305                                         opt_reduce(cells, drivers, cell);
 306                                 }
 307                         }
 308
 309                         // merge identical inputs on $mux and $pmux cells
 310
 311                         std::vector<RTLIL::Cell*> cells;
 312
 313                         for (auto &it : module->cells_)
 314                                 if ((it.second->type == "$mux" || it.second->type == "$pmux") && design->selected(module, it.second))
 315                                         cells.push_back(it.second);
 316
 317                         for (auto cell : cells)
 318                         {
 319                                 // this optimization is to aggressive for most coarse-grain applications.
 320                                 // but we always want it for multiplexers driving write enable ports.
 321                                 if (do_fine || mem_wren_sigs.check_any(assign_map(cell->getPort("\\Y"))))
 322                                         opt_mux_bits(cell);
 323
 324                                 opt_mux(cell);
 325                         }
 326                 }
 327         }
 328 };
 329
 330 struct OptReducePass : public Pass {
 331         OptReducePass() : Pass("opt_reduce", "simplify large MUXes and AND/OR gates") { }
 332         virtual void help()
 333         {
 334                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 335                 log("\n");
 336                 log("    opt_reduce [options] [selection]\n");
 337                 log("\n");
 338                 log("This pass performs two interlinked optimizations:\n");
 339                 log("\n");
 340                 log("1. it consolidates trees of large AND gates or OR gates and eliminates\n");
 341                 log("duplicated inputs.\n");
 342                 log("\n");
 343                 log("2. it identifies duplicated inputs to MUXes and replaces them with a single\n");
 344                 log("input with the original control signals OR'ed together.\n");
 345                 log("\n");
 346                 log("    -fine\n");
 347                 log("      perform fine-grain optimizations\n");
 348                 log("\n");
 349                 log("    -full\n");
 350                 log("      alias for -fine\n");
 351                 log("\n");
 352         }
 353         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 354         {
 355                 bool do_fine = false;
 356
 357                 log_header(design, "Executing OPT_REDUCE pass (consolidate $*mux and $reduce_* inputs).\n");
 358
 359                 size_t argidx;
 360                 for (argidx = 1; argidx < args.size(); argidx++) {
 361                         if (args[argidx] == "-fine") {
 362                                 do_fine = true;
 363                                 continue;
 364                         }
 365                         if (args[argidx] == "-full") {
 366                                 do_fine = true;
 367                                 continue;
 368                         }
 369                         break;
 370                 }
 371                 extra_args(args, argidx, design);
 372
 373                 int total_count = 0;
 374                 for (auto module : design->selected_modules())
 375                         while (1) {
 376                                 OptReduceWorker worker(design, module, do_fine);
 377                                 total_count += worker.total_count;
 378                                 if (worker.total_count == 0)
 379                                         break;
 380                         }
 381
 382                 if (total_count)
 383                         design->scratchpad_set_bool("opt.did_something", true);
 384                 log("Performed a total of %d changes.\n", total_count);
 385         }
 386 } OptReducePass;
 387
 388 PRIVATE_NAMESPACE_END