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         const dict<IdString, IdString> &direct_dict;
  31
  32         RTLIL::Module *module;
  33         SigMap sigmap;
  34         CellTypes ct;
  35
  36         typedef std::pair<RTLIL::Cell*, int> cell_int_t;
  37         std::map<RTLIL::SigBit, cell_int_t> bit2mux;
  38         std::vector<RTLIL::Cell*> dff_cells;
  39         std::map<RTLIL::SigBit, int> bitusers;
  40
  41         typedef std::map<RTLIL::SigBit, bool> pattern_t;
  42         typedef std::set<pattern_t> patterns_t;
  43
  44
  45         Dff2dffeWorker(RTLIL::Module *module, const dict<IdString, IdString> &direct_dict) :
  46                         direct_dict(direct_dict), module(module), sigmap(module), ct(module->design)
  47         {
  48                 for (auto wire : module->wires()) {
  49                         if (wire->port_output)
  50                                 for (auto bit : sigmap(wire))
  51                                         bitusers[bit]++;
  52                 }
  53
  54                 for (auto cell : module->cells()) {
  55                         if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$_MUX_") {
  56                                 RTLIL::SigSpec sig_y = sigmap(cell->getPort("\\Y"));
  57                                 for (int i = 0; i < GetSize(sig_y); i++)
  58                                         bit2mux[sig_y[i]] = cell_int_t(cell, i);
  59                         }
  60                         if (direct_dict.empty()) {
  61                                 if (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_")
  62                                         dff_cells.push_back(cell);
  63                         } else {
  64                                 if (direct_dict.count(cell->type))
  65                                         dff_cells.push_back(cell);
  66                         }
  67                         for (auto conn : cell->connections()) {
  68                                 if (ct.cell_output(cell->type, conn.first))
  69                                         continue;
  70                                 for (auto bit : sigmap(conn.second))
  71                                         bitusers[bit]++;
  72                         }
  73                 }
  74         }
  75
  76         patterns_t find_muxtree_feedback_patterns(RTLIL::SigBit d, RTLIL::SigBit q, pattern_t path)
  77         {
  78                 patterns_t ret;
  79
  80                 if (d == q) {
  81                         ret.insert(path);
  82                         return ret;
  83                 }
  84
  85                 if (bit2mux.count(d) == 0 || bitusers[d] > 1)
  86                         return ret;
  87
  88                 cell_int_t mux_cell_int = bit2mux.at(d);
  89                 RTLIL::SigSpec sig_a = sigmap(mux_cell_int.first->getPort("\\A"));
  90                 RTLIL::SigSpec sig_b = sigmap(mux_cell_int.first->getPort("\\B"));
  91                 RTLIL::SigSpec sig_s = sigmap(mux_cell_int.first->getPort("\\S"));
  92                 int width = GetSize(sig_a), index = mux_cell_int.second;
  93
  94                 for (int i = 0; i < GetSize(sig_s); i++)
  95                         if (path.count(sig_s[i]) && path.at(sig_s[i]))
  96                         {
  97                                 ret = find_muxtree_feedback_patterns(sig_b[i*width + index], q, path);
  98
  99                                 if (sig_b[i*width + index] == q) {
 100                                         RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
 101                                         s[i*width + index] = RTLIL::Sx;
 102                                         mux_cell_int.first->setPort("\\B", s);
 103                                 }
 104
 105                                 return ret;
 106                         }
 107
 108                 pattern_t path_else = path;
 109
 110                 for (int i = 0; i < GetSize(sig_s); i++)
 111                 {
 112                         if (path.count(sig_s[i]))
 113                                 continue;
 114
 115                         pattern_t path_this = path;
 116                         path_else[sig_s[i]] = false;
 117                         path_this[sig_s[i]] = true;
 118
 119                         for (auto &pat : find_muxtree_feedback_patterns(sig_b[i*width + index], q, path_this))
 120                                 ret.insert(pat);
 121
 122                         if (sig_b[i*width + index] == q) {
 123                                 RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
 124                                 s[i*width + index] = RTLIL::Sx;
 125                                 mux_cell_int.first->setPort("\\B", s);
 126                         }
 127                 }
 128
 129                 for (auto &pat : find_muxtree_feedback_patterns(sig_a[index], q, path_else))
 130                         ret.insert(pat);
 131
 132                 if (sig_a[index] == q) {
 133                         RTLIL::SigSpec s = mux_cell_int.first->getPort("\\A");
 134                         s[index] = RTLIL::Sx;
 135                         mux_cell_int.first->setPort("\\A", s);
 136                 }
 137
 138                 return ret;
 139         }
 140
 141         void simplify_patterns(patterns_t&)
 142         {
 143                 // TBD
 144         }
 145
 146         RTLIL::SigSpec make_patterns_logic(patterns_t patterns, bool make_gates)
 147         {
 148                 RTLIL::SigSpec or_input;
 149
 150                 for (auto pat : patterns)
 151                 {
 152                         RTLIL::SigSpec s1, s2;
 153                         for (auto it : pat) {
 154                                 s1.append(it.first);
 155                                 s2.append(it.second);
 156                         }
 157
 158                         RTLIL::SigSpec y = module->addWire(NEW_ID);
 159                         RTLIL::Cell *c = module->addNe(NEW_ID, s1, s2, y);
 160
 161                         if (make_gates) {
 162                                 simplemap(module, c);
 163                                 module->remove(c);
 164                         }
 165
 166                         or_input.append(y);
 167                 }
 168
 169                 if (GetSize(or_input) == 0)
 170                         return RTLIL::S1;
 171
 172                 if (GetSize(or_input) == 1)
 173                         return or_input;
 174
 175                 RTLIL::SigSpec y = module->addWire(NEW_ID);
 176                 RTLIL::Cell *c = module->addReduceAnd(NEW_ID, or_input, y);
 177
 178                 if (make_gates) {
 179                         simplemap(module, c);
 180                         module->remove(c);
 181                 }
 182
 183                 return y;
 184         }
 185
 186         void handle_dff_cell(RTLIL::Cell *dff_cell)
 187         {
 188                 RTLIL::SigSpec sig_d = sigmap(dff_cell->getPort("\\D"));
 189                 RTLIL::SigSpec sig_q = sigmap(dff_cell->getPort("\\Q"));
 190
 191                 std::map<patterns_t, std::set<int>> grouped_patterns;
 192                 std::set<int> remaining_indices;
 193
 194                 for (int i = 0 ; i < GetSize(sig_d); i++) {
 195                         patterns_t patterns = find_muxtree_feedback_patterns(sig_d[i], sig_q[i], pattern_t());
 196                         if (!patterns.empty()) {
 197                                 simplify_patterns(patterns);
 198                                 grouped_patterns[patterns].insert(i);
 199                         } else
 200                                 remaining_indices.insert(i);
 201                 }
 202
 203                 for (auto &it : grouped_patterns) {
 204                         RTLIL::SigSpec new_sig_d, new_sig_q;
 205                         for (int i : it.second) {
 206                                 new_sig_d.append(sig_d[i]);
 207                                 new_sig_q.append(sig_q[i]);
 208                         }
 209                         if (!direct_dict.empty()) {
 210                                 log("  converting %s cell %s to %s for %s -> %s.\n", log_id(dff_cell->type), log_id(dff_cell), log_id(direct_dict.at(dff_cell->type)), log_signal(new_sig_d), log_signal(new_sig_q));
 211                                 dff_cell->setPort("\\E", make_patterns_logic(it.first, true));
 212                                 dff_cell->type = direct_dict.at(dff_cell->type);
 213                         } else
 214                         if (dff_cell->type == "$dff") {
 215                                 RTLIL::Cell *new_cell = module->addDffe(NEW_ID, dff_cell->getPort("\\CLK"), make_patterns_logic(it.first, false),
 216                                                 new_sig_d, new_sig_q, dff_cell->getParam("\\CLK_POLARITY").as_bool(), true);
 217                                 log("  created $dffe cell %s for %s -> %s.\n", log_id(new_cell), log_signal(new_sig_d), log_signal(new_sig_q));
 218                         } else {
 219                                 RTLIL::Cell *new_cell = module->addDffeGate(NEW_ID, dff_cell->getPort("\\C"), make_patterns_logic(it.first, true),
 220                                                 new_sig_d, new_sig_q, dff_cell->type == "$_DFF_P_", true);
 221                                 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));
 222                         }
 223                 }
 224
 225                 if (!direct_dict.empty())
 226                         return;
 227
 228                 if (remaining_indices.empty()) {
 229                         log("  removing now obsolete cell %s.\n", log_id(dff_cell));
 230                         module->remove(dff_cell);
 231                 } else if (GetSize(remaining_indices) != GetSize(sig_d)) {
 232                         log("  removing %d now obsolete bits from cell %s.\n", GetSize(sig_d) - GetSize(remaining_indices), log_id(dff_cell));
 233                         RTLIL::SigSpec new_sig_d, new_sig_q;
 234                         for (int i : remaining_indices) {
 235                                 new_sig_d.append(sig_d[i]);
 236                                 new_sig_q.append(sig_q[i]);
 237                         }
 238                         dff_cell->setPort("\\D", new_sig_d);
 239                         dff_cell->setPort("\\Q", new_sig_q);
 240                         dff_cell->setParam("\\WIDTH", GetSize(remaining_indices));
 241                 }
 242         }
 243
 244         void run()
 245         {
 246                 log("Transforming $dff to $dffe cells in module %s:\n", log_id(module));
 247                 for (auto dff_cell : dff_cells)
 248                         handle_dff_cell(dff_cell);
 249         }
 250 };
 251
 252 struct Dff2dffePass : public Pass {
 253         Dff2dffePass() : Pass("dff2dffe", "transform $dff cells to $dffe cells") { }
 254         virtual void help()
 255         {
 256                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 257                 log("\n");
 258                 log("    dff2dffe [options] [selection]\n");
 259                 log("\n");
 260                 log("This pass transforms $dff cells driven by a tree of multiplexers with one or\n");
 261                 log("more feedback paths to $dffe cells. It also works on gate-level cells such as\n");
 262                 log("$_DFF_P_, $_DFF_N_ and $_MUX_.\n");
 263                 log("\n");
 264                 log("    -unmap\n");
 265                 log("        operate in the opposite direction: replace $dffe cells with combinations\n");
 266                 log("        of $dff and $mux cells. the options below are ignore in unmap mode.\n");
 267                 log("\n");
 268                 log("    -direct <internal_gate_type> <external_gate_type>\n");
 269                 log("        map directly to external gate type. <internal_gate_type> can\n");
 270                 log("        be any internal gate-level FF cell (except $_DFFE_??_). the\n");
 271                 log("        <external_gate_type> is the cell type name for a cell with an\n");
 272                 log("        identical interface to the <internal_gate_type>, except it\n");
 273                 log("        also has an high-active enable port 'E'.\n");
 274                 log("          Usually <external_gate_type> is an intemediate cell type\n");
 275                 log("        that is then translated to the final type using 'techmap'.\n");
 276                 log("\n");
 277                 log("    -direct-match <pattern>\n");
 278                 log("        like -direct for all DFF cell types matching the expression.\n");
 279                 log("        this will use $__DFFE_* as <external_gate_type> matching the\n");
 280                 log("        internal gate type $_DFF_*_, except for $_DFF_[NP]_, which is\n");
 281                 log("        converted to $_DFFE_[NP]_.\n");
 282                 log("\n");
 283         }
 284         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 285         {
 286                 log_header("Executing DFF2DFFE pass (transform $dff to $dffe where applicable).\n");
 287
 288                 bool unmap_mode = false;
 289                 dict<IdString, IdString> direct_dict;
 290
 291                 size_t argidx;
 292                 for (argidx = 1; argidx < args.size(); argidx++) {
 293                         if (args[argidx] == "-unmap") {
 294                                 unmap_mode = true;
 295                                 continue;
 296                         }
 297                         if (args[argidx] == "-direct" && argidx + 2 < args.size()) {
 298                                 string direct_from = RTLIL::escape_id(args[++argidx]);
 299                                 string direct_to = RTLIL::escape_id(args[++argidx]);
 300                                 direct_dict[direct_from] = direct_to;
 301                                 continue;
 302                         }
 303                         if (args[argidx] == "-direct-match" && argidx + 1 < args.size()) {
 304                                 const char *pattern = args[++argidx].c_str();
 305                                 if (patmatch(pattern, "$_DFF_P_"  ))  direct_dict["$_DFF_P_" ] = "$_DFFE_P_";
 306                                 if (patmatch(pattern, "$_DFF_N_"  ))  direct_dict["$_DFF_N_" ] = "$_DFFE_N_";
 307                                 if (patmatch(pattern, "$_DFF_NN0_")) direct_dict["$_DFF_NN0"] = "$__DFFE_NN0";
 308                                 if (patmatch(pattern, "$_DFF_NN1_")) direct_dict["$_DFF_NN1"] = "$__DFFE_NN1";
 309                                 if (patmatch(pattern, "$_DFF_NP0_")) direct_dict["$_DFF_NP0"] = "$__DFFE_NP0";
 310                                 if (patmatch(pattern, "$_DFF_NP1_")) direct_dict["$_DFF_NP1"] = "$__DFFE_NP1";
 311                                 if (patmatch(pattern, "$_DFF_PN0_")) direct_dict["$_DFF_PN0"] = "$__DFFE_PN0";
 312                                 if (patmatch(pattern, "$_DFF_PN1_")) direct_dict["$_DFF_PN1"] = "$__DFFE_PN1";
 313                                 if (patmatch(pattern, "$_DFF_PP0_")) direct_dict["$_DFF_PP0"] = "$__DFFE_PP0";
 314                                 if (patmatch(pattern, "$_DFF_PP1_")) direct_dict["$_DFF_PP1"] = "$__DFFE_PP1";
 315                                 continue;
 316                         }
 317                         break;
 318                 }
 319                 extra_args(args, argidx, design);
 320
 321                 for (auto mod : design->selected_modules())
 322                         if (!mod->has_processes_warn())
 323                         {
 324                                 if (unmap_mode) {
 325                                         for (auto cell : mod->selected_cells()) {
 326                                                 if (cell->type == "$dffe") {
 327                                                         RTLIL::SigSpec tmp = mod->addWire(NEW_ID, GetSize(cell->getPort("\\D")));
 328                                                         mod->addDff(NEW_ID, cell->getPort("\\CLK"), tmp, cell->getPort("\\Q"), cell->getParam("\\CLK_POLARITY").as_bool());
 329                                                         if (cell->getParam("\\EN_POLARITY").as_bool())
 330                                                                 mod->addMux(NEW_ID, cell->getPort("\\Q"), cell->getPort("\\D"), cell->getPort("\\EN"), tmp);
 331                                                         else
 332                                                                 mod->addMux(NEW_ID, cell->getPort("\\D"), cell->getPort("\\Q"), cell->getPort("\\EN"), tmp);
 333                                                         mod->remove(cell);
 334                                                         continue;
 335                                                 }
 336                                                 if (cell->type.substr(0, 7) == "$_DFFE_") {
 337                                                         bool clk_pol = cell->type.substr(7, 1) == "P";
 338                                                         bool en_pol = cell->type.substr(8, 1) == "P";
 339                                                         RTLIL::SigSpec tmp = mod->addWire(NEW_ID);
 340                                                         mod->addDff(NEW_ID, cell->getPort("\\C"), tmp, cell->getPort("\\Q"), clk_pol);
 341                                                         if (en_pol)
 342                                                                 mod->addMux(NEW_ID, cell->getPort("\\Q"), cell->getPort("\\D"), cell->getPort("\\E"), tmp);
 343                                                         else
 344                                                                 mod->addMux(NEW_ID, cell->getPort("\\D"), cell->getPort("\\Q"), cell->getPort("\\E"), tmp);
 345                                                         mod->remove(cell);
 346                                                         continue;
 347                                                 }
 348                                         }
 349                                         continue;
 350                                 }
 351
 352                                 Dff2dffeWorker worker(mod, direct_dict);
 353                                 worker.run();
 354                         }
 355         }
 356 } Dff2dffePass;
 357
 358 PRIVATE_NAMESPACE_END