passes/opt/opt_ffinv.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2022  Marcelina Kościelnicka <mwk@0x04.net>
   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/modtools.h"
  23 #include "kernel/ffinit.h"
  24 #include "kernel/ff.h"
  25
  26 USING_YOSYS_NAMESPACE
  27 PRIVATE_NAMESPACE_BEGIN
  28
  29 struct OptFfInvWorker
  30 {
  31         int count = 0;
  32         RTLIL::Module *module;
  33         ModWalker walker;
  34         FfInitVals initvals;
  35
  36         // Case 1:
  37         // - FF is driven by inverter
  38         // - ... which has no other users
  39         // - all users of FF are LUTs
  40         bool push_d_inv(FfData &ff) {
  41                 pool<SigBit> dummy;
  42
  43                 if (walker.get_inputs(dummy, ff.sig_d))
  44                         return false;
  45                 if (walker.get_outputs(dummy, ff.sig_d))
  46                         return false;
  47                 pool<ModWalker::PortBit> d_drivers;
  48                 walker.get_drivers(d_drivers, ff.sig_d);
  49                 if (d_drivers.size() != 1)
  50                         return false;
  51                 Cell *d_inv = nullptr;
  52                 for (auto &driver: d_drivers) {
  53                         if (driver.cell->type.in(ID($not), ID($_NOT_))) {
  54                                 // OK
  55                         } else if (driver.cell->type.in(ID($lut))) {
  56                                 if (driver.cell->getParam(ID::WIDTH) != 1)
  57                                         return false;
  58                                 if (driver.cell->getParam(ID::LUT).as_int() != 1)
  59                                         return false;
  60                         } else {
  61                                 return false;
  62                         }
  63                         d_inv = driver.cell;
  64                 }
  65                 pool<ModWalker::PortBit> d_consumers;
  66                 walker.get_consumers(d_consumers, ff.sig_d);
  67                 if (d_consumers.size() != 1)
  68                         return false;
  69
  70                 if (walker.get_outputs(dummy, ff.sig_q))
  71                         return false;
  72                 pool<Cell *> q_luts;
  73                 pool<ModWalker::PortBit> q_consumers;
  74                 walker.get_consumers(q_consumers, ff.sig_q);
  75                 for (auto &consumer: q_consumers) {
  76                         if (!consumer.cell->type.in(ID($not), ID($_NOT_), ID($lut)))
  77                                 return false;
  78                         q_luts.insert(consumer.cell);
  79                 }
  80
  81                 ff.flip_rst_bits({0});
  82                 ff.sig_d = d_inv->getPort(ID::A);
  83
  84                 for (Cell *lut: q_luts) {
  85                         if (lut->type == ID($lut)) {
  86                                 int flip_mask = 0;
  87                                 SigSpec sig_a = lut->getPort(ID::A);
  88                                 for (int i = 0; i < GetSize(sig_a); i++) {
  89                                         if (walker.sigmap(sig_a[i]) == walker.sigmap(ff.sig_q)) {
  90                                                 flip_mask |= 1 << i;
  91                                         }
  92                                 }
  93                                 Const mask = lut->getParam(ID::LUT);
  94                                 Const new_mask;
  95                                 for (int j = 0; j < (1 << GetSize(sig_a)); j++) {
  96                                         new_mask.bits.push_back(mask.bits[j ^ flip_mask]);
  97                                 }
  98                                 if (GetSize(sig_a) == 1 && new_mask.as_int() == 2) {
  99                                         module->connect(lut->getPort(ID::Y), ff.sig_q);
 100                                         module->remove(lut);
 101                                 } else {
 102                                         lut->setParam(ID::LUT, new_mask);
 103                                 }
 104                         } else {
 105                                 // it was an inverter
 106                                 module->connect(lut->getPort(ID::Y), ff.sig_q);
 107                                 module->remove(lut);
 108                         }
 109                 }
 110
 111                 ff.emit();
 112                 return true;
 113         }
 114
 115         // Case 2:
 116         // - FF is driven by LUT
 117         // - ... which has no other users
 118         // - FF has one user
 119         // - ... which is an inverter
 120         bool push_q_inv(FfData &ff) {
 121                 pool<SigBit> dummy;
 122
 123                 if (walker.get_inputs(dummy, ff.sig_d))
 124                         return false;
 125                 if (walker.get_outputs(dummy, ff.sig_d))
 126                         return false;
 127
 128                 Cell *d_lut = nullptr;
 129                 pool<ModWalker::PortBit> d_drivers;
 130                 walker.get_drivers(d_drivers, ff.sig_d);
 131                 if (d_drivers.size() != 1)
 132                         return false;
 133                 for (auto &driver: d_drivers) {
 134                         if (!driver.cell->type.in(ID($not), ID($_NOT_), ID($lut)))
 135                                 return false;
 136                         d_lut = driver.cell;
 137                 }
 138                 pool<ModWalker::PortBit> d_consumers;
 139                 walker.get_consumers(d_consumers, ff.sig_d);
 140                 if (d_consumers.size() != 1)
 141                         return false;
 142
 143                 if (walker.get_outputs(dummy, ff.sig_q))
 144                         return false;
 145                 pool<ModWalker::PortBit> q_consumers;
 146                 walker.get_consumers(q_consumers, ff.sig_q);
 147                 if (q_consumers.size() != 1)
 148                         return false;
 149                 Cell *q_inv = nullptr;
 150                 for (auto &consumer: q_consumers) {
 151                         if (consumer.cell->type.in(ID($not), ID($_NOT_))) {
 152                                 // OK
 153                         } else if (consumer.cell->type.in(ID($lut))) {
 154                                 if (consumer.cell->getParam(ID::WIDTH) != 1)
 155                                         return false;
 156                                 if (consumer.cell->getParam(ID::LUT).as_int() != 1)
 157                                         return false;
 158                         } else {
 159                                 return false;
 160                         }
 161                         q_inv = consumer.cell;
 162                 }
 163
 164                 ff.flip_rst_bits({0});
 165                 ff.sig_q = q_inv->getPort(ID::Y);
 166                 module->remove(q_inv);
 167
 168                 if (d_lut->type == ID($lut)) {
 169                         Const mask = d_lut->getParam(ID::LUT);
 170                         Const new_mask;
 171                         for (int i = 0; i < GetSize(mask); i++) {
 172                                 if (mask.bits[i] == State::S0)
 173                                         new_mask.bits.push_back(State::S1);
 174                                 else
 175                                         new_mask.bits.push_back(State::S0);
 176                         }
 177                         d_lut->setParam(ID::LUT, new_mask);
 178                         if (d_lut->getParam(ID::WIDTH) == 1 && new_mask.as_int() == 2) {
 179                                 module->connect(ff.sig_d, d_lut->getPort(ID::A));
 180                                 module->remove(d_lut);
 181                         }
 182                 } else {
 183                         // it was an inverter
 184                         module->connect(ff.sig_d, d_lut->getPort(ID::A));
 185                         module->remove(d_lut);
 186                 }
 187
 188                 ff.emit();
 189                 return true;
 190         }
 191
 192         OptFfInvWorker(RTLIL::Module *module) :
 193                 module(module), walker(module->design, module), initvals(&walker.sigmap, module)
 194         {
 195                 log("Discovering LUTs.\n");
 196
 197                 for (Cell *cell : module->selected_cells()) {
 198                         if (!RTLIL::builtin_ff_cell_types().count(cell->type))
 199                                 continue;
 200
 201                         FfData ff(&initvals, cell);
 202                         if (ff.has_sr)
 203                                 continue;
 204                         if (!ff.has_clk)
 205                                 continue;
 206                         if (ff.has_aload)
 207                                 continue;
 208                         if (ff.width != 1)
 209                                 continue;
 210
 211                         if (push_d_inv(ff)) {
 212                                 count++;
 213                         } else if (push_q_inv(ff)) {
 214                                 count++;
 215                         }
 216                 }
 217         }
 218 };
 219
 220 struct OptFfInvPass : public Pass {
 221         OptFfInvPass() : Pass("opt_ffinv", "push inverters through FFs") { }
 222         void help() override
 223         {
 224                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 225                 log("\n");
 226                 log("    opt_ffinv [selection]\n");
 227                 log("\n");
 228                 log("This pass pushes inverters to the other side of a FF when they can be merged\n");
 229                 log("into LUTs on the other side.\n");
 230                 log("\n");
 231         }
 232         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 233         {
 234                 log_header(design, "Executing OPT_FFINV pass (push inverters through FFs).\n");
 235
 236                 size_t argidx;
 237                 for (argidx = 1; argidx < args.size(); argidx++)
 238                 {
 239                         break;
 240                 }
 241                 extra_args(args, argidx, design);
 242
 243                 int total_count = 0;
 244                 for (auto module : design->selected_modules())
 245                 {
 246                         OptFfInvWorker worker(module);
 247                         total_count += worker.count;
 248                 }
 249                 if (total_count)
 250                         design->scratchpad_set_bool("opt.did_something", true);
 251                 log("Pushed %d inverters.\n", total_count);
 252         }
 253 } OptFfInvPass;
 254
 255 PRIVATE_NAMESPACE_END