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 FF to FF+Enable cells in module %s:\n", log_id(module));
 247                 for (auto dff_cell : dff_cells) {
 248                         // log("Handling candidate %s:\n", log_id(dff_cell));
 249                         handle_dff_cell(dff_cell);
 250                 }
 251         }
 252 };
 253
 254 struct Dff2dffePass : public Pass {
 255         Dff2dffePass() : Pass("dff2dffe", "transform $dff cells to $dffe cells") { }
 256         void help() YS_OVERRIDE
 257         {
 258                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 259                 log("\n");
 260                 log("    dff2dffe [options] [selection]\n");
 261                 log("\n");
 262                 log("This pass transforms $dff cells driven by a tree of multiplexers with one or\n");
 263                 log("more feedback paths to $dffe cells. It also works on gate-level cells such as\n");
 264                 log("$_DFF_P_, $_DFF_N_ and $_MUX_.\n");
 265                 log("\n");
 266                 log("    -unmap\n");
 267                 log("        operate in the opposite direction: replace $dffe cells with combinations\n");
 268                 log("        of $dff and $mux cells. the options below are ignore in unmap mode.\n");
 269                 log("\n");
 270                 log("    -unmap-mince N\n");
 271                 log("        Same as -unmap but only unmap $dffe where the clock enable port\n");
 272                 log("        signal is used by less $dffe than the specified number\n");
 273                 log("\n");
 274                 log("    -direct <internal_gate_type> <external_gate_type>\n");
 275                 log("        map directly to external gate type. <internal_gate_type> can\n");
 276                 log("        be any internal gate-level FF cell (except $_DFFE_??_). the\n");
 277                 log("        <external_gate_type> is the cell type name for a cell with an\n");
 278                 log("        identical interface to the <internal_gate_type>, except it\n");
 279                 log("        also has an high-active enable port 'E'.\n");
 280                 log("          Usually <external_gate_type> is an intermediate cell type\n");
 281                 log("        that is then translated to the final type using 'techmap'.\n");
 282                 log("\n");
 283                 log("    -direct-match <pattern>\n");
 284                 log("        like -direct for all DFF cell types matching the expression.\n");
 285                 log("        this will use $__DFFE_* as <external_gate_type> matching the\n");
 286                 log("        internal gate type $_DFF_*_, and $__DFFSE_* for those matching\n");
 287                 log("        $_DFFS_*_, except for $_DFF_[NP]_, which is converted to \n");
 288                 log("        $_DFFE_[NP]_.\n");
 289                 log("\n");
 290         }
 291         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 292         {
 293                 log_header(design, "Executing DFF2DFFE pass (transform $dff to $dffe where applicable).\n");
 294
 295                 bool unmap_mode = false;
 296                 int min_ce_use = -1;
 297                 dict<IdString, IdString> direct_dict;
 298
 299                 size_t argidx;
 300                 for (argidx = 1; argidx < args.size(); argidx++) {
 301                         if (args[argidx] == "-unmap") {
 302                                 unmap_mode = true;
 303                                 continue;
 304                         }
 305                         if (args[argidx] == "-unmap-mince" && argidx + 1 < args.size()) {
 306                                 unmap_mode = true;
 307                                 min_ce_use = std::stoi(args[++argidx]);
 308                                 continue;
 309                         }
 310                         if (args[argidx] == "-direct" && argidx + 2 < args.size()) {
 311                                 string direct_from = RTLIL::escape_id(args[++argidx]);
 312                                 string direct_to = RTLIL::escape_id(args[++argidx]);
 313                                 direct_dict[direct_from] = direct_to;
 314                                 continue;
 315                         }
 316                         if (args[argidx] == "-direct-match" && argidx + 1 < args.size()) {
 317                                 bool found_match = false;
 318                                 const char *pattern = args[++argidx].c_str();
 319                                 if (patmatch(pattern, "$_DFF_P_"  )) found_match = true, direct_dict["$_DFF_P_"  ] = "$_DFFE_PP_";
 320                                 if (patmatch(pattern, "$_DFF_N_"  )) found_match = true, direct_dict["$_DFF_N_"  ] = "$_DFFE_NP_";
 321                                 if (patmatch(pattern, "$_DFF_NN0_")) found_match = true, direct_dict["$_DFF_NN0_"] = "$__DFFE_NN0";
 322                                 if (patmatch(pattern, "$_DFF_NN1_")) found_match = true, direct_dict["$_DFF_NN1_"] = "$__DFFE_NN1";
 323                                 if (patmatch(pattern, "$_DFF_NP0_")) found_match = true, direct_dict["$_DFF_NP0_"] = "$__DFFE_NP0";
 324                                 if (patmatch(pattern, "$_DFF_NP1_")) found_match = true, direct_dict["$_DFF_NP1_"] = "$__DFFE_NP1";
 325                                 if (patmatch(pattern, "$_DFF_PN0_")) found_match = true, direct_dict["$_DFF_PN0_"] = "$__DFFE_PN0";
 326                                 if (patmatch(pattern, "$_DFF_PN1_")) found_match = true, direct_dict["$_DFF_PN1_"] = "$__DFFE_PN1";
 327                                 if (patmatch(pattern, "$_DFF_PP0_")) found_match = true, direct_dict["$_DFF_PP0_"] = "$__DFFE_PP0";
 328                                 if (patmatch(pattern, "$_DFF_PP1_")) found_match = true, direct_dict["$_DFF_PP1_"] = "$__DFFE_PP1";
 329
 330                                 if (patmatch(pattern, "$__DFFS_NN0_")) found_match = true, direct_dict["$__DFFS_NN0_"] = "$__DFFSE_NN0";
 331                                 if (patmatch(pattern, "$__DFFS_NN1_")) found_match = true, direct_dict["$__DFFS_NN1_"] = "$__DFFSE_NN1";
 332                                 if (patmatch(pattern, "$__DFFS_NP0_")) found_match = true, direct_dict["$__DFFS_NP0_"] = "$__DFFSE_NP0";
 333                                 if (patmatch(pattern, "$__DFFS_NP1_")) found_match = true, direct_dict["$__DFFS_NP1_"] = "$__DFFSE_NP1";
 334                                 if (patmatch(pattern, "$__DFFS_PN0_")) found_match = true, direct_dict["$__DFFS_PN0_"] = "$__DFFSE_PN0";
 335                                 if (patmatch(pattern, "$__DFFS_PN1_")) found_match = true, direct_dict["$__DFFS_PN1_"] = "$__DFFSE_PN1";
 336                                 if (patmatch(pattern, "$__DFFS_PP0_")) found_match = true, direct_dict["$__DFFS_PP0_"] = "$__DFFSE_PP0";
 337                                 if (patmatch(pattern, "$__DFFS_PP1_")) found_match = true, direct_dict["$__DFFS_PP1_"] = "$__DFFSE_PP1";
 338                                 if (!found_match)
 339                                         log_cmd_error("No cell types matched pattern '%s'.\n", pattern);
 340                                 continue;
 341                         }
 342                         break;
 343                 }
 344                 extra_args(args, argidx, design);
 345
 346                 if (!direct_dict.empty()) {
 347                         log("Selected cell types for direct conversion:\n");
 348                         for (auto &it : direct_dict)
 349                                 log("  %s -> %s\n", log_id(it.first), log_id(it.second));
 350                 }
 351
 352                 for (auto mod : design->selected_modules())
 353                         if (!mod->has_processes_warn())
 354                         {
 355                                 if (unmap_mode) {
 356                                         SigMap sigmap(mod);
 357                                         for (auto cell : mod->selected_cells()) {
 358                                                 if (cell->type == "$dffe") {
 359                                                         if (min_ce_use >= 0) {
 360                                                                 int ce_use = 0;
 361                                                                 for (auto cell_other : mod->selected_cells()) {
 362                                                                         if (cell_other->type != cell->type)
 363                                                                                 continue;
 364                                                                         if (sigmap(cell->getPort("\\EN")) == sigmap(cell_other->getPort("\\EN")))
 365                                                                                 ce_use++;
 366                                                                 }
 367                                                                 if (ce_use >= min_ce_use)
 368                                                                         continue;
 369                                                         }
 370
 371                                                         RTLIL::SigSpec tmp = mod->addWire(NEW_ID, GetSize(cell->getPort("\\D")));
 372                                                         mod->addDff(NEW_ID, cell->getPort("\\CLK"), tmp, cell->getPort("\\Q"), cell->getParam("\\CLK_POLARITY").as_bool());
 373                                                         if (cell->getParam("\\EN_POLARITY").as_bool())
 374                                                                 mod->addMux(NEW_ID, cell->getPort("\\Q"), cell->getPort("\\D"), cell->getPort("\\EN"), tmp);
 375                                                         else
 376                                                                 mod->addMux(NEW_ID, cell->getPort("\\D"), cell->getPort("\\Q"), cell->getPort("\\EN"), tmp);
 377                                                         mod->remove(cell);
 378                                                         continue;
 379                                                 }
 380                                                 if (cell->type.substr(0, 7) == "$_DFFE_") {
 381                                                         if (min_ce_use >= 0) {
 382                                                                 int ce_use = 0;
 383                                                                 for (auto cell_other : mod->selected_cells()) {
 384                                                                         if (cell_other->type != cell->type)
 385                                                                                 continue;
 386                                                                         if (sigmap(cell->getPort("\\E")) == sigmap(cell_other->getPort("\\E")))
 387                                                                                 ce_use++;
 388                                                                 }
 389                                                                 if (ce_use >= min_ce_use)
 390                                                                         continue;
 391                                                         }
 392
 393                                                         bool clk_pol = cell->type.substr(7, 1) == "P";
 394                                                         bool en_pol = cell->type.substr(8, 1) == "P";
 395                                                         RTLIL::SigSpec tmp = mod->addWire(NEW_ID);
 396                                                         mod->addDff(NEW_ID, cell->getPort("\\C"), tmp, cell->getPort("\\Q"), clk_pol);
 397                                                         if (en_pol)
 398                                                                 mod->addMux(NEW_ID, cell->getPort("\\Q"), cell->getPort("\\D"), cell->getPort("\\E"), tmp);
 399                                                         else
 400                                                                 mod->addMux(NEW_ID, cell->getPort("\\D"), cell->getPort("\\Q"), cell->getPort("\\E"), tmp);
 401                                                         mod->remove(cell);
 402                                                         continue;
 403                                                 }
 404                                         }
 405                                         continue;
 406                                 }
 407
 408                                 Dff2dffeWorker worker(mod, direct_dict);
 409                                 worker.run();
 410                         }
 411         }
 412 } Dff2dffePass;
 413
 414 PRIVATE_NAMESPACE_END