From 2fb4931e5be2c2a0c80ffbca73ad74ebb8c9032f Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Tue, 14 Apr 2020 18:09:05 +0000 Subject: Add specialized `hash()` for type `dict` and use a `dict` instead of a `std::map` for `techmap_cache` and `techmap_do_cache`. --- kernel/hashlib.h | 25 ++++++++++++++++++++----- kernel/rtlil.h | 2 +- 2 files changed, 21 insertions(+), 6 deletions(-) (limited to 'kernel') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 592d6e577..cdbad87c4 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -19,6 +19,12 @@ namespace hashlib { +template struct hash_ops; +template> class dict; +template> class idict; +template> class pool; +template> class mfp; + const int hashtable_size_trigger = 2; const int hashtable_size_factor = 3; @@ -100,6 +106,20 @@ template struct hash_ops> { } }; +template struct hash_ops> { + static inline bool cmp(dict a, dict b) { + return a == b; + } + static inline unsigned int hash(dict a) { + unsigned int h = mkhash_init; + for (auto &it : a) { + h = mkhash(h, hash_ops

::hash(it.first)); + h = mkhash(h, hash_ops::hash(it.second)); + } + return h; + } +}; + template struct hash_ops> { static inline bool cmp(std::tuple a, std::tuple b) { return a == b; @@ -191,11 +211,6 @@ inline int hashtable_size(int min_size) throw std::length_error("hash table exceeded maximum size."); } -template> class dict; -template> class idict; -template> class pool; -template> class mfp; - template class dict { diff --git a/kernel/rtlil.h b/kernel/rtlil.h index 11c45bbec..dad8508c3 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -150,7 +150,7 @@ namespace RTLIL if (!p[0]) return 0; - log_assert(p[0] == '$' || p[0] == '\\'); + log_assert(p[0] == '$' || p[0] == '\\' || strncmp(p, "_TECHMAP_", strlen("_TECHMAP_")) == 0); log_assert(p[1] != 0); auto it = global_id_index_.find((char*)p); -- cgit v1.2.3 From dabeb1e8a136730536d17fd79e6c348d8cdca271 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 20 Apr 2020 15:50:12 -0700 Subject: techmap: prefix special wires with backslash for use as IdString --- kernel/constids.inc | 1 + kernel/rtlil.h | 2 +- 2 files changed, 2 insertions(+), 1 deletion(-) (limited to 'kernel') diff --git a/kernel/constids.inc b/kernel/constids.inc index aa75a9c09..5c8373513 100644 --- a/kernel/constids.inc +++ b/kernel/constids.inc @@ -169,6 +169,7 @@ X(techmap_autopurge) X(_TECHMAP_BITS_CONNMAP_) X(_TECHMAP_CELLTYPE_) X(techmap_celltype) +X(_TECHMAP_FAIL_) X(techmap_maccmap) X(_TECHMAP_REPLACE_) X(techmap_simplemap) diff --git a/kernel/rtlil.h b/kernel/rtlil.h index dad8508c3..11c45bbec 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -150,7 +150,7 @@ namespace RTLIL if (!p[0]) return 0; - log_assert(p[0] == '$' || p[0] == '\\' || strncmp(p, "_TECHMAP_", strlen("_TECHMAP_")) == 0); + log_assert(p[0] == '$' || p[0] == '\\'); log_assert(p[1] != 0); auto it = global_id_index_.find((char*)p); -- cgit v1.2.3 From 35b94d1f664928dcf8476a9a6f35e2bb7f647ee1 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Wed, 22 Apr 2020 22:04:22 +0000 Subject: kernel: Re-implement `dict` hash code as a `dict` member function instead of a specialized template for `hash_ops`. --- kernel/hashlib.h | 34 ++++++++++++++-------------------- 1 file changed, 14 insertions(+), 20 deletions(-) (limited to 'kernel') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index cdbad87c4..18114b6ad 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -19,12 +19,6 @@ namespace hashlib { -template struct hash_ops; -template> class dict; -template> class idict; -template> class pool; -template> class mfp; - const int hashtable_size_trigger = 2; const int hashtable_size_factor = 3; @@ -106,20 +100,6 @@ template struct hash_ops> { } }; -template struct hash_ops> { - static inline bool cmp(dict a, dict b) { - return a == b; - } - static inline unsigned int hash(dict a) { - unsigned int h = mkhash_init; - for (auto &it : a) { - h = mkhash(h, hash_ops

::hash(it.first)); - h = mkhash(h, hash_ops::hash(it.second)); - } - return h; - } -}; - template struct hash_ops> { static inline bool cmp(std::tuple a, std::tuple b) { return a == b; @@ -211,6 +191,11 @@ inline int hashtable_size(int min_size) throw std::length_error("hash table exceeded maximum size."); } +template> class dict; +template> class idict; +template> class pool; +template> class mfp; + template class dict { @@ -630,6 +615,15 @@ public: return !operator==(other); } + unsigned int hash() const { + unsigned int h = mkhash_init; + for (auto &it : entries) { + h = mkhash(h, hash_ops::hash(it.udata.first)); + h = mkhash(h, hash_ops::hash(it.udata.second)); + } + return h; + } + void reserve(size_t n) { entries.reserve(n); } size_t size() const { return entries.size(); } bool empty() const { return entries.empty(); } -- cgit v1.2.3 From 976edb7597692ac04111b3c51b13e18105c14f42 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Fri, 24 Apr 2020 08:37:16 +0000 Subject: kernel: Ensure `dict` always hashes to the same value given the same contents. --- kernel/hashlib.h | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'kernel') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 18114b6ad..1284f3f8d 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -207,6 +207,7 @@ class dict entry_t() { } entry_t(const std::pair &udata, int next) : udata(udata), next(next) { } entry_t(std::pair &&udata, int next) : udata(std::move(udata)), next(next) { } + bool operator<(const entry_t &other) const { return udata.first < other.udata.first; } }; std::vector hashtable; @@ -616,10 +617,12 @@ public: } unsigned int hash() const { + std::vector entries_(entries); //make a copy to preserve const-ness + std::sort(entries_.begin(), entries_.end()); unsigned int h = mkhash_init; - for (auto &it : entries) { - h = mkhash(h, hash_ops::hash(it.udata.first)); - h = mkhash(h, hash_ops::hash(it.udata.second)); + for (unsigned int i = 0; i < entries_.size(); ++i) { + h = mkhash(h, hash_ops::hash(entries_[i].udata.first)); + h = mkhash(h, hash_ops::hash(entries_[i].udata.second)); } return h; } -- cgit v1.2.3 From 6eea4b3d79590f874caa3ec740785781f3926666 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Mon, 18 May 2020 17:10:01 +0000 Subject: kernel: Try an order-independent approach to hashing `dict`. Co-Authored-By: David Shah Co-Authored-By: Eddie Hung --- kernel/hashlib.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'kernel') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 1284f3f8d..5c87b55f5 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -617,12 +617,10 @@ public: } unsigned int hash() const { - std::vector entries_(entries); //make a copy to preserve const-ness - std::sort(entries_.begin(), entries_.end()); unsigned int h = mkhash_init; - for (unsigned int i = 0; i < entries_.size(); ++i) { - h = mkhash(h, hash_ops::hash(entries_[i].udata.first)); - h = mkhash(h, hash_ops::hash(entries_[i].udata.second)); + for (auto &entry : entries) { + h ^= hash_ops::hash(entry.udata.first); + h ^= hash_ops::hash(entry.udata.second); } return h; } -- cgit v1.2.3