Cleanup/optimise toposort in write_xaiger

1 files changed, 47 insertions, 54 deletions

diff --git a/backends/aiger/xaiger.cc b/backends/aiger/xaiger.cc
index fcf9a7bf1..5a26548b8 100644
--- a/backends/aiger/xaiger.cc
+++ b/backends/aiger/xaiger.cc
@@ -167,51 +167,12 @@ struct XAigerWriter
 			if (!bit.wire->port_input)
 				unused_bits.erase(bit);
 
-		dict<SigBit, pool<IdString>> bit_drivers, bit_users;
-		TopoSort<IdString, RTLIL::sort_by_id_str> toposort;
+		SigMap topomap;
+		topomap.database = sigmap.database;
+
 		bool abc_box_seen = false;
 
 		for (auto cell : module->cells()) {
-			RTLIL::Module* inst_module = module->design->module(cell->type);
-			bool builtin_type = yosys_celltypes.cell_known(cell->type);
-			bool abc_type = inst_module && inst_module->attributes.count("\\abc_box_id");
-
-			if (!holes_mode) {
-				toposort.node(cell->name);
-				for (const auto &conn : cell->connections()) {
-					if (!builtin_type && !abc_type)
-						continue;
-
-					if (!cell->type.in("$_NOT_", "$_AND_")) {
-						if (builtin_type) {
-							if (conn.first.in("\\Q", "\\CTRL_OUT", "\\RD_DATA"))
-								continue;
-							if (cell->type == "$memrd" && conn.first == "\\DATA")
-								continue;
-						}
-
-						if (inst_module) {
-							RTLIL::Wire* inst_module_port = inst_module->wire(conn.first);
-							log_assert(inst_module_port);
-
-							if (inst_module_port->port_output && inst_module_port->attributes.count("\\abc_flop_q"))
-									continue;
-						}
-					}
-
-					if (cell->input(conn.first)) {
-						// Ignore inout for the sake of topographical ordering
-						if (cell->output(conn.first)) continue;
-						for (auto bit : sigmap(conn.second))
-							bit_users[bit].insert(cell->name);
-					}
-
-					if (cell->output(conn.first))
-						for (auto bit : sigmap(conn.second))
-							bit_drivers[bit].insert(cell->name);
-				}
-			}
-
 			if (cell->type == "$_NOT_")
 			{
 				SigBit A = sigmap(cell->getPort("\\A").as_bit());
@@ -219,6 +180,8 @@ struct XAigerWriter
 				unused_bits.erase(A);
 				undriven_bits.erase(Y);
 				not_map[Y] = A;
+				if (!holes_mode)
+					topomap.add(Y, A);
 				continue;
 			}
 
@@ -241,6 +204,10 @@ struct XAigerWriter
 				unused_bits.erase(B);
 				undriven_bits.erase(Y);
 				and_map[Y] = make_pair(A, B);
+				if (!holes_mode) {
+					topomap.add(Y, A);
+					topomap.add(Y, B);
+				}
 				continue;
 			}
 
@@ -252,6 +219,7 @@ struct XAigerWriter
 			//	continue;
 			//}
 
+			RTLIL::Module* inst_module = module->design->module(cell->type);
 			bool inst_flop = inst_module ? inst_module->attributes.count("\\abc_flop") : false;
 			if (inst_flop) {
 				SigBit d, q;
@@ -322,20 +290,46 @@ struct XAigerWriter
 			//log_warning("Unsupported cell type: %s (%s)\n", log_id(cell->type), log_id(cell));
 		}
 
-		if (abc_box_seen) {
+		if (abc_box_seen && !holes_mode) {
+			TopoSort<IdString, RTLIL::sort_by_id_str> toposort;
+			dict<SigBit, pool<IdString>> bit_drivers, bit_users;
+
+			for (auto cell : module->cells()) {
+				RTLIL::Module* inst_module = module->design->module(cell->type);
+				if (!inst_module || !inst_module->attributes.count("\\abc_box_id"))
+					continue;
+				toposort.node(cell->name);
+				for (const auto &conn : cell->connections()) {
+					if (cell->input(conn.first)) {
+						// Ignore inout for the sake of topographical ordering
+						if (cell->output(conn.first)) continue;
+						for (auto bit : topomap(conn.second))
+							if (bit.wire)
+								bit_users[bit].insert(cell->name);
+					}
+
+					if (cell->output(conn.first)) {
+						RTLIL::Wire* inst_module_port = inst_module->wire(conn.first);
+						log_assert(inst_module_port);
+						if (inst_module_port->attributes.count("\\abc_flop_q"))
+							continue;
+						for (auto bit : topomap(conn.second))
+							bit_drivers[bit].insert(cell->name);
+					}
+				}
+			}
+
 			for (auto &it : bit_users)
 				if (bit_drivers.count(it.first))
 					for (auto driver_cell : bit_drivers.at(it.first))
-					for (auto user_cell : it.second)
-						toposort.edge(driver_cell, user_cell);
+						for (auto user_cell : it.second)
+							toposort.edge(driver_cell, user_cell);
 
-			pool<RTLIL::Module*> abc_carry_modules;
-
-#if 0
+#if 1
 			toposort.analyze_loops = true;
 #endif
 			bool no_loops = toposort.sort();
-#if 0
+#if 1
 			unsigned i = 0;
 			for (auto &it : toposort.loops) {
 				log("  loop %d", i++);
@@ -346,13 +340,14 @@ struct XAigerWriter
 #endif
 			log_assert(no_loops);
 
+			pool<RTLIL::Module*> abc_carry_modules;
 			for (auto cell_name : toposort.sorted) {
 				RTLIL::Cell *cell = module->cell(cell_name);
 				RTLIL::Module* box_module = module->design->module(cell->type);
-				if (!box_module || !box_module->attributes.count("\\abc_box_id"))
-					continue;
+				log_assert(box_module);
+				log_assert(box_module->attributes.count("\\abc_box_id"));
 
-				if (box_module->attributes.count("\\abc_carry") && !abc_carry_modules.count(box_module)) {
+				if (!abc_carry_modules.count(box_module) && box_module->attributes.count("\\abc_carry")) {
 					RTLIL::Wire* carry_in = nullptr, *carry_out = nullptr;
 					RTLIL::Wire* last_in = nullptr, *last_out = nullptr;
 					for (const auto &port_name : box_module->ports) {
@@ -448,8 +443,6 @@ struct XAigerWriter
 				}
 				box_list.emplace_back(cell);
 			}
-
-			// TODO: Free memory from toposort, bit_drivers, bit_users
 		}
 
 		for (auto bit : input_bits) {