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 MuxpackWorker
  28 {
  29         Module *module;
  30         SigMap sigmap;
  31
  32         int mux_count, pmux_count;
  33
  34         pool<Cell*> remove_cells;
  35
  36         dict<SigSpec, Cell*> sig_chain_next;
  37         dict<SigSpec, Cell*> sig_chain_prev;
  38         pool<SigBit> sigbit_with_non_chain_users;
  39         pool<Cell*> chain_start_cells;
  40         pool<Cell*> candidate_cells;
  41
  42         void make_sig_chain_next_prev()
  43         {
  44                 for (auto wire : module->wires())
  45                 {
  46                         if (wire->port_output || wire->get_bool_attribute("\\keep")) {
  47                                 for (auto bit : sigmap(wire))
  48                                         sigbit_with_non_chain_users.insert(bit);
  49                         }
  50                 }
  51
  52                 for (auto cell : module->cells())
  53                 {
  54                         if (cell->type.in("$mux", "$pmux") && !cell->get_bool_attribute("\\keep"))
  55                         {
  56                                 SigSpec a_sig = sigmap(cell->getPort("\\A"));
  57                                 SigSpec b_sig;
  58                                 if (cell->type == "$mux")
  59                                         b_sig = sigmap(cell->getPort("\\B"));
  60                                 SigSpec y_sig = sigmap(cell->getPort("\\Y"));
  61
  62                                 if (sig_chain_next.count(a_sig))
  63                                         for (auto a_bit : a_sig.bits())
  64                                                 sigbit_with_non_chain_users.insert(a_bit);
  65                                 else {
  66                                         sig_chain_next[a_sig] = cell;
  67                                         candidate_cells.insert(cell);
  68                                 }
  69
  70                                 if (!b_sig.empty()) {
  71                                         if (sig_chain_next.count(b_sig))
  72                                                 for (auto b_bit : b_sig.bits())
  73                                                         sigbit_with_non_chain_users.insert(b_bit);
  74                                         else {
  75                                                 sig_chain_next[b_sig] = cell;
  76                                                 candidate_cells.insert(cell);
  77                                         }
  78                                 }
  79
  80                                 sig_chain_prev[y_sig] = cell;
  81                                 continue;
  82                         }
  83
  84                         for (auto conn : cell->connections())
  85                                 if (cell->input(conn.first))
  86                                         for (auto bit : sigmap(conn.second))
  87                                                 sigbit_with_non_chain_users.insert(bit);
  88                 }
  89         }
  90
  91         void find_chain_start_cells()
  92         {
  93                 for (auto cell : candidate_cells)
  94                 {
  95                         log_debug("Considering %s (%s)\n", log_id(cell), log_id(cell->type));
  96
  97                         SigSpec a_sig = cell->getPort("\\A");
  98                         if (cell->type == "$mux") {
  99                                 SigSpec b_sig = cell->getPort("\\B");
 100                                 if (sig_chain_prev.count(a_sig) + sig_chain_prev.count(b_sig) != 1)
 101                                         goto start_cell;
 102
 103                                 if (!sig_chain_prev.count(a_sig))
 104                                         a_sig = b_sig;
 105                         }
 106                         else if (cell->type == "$pmux") {
 107                                 if (!sig_chain_prev.count(a_sig))
 108                                         goto start_cell;
 109                         }
 110                         else log_abort();
 111
 112                         {
 113                                 for (auto bit : a_sig.bits())
 114                                         if (sigbit_with_non_chain_users.count(bit))
 115                                                 goto start_cell;
 116
 117                                 Cell *c1 = sig_chain_prev.at(a_sig);
 118                                 Cell *c2 = cell;
 119
 120                                 if (c1->getParam("\\WIDTH") != c2->getParam("\\WIDTH"))
 121                                         goto start_cell;
 122                         }
 123
 124                         continue;
 125
 126                 start_cell:
 127                         chain_start_cells.insert(cell);
 128                 }
 129         }
 130
 131         vector<Cell*> create_chain(Cell *start_cell)
 132         {
 133                 vector<Cell*> chain;
 134
 135                 Cell *c = start_cell;
 136                 while (c != nullptr)
 137                 {
 138                         chain.push_back(c);
 139
 140                         SigSpec y_sig = sigmap(c->getPort("\\Y"));
 141
 142                         if (sig_chain_next.count(y_sig) == 0)
 143                                 break;
 144
 145                         c = sig_chain_next.at(y_sig);
 146                         if (chain_start_cells.count(c) != 0)
 147                                 break;
 148                 }
 149
 150                 return chain;
 151         }
 152
 153         void process_chain(vector<Cell*> &chain)
 154         {
 155                 if (GetSize(chain) < 2)
 156                         return;
 157
 158                 int cursor = 0;
 159                 while (cursor < GetSize(chain))
 160                 {
 161                         int cases = GetSize(chain) - cursor;
 162
 163                         Cell *first_cell = chain[cursor];
 164                         dict<int, SigBit> taps_dict;
 165
 166                         if (cases < 2) {
 167                                 cursor++;
 168                                 continue;
 169                         }
 170
 171                         Cell *last_cell = chain[cursor+cases-1];
 172
 173                         log("Converting %s.%s ... %s.%s to a pmux with %d cases.\n",
 174                                 log_id(module), log_id(first_cell), log_id(module), log_id(last_cell), cases);
 175
 176                         mux_count += cases;
 177                         pmux_count += 1;
 178
 179                         first_cell->type = "$pmux";
 180                         SigSpec b_sig = first_cell->getPort("\\B");
 181                         SigSpec s_sig = first_cell->getPort("\\S");
 182
 183                         for (int i = 1; i < cases; i++) {
 184                                 Cell* prev_cell = chain[cursor+i-1];
 185                                 Cell* cursor_cell = chain[cursor+i];
 186                                 if (sigmap(prev_cell->getPort("\\Y")) == sigmap(cursor_cell->getPort("\\A"))) {
 187                                         b_sig.append(cursor_cell->getPort("\\B"));
 188                                         s_sig.append(cursor_cell->getPort("\\S"));
 189                                 }
 190                                 else {
 191                                         b_sig.append(cursor_cell->getPort("\\A"));
 192                                         s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S")));
 193                                 }
 194                                 remove_cells.insert(cursor_cell);
 195                         }
 196
 197                         first_cell->setPort("\\B", b_sig);
 198                         first_cell->setPort("\\S", s_sig);
 199                         first_cell->setParam("\\S_WIDTH", GetSize(s_sig));
 200                         first_cell->setPort("\\Y", last_cell->getPort("\\Y"));
 201
 202                         cursor += cases;
 203                 }
 204         }
 205
 206         void cleanup()
 207         {
 208                 for (auto cell : remove_cells)
 209                         module->remove(cell);
 210
 211                 remove_cells.clear();
 212                 sig_chain_next.clear();
 213                 sig_chain_prev.clear();
 214                 chain_start_cells.clear();
 215                 candidate_cells.clear();
 216         }
 217
 218         MuxpackWorker(Module *module) :
 219                         module(module), sigmap(module), mux_count(0), pmux_count(0)
 220         {
 221                 make_sig_chain_next_prev();
 222                 find_chain_start_cells();
 223
 224                 for (auto c : chain_start_cells) {
 225                         vector<Cell*> chain = create_chain(c);
 226                         process_chain(chain);
 227                 }
 228
 229                 cleanup();
 230         }
 231 };
 232
 233 struct MuxpackPass : public Pass {
 234         MuxpackPass() : Pass("muxpack", "$mux/$pmux cascades to $pmux") { }
 235         void help() YS_OVERRIDE
 236         {
 237                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 238                 log("\n");
 239                 log("    muxpack [selection]\n");
 240                 log("\n");
 241                 log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n");
 242                 log("constructs) and $mux cells (e.g. those created by if-else constructs) into \n");
 243                 log("into $pmux cells.\n");
 244                 log("\n");
 245         }
 246         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 247         {
 248                 log_header(design, "Executing MUXPACK pass ($mux cell cascades to $pmux).\n");
 249
 250                 size_t argidx;
 251                 for (argidx = 1; argidx < args.size(); argidx++)
 252                 {
 253                         break;
 254                 }
 255                 extra_args(args, argidx, design);
 256
 257                 int mux_count = 0;
 258                 int pmux_count = 0;
 259
 260                 for (auto module : design->selected_modules()) {
 261                         MuxpackWorker worker(module);
 262                         mux_count += worker.mux_count;
 263                         pmux_count += worker.pmux_count;
 264                 }
 265
 266                 log("Converted %d (p)mux cells into %d pmux cells.\n", mux_count, pmux_count);
 267         }
 268 } MuxpackPass;
 269
 270 PRIVATE_NAMESPACE_END