From cfe0817697c9e7a656fd3a64e3a9014fa86e78d0 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Mon, 29 Dec 2014 02:01:42 +0100
Subject: [PATCH] Converting "share" to dict<> and pool<> complete

---
 kernel/hashlib.h    | 11 +++++++
 kernel/rtlil.h      | 11 +++++--
 passes/opt/share.cc | 76 +++++++++++++++++++++++++--------------------
 3 files changed, 62 insertions(+), 36 deletions(-)

diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index 021cc66ee..4e8c00026 100644
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -76,6 +76,17 @@ template<> struct hash_ops<std::string> {
 	}
 };
 
+template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
+	bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) const {
+		return a == b;
+	}
+	unsigned int hash(std::pair<P, Q> a) const {
+		hash_ops<P> p_ops;
+		hash_ops<Q> q_ops;
+		return mkhash(p_ops.hash(a.first), q_ops.hash(a.second));
+	}
+};
+
 struct hash_cstr_ops {
 	bool cmp(const char *a, const char *b) const {
 		for (int i = 0; a[i] || b[i]; i++)
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index 5bca060f4..25477d02e 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -219,8 +219,8 @@ namespace RTLIL
 			return index_;
 		}
 
-		// The following is a helper key_compare class. Instead of for example pool<Cell*>
-		// use pool<Cell*, IdString::compare_ptr_by_name<Cell>> if the order of cells in the
+		// The following is a helper key_compare class. Instead of for example std::set<Cell*>
+		// use std::set<Cell*, IdString::compare_ptr_by_name<Cell>> if the order of cells in the
 		// set has an influence on the algorithm.
 
 		template<typename T> struct compare_ptr_by_name {
@@ -450,6 +450,13 @@ struct RTLIL::Const
 	std::string decode_string() const;
 
 	inline int size() const { return bits.size(); }
+
+	inline unsigned int hash() const {
+		unsigned int h = 5381;
+		for (auto b : bits)
+			mkhash(h, b);
+		return h;
+	}
 };
 
 struct RTLIL::SigChunk
diff --git a/passes/opt/share.cc b/passes/opt/share.cc
index 2a81a63f5..e2c31bec5 100644
--- a/passes/opt/share.cc
+++ b/passes/opt/share.cc
@@ -28,6 +28,7 @@ USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
 
 typedef RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell> cell_ptr_cmp;
+typedef std::pair<RTLIL::SigSpec, RTLIL::Const> ssc_pair_t;
 
 struct ShareWorkerConfig
 {
@@ -35,7 +36,7 @@ struct ShareWorkerConfig
 	bool opt_force;
 	bool opt_aggressive;
 	bool opt_fast;
-	std::set<RTLIL::IdString> generic_uni_ops, generic_bin_ops, generic_cbin_ops, generic_other_ops;
+	pool<RTLIL::IdString> generic_uni_ops, generic_bin_ops, generic_cbin_ops, generic_other_ops;
 };
 
 struct ShareWorker
@@ -50,8 +51,8 @@ struct ShareWorker
 	ModWalker modwalker;
 	ModIndex mi;
 
-	std::set<RTLIL::Cell*> cells_to_remove;
-	std::set<RTLIL::Cell*> recursion_state;
+	pool<RTLIL::Cell*> cells_to_remove;
+	pool<RTLIL::Cell*> recursion_state;
 
 	SigMap topo_sigmap;
 	std::map<RTLIL::Cell*, std::set<RTLIL::Cell*, cell_ptr_cmp>, cell_ptr_cmp> topo_cell_drivers;
@@ -64,11 +65,11 @@ struct ShareWorker
 	// Find terminal bits -- i.e. bits that do not (exclusively) feed into a mux tree
 	// ------------------------------------------------------------------------------
 
-	std::set<RTLIL::SigBit> terminal_bits;
+	pool<RTLIL::SigBit> terminal_bits;
 
 	void find_terminal_bits()
 	{
-		std::set<RTLIL::SigBit> queue_bits;
+		pool<RTLIL::SigBit> queue_bits;
 		pool<RTLIL::Cell*> visited_cells;
 
 		queue_bits.insert(modwalker.signal_outputs.begin(), modwalker.signal_outputs.end());
@@ -718,12 +719,12 @@ struct ShareWorker
 	// Finding forbidden control inputs for a cell
 	// -------------------------------------------
 
-	dict<RTLIL::Cell*, std::set<RTLIL::SigBit>> forbidden_controls_cache;
+	std::map<RTLIL::Cell*, pool<RTLIL::SigBit>, cell_ptr_cmp> forbidden_controls_cache;
 
-	const std::set<RTLIL::SigBit> &find_forbidden_controls(RTLIL::Cell *cell)
+	const pool<RTLIL::SigBit> &find_forbidden_controls(RTLIL::Cell *cell)
 	{
 		if (recursion_state.count(cell)) {
-			static std::set<RTLIL::SigBit> empty_controls_set;
+			static pool<RTLIL::SigBit> empty_controls_set;
 			return empty_controls_set;
 		}
 
@@ -745,7 +746,7 @@ struct ShareWorker
 
 		for (auto c : consumer_cells)
 			if (fwd_ct.cell_known(c->type)) {
-				const std::set<RTLIL::SigBit> &bits = find_forbidden_controls(c);
+				const pool<RTLIL::SigBit> &bits = find_forbidden_controls(c);
 				forbidden_controls_cache[cell].insert(bits.begin(), bits.end());
 			}
 
@@ -760,10 +761,9 @@ struct ShareWorker
 	// Finding control inputs and activation pattern for a cell
 	// --------------------------------------------------------
 
-	// FIXME: For some reasone this must be std::map<> and not dict<>
-	std::map<RTLIL::Cell*, std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>>> activation_patterns_cache;
+	std::map<RTLIL::Cell*, pool<ssc_pair_t>, cell_ptr_cmp> activation_patterns_cache;
 
-	bool sort_check_activation_pattern(std::pair<RTLIL::SigSpec, RTLIL::Const> &p)
+	bool sort_check_activation_pattern(ssc_pair_t &p)
 	{
 		std::map<RTLIL::SigBit, RTLIL::State> p_bits;
 
@@ -787,16 +787,16 @@ struct ShareWorker
 		return true;
 	}
 
-	void optimize_activation_patterns(std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> & /* patterns */)
+	void optimize_activation_patterns(pool<ssc_pair_t> & /* patterns */)
 	{
 		// TODO: Remove patterns that are contained in other patterns
 		// TODO: Consolidate pairs of patterns that only differ in the value for one signal bit
 	}
 
-	const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &find_cell_activation_patterns(RTLIL::Cell *cell, const char *indent)
+	const pool<ssc_pair_t> &find_cell_activation_patterns(RTLIL::Cell *cell, const char *indent)
 	{
 		if (recursion_state.count(cell)) {
-			static std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> empty_patterns_set;
+			static pool<ssc_pair_t> empty_patterns_set;
 			return empty_patterns_set;
 		}
 
@@ -810,7 +810,7 @@ struct ShareWorker
 		{
 			if (terminal_bits.count(bit)) {
 				// Terminal cells are always active: unconditional activation pattern
-				activation_patterns_cache[cell].insert(std::pair<RTLIL::SigSpec, RTLIL::Const>());
+				activation_patterns_cache[cell].insert(ssc_pair_t());
 				return activation_patterns_cache.at(cell);
 			}
 			for (auto &pbit : modwalker.signal_consumers[bit]) {
@@ -826,7 +826,7 @@ struct ShareWorker
 
 		for (auto c : driven_data_muxes)
 		{
-			const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &c_patterns = find_cell_activation_patterns(c, indent);
+			const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 
 			bool used_in_a = false;
 			std::set<int> used_in_b_parts;
@@ -861,7 +861,7 @@ struct ShareWorker
 		}
 
 		for (auto c : driven_cells) {
-			const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &c_patterns = find_cell_activation_patterns(c, indent);
+			const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 			activation_patterns_cache[cell].insert(c_patterns.begin(), c_patterns.end());
 		}
 
@@ -879,7 +879,7 @@ struct ShareWorker
 		return activation_patterns_cache[cell];
 	}
 
-	RTLIL::SigSpec bits_from_activation_patterns(const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &activation_patterns)
+	RTLIL::SigSpec bits_from_activation_patterns(const pool<ssc_pair_t> &activation_patterns)
 	{
 		std::set<RTLIL::SigBit> all_bits;
 		for (auto &it : activation_patterns) {
@@ -894,13 +894,13 @@ struct ShareWorker
 		return signal;
 	}
 
-	void filter_activation_patterns(std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &out,
-			const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &in, const std::set<RTLIL::SigBit> &filter_bits)
+	void filter_activation_patterns(pool<ssc_pair_t> &out,
+			const pool<ssc_pair_t> &in, const std::set<RTLIL::SigBit> &filter_bits)
 	{
 		for (auto &p : in)
 		{
 			std::vector<RTLIL::SigBit> p_first = p.first;
-			std::pair<RTLIL::SigSpec, RTLIL::Const> new_p;
+			ssc_pair_t new_p;
 
 			for (int i = 0; i < GetSize(p_first); i++)
 				if (filter_bits.count(p_first[i]) == 0) {
@@ -912,7 +912,7 @@ struct ShareWorker
 		}
 	}
 
-	RTLIL::SigSpec make_cell_activation_logic(const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &activation_patterns, pool<RTLIL::Cell*> &supercell_aux)
+	RTLIL::SigSpec make_cell_activation_logic(const pool<ssc_pair_t> &activation_patterns, pool<RTLIL::Cell*> &supercell_aux)
 	{
 		RTLIL::Wire *all_cases_wire = module->addWire(NEW_ID, 0);
 
@@ -1050,6 +1050,14 @@ struct ShareWorker
 	// Setup and run
 	// -------------
 
+	void remove_cell(Cell *cell)
+	{
+		shareable_cells.erase(cell);
+		forbidden_controls_cache.erase(cell);
+		activation_patterns_cache.erase(cell);
+		module->remove(cell);
+	}
+
 	ShareWorker(ShareWorkerConfig config, RTLIL::Design *design, RTLIL::Module *module) :
 			config(config), design(design), module(module), mi(module)
 	{
@@ -1097,7 +1105,7 @@ struct ShareWorker
 
 			log("  Analyzing resource sharing options for %s:\n", log_id(cell));
 
-			const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &cell_activation_patterns = find_cell_activation_patterns(cell, "    ");
+			const pool<ssc_pair_t> &cell_activation_patterns = find_cell_activation_patterns(cell, "    ");
 			RTLIL::SigSpec cell_activation_signals = bits_from_activation_patterns(cell_activation_patterns);
 
 			if (cell_activation_patterns.empty()) {
@@ -1106,7 +1114,7 @@ struct ShareWorker
 				continue;
 			}
 
-			if (cell_activation_patterns.count(std::pair<RTLIL::SigSpec, RTLIL::Const>())) {
+			if (cell_activation_patterns.count(ssc_pair_t())) {
 				log("    Cell is always active. Therefore no sharing is possible.\n");
 				continue;
 			}
@@ -1130,7 +1138,7 @@ struct ShareWorker
 			{
 				log("    Analyzing resource sharing with %s:\n", log_id(other_cell));
 
-				const std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> &other_cell_activation_patterns = find_cell_activation_patterns(other_cell, "      ");
+				const pool<ssc_pair_t> &other_cell_activation_patterns = find_cell_activation_patterns(other_cell, "      ");
 				RTLIL::SigSpec other_cell_activation_signals = bits_from_activation_patterns(other_cell_activation_patterns);
 
 				if (other_cell_activation_patterns.empty()) {
@@ -1140,7 +1148,7 @@ struct ShareWorker
 					continue;
 				}
 
-				if (other_cell_activation_patterns.count(std::pair<RTLIL::SigSpec, RTLIL::Const>())) {
+				if (other_cell_activation_patterns.count(ssc_pair_t())) {
 					log("      Cell is always active. Therefore no sharing is possible.\n");
 					shareable_cells.erase(other_cell);
 					continue;
@@ -1149,8 +1157,8 @@ struct ShareWorker
 				log("      Found %d activation_patterns using ctrl signal %s.\n",
 						GetSize(other_cell_activation_patterns), log_signal(other_cell_activation_signals));
 
-				const std::set<RTLIL::SigBit> &cell_forbidden_controls = find_forbidden_controls(cell);
-				const std::set<RTLIL::SigBit> &other_cell_forbidden_controls = find_forbidden_controls(other_cell);
+				const pool<RTLIL::SigBit> &cell_forbidden_controls = find_forbidden_controls(cell);
+				const pool<RTLIL::SigBit> &other_cell_forbidden_controls = find_forbidden_controls(other_cell);
 
 				std::set<RTLIL::SigBit> union_forbidden_controls;
 				union_forbidden_controls.insert(cell_forbidden_controls.begin(), cell_forbidden_controls.end());
@@ -1159,8 +1167,8 @@ struct ShareWorker
 				if (!union_forbidden_controls.empty())
 					log("      Forbidden control signals for this pair of cells: %s\n", log_signal(union_forbidden_controls));
 
-				std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> filtered_cell_activation_patterns;
-				std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> filtered_other_cell_activation_patterns;
+				pool<ssc_pair_t> filtered_cell_activation_patterns;
+				pool<ssc_pair_t> filtered_other_cell_activation_patterns;
 
 				filter_activation_patterns(filtered_cell_activation_patterns, cell_activation_patterns, union_forbidden_controls);
 				filter_activation_patterns(filtered_other_cell_activation_patterns, other_cell_activation_patterns, union_forbidden_controls);
@@ -1305,11 +1313,11 @@ struct ShareWorker
 					cells_to_remove.erase(other_cell);
 					shareable_cells.insert(other_cell);
 					for (auto cc : supercell_aux)
-						module->remove(cc);
+						remove_cell(cc);
 					continue;
 				}
 
-				std::set<std::pair<RTLIL::SigSpec, RTLIL::Const>> supercell_activation_patterns;
+				pool<ssc_pair_t> supercell_activation_patterns;
 				supercell_activation_patterns.insert(filtered_cell_activation_patterns.begin(), filtered_cell_activation_patterns.end());
 				supercell_activation_patterns.insert(filtered_other_cell_activation_patterns.begin(), filtered_other_cell_activation_patterns.end());
 				optimize_activation_patterns(supercell_activation_patterns);
@@ -1337,7 +1345,7 @@ struct ShareWorker
 			log("Removing %d cells in module %s:\n", GetSize(cells_to_remove), log_id(module));
 			for (auto c : cells_to_remove) {
 				log("  Removing cell %s (%s).\n", log_id(c), log_id(c->type));
-				module->remove(c);
+				remove_cell(c);
 			}
 		}
 
-- 
2.30.2