diff options
author | Clifford Wolf <clifford@clifford.at> | 2019-03-15 00:18:31 +0100 |
---|---|---|
committer | Clifford Wolf <clifford@clifford.at> | 2019-03-15 00:18:31 +0100 |
commit | d1985f6a223d18e0ae8545a620e4117fd4ca23b3 (patch) | |
tree | 2a47da00939f3e50ef8f3ba4a17f3b0ca63d6f93 /passes | |
parent | 27a5d9c91e44dd04fa45e1e2aeff8c6d1cd50872 (diff) | |
download | yosys-d1985f6a223d18e0ae8545a620e4117fd4ca23b3.tar.gz yosys-d1985f6a223d18e0ae8545a620e4117fd4ca23b3.tar.bz2 yosys-d1985f6a223d18e0ae8545a620e4117fd4ca23b3.zip |
Improvements in "mutate" list-reduce algorithm
Signed-off-by: Clifford Wolf <clifford@clifford.at>
Diffstat (limited to 'passes')
-rw-r--r-- | passes/sat/mutate.cc | 49 |
1 files changed, 36 insertions, 13 deletions
diff --git a/passes/sat/mutate.cc b/passes/sat/mutate.cc index 6b9eb3c04..4c103dcd5 100644 --- a/passes/sat/mutate.cc +++ b/passes/sat/mutate.cc @@ -133,7 +133,7 @@ struct xs128_t } }; -struct mutate_leaf_queue_t +struct mutate_queue_t { pool<mutate_t*, hash_ptr_ops> db; @@ -181,7 +181,7 @@ struct mutate_leaf_queue_t }; template <typename K, typename T> -struct mutate_inner_queue_t +struct mutate_chain_queue_t { dict<K, T> db; @@ -203,6 +203,29 @@ struct mutate_inner_queue_t } }; +template <typename K, typename T> +struct mutate_once_queue_t +{ + dict<K, T> db; + + mutate_t *pick(xs128_t &rng, dict<string, int> &coverdb, const mutate_opts_t &opts) { + while (!db.empty()) { + int i = rng(GetSize(db)); + auto it = db.element(i); + mutate_t *m = it->second.pick(rng, coverdb, opts); + db.erase(it); + if (m != nullptr) + return m; + } + return nullptr; + } + + template<typename... Args> + void add(mutate_t *m, K key, Args... args) { + db[key].add(m, args...); + } +}; + void database_reduce(std::vector<mutate_t> &database, const mutate_opts_t &opts, int N, xs128_t &rng) { std::vector<mutate_t> new_database; @@ -214,26 +237,26 @@ void database_reduce(std::vector<mutate_t> &database, const mutate_opts_t &opts, if (N >= GetSize(database)) return; - mutate_inner_queue_t<IdString, mutate_leaf_queue_t> primary_queue_wire; - mutate_inner_queue_t<pair<IdString, int>, mutate_leaf_queue_t> primary_queue_bit; - mutate_inner_queue_t<IdString, mutate_leaf_queue_t> primary_queue_cell; - mutate_inner_queue_t<string, mutate_leaf_queue_t> primary_queue_src; + mutate_once_queue_t<tuple<IdString, IdString>, mutate_queue_t> primary_queue_wire; + mutate_once_queue_t<tuple<IdString, IdString, int>, mutate_queue_t> primary_queue_bit; + mutate_once_queue_t<tuple<IdString, IdString>, mutate_queue_t> primary_queue_cell; + mutate_once_queue_t<string, mutate_queue_t> primary_queue_src; - mutate_inner_queue_t<IdString, mutate_inner_queue_t<IdString, mutate_leaf_queue_t>> primary_queue_module_wire; - mutate_inner_queue_t<IdString, mutate_inner_queue_t<pair<IdString, int>, mutate_leaf_queue_t>> primary_queue_module_bit; - mutate_inner_queue_t<IdString, mutate_inner_queue_t<IdString, mutate_leaf_queue_t>> primary_queue_module_cell; - mutate_inner_queue_t<IdString, mutate_inner_queue_t<string, mutate_leaf_queue_t>> primary_queue_module_src; + mutate_chain_queue_t<IdString, mutate_once_queue_t<IdString, mutate_queue_t>> primary_queue_module_wire; + mutate_chain_queue_t<IdString, mutate_once_queue_t<pair<IdString, int>, mutate_queue_t>> primary_queue_module_bit; + mutate_chain_queue_t<IdString, mutate_once_queue_t<IdString, mutate_queue_t>> primary_queue_module_cell; + mutate_chain_queue_t<IdString, mutate_once_queue_t<string, mutate_queue_t>> primary_queue_module_src; for (auto &m : database) { if (!m.wire.empty()) { - primary_queue_wire.add(&m, m.wire); - primary_queue_bit.add(&m, pair<IdString, int>(m.wire, m.wirebit)); + primary_queue_wire.add(&m, tuple<IdString, IdString>(m.module, m.wire)); + primary_queue_bit.add(&m, tuple<IdString, IdString, int>(m.module, m.wire, m.wirebit)); primary_queue_module_wire.add(&m, m.module, m.wire); primary_queue_module_bit.add(&m, m.module, pair<IdString, int>(m.wire, m.wirebit)); } - primary_queue_cell.add(&m, m.cell); + primary_queue_cell.add(&m, tuple<IdString, IdString>(m.module, m.cell)); primary_queue_module_cell.add(&m, m.module, m.cell); for (auto &s : m.src) { |