aboutsummaryrefslogtreecommitdiffstats
path: root/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'kernel')
-rw-r--r--kernel/cost.h14
-rw-r--r--kernel/hashmap.h230
-rw-r--r--kernel/log.cc6
-rw-r--r--kernel/log.h4
-rw-r--r--kernel/rtlil.cc22
-rw-r--r--kernel/rtlil.h32
-rw-r--r--kernel/yosys.h1
7 files changed, 262 insertions, 47 deletions
diff --git a/kernel/cost.h b/kernel/cost.h
index 1b4166e00..c6c631e0a 100644
--- a/kernel/cost.h
+++ b/kernel/cost.h
@@ -24,10 +24,10 @@
YOSYS_NAMESPACE_BEGIN
-int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::Module*, int> *mod_cost_cache = nullptr);
+int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::IdString, int> *mod_cost_cache = nullptr);
int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const> &parameters = dict<RTLIL::IdString, RTLIL::Const>(),
- RTLIL::Design *design = nullptr, dict<RTLIL::Module*, int> *mod_cost_cache = nullptr)
+ RTLIL::Design *design = nullptr, dict<RTLIL::IdString, int> *mod_cost_cache = nullptr)
{
static dict<RTLIL::IdString, int> gate_cost = {
{ "$_BUF_", 1 },
@@ -55,18 +55,18 @@ int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const
if (mod->attributes.count("\\cost"))
return mod->attributes.at("\\cost").as_int();
- dict<RTLIL::Module*, int> local_mod_cost_cache;
+ dict<RTLIL::IdString, int> local_mod_cost_cache;
if (mod_cost_cache == nullptr)
mod_cost_cache = &local_mod_cost_cache;
- if (mod_cost_cache->count(mod))
- return mod_cost_cache->at(mod);
+ if (mod_cost_cache->count(mod->name))
+ return mod_cost_cache->at(mod->name);
int module_cost = 1;
for (auto c : mod->cells())
module_cost += get_cell_cost(c, mod_cost_cache);
- (*mod_cost_cache)[mod] = module_cost;
+ (*mod_cost_cache)[mod->name] = module_cost;
return module_cost;
}
@@ -74,7 +74,7 @@ int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const
return 1;
}
-int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::Module*, int> *mod_cost_cache)
+int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::IdString, int> *mod_cost_cache)
{
return get_cell_cost(cell->type, cell->parameters, cell->module->design, mod_cost_cache);
}
diff --git a/kernel/hashmap.h b/kernel/hashmap.h
index bd4fc4d22..d5f8c4e98 100644
--- a/kernel/hashmap.h
+++ b/kernel/hashmap.h
@@ -19,6 +19,7 @@
#ifndef YOSYS_HASHMAP_H
+#include <stdexcept>
#include <string>
#include <vector>
@@ -27,28 +28,28 @@ inline unsigned int mkhash(unsigned int a, unsigned int b) {
}
template<typename T> struct hash_ops {
- bool cmp(const T &a, const T &b) {
+ bool cmp(const T &a, const T &b) const {
return a == b;
}
- unsigned int hash(const T &a) {
+ unsigned int hash(const T &a) const {
return a.hash();
}
};
template<> struct hash_ops<int> {
- bool cmp(int a, int b) {
+ bool cmp(int a, int b) const {
return a == b;
}
- unsigned int hash(int a) {
+ unsigned int hash(int a) const {
return a;
}
};
template<> struct hash_ops<std::string> {
- bool cmp(const std::string &a, const std::string &b) {
+ bool cmp(const std::string &a, const std::string &b) const {
return a == b;
}
- unsigned int hash(const std::string &a) {
+ unsigned int hash(const std::string &a) const {
unsigned int v = 0;
for (auto c : a)
v = mkhash(v, c);
@@ -56,14 +57,25 @@ template<> struct hash_ops<std::string> {
}
};
+struct hash_ptr_ops {
+ bool cmp(const void *a, const void *b) const {
+ return a == b;
+ }
+ unsigned int hash(const void *a) const {
+ return (unsigned long)a;
+ }
+};
+
template<typename K, typename T, typename OPS = hash_ops<K>>
-class new_dict
+class dict
{
struct entry_t
{
int link;
std::pair<K, T> udata;
+
entry_t() : link(-1) { }
+ entry_t(const std::pair<K, T> &udata) : link(1), udata(udata) { }
bool is_free() const { return link < 0; }
int get_next() const { return (link > 0 ? link : -link) - 2; }
@@ -79,17 +91,61 @@ class new_dict
void init()
{
+ free_list = -1;
counter = 0;
- entries.resize(61);
+ }
+
+ void init_from(const dict<K, T, OPS> &other)
+ {
+ hashtable.clear();
+ entries.clear();
+
+ counter = other.size();
+ int new_size = grow_size(counter);
+ entries.reserve(new_size);
+
+ for (auto &it : other)
+ entries.push_back(entry_t(it));
+ entries.resize(new_size);
rehash();
}
- int mkhash(const K &key)
+ size_t grow_size(size_t old_size)
{
- return ops.hash(key) % int(hashtable.size());
+ if (old_size < 53) return 53;
+ if (old_size < 113) return 113;
+ if (old_size < 251) return 251;
+ if (old_size < 503) return 503;
+ if (old_size < 1130) return 1130;
+ if (old_size < 2510) return 2510;
+ if (old_size < 5030) return 5030;
+ if (old_size < 11300) return 11300;
+ if (old_size < 25100) return 25100;
+ if (old_size < 50300) return 50300;
+ if (old_size < 113000) return 113000;
+ if (old_size < 251000) return 251000;
+ if (old_size < 503000) return 503000;
+ if (old_size < 1130000) return 1130000;
+ if (old_size < 2510000) return 2510000;
+ if (old_size < 5030000) return 5030000;
+ if (old_size < 11300000) return 11300000;
+ if (old_size < 25100000) return 25100000;
+ if (old_size < 50300000) return 50300000;
+ if (old_size < 113000000) return 113000000;
+ if (old_size < 251000000) return 251000000;
+ if (old_size < 503000000) return 503000000;
+ if (old_size < 1130000000) return 1130000000;
+ throw std::length_error("maximum size for dict reached");
+ }
+
+ int mkhash(const K &key) const
+ {
+ unsigned int hash = 0;
+ if (!hashtable.empty())
+ hash = ops.hash(key) % (unsigned int)(hashtable.size());
+ return hash;
}
-public:
void rehash()
{
free_list = -1;
@@ -112,7 +168,7 @@ public:
void do_erase(const K &key, int hash)
{
int last_index = -1;
- int index = hashtable[hash];
+ int index = hashtable.empty() ? -1 : hashtable[hash];
while (1) {
if (index < 0)
return;
@@ -124,7 +180,8 @@ public:
entries[index].udata = std::pair<K, T>();
entries[index].set_next_free(free_list);
free_list = index;
- counter--;
+ if (--counter == 0)
+ init();
return;
}
last_index = index;
@@ -132,9 +189,9 @@ public:
}
}
- int lookup_index(const K &key, int hash)
+ int lookup_index(const K &key, int hash) const
{
- int index = hashtable[hash];
+ int index = hashtable.empty() ? -1 : hashtable[hash];
while (1) {
if (index < 0)
return -1;
@@ -149,7 +206,7 @@ public:
if (free_list < 0)
{
int i = entries.size();
- entries.resize(2*entries.size());
+ entries.resize(grow_size(i));
entries[i].udata = value;
entries[i].set_next_used(0);
counter++;
@@ -169,24 +226,74 @@ public:
public:
class iterator
{
- new_dict<K, T, OPS> *ptr;
+ dict<K, T, OPS> *ptr;
int index;
public:
- iterator(new_dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
+ iterator() { }
+ iterator(dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
iterator operator++() { do index++; while (index != int(ptr->entries.size()) && ptr->entries[index].is_free()); return *this; }
iterator operator--() { do index--; while (index != 0 && ptr->entries[index].is_free()); return *this; }
bool operator==(const iterator &other) const { return index == other.index; }
bool operator!=(const iterator &other) const { return index != other.index; }
std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
+ std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
+ const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+ const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
};
- new_dict()
+ class const_iterator
+ {
+ const dict<K, T, OPS> *ptr;
+ int index;
+ public:
+ const_iterator() { }
+ const_iterator(const dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
+ const_iterator operator++() { do index++; while (index != int(ptr->entries.size()) && ptr->entries[index].is_free()); return *this; }
+ const_iterator operator--() { do index--; while (index != 0 && ptr->entries[index].is_free()); return *this; }
+ bool operator==(const const_iterator &other) const { return index == other.index; }
+ bool operator!=(const const_iterator &other) const { return index != other.index; }
+ const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+ const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
+ };
+
+ dict()
{
init();
}
+ dict(const dict<K, T, OPS> &other)
+ {
+ init_from(other);
+ }
+
+ dict(dict<K, T, OPS> &&other)
+ {
+ free_list = -1;
+ counter = 0;
+ swap(other);
+ }
+
+ dict<K, T, OPS> &operator=(const dict<K, T, OPS> &other) {
+ clear();
+ init_from(other);
+ return *this;
+ }
+
+ dict<K, T, OPS> &operator=(dict<K, T, OPS> &&other) {
+ clear();
+ swap(other);
+ return *this;
+ }
+
+ dict(const std::initializer_list<std::pair<K, T>> &list)
+ {
+ init();
+ for (auto &it : list)
+ insert(it);
+ }
+
template<class InputIterator>
- new_dict(InputIterator first, InputIterator last)
+ dict(InputIterator first, InputIterator last)
{
init();
insert(first, last);
@@ -215,13 +322,55 @@ public:
do_erase(key, hash);
}
- int count(const K &key)
+ void erase(const iterator it)
+ {
+ int hash = mkhash(it->first);
+ do_erase(it->first, hash);
+ }
+
+ int count(const K &key) const
{
int hash = mkhash(key);
int i = lookup_index(key, hash);
return i < 0 ? 0 : 1;
}
+ iterator find(const K &key)
+ {
+ int hash = mkhash(key);
+ int i = lookup_index(key, hash);
+ if (i < 0)
+ return end();
+ return iterator(this, i);
+ }
+
+ const_iterator find(const K &key) const
+ {
+ int hash = mkhash(key);
+ int i = lookup_index(key, hash);
+ if (i < 0)
+ return end();
+ return const_iterator(this, i);
+ }
+
+ T& at(const K &key)
+ {
+ int hash = mkhash(key);
+ int i = lookup_index(key, hash);
+ if (i < 0)
+ throw std::out_of_range("dict::at()");
+ return entries[i].udata.second;
+ }
+
+ const T& at(const K &key) const
+ {
+ int hash = mkhash(key);
+ int i = lookup_index(key, hash);
+ if (i < 0)
+ throw std::out_of_range("dict::at()");
+ return entries[i].udata.second;
+ }
+
T& operator[](const K &key)
{
int hash = mkhash(key);
@@ -231,8 +380,47 @@ public:
return entries[i].udata.second;
}
+ void swap(dict<K, T, OPS> &other)
+ {
+ hashtable.swap(other.hashtable);
+ entries.swap(other.entries);
+ std::swap(free_list, other.free_list);
+ std::swap(counter, other.counter);
+ }
+
+ bool operator==(const dict<K, T, OPS> &other) const {
+ if (counter != other.counter)
+ return false;
+ if (counter == 0)
+ return true;
+ if (entries.size() < other.entries.size())
+ for (auto &it : *this) {
+ auto oit = other.find(it.first);
+ if (oit == other.end() || oit->second != it.second)
+ return false;
+ }
+ else
+ for (auto &oit : other) {
+ auto it = find(oit.first);
+ if (it == end() || it->second != oit.second)
+ return false;
+ }
+ return true;
+ }
+
+ bool operator!=(const dict<K, T, OPS> &other) const {
+ return !(*this == other);
+ }
+
+ size_t size() const { return counter; }
+ bool empty() const { return counter == 0; }
+ void clear() { hashtable.clear(); entries.clear(); init(); }
+
iterator begin() { int index = 0; while (index != int(entries.size()) && entries[index].is_free()) index++; return iterator(this, index); }
iterator end() { return iterator(this, entries.size()); }
+
+ const_iterator begin() const { int index = 0; while (index != int(entries.size()) && entries[index].is_free()) index++; return const_iterator(this, index); }
+ const_iterator end() const { return const_iterator(this, entries.size()); }
};
#endif
diff --git a/kernel/log.cc b/kernel/log.cc
index 677884c97..5b18e3d6c 100644
--- a/kernel/log.cc
+++ b/kernel/log.cc
@@ -301,7 +301,7 @@ void log_cell(RTLIL::Cell *cell, std::string indent)
// ---------------------------------------------------
#ifdef YOSYS_ENABLE_COVER
-new_dict<std::string, std::pair<std::string, int>> extra_coverage_data;
+dict<std::string, std::pair<std::string, int>> extra_coverage_data;
void cover_extra(std::string parent, std::string id, bool increment) {
if (extra_coverage_data.count(id) == 0) {
@@ -314,9 +314,9 @@ void cover_extra(std::string parent, std::string id, bool increment) {
extra_coverage_data[id].second++;
}
-new_dict<std::string, std::pair<std::string, int>> get_coverage_data()
+dict<std::string, std::pair<std::string, int>> get_coverage_data()
{
- new_dict<std::string, std::pair<std::string, int>> coverage_data;
+ dict<std::string, std::pair<std::string, int>> coverage_data;
for (auto &it : pass_register) {
std::string key = stringf("passes.%s", it.first.c_str());
diff --git a/kernel/log.h b/kernel/log.h
index eec071991..9bb2b3621 100644
--- a/kernel/log.h
+++ b/kernel/log.h
@@ -106,10 +106,10 @@ struct CoverData {
extern "C" struct CoverData __start_yosys_cover_list[];
extern "C" struct CoverData __stop_yosys_cover_list[];
-extern new_dict<std::string, std::pair<std::string, int>> extra_coverage_data;
+extern dict<std::string, std::pair<std::string, int>> extra_coverage_data;
void cover_extra(std::string parent, std::string id, bool increment = true);
-new_dict<std::string, std::pair<std::string, int>> get_coverage_data();
+dict<std::string, std::pair<std::string, int>> get_coverage_data();
#define cover_list(_id, ...) do { cover(_id); \
std::string r = cover_list_worker(_id, __VA_ARGS__); \
diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc
index 28fdeecdd..05160b869 100644
--- a/kernel/rtlil.cc
+++ b/kernel/rtlil.cc
@@ -30,7 +30,7 @@ YOSYS_NAMESPACE_BEGIN
RTLIL::IdString::destruct_guard_t RTLIL::IdString::destruct_guard;
std::vector<int> RTLIL::IdString::global_refcount_storage_;
std::vector<char*> RTLIL::IdString::global_id_storage_;
-dict<char*, int, RTLIL::IdString::char_ptr_hash, RTLIL::IdString::char_ptr_eq> RTLIL::IdString::global_id_index_;
+dict<char*, int, RTLIL::IdString::char_ptr_ops> RTLIL::IdString::global_id_index_;
std::vector<int> RTLIL::IdString::global_free_idx_list_;
RTLIL::Const::Const()
@@ -242,7 +242,7 @@ RTLIL::Design::Design()
RTLIL::Design::~Design()
{
- for (auto it = modules_.begin(); it != modules_.end(); it++)
+ for (auto it = modules_.begin(); it != modules_.end(); ++it)
delete it->second;
}
@@ -454,13 +454,13 @@ RTLIL::Module::Module()
RTLIL::Module::~Module()
{
- for (auto it = wires_.begin(); it != wires_.end(); it++)
+ for (auto it = wires_.begin(); it != wires_.end(); ++it)
delete it->second;
- for (auto it = memories.begin(); it != memories.end(); it++)
+ for (auto it = memories.begin(); it != memories.end(); ++it)
delete it->second;
- for (auto it = cells_.begin(); it != cells_.end(); it++)
+ for (auto it = cells_.begin(); it != cells_.end(); ++it)
delete it->second;
- for (auto it = processes.begin(); it != processes.end(); it++)
+ for (auto it = processes.begin(); it != processes.end(); ++it)
delete it->second;
}
@@ -2258,7 +2258,7 @@ void RTLIL::SigSpec::unpack() const
#define DJB2(_hash, _value) (_hash) = (((_hash) << 5) + (_hash)) + (_value)
-void RTLIL::SigSpec::hash() const
+void RTLIL::SigSpec::updhash() const
{
RTLIL::SigSpec *that = (RTLIL::SigSpec*)this;
@@ -2721,8 +2721,8 @@ bool RTLIL::SigSpec::operator <(const RTLIL::SigSpec &other) const
if (chunks_.size() != other.chunks_.size())
return chunks_.size() < other.chunks_.size();
- hash();
- other.hash();
+ updhash();
+ other.updhash();
if (hash_ != other.hash_)
return hash_ < other.hash_;
@@ -2753,8 +2753,8 @@ bool RTLIL::SigSpec::operator ==(const RTLIL::SigSpec &other) const
if (chunks_.size() != chunks_.size())
return false;
- hash();
- other.hash();
+ updhash();
+ other.updhash();
if (hash_ != other.hash_)
return false;
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index e684ba4ae..756cca71c 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -124,6 +124,21 @@ namespace RTLIL
}
};
+ struct char_ptr_ops {
+ bool cmp(const char *a, const char *b) const {
+ for (int i = 0; a[i] || b[i]; i++)
+ if (a[i] != b[i])
+ return false;
+ return true;
+ }
+ unsigned int hash(const char *a) const {
+ size_t hash = 5381;
+ while (*a)
+ hash = mkhash(hash, *(a++));
+ return hash;
+ }
+ };
+
static struct destruct_guard_t {
bool ok; // POD, will be initialized to zero
destruct_guard_t() { ok = true; }
@@ -132,7 +147,7 @@ namespace RTLIL
static std::vector<int> global_refcount_storage_;
static std::vector<char*> global_id_storage_;
- static dict<char*, int, char_ptr_hash, char_ptr_eq> global_id_index_;
+ static dict<char*, int, char_ptr_ops> global_id_index_;
static std::vector<int> global_free_idx_list_;
static inline int get_reference(int idx)
@@ -263,6 +278,10 @@ namespace RTLIL
*this = IdString();
}
+ unsigned int hash() const {
+ return index_;
+ }
+
// The following is a helper key_compare class. Instead of for example nodict<Cell*>
// use nodict<Cell*, IdString::compare_ptr_by_name<Cell>> if the order of cells in the
// set has an influence on the algorithm.
@@ -538,6 +557,7 @@ struct RTLIL::SigBit
bool operator <(const RTLIL::SigBit &other) const;
bool operator ==(const RTLIL::SigBit &other) const;
bool operator !=(const RTLIL::SigBit &other) const;
+ unsigned int hash() const;
};
struct RTLIL::SigSpecIterator : public std::iterator<std::input_iterator_tag, RTLIL::SigSpec>
@@ -572,7 +592,7 @@ private:
void pack() const;
void unpack() const;
- void hash() const;
+ void updhash() const;
inline bool packed() const {
return bits_.empty();
@@ -710,6 +730,8 @@ public:
operator std::vector<RTLIL::SigChunk>() const { return chunks(); }
operator std::vector<RTLIL::SigBit>() const { return bits(); }
+ unsigned int hash() const { if (!hash_) updhash(); return hash_; };
+
#ifndef NDEBUG
void check() const;
#else
@@ -1213,6 +1235,12 @@ inline bool RTLIL::SigBit::operator!=(const RTLIL::SigBit &other) const {
return (wire != other.wire) || (wire ? (offset != other.offset) : (data != other.data));
}
+inline unsigned int RTLIL::SigBit::hash() const {
+ if (wire)
+ return wire->name.hash() * 33 + offset;
+ return data;
+}
+
inline RTLIL::SigBit &RTLIL::SigSpecIterator::operator*() const {
return (*sig_p)[index];
}
diff --git a/kernel/yosys.h b/kernel/yosys.h
index b14852eaf..9b76d28c6 100644
--- a/kernel/yosys.h
+++ b/kernel/yosys.h
@@ -124,7 +124,6 @@
YOSYS_NAMESPACE_BEGIN
-#define dict std::unordered_map
#define nodict std::unordered_set
#include "kernel/hashmap.h"
using std::vector;
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-03 21:11:06 +0000