passes/techmap/dff2dffe.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/yosys.h"
  21 #include "kernel/sigtools.h"
  22 #include "kernel/celltypes.h"
  23 #include "passes/techmap/simplemap.h"
  24
  25 USING_YOSYS_NAMESPACE
  26 PRIVATE_NAMESPACE_BEGIN
  27
  28 struct Dff2dffeWorker
  29 {
  30         RTLIL::Module *module;
  31         SigMap sigmap;
  32         CellTypes ct;
  33
  34         typedef std::pair<RTLIL::Cell*, int> cell_int_t;
  35         std::map<RTLIL::SigBit, cell_int_t> bit2mux;
  36         std::vector<RTLIL::Cell*> dff_cells;
  37         std::map<RTLIL::SigBit, int> bitusers;
  38
  39         typedef std::map<RTLIL::SigBit, bool> pattern_t;
  40         typedef std::set<pattern_t> patterns_t;
  41
  42         Dff2dffeWorker(RTLIL::Module *module) : module(module), sigmap(module), ct(module->design)
  43         {
  44                 for (auto wire : module->wires()) {
  45                         if (wire->port_output)
  46                                 for (auto bit : sigmap(wire))
  47                                         bitusers[bit]++;
  48                 }
  49
  50                 for (auto cell : module->cells()) {
  51                         if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$_MUX_") {
  52                                 RTLIL::SigSpec sig_y = sigmap(cell->getPort("\\Y"));
  53                                 for (int i = 0; i < GetSize(sig_y); i++)
  54                                         bit2mux[sig_y[i]] = cell_int_t(cell, i);
  55                         }
  56                         if (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_")
  57                                 dff_cells.push_back(cell);
  58                         for (auto conn : cell->connections()) {
  59                                 if (ct.cell_output(cell->type, conn.first))
  60                                         continue;
  61                                 for (auto bit : sigmap(conn.second))
  62                                         bitusers[bit]++;
  63                         }
  64                 }
  65         }
  66
  67         patterns_t find_muxtree_feedback_patterns(RTLIL::SigBit d, RTLIL::SigBit q, pattern_t path)
  68         {
  69                 patterns_t ret;
  70
  71                 if (d == q) {
  72                         ret.insert(path);
  73                         return ret;
  74                 }
  75
  76                 if (bit2mux.count(d) == 0 || bitusers[d] > 1)
  77                         return ret;
  78
  79                 cell_int_t mux_cell_int = bit2mux.at(d);
  80                 RTLIL::SigSpec sig_a = sigmap(mux_cell_int.first->getPort("\\A"));
  81                 RTLIL::SigSpec sig_b = sigmap(mux_cell_int.first->getPort("\\B"));
  82                 RTLIL::SigSpec sig_s = sigmap(mux_cell_int.first->getPort("\\S"));
  83                 int width = GetSize(sig_a), index = mux_cell_int.second;
  84
  85                 for (int i = 0; i < GetSize(sig_s); i++)
  86                         if (path.count(sig_s[i]) && path.at(sig_s[i]))
  87                         {
  88                                 ret = find_muxtree_feedback_patterns(sig_b[i*width + index], q, path);
  89
  90                                 if (sig_b[i*width + index] == q) {
  91                                         RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
  92                                         s[i*width + index] = RTLIL::Sx;
  93                                         mux_cell_int.first->setPort("\\B", s);
  94                                 }
  95
  96                                 return ret;
  97                         }
  98
  99                 pattern_t path_else = path;
 100
 101                 for (int i = 0; i < GetSize(sig_s); i++)
 102                 {
 103                         if (path.count(sig_s[i]))
 104                                 continue;
 105
 106                         pattern_t path_this = path;
 107                         path_else[sig_s[i]] = false;
 108                         path_this[sig_s[i]] = true;
 109
 110                         for (auto &pat : find_muxtree_feedback_patterns(sig_b[i*width + index], q, path_this))
 111                                 ret.insert(pat);
 112
 113                         if (sig_b[i*width + index] == q) {
 114                                 RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
 115                                 s[i*width + index] = RTLIL::Sx;
 116                                 mux_cell_int.first->setPort("\\B", s);
 117                         }
 118                 }
 119
 120                 for (auto &pat : find_muxtree_feedback_patterns(sig_a[index], q, path_else))
 121                         ret.insert(pat);
 122
 123                 if (sig_a[index] == q) {
 124                         RTLIL::SigSpec s = mux_cell_int.first->getPort("\\A");
 125                         s[index] = RTLIL::Sx;
 126                         mux_cell_int.first->setPort("\\A", s);
 127                 }
 128
 129                 return ret;
 130         }
 131
 132         void simplify_patterns(patterns_t&)
 133         {
 134                 // TBD
 135         }
 136
 137         RTLIL::SigSpec make_patterns_logic(patterns_t patterns, bool make_gates)
 138         {
 139                 RTLIL::SigSpec or_input;
 140
 141                 for (auto pat : patterns)
 142                 {
 143                         RTLIL::SigSpec s1, s2;
 144                         for (auto it : pat) {
 145                                 s1.append(it.first);
 146                                 s2.append(it.second);
 147                         }
 148
 149                         RTLIL::SigSpec y = module->addWire(NEW_ID);
 150                         RTLIL::Cell *c = module->addNe(NEW_ID, s1, s2, y);
 151
 152                         if (make_gates) {
 153                                 simplemap(module, c);
 154                                 module->remove(c);
 155                         }
 156
 157                         or_input.append(y);
 158                 }
 159
 160                 if (GetSize(or_input) == 0)
 161                         return RTLIL::S1;
 162
 163                 if (GetSize(or_input) == 1)
 164                         return or_input;
 165
 166                 RTLIL::SigSpec y = module->addWire(NEW_ID);
 167                 RTLIL::Cell *c = module->addReduceOr(NEW_ID, or_input, y);
 168
 169                 if (make_gates) {
 170                         simplemap(module, c);
 171                         module->remove(c);
 172                 }
 173
 174                 return y;
 175         }
 176
 177         void handle_dff_cell(RTLIL::Cell *dff_cell)
 178         {
 179                 RTLIL::SigSpec sig_d = sigmap(dff_cell->getPort("\\D"));
 180                 RTLIL::SigSpec sig_q = sigmap(dff_cell->getPort("\\Q"));
 181
 182                 std::map<patterns_t, std::set<int>> grouped_patterns;
 183                 std::set<int> remaining_indices;
 184
 185                 for (int i = 0 ; i < GetSize(sig_d); i++) {
 186                         patterns_t patterns = find_muxtree_feedback_patterns(sig_d[i], sig_q[i], pattern_t());
 187                         if (!patterns.empty()) {
 188                                 simplify_patterns(patterns);
 189                                 grouped_patterns[patterns].insert(i);
 190                         } else
 191                                 remaining_indices.insert(i);
 192                 }
 193
 194                 for (auto &it : grouped_patterns) {
 195                         RTLIL::SigSpec new_sig_d, new_sig_q;
 196                         for (int i : it.second) {
 197                                 new_sig_d.append(sig_d[i]);
 198                                 new_sig_q.append(sig_q[i]);
 199                         }
 200                         if (dff_cell->type == "$dff") {
 201                                 RTLIL::Cell *new_cell = module->addDffe(NEW_ID, dff_cell->getPort("\\CLK"), make_patterns_logic(it.first, false),
 202                                                 new_sig_d, new_sig_q, dff_cell->getParam("\\CLK_POLARITY").as_bool(), true);
 203                                 log("  created $dffe cell %s for %s -> %s.\n", log_id(new_cell), log_signal(new_sig_d), log_signal(new_sig_q));
 204                         } else {
 205                                 RTLIL::Cell *new_cell = module->addDffeGate(NEW_ID, dff_cell->getPort("\\C"), make_patterns_logic(it.first, true),
 206                                                 new_sig_d, new_sig_q, dff_cell->type == "$_DFF_P_", true);
 207                                 log("  created %s cell %s for %s -> %s.\n", log_id(new_cell->type), log_id(new_cell), log_signal(new_sig_d), log_signal(new_sig_q));
 208                         }
 209                 }
 210
 211                 if (remaining_indices.empty()) {
 212                         log("  removing now obsolete cell %s.\n", log_id(dff_cell));
 213                         module->remove(dff_cell);
 214                 } else if (GetSize(remaining_indices) != GetSize(sig_d)) {
 215                         log("  removing %d now obsolete bits from cell %s.\n", GetSize(sig_d) - GetSize(remaining_indices), log_id(dff_cell));
 216                         RTLIL::SigSpec new_sig_d, new_sig_q;
 217                         for (int i : remaining_indices) {
 218                                 new_sig_d.append(sig_d[i]);
 219                                 new_sig_q.append(sig_q[i]);
 220                         }
 221                         dff_cell->setPort("\\D", new_sig_d);
 222                         dff_cell->setPort("\\Q", new_sig_q);
 223                         dff_cell->setParam("\\WIDTH", GetSize(remaining_indices));
 224                 }
 225         }
 226
 227         void run()
 228         {
 229                 log("Transforming $dff to $dffe cells in module %s:\n", log_id(module));
 230                 for (auto dff_cell : dff_cells)
 231                         handle_dff_cell(dff_cell);
 232         }
 233 };
 234
 235 struct Dff2dffePass : public Pass {
 236         Dff2dffePass() : Pass("dff2dffe", "transform $dff cells to $dffe cells") { }
 237         virtual void help()
 238         {
 239                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 240                 log("\n");
 241                 log("    dff2dffe [selection]\n");
 242                 log("\n");
 243                 log("This pass transforms $dff cells driven by a tree of multiplexers with one or\n");
 244                 log("more feedback paths to $dffe cells.\n");
 245                 log("\n");
 246         }
 247         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 248         {
 249                 log_header("Executing DFF2DFFE pass (transform $dff to $dffe where applicable).\n");
 250
 251                 size_t argidx;
 252                 for (argidx = 1; argidx < args.size(); argidx++) {
 253                         // if (args[argidx] == "-foobar") {
 254                         //      foobar_mode = true;
 255                         //      continue;
 256                         // }
 257                         break;
 258                 }
 259                 extra_args(args, argidx, design);
 260
 261                 for (auto mod : design->selected_modules())
 262                         if (!mod->has_processes_warn()) {
 263                                 Dff2dffeWorker worker(mod);
 264                                 worker.run();
 265                         }
 266         }
 267 } Dff2dffePass;
 268
 269 PRIVATE_NAMESPACE_END