From 382cc90c650939e53f53c2389155020fcb0ef1ac Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Fri, 25 Aug 2017 13:41:54 +0200 Subject: [PATCH] Further improve extract_fa (seems to be fully functional now) --- passes/techmap/extract_fa.cc | 236 +++++++++++++++++++++++++++++++++-- 1 file changed, 226 insertions(+), 10 deletions(-) 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); + } } } }; -- 2.30.2