X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=kernel%2Fbitpattern.h;h=894a95ed1ff3ff22d714f2c8a081b6b72a6db817;hb=d61a6b81fcbc90dba81e136e0de65904f73a859e;hp=934796d24b49ce5ba535b10a21cf4fbf30604e52;hpb=4b4048bc5feba1ab05c7a63f12c0a17879cb7e04;p=yosys.git

diff --git a/kernel/bitpattern.h b/kernel/bitpattern.h
index 934796d24..894a95ed1 100644
--- a/kernel/bitpattern.h
+++ b/kernel/bitpattern.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
@@ -23,28 +23,46 @@
 #include "kernel/log.h"
 #include "kernel/rtlil.h"
 
+YOSYS_NAMESPACE_BEGIN
+
 struct BitPatternPool
 {
 	int width;
-	typedef std::vector<RTLIL::State> bits_t;
-	std::set<bits_t> pool;
+	struct bits_t {
+		std::vector<RTLIL::State> bitdata;
+		mutable unsigned int cached_hash;
+		bits_t(int width = 0) : bitdata(width), cached_hash(0) { }
+		RTLIL::State &operator[](int index) {
+			return bitdata[index];
+		}
+		const RTLIL::State &operator[](int index) const {
+			return bitdata[index];
+		}
+		bool operator==(const bits_t &other) const {
+			if (hash() != other.hash())
+				return false;
+			return bitdata == other.bitdata;
+		}
+		unsigned int hash() const {
+			if (!cached_hash)
+				cached_hash = hash_ops<std::vector<RTLIL::State>>::hash(bitdata);
+			return cached_hash;
+		}
+	};
+	pool<bits_t> database;
 
 	BitPatternPool(RTLIL::SigSpec sig)
 	{
 		width = sig.size();
 		if (width > 0) {
-			std::vector<RTLIL::State> pattern(width);
-			sig.optimize();
+			bits_t pattern(width);
 			for (int i = 0; i < width; i++) {
-				RTLIL::SigSpec s = sig.extract(i, 1);
-				s.optimize();
-				assert(s.chunks().size() == 1);
-				if (s.chunks()[0].wire == NULL && s.chunks()[0].data.bits[0] <= RTLIL::State::S1)
-					pattern[i] = s.chunks()[0].data.bits[0];
+				if (sig[i].wire == NULL && sig[i].data <= RTLIL::State::S1)
+					pattern[i] = sig[i].data;
 				else
 					pattern[i] = RTLIL::State::Sa;
 			}
-			pool.insert(pattern);
+			database.insert(pattern);
 		}
 	}
 
@@ -52,20 +70,18 @@ struct BitPatternPool
 	{
 		this->width = width;
 		if (width > 0) {
-			std::vector<RTLIL::State> pattern(width);
+			bits_t pattern(width);
 			for (int i = 0; i < width; i++)
 				pattern[i] = RTLIL::State::Sa;
-			pool.insert(pattern);
+			database.insert(pattern);
 		}
 	}
 
 	bits_t sig2bits(RTLIL::SigSpec sig)
 	{
-		sig.optimize();
-		assert(sig.is_fully_const());
-		assert(sig.chunks().size() == 1);
-		bits_t bits = sig.chunks()[0].data.bits;
-		for (auto &b : bits)
+		bits_t bits;
+		bits.bitdata = sig.as_const().bits;
+		for (auto &b : bits.bitdata)
 			if (b > RTLIL::State::S1)
 				b = RTLIL::State::Sa;
 		return bits;
@@ -73,8 +89,8 @@ struct BitPatternPool
 
 	bool match(bits_t a, bits_t b)
 	{
-		assert(int(a.size()) == width);
-		assert(int(b.size()) == width);
+		log_assert(int(a.bitdata.size()) == width);
+		log_assert(int(b.bitdata.size()) == width);
 		for (int i = 0; i < width; i++)
 			if (a[i] <= RTLIL::State::S1 && b[i] <= RTLIL::State::S1 && a[i] != b[i])
 				return false;
@@ -84,7 +100,7 @@ struct BitPatternPool
 	bool has_any(RTLIL::SigSpec sig)
 	{
 		bits_t bits = sig2bits(sig);
-		for (auto &it : pool)
+		for (auto &it : database)
 			if (match(it, bits))
 				return true;
 		return false;
@@ -93,13 +109,13 @@ struct BitPatternPool
 	bool has_all(RTLIL::SigSpec sig)
 	{
 		bits_t bits = sig2bits(sig);
-		for (auto &it : pool)
+		for (auto &it : database)
 			if (match(it, bits)) {
 				for (int i = 0; i < width; i++)
 					if (bits[i] > RTLIL::State::S1 && it[i] <= RTLIL::State::S1)
-						goto next_pool_entry;
+						goto next_database_entry;
 				return true;
-	next_pool_entry:;
+	next_database_entry:;
 			}
 		return false;
 	}
@@ -108,36 +124,38 @@ struct BitPatternPool
 	{
 		bool status = false;
 		bits_t bits = sig2bits(sig);
-		std::vector<bits_t> pattern_list;
-		for (auto &it : pool)
-			if (match(it, bits))
-				pattern_list.push_back(it);
-		for (auto pattern : pattern_list) {
-			pool.erase(pattern);
-			for (int i = 0; i < width; i++) {
-				if (pattern[i] != RTLIL::State::Sa || bits[i] == RTLIL::State::Sa)
-					continue;
-				bits_t new_pattern = pattern;
-				new_pattern[i] = bits[i] == RTLIL::State::S1 ? RTLIL::State::S0 : RTLIL::State::S1;
-				pool.insert(new_pattern);
-			}
-			status = true;
-		}
+		for (auto it = database.begin(); it != database.end();)
+			if (match(*it, bits)) {
+				for (int i = 0; i < width; i++) {
+					if ((*it)[i] != RTLIL::State::Sa || bits[i] == RTLIL::State::Sa)
+						continue;
+					bits_t new_pattern;
+					new_pattern.bitdata = it->bitdata;
+					new_pattern[i] = bits[i] == RTLIL::State::S1 ? RTLIL::State::S0 : RTLIL::State::S1;
+					database.insert(new_pattern);
+				}
+				it = database.erase(it);
+				status = true;
+				continue;
+			} else
+				++it;
 		return status;
 	}
 
 	bool take_all()
 	{
-		if (pool.empty())
+		if (database.empty())
 			return false;
-		pool.clear();
+		database.clear();
 		return true;
 	}
 
 	bool empty()
 	{
-		return pool.empty();
+		return database.empty();
 	}
-}; 
+};
+
+YOSYS_NAMESPACE_END
 
 #endif