diff options
Diffstat (limited to 'passes/opt/opt_demorgan.cc')
| -rw-r--r-- | passes/opt/opt_demorgan.cc | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/passes/opt/opt_demorgan.cc b/passes/opt/opt_demorgan.cc new file mode 100644 index 00000000..1699a645 --- /dev/null +++ b/passes/opt/opt_demorgan.cc @@ -0,0 +1,202 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2017 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/yosys.h" +#include "kernel/sigtools.h" +#include "kernel/modtools.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +void demorgan_worker( + ModIndex& index, + Cell *cell, + unsigned int& cells_changed) +{ + SigMap& sigmap = index.sigmap; + auto m = cell->module; + + //TODO: Add support for reduce_xor + //DeMorgan of XOR is either XOR (if even number of inputs) or XNOR (if odd number) + + if( (cell->type != "$reduce_and") && (cell->type != "$reduce_or") ) + return; + + auto insig = sigmap(cell->getPort("\\A")); + log("Inspecting %s cell %s (%d inputs)\n", log_id(cell->type), log_id(cell->name), GetSize(insig)); + int num_inverted = 0; + for(int i=0; i<GetSize(insig); i++) + { + auto b = insig[i]; + + //See if this bit is driven by a $not cell + //TODO: do other stuff like nor/nand? + pool<ModIndex::PortInfo> ports = index.query_ports(b); + bool inverted = false; + for(auto x : ports) + { + if(x.port == "\\Y" && x.cell->type == "$_NOT_") + { + inverted = true; + break; + } + } + + if(inverted) + num_inverted ++; + } + + //Stop if less than half of the inputs are inverted + if(num_inverted*2 < GetSize(insig)) + { + log(" %d / %d inputs are inverted, not pushing\n", num_inverted, GetSize(insig)); + return; + } + + //More than half of the inputs are inverted! Push through + cells_changed ++; + log(" %d / %d inputs are inverted, pushing inverter through reduction\n", num_inverted, GetSize(insig)); + + //For each input, either add or remove the inverter as needed + //TODO: this duplicates the loop up above, can we refactor it? + for(int i=0; i<GetSize(insig); i++) + { + auto b = insig[i]; + + //See if this bit is driven by a $not cell + //TODO: do other stuff like nor/nand? + pool<ModIndex::PortInfo> ports = index.query_ports(b); + RTLIL::Cell* srcinv = NULL; + for(auto x : ports) + { + if(x.port == "\\Y" && x.cell->type == "$_NOT_") + { + srcinv = x.cell; + break; + } + } + + //We are NOT inverted! Add an inverter + if(!srcinv) + { + auto inverted_b = m->addWire(NEW_ID); + m->addNot(NEW_ID, RTLIL::SigSpec(b), RTLIL::SigSpec(inverted_b)); + insig[i] = inverted_b; + } + + //We ARE inverted - bypass it + //Don't automatically delete the inverter since other stuff might still use it + else + insig[i] = srcinv->getPort("\\A"); + } + + //Cosmetic fixup: If our input is just a scrambled version of one bus, rearrange it + //Reductions are all commutative, so there's no point in having them in a weird order + bool same_signal = true; + RTLIL::Wire* srcwire = insig[0].wire; + dict<int, int> seen_bits; + for(int i=0; i<GetSize(insig); i++) + seen_bits[i] = 0; + for(int i=0; i<GetSize(insig); i++) + { + seen_bits[insig[i].offset] ++; + if(insig[i].wire != srcwire) + { + same_signal = false; + break; + } + } + if(same_signal) + { + //Make sure we've seen every bit exactly once + bool every_bit_once = true; + for(int i=0; i<GetSize(insig); i++) + { + if(seen_bits[i] != 1) + { + every_bit_once = false; + break; + } + } + + //All good? Just use the whole wire as-is without any reordering + //We do have to swap MSB to LSB b/c that's the way the reduction cells seem to work? + //Unclear on why this isn't sorting properly + //TODO: can we do SigChunks instead of single bits if we have subsets of a bus? + if(every_bit_once && (GetSize(insig) == srcwire->width) ) + { + log("Rearranging bits\n"); + RTLIL::SigSpec newsig; + for(int i=0; i<GetSize(insig); i++) + newsig.append(RTLIL::SigBit(srcwire, GetSize(insig) - i - 1)); + insig = newsig; + insig.sort(); + } + } + + //Push the new input signal back to the reduction (after bypassing/adding inverters) + cell->setPort("\\A", insig); + + //Change the cell type + if(cell->type == "$reduce_and") + cell->type = "$reduce_or"; + else if(cell->type == "$reduce_or") + cell->type = "$reduce_and"; + //don't change XOR + + //Add an inverter to the output + auto inverted_output = cell->getPort("\\Y"); + auto uninverted_output = m->addWire(NEW_ID); + m->addNot(NEW_ID, RTLIL::SigSpec(uninverted_output), inverted_output); + cell->setPort("\\Y", uninverted_output); +} + +struct OptDemorganPass : public Pass { + OptDemorganPass() : Pass("opt_demorgan", "Optimize reductions with DeMorgan equivalents") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" opt_demorgan [selection]\n"); + log("\n"); + log("This pass pushes inverters through $reduce_* cells if this will reduce the\n"); + log("overall gate count of the circuit\n"); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing OPT_DEMORGAN pass (push inverters through $reduce_* cells).\n"); + + int argidx = 0; + extra_args(args, argidx, design); + + unsigned int cells_changed = 0; + for (auto module : design->selected_modules()) + { + ModIndex index(module); + for (auto cell : module->selected_cells()) + demorgan_worker(index, cell, cells_changed); + } + + if(cells_changed) + log("Pushed inverters through %u reductions\n", cells_changed); + } +} OptDemorganPass; + +PRIVATE_NAMESPACE_END |