From f28b6aff40a65aa30a04b77cd51e6c0a346e739e Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Wed, 27 Feb 2013 16:27:20 +0100
Subject: [PATCH] Implemented basic functionality of "extract" pass

---
 kernel/sigtools.h          | 14 +++++++
 passes/extract/extract.cc  | 78 ++++++++++++++++++++++++++++++--------
 passes/opt/opt_rmunused.cc | 10 +++++
 3 files changed, 87 insertions(+), 15 deletions(-)

diff --git a/kernel/sigtools.h b/kernel/sigtools.h
index e76fd6023..e6c09331d 100644
--- a/kernel/sigtools.h
+++ b/kernel/sigtools.h
@@ -207,6 +207,20 @@ struct SigSet
 		find(sig, result);
 		return result;
 	}
+
+	bool has(RTLIL::SigSpec sig)
+	{
+		sig.expand();
+		for (auto &c : sig.chunks) {
+			if (c.wire == NULL)
+				continue;
+			assert(c.width == 1);
+			bitDef_t bit(c.wire, c.offset);
+			if (bits.count(bit))
+				return true;
+		}
+		return false;
+	}
 };
 
 struct SigMap
diff --git a/passes/extract/extract.cc b/passes/extract/extract.cc
index 0bf1b2a14..b80d6e889 100644
--- a/passes/extract/extract.cc
+++ b/passes/extract/extract.cc
@@ -48,6 +48,7 @@ namespace
 			return false;
 		}
 
+		// create graph nodes from cells
 		for (auto &cell_it : mod->cells)
 		{
 			RTLIL::Cell *cell = cell_it.second;
@@ -89,6 +90,7 @@ namespace
 			}
 		}
 
+		// mark external signals (used in non-selected cells)
 		for (auto &cell_it : mod->cells)
 		{
 			RTLIL::Cell *cell = cell_it.second;
@@ -107,25 +109,72 @@ namespace
 				}
 		}
 
+		// mark external signals (used in module ports)
 		for (auto &wire_it : mod->wires)
 		{
 			RTLIL::Wire *wire = wire_it.second;
 			if (wire->port_id > 0)
-				{
-					RTLIL::SigSpec conn_sig(wire);
-					sigmap.apply(conn_sig);
-					conn_sig.expand();
+			{
+				RTLIL::SigSpec conn_sig(wire);
+				sigmap.apply(conn_sig);
+				conn_sig.expand();
 
-					for (auto &chunk : conn_sig.chunks)
-						if (sig_bit_ref.count(chunk) != 0) {
-							bit_ref_t &bit_ref = sig_bit_ref[chunk];
-							graph.markExtern(bit_ref.cell, bit_ref.port, bit_ref.bit);
-						}
-				}
+				for (auto &chunk : conn_sig.chunks)
+					if (sig_bit_ref.count(chunk) != 0) {
+						bit_ref_t &bit_ref = sig_bit_ref[chunk];
+						graph.markExtern(bit_ref.cell, bit_ref.port, bit_ref.bit);
+					}
+			}
 		}
 
 		return true;
 	}
+
+	void replace(RTLIL::Module *needle, RTLIL::Module *haystack, SubCircuit::Solver::Result &match)
+	{
+		SigMap sigmap(needle);
+		SigSet<std::pair<std::string, int>> sig2port;
+
+		// create new cell
+		RTLIL::Cell *cell = new RTLIL::Cell;
+		cell->name = stringf("$extract$%s$%d", needle->name.c_str(), RTLIL::autoidx++);
+		cell->type = needle->name;
+		haystack->add(cell);
+
+		// create cell ports
+		for (auto &it : needle->wires) {
+			RTLIL::Wire *wire = it.second;
+			if (wire->port_id > 0) {
+				for (int i = 0; i < wire->width; i++)
+					sig2port.insert(sigmap(RTLIL::SigSpec(wire, 1, i)), std::pair<std::string, int>(wire->name, i));
+				cell->connections[wire->name] = RTLIL::SigSpec(RTLIL::State::Sz, wire->width);
+			}
+		}
+
+		// delete replaced cells and connect new ports
+		for (auto &it : match.mappings)
+		{
+			auto &mapping = it.second;
+			RTLIL::Cell *needle_cell = (RTLIL::Cell*)mapping.needleUserData;
+			RTLIL::Cell *haystack_cell = (RTLIL::Cell*)mapping.haystackUserData;
+
+			for (auto &conn : needle_cell->connections)
+				if (mapping.portMapping.count(conn.first) > 0 && sig2port.has(conn.second))
+				{
+					RTLIL::SigSpec sig = sigmap(conn.second);
+					sig.expand();
+
+					for (int i = 0; i < sig.width; i++)
+					for (auto &port : sig2port.find(sig.chunks[i])) {
+						RTLIL::SigSpec bitsig = haystack_cell->connections.at(mapping.portMapping[conn.first]).extract(i, 1);
+						cell->connections.at(port.first).replace(port.second, bitsig);
+					}
+				}
+
+			haystack->cells.erase(haystack_cell->name);
+			delete haystack_cell;
+		}
+	}
 }
 
 struct ExtractPass : public Pass {
@@ -199,21 +248,20 @@ struct ExtractPass : public Pass {
 			log_header("Substitute SubCircuits with cells.\n");
 
 			for (int i = 0; i < int(results.size()); i++) {
-				log("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str());
-				for (const auto & it : results[i].mappings) {
+				auto &result = results[i];
+				log("\nMatch #%d: (%s in %s)\n", i, result.needleGraphId.c_str(), result.haystackGraphId.c_str());
+				for (const auto &it : result.mappings) {
 					log("  %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str());
 					for (const auto & it2 : it.second.portMapping)
 						log(" %s:%s", it2.first.c_str(), it2.second.c_str());
 					log("\n");
 				}
+				replace(needle_map.at(result.needleGraphId), haystack_map.at(result.haystackGraphId), result);
 			}
 		}
 
 		delete map;
 		log_pop();
-
-		log("\n** UNFINISHED IMPLEMENTATION **\n");
-		log_cmd_error("TBD: Replace found subcircuits with cells.\n");
 	}
 } ExtractPass;
  
diff --git a/passes/opt/opt_rmunused.cc b/passes/opt/opt_rmunused.cc
index 29a6f2bc4..33c09f287 100644
--- a/passes/opt/opt_rmunused.cc
+++ b/passes/opt/opt_rmunused.cc
@@ -141,6 +141,16 @@ static void rmunused_module_signals(RTLIL::Module *module)
 				used_signals_nodrivers.add(it2.second);
 		}
 	}
+	for (auto &it : module->wires) {
+		RTLIL::Wire *wire = it.second;
+		if (wire->port_id > 0) {
+			RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
+			assign_map.apply(sig);
+			used_signals.add(sig);
+			if (!wire->port_input)
+				used_signals_nodrivers.add(sig);
+		}
+	}
 
 	std::vector<RTLIL::Wire*> del_wires;
 	for (auto &it : module->wires) {
-- 
2.30.2