From 6c8b0a5fd138d19b47191400f020c2472944f826 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 27 Dec 2014 12:02:57 +0100 Subject: [PATCH] More dict/pool related changes --- kernel/hashmap.h | 8 ++++ kernel/modtools.h | 81 +++++++++++++++++++++-------------- kernel/rtlil.cc | 16 +++---- kernel/rtlil.h | 4 +- passes/memory/memory_share.cc | 4 +- passes/opt/share.cc | 18 ++++---- 6 files changed, 77 insertions(+), 54 deletions(-) diff --git a/kernel/hashmap.h b/kernel/hashmap.h index 729b4916c..431e8122e 100644 --- a/kernel/hashmap.h +++ b/kernel/hashmap.h @@ -25,10 +25,18 @@ #define YOSYS_HASHTABLE_SIZE_FACTOR 3 +// The XOR version of DJB2 +// (traditionally 5381 is used as starting value for the djb2 hash) inline unsigned int mkhash(unsigned int a, unsigned int b) { return ((a << 5) + a) ^ b; } +// The ADD version of DJB2 +// (use this version as last call for cache locality in b) +inline unsigned int mkhash_add(unsigned int a, unsigned int b) { + return ((a << 5) + a) + b; +} + template struct hash_ops { bool cmp(const T &a, const T &b) const { return a == b; diff --git a/kernel/modtools.h b/kernel/modtools.h index e3020ae3c..439699eaf 100644 --- a/kernel/modtools.h +++ b/kernel/modtools.h @@ -33,6 +33,7 @@ struct ModIndex : public RTLIL::Monitor RTLIL::IdString port; int offset; + PortInfo() : cell(), port(), offset() { } PortInfo(RTLIL::Cell* _c, RTLIL::IdString _p, int _o) : cell(_c), port(_p), offset(_o) { } bool operator<(const PortInfo &other) const { @@ -42,19 +43,27 @@ struct ModIndex : public RTLIL::Monitor return offset < other.offset; return port < other.port; } + + bool operator==(const PortInfo &other) const { + return cell == other.cell && port == other.port && offset == other.offset; + } + + unsigned int hash() const { + return mkhash_add(mkhash(cell->name.hash(), port.hash()), offset); + } }; struct SigBitInfo { bool is_input, is_output; - std::set ports; + pool ports; SigBitInfo() : is_input(false), is_output(false) { } }; SigMap sigmap; RTLIL::Module *module; - std::map database; + dict database; bool auto_reload_module; void port_add(RTLIL::Cell *cell, RTLIL::IdString port, const RTLIL::SigSpec &sig) @@ -168,9 +177,9 @@ struct ModIndex : public RTLIL::Monitor return info->is_output; } - std::set &query_ports(RTLIL::SigBit bit) + pool &query_ports(RTLIL::SigBit bit) { - static std::set empty_result_set; + static pool empty_result_set; SigBitInfo *info = query(bit); if (info == nullptr) return empty_result_set; @@ -193,6 +202,14 @@ struct ModWalker return port < other.port; return offset < other.offset; } + + bool operator==(const PortBit &other) const { + return cell == other.cell && port == other.port && offset == other.offset; + } + + unsigned int hash() const { + return mkhash_add(mkhash(cell->name.hash(), port.hash()), offset); + } }; RTLIL::Design *design; @@ -201,11 +218,11 @@ struct ModWalker CellTypes ct; SigMap sigmap; - std::map> signal_drivers; - std::map> signal_consumers; - std::set signal_inputs, signal_outputs; + dict> signal_drivers; + dict> signal_consumers; + pool signal_inputs, signal_outputs; - std::map> cell_outputs, cell_inputs; + dict, hash_obj_ops> cell_outputs, cell_inputs; void add_wire(RTLIL::Wire *wire) { @@ -286,11 +303,11 @@ struct ModWalker // get_* methods -- single RTLIL::SigBit template - inline bool get_drivers(std::set &result, RTLIL::SigBit bit) const + inline bool get_drivers(pool &result, RTLIL::SigBit bit) const { bool found = false; if (signal_drivers.count(bit)) { - const std::set &r = signal_drivers.at(bit); + const pool &r = signal_drivers.at(bit); result.insert(r.begin(), r.end()); found = true; } @@ -298,11 +315,11 @@ struct ModWalker } template - inline bool get_consumers(std::set &result, RTLIL::SigBit bit) const + inline bool get_consumers(pool &result, RTLIL::SigBit bit) const { bool found = false; if (signal_consumers.count(bit)) { - const std::set &r = signal_consumers.at(bit); + const pool &r = signal_consumers.at(bit); result.insert(r.begin(), r.end()); found = true; } @@ -310,7 +327,7 @@ struct ModWalker } template - inline bool get_inputs(std::set &result, RTLIL::SigBit bit) const + inline bool get_inputs(pool &result, RTLIL::SigBit bit) const { bool found = false; if (signal_inputs.count(bit)) @@ -319,7 +336,7 @@ struct ModWalker } template - inline bool get_outputs(std::set &result, RTLIL::SigBit bit) const + inline bool get_outputs(pool &result, RTLIL::SigBit bit) const { bool found = false; if (signal_outputs.count(bit)) @@ -330,12 +347,12 @@ struct ModWalker // get_* methods -- container of RTLIL::SigBit's (always by reference) template - inline bool get_drivers(std::set &result, const T &bits) const + inline bool get_drivers(pool &result, const T &bits) const { bool found = false; for (RTLIL::SigBit bit : bits) if (signal_drivers.count(bit)) { - const std::set &r = signal_drivers.at(bit); + const pool &r = signal_drivers.at(bit); result.insert(r.begin(), r.end()); found = true; } @@ -343,12 +360,12 @@ struct ModWalker } template - inline bool get_consumers(std::set &result, const T &bits) const + inline bool get_consumers(pool &result, const T &bits) const { bool found = false; for (RTLIL::SigBit bit : bits) if (signal_consumers.count(bit)) { - const std::set &r = signal_consumers.at(bit); + const pool &r = signal_consumers.at(bit); result.insert(r.begin(), r.end()); found = true; } @@ -356,7 +373,7 @@ struct ModWalker } template - inline bool get_inputs(std::set &result, const T &bits) const + inline bool get_inputs(pool &result, const T &bits) const { bool found = false; for (RTLIL::SigBit bit : bits) @@ -366,7 +383,7 @@ struct ModWalker } template - inline bool get_outputs(std::set &result, const T &bits) const + inline bool get_outputs(pool &result, const T &bits) const { bool found = false; for (RTLIL::SigBit bit : bits) @@ -377,25 +394,25 @@ struct ModWalker // get_* methods -- call by RTLIL::SigSpec (always by value) - bool get_drivers(std::set &result, RTLIL::SigSpec signal) const + bool get_drivers(pool &result, RTLIL::SigSpec signal) const { std::vector bits = sigmap(signal); return get_drivers(result, bits); } - bool get_consumers(std::set &result, RTLIL::SigSpec signal) const + bool get_consumers(pool &result, RTLIL::SigSpec signal) const { std::vector bits = sigmap(signal); return get_consumers(result, bits); } - bool get_inputs(std::set &result, RTLIL::SigSpec signal) const + bool get_inputs(pool &result, RTLIL::SigSpec signal) const { std::vector bits = sigmap(signal); return get_inputs(result, bits); } - bool get_outputs(std::set &result, RTLIL::SigSpec signal) const + bool get_outputs(pool &result, RTLIL::SigSpec signal) const { std::vector bits = sigmap(signal); return get_outputs(result, bits); @@ -405,47 +422,47 @@ struct ModWalker template inline bool has_drivers(const T &sig) const { - std::set result; + pool result; return get_drivers(result, sig); } template inline bool has_consumers(const T &sig) const { - std::set result; + pool result; return get_consumers(result, sig); } template inline bool has_inputs(const T &sig) const { - std::set result; + pool result; return get_inputs(result, sig); } template inline bool has_outputs(const T &sig) const { - std::set result; + pool result; return get_outputs(result, sig); } // has_* methods -- call by value inline bool has_drivers(RTLIL::SigSpec sig) const { - std::set result; + pool result; return get_drivers(result, sig); } inline bool has_consumers(RTLIL::SigSpec sig) const { - std::set result; + pool result; return get_consumers(result, sig); } inline bool has_inputs(RTLIL::SigSpec sig) const { - std::set result; + pool result; return get_inputs(result, sig); } inline bool has_outputs(RTLIL::SigSpec sig) const { - std::set result; + pool result; return get_outputs(result, sig); } }; diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc index 0114cbd60..23edcceef 100644 --- a/kernel/rtlil.cc +++ b/kernel/rtlil.cc @@ -2256,8 +2256,6 @@ void RTLIL::SigSpec::unpack() const that->hash_ = 0; } -#define DJB2(_hash, _value) (_hash) = (((_hash) << 5) + (_hash)) + (_value) - void RTLIL::SigSpec::updhash() const { RTLIL::SigSpec *that = (RTLIL::SigSpec*)this; @@ -2272,11 +2270,11 @@ void RTLIL::SigSpec::updhash() const for (auto &c : that->chunks_) if (c.wire == NULL) { for (auto &v : c.data) - DJB2(that->hash_, v); + that->hash_ = mkhash(that->hash_, v); } else { - DJB2(that->hash_, c.wire->name.index_); - DJB2(that->hash_, c.offset); - DJB2(that->hash_, c.width); + that->hash_ = mkhash(that->hash_, c.wire->name.index_); + that->hash_ = mkhash(that->hash_, c.offset); + that->hash_ = mkhash(that->hash_, c.width); } if (that->hash_ == 0) @@ -2378,7 +2376,7 @@ void RTLIL::SigSpec::remove(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other void RTLIL::SigSpec::remove2(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other) { - pool pattern_bits = pattern.to_sigbit_nodict(); + pool pattern_bits = pattern.to_sigbit_pool(); remove2(pattern_bits, other); } @@ -2439,7 +2437,7 @@ void RTLIL::SigSpec::remove2(const pool &pattern, RTLIL::SigSpec RTLIL::SigSpec RTLIL::SigSpec::extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other) const { - pool pattern_bits = pattern.to_sigbit_nodict(); + pool pattern_bits = pattern.to_sigbit_pool(); return extract(pattern_bits, other); } @@ -2943,7 +2941,7 @@ std::set RTLIL::SigSpec::to_sigbit_set() const return sigbits; } -pool RTLIL::SigSpec::to_sigbit_nodict() const +pool RTLIL::SigSpec::to_sigbit_pool() const { cover("kernel.rtlil.sigspec.to_sigbit_pool"); diff --git a/kernel/rtlil.h b/kernel/rtlil.h index c50a58619..cb654c3af 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -654,7 +654,7 @@ public: bool match(std::string pattern) const; std::set to_sigbit_set() const; - pool to_sigbit_nodict() const; + pool to_sigbit_pool() const; std::vector to_sigbit_vector() const; std::map to_sigbit_map(const RTLIL::SigSpec &other) const; dict to_sigbit_dict(const RTLIL::SigSpec &other) const; @@ -1176,7 +1176,7 @@ inline bool RTLIL::SigBit::operator!=(const RTLIL::SigBit &other) const { inline unsigned int RTLIL::SigBit::hash() const { if (wire) - return wire->name.hash() * 33 + offset; + return mkhash_add(wire->name.hash(), offset); return data; } diff --git a/passes/memory/memory_share.cc b/passes/memory/memory_share.cc index f77b304b4..ec8df7598 100644 --- a/passes/memory/memory_share.cc +++ b/passes/memory/memory_share.cc @@ -560,13 +560,13 @@ struct MemoryShareWorker while (!bits_queue.empty()) { - std::set portbits; + pool portbits; modwalker.get_drivers(portbits, bits_queue); bits_queue.clear(); for (auto &pbit : portbits) if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) { - std::set &cell_inputs = modwalker.cell_inputs[pbit.cell]; + pool &cell_inputs = modwalker.cell_inputs[pbit.cell]; bits_queue.insert(cell_inputs.begin(), cell_inputs.end()); sat_cells.insert(pbit.cell); } diff --git a/passes/opt/share.cc b/passes/opt/share.cc index cb7510553..41a4a6908 100644 --- a/passes/opt/share.cc +++ b/passes/opt/share.cc @@ -75,7 +75,7 @@ struct ShareWorker for (auto &it : module->cells_) if (!fwd_ct.cell_known(it.second->type)) { - std::set &bits = modwalker.cell_inputs[it.second]; + pool &bits = modwalker.cell_inputs[it.second]; queue_bits.insert(bits.begin(), bits.end()); } @@ -83,19 +83,19 @@ struct ShareWorker while (!queue_bits.empty()) { - std::set portbits; + pool portbits; modwalker.get_drivers(portbits, queue_bits); queue_bits.clear(); for (auto &pbit : portbits) { if (pbit.cell->type == "$mux" || pbit.cell->type == "$pmux") { - std::set bits = modwalker.sigmap(pbit.cell->getPort("\\S")).to_sigbit_set(); + pool bits = modwalker.sigmap(pbit.cell->getPort("\\S")).to_sigbit_pool(); terminal_bits.insert(bits.begin(), bits.end()); queue_bits.insert(bits.begin(), bits.end()); visited_cells.insert(pbit.cell); } if (fwd_ct.cell_known(pbit.cell->type) && visited_cells.count(pbit.cell) == 0) { - std::set &bits = modwalker.cell_inputs[pbit.cell]; + pool &bits = modwalker.cell_inputs[pbit.cell]; terminal_bits.insert(bits.begin(), bits.end()); queue_bits.insert(bits.begin(), bits.end()); visited_cells.insert(pbit.cell); @@ -730,8 +730,8 @@ struct ShareWorker if (forbidden_controls_cache.count(cell)) return forbidden_controls_cache.at(cell); - std::set pbits; - std::set consumer_cells; + pool pbits; + pool consumer_cells; modwalker.get_consumers(pbits, modwalker.cell_outputs[cell]); @@ -802,8 +802,8 @@ struct ShareWorker if (activation_patterns_cache.count(cell)) return activation_patterns_cache.at(cell); - const std::set &cell_out_bits = modwalker.cell_outputs[cell]; - std::set driven_cells, driven_data_muxes; + const pool &cell_out_bits = modwalker.cell_outputs[cell]; + pool driven_cells, driven_data_muxes; for (auto &bit : cell_out_bits) { @@ -1196,7 +1196,7 @@ struct ShareWorker while (!bits_queue.empty()) { - std::set portbits; + pool portbits; modwalker.get_drivers(portbits, bits_queue); bits_queue.clear(); -- 2.30.2