flowmap: cleanup for clarity. NFCI.

1 files changed, 141 insertions, 107 deletions

diff --git a/passes/techmap/flowmap.cc b/passes/techmap/flowmap.cc
index 5d6b8b645..1b53de4db 100644
--- a/passes/techmap/flowmap.cc
+++ b/passes/techmap/flowmap.cc
@@ -402,29 +402,34 @@ struct FlowGraph
 struct FlowmapWorker
 {
 	int order;
-	pool<IdString> cell_types;
 	bool debug;
 
 	RTLIL::Module *module;
 	SigMap sigmap;
 	ModIndex index;
-	pool<RTLIL::Cell*> cells;
+
+	dict<RTLIL::SigBit, ModIndex::PortInfo> node_origins;
 
 	pool<RTLIL::SigBit> nodes, inputs, outputs;
 	dict<RTLIL::SigBit, pool<RTLIL::SigBit>> edges_fw, edges_bw;
 	dict<RTLIL::SigBit, int> labels;
 
-	dict<RTLIL::SigBit, pool<RTLIL::SigBit>> lut_gates, lut_inputs;
+	pool<RTLIL::SigBit> lut_nodes;
+	dict<RTLIL::SigBit, pool<RTLIL::SigBit>> lut_gates;
+	dict<RTLIL::SigBit, pool<RTLIL::SigBit>> lut_edges_fw, lut_edges_bw;
 
-	dict<RTLIL::SigBit, ModIndex::PortInfo> node_origins;
-	dict<RTLIL::Cell*, pool<RTLIL::SigBit>> cell_fanout;
+	int gate_count = 0, lut_count = 0, packed_count = 0;
+	int gate_area = 0, lut_area = 0;
 
-	int mapped_count = 0, packed_count = 0, unique_packed_count = 0;
+	enum class GraphMode {
+		Label,
+		Cut,
+	};
 
-	void dump_dot_graph(string filename,
+	void dump_dot_graph(string filename, GraphMode mode,
 	                    pool<RTLIL::SigBit> subgraph_nodes = {}, dict<RTLIL::SigBit, pool<RTLIL::SigBit>> subgraph_edges = {},
-	                    pair<pool<RTLIL::SigBit>, pool<RTLIL::SigBit>> cut = {},
-	                    dict<RTLIL::SigBit, pool<RTLIL::SigBit>> collapsed = {})
+	                    dict<RTLIL::SigBit, pool<RTLIL::SigBit>> collapsed = {},
+	                    pair<pool<RTLIL::SigBit>, pool<RTLIL::SigBit>> cut = {})
 	{
 		if (subgraph_nodes.empty())
 			subgraph_nodes = nodes;
@@ -436,26 +441,29 @@ struct FlowmapWorker
 			for (auto collapsed_node : collapsed[node])
 				if (collapsed_node != node)
 					label += stringf(" %s", log_signal(collapsed_node));
-			if (labels[node] == -1)
-				label += "\nl=?";
-			else
-				label += stringf("\nl=%d", labels[node]);
-			if (cut.first.empty() && cut.second.empty())
+			switch (mode)
 			{
-				if (labels[node] == -1)
+				case GraphMode::Label:
+					if (labels[node] == -1)
+					{
+						label += "\nl=?";
+						return GraphStyle{label};
+					}
+					else
+					{
+						label += stringf("\nl=%d", labels[node]);
+						string fillcolor = stringf("/set311/%d", 1 + labels[node] % 11);
+						return GraphStyle{label, "", fillcolor};
+					}
+
+				case GraphMode::Cut:
+					if (cut.first[node])
+						return GraphStyle{label, "blue"};
+					if (cut.second[node])
+						return GraphStyle{label, "red"};
 					return GraphStyle{label};
-				string fillcolor = stringf("/set311/%d", 1 + labels[node] % 11);
-				return GraphStyle{label, "", fillcolor};
-			}
-			else
-			{
-				string color = "black";
-				if (cut.first[node])
-					color = "blue";
-				if (cut.second[node])
-					color = "red";
-				return GraphStyle{label, color};
 			}
+			return GraphStyle{label};
 		};
 		auto edge_style = [&](RTLIL::SigBit, RTLIL::SigBit) {
 			return GraphStyle{};
@@ -519,57 +527,56 @@ struct FlowmapWorker
 		return flow_graph;
 	}
 
-	FlowmapWorker(int order, pool<IdString> cell_types, bool debug, RTLIL::Module *module) :
-		order(order), cell_types(cell_types), debug(debug), module(module), sigmap(module), index(module)
+	void discover_nodes(pool<IdString> cell_types)
 	{
-		log("Labeling cells.\n");
 		for (auto cell : module->selected_cells())
 		{
-			if (cell_types[cell->type])
+			if (!cell_types[cell->type])
+				continue;
+
+			if (!cell->known())
+				log_error("Cell %s (%s.%s) is unknown.\n", cell->type.c_str(), log_id(module), log_id(cell));
+
+			pool<RTLIL::SigBit> fanout;
+			for (auto conn : cell->connections())
 			{
-				if (!cell->known())
+				if (!cell->output(conn.first)) continue;
+				int offset = -1;
+				for (auto bit : conn.second)
 				{
-					log_error("Cell %s (%s.%s) is unknown.\n", cell->type.c_str(), log_id(module), log_id(cell));
+					offset++;
+					if (!bit.wire) continue;
+					auto mapped_bit = sigmap(bit);
+					if (nodes[mapped_bit])
+						log_error("Multiple drivers found for wire %s.\n", log_signal(mapped_bit));
+					nodes.insert(mapped_bit);
+					node_origins[mapped_bit] = ModIndex::PortInfo(cell, conn.first, offset);
+					fanout.insert(mapped_bit);
 				}
-				cells.insert(cell);
+			}
 
-				for (auto conn : cell->connections())
+			int fanin = 0;
+			for (auto conn : cell->connections())
+			{
+				if (!cell->input(conn.first)) continue;
+				for (auto bit : sigmap(conn.second))
 				{
-					if (!cell->output(conn.first)) continue;
-					int offset = -1;
-					for (auto bit : conn.second)
+					if (!bit.wire) continue;
+					for (auto fanout_bit : fanout)
 					{
-						offset++;
-						if (!bit.wire) continue;
-						auto mapped_bit = sigmap(bit);
-						if (nodes[mapped_bit])
-							log_error("Multiple drivers found for wire %s.\n", log_signal(mapped_bit));
-						nodes.insert(mapped_bit);
-						node_origins[mapped_bit] = ModIndex::PortInfo(cell, conn.first, offset);
-						cell_fanout[cell].insert(mapped_bit);
+						edges_fw[bit].insert(fanout_bit);
+						edges_bw[fanout_bit].insert(bit);
 					}
+					fanin++;
 				}
+			}
 
-				int fanin = 0;
-				for (auto conn : cell->connections())
-				{
-					if (!cell->input(conn.first)) continue;
-					for (auto bit : sigmap(conn.second))
-					{
-						if (!bit.wire) continue;
-						for (auto fanout_bit : cell_fanout[cell])
-						{
-							edges_fw[bit].insert(fanout_bit);
-							edges_bw[fanout_bit].insert(bit);
-						}
-						fanin++;
-					}
-				}
+			if (fanin > order)
+				log_error("Cell %s (%s.%s) with fan-in %d cannot be mapped to a %d-LUT.\n",
+				          cell->type.c_str(), log_id(module), log_id(cell), fanin, order);
 
-				if (fanin > order)
-					log_error("Cell %s (%s.%s) with fan-in %d cannot be mapped to a %d-LUT.\n",
-					          cell->type.c_str(), log_id(module), log_id(cell), fanin, order);
-			}
+			gate_count++;
+			gate_area += 1 << fanin;
 		}
 
 		for (auto edge : edges_fw)
@@ -591,15 +598,23 @@ struct FlowmapWorker
 					outputs.insert(node);
 		}
 
+		if (debug)
+		{
+			dump_dot_graph("flowmap-initial.dot", GraphMode::Label);
+			log("Dumped initial graph to `flowmap-initial.dot`.\n");
+		}
+	}
+
+	void label_nodes()
+	{
 		for (auto node : nodes)
 			labels[node] = -1;
 		for (auto input : inputs)
-			labels[input] = 0;
-
-		if (debug)
 		{
-			dump_dot_graph("flowmap-initial.dot");
-			log("Dumped complete initial graph to `flowmap-initial.dot`.\n");
+			if (input.wire->attributes.count("\\$flowmap_level"))
+				labels[input] = input.wire->attributes["\\$flowmap_level"].as_int();
+			else
+				labels[input] = 0;
 		}
 
 		pool<RTLIL::SigBit> worklist = nodes;
@@ -661,70 +676,73 @@ struct FlowmapWorker
 						k.insert(xi_node_pred);
 			}
 			log_assert((int)k.size() <= order);
-			lut_inputs[sink] = k;
+			lut_edges_bw[sink] = k;
+			for (auto k_node : k)
+				lut_edges_fw[k_node].insert(sink);
 
 			if (debug)
 			{
 				log("  Maximum flow: %d. Assigned label %d.\n", flow, labels[sink]);
-				dump_dot_graph(stringf("flowmap-%d-sub.dot", debug_num), subgraph, {}, {x, xi});
+				dump_dot_graph(stringf("flowmap-%d-sub.dot", debug_num), GraphMode::Cut, subgraph, {}, {}, {x, xi});
 				log("  Dumped subgraph to `flowmap-%d-sub.dot`.\n", debug_num);
 				flow_graph.dump_dot_graph(stringf("flowmap-%d-flow.dot", debug_num));
 				log("  Dumped flow graph to `flowmap-%d-flow.dot`.\n", debug_num);
-				log("    LUT packed:");
-				for (auto xi_node : xi)
-					log(" %s", log_signal(xi_node));
-				log(".\n");
 				log("    LUT inputs:");
 				for (auto k_node : k)
 					log(" %s", log_signal(k_node));
 				log(".\n");
+				log("    LUT packed gates:");
+				for (auto xi_node : xi)
+					log(" %s", log_signal(xi_node));
+				log(".\n");
 			}
 
 			for (auto sink_succ : edges_fw[sink])
 				worklist.insert(sink_succ);
 		}
 
-		int depth = 0;
-		for (auto label : labels)
-			depth = max(depth, label.second);
-		log("Maximum depth: %d levels.\n", depth);
-
 		if (debug)
 		{
-			dump_dot_graph("flowmap-labeled.dot");
-			log("Dumped complete labeled graph to `flowmap-labeled.dot`.\n");
+			dump_dot_graph("flowmap-labeled.dot", GraphMode::Label);
+			log("Dumped labeled graph to `flowmap-labeled.dot`.\n");
 		}
+	}
 
-		pool<RTLIL::SigBit> lut_nodes;
-		dict<RTLIL::SigBit, pool<RTLIL::SigBit>> lut_edges;
-		worklist = outputs;
+	int pack_luts()
+	{
+		pool<RTLIL::SigBit> worklist = outputs;
 		while (!worklist.empty())
 		{
 			auto lut_node = worklist.pop();
 			lut_nodes.insert(lut_node);
-			for (auto input_node : lut_inputs[lut_node])
-			{
-				lut_edges[input_node].insert(lut_node);
+			for (auto input_node : lut_edges_bw[lut_node])
 				if (!lut_nodes[input_node] && !inputs[input_node])
 					worklist.insert(input_node);
-			}
 		}
 
+		int depth = 0;
+		for (auto label : labels)
+			depth = max(depth, label.second);
+		log("Solved to %d LUTs in %d levels.\n", (int)lut_nodes.size(), depth);
+
 		if (debug)
 		{
-			pool<RTLIL::SigBit> lut_and_input_nodes = lut_nodes;
+			pool<RTLIL::SigBit> lut_and_input_nodes;
+			lut_and_input_nodes.insert(lut_nodes.begin(), lut_nodes.end());
 			lut_and_input_nodes.insert(inputs.begin(), inputs.end());
-			dump_dot_graph("flowmap-packed.dot", lut_and_input_nodes, lut_edges, {}, lut_gates);
-			log("Dumped complete packed graph to `flowmap-packed.dot`.\n");
+			dump_dot_graph("flowmap-packed.dot", GraphMode::Label, lut_and_input_nodes, lut_edges_fw, lut_gates);
+			log("Dumped packed graph to `flowmap-packed.dot`.\n");
 		}
 
+		return depth;
+	}
+
+	void map_cells()
+	{
 		ConstEval ce(module);
 		for (auto input_node : inputs)
 			ce.stop(input_node);
 
-		log("\n");
-		log("Mapping cells.\n");
-
 		pool<RTLIL::SigBit> mapped_nodes;
 		for (auto node : lut_nodes)
 		{
@@ -759,7 +777,7 @@ struct FlowmapWorker
 					    log_id(module), log_id(gate_origin.cell), gate_origin.port.c_str(), gate_origin.offset, log_signal(gate_node));
 			}
 
-			vector<RTLIL::SigBit> input_nodes(lut_inputs[node].begin(), lut_inputs[node].end());
+			vector<RTLIL::SigBit> input_nodes(lut_edges_bw[node].begin(), lut_edges_bw[node].end());
 			RTLIL::Const lut_table(State::Sx, 1 << input_nodes.size());
 			for (unsigned i = 0; i < (1 << input_nodes.size()); i++)
 			{
@@ -786,7 +804,6 @@ struct FlowmapWorker
 				lut_a.append_bit(input_node);
 
 			RTLIL::Cell *lut = module->addLut(NEW_ID, lut_a, lut_y, lut_table);
-			mapped_count++;
 			mapped_nodes.insert(node);
 			for (auto gate_node : lut_gates[node])
 			{
@@ -794,11 +811,11 @@ struct FlowmapWorker
 				lut->add_strpool_attribute("\\src", gate_origin.cell->get_strpool_attribute("\\src"));
 				packed_count++;
 			}
+			lut_count++;
+			lut_area += 1 << input_nodes.size();
 			log("  Packed into a %d-LUT %s.%s.\n", (int)input_nodes.size(), log_id(module), log_id(lut));
 		}
 
-		unique_packed_count += nodes.size();
-
 		for (auto node : mapped_nodes)
 		{
 			auto origin = node_origins[node];
@@ -807,6 +824,19 @@ struct FlowmapWorker
 			origin.cell->setPort(origin.port, driver);
 		}
 	}
+
+	FlowmapWorker(int order, pool<IdString> cell_types, bool debug, RTLIL::Module *module) :
+		order(order), debug(debug), module(module), sigmap(module), index(module)
+	{
+		log("Labeling cells.\n");
+		discover_nodes(cell_types);
+		label_nodes();
+		pack_luts();
+
+		log("\n");
+		log("Mapping cells.\n");
+		map_cells();
+	}
 };
 
 static void split(std::vector<std::string> &tokens, const std::string &text, char sep)
@@ -832,7 +862,7 @@ struct FlowmapPass : public Pass {
 		log("be evaluated with the `eval` pass, including cells with multiple output ports\n");
 		log("and multi-bit input and output ports.\n");
 		log("\n");
-		log("    -maxlut <k>\n");
+		log("    -maxlut k\n");
 		log("        perform technology mapping for a k-LUT architecture. if not specified,\n");
 		log("        defaults to 3.\n");
 		log("\n");
@@ -846,8 +876,6 @@ struct FlowmapPass : public Pass {
 	}
 	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 	{
-		log_header(design, "Executing FLOWMAP pass (pack LUTs with FlowMap).\n");
-
 		int order = 3;
 		vector<string> cells;
 		bool debug = false;
@@ -885,18 +913,24 @@ struct FlowmapPass : public Pass {
 			cell_types = {"$_NOT_", "$_AND_", "$_OR_", "$_XOR_", "$_MUX_"};
 		}
 
-		int mapped_count = 0, packed_count = 0, unique_packed_count = 0;
+		log_header(design, "Executing FLOWMAP pass (pack LUTs with FlowMap).\n");
+
+		int gate_count = 0, lut_count = 0, packed_count = 0;
+		int gate_area = 0, lut_area = 0;
 		for (auto module : design->selected_modules())
 		{
 			FlowmapWorker worker(order, cell_types, debug, module);
-			mapped_count += worker.mapped_count;
+			gate_count += worker.gate_count;
+			lut_count += worker.lut_count;
 			packed_count += worker.packed_count;
-			unique_packed_count += worker.unique_packed_count;
+			gate_area += worker.gate_area;
+			lut_area += worker.lut_area;
 		}
 
 		log("\n");
-		log("Mapped %d LUTs.\n", mapped_count);
-		log("Packed %d cells %d times.\n", unique_packed_count, packed_count);
+		log("Mapped %d LUTs.\n", lut_count);
+		log("Packed %d cells; duplicated %d cells.\n", packed_count, packed_count - gate_count);
+		log("Solution has %.1f%% area overhead.\n", (lut_area - gate_area) * 100.0 / gate_area);
 	}
 } FlowmapPass;