passes/opt/muxpack.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   5  *                2019  Eddie Hung    <eddie@fpgeh.com>
   6  *
   7  *  Permission to use, copy, modify, and/or distribute this software for any
   8  *  purpose with or without fee is hereby granted, provided that the above
   9  *  copyright notice and this permission notice appear in all copies.
  10  *
  11  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  *
  19  */
  20
  21 #include "kernel/yosys.h"
  22 #include "kernel/sigtools.h"
  23
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct ExclusiveDatabase
  28 {
  29         Module *module;
  30         const SigMap &sigmap;
  31
  32         dict<SigBit, std::pair<SigSpec,std::vector<Const>>> sig_cmp_prev;
  33
  34         ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap)
  35         {
  36                 SigSpec const_sig, nonconst_sig;
  37                 SigBit y_port;
  38                 pool<Cell*> reduce_or;
  39                 for (auto cell : module->cells()) {
  40                         if (cell->type == "$eq") {
  41                                 nonconst_sig = sigmap(cell->getPort("\\A"));
  42                                 const_sig = sigmap(cell->getPort("\\B"));
  43                                 if (!const_sig.is_fully_const()) {
  44                                         if (!nonconst_sig.is_fully_const())
  45                                                 continue;
  46                                         std::swap(nonconst_sig, const_sig);
  47                                 }
  48                                 y_port = sigmap(cell->getPort("\\Y"));
  49                         }
  50                         else if (cell->type == "$logic_not") {
  51                                 nonconst_sig = sigmap(cell->getPort("\\A"));
  52                                 const_sig = Const(RTLIL::S0, GetSize(nonconst_sig));
  53                                 y_port = sigmap(cell->getPort("\\Y"));
  54                         }
  55                         else if (cell->type == "$reduce_or") {
  56                                 reduce_or.insert(cell);
  57                                 continue;
  58                         }
  59                         else continue;
  60
  61                         log_assert(!nonconst_sig.empty());
  62                         log_assert(!const_sig.empty());
  63                         sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::vector<Const>{const_sig.as_const()});
  64                 }
  65
  66                 for (auto cell : reduce_or) {
  67                         nonconst_sig = SigSpec();
  68                         std::vector<Const> values;
  69                         SigSpec a_port = sigmap(cell->getPort("\\A"));
  70                         for (auto bit : a_port) {
  71                                 auto it = sig_cmp_prev.find(bit);
  72                                 if (it == sig_cmp_prev.end()) {
  73                                         nonconst_sig = SigSpec();
  74                                         break;
  75                                 }
  76                                 if (nonconst_sig.empty())
  77                                         nonconst_sig = it->second.first;
  78                                 else if (nonconst_sig != it->second.first) {
  79                                         nonconst_sig = SigSpec();
  80                                         break;
  81                                 }
  82                                 for (auto value : it->second.second)
  83                                         values.push_back(value);
  84                         }
  85                         if (nonconst_sig.empty())
  86                                 continue;
  87                         y_port = sigmap(cell->getPort("\\Y"));
  88                         sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::move(values));
  89                 }
  90         }
  91
  92         bool query(const SigSpec &sig) const
  93         {
  94                 SigSpec nonconst_sig;
  95                 pool<Const> const_values;
  96
  97                 for (auto bit : sig.bits()) {
  98                         auto it = sig_cmp_prev.find(bit);
  99                         if (it == sig_cmp_prev.end())
 100                                 return false;
 101
 102                         if (nonconst_sig.empty())
 103                                 nonconst_sig = it->second.first;
 104                         else if (nonconst_sig != it->second.first)
 105                                 return false;
 106
 107                         for (auto value : it->second.second)
 108                                 if (!const_values.insert(value).second)
 109                                         return false;
 110                 }
 111
 112                 return true;
 113         }
 114 };
 115
 116
 117 struct MuxpackWorker
 118 {
 119         Module *module;
 120         SigMap sigmap;
 121
 122         int mux_count, pmux_count;
 123
 124         pool<Cell*> remove_cells;
 125
 126         dict<SigSpec, Cell*> sig_chain_next;
 127         dict<SigSpec, Cell*> sig_chain_prev;
 128         pool<SigBit> sigbit_with_non_chain_users;
 129         pool<Cell*> chain_start_cells;
 130         pool<Cell*> candidate_cells;
 131
 132         ExclusiveDatabase excl_db;
 133
 134         void make_sig_chain_next_prev()
 135         {
 136                 for (auto wire : module->wires())
 137                 {
 138                         if (wire->port_output || wire->get_bool_attribute("\\keep")) {
 139                                 for (auto bit : sigmap(wire))
 140                                         sigbit_with_non_chain_users.insert(bit);
 141                         }
 142                 }
 143
 144                 for (auto cell : module->cells())
 145                 {
 146                         if (cell->type.in("$mux", "$pmux") && !cell->get_bool_attribute("\\keep"))
 147                         {
 148                                 SigSpec a_sig = sigmap(cell->getPort("\\A"));
 149                                 SigSpec b_sig;
 150                                 if (cell->type == "$mux")
 151                                         b_sig = sigmap(cell->getPort("\\B"));
 152                                 SigSpec y_sig = sigmap(cell->getPort("\\Y"));
 153
 154                                 if (sig_chain_next.count(a_sig))
 155                                         for (auto a_bit : a_sig.bits())
 156                                                 sigbit_with_non_chain_users.insert(a_bit);
 157                                 else {
 158                                         sig_chain_next[a_sig] = cell;
 159                                         candidate_cells.insert(cell);
 160                                 }
 161
 162                                 if (!b_sig.empty()) {
 163                                         if (sig_chain_next.count(b_sig))
 164                                                 for (auto b_bit : b_sig.bits())
 165                                                         sigbit_with_non_chain_users.insert(b_bit);
 166                                         else {
 167                                                 sig_chain_next[b_sig] = cell;
 168                                                 candidate_cells.insert(cell);
 169                                         }
 170                                 }
 171
 172                                 sig_chain_prev[y_sig] = cell;
 173                                 continue;
 174                         }
 175
 176                         for (auto conn : cell->connections())
 177                                 if (cell->input(conn.first))
 178                                         for (auto bit : sigmap(conn.second))
 179                                                 sigbit_with_non_chain_users.insert(bit);
 180                 }
 181         }
 182
 183         void find_chain_start_cells()
 184         {
 185                 for (auto cell : candidate_cells)
 186                 {
 187                         log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type));
 188
 189                         SigSpec a_sig = sigmap(cell->getPort("\\A"));
 190                         if (cell->type == "$mux") {
 191                                 SigSpec b_sig = sigmap(cell->getPort("\\B"));
 192                                 if (sig_chain_prev.count(a_sig) + sig_chain_prev.count(b_sig) != 1)
 193                                         goto start_cell;
 194
 195                                 if (!sig_chain_prev.count(a_sig))
 196                                         a_sig = b_sig;
 197                         }
 198                         else if (cell->type == "$pmux") {
 199                                 if (!sig_chain_prev.count(a_sig))
 200                                         goto start_cell;
 201                         }
 202                         else log_abort();
 203
 204                         for (auto bit : a_sig.bits())
 205                                 if (sigbit_with_non_chain_users.count(bit))
 206                                         goto start_cell;
 207
 208                         {
 209                                 Cell *prev_cell = sig_chain_prev.at(a_sig);
 210                                 log_assert(prev_cell);
 211                                 SigSpec s_sig = sigmap(cell->getPort("\\S"));
 212                                 s_sig.append(sigmap(prev_cell->getPort("\\S")));
 213                                 if (!excl_db.query(s_sig))
 214                                         goto start_cell;
 215                         }
 216
 217                         continue;
 218
 219                 start_cell:
 220                         chain_start_cells.insert(cell);
 221                 }
 222         }
 223
 224         vector<Cell*> create_chain(Cell *start_cell)
 225         {
 226                 vector<Cell*> chain;
 227
 228                 Cell *c = start_cell;
 229                 while (c != nullptr)
 230                 {
 231                         chain.push_back(c);
 232
 233                         SigSpec y_sig = sigmap(c->getPort("\\Y"));
 234
 235                         if (sig_chain_next.count(y_sig) == 0)
 236                                 break;
 237
 238                         c = sig_chain_next.at(y_sig);
 239                         if (chain_start_cells.count(c) != 0)
 240                                 break;
 241                 }
 242
 243                 return chain;
 244         }
 245
 246         void process_chain(vector<Cell*> &chain)
 247         {
 248                 if (GetSize(chain) < 2)
 249                         return;
 250
 251                 int cursor = 0;
 252                 while (cursor < GetSize(chain))
 253                 {
 254                         int cases = GetSize(chain) - cursor;
 255
 256                         Cell *first_cell = chain[cursor];
 257                         dict<int, SigBit> taps_dict;
 258
 259                         if (cases < 2) {
 260                                 cursor++;
 261                                 continue;
 262                         }
 263
 264                         Cell *last_cell = chain[cursor+cases-1];
 265
 266                         log("Converting %s.%s ... %s.%s to a pmux with %d cases.\n",
 267                                 log_id(module), log_id(first_cell), log_id(module), log_id(last_cell), cases);
 268
 269                         mux_count += cases;
 270                         pmux_count += 1;
 271
 272                         first_cell->type = "$pmux";
 273                         SigSpec b_sig = first_cell->getPort("\\B");
 274                         SigSpec s_sig = first_cell->getPort("\\S");
 275
 276                         for (int i = 1; i < cases; i++) {
 277                                 Cell* prev_cell = chain[cursor+i-1];
 278                                 Cell* cursor_cell = chain[cursor+i];
 279                                 if (sigmap(prev_cell->getPort("\\Y")) == sigmap(cursor_cell->getPort("\\A"))) {
 280                                         b_sig.append(cursor_cell->getPort("\\B"));
 281                                         s_sig.append(cursor_cell->getPort("\\S"));
 282                                 }
 283                                 else {
 284                                         log_assert(cursor_cell->type == "$mux");
 285                                         b_sig.append(cursor_cell->getPort("\\A"));
 286                                         s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S")));
 287                                 }
 288                                 remove_cells.insert(cursor_cell);
 289                         }
 290
 291                         first_cell->setPort("\\B", b_sig);
 292                         first_cell->setPort("\\S", s_sig);
 293                         first_cell->setParam("\\S_WIDTH", GetSize(s_sig));
 294                         first_cell->setPort("\\Y", last_cell->getPort("\\Y"));
 295
 296                         cursor += cases;
 297                 }
 298         }
 299
 300         void cleanup()
 301         {
 302                 for (auto cell : remove_cells)
 303                         module->remove(cell);
 304
 305                 remove_cells.clear();
 306                 sig_chain_next.clear();
 307                 sig_chain_prev.clear();
 308                 chain_start_cells.clear();
 309                 candidate_cells.clear();
 310         }
 311
 312         MuxpackWorker(Module *module) :
 313                         module(module), sigmap(module), mux_count(0), pmux_count(0), excl_db(module, sigmap)
 314         {
 315                 make_sig_chain_next_prev();
 316                 find_chain_start_cells();
 317
 318                 for (auto c : chain_start_cells) {
 319                         vector<Cell*> chain = create_chain(c);
 320                         process_chain(chain);
 321                 }
 322
 323                 cleanup();
 324         }
 325 };
 326
 327 struct MuxpackPass : public Pass {
 328         MuxpackPass() : Pass("muxpack", "$mux/$pmux cascades to $pmux") { }
 329         void help() YS_OVERRIDE
 330         {
 331                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 332                 log("\n");
 333                 log("    muxpack [selection]\n");
 334                 log("\n");
 335                 log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n");
 336                 log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n");
 337                 log("$pmux cells.\n");
 338                 log("\n");
 339                 log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n");
 340                 log("whose select lines are driven by '$eq' cells with other such cells if it can be\n");
 341                 log("certain that their select inputs are mutually exclusive.\n");
 342                 log("\n");
 343         }
 344         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 345         {
 346                 log_header(design, "Executing MUXPACK pass ($mux cell cascades to $pmux).\n");
 347
 348                 size_t argidx;
 349                 for (argidx = 1; argidx < args.size(); argidx++)
 350                 {
 351                         break;
 352                 }
 353                 extra_args(args, argidx, design);
 354
 355                 int mux_count = 0;
 356                 int pmux_count = 0;
 357
 358                 for (auto module : design->selected_modules()) {
 359                         MuxpackWorker worker(module);
 360                         mux_count += worker.mux_count;
 361                         pmux_count += worker.pmux_count;
 362                 }
 363
 364                 log("Converted %d (p)mux cells into %d pmux cells.\n", mux_count, pmux_count);
 365         }
 366 } MuxpackPass;
 367
 368 PRIVATE_NAMESPACE_END