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,Const>> sig_cmp_prev;
  33
  34         ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap)
  35         {
  36                 SigSpec const_sig, nonconst_sig, y_port;
  37                 for (auto cell : module->cells()) {
  38                         if (cell->type == "$eq") {
  39                                 nonconst_sig = sigmap(cell->getPort("\\A"));
  40                                 const_sig = sigmap(cell->getPort("\\B"));
  41                                 if (!const_sig.is_fully_const()) {
  42                                         if (!nonconst_sig.is_fully_const())
  43                                                 continue;
  44                                         std::swap(nonconst_sig, const_sig);
  45                                 }
  46                                 y_port = sigmap(cell->getPort("\\Y"));
  47                         }
  48                         else if (cell->type == "$logic_not") {
  49                                 nonconst_sig = sigmap(cell->getPort("\\A"));
  50                                 const_sig = Const(RTLIL::S0, GetSize(nonconst_sig));
  51                                 y_port = sigmap(cell->getPort("\\Y"));
  52                         }
  53                         else continue;
  54
  55                         log_assert(!nonconst_sig.empty());
  56                         log_assert(!const_sig.empty());
  57                         sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const());
  58                 }
  59         }
  60
  61         bool query(const SigSpec &sig) const
  62         {
  63                 SigSpec nonconst_sig;
  64                 pool<Const> const_values;
  65
  66                 for (auto bit : sig.bits()) {
  67                         auto it = sig_cmp_prev.find(bit);
  68                         if (it == sig_cmp_prev.end())
  69                                 return false;
  70
  71                         if (nonconst_sig.empty())
  72                                 nonconst_sig = it->second.first;
  73                         else if (nonconst_sig != it->second.first)
  74                                 return false;
  75
  76                         if (!const_values.insert(it->second.second).second)
  77                                 return false;
  78                 }
  79
  80                 return true;
  81         }
  82 };
  83
  84
  85 struct MuxpackWorker
  86 {
  87         Module *module;
  88         SigMap sigmap;
  89
  90         int mux_count, pmux_count;
  91
  92         pool<Cell*> remove_cells;
  93
  94         dict<SigSpec, Cell*> sig_chain_next;
  95         dict<SigSpec, Cell*> sig_chain_prev;
  96         pool<SigBit> sigbit_with_non_chain_users;
  97         pool<Cell*> chain_start_cells;
  98         pool<Cell*> candidate_cells;
  99
 100         ExclusiveDatabase excl_db;
 101
 102         void make_sig_chain_next_prev()
 103         {
 104                 for (auto wire : module->wires())
 105                 {
 106                         if (wire->port_output || wire->get_bool_attribute("\\keep")) {
 107                                 for (auto bit : sigmap(wire))
 108                                         sigbit_with_non_chain_users.insert(bit);
 109                         }
 110                 }
 111
 112                 for (auto cell : module->cells())
 113                 {
 114                         if (cell->type.in("$mux", "$pmux") && !cell->get_bool_attribute("\\keep"))
 115                         {
 116                                 SigSpec a_sig = sigmap(cell->getPort("\\A"));
 117                                 SigSpec b_sig;
 118                                 if (cell->type == "$mux")
 119                                         b_sig = sigmap(cell->getPort("\\B"));
 120                                 SigSpec y_sig = sigmap(cell->getPort("\\Y"));
 121
 122                                 if (sig_chain_next.count(a_sig))
 123                                         for (auto a_bit : a_sig.bits())
 124                                                 sigbit_with_non_chain_users.insert(a_bit);
 125                                 else {
 126                                         sig_chain_next[a_sig] = cell;
 127                                         candidate_cells.insert(cell);
 128                                 }
 129
 130                                 if (!b_sig.empty()) {
 131                                         if (sig_chain_next.count(b_sig))
 132                                                 for (auto b_bit : b_sig.bits())
 133                                                         sigbit_with_non_chain_users.insert(b_bit);
 134                                         else {
 135                                                 sig_chain_next[b_sig] = cell;
 136                                                 candidate_cells.insert(cell);
 137                                         }
 138                                 }
 139
 140                                 sig_chain_prev[y_sig] = cell;
 141                                 continue;
 142                         }
 143
 144                         for (auto conn : cell->connections())
 145                                 if (cell->input(conn.first))
 146                                         for (auto bit : sigmap(conn.second))
 147                                                 sigbit_with_non_chain_users.insert(bit);
 148                 }
 149         }
 150
 151         void find_chain_start_cells()
 152         {
 153                 for (auto cell : candidate_cells)
 154                 {
 155                         log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type));
 156
 157                         SigSpec a_sig = sigmap(cell->getPort("\\A"));
 158                         if (cell->type == "$mux") {
 159                                 SigSpec b_sig = sigmap(cell->getPort("\\B"));
 160                                 if (sig_chain_prev.count(a_sig) + sig_chain_prev.count(b_sig) != 1)
 161                                         goto start_cell;
 162
 163                                 if (!sig_chain_prev.count(a_sig))
 164                                         a_sig = b_sig;
 165                         }
 166                         else if (cell->type == "$pmux") {
 167                                 if (!sig_chain_prev.count(a_sig))
 168                                         goto start_cell;
 169                         }
 170                         else log_abort();
 171
 172                         for (auto bit : a_sig.bits())
 173                                 if (sigbit_with_non_chain_users.count(bit))
 174                                         goto start_cell;
 175
 176                         {
 177                                 Cell *prev_cell = sig_chain_prev.at(a_sig);
 178                                 log_assert(prev_cell);
 179                                 SigSpec s_sig = sigmap(cell->getPort("\\S"));
 180                                 s_sig.append(sigmap(prev_cell->getPort("\\S")));
 181                                 if (!excl_db.query(s_sig))
 182                                         goto start_cell;
 183                         }
 184
 185                         continue;
 186
 187                 start_cell:
 188                         chain_start_cells.insert(cell);
 189                 }
 190         }
 191
 192         vector<Cell*> create_chain(Cell *start_cell)
 193         {
 194                 vector<Cell*> chain;
 195
 196                 Cell *c = start_cell;
 197                 while (c != nullptr)
 198                 {
 199                         chain.push_back(c);
 200
 201                         SigSpec y_sig = sigmap(c->getPort("\\Y"));
 202
 203                         if (sig_chain_next.count(y_sig) == 0)
 204                                 break;
 205
 206                         c = sig_chain_next.at(y_sig);
 207                         if (chain_start_cells.count(c) != 0)
 208                                 break;
 209                 }
 210
 211                 return chain;
 212         }
 213
 214         void process_chain(vector<Cell*> &chain)
 215         {
 216                 if (GetSize(chain) < 2)
 217                         return;
 218
 219                 int cursor = 0;
 220                 while (cursor < GetSize(chain))
 221                 {
 222                         int cases = GetSize(chain) - cursor;
 223
 224                         Cell *first_cell = chain[cursor];
 225                         dict<int, SigBit> taps_dict;
 226
 227                         if (cases < 2) {
 228                                 cursor++;
 229                                 continue;
 230                         }
 231
 232                         Cell *last_cell = chain[cursor+cases-1];
 233
 234                         log("Converting %s.%s ... %s.%s to a pmux with %d cases.\n",
 235                                 log_id(module), log_id(first_cell), log_id(module), log_id(last_cell), cases);
 236
 237                         mux_count += cases;
 238                         pmux_count += 1;
 239
 240                         first_cell->type = "$pmux";
 241                         SigSpec b_sig = first_cell->getPort("\\B");
 242                         SigSpec s_sig = first_cell->getPort("\\S");
 243
 244                         for (int i = 1; i < cases; i++) {
 245                                 Cell* prev_cell = chain[cursor+i-1];
 246                                 Cell* cursor_cell = chain[cursor+i];
 247                                 if (sigmap(prev_cell->getPort("\\Y")) == sigmap(cursor_cell->getPort("\\A"))) {
 248                                         b_sig.append(cursor_cell->getPort("\\B"));
 249                                         s_sig.append(cursor_cell->getPort("\\S"));
 250                                 }
 251                                 else {
 252                                         log_assert(cursor_cell->type == "$mux");
 253                                         b_sig.append(cursor_cell->getPort("\\A"));
 254                                         s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S")));
 255                                 }
 256                                 remove_cells.insert(cursor_cell);
 257                         }
 258
 259                         first_cell->setPort("\\B", b_sig);
 260                         first_cell->setPort("\\S", s_sig);
 261                         first_cell->setParam("\\S_WIDTH", GetSize(s_sig));
 262                         first_cell->setPort("\\Y", last_cell->getPort("\\Y"));
 263
 264                         cursor += cases;
 265                 }
 266         }
 267
 268         void cleanup()
 269         {
 270                 for (auto cell : remove_cells)
 271                         module->remove(cell);
 272
 273                 remove_cells.clear();
 274                 sig_chain_next.clear();
 275                 sig_chain_prev.clear();
 276                 chain_start_cells.clear();
 277                 candidate_cells.clear();
 278         }
 279
 280         MuxpackWorker(Module *module) :
 281                         module(module), sigmap(module), mux_count(0), pmux_count(0), excl_db(module, sigmap)
 282         {
 283                 make_sig_chain_next_prev();
 284                 find_chain_start_cells();
 285
 286                 for (auto c : chain_start_cells) {
 287                         vector<Cell*> chain = create_chain(c);
 288                         process_chain(chain);
 289                 }
 290
 291                 cleanup();
 292         }
 293 };
 294
 295 struct MuxpackPass : public Pass {
 296         MuxpackPass() : Pass("muxpack", "$mux/$pmux cascades to $pmux") { }
 297         void help() YS_OVERRIDE
 298         {
 299                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 300                 log("\n");
 301                 log("    muxpack [selection]\n");
 302                 log("\n");
 303                 log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n");
 304                 log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n");
 305                 log("$pmux cells.\n");
 306                 log("\n");
 307                 log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n");
 308                 log("whose select lines are driven by '$eq' cells with other such cells if it can be\n");
 309                 log("certain that their select inputs are mutually exclusive.\n");
 310                 log("\n");
 311         }
 312         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 313         {
 314                 log_header(design, "Executing MUXPACK pass ($mux cell cascades to $pmux).\n");
 315
 316                 size_t argidx;
 317                 for (argidx = 1; argidx < args.size(); argidx++)
 318                 {
 319                         break;
 320                 }
 321                 extra_args(args, argidx, design);
 322
 323                 int mux_count = 0;
 324                 int pmux_count = 0;
 325
 326                 for (auto module : design->selected_modules()) {
 327                         MuxpackWorker worker(module);
 328                         mux_count += worker.mux_count;
 329                         pmux_count += worker.pmux_count;
 330                 }
 331
 332                 log("Converted %d (p)mux cells into %d pmux cells.\n", mux_count, pmux_count);
 333         }
 334 } MuxpackPass;
 335
 336 PRIVATE_NAMESPACE_END