From b1d6f05fa2156017f50383d01d49342c8ec5e209 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Sun, 24 Apr 2016 19:29:56 +0200
Subject: [PATCH] Fixed performance bug in proc_dlatch

---
 passes/proc/proc_dlatch.cc | 63 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 61 insertions(+), 2 deletions(-)

diff --git a/passes/proc/proc_dlatch.cc b/passes/proc/proc_dlatch.cc
index c339ac682..92bf8906d 100644
--- a/passes/proc/proc_dlatch.cc
+++ b/passes/proc/proc_dlatch.cc
@@ -33,6 +33,7 @@ struct proc_dlatch_db_t
 	Module *module;
 	SigMap sigmap;
 
+	dict<Cell*, vector<SigBit>> mux_srcbits;
 	dict<SigBit, pair<Cell*, int>> mux_drivers;
 	dict<SigBit, int> sigusers;
 
@@ -40,10 +41,24 @@ struct proc_dlatch_db_t
 	{
 		for (auto cell : module->cells())
 		{
-			if (cell->type.in("$mux", "$pmux")) {
+			if (cell->type.in("$mux", "$pmux"))
+			{
 				auto sig_y = sigmap(cell->getPort("\\Y"));
 				for (int i = 0; i < GetSize(sig_y); i++)
 					mux_drivers[sig_y[i]] = pair<Cell*, int>(cell, i);
+
+				pool<SigBit> mux_srcbits_pool;
+				for (auto bit : sigmap(cell->getPort("\\A")))
+					mux_srcbits_pool.insert(bit);
+				for (auto bit : sigmap(cell->getPort("\\B")))
+					mux_srcbits_pool.insert(bit);
+
+				vector<SigBit> mux_srcbits_vec;
+				for (auto bit : mux_srcbits_pool)
+					if (bit.wire != nullptr)
+						mux_srcbits_vec.push_back(bit);
+
+				mux_srcbits[cell].swap(mux_srcbits_vec);
 			}
 
 			for (auto &conn : cell->connections())
@@ -58,6 +73,42 @@ struct proc_dlatch_db_t
 					sigusers[bit]++;
 	}
 
+	bool quickcheck(const SigSpec &haystack, const SigSpec &needle)
+	{
+		pool<SigBit> haystack_bits = sigmap(haystack).to_sigbit_pool();
+		pool<SigBit> needle_bits = sigmap(needle).to_sigbit_pool();
+
+		pool<Cell*> cells_queue, cells_visited;
+		pool<SigBit> bits_queue, bits_visited;
+
+		bits_queue = haystack_bits;
+		while (!bits_queue.empty())
+		{
+			for (auto &bit : bits_queue) {
+				auto it = mux_drivers.find(bit);
+				if (it != mux_drivers.end())
+					if (!cells_visited.count(it->second.first))
+						cells_queue.insert(it->second.first);
+				bits_visited.insert(bit);
+			}
+
+			bits_queue.clear();
+
+			for (auto c : cells_queue) {
+				for (auto bit : mux_srcbits[c]) {
+					if (needle_bits.count(bit))
+						return true;
+					if (!bits_visited.count(bit))
+						bits_queue.insert(bit);
+				}
+			}
+
+			cells_queue.clear();
+		}
+
+		return false;
+	}
+
 	struct rule_node_t
 	{
 		// a node is true if "signal" equals "match" and [any
@@ -218,9 +269,17 @@ void proc_dlatch(proc_dlatch_db_t &db, RTLIL::Process *proc)
 			continue;
 		}
 
-		for (auto ss : sr->actions) {
+		for (auto ss : sr->actions)
+		{
 			db.sigmap.apply(ss.first);
 			db.sigmap.apply(ss.second);
+
+			if (!db.quickcheck(ss.second, ss.first)) {
+				nolatches_bits.first.append(ss.first);
+				nolatches_bits.second.append(ss.second);
+				continue;
+			}
+
 			for (int i = 0; i < GetSize(ss.first); i++)
 				latches_out_in[ss.first[i]] = ss.second[i];
 		}
-- 
2.30.2