From 51cbec7f75d0f78e9a1fcc6b5d10d564c3035c13 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Tue, 22 Aug 2017 13:48:55 +0200 Subject: Add experimental adders pass --- passes/techmap/Makefile.inc | 1 + passes/techmap/adders.cc | 446 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 447 insertions(+) create mode 100644 passes/techmap/adders.cc (limited to 'passes') diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc index 311a1af95..418cc6c2b 100644 --- a/passes/techmap/Makefile.inc +++ b/passes/techmap/Makefile.inc @@ -32,6 +32,7 @@ OBJS += passes/techmap/insbuf.o OBJS += passes/techmap/attrmvcp.o OBJS += passes/techmap/attrmap.o OBJS += passes/techmap/zinit.o +OBJS += passes/techmap/adders.o endif GENFILES += passes/techmap/techmap.inc diff --git a/passes/techmap/adders.cc b/passes/techmap/adders.cc new file mode 100644 index 000000000..7482d2c9b --- /dev/null +++ b/passes/techmap/adders.cc @@ -0,0 +1,446 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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/consteval.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct AddersConfig +{ + bool enable_fa = false; + bool enable_ha = false; + bool enable_fs = false; + bool enable_hs = false; +}; + +struct AddersWorker +{ + const AddersConfig &config; + Module *module; + ConstEval ce; + SigMap &sigmap; + + dict driver; + pool handled_bits; + + dict, pool> part_xor; + dict, pool> part_and; + dict, pool> part_andnot; + + dict, pool> part_xor3; + dict, pool> part_maj; + dict, pool> part_majnot; + + AddersWorker(const AddersConfig &config, Module *module) : + config(config), module(module), ce(module), sigmap(ce.assign_map) + { + for (auto cell : module->selected_cells()) + { + if (cell->type.in( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_", + "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_", + "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_")) + { + SigBit y = sigmap(SigBit(cell->getPort("\\Y"))); + log_assert(driver.count(y) == 0); + driver[y] = cell; + } + } + } + + void check_partition(SigBit root, pool &leaves) + { + if (GetSize(leaves) == 2) + { + leaves.sort(); + + SigBit A = SigSpec(leaves)[0]; + SigBit B = SigSpec(leaves)[1]; + + bool is_xor = true; + bool is_and = true; + bool is_andnot_a = true; + bool is_andnot_b = true; + + for (int i = 0; i < 4; i++) + { + bool a_value = (i & 1) != 0; + bool b_value = (i & 2) != 0; + bool xor_value = a_value != b_value; + bool and_value = a_value && b_value; + bool andnot_a_value = !a_value && b_value; + bool andnot_b_value = a_value && !b_value; + + ce.push(); + ce.set(A, a_value ? State::S1 : State::S0); + ce.set(B, b_value ? State::S1 : State::S0); + + SigSpec sig = root; + + if (!ce.eval(sig)) + log_abort(); + + if (sig != xor_value) + is_xor = false; + + if (sig != and_value) + is_and = false; + + if (sig != andnot_a_value) + is_andnot_a = false; + + if (sig != andnot_b_value) + is_andnot_b = false; + + ce.pop(); + } + + if (is_xor) + part_xor[tuple(A, B)].insert(root); + + if (is_and) + part_and[tuple(A, B)].insert(root); + + if (is_andnot_a) + part_andnot[tuple(B, A)].insert(root); + + if (is_andnot_b) + part_andnot[tuple(A, B)].insert(root); + } + + if (GetSize(leaves) == 3) + { + leaves.sort(); + + SigBit A = SigSpec(leaves)[0]; + SigBit B = SigSpec(leaves)[1]; + SigBit C = SigSpec(leaves)[2]; + + bool is_xor3 = true; + bool is_maj = true; + bool is_maj_nota = true; + bool is_maj_notb = true; + bool is_maj_notc = true; + + for (int i = 0; i < 8; i++) + { + bool a_value = (i & 1) != 0; + bool b_value = (i & 2) != 0; + bool c_value = (i & 4) != 0; + + bool xor3_value = (a_value != b_value) != c_value; + bool maj_value = (a_value && b_value) || (a_value && c_value) || (b_value && c_value); + bool maj_nota_value = (!a_value && b_value) || (!a_value && c_value) || (b_value && c_value); + bool maj_notb_value = (a_value && !b_value) || (a_value && c_value) || (!b_value && c_value); + bool maj_notc_value = (a_value && b_value) || (a_value && !c_value) || (b_value && !c_value); + + ce.push(); + ce.set(A, a_value ? State::S1 : State::S0); + ce.set(B, b_value ? State::S1 : State::S0); + ce.set(C, c_value ? State::S1 : State::S0); + + SigSpec sig = root; + + if (!ce.eval(sig)) + log_abort(); + + if (sig != xor3_value) + is_xor3 = false; + + if (sig != maj_value) + is_maj = false; + + if (sig != maj_nota_value) + is_maj_nota = false; + + if (sig != maj_notb_value) + is_maj_notb = false; + + if (sig != maj_notc_value) + is_maj_notc = false; + + ce.pop(); + } + + if (is_xor3) + part_xor3[tuple(A, B, C)].insert(root); + + if (is_maj) + part_maj[tuple(A, B, C)].insert(root); + + if (is_maj_nota) + part_majnot[tuple(B, C, A)].insert(root); + + if (is_maj_notb) + part_majnot[tuple(A, C, B)].insert(root); + + if (is_maj_notc) + part_majnot[tuple(A, B, C)].insert(root); + } + } + + void find_partitions(SigBit root, pool &leaves, pool> &cache, int maxdepth, int maxbreadth) + { + if (cache.count(leaves)) + return; + + cache.insert(leaves); + check_partition(root, leaves); + + if (maxdepth == 0) + return; + + for (SigBit bit : leaves) + { + if (driver.count(bit) == 0) + continue; + + Cell *cell = driver.at(bit); + pool new_leaves = leaves; + + new_leaves.erase(bit); + if (cell->hasPort("\\A")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\A")))); + if (cell->hasPort("\\B")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\B")))); + if (cell->hasPort("\\C")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\C")))); + if (cell->hasPort("\\D")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\D")))); + + if (GetSize(new_leaves) > maxbreadth) + continue; + + find_partitions(root, new_leaves, cache, maxdepth-1, maxbreadth); + } + } + + void make_fa(SigBit A, SigBit B, SigBit C, const pool &sum_out, const pool &carry_out) + { + if (!config.enable_fa) + return; + + Wire *so = module->addWire(NEW_ID); + Wire *co = module->addWire(NEW_ID); + + Cell *cell = module->addCell(NEW_ID, "$__fa"); + cell->setPort("\\A", A); + cell->setPort("\\B", B); + cell->setPort("\\C", C); + cell->setPort("\\SO", so); + cell->setPort("\\CO", co); + + log("New full adder %s in module %s: A=%s B=%s C=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B), log_signal(C)); + + for (auto bit : sum_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, so); + handled_bits.insert(bit); + log(" sum out: %s\n", log_signal(bit)); + } + + for (auto bit : carry_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, co); + handled_bits.insert(bit); + log(" carry out: %s\n", log_signal(bit)); + } + } + + void make_ha(SigBit A, SigBit B, const pool &sum_out, const pool &carry_out) + { + if (!config.enable_ha) + return; + + Wire *so = module->addWire(NEW_ID); + Wire *co = module->addWire(NEW_ID); + + Cell *cell = module->addCell(NEW_ID, "$__ha"); + cell->setPort("\\A", A); + cell->setPort("\\B", B); + cell->setPort("\\SO", so); + cell->setPort("\\CO", co); + + log("New half adder %s in module %s: A=%s B=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B)); + + for (auto bit : sum_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, so); + handled_bits.insert(bit); + log(" sum out: %s\n", log_signal(bit)); + } + + for (auto bit : carry_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, co); + handled_bits.insert(bit); + log(" carry out: %s\n", log_signal(bit)); + } + } + + void make_hs(SigBit A, SigBit B, const pool &sum_out, const pool &carry_out) + { + if (!config.enable_hs) + return; + + Wire *so = module->addWire(NEW_ID); + Wire *co = module->addWire(NEW_ID); + + Cell *cell = module->addCell(NEW_ID, "$__hs"); + cell->setPort("\\A", A); + cell->setPort("\\B", B); + cell->setPort("\\SO", so); + cell->setPort("\\CO", co); + + log("New half subtractor %s in module %s: A=%s B=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B)); + + for (auto bit : sum_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, so); + handled_bits.insert(bit); + log(" sum out: %s\n", log_signal(bit)); + } + + for (auto bit : carry_out) { + if (handled_bits.count(bit)) + continue; + Cell *drv = driver.at(bit); + drv->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, co); + handled_bits.insert(bit); + log(" carry out: %s\n", log_signal(bit)); + } + } + + void run() + { + for (auto it : driver) + { + SigBit root = it.first; + pool leaves = { root }; + pool> cache; + + find_partitions(root, leaves, cache, 5, 10); + } + + for (auto &it : part_xor3) + { + SigBit A = get<0>(it.first); + SigBit B = get<1>(it.first); + SigBit C = get<2>(it.first); + + // FIXME: Add support for full subtractors + + if (part_maj.count(tuple(A, B, C))) + make_fa(A, B, C, it.second, part_maj.at(tuple(A, B, C))); + } + + for (auto &it : part_xor) + { + SigBit A = get<0>(it.first); + SigBit B = get<1>(it.first); + + if (part_andnot.count(tuple(A, B))) + make_hs(A, B, it.second, part_andnot.at(tuple(A, B))); + + if (part_andnot.count(tuple(B, A))) + make_hs(B, A, it.second, part_andnot.at(tuple(B, A))); + + if (part_and.count(tuple(A, B))) + make_ha(A, B, it.second, part_and.at(tuple(A, B))); + } + } +}; + +struct AddersPass : public Pass { + AddersPass() : Pass("adders", "find and extract full/half adders/subtractors") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" adders [options] [selection]\n"); + log("\n"); + log("This pass extracts full/half adders/subtractors from a gate-level design.\n"); + log("\n"); + log(" -fa, -ha, -fs, -hs\n"); + log(" Enable cell types (f=full, h=half, a=adder, s=subtractor)\n"); + log(" All types are enabled if none of this options is used\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + AddersConfig config; + + log_header(design, "Executing ADDERS pass (find and extract full/half adders/subtractors).\n"); + log_push(); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-fa") { + config.enable_fa = true; + continue; + } + if (args[argidx] == "-ha") { + config.enable_ha = true; + continue; + } + if (args[argidx] == "-fs") { + config.enable_fs = true; + continue; + } + if (args[argidx] == "-hs") { + config.enable_hs = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + if (!config.enable_fa && !config.enable_ha && !config.enable_fs && !config.enable_hs) { + config.enable_fa = true; + config.enable_ha = true; + config.enable_fs = true; + config.enable_hs = true; + } + + for (auto module : design->selected_modules()) + { + AddersWorker worker(config, module); + worker.run(); + } + + log_pop(); + } +} AddersPass; + +PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 15cdda7c4b1f5d3dff636220bce34bde407521af Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 23 Aug 2017 14:20:10 +0200 Subject: Towards more generic "adder" function extractor --- passes/techmap/adders.cc | 255 ++++++++++------------------------------------- 1 file changed, 53 insertions(+), 202 deletions(-) (limited to 'passes') diff --git a/passes/techmap/adders.cc b/passes/techmap/adders.cc index 7482d2c9b..942820609 100644 --- a/passes/techmap/adders.cc +++ b/passes/techmap/adders.cc @@ -32,6 +32,20 @@ struct AddersConfig bool enable_hs = false; }; +// http://svn.clifford.at/handicraft/2016/bindec/bindec.c +int bindec(unsigned char v) +{ + int r = v & 1; + r += (~((v & 2) - 1)) & 10; + r += (~((v & 4) - 1)) & 100; + r += (~((v & 8) - 1)) & 1000; + r += (~((v & 16) - 1)) & 10000; + r += (~((v & 32) - 1)) & 100000; + r += (~((v & 64) - 1)) & 1000000; + r += (~((v & 128) - 1)) & 10000000; + return r; +} + struct AddersWorker { const AddersConfig &config; @@ -42,13 +56,11 @@ struct AddersWorker dict driver; pool handled_bits; - dict, pool> part_xor; - dict, pool> part_and; - dict, pool> part_andnot; + pool> xorxnor2; + pool> xorxnor3; - dict, pool> part_xor3; - dict, pool> part_maj; - dict, pool> part_majnot; + dict, dict>> func2; + dict, dict>> func3; AddersWorker(const AddersConfig &config, Module *module) : config(config), module(module), ce(module), sigmap(ce.assign_map) @@ -75,19 +87,11 @@ struct AddersWorker SigBit A = SigSpec(leaves)[0]; SigBit B = SigSpec(leaves)[1]; - bool is_xor = true; - bool is_and = true; - bool is_andnot_a = true; - bool is_andnot_b = true; - + int func = 0; for (int i = 0; i < 4; i++) { bool a_value = (i & 1) != 0; bool b_value = (i & 2) != 0; - bool xor_value = a_value != b_value; - bool and_value = a_value && b_value; - bool andnot_a_value = !a_value && b_value; - bool andnot_b_value = a_value && !b_value; ce.push(); ce.set(A, a_value ? State::S1 : State::S0); @@ -98,32 +102,18 @@ struct AddersWorker if (!ce.eval(sig)) log_abort(); - if (sig != xor_value) - is_xor = false; - - if (sig != and_value) - is_and = false; - - if (sig != andnot_a_value) - is_andnot_a = false; - - if (sig != andnot_b_value) - is_andnot_b = false; + if (sig == State::S1) + func |= 1 << i; ce.pop(); } - if (is_xor) - part_xor[tuple(A, B)].insert(root); + // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root)); - if (is_and) - part_and[tuple(A, B)].insert(root); + if (func == 0x6 || func == 0x9) + xorxnor2.insert(tuple(A, B)); - if (is_andnot_a) - part_andnot[tuple(B, A)].insert(root); - - if (is_andnot_b) - part_andnot[tuple(A, B)].insert(root); + func2[tuple(A, B)][func].insert(root); } if (GetSize(leaves) == 3) @@ -134,24 +124,13 @@ struct AddersWorker SigBit B = SigSpec(leaves)[1]; SigBit C = SigSpec(leaves)[2]; - bool is_xor3 = true; - bool is_maj = true; - bool is_maj_nota = true; - bool is_maj_notb = true; - bool is_maj_notc = true; - + int func = 0; for (int i = 0; i < 8; i++) { bool a_value = (i & 1) != 0; bool b_value = (i & 2) != 0; bool c_value = (i & 4) != 0; - bool xor3_value = (a_value != b_value) != c_value; - bool maj_value = (a_value && b_value) || (a_value && c_value) || (b_value && c_value); - bool maj_nota_value = (!a_value && b_value) || (!a_value && c_value) || (b_value && c_value); - bool maj_notb_value = (a_value && !b_value) || (a_value && c_value) || (!b_value && c_value); - bool maj_notc_value = (a_value && b_value) || (a_value && !c_value) || (b_value && !c_value); - ce.push(); ce.set(A, a_value ? State::S1 : State::S0); ce.set(B, b_value ? State::S1 : State::S0); @@ -162,38 +141,18 @@ struct AddersWorker if (!ce.eval(sig)) log_abort(); - if (sig != xor3_value) - is_xor3 = false; - - if (sig != maj_value) - is_maj = false; - - if (sig != maj_nota_value) - is_maj_nota = false; - - if (sig != maj_notb_value) - is_maj_notb = false; - - if (sig != maj_notc_value) - is_maj_notc = false; + if (sig == State::S1) + func |= 1 << i; ce.pop(); } - if (is_xor3) - part_xor3[tuple(A, B, C)].insert(root); - - if (is_maj) - part_maj[tuple(A, B, C)].insert(root); - - if (is_maj_nota) - part_majnot[tuple(B, C, A)].insert(root); + // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root)); - if (is_maj_notb) - part_majnot[tuple(A, C, B)].insert(root); + if (func == 0x69 || func == 0x96) + xorxnor3.insert(tuple(A, B, C)); - if (is_maj_notc) - part_majnot[tuple(A, B, C)].insert(root); + func3[tuple(A, B, C)][func].insert(root); } } @@ -229,118 +188,6 @@ struct AddersWorker } } - void make_fa(SigBit A, SigBit B, SigBit C, const pool &sum_out, const pool &carry_out) - { - if (!config.enable_fa) - return; - - Wire *so = module->addWire(NEW_ID); - Wire *co = module->addWire(NEW_ID); - - Cell *cell = module->addCell(NEW_ID, "$__fa"); - cell->setPort("\\A", A); - cell->setPort("\\B", B); - cell->setPort("\\C", C); - cell->setPort("\\SO", so); - cell->setPort("\\CO", co); - - log("New full adder %s in module %s: A=%s B=%s C=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B), log_signal(C)); - - for (auto bit : sum_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, so); - handled_bits.insert(bit); - log(" sum out: %s\n", log_signal(bit)); - } - - for (auto bit : carry_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, co); - handled_bits.insert(bit); - log(" carry out: %s\n", log_signal(bit)); - } - } - - void make_ha(SigBit A, SigBit B, const pool &sum_out, const pool &carry_out) - { - if (!config.enable_ha) - return; - - Wire *so = module->addWire(NEW_ID); - Wire *co = module->addWire(NEW_ID); - - Cell *cell = module->addCell(NEW_ID, "$__ha"); - cell->setPort("\\A", A); - cell->setPort("\\B", B); - cell->setPort("\\SO", so); - cell->setPort("\\CO", co); - - log("New half adder %s in module %s: A=%s B=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B)); - - for (auto bit : sum_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, so); - handled_bits.insert(bit); - log(" sum out: %s\n", log_signal(bit)); - } - - for (auto bit : carry_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, co); - handled_bits.insert(bit); - log(" carry out: %s\n", log_signal(bit)); - } - } - - void make_hs(SigBit A, SigBit B, const pool &sum_out, const pool &carry_out) - { - if (!config.enable_hs) - return; - - Wire *so = module->addWire(NEW_ID); - Wire *co = module->addWire(NEW_ID); - - Cell *cell = module->addCell(NEW_ID, "$__hs"); - cell->setPort("\\A", A); - cell->setPort("\\B", B); - cell->setPort("\\SO", so); - cell->setPort("\\CO", co); - - log("New half subtractor %s in module %s: A=%s B=%s\n", log_id(cell), log_id(module), log_signal(A), log_signal(B)); - - for (auto bit : sum_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, so); - handled_bits.insert(bit); - log(" sum out: %s\n", log_signal(bit)); - } - - for (auto bit : carry_out) { - if (handled_bits.count(bit)) - continue; - Cell *drv = driver.at(bit); - drv->setPort("\\Y", module->addWire(NEW_ID)); - module->connect(bit, co); - handled_bits.insert(bit); - log(" carry out: %s\n", log_signal(bit)); - } - } - void run() { for (auto it : driver) @@ -352,31 +199,35 @@ struct AddersWorker find_partitions(root, leaves, cache, 5, 10); } - for (auto &it : part_xor3) + for (auto &key : xorxnor3) { - SigBit A = get<0>(it.first); - SigBit B = get<1>(it.first); - SigBit C = get<2>(it.first); + SigBit A = get<0>(key); + SigBit B = get<1>(key); + SigBit C = get<2>(key); - // FIXME: Add support for full subtractors + log("3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C)); - if (part_maj.count(tuple(A, B, C))) - make_fa(A, B, C, it.second, part_maj.at(tuple(A, B, C))); + for (auto &it : func3.at(key)) { + log(" %08d ->", bindec(it.first)); + for (auto bit : it.second) + log(" %s", log_signal(bit)); + log("\n"); + } } - for (auto &it : part_xor) + for (auto &key : xorxnor2) { - SigBit A = get<0>(it.first); - SigBit B = get<1>(it.first); - - if (part_andnot.count(tuple(A, B))) - make_hs(A, B, it.second, part_andnot.at(tuple(A, B))); + SigBit A = get<0>(key); + SigBit B = get<1>(key); - if (part_andnot.count(tuple(B, A))) - make_hs(B, A, it.second, part_andnot.at(tuple(B, A))); + log("2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B)); - if (part_and.count(tuple(A, B))) - make_ha(A, B, it.second, part_and.at(tuple(A, B))); + for (auto &it : func2.at(key)) { + log(" %04d ->", bindec(it.first)); + for (auto bit : it.second) + log(" %s", log_signal(bit)); + log("\n"); + } } } }; -- cgit v1.2.3 From 0bf612506c8ab67252415778db34e28f5e9d5a6d Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Fri, 25 Aug 2017 12:04:40 +0200 Subject: Rename "adders" to "extract_fa" --- passes/techmap/Makefile.inc | 2 +- passes/techmap/adders.cc | 297 ------------------------------------------- passes/techmap/extract_fa.cc | 285 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 286 insertions(+), 298 deletions(-) delete mode 100644 passes/techmap/adders.cc create mode 100644 passes/techmap/extract_fa.cc (limited to 'passes') diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc index 418cc6c2b..ce67b711d 100644 --- a/passes/techmap/Makefile.inc +++ b/passes/techmap/Makefile.inc @@ -16,6 +16,7 @@ ifneq ($(SMALL),1) OBJS += passes/techmap/iopadmap.o OBJS += passes/techmap/hilomap.o OBJS += passes/techmap/extract.o +OBJS += passes/techmap/extract_fa.o OBJS += passes/techmap/alumacc.o OBJS += passes/techmap/dff2dffe.o OBJS += passes/techmap/dffinit.o @@ -32,7 +33,6 @@ OBJS += passes/techmap/insbuf.o OBJS += passes/techmap/attrmvcp.o OBJS += passes/techmap/attrmap.o OBJS += passes/techmap/zinit.o -OBJS += passes/techmap/adders.o endif GENFILES += passes/techmap/techmap.inc diff --git a/passes/techmap/adders.cc b/passes/techmap/adders.cc deleted file mode 100644 index 942820609..000000000 --- a/passes/techmap/adders.cc +++ /dev/null @@ -1,297 +0,0 @@ -/* - * yosys -- Yosys Open SYnthesis Suite - * - * Copyright (C) 2012 Clifford Wolf - * - * 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/consteval.h" - -USING_YOSYS_NAMESPACE -PRIVATE_NAMESPACE_BEGIN - -struct AddersConfig -{ - bool enable_fa = false; - bool enable_ha = false; - bool enable_fs = false; - bool enable_hs = false; -}; - -// http://svn.clifford.at/handicraft/2016/bindec/bindec.c -int bindec(unsigned char v) -{ - int r = v & 1; - r += (~((v & 2) - 1)) & 10; - r += (~((v & 4) - 1)) & 100; - r += (~((v & 8) - 1)) & 1000; - r += (~((v & 16) - 1)) & 10000; - r += (~((v & 32) - 1)) & 100000; - r += (~((v & 64) - 1)) & 1000000; - r += (~((v & 128) - 1)) & 10000000; - return r; -} - -struct AddersWorker -{ - const AddersConfig &config; - Module *module; - ConstEval ce; - SigMap &sigmap; - - dict driver; - pool handled_bits; - - pool> xorxnor2; - pool> xorxnor3; - - dict, dict>> func2; - dict, dict>> func3; - - AddersWorker(const AddersConfig &config, Module *module) : - config(config), module(module), ce(module), sigmap(ce.assign_map) - { - for (auto cell : module->selected_cells()) - { - if (cell->type.in( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_", - "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_", - "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_")) - { - SigBit y = sigmap(SigBit(cell->getPort("\\Y"))); - log_assert(driver.count(y) == 0); - driver[y] = cell; - } - } - } - - void check_partition(SigBit root, pool &leaves) - { - if (GetSize(leaves) == 2) - { - leaves.sort(); - - SigBit A = SigSpec(leaves)[0]; - SigBit B = SigSpec(leaves)[1]; - - int func = 0; - for (int i = 0; i < 4; i++) - { - bool a_value = (i & 1) != 0; - bool b_value = (i & 2) != 0; - - ce.push(); - ce.set(A, a_value ? State::S1 : State::S0); - ce.set(B, b_value ? State::S1 : State::S0); - - SigSpec sig = root; - - if (!ce.eval(sig)) - log_abort(); - - if (sig == State::S1) - func |= 1 << i; - - ce.pop(); - } - - // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root)); - - if (func == 0x6 || func == 0x9) - xorxnor2.insert(tuple(A, B)); - - func2[tuple(A, B)][func].insert(root); - } - - if (GetSize(leaves) == 3) - { - leaves.sort(); - - SigBit A = SigSpec(leaves)[0]; - SigBit B = SigSpec(leaves)[1]; - SigBit C = SigSpec(leaves)[2]; - - int func = 0; - for (int i = 0; i < 8; i++) - { - bool a_value = (i & 1) != 0; - bool b_value = (i & 2) != 0; - bool c_value = (i & 4) != 0; - - ce.push(); - ce.set(A, a_value ? State::S1 : State::S0); - ce.set(B, b_value ? State::S1 : State::S0); - ce.set(C, c_value ? State::S1 : State::S0); - - SigSpec sig = root; - - if (!ce.eval(sig)) - log_abort(); - - if (sig == State::S1) - func |= 1 << i; - - ce.pop(); - } - - // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root)); - - if (func == 0x69 || func == 0x96) - xorxnor3.insert(tuple(A, B, C)); - - func3[tuple(A, B, C)][func].insert(root); - } - } - - void find_partitions(SigBit root, pool &leaves, pool> &cache, int maxdepth, int maxbreadth) - { - if (cache.count(leaves)) - return; - - cache.insert(leaves); - check_partition(root, leaves); - - if (maxdepth == 0) - return; - - for (SigBit bit : leaves) - { - if (driver.count(bit) == 0) - continue; - - Cell *cell = driver.at(bit); - pool new_leaves = leaves; - - new_leaves.erase(bit); - if (cell->hasPort("\\A")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\A")))); - if (cell->hasPort("\\B")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\B")))); - if (cell->hasPort("\\C")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\C")))); - if (cell->hasPort("\\D")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\D")))); - - if (GetSize(new_leaves) > maxbreadth) - continue; - - find_partitions(root, new_leaves, cache, maxdepth-1, maxbreadth); - } - } - - void run() - { - for (auto it : driver) - { - SigBit root = it.first; - pool leaves = { root }; - pool> cache; - - find_partitions(root, leaves, cache, 5, 10); - } - - for (auto &key : xorxnor3) - { - SigBit A = get<0>(key); - SigBit B = get<1>(key); - SigBit C = get<2>(key); - - log("3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C)); - - for (auto &it : func3.at(key)) { - log(" %08d ->", bindec(it.first)); - for (auto bit : it.second) - log(" %s", log_signal(bit)); - log("\n"); - } - } - - for (auto &key : xorxnor2) - { - SigBit A = get<0>(key); - SigBit B = get<1>(key); - - log("2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B)); - - for (auto &it : func2.at(key)) { - log(" %04d ->", bindec(it.first)); - for (auto bit : it.second) - log(" %s", log_signal(bit)); - log("\n"); - } - } - } -}; - -struct AddersPass : public Pass { - AddersPass() : Pass("adders", "find and extract full/half adders/subtractors") { } - virtual void help() - { - // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| - log("\n"); - log(" adders [options] [selection]\n"); - log("\n"); - log("This pass extracts full/half adders/subtractors from a gate-level design.\n"); - log("\n"); - log(" -fa, -ha, -fs, -hs\n"); - log(" Enable cell types (f=full, h=half, a=adder, s=subtractor)\n"); - log(" All types are enabled if none of this options is used\n"); - log("\n"); - } - virtual void execute(std::vector args, RTLIL::Design *design) - { - AddersConfig config; - - log_header(design, "Executing ADDERS pass (find and extract full/half adders/subtractors).\n"); - log_push(); - - size_t argidx; - for (argidx = 1; argidx < args.size(); argidx++) - { - if (args[argidx] == "-fa") { - config.enable_fa = true; - continue; - } - if (args[argidx] == "-ha") { - config.enable_ha = true; - continue; - } - if (args[argidx] == "-fs") { - config.enable_fs = true; - continue; - } - if (args[argidx] == "-hs") { - config.enable_hs = true; - continue; - } - break; - } - extra_args(args, argidx, design); - - if (!config.enable_fa && !config.enable_ha && !config.enable_fs && !config.enable_hs) { - config.enable_fa = true; - config.enable_ha = true; - config.enable_fs = true; - config.enable_hs = true; - } - - for (auto module : design->selected_modules()) - { - AddersWorker worker(config, module); - worker.run(); - } - - log_pop(); - } -} AddersPass; - -PRIVATE_NAMESPACE_END diff --git a/passes/techmap/extract_fa.cc b/passes/techmap/extract_fa.cc new file mode 100644 index 000000000..3f040e05b --- /dev/null +++ b/passes/techmap/extract_fa.cc @@ -0,0 +1,285 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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/consteval.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct ExtractFaConfig +{ + bool enable_fa = false; + bool enable_ha = false; +}; + +// http://svn.clifford.at/handicraft/2016/bindec/bindec.c +int bindec(unsigned char v) +{ + int r = v & 1; + r += (~((v & 2) - 1)) & 10; + r += (~((v & 4) - 1)) & 100; + r += (~((v & 8) - 1)) & 1000; + r += (~((v & 16) - 1)) & 10000; + r += (~((v & 32) - 1)) & 100000; + r += (~((v & 64) - 1)) & 1000000; + r += (~((v & 128) - 1)) & 10000000; + return r; +} + +struct ExtractFaWorker +{ + const ExtractFaConfig &config; + Module *module; + ConstEval ce; + SigMap &sigmap; + + dict driver; + pool handled_bits; + + pool> xorxnor2; + pool> xorxnor3; + + dict, dict>> func2; + dict, dict>> func3; + + ExtractFaWorker(const ExtractFaConfig &config, Module *module) : + config(config), module(module), ce(module), sigmap(ce.assign_map) + { + for (auto cell : module->selected_cells()) + { + if (cell->type.in( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_", + "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_", + "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_")) + { + SigBit y = sigmap(SigBit(cell->getPort("\\Y"))); + log_assert(driver.count(y) == 0); + driver[y] = cell; + } + } + } + + void check_partition(SigBit root, pool &leaves) + { + if (GetSize(leaves) == 2) + { + leaves.sort(); + + SigBit A = SigSpec(leaves)[0]; + SigBit B = SigSpec(leaves)[1]; + + int func = 0; + for (int i = 0; i < 4; i++) + { + bool a_value = (i & 1) != 0; + bool b_value = (i & 2) != 0; + + ce.push(); + ce.set(A, a_value ? State::S1 : State::S0); + ce.set(B, b_value ? State::S1 : State::S0); + + SigSpec sig = root; + + if (!ce.eval(sig)) + log_abort(); + + if (sig == State::S1) + func |= 1 << i; + + ce.pop(); + } + + // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root)); + + if (func == 0x6 || func == 0x9) + xorxnor2.insert(tuple(A, B)); + + func2[tuple(A, B)][func].insert(root); + } + + if (GetSize(leaves) == 3) + { + leaves.sort(); + + SigBit A = SigSpec(leaves)[0]; + SigBit B = SigSpec(leaves)[1]; + SigBit C = SigSpec(leaves)[2]; + + int func = 0; + for (int i = 0; i < 8; i++) + { + bool a_value = (i & 1) != 0; + bool b_value = (i & 2) != 0; + bool c_value = (i & 4) != 0; + + ce.push(); + ce.set(A, a_value ? State::S1 : State::S0); + ce.set(B, b_value ? State::S1 : State::S0); + ce.set(C, c_value ? State::S1 : State::S0); + + SigSpec sig = root; + + if (!ce.eval(sig)) + log_abort(); + + if (sig == State::S1) + func |= 1 << i; + + ce.pop(); + } + + // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root)); + + if (func == 0x69 || func == 0x96) + xorxnor3.insert(tuple(A, B, C)); + + func3[tuple(A, B, C)][func].insert(root); + } + } + + void find_partitions(SigBit root, pool &leaves, pool> &cache, int maxdepth, int maxbreadth) + { + if (cache.count(leaves)) + return; + + cache.insert(leaves); + check_partition(root, leaves); + + if (maxdepth == 0) + return; + + for (SigBit bit : leaves) + { + if (driver.count(bit) == 0) + continue; + + Cell *cell = driver.at(bit); + pool new_leaves = leaves; + + new_leaves.erase(bit); + if (cell->hasPort("\\A")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\A")))); + if (cell->hasPort("\\B")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\B")))); + if (cell->hasPort("\\C")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\C")))); + if (cell->hasPort("\\D")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\D")))); + + if (GetSize(new_leaves) > maxbreadth) + continue; + + find_partitions(root, new_leaves, cache, maxdepth-1, maxbreadth); + } + } + + void run() + { + for (auto it : driver) + { + SigBit root = it.first; + pool leaves = { root }; + pool> cache; + + find_partitions(root, leaves, cache, 5, 10); + } + + for (auto &key : xorxnor3) + { + SigBit A = get<0>(key); + SigBit B = get<1>(key); + SigBit C = get<2>(key); + + log("3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C)); + + for (auto &it : func3.at(key)) { + log(" %08d ->", bindec(it.first)); + for (auto bit : it.second) + log(" %s", log_signal(bit)); + log("\n"); + } + } + + for (auto &key : xorxnor2) + { + SigBit A = get<0>(key); + SigBit B = get<1>(key); + + log("2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B)); + + for (auto &it : func2.at(key)) { + log(" %04d ->", bindec(it.first)); + for (auto bit : it.second) + log(" %s", log_signal(bit)); + log("\n"); + } + } + } +}; + +struct ExtractFaPass : public Pass { + ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" extract_fa [options] [selection]\n"); + log("\n"); + log("This pass extracts full/half adders from a gate-level design.\n"); + log("\n"); + log(" -fa, -ha\n"); + log(" Enable cell types (fa=full adder, ha=half adder)\n"); + log(" All types are enabled if none of this options is used\n"); + log("\n"); + } + virtual void execute(std::vector args, RTLIL::Design *design) + { + ExtractFaConfig config; + + log_header(design, "Executing EXTRACT_FA pass (find and extract full/half adders).\n"); + log_push(); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-fa") { + config.enable_fa = true; + continue; + } + if (args[argidx] == "-ha") { + config.enable_ha = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + if (!config.enable_fa && !config.enable_ha) { + config.enable_fa = true; + config.enable_ha = true; + } + + for (auto module : design->selected_modules()) + { + ExtractFaWorker worker(config, module); + worker.run(); + } + + log_pop(); + } +} ExtractFaPass; + +PRIVATE_NAMESPACE_END -- cgit v1.2.3 From 382cc90c650939e53f53c2389155020fcb0ef1ac Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Fri, 25 Aug 2017 13:41:54 +0200 Subject: Further improve extract_fa (seems to be fully functional now) --- passes/techmap/extract_fa.cc | 236 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 226 insertions(+), 10 deletions(-) (limited to 'passes') diff --git a/passes/techmap/extract_fa.cc b/passes/techmap/extract_fa.cc index 3f040e05b..162a90306 100644 --- a/passes/techmap/extract_fa.cc +++ b/passes/techmap/extract_fa.cc @@ -54,12 +54,26 @@ struct ExtractFaWorker dict driver; pool handled_bits; + const int xor2_func = 0x6, xnor2_func = 0x9; + const int xor3_func = 0x96, xnor3_func = 0x69; + pool> xorxnor2; pool> xorxnor3; dict, dict>> func2; dict, dict>> func3; + struct func2_and_info_t { + bool inv_a, inv_b, inv_y; + }; + + struct func3_maj_info_t { + bool inv_a, inv_b, inv_c, inv_y; + }; + + dict func2_and_info; + dict func3_maj_info; + ExtractFaWorker(const ExtractFaConfig &config, Module *module) : config(config), module(module), ce(module), sigmap(ce.assign_map) { @@ -74,11 +88,68 @@ struct ExtractFaWorker driver[y] = cell; } } + + for (int ia = 0; ia < 2; ia++) + for (int ib = 0; ib < 2; ib++) + { + func2_and_info_t f2i; + + f2i.inv_a = ia; + f2i.inv_b = ib; + f2i.inv_y = false; + + int func = 0; + for (int i = 0; i < 4; i++) + { + bool a = (i & 1) ? !f2i.inv_a : f2i.inv_a; + bool b = (i & 2) ? !f2i.inv_b : f2i.inv_b; + if (a && b) func |= 1 << i; + } + + log_assert(func2_and_info.count(func) == 0); + func2_and_info[func] = f2i; + + f2i.inv_y = true; + func ^= 15; + + log_assert(func2_and_info.count(func) == 0); + func2_and_info[func] = f2i; + } + + for (int ia = 0; ia < 2; ia++) + for (int ib = 0; ib < 2; ib++) + for (int ic = 0; ic < 2; ic++) + { + func3_maj_info_t f3i; + + f3i.inv_a = ia; + f3i.inv_b = ib; + f3i.inv_c = ic; + f3i.inv_y = false; + + int func = 0; + for (int i = 0; i < 8; i++) + { + bool a = (i & 1) ? !f3i.inv_a : f3i.inv_a; + bool b = (i & 2) ? !f3i.inv_b : f3i.inv_b; + bool c = (i & 4) ? !f3i.inv_c : f3i.inv_c; + if ((a && b) || (a && c) || (b &&c)) func |= 1 << i; + } + + log_assert(func3_maj_info.count(func) == 0); + func3_maj_info[func] = f3i; + + // f3i.inv_y = true; + // func ^= 255; + + // log_assert(func3_maj_info.count(func) == 0); + // func3_maj_info[func] = f3i; + } } void check_partition(SigBit root, pool &leaves) { - if (GetSize(leaves) == 2) + if (config.enable_ha && GetSize(leaves) == 2) { leaves.sort(); @@ -108,13 +179,13 @@ struct ExtractFaWorker // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root)); - if (func == 0x6 || func == 0x9) + if (func == xor2_func || func == xnor2_func) xorxnor2.insert(tuple(A, B)); func2[tuple(A, B)][func].insert(root); } - if (GetSize(leaves) == 3) + if (config.enable_fa && GetSize(leaves) == 3) { leaves.sort(); @@ -147,7 +218,7 @@ struct ExtractFaWorker // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root)); - if (func == 0x69 || func == 0x96) + if (func == xor3_func || func == xnor3_func) xorxnor3.insert(tuple(A, B, C)); func3[tuple(A, B, C)][func].insert(root); @@ -159,6 +230,11 @@ struct ExtractFaWorker if (cache.count(leaves)) return; + // log("%*s[%d] %s:", 20-maxdepth, "", maxdepth, log_signal(root)); + // for (auto bit : leaves) + // log(" %s", log_signal(bit)); + // log("\n"); + cache.insert(leaves); check_partition(root, leaves); @@ -186,15 +262,29 @@ struct ExtractFaWorker } } + void assign_new_driver(SigBit bit, SigBit new_driver) + { + Cell *cell = driver.at(bit); + if (sigmap(cell->getPort("\\Y")) == bit) { + cell->setPort("\\Y", module->addWire(NEW_ID)); + module->connect(bit, new_driver); + } + } + void run() { + log("Extracting full/half adders from %s:\n", log_id(module)); + for (auto it : driver) { + if (it.second->type.in("$_BUF_", "$_NOT_")) + continue; + SigBit root = it.first; pool leaves = { root }; pool> cache; - find_partitions(root, leaves, cache, 5, 10); + find_partitions(root, leaves, cache, 20, 10); } for (auto &key : xorxnor3) @@ -203,14 +293,81 @@ struct ExtractFaWorker SigBit B = get<1>(key); SigBit C = get<2>(key); - log("3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C)); + log(" 3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C)); - for (auto &it : func3.at(key)) { - log(" %08d ->", bindec(it.first)); + for (auto &it : func3.at(key)) + { + if (it.first != xor3_func && it.first != xnor3_func) + continue; + + log(" %08d ->", bindec(it.first)); for (auto bit : it.second) log(" %s", log_signal(bit)); log("\n"); } + + for (auto &it : func3_maj_info) + { + int func = it.first; + auto f3i = it.second; + + if (func3.at(key).count(func) == 0) + continue; + + if (func3.at(key).count(xor3_func) == 0 && func3.at(key).count(xnor3_func) != 0) { + f3i.inv_a = !f3i.inv_a; + f3i.inv_b = !f3i.inv_b; + f3i.inv_c = !f3i.inv_c; + f3i.inv_y = !f3i.inv_y; + } + + if (!f3i.inv_a && !f3i.inv_b && !f3i.inv_c && !f3i.inv_y) { + log(" Majority without inversions:\n"); + } else { + log(" Majority with inverted"); + if (f3i.inv_a) log(" A"); + if (f3i.inv_b) log(" B"); + if (f3i.inv_c) log(" C"); + if (f3i.inv_y) log(" Y"); + log(":\n"); + } + + log(" %08d ->", bindec(func)); + for (auto bit : func3.at(key).at(func)) + log(" %s", log_signal(bit)); + log("\n"); + + Cell *cell = module->addCell(NEW_ID, "$fa"); + cell->setParam("\\WIDTH", 1); + + log(" Created $fa cell %s.\n", log_id(cell)); + + cell->setPort("\\A", f3i.inv_a ? module->NotGate(NEW_ID, A) : A); + cell->setPort("\\B", f3i.inv_b ? module->NotGate(NEW_ID, B) : B); + cell->setPort("\\C", f3i.inv_c ? module->NotGate(NEW_ID, C) : C); + + SigBit X = module->addWire(NEW_ID); + SigBit Y = module->addWire(NEW_ID); + + cell->setPort("\\X", X); + cell->setPort("\\Y", Y); + + if (func3.at(key).count(xor3_func)) { + for (auto bit : func3.at(key).at(xor3_func)) + assign_new_driver(bit, Y); + } + + if (func3.at(key).count(xnor3_func)) { + SigBit YN = module->NotGate(NEW_ID, Y); + for (auto bit : func3.at(key).at(xnor3_func)) + assign_new_driver(bit, YN); + } + + SigBit XX = f3i.inv_y ? module->NotGate(NEW_ID, X) : X; + + for (auto bit : func3.at(key).at(func)) + assign_new_driver(bit, XX); + } } for (auto &key : xorxnor2) @@ -218,14 +375,73 @@ struct ExtractFaWorker SigBit A = get<0>(key); SigBit B = get<1>(key); - log("2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B)); + log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B)); + + for (auto &it : func2.at(key)) + { + if (it.first != xor2_func && it.first != xnor2_func) + continue; - for (auto &it : func2.at(key)) { log(" %04d ->", bindec(it.first)); for (auto bit : it.second) log(" %s", log_signal(bit)); log("\n"); } + + for (auto &it : func2_and_info) + { + int func = it.first; + auto &f2i = it.second; + + if (func2.at(key).count(func) == 0) + continue; + + if (!f2i.inv_a && !f2i.inv_b && !f2i.inv_y) { + log(" AND without inversions:\n"); + } else { + log(" AND with inverted"); + if (f2i.inv_a) log(" A"); + if (f2i.inv_b) log(" B"); + if (f2i.inv_y) log(" Y"); + log(":\n"); + } + + log(" %04d ->", bindec(func)); + for (auto bit : func2.at(key).at(func)) + log(" %s", log_signal(bit)); + log("\n"); + + Cell *cell = module->addCell(NEW_ID, "$fa"); + cell->setParam("\\WIDTH", 1); + + log(" Created $fa cell %s.\n", log_id(cell)); + + cell->setPort("\\A", f2i.inv_a ? module->NotGate(NEW_ID, A) : A); + cell->setPort("\\B", f2i.inv_b ? module->NotGate(NEW_ID, B) : B); + cell->setPort("\\C", State::S0); + + SigBit X = module->addWire(NEW_ID); + SigBit Y = module->addWire(NEW_ID); + + cell->setPort("\\X", X); + cell->setPort("\\Y", Y); + + if (func2.at(key).count(xor2_func)) { + for (auto bit : func2.at(key).at(xor2_func)) + assign_new_driver(bit, Y); + } + + if (func2.at(key).count(xnor2_func)) { + SigBit YN = module->NotGate(NEW_ID, Y); + for (auto bit : func2.at(key).at(xnor2_func)) + assign_new_driver(bit, YN); + } + + SigBit XX = f2i.inv_y ? module->NotGate(NEW_ID, X) : X; + + for (auto bit : func2.at(key).at(func)) + assign_new_driver(bit, XX); + } } } }; -- cgit v1.2.3