X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=kernel%2Fsigtools.h;h=c631fa481dad7363f0b75d3b0cb62707880364db;hb=6d5d8457883e5de8df58997d95373d3433b781bf;hp=f92a87dbbe7a4465b258f803e27f81406612d73c;hpb=bc86b4a7e9c847180e6fd7ed81e0a15d5aee00a0;p=yosys.git

diff --git a/kernel/sigtools.h b/kernel/sigtools.h
index f92a87dbb..c631fa481 100644
--- a/kernel/sigtools.h
+++ b/kernel/sigtools.h
@@ -2,11 +2,11 @@
  *  yosys -- Yosys Open SYnthesis Suite
  *
  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
- *  
+ *
  *  Permission to use, copy, modify, and/or distribute this software for any
  *  purpose with or without fee is hereby granted, provided that the above
  *  copyright notice and this permission notice appear in all copies.
- *  
+ *
  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
@@ -39,7 +39,7 @@ struct SigPool
 		bits.clear();
 	}
 
-	void add(RTLIL::SigSpec sig)
+	void add(const RTLIL::SigSpec &sig)
 	{
 		for (auto &bit : sig)
 			if (bit.wire != NULL)
@@ -52,7 +52,7 @@ struct SigPool
 			bits.insert(bit);
 	}
 
-	void del(RTLIL::SigSpec sig)
+	void del(const RTLIL::SigSpec &sig)
 	{
 		for (auto &bit : sig)
 			if (bit.wire != NULL)
@@ -65,7 +65,7 @@ struct SigPool
 			bits.erase(bit);
 	}
 
-	void expand(RTLIL::SigSpec from, RTLIL::SigSpec to)
+	void expand(const RTLIL::SigSpec &from, const RTLIL::SigSpec &to)
 	{
 		log_assert(GetSize(from) == GetSize(to));
 		for (int i = 0; i < GetSize(from); i++) {
@@ -75,16 +75,16 @@ struct SigPool
 		}
 	}
 
-	RTLIL::SigSpec extract(RTLIL::SigSpec sig)
+	RTLIL::SigSpec extract(const RTLIL::SigSpec &sig) const
 	{
 		RTLIL::SigSpec result;
 		for (auto &bit : sig)
 			if (bit.wire != NULL && bits.count(bit))
-				result.append_bit(bit);
+				result.append(bit);
 		return result;
 	}
 
-	RTLIL::SigSpec remove(RTLIL::SigSpec sig)
+	RTLIL::SigSpec remove(const RTLIL::SigSpec &sig) const
 	{
 		RTLIL::SigSpec result;
 		for (auto &bit : sig)
@@ -93,12 +93,12 @@ struct SigPool
 		return result;
 	}
 
-	bool check(RTLIL::SigBit bit)
+	bool check(const RTLIL::SigBit &bit) const
 	{
 		return bit.wire != NULL && bits.count(bit);
 	}
 
-	bool check_any(RTLIL::SigSpec sig)
+	bool check_any(const RTLIL::SigSpec &sig) const
 	{
 		for (auto &bit : sig)
 			if (bit.wire != NULL && bits.count(bit))
@@ -106,7 +106,7 @@ struct SigPool
 		return false;
 	}
 
-	bool check_all(RTLIL::SigSpec sig)
+	bool check_all(const RTLIL::SigSpec &sig) const
 	{
 		for (auto &bit : sig)
 			if (bit.wire != NULL && bits.count(bit) == 0)
@@ -114,14 +114,14 @@ struct SigPool
 		return true;
 	}
 
-	RTLIL::SigSpec export_one()
+	RTLIL::SigSpec export_one() const
 	{
 		for (auto &bit : bits)
 			return RTLIL::SigSpec(bit.first, bit.second);
 		return RTLIL::SigSpec();
 	}
 
-	RTLIL::SigSpec export_all()
+	RTLIL::SigSpec export_all() const
 	{
 		pool<RTLIL::SigBit> sig;
 		for (auto &bit : bits)
@@ -135,9 +135,11 @@ struct SigPool
 	}
 };
 
-template <typename T, class Compare = std::less<T>>
+template <typename T, class Compare = void>
 struct SigSet
 {
+	static_assert(!std::is_same<Compare,void>::value, "Default value for `Compare' class not found for SigSet<T>. Please specify.");
+
 	struct bitDef_t : public std::pair<RTLIL::Wire*, int> {
 		bitDef_t() : std::pair<RTLIL::Wire*, int>(NULL, 0) { }
 		bitDef_t(const RTLIL::SigBit &bit) : std::pair<RTLIL::Wire*, int>(bit.wire, bit.offset) { }
@@ -151,67 +153,67 @@ struct SigSet
 		bits.clear();
 	}
 
-	void insert(RTLIL::SigSpec sig, T data)
+	void insert(const RTLIL::SigSpec &sig, T data)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL)
 				bits[bit].insert(data);
 	}
 
-	void insert(RTLIL::SigSpec sig, const std::set<T> &data)
+	void insert(const RTLIL::SigSpec& sig, const std::set<T> &data)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL)
 				bits[bit].insert(data.begin(), data.end());
 	}
 
-	void erase(RTLIL::SigSpec sig)
+	void erase(const RTLIL::SigSpec& sig)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL)
 				bits[bit].clear();
 	}
 
-	void erase(RTLIL::SigSpec sig, T data)
+	void erase(const RTLIL::SigSpec &sig, T data)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL)
 				bits[bit].erase(data);
 	}
 
-	void erase(RTLIL::SigSpec sig, const std::set<T> &data)
+	void erase(const RTLIL::SigSpec &sig, const std::set<T> &data)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL)
 				bits[bit].erase(data.begin(), data.end());
 	}
 
-	void find(RTLIL::SigSpec sig, std::set<T> &result)
+	void find(const RTLIL::SigSpec &sig, std::set<T> &result)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL) {
 				auto &data = bits[bit];
 				result.insert(data.begin(), data.end());
 			}
 	}
 
-	void find(RTLIL::SigSpec sig, pool<T> &result)
+	void find(const RTLIL::SigSpec &sig, pool<T> &result)
 	{
-		for (auto &bit : sig)
+		for (const auto &bit : sig)
 			if (bit.wire != NULL) {
 				auto &data = bits[bit];
 				result.insert(data.begin(), data.end());
 			}
 	}
 
-	std::set<T> find(RTLIL::SigSpec sig)
+	std::set<T> find(const RTLIL::SigSpec &sig)
 	{
 		std::set<T> result;
 		find(sig, result);
 		return result;
 	}
 
-	bool has(RTLIL::SigSpec sig)
+	bool has(const RTLIL::SigSpec &sig)
 	{
 		for (auto &bit : sig)
 			if (bit.wire != NULL && bits.count(bit))
@@ -220,20 +222,16 @@ struct SigSet
 	}
 };
 
+template<typename T>
+class SigSet<T, typename std::enable_if<!std::is_pointer<T>::value>::type> : public SigSet<T, std::less<T>> {};
+template<typename T>
+using sort_by_name_id_guard = typename std::enable_if<std::is_same<T,RTLIL::Cell*>::value>::type;
+template<typename T>
+class SigSet<T, sort_by_name_id_guard<T>> : public SigSet<T, RTLIL::sort_by_name_id<typename std::remove_pointer<T>::type>> {};
+
 struct SigMap
 {
-	struct bitDef_t : public std::pair<RTLIL::Wire*, int> {
-		bitDef_t() : std::pair<RTLIL::Wire*, int>(NULL, 0) { }
-		bitDef_t(const RTLIL::SigBit &bit) : std::pair<RTLIL::Wire*, int>(bit.wire, bit.offset) { }
-		unsigned int hash() const { return first->name.hash() + second; }
-	};
-
-	struct shared_bit_data_t {
-		RTLIL::SigBit map_to;
-		std::set<bitDef_t> bits;
-	};
-
-	dict<bitDef_t, shared_bit_data_t*> bits;
+	mfp<SigBit> database;
 
 	SigMap(RTLIL::Module *module = NULL)
 	{
@@ -241,166 +239,78 @@ struct SigMap
 			set(module);
 	}
 
-	SigMap(const SigMap &other)
-	{
-		copy(other);
-	}
-
-	const SigMap &operator=(const SigMap &other)
-	{
-		copy(other);
-		return *this;
-	}
-
-	void copy(const SigMap &other)
-	{
-		clear();
-		for (auto &bit : other.bits) {
-			bits[bit.first] = new shared_bit_data_t;
-			bits[bit.first]->map_to = bit.second->map_to;
-			bits[bit.first]->bits = bit.second->bits;
-		}
-	}
-
 	void swap(SigMap &other)
 	{
-		bits.swap(other.bits);
-	}
-
-	~SigMap()
-	{
-		clear();
+		database.swap(other.database);
 	}
 
 	void clear()
 	{
-		std::set<shared_bit_data_t*> all_bd_ptr;
-		for (auto &it : bits)
-			all_bd_ptr.insert(it.second);
-		for (auto bd_ptr : all_bd_ptr)
-			delete bd_ptr;
-		bits.clear();
+		database.clear();
 	}
 
 	void set(RTLIL::Module *module)
 	{
-		clear();
+		int bitcount = 0;
 		for (auto &it : module->connections())
-			add(it.first, it.second);
-	}
-
-	// internal helper function
-	void register_bit(const RTLIL::SigBit &bit)
-	{
-		if (bit.wire && bits.count(bit) == 0) {
-			shared_bit_data_t *bd = new shared_bit_data_t;
-			bd->map_to = bit;
-			bd->bits.insert(bit);
-			bits[bit] = bd;
-		}
-	}
-
-	// internal helper function
-	void unregister_bit(const RTLIL::SigBit &bit)
-	{
-		if (bit.wire && bits.count(bit) > 0) {
-			shared_bit_data_t *bd = bits[bit];
-			bd->bits.erase(bit);
-			if (bd->bits.size() == 0)
-				delete bd;
-			bits.erase(bit);
-		}
-	}
-
-	// internal helper function
-	void merge_bit(const RTLIL::SigBit &bit1, const RTLIL::SigBit &bit2)
-	{
-		log_assert(bit1.wire != NULL && bit2.wire != NULL);
-
-		shared_bit_data_t *bd1 = bits[bit1];
-		shared_bit_data_t *bd2 = bits[bit2];
-		log_assert(bd1 != NULL && bd2 != NULL);
-
-		if (bd1 == bd2)
-			return;
-
-		if (bd1->bits.size() < bd2->bits.size())
-		{
-			for (auto &bit : bd1->bits)
-				bits[bit] = bd2;
-			bd2->bits.insert(bd1->bits.begin(), bd1->bits.end());
-			delete bd1;
-		}
-		else
-		{
-			bd1->map_to = bd2->map_to;
-			for (auto &bit : bd2->bits)
-				bits[bit] = bd1;
-			bd1->bits.insert(bd2->bits.begin(), bd2->bits.end());
-			delete bd2;
-		}
-	}
+			bitcount += it.first.size();
 
-	// internal helper function
-	void set_bit(const RTLIL::SigBit &bit1, const RTLIL::SigBit &bit2)
-	{
-		log_assert(bit1.wire != NULL);
-		log_assert(bits.count(bit1) > 0);
-		bits[bit1]->map_to = bit2;
-	}
+		database.clear();
+		database.reserve(bitcount);
 
-	// internal helper function
-	void map_bit(RTLIL::SigBit &bit) const
-	{
-		if (bit.wire && bits.count(bit) > 0)
-			bit = bits.at(bit)->map_to;
+		for (auto &it : module->connections())
+			add(it.first, it.second);
 	}
 
-	void add(RTLIL::SigSpec from, RTLIL::SigSpec to)
+	void add(const RTLIL::SigSpec& from, const RTLIL::SigSpec& to)
 	{
 		log_assert(GetSize(from) == GetSize(to));
 
 		for (int i = 0; i < GetSize(from); i++)
 		{
-			RTLIL::SigBit &bf = from[i];
-			RTLIL::SigBit &bt = to[i];
+			int bfi = database.lookup(from[i]);
+			int bti = database.lookup(to[i]);
+
+			const RTLIL::SigBit &bf = database[bfi];
+			const RTLIL::SigBit &bt = database[bti];
 
-			if (bf.wire == NULL)
-				continue;
+			if (bf.wire || bt.wire)
+			{
+				database.imerge(bfi, bti);
 
-			register_bit(bf);
-			register_bit(bt);
+				if (bf.wire == nullptr)
+					database.ipromote(bfi);
 
-			if (bt.wire != NULL)
-				merge_bit(bf, bt);
-			else
-				set_bit(bf, bt);
+				if (bt.wire == nullptr)
+					database.ipromote(bti);
+			}
 		}
 	}
 
-	void add(RTLIL::SigSpec sig)
+	void add(const RTLIL::SigBit &bit)
 	{
-		for (auto &bit : sig) {
-			register_bit(bit);
-			set_bit(bit, bit);
-		}
+		const auto &b = database.find(bit);
+		if (b.wire != nullptr)
+			database.promote(bit);
 	}
 
-	void del(RTLIL::SigSpec sig)
+	void add(const RTLIL::SigSpec &sig)
 	{
-		for (auto &bit : sig)
-			unregister_bit(bit);
+		for (const auto &bit : sig)
+			add(bit);
 	}
 
+	inline void add(Wire *wire) { return add(RTLIL::SigSpec(wire)); }
+
 	void apply(RTLIL::SigBit &bit) const
 	{
-		map_bit(bit);
+		bit = database.find(bit);
 	}
 
 	void apply(RTLIL::SigSpec &sig) const
 	{
 		for (auto &bit : sig)
-			map_bit(bit);
+			apply(bit);
 	}
 
 	RTLIL::SigBit operator()(RTLIL::SigBit bit) const
@@ -417,10 +327,19 @@ struct SigMap
 
 	RTLIL::SigSpec operator()(RTLIL::Wire *wire) const
 	{
-		RTLIL::SigSpec sig(wire);
+		SigSpec sig(wire);
 		apply(sig);
 		return sig;
 	}
+
+	RTLIL::SigSpec allbits() const
+	{
+		RTLIL::SigSpec sig;
+		for (const auto &bit : database)
+			if (bit.wire != nullptr)
+				sig.append(bit);
+		return sig;
+	}
 };
 
 YOSYS_NAMESPACE_END