passes/opt/opt_demorgan.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2017  Claire Xenia Wolf <claire@yosyshq.com>
   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
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 void demorgan_worker(
  28         ModIndex& index,
  29         Cell *cell,
  30         unsigned int& cells_changed)
  31 {
  32         SigMap& sigmap = index.sigmap;
  33         auto m = cell->module;
  34
  35         //TODO: Add support for reduce_xor
  36         //DeMorgan of XOR is either XOR (if even number of inputs) or XNOR (if odd number)
  37
  38         if( (cell->type != ID($reduce_and)) && (cell->type != ID($reduce_or)) )
  39                 return;
  40
  41         auto insig = sigmap(cell->getPort(ID::A));
  42         log("Inspecting %s cell %s (%d inputs)\n", log_id(cell->type), log_id(cell->name), GetSize(insig));
  43         int num_inverted = 0;
  44         for(int i=0; i<GetSize(insig); i++)
  45         {
  46                 auto b = insig[i];
  47
  48                 //See if this bit is driven by a $not cell
  49                 //TODO: do other stuff like nor/nand?
  50                 pool<ModIndex::PortInfo> ports = index.query_ports(b);
  51                 bool inverted = false;
  52                 for(auto x : ports)
  53                 {
  54                         if(x.port == ID::Y && x.cell->type == ID($_NOT_))
  55                         {
  56                                 inverted = true;
  57                                 break;
  58                         }
  59                 }
  60
  61                 if(inverted)
  62                         num_inverted ++;
  63         }
  64
  65         //Stop if less than half of the inputs are inverted
  66         if(num_inverted*2 < GetSize(insig))
  67         {
  68                 log("  %d / %d inputs are inverted, not pushing\n", num_inverted, GetSize(insig));
  69                 return;
  70         }
  71
  72         //More than half of the inputs are inverted! Push through
  73         cells_changed ++;
  74         log("  %d / %d inputs are inverted, pushing inverter through reduction\n", num_inverted, GetSize(insig));
  75
  76         //For each input, either add or remove the inverter as needed
  77         //TODO: this duplicates the loop up above, can we refactor it?
  78         for(int i=0; i<GetSize(insig); i++)
  79         {
  80                 auto b = insig[i];
  81
  82                 //See if this bit is driven by a $not cell
  83                 //TODO: do other stuff like nor/nand?
  84                 pool<ModIndex::PortInfo> ports = index.query_ports(b);
  85                 RTLIL::Cell* srcinv = NULL;
  86                 for(auto x : ports)
  87                 {
  88                         if(x.port == ID::Y && x.cell->type == ID($_NOT_))
  89                         {
  90                                 srcinv = x.cell;
  91                                 break;
  92                         }
  93                 }
  94
  95                 //We are NOT inverted! Add an inverter
  96                 if(!srcinv)
  97                 {
  98                         auto inverted_b = m->addWire(NEW_ID);
  99                         m->addNot(NEW_ID, RTLIL::SigSpec(b), RTLIL::SigSpec(inverted_b));
 100                         insig[i] = inverted_b;
 101                 }
 102
 103                 //We ARE inverted - bypass it
 104                 //Don't automatically delete the inverter since other stuff might still use it
 105                 else
 106                         insig[i] = srcinv->getPort(ID::A);
 107         }
 108
 109         //Cosmetic fixup: If our input is just a scrambled version of one bus, rearrange it
 110         //Reductions are all commutative, so there's no point in having them in a weird order
 111         bool same_signal = true;
 112         RTLIL::Wire* srcwire = insig[0].wire;
 113         dict<int, int> seen_bits;
 114         for(int i=0; i<GetSize(insig); i++)
 115                 seen_bits[i] = 0;
 116         for(int i=0; i<GetSize(insig); i++)
 117         {
 118                 seen_bits[insig[i].offset] ++;
 119                 if(insig[i].wire != srcwire)
 120                 {
 121                         same_signal = false;
 122                         break;
 123                 }
 124         }
 125         if(same_signal)
 126         {
 127                 //Make sure we've seen every bit exactly once
 128                 bool every_bit_once = true;
 129                 for(int i=0; i<GetSize(insig); i++)
 130                 {
 131                         if(seen_bits[i] != 1)
 132                         {
 133                                 every_bit_once = false;
 134                                 break;
 135                         }
 136                 }
 137
 138                 //All good? Just use the whole wire as-is without any reordering
 139                 //We do have to swap MSB to LSB b/c that's the way the reduction cells seem to work?
 140                 //Unclear on why this isn't sorting properly
 141                 //TODO: can we do SigChunks instead of single bits if we have subsets of a bus?
 142                 if(every_bit_once && (GetSize(insig) == srcwire->width) )
 143                 {
 144                         log("Rearranging bits\n");
 145                         RTLIL::SigSpec newsig;
 146                         for(int i=0; i<GetSize(insig); i++)
 147                                 newsig.append(RTLIL::SigBit(srcwire, GetSize(insig) - i - 1));
 148                         insig = newsig;
 149                         insig.sort();
 150                 }
 151         }
 152
 153         //Push the new input signal back to the reduction (after bypassing/adding inverters)
 154         cell->setPort(ID::A, insig);
 155
 156         //Change the cell type
 157         if(cell->type == ID($reduce_and))
 158                 cell->type = ID($reduce_or);
 159         else if(cell->type == ID($reduce_or))
 160                 cell->type = ID($reduce_and);
 161         //don't change XOR
 162
 163         //Add an inverter to the output
 164         auto inverted_output = cell->getPort(ID::Y);
 165         auto uninverted_output = m->addWire(NEW_ID);
 166         m->addNot(NEW_ID, RTLIL::SigSpec(uninverted_output), inverted_output);
 167         cell->setPort(ID::Y, uninverted_output);
 168 }
 169
 170 struct OptDemorganPass : public Pass {
 171         OptDemorganPass() : Pass("opt_demorgan", "Optimize reductions with DeMorgan equivalents") { }
 172         void help() override
 173         {
 174                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 175                 log("\n");
 176                 log("    opt_demorgan [selection]\n");
 177                 log("\n");
 178                 log("This pass pushes inverters through $reduce_* cells if this will reduce the\n");
 179                 log("overall gate count of the circuit\n");
 180                 log("\n");
 181         }
 182         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 183         {
 184                 log_header(design, "Executing OPT_DEMORGAN pass (push inverters through $reduce_* cells).\n");
 185
 186                 int argidx = 0;
 187                 extra_args(args, argidx, design);
 188
 189                 unsigned int cells_changed = 0;
 190                 for (auto module : design->selected_modules())
 191                 {
 192                         ModIndex index(module);
 193                         for (auto cell : module->selected_cells())
 194                                 demorgan_worker(index, cell, cells_changed);
 195                 }
 196
 197                 if(cells_changed)
 198                         log("Pushed inverters through %u reductions\n", cells_changed);
 199         }
 200 } OptDemorganPass;
 201
 202 PRIVATE_NAMESPACE_END