More dict/pool related changes

6 files changed, 77 insertions, 54 deletions

diff --git a/kernel/hashmap.h b/kernel/hashmap.h
index 729b4916..431e8122 100644
--- a/kernel/hashmap.h
+++ b/kernel/hashmap.h
@@ -25,10 +25,18 @@
 
 #define YOSYS_HASHTABLE_SIZE_FACTOR 3
 
+// The XOR version of DJB2
+// (traditionally 5381 is used as starting value for the djb2 hash)
 inline unsigned int mkhash(unsigned int a, unsigned int b) {
 	return ((a << 5) + a) ^ b;
 }
 
+// The ADD version of DJB2
+// (use this version as last call for cache locality in b)
+inline unsigned int mkhash_add(unsigned int a, unsigned int b) {
+	return ((a << 5) + a) + b;
+}
+
 template<typename T> struct hash_ops {
 	bool cmp(const T &a, const T &b) const {
 		return a == b;
diff --git a/kernel/modtools.h b/kernel/modtools.h
index e3020ae3..439699ea 100644
--- a/kernel/modtools.h
+++ b/kernel/modtools.h
@@ -33,6 +33,7 @@ struct ModIndex : public RTLIL::Monitor
 		RTLIL::IdString port;
 		int offset;
 
+		PortInfo() : cell(), port(), offset() { }
 		PortInfo(RTLIL::Cell* _c, RTLIL::IdString _p, int _o) : cell(_c), port(_p), offset(_o) { }
 
 		bool operator<(const PortInfo &other) const {
@@ -42,19 +43,27 @@ struct ModIndex : public RTLIL::Monitor
 				return offset < other.offset;
 			return port < other.port;
 		}
+
+		bool operator==(const PortInfo &other) const {
+			return cell == other.cell && port == other.port && offset == other.offset;
+		}
+
+		unsigned int hash() const {
+			return mkhash_add(mkhash(cell->name.hash(), port.hash()), offset);
+		}
 	};
 
 	struct SigBitInfo
 	{
 		bool is_input, is_output;
-		std::set<PortInfo> ports;
+		pool<PortInfo> ports;
 
 		SigBitInfo() : is_input(false), is_output(false) { }
 	};
 
 	SigMap sigmap;
 	RTLIL::Module *module;
-	std::map<RTLIL::SigBit, SigBitInfo> database;
+	dict<RTLIL::SigBit, SigBitInfo> database;
 	bool auto_reload_module;
 
 	void port_add(RTLIL::Cell *cell, RTLIL::IdString port, const RTLIL::SigSpec &sig)
@@ -168,9 +177,9 @@ struct ModIndex : public RTLIL::Monitor
 		return info->is_output;
 	}
 
-	std::set<PortInfo> &query_ports(RTLIL::SigBit bit)
+	pool<PortInfo> &query_ports(RTLIL::SigBit bit)
 	{
-		static std::set<PortInfo> empty_result_set;
+		static pool<PortInfo> empty_result_set;
 		SigBitInfo *info = query(bit);
 		if (info == nullptr)
 			return empty_result_set;
@@ -193,6 +202,14 @@ struct ModWalker
 				return port < other.port;
 			return offset < other.offset;
 		}
+
+		bool operator==(const PortBit &other) const {
+			return cell == other.cell && port == other.port && offset == other.offset;
+		}
+
+		unsigned int hash() const {
+			return mkhash_add(mkhash(cell->name.hash(), port.hash()), offset);
+		}
 	};
 
 	RTLIL::Design *design;
@@ -201,11 +218,11 @@ struct ModWalker
 	CellTypes ct;
 	SigMap sigmap;
 
-	std::map<RTLIL::SigBit, std::set<PortBit>> signal_drivers;
-	std::map<RTLIL::SigBit, std::set<PortBit>> signal_consumers;
-	std::set<RTLIL::SigBit> signal_inputs, signal_outputs;
+	dict<RTLIL::SigBit, pool<PortBit>> signal_drivers;
+	dict<RTLIL::SigBit, pool<PortBit>> signal_consumers;
+	pool<RTLIL::SigBit> signal_inputs, signal_outputs;
 
-	std::map<RTLIL::Cell*, std::set<RTLIL::SigBit>> cell_outputs, cell_inputs;
+	dict<RTLIL::Cell*, pool<RTLIL::SigBit>, hash_obj_ops> cell_outputs, cell_inputs;
 
 	void add_wire(RTLIL::Wire *wire)
 	{
@@ -286,11 +303,11 @@ struct ModWalker
 	// get_* methods -- single RTLIL::SigBit
 
 	template<typename T>
-	inline bool get_drivers(std::set<PortBit> &result, RTLIL::SigBit bit) const
+	inline bool get_drivers(pool<PortBit> &result, RTLIL::SigBit bit) const
 	{
 		bool found = false;
 		if (signal_drivers.count(bit)) {
-			const std::set<PortBit> &r = signal_drivers.at(bit);
+			const pool<PortBit> &r = signal_drivers.at(bit);
 			result.insert(r.begin(), r.end());
 			found = true;
 		}
@@ -298,11 +315,11 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_consumers(std::set<PortBit> &result, RTLIL::SigBit bit) const
+	inline bool get_consumers(pool<PortBit> &result, RTLIL::SigBit bit) const
 	{
 		bool found = false;
 		if (signal_consumers.count(bit)) {
-			const std::set<PortBit> &r = signal_consumers.at(bit);
+			const pool<PortBit> &r = signal_consumers.at(bit);
 			result.insert(r.begin(), r.end());
 			found = true;
 		}
@@ -310,7 +327,7 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_inputs(std::set<RTLIL::SigBit> &result, RTLIL::SigBit bit) const
+	inline bool get_inputs(pool<RTLIL::SigBit> &result, RTLIL::SigBit bit) const
 	{
 		bool found = false;
 		if (signal_inputs.count(bit))
@@ -319,7 +336,7 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_outputs(std::set<RTLIL::SigBit> &result, RTLIL::SigBit bit) const
+	inline bool get_outputs(pool<RTLIL::SigBit> &result, RTLIL::SigBit bit) const
 	{
 		bool found = false;
 		if (signal_outputs.count(bit))
@@ -330,12 +347,12 @@ struct ModWalker
 	// get_* methods -- container of RTLIL::SigBit's (always by reference)
 
 	template<typename T>
-	inline bool get_drivers(std::set<PortBit> &result, const T &bits) const
+	inline bool get_drivers(pool<PortBit> &result, const T &bits) const
 	{
 		bool found = false;
 		for (RTLIL::SigBit bit : bits)
 			if (signal_drivers.count(bit)) {
-				const std::set<PortBit> &r = signal_drivers.at(bit);
+				const pool<PortBit> &r = signal_drivers.at(bit);
 				result.insert(r.begin(), r.end());
 				found = true;
 			}
@@ -343,12 +360,12 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_consumers(std::set<PortBit> &result, const T &bits) const
+	inline bool get_consumers(pool<PortBit> &result, const T &bits) const
 	{
 		bool found = false;
 		for (RTLIL::SigBit bit : bits)
 			if (signal_consumers.count(bit)) {
-				const std::set<PortBit> &r = signal_consumers.at(bit);
+				const pool<PortBit> &r = signal_consumers.at(bit);
 				result.insert(r.begin(), r.end());
 				found = true;
 			}
@@ -356,7 +373,7 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_inputs(std::set<RTLIL::SigBit> &result, const T &bits) const
+	inline bool get_inputs(pool<RTLIL::SigBit> &result, const T &bits) const
 	{
 		bool found = false;
 		for (RTLIL::SigBit bit : bits)
@@ -366,7 +383,7 @@ struct ModWalker
 	}
 
 	template<typename T>
-	inline bool get_outputs(std::set<RTLIL::SigBit> &result, const T &bits) const
+	inline bool get_outputs(pool<RTLIL::SigBit> &result, const T &bits) const
 	{
 		bool found = false;
 		for (RTLIL::SigBit bit : bits)
@@ -377,25 +394,25 @@ struct ModWalker
 
 	// get_* methods -- call by RTLIL::SigSpec (always by value)
 
-	bool get_drivers(std::set<PortBit> &result, RTLIL::SigSpec signal) const
+	bool get_drivers(pool<PortBit> &result, RTLIL::SigSpec signal) const
 	{
 		std::vector<RTLIL::SigBit> bits = sigmap(signal);
 		return get_drivers(result, bits);
 	}
 
-	bool get_consumers(std::set<PortBit> &result, RTLIL::SigSpec signal) const
+	bool get_consumers(pool<PortBit> &result, RTLIL::SigSpec signal) const
 	{
 		std::vector<RTLIL::SigBit> bits = sigmap(signal);
 		return get_consumers(result, bits);
 	}
 
-	bool get_inputs(std::set<RTLIL::SigBit> &result, RTLIL::SigSpec signal) const
+	bool get_inputs(pool<RTLIL::SigBit> &result, RTLIL::SigSpec signal) const
 	{
 		std::vector<RTLIL::SigBit> bits = sigmap(signal);
 		return get_inputs(result, bits);
 	}
 
-	bool get_outputs(std::set<RTLIL::SigBit> &result, RTLIL::SigSpec signal) const
+	bool get_outputs(pool<RTLIL::SigBit> &result, RTLIL::SigSpec signal) const
 	{
 		std::vector<RTLIL::SigBit> bits = sigmap(signal);
 		return get_outputs(result, bits);
@@ -405,47 +422,47 @@ struct ModWalker
 
 	template<typename T>
 	inline bool has_drivers(const T &sig) const {
-		std::set<PortBit> result;
+		pool<PortBit> result;
 		return get_drivers(result, sig);
 	}
 
 	template<typename T>
 	inline bool has_consumers(const T &sig) const {
-		std::set<PortBit> result;
+		pool<PortBit> result;
 		return get_consumers(result, sig);
 	}
 
 	template<typename T>
 	inline bool has_inputs(const T &sig) const {
-		std::set<RTLIL::SigBit> result;
+		pool<RTLIL::SigBit> result;
 		return get_inputs(result, sig);
 	}
 
 	template<typename T>
 	inline bool has_outputs(const T &sig) const {
-		std::set<RTLIL::SigBit> result;
+		pool<RTLIL::SigBit> result;
 		return get_outputs(result, sig);
 	}
 
 	// has_* methods -- call by value
 
 	inline bool has_drivers(RTLIL::SigSpec sig) const {
-		std::set<PortBit> result;
+		pool<PortBit> result;
 		return get_drivers(result, sig);
 	}
 
 	inline bool has_consumers(RTLIL::SigSpec sig) const {
-		std::set<PortBit> result;
+		pool<PortBit> result;
 		return get_consumers(result, sig);
 	}
 
 	inline bool has_inputs(RTLIL::SigSpec sig) const {
-		std::set<RTLIL::SigBit> result;
+		pool<RTLIL::SigBit> result;
 		return get_inputs(result, sig);
 	}
 
 	inline bool has_outputs(RTLIL::SigSpec sig) const {
-		std::set<RTLIL::SigBit> result;
+		pool<RTLIL::SigBit> result;
 		return get_outputs(result, sig);
 	}
 };
diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc
index 0114cbd6..23edccee 100644
--- a/kernel/rtlil.cc
+++ b/kernel/rtlil.cc
@@ -2256,8 +2256,6 @@ void RTLIL::SigSpec::unpack() const
 	that->hash_ = 0;
 }
 
-#define DJB2(_hash, _value) (_hash) = (((_hash) << 5) + (_hash)) + (_value)
-
 void RTLIL::SigSpec::updhash() const
 {
 	RTLIL::SigSpec *that = (RTLIL::SigSpec*)this;
@@ -2272,11 +2270,11 @@ void RTLIL::SigSpec::updhash() const
 	for (auto &c : that->chunks_)
 		if (c.wire == NULL) {
 			for (auto &v : c.data)
-				DJB2(that->hash_, v);
+				that->hash_ = mkhash(that->hash_, v);
 		} else {
-			DJB2(that->hash_, c.wire->name.index_);
-			DJB2(that->hash_, c.offset);
-			DJB2(that->hash_, c.width);
+			that->hash_ = mkhash(that->hash_, c.wire->name.index_);
+			that->hash_ = mkhash(that->hash_, c.offset);
+			that->hash_ = mkhash(that->hash_, c.width);
 		}
 
 	if (that->hash_ == 0)
@@ -2378,7 +2376,7 @@ void RTLIL::SigSpec::remove(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other
 
 void RTLIL::SigSpec::remove2(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other)
 {
-	pool<RTLIL::SigBit> pattern_bits = pattern.to_sigbit_nodict();
+	pool<RTLIL::SigBit> pattern_bits = pattern.to_sigbit_pool();
 	remove2(pattern_bits, other);
 }
 
@@ -2439,7 +2437,7 @@ void RTLIL::SigSpec::remove2(const pool<RTLIL::SigBit> &pattern, RTLIL::SigSpec
 
 RTLIL::SigSpec RTLIL::SigSpec::extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other) const
 {
-	pool<RTLIL::SigBit> pattern_bits = pattern.to_sigbit_nodict();
+	pool<RTLIL::SigBit> pattern_bits = pattern.to_sigbit_pool();
 	return extract(pattern_bits, other);
 }
 
@@ -2943,7 +2941,7 @@ std::set<RTLIL::SigBit> RTLIL::SigSpec::to_sigbit_set() const
 	return sigbits;
 }
 
-pool<RTLIL::SigBit> RTLIL::SigSpec::to_sigbit_nodict() const
+pool<RTLIL::SigBit> RTLIL::SigSpec::to_sigbit_pool() const
 {
 	cover("kernel.rtlil.sigspec.to_sigbit_pool");
 
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index c50a5861..cb654c3a 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -654,7 +654,7 @@ public:
 	bool match(std::string pattern) const;
 
 	std::set<RTLIL::SigBit> to_sigbit_set() const;
-	pool<RTLIL::SigBit> to_sigbit_nodict() const;
+	pool<RTLIL::SigBit> to_sigbit_pool() const;
 	std::vector<RTLIL::SigBit> to_sigbit_vector() const;
 	std::map<RTLIL::SigBit, RTLIL::SigBit> to_sigbit_map(const RTLIL::SigSpec &other) const;
 	dict<RTLIL::SigBit, RTLIL::SigBit> to_sigbit_dict(const RTLIL::SigSpec &other) const;
@@ -1176,7 +1176,7 @@ inline bool RTLIL::SigBit::operator!=(const RTLIL::SigBit &other) const {
 
 inline unsigned int RTLIL::SigBit::hash() const {
 	if (wire)
-		return wire->name.hash() * 33 + offset;
+		return mkhash_add(wire->name.hash(), offset);
 	return data;
 }
 
diff --git a/passes/memory/memory_share.cc b/passes/memory/memory_share.cc
index f77b304b..ec8df759 100644
--- a/passes/memory/memory_share.cc
+++ b/passes/memory/memory_share.cc
@@ -560,13 +560,13 @@ struct MemoryShareWorker
 
 		while (!bits_queue.empty())
 		{
-			std::set<ModWalker::PortBit> portbits;
+			pool<ModWalker::PortBit> portbits;
 			modwalker.get_drivers(portbits, bits_queue);
 			bits_queue.clear();
 
 			for (auto &pbit : portbits)
 				if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) {
-					std::set<RTLIL::SigBit> &cell_inputs = modwalker.cell_inputs[pbit.cell];
+					pool<RTLIL::SigBit> &cell_inputs = modwalker.cell_inputs[pbit.cell];
 					bits_queue.insert(cell_inputs.begin(), cell_inputs.end());
 					sat_cells.insert(pbit.cell);
 				}
diff --git a/passes/opt/share.cc b/passes/opt/share.cc
index cb751055..41a4a690 100644
--- a/passes/opt/share.cc
+++ b/passes/opt/share.cc
@@ -75,7 +75,7 @@ struct ShareWorker
 
 		for (auto &it : module->cells_)
 			if (!fwd_ct.cell_known(it.second->type)) {
-				std::set<RTLIL::SigBit> &bits = modwalker.cell_inputs[it.second];
+				pool<RTLIL::SigBit> &bits = modwalker.cell_inputs[it.second];
 				queue_bits.insert(bits.begin(), bits.end());
 			}
 
@@ -83,19 +83,19 @@ struct ShareWorker
 
 		while (!queue_bits.empty())
 		{
-			std::set<ModWalker::PortBit> portbits;
+			pool<ModWalker::PortBit> portbits;
 			modwalker.get_drivers(portbits, queue_bits);
 			queue_bits.clear();
 
 			for (auto &pbit : portbits) {
 				if (pbit.cell->type == "$mux" || pbit.cell->type == "$pmux") {
-					std::set<RTLIL::SigBit> bits = modwalker.sigmap(pbit.cell->getPort("\\S")).to_sigbit_set();
+					pool<RTLIL::SigBit> bits = modwalker.sigmap(pbit.cell->getPort("\\S")).to_sigbit_pool();
 					terminal_bits.insert(bits.begin(), bits.end());
 					queue_bits.insert(bits.begin(), bits.end());
 					visited_cells.insert(pbit.cell);
 				}
 				if (fwd_ct.cell_known(pbit.cell->type) && visited_cells.count(pbit.cell) == 0) {
-					std::set<RTLIL::SigBit> &bits = modwalker.cell_inputs[pbit.cell];
+					pool<RTLIL::SigBit> &bits = modwalker.cell_inputs[pbit.cell];
 					terminal_bits.insert(bits.begin(), bits.end());
 					queue_bits.insert(bits.begin(), bits.end());
 					visited_cells.insert(pbit.cell);
@@ -730,8 +730,8 @@ struct ShareWorker
 		if (forbidden_controls_cache.count(cell))
 			return forbidden_controls_cache.at(cell);
 
-		std::set<ModWalker::PortBit> pbits;
-		std::set<RTLIL::Cell*> consumer_cells;
+		pool<ModWalker::PortBit> pbits;
+		pool<RTLIL::Cell*, hash_obj_ops> consumer_cells;
 
 		modwalker.get_consumers(pbits, modwalker.cell_outputs[cell]);
 
@@ -802,8 +802,8 @@ struct ShareWorker
 		if (activation_patterns_cache.count(cell))
 			return activation_patterns_cache.at(cell);
 
-		const std::set<RTLIL::SigBit> &cell_out_bits = modwalker.cell_outputs[cell];
-		std::set<RTLIL::Cell*> driven_cells, driven_data_muxes;
+		const pool<RTLIL::SigBit> &cell_out_bits = modwalker.cell_outputs[cell];
+		pool<RTLIL::Cell*, hash_obj_ops> driven_cells, driven_data_muxes;
 
 		for (auto &bit : cell_out_bits)
 		{
@@ -1196,7 +1196,7 @@ struct ShareWorker
 
 				while (!bits_queue.empty())
 				{
-					std::set<ModWalker::PortBit> portbits;
+					pool<ModWalker::PortBit> portbits;
 					modwalker.get_drivers(portbits, bits_queue);
 					bits_queue.clear();