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