From 546e8b5fe7063caf0140d753d8c20614cbeae723 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Fri, 7 Nov 2014 15:21:03 +0100
Subject: [PATCH] Improved TopoSort determinism

---
 kernel/rtlil.h            |  2 +-
 kernel/utils.h            | 16 ++++++++--------
 passes/opt/opt_const.cc   |  2 +-
 passes/opt/share.cc       |  8 +++++---
 passes/techmap/techmap.cc |  2 +-
 5 files changed, 16 insertions(+), 14 deletions(-)

diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index 8a4d348be..0bb1e4e84 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -216,7 +216,7 @@ namespace RTLIL
 		// set has an influence on the algorithm.
 
 		template<typename T> struct compare_ptr_by_name {
-			bool operator()(const T *a, const T *b) {
+			bool operator()(const T *a, const T *b) const {
 				return (a == nullptr || b == nullptr) ? (a < b) : (a->name < b->name);
 			}
 		};
diff --git a/kernel/utils.h b/kernel/utils.h
index 1779a9afc..479effdc9 100644
--- a/kernel/utils.h
+++ b/kernel/utils.h
@@ -128,12 +128,12 @@ public:
 // A simple class for topological sorting
 // ------------------------------------------------
 
-template<typename T>
+template<typename T, typename C = std::less<T>>
 struct TopoSort
 {
 	bool analyze_loops, found_loops;
-	std::map<T, std::set<T>> database;
-	std::set<std::set<T>> loops;
+	std::map<T, std::set<T, C>, C> database;
+	std::set<std::set<T, C>> loops;
 	std::vector<T> sorted;
 
 	TopoSort()
@@ -145,7 +145,7 @@ struct TopoSort
 	void node(T n)
 	{
 		if (database.count(n) == 0)
-			database[n] = std::set<T>();
+			database[n] = std::set<T, C>();
 	}
 
 	void edge(T left, T right)
@@ -154,12 +154,12 @@ struct TopoSort
 		database[right].insert(left);
 	}
 
-	void sort_worker(const T &n, std::set<T> &marked_cells, std::set<T> &active_cells, std::vector<T> &active_stack)
+	void sort_worker(const T &n, std::set<T, C> &marked_cells, std::set<T, C> &active_cells, std::vector<T> &active_stack)
 	{
 		if (active_cells.count(n)) {
 			found_loops = true;
 			if (analyze_loops) {
-				std::set<T> loop;
+				std::set<T, C> loop;
 				for (int i = GetSize(active_stack)-1; i >= 0; i--) {
 					loop.insert(active_stack[i]);
 					if (active_stack[i] == n)
@@ -197,8 +197,8 @@ struct TopoSort
 		sorted.clear();
 		found_loops = false;
 
-		std::set<T> marked_cells;
-		std::set<T> active_cells;
+		std::set<T, C> marked_cells;
+		std::set<T, C> active_cells;
 		std::vector<T> active_stack;
 
 		for (auto &it : database)
diff --git a/passes/opt/opt_const.cc b/passes/opt/opt_const.cc
index e00d5e3b1..1e59f18c1 100644
--- a/passes/opt/opt_const.cc
+++ b/passes/opt/opt_const.cc
@@ -198,7 +198,7 @@ void replace_const_cells(RTLIL::Design *design, RTLIL::Module *module, bool cons
 	SigMap assign_map(module);
 	std::map<RTLIL::SigSpec, RTLIL::SigSpec> invert_map;
 
-	TopoSort<RTLIL::Cell*> cells;
+	TopoSort<RTLIL::Cell*, RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell>> cells;
 	std::map<RTLIL::Cell*, std::set<RTLIL::SigBit>> cell_to_inbit;
 	std::map<RTLIL::SigBit, std::set<RTLIL::Cell*>> outbit_to_cell;
 
diff --git a/passes/opt/share.cc b/passes/opt/share.cc
index 2496f15d3..cb7510553 100644
--- a/passes/opt/share.cc
+++ b/passes/opt/share.cc
@@ -27,6 +27,8 @@
 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
 
+typedef RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell> cell_ptr_cmp;
+
 struct ShareWorkerConfig
 {
 	int limit;
@@ -52,8 +54,8 @@ struct ShareWorker
 	std::set<RTLIL::Cell*> recursion_state;
 
 	SigMap topo_sigmap;
-	std::map<RTLIL::Cell*, std::set<RTLIL::Cell*>> topo_cell_drivers;
-	std::map<RTLIL::SigBit, std::set<RTLIL::Cell*>> topo_bit_drivers;
+	std::map<RTLIL::Cell*, std::set<RTLIL::Cell*, cell_ptr_cmp>, cell_ptr_cmp> topo_cell_drivers;
+	std::map<RTLIL::SigBit, std::set<RTLIL::Cell*, cell_ptr_cmp>> topo_bit_drivers;
 
 	std::vector<std::pair<RTLIL::SigBit, RTLIL::SigBit>> exclusive_ctrls;
 
@@ -937,7 +939,7 @@ struct ShareWorker
 		ct.setup_internals();
 		ct.setup_stdcells();
 
-		TopoSort<RTLIL::Cell*> toposort;
+		TopoSort<RTLIL::Cell*, cell_ptr_cmp> toposort;
 		toposort.analyze_loops = false;
 
 		topo_sigmap.set(module);
diff --git a/passes/techmap/techmap.cc b/passes/techmap/techmap.cc
index 73da6ce1d..e109c5b58 100644
--- a/passes/techmap/techmap.cc
+++ b/passes/techmap/techmap.cc
@@ -281,7 +281,7 @@ struct TechmapWorker
 
 		SigMap sigmap(module);
 
-		TopoSort<RTLIL::Cell*> cells;
+		TopoSort<RTLIL::Cell*, RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell>> cells;
 		std::map<RTLIL::Cell*, std::set<RTLIL::SigBit>> cell_to_inbit;
 		std::map<RTLIL::SigBit, std::set<RTLIL::Cell*>> outbit_to_cell;
 
-- 
2.30.2