diff options
author | Clifford Wolf <clifford@clifford.at> | 2014-12-28 17:51:16 +0100 |
---|---|---|
committer | Clifford Wolf <clifford@clifford.at> | 2014-12-28 17:51:16 +0100 |
commit | 3da46d3437f076c27cef5121f26a1fa151dde1f6 (patch) | |
tree | 2116520ceba65cb28603ef6685b07d25bdc9a47c | |
parent | 3e8e483233321d7efadbb78ba746a7797c102a3a (diff) |
Renamed hashmap.h to hashlib.h, some related improvements
-rw-r--r-- | kernel/hashlib.h (renamed from kernel/hashmap.h) | 79 | ||||
-rw-r--r-- | kernel/modtools.h | 2 | ||||
-rw-r--r-- | kernel/rtlil.cc | 18 | ||||
-rw-r--r-- | kernel/rtlil.h | 31 | ||||
-rw-r--r-- | kernel/yosys.h | 36 | ||||
-rw-r--r-- | passes/cmds/delete.cc | 4 | ||||
-rw-r--r-- | passes/cmds/splitnets.cc | 2 | ||||
-rw-r--r-- | passes/opt/opt_clean.cc | 2 | ||||
-rw-r--r-- | passes/opt/opt_const.cc | 2 | ||||
-rw-r--r-- | passes/opt/opt_share.cc | 2 | ||||
-rw-r--r-- | passes/opt/share.cc | 4 |
11 files changed, 124 insertions, 58 deletions
diff --git a/kernel/hashmap.h b/kernel/hashlib.h index 431e8122..a8d32086 100644 --- a/kernel/hashmap.h +++ b/kernel/hashlib.h @@ -1,29 +1,23 @@ -/* - * 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 - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - * - */ - -#ifndef YOSYS_HASHMAP_H +// This is free and unencumbered software released into the public domain. +// +// Anyone is free to copy, modify, publish, use, compile, sell, or +// distribute this software, either in source code form or as a compiled +// binary, for any purpose, commercial or non-commercial, and by any +// means. + +// ------------------------------------------------------- +// Written by Clifford Wolf <clifford@clifford.at> in 2014 +// ------------------------------------------------------- + +#ifndef HASHLIB_H #include <stdexcept> #include <string> #include <vector> -#define YOSYS_HASHTABLE_SIZE_FACTOR 3 +namespace hashlib { + +#define HASHLIB_SIZE_FACTOR 3 // The XOR version of DJB2 // (traditionally 5381 is used as starting value for the djb2 hash) @@ -32,7 +26,7 @@ inline unsigned int mkhash(unsigned int a, unsigned int b) { } // The ADD version of DJB2 -// (use this version as last call for cache locality in b) +// (use this version for cache locality in b) inline unsigned int mkhash_add(unsigned int a, unsigned int b) { return ((a << 5) + a) + b; } @@ -47,10 +41,11 @@ template<typename T> struct hash_ops { }; template<> struct hash_ops<int> { - bool cmp(int a, int b) const { + template<typename T> + bool cmp(T a, T b) const { return a == b; } - unsigned int hash(int a) const { + unsigned int hash(unsigned int a) const { return a; } }; @@ -97,7 +92,7 @@ struct hash_obj_ops { } template<typename T> unsigned int hash(const T *a) const { - return a->name.hash(); + return a->hash(); } }; @@ -165,9 +160,9 @@ class dict entries.clear(); counter = other.size(); - int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * counter); + int new_size = hashtable_size(HASHLIB_SIZE_FACTOR * counter); hashtable.resize(new_size); - new_size = new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1; + new_size = new_size / HASHLIB_SIZE_FACTOR + 1; entries.reserve(new_size); for (auto &it : other) @@ -243,9 +238,9 @@ class dict if (free_list < 0) { int i = entries.size(); - int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * entries.size()); + int new_size = hashtable_size(HASHLIB_SIZE_FACTOR * entries.size()); hashtable.resize(new_size); - entries.resize(new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1); + entries.resize(new_size / HASHLIB_SIZE_FACTOR + 1); entries[i].udata = value; entries[i].set_next_used(0); counter++; @@ -345,14 +340,14 @@ public: insert(*first); } - iterator insert(const std::pair<K, T> &value) + std::pair<iterator, bool> insert(const std::pair<K, T> &value) { int hash = mkhash(value.first); int i = lookup_index(value.first, hash); if (i >= 0) - return iterator(this, i); + return std::pair<iterator, bool>(iterator(this, i), false); i = insert_at(value, hash); - return iterator(this, i); + return std::pair<iterator, bool>(iterator(this, i), true); } void erase(const K &key) @@ -497,9 +492,9 @@ class pool entries.clear(); counter = other.size(); - int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * counter); + int new_size = hashtable_size(HASHLIB_SIZE_FACTOR * counter); hashtable.resize(new_size); - new_size = new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1; + new_size = new_size / HASHLIB_SIZE_FACTOR + 1; entries.reserve(new_size); for (auto &it : other) @@ -575,9 +570,9 @@ class pool if (free_list < 0) { int i = entries.size(); - int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * entries.size()); + int new_size = hashtable_size(HASHLIB_SIZE_FACTOR * entries.size()); hashtable.resize(new_size); - entries.resize(new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1); + entries.resize(new_size / HASHLIB_SIZE_FACTOR + 1); entries[i].key = key; entries[i].set_next_used(0); counter++; @@ -677,14 +672,14 @@ public: insert(*first); } - iterator insert(const K &key) + std::pair<iterator, bool> insert(const K &key) { int hash = mkhash(key); int i = lookup_index(key, hash); if (i >= 0) - return iterator(this, i); + return std::pair<iterator, bool>(iterator(this, i), false); i = insert_at(key, hash); - return iterator(this, i); + return std::pair<iterator, bool>(iterator(this, i), true); } void erase(const K &key) @@ -695,8 +690,8 @@ public: void erase(const iterator it) { - int hash = mkhash(it->first); - do_erase(it->first, hash); + int hash = mkhash(*it); + do_erase(*it, hash); } int count(const K &key) const @@ -774,4 +769,6 @@ public: const_iterator end() const { return const_iterator(this, entries.size()); } }; +} /* namespace hashlib */ + #endif diff --git a/kernel/modtools.h b/kernel/modtools.h index 56362dbc..558cc08b 100644 --- a/kernel/modtools.h +++ b/kernel/modtools.h @@ -270,7 +270,7 @@ struct ModWalker dict<RTLIL::SigBit, pool<PortBit>> signal_consumers; pool<RTLIL::SigBit> signal_inputs, signal_outputs; - dict<RTLIL::Cell*, pool<RTLIL::SigBit>, hash_obj_ops> cell_outputs, cell_inputs; + dict<RTLIL::Cell*, pool<RTLIL::SigBit>> cell_outputs, cell_inputs; void add_wire(RTLIL::Wire *wire) { diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc index 23edccee..c262801d 100644 --- a/kernel/rtlil.cc +++ b/kernel/rtlil.cc @@ -236,6 +236,9 @@ void RTLIL::Selection::optimize(RTLIL::Design *design) RTLIL::Design::Design() { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; + refcount_modules_ = 0; selection_stack.push_back(RTLIL::Selection()); } @@ -447,6 +450,9 @@ std::vector<RTLIL::Module*> RTLIL::Design::selected_whole_modules_warn() const RTLIL::Module::Module() { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; + design = nullptr; refcount_wires_ = 0; refcount_cells_ = 0; @@ -1132,7 +1138,7 @@ namespace { struct DeleteWireWorker { RTLIL::Module *module; - const pool<RTLIL::Wire*, hash_obj_ops> *wires_p; + const pool<RTLIL::Wire*> *wires_p; void operator()(RTLIL::SigSpec &sig) { std::vector<RTLIL::SigChunk> chunks = sig; @@ -1146,7 +1152,7 @@ namespace { }; } -void RTLIL::Module::remove(const pool<RTLIL::Wire*, hash_obj_ops> &wires) +void RTLIL::Module::remove(const pool<RTLIL::Wire*> &wires) { log_assert(refcount_wires_ == 0); @@ -1735,6 +1741,9 @@ RTLIL::Cell* RTLIL::Module::addDlatchsrGate(RTLIL::IdString name, RTLIL::SigSpec RTLIL::Wire::Wire() { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; + module = nullptr; width = 1; start_offset = 0; @@ -1746,12 +1755,17 @@ RTLIL::Wire::Wire() RTLIL::Memory::Memory() { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; + width = 1; size = 0; } RTLIL::Cell::Cell() : module(nullptr) { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; } bool RTLIL::Cell::hasPort(RTLIL::IdString portname) const diff --git a/kernel/rtlil.h b/kernel/rtlil.h index cb654c3a..8cf70799 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -708,8 +708,14 @@ struct RTLIL::Selection struct RTLIL::Monitor { - RTLIL::IdString name; - Monitor() { name = stringf("$%d", autoidx++); } + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + + Monitor() { + unsigned int hashidx_count = 0; + hashidx_ = hashidx_count++; + } + virtual ~Monitor() { } virtual void notify_module_add(RTLIL::Module*) { } virtual void notify_module_del(RTLIL::Module*) { } @@ -721,7 +727,10 @@ struct RTLIL::Monitor struct RTLIL::Design { - pool<RTLIL::Monitor*, hash_obj_ops> monitors; + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + + pool<RTLIL::Monitor*> monitors; dict<std::string, std::string> scratchpad; int refcount_modules_; @@ -802,13 +811,16 @@ struct RTLIL::Design struct RTLIL::Module { + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + protected: void add(RTLIL::Wire *wire); void add(RTLIL::Cell *cell); public: RTLIL::Design *design; - pool<RTLIL::Monitor*, hash_obj_ops> monitors; + pool<RTLIL::Monitor*> monitors; int refcount_wires_; int refcount_cells_; @@ -862,7 +874,7 @@ public: RTLIL::ObjRange<RTLIL::Cell*> cells() { return RTLIL::ObjRange<RTLIL::Cell*>(&cells_, &refcount_cells_); } // Removing wires is expensive. If you have to remove wires, remove them all at once. - void remove(const pool<RTLIL::Wire*, hash_obj_ops> &wires); + void remove(const pool<RTLIL::Wire*> &wires); void remove(RTLIL::Cell *cell); void rename(RTLIL::Wire *wire, RTLIL::IdString new_name); @@ -1031,6 +1043,9 @@ public: struct RTLIL::Wire { + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + protected: // use module->addWire() and module->remove() to create or destroy wires friend struct RTLIL::Module; @@ -1051,6 +1066,9 @@ public: struct RTLIL::Memory { + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + Memory(); RTLIL::IdString name; @@ -1060,6 +1078,9 @@ struct RTLIL::Memory struct RTLIL::Cell { + unsigned int hashidx_; + unsigned int hash() const { return hashidx_; } + protected: // use module->addCell() and module->remove() to create or destroy cells friend struct RTLIL::Module; diff --git a/kernel/yosys.h b/kernel/yosys.h index d47f3a95..b653941c 100644 --- a/kernel/yosys.h +++ b/kernel/yosys.h @@ -124,17 +124,51 @@ YOSYS_NAMESPACE_BEGIN -#include "kernel/hashmap.h" +#include "kernel/hashlib.h" using std::vector; +using std::string; +using hashlib::mkhash; +using hashlib::mkhash_add; +using hashlib::hash_ops; +using hashlib::hash_cstr_ops; +using hashlib::hash_ptr_ops; +using hashlib::hash_obj_ops; +using hashlib::dict; +using hashlib::pool; namespace RTLIL { struct IdString; + struct Const; struct SigBit; struct SigSpec; struct Wire; struct Cell; + struct Module; + struct Design; + struct Monitor; } +using RTLIL::IdString; +using RTLIL::Const; +using RTLIL::SigBit; +using RTLIL::SigSpec; +using RTLIL::Wire; +using RTLIL::Cell; +using RTLIL::Module; +using RTLIL::Design; + +template<> struct hash_ops<RTLIL::Wire*> : hash_obj_ops {}; +template<> struct hash_ops<RTLIL::Cell*> : hash_obj_ops {}; +template<> struct hash_ops<RTLIL::Module*> : hash_obj_ops {}; +template<> struct hash_ops<RTLIL::Design*> : hash_obj_ops {}; +template<> struct hash_ops<RTLIL::Monitor*> : hash_obj_ops {}; + +template<> struct hash_ops<const RTLIL::Wire*> : hash_obj_ops {}; +template<> struct hash_ops<const RTLIL::Cell*> : hash_obj_ops {}; +template<> struct hash_ops<const RTLIL::Module*> : hash_obj_ops {}; +template<> struct hash_ops<const RTLIL::Design*> : hash_obj_ops {}; +template<> struct hash_ops<const RTLIL::Monitor*> : hash_obj_ops {}; + std::string stringf(const char *fmt, ...) YS_ATTRIBUTE(format(printf, 1, 2)); std::string vstringf(const char *fmt, va_list ap); int readsome(std::istream &f, char *s, int n); diff --git a/passes/cmds/delete.cc b/passes/cmds/delete.cc index 5bf2a36b..b4362887 100644 --- a/passes/cmds/delete.cc +++ b/passes/cmds/delete.cc @@ -91,8 +91,8 @@ struct DeletePass : public Pass { continue; } - pool<RTLIL::Wire*, hash_obj_ops> delete_wires; - pool<RTLIL::Cell*, hash_obj_ops> delete_cells; + pool<RTLIL::Wire*> delete_wires; + pool<RTLIL::Cell*> delete_cells; pool<RTLIL::IdString> delete_procs; pool<RTLIL::IdString> delete_mems; diff --git a/passes/cmds/splitnets.cc b/passes/cmds/splitnets.cc index 2523c166..d4e721a5 100644 --- a/passes/cmds/splitnets.cc +++ b/passes/cmds/splitnets.cc @@ -176,7 +176,7 @@ struct SplitnetsPass : public Pass { module->rewrite_sigspecs(worker); - pool<RTLIL::Wire*, hash_obj_ops> delete_wires; + pool<RTLIL::Wire*> delete_wires; for (auto &it : worker.splitmap) delete_wires.insert(it.first); module->remove(delete_wires); diff --git a/passes/opt/opt_clean.cc b/passes/opt/opt_clean.cc index b387e038..b9ff5d30 100644 --- a/passes/opt/opt_clean.cc +++ b/passes/opt/opt_clean.cc @@ -262,7 +262,7 @@ void rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbos } - pool<RTLIL::Wire*, hash_obj_ops> del_wires; + pool<RTLIL::Wire*> del_wires; int del_wires_count = 0; for (auto wire : maybe_del_wires) diff --git a/passes/opt/opt_const.cc b/passes/opt/opt_const.cc index f78ea6cc..7f800bde 100644 --- a/passes/opt/opt_const.cc +++ b/passes/opt/opt_const.cc @@ -199,7 +199,7 @@ void replace_const_cells(RTLIL::Design *design, RTLIL::Module *module, bool cons dict<RTLIL::SigSpec, RTLIL::SigSpec> invert_map; TopoSort<RTLIL::Cell*, RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell>> cells; - dict<RTLIL::Cell*, std::set<RTLIL::SigBit>, hash_obj_ops> cell_to_inbit; + dict<RTLIL::Cell*, std::set<RTLIL::SigBit>> cell_to_inbit; dict<RTLIL::SigBit, std::set<RTLIL::Cell*>> outbit_to_cell; for (auto cell : module->cells()) diff --git a/passes/opt/opt_share.cc b/passes/opt/opt_share.cc index 91bfd58a..c581b749 100644 --- a/passes/opt/opt_share.cc +++ b/passes/opt/opt_share.cc @@ -41,7 +41,7 @@ struct OptShareWorker CellTypes ct; int total_count; #ifdef USE_CELL_HASH_CACHE - dict<const RTLIL::Cell*, std::string, hash_obj_ops> cell_hash_cache; + dict<const RTLIL::Cell*, std::string> cell_hash_cache; #endif #ifdef USE_CELL_HASH_CACHE diff --git a/passes/opt/share.cc b/passes/opt/share.cc index 41a4a690..0d1a54d9 100644 --- a/passes/opt/share.cc +++ b/passes/opt/share.cc @@ -731,7 +731,7 @@ struct ShareWorker return forbidden_controls_cache.at(cell); pool<ModWalker::PortBit> pbits; - pool<RTLIL::Cell*, hash_obj_ops> consumer_cells; + pool<RTLIL::Cell*> consumer_cells; modwalker.get_consumers(pbits, modwalker.cell_outputs[cell]); @@ -803,7 +803,7 @@ struct ShareWorker return activation_patterns_cache.at(cell); const pool<RTLIL::SigBit> &cell_out_bits = modwalker.cell_outputs[cell]; - pool<RTLIL::Cell*, hash_obj_ops> driven_cells, driven_data_muxes; + pool<RTLIL::Cell*> driven_cells, driven_data_muxes; for (auto &bit : cell_out_bits) { |