From 1ae360cf725db65c54c69042bcef66f1728b4df6 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 10 Jun 2015 23:00:12 +0200 Subject: [PATCH] AigMaker refactoring --- backends/json/json.cc | 2 +- kernel/cellaigs.cc | 226 ++++++++++++++++++++++++++------------- kernel/cellaigs.h | 1 + passes/techmap/aigmap.cc | 2 +- 4 files changed, 153 insertions(+), 78 deletions(-) diff --git a/backends/json/json.cc b/backends/json/json.cc index 42bec2776..52b97ef0b 100644 --- a/backends/json/json.cc +++ b/backends/json/json.cc @@ -225,7 +225,7 @@ struct JsonWriter f << stringf("\"%sport\", \"%s\", %d", node.inverter ? "n" : "", log_id(node.portname), node.portbit); else if (node.left_parent < 0 && node.right_parent < 0) - f << stringf("\"%s\"", node.inverter ? "false" : "true"); + f << stringf("\"%s\"", node.inverter ? "true" : "false"); else f << stringf("\"%s\", %d, %d", node.inverter ? "nand" : "and", node.left_parent, node.right_parent); for (auto &op : node.outports) diff --git a/kernel/cellaigs.cc b/kernel/cellaigs.cc index 1d9612e81..48727c145 100644 --- a/kernel/cellaigs.cc +++ b/kernel/cellaigs.cc @@ -21,6 +21,14 @@ YOSYS_NAMESPACE_BEGIN +AigNode::AigNode() +{ + portbit = -1; + inverter = false; + left_parent = -1; + right_parent = -1; +} + bool AigNode::operator==(const AigNode &other) const { if (portname != other.portname) return false; @@ -66,13 +74,13 @@ struct AigMaker the_false_node = -1; } - int bool_node(bool value) + int node2index(const AigNode &node) { - AigNode node; - node.portbit = -1; - node.inverter = !value; - node.left_parent = -1; - node.right_parent = -1; + if (node.left_parent > node.right_parent) { + AigNode n(node); + std::swap(n.left_parent, n.right_parent); + return node2index(n); + } if (!aig_indices.count(node)) { aig_indices.expect(node, GetSize(aig->nodes)); @@ -82,6 +90,13 @@ struct AigMaker return aig_indices.at(node); } + int bool_node(bool value) + { + AigNode node; + node.inverter = value; + return node2index(node); + } + int inport(IdString portname, int portbit = 0, bool inverter = false) { if (portbit >= GetSize(cell->getPort(portname))) { @@ -94,15 +109,7 @@ struct AigMaker node.portname = portname; node.portbit = portbit; node.inverter = inverter; - node.left_parent = -1; - node.right_parent = -1; - - if (!aig_indices.count(node)) { - aig_indices.expect(node, GetSize(aig->nodes)); - aig->nodes.push_back(node); - } - - return aig_indices.at(node); + return node2index(node); } int not_inport(IdString portname, int portbit = 0) @@ -110,28 +117,86 @@ struct AigMaker return inport(portname, portbit, true); } - int and_gate(int left_parent, int right_parent, bool inverter = false) + int not_gate(int A) + { + AigNode node(aig_indices[A]); + node.outports.clear(); + node.inverter = !node.inverter; + return node2index(node); + } + + int and_gate(int A, int B, bool inverter = false) { - if (left_parent > right_parent) - std::swap(left_parent, right_parent); + if (A == B) + return A; + + const AigNode &nA = aig_indices[A]; + const AigNode &nB = aig_indices[B]; + + AigNode nB_inv(nB); + nB_inv.inverter = !nB_inv.inverter; + + if (nA == nB_inv) + return bool_node(inverter); + + bool nA_bool = nA.portbit < 0 && nA.left_parent < 0 && nA.right_parent < 0; + bool nB_bool = nB.portbit < 0 && nB.left_parent < 0 && nB.right_parent < 0; + + if (nA_bool && nB_bool) { + bool bA = nA.inverter; + bool bB = nB.inverter; + return bool_node(inverter != (bA && bB)); + } + + if (nA_bool) { + bool bA = nA.inverter; + if (inverter) + return bA ? not_gate(B) : bool_node(true); + return bA ? B : bool_node(false); + } + + if (nB_bool) { + bool bB = nB.inverter; + if (inverter) + return bB ? not_gate(A) : bool_node(true); + return bB ? A : bool_node(false); + } AigNode node; - node.portbit = -1; node.inverter = inverter; - node.left_parent = left_parent; - node.right_parent = right_parent; + node.left_parent = A; + node.right_parent = B; + return node2index(node); + } - if (!aig_indices.count(node)) { - aig_indices.expect(node, GetSize(aig->nodes)); - aig->nodes.push_back(node); - } + int nand_gate(int A, int B) + { + return and_gate(A, B, true); + } - return aig_indices.at(node); + int or_gate(int A, int B) + { + return nand_gate(not_gate(A), not_gate(B)); + } + + int nor_gate(int A, int B) + { + return and_gate(not_gate(A), not_gate(B)); } - int nand_gate(int left_parent, int right_parent) + int xor_gate(int A, int B) { - return and_gate(left_parent, right_parent, true); + return nor_gate(and_gate(A, B), nor_gate(A, B)); + } + + int xnor_gate(int A, int B) + { + return or_gate(and_gate(A, B), nor_gate(A, B)); + } + + int mux_gate(int A, int B, int S) + { + return or_gate(and_gate(A, not_gate(S)), and_gate(B, S)); } void outport(int node, IdString portname, int portbit = 0) @@ -153,78 +218,62 @@ Aig::Aig(Cell *cell) for (auto p : cell->parameters) name += stringf(":%d", p.second.as_int()); - if (cell->type.in("$and", "$_AND_", "$_NAND_")) + if (cell->type.in("$not", "$_NOT_")) { for (int i = 0; i < GetSize(cell->getPort("\\Y")); i++) { int A = mk.inport("\\A", i); - int B = mk.inport("\\B", i); - int Y = mk.and_gate(A, B, cell->type == "$_NAND_"); - mk.outport(Y, "\\Y", i); - } - return; - } - - if (cell->type.in("$or", "$_OR_", "$_NOR_")) - { - for (int i = 0; i < GetSize(cell->getPort("\\Y")); i++) { - int A = mk.not_inport("\\A", i); - int B = mk.not_inport("\\B", i); - int Y = mk.and_gate(A, B, cell->type != "$_NOR_"); + int Y = mk.not_gate(A); mk.outport(Y, "\\Y", i); } - return; + goto optimize; } - if (cell->type.in("$xor", "$xnor", "$_XOR_", "$_XNOR_")) + if (cell->type.in("$and", "$_AND_", "$_NAND_", "$or", "$_OR_", "$_NOR_", "$xor", "$xnor", "$_XOR_", "$_XNOR_")) { for (int i = 0; i < GetSize(cell->getPort("\\Y")); i++) { int A = mk.inport("\\A", i); int B = mk.inport("\\B", i); - int NA = mk.not_inport("\\A", i); - int NB = mk.not_inport("\\B", i); - int NOT_AB = mk.nand_gate(A, B); - int NOT_NAB = mk.nand_gate(NA, NB); - int Y = mk.and_gate(NOT_AB, NOT_NAB, !cell->type.in("$xor", "$_XOR_")); + int Y = cell->type.in("$and", "$_AND_") ? mk.and_gate(A, B) : + cell->type.in("$_NAND_") ? mk.nand_gate(A, B) : + cell->type.in("$or", "$_OR_") ? mk.or_gate(A, B) : + cell->type.in("$_NOR_") ? mk.nor_gate(A, B) : + cell->type.in("$xor", "$_XOR_") ? mk.xor_gate(A, B) : + cell->type.in("$xnor", "$_XNOR_") ? mk.xnor_gate(A, B) : -1; mk.outport(Y, "\\Y", i); } - return; + goto optimize; } if (cell->type.in("$mux", "$_MUX_")) { int S = mk.inport("\\S"); - int NS = mk.not_inport("\\S"); for (int i = 0; i < GetSize(cell->getPort("\\Y")); i++) { int A = mk.inport("\\A", i); int B = mk.inport("\\B", i); - int NOT_SB = mk.nand_gate(S, B); - int NOT_NSA = mk.nand_gate(NS, A); - int Y = mk.nand_gate(NOT_SB, NOT_NSA); + int Y = mk.mux_gate(A, B, S); mk.outport(Y, "\\Y", i); } - return; + goto optimize; } if (cell->type == "$_AOI3_") { int A = mk.inport("\\A"); int B = mk.inport("\\B"); - int NC = mk.not_inport("\\C"); - int NOT_AB = mk.nand_gate(A, B); - int Y = mk.and_gate(NOT_AB, NC); + int C = mk.inport("\\C"); + int Y = mk.nor_gate(mk.and_gate(A, B), C); mk.outport(Y, "\\Y"); - return; + goto optimize; } if (cell->type == "$_OAI3_") { - int NA = mk.not_inport("\\A"); - int NB = mk.not_inport("\\B"); + int A = mk.inport("\\A"); + int B = mk.inport("\\B"); int C = mk.inport("\\C"); - int NOT_NAB = mk.nand_gate(NA, NB); - int Y = mk.nand_gate(NOT_NAB, C); + int Y = mk.nand_gate(mk.or_gate(A, B), C); mk.outport(Y, "\\Y"); - return; + goto optimize; } if (cell->type == "$_AOI4_") @@ -233,27 +282,52 @@ Aig::Aig(Cell *cell) int B = mk.inport("\\B"); int C = mk.inport("\\C"); int D = mk.inport("\\D"); - int NOT_AB = mk.nand_gate(A, B); - int NOT_CD = mk.nand_gate(C, D); - int Y = mk.and_gate(NOT_AB, NOT_CD); + int Y = mk.nor_gate(mk.and_gate(A, B), mk.and_gate(C, D)); mk.outport(Y, "\\Y"); - return; + goto optimize; } if (cell->type == "$_OAI4_") { - int NA = mk.not_inport("\\A"); - int NB = mk.not_inport("\\B"); - int NC = mk.not_inport("\\C"); - int ND = mk.not_inport("\\D"); - int NOT_NAB = mk.nand_gate(NA, NB); - int NOT_NCD = mk.nand_gate(NC, ND); - int Y = mk.nand_gate(NOT_NAB, NOT_NCD); + int A = mk.inport("\\A"); + int B = mk.inport("\\B"); + int C = mk.inport("\\C"); + int D = mk.inport("\\D"); + int Y = mk.nand_gate(mk.nor_gate(A, B), mk.nor_gate(C, D)); mk.outport(Y, "\\Y"); - return; + goto optimize; } name.clear(); + return; + +optimize:; + pool used_old_ids; + vector new_nodes; + dict old_to_new_ids; + old_to_new_ids[-1] = -1; + + for (int i = GetSize(nodes)-1; i >= 0; i--) { + if (!nodes[i].outports.empty()) + used_old_ids.insert(i); + if (!used_old_ids.count(i)) + continue; + if (nodes[i].left_parent >= 0) + used_old_ids.insert(nodes[i].left_parent); + if (nodes[i].right_parent >= 0) + used_old_ids.insert(nodes[i].right_parent); + } + + for (int i = 0; i < GetSize(nodes); i++) { + if (!used_old_ids.count(i)) + continue; + nodes[i].left_parent = old_to_new_ids.at(nodes[i].left_parent); + nodes[i].right_parent = old_to_new_ids.at(nodes[i].right_parent); + old_to_new_ids[i] = GetSize(new_nodes); + new_nodes.push_back(nodes[i]); + } + + new_nodes.swap(nodes); } YOSYS_NAMESPACE_END diff --git a/kernel/cellaigs.h b/kernel/cellaigs.h index efe9d83c1..f548f4667 100644 --- a/kernel/cellaigs.h +++ b/kernel/cellaigs.h @@ -32,6 +32,7 @@ struct AigNode int left_parent, right_parent; vector> outports; + AigNode(); bool operator==(const AigNode &other) const; unsigned int hash() const; }; diff --git a/passes/techmap/aigmap.cc b/passes/techmap/aigmap.cc index 9f552e3e5..5253b0f8a 100644 --- a/passes/techmap/aigmap.cc +++ b/passes/techmap/aigmap.cc @@ -89,7 +89,7 @@ struct AigmapPass : public Pass { if (node.portbit >= 0) { bit = cell->getPort(node.portname)[node.portbit]; } else if (node.left_parent < 0 && node.right_parent < 0) { - bit = node.inverter ? State::S0 : State::S1; + bit = node.inverter ? State::S1 : State::S0; goto skip_inverter; } else { SigBit A = sigs.at(node.left_parent); -- 2.30.2