From 9f30d7f843f224942dad7ce0ef90d3a99ac05036 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 10 Mar 2020 16:13:44 -0700 Subject: [PATCH] opt_merge: speedup --- passes/opt/opt_merge.cc | 234 ++++++++++++++++-------------------- tests/opt/opt_merge_init.ys | 28 +++++ tests/opt/opt_merge_keep.ys | 64 ++++++++++ 3 files changed, 194 insertions(+), 132 deletions(-) create mode 100644 tests/opt/opt_merge_keep.ys diff --git a/passes/opt/opt_merge.cc b/passes/opt/opt_merge.cc index 8823a9061..270e49a96 100644 --- a/passes/opt/opt_merge.cc +++ b/passes/opt/opt_merge.cc @@ -26,7 +26,6 @@ #include #include -#define USE_CELL_HASH_CACHE USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN @@ -41,9 +40,7 @@ struct OptMergeWorker CellTypes ct; int total_count; -#ifdef USE_CELL_HASH_CACHE - dict cell_hash_cache; -#endif + SHA1 checksum; static void sort_pmux_conn(dict &conn) { @@ -68,7 +65,6 @@ struct OptMergeWorker } } -#ifdef USE_CELL_HASH_CACHE std::string int_to_hash_string(unsigned int v) { if (v == 0) @@ -83,14 +79,9 @@ struct OptMergeWorker std::string hash_cell_parameters_and_connections(const RTLIL::Cell *cell) { - if (cell_hash_cache.count(cell) > 0) - return cell_hash_cache[cell]; - + vector hash_conn_strings; std::string hash_string = cell->type.str() + "\n"; - for (auto &it : cell->parameters) - hash_string += "P " + it.first.str() + "=" + it.second.as_string() + "\n"; - const dict *conn = &cell->connections(); dict alt_conn; @@ -124,13 +115,22 @@ struct OptMergeWorker conn = &alt_conn; } - vector hash_conn_strings; - for (auto &it : *conn) { - if (cell->output(it.first)) - continue; - RTLIL::SigSpec sig = it.second; - assign_map.apply(sig); + RTLIL::SigSpec sig; + if (cell->output(it.first)) { + if (it.first == ID(Q) && (cell->type.begins_with("$dff") || cell->type.begins_with("$dlatch") || + cell->type.begins_with("$_DFF") || cell->type.begins_with("$_DLATCH") || cell->type.begins_with("$_SR_") || + cell->type.in("$adff", "$sr", "$ff", "$_FF_"))) { + // For the 'Q' output of state elements, + // use its (* init *) attribute value + for (const auto &b : dff_init_map(it.second)) + sig.append(b.wire ? State::Sx : b); + } + else + continue; + } + else + sig = assign_map(it.second); string s = "C " + it.first.str() + "="; for (auto &chunk : sig.chunks()) { if (chunk.wire) @@ -143,50 +143,59 @@ struct OptMergeWorker hash_conn_strings.push_back(s + "\n"); } + for (auto &it : cell->parameters) + hash_conn_strings.push_back("P " + it.first.str() + "=" + it.second.as_string() + "\n"); + std::sort(hash_conn_strings.begin(), hash_conn_strings.end()); for (auto it : hash_conn_strings) hash_string += it; - cell_hash_cache[cell] = sha1(hash_string); - return cell_hash_cache[cell]; + checksum.update(hash_string); + return checksum.final(); } -#endif - bool compare_cell_parameters_and_connections(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2, bool <) + bool compare_cell_parameters_and_connections(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) { -#ifdef USE_CELL_HASH_CACHE - std::string hash1 = hash_cell_parameters_and_connections(cell1); - std::string hash2 = hash_cell_parameters_and_connections(cell2); - - if (hash1 != hash2) { - lt = hash1 < hash2; - return true; - } -#endif - - if (cell1->parameters != cell2->parameters) { - std::map p1(cell1->parameters.begin(), cell1->parameters.end()); - std::map p2(cell2->parameters.begin(), cell2->parameters.end()); - lt = p1 < p2; - return true; - } - - dict conn1 = cell1->connections(); - dict conn2 = cell2->connections(); - - for (auto &it : conn1) { - if (cell1->output(it.first)) - it.second = RTLIL::SigSpec(); - else - assign_map.apply(it.second); - } - - for (auto &it : conn2) { - if (cell2->output(it.first)) - it.second = RTLIL::SigSpec(); - else - assign_map.apply(it.second); + log_assert(cell1 != cell2); + if (cell1->type != cell2->type) return false; + + if (cell1->parameters != cell2->parameters) + return false; + + if (cell1->connections_.size() != cell2->connections_.size()) + return false; + for (const auto &it : cell1->connections_) + if (!cell2->connections_.count(it.first)) + return false; + + decltype(Cell::connections_) conn1, conn2; + conn1.reserve(cell1->connections_.size()); + conn2.reserve(cell1->connections_.size()); + + for (const auto &it : cell1->connections_) { + if (cell1->output(it.first)) { + if (it.first == ID(Q) && (cell1->type.begins_with("$dff") || cell1->type.begins_with("$dlatch") || + cell1->type.begins_with("$_DFF") || cell1->type.begins_with("$_DLATCH") || cell1->type.begins_with("$_SR_") || + cell1->type.in("$adff", "$sr", "$ff", "$_FF_"))) { + // For the 'Q' output of state elements, + // use the (* init *) attribute value + auto &sig1 = conn1[it.first]; + for (const auto &b : dff_init_map(it.second)) + sig1.append(b.wire ? State::Sx : b); + auto &sig2 = conn2[it.first]; + for (const auto &b : dff_init_map(cell2->getPort(it.first))) + sig2.append(b.wire ? State::Sx : b); + } + else { + conn1[it.first] = RTLIL::SigSpec(); + conn2[it.first] = RTLIL::SigSpec(); + } + } + else { + conn1[it.first] = assign_map(it.second); + conn2[it.first] = assign_map(cell2->getPort(it.first)); + } } if (cell1->type == ID($and) || cell1->type == ID($or) || cell1->type == ID($xor) || cell1->type == ID($xnor) || cell1->type == ID($add) || cell1->type == ID($mul) || @@ -215,54 +224,9 @@ struct OptMergeWorker sort_pmux_conn(conn2); } - if (conn1 != conn2) { - std::map c1(conn1.begin(), conn1.end()); - std::map c2(conn2.begin(), conn2.end()); - lt = c1 < c2; - return true; - } - - if (conn1.count(ID(Q)) != 0 && (cell1->type.begins_with("$dff") || cell1->type.begins_with("$dlatch") || - cell1->type.begins_with("$_DFF") || cell1->type.begins_with("$_DLATCH") || cell1->type.begins_with("$_SR_") || - cell1->type.in("$adff", "$sr", "$ff", "$_FF_"))) { - std::vector q1 = dff_init_map(cell1->getPort(ID(Q))).to_sigbit_vector(); - std::vector q2 = dff_init_map(cell2->getPort(ID(Q))).to_sigbit_vector(); - for (size_t i = 0; i < q1.size(); i++) - if ((q1.at(i).wire == NULL || q2.at(i).wire == NULL) && q1.at(i) != q2.at(i)) { - lt = q1.at(i) < q2.at(i); - return true; - } - } - - return false; + return conn1 == conn2; } - bool compare_cells(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) - { - if (cell1->type != cell2->type) - return cell1->type < cell2->type; - - if ((!mode_share_all && !ct.cell_known(cell1->type)) || !cell1->known()) - return cell1 < cell2; - - if (cell1->has_keep_attr() || cell2->has_keep_attr()) - return cell1 < cell2; - - bool lt; - if (compare_cell_parameters_and_connections(cell1, cell2, lt)) - return lt; - - return false; - } - - struct CompareCells { - OptMergeWorker *that; - CompareCells(OptMergeWorker *that) : that(that) {} - bool operator()(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) const { - return that->compare_cells(cell1, cell2); - } - }; - OptMergeWorker(RTLIL::Design *design, RTLIL::Module *module, bool mode_nomux, bool mode_share_all) : design(design), module(module), assign_map(module), mode_share_all(mode_share_all) { @@ -299,9 +263,6 @@ struct OptMergeWorker bool did_something = true; while (did_something) { -#ifdef USE_CELL_HASH_CACHE - cell_hash_cache.clear(); -#endif std::vector cells; cells.reserve(module->cells_.size()); for (auto &it : module->cells_) { @@ -312,42 +273,51 @@ struct OptMergeWorker } did_something = false; - std::map sharemap(CompareCells(this)); + std::unordered_map sharemap; for (auto cell : cells) { - if (sharemap.count(cell) > 0) { - did_something = true; - log_debug(" Cell `%s' is identical to cell `%s'.\n", cell->name.c_str(), sharemap[cell]->name.c_str()); - for (auto &it : cell->connections()) { - if (cell->output(it.first)) { - RTLIL::SigSpec other_sig = sharemap[cell]->getPort(it.first); - log_debug(" Redirecting output %s: %s = %s\n", it.first.c_str(), - log_signal(it.second), log_signal(other_sig)); - module->connect(RTLIL::SigSig(it.second, other_sig)); - assign_map.add(it.second, other_sig); - - if (it.first == ID(Q) && (cell->type.begins_with("$dff") || cell->type.begins_with("$dlatch") || - cell->type.begins_with("$_DFF") || cell->type.begins_with("$_DLATCH") || cell->type.begins_with("$_SR_") || - cell->type.in("$adff", "$sr", "$ff", "$_FF_"))) { - for (auto c : it.second.chunks()) { - auto jt = c.wire->attributes.find(ID(init)); - if (jt == c.wire->attributes.end()) - continue; - for (int i = c.offset; i < c.offset + c.width; i++) - jt->second[i] = State::Sx; + if ((!mode_share_all && !ct.cell_known(cell->type)) || !cell->known()) + continue; + + auto hash = hash_cell_parameters_and_connections(cell); + auto r = sharemap.insert(std::make_pair(hash, cell)); + if (!r.second) { + if (compare_cell_parameters_and_connections(cell, r.first->second)) { + if (cell->has_keep_attr()) { + if (r.first->second->has_keep_attr()) + continue; + std::swap(r.first->second, cell); + } + + + did_something = true; + log_debug(" Cell `%s' is identical to cell `%s'.\n", cell->name.c_str(), r.first->second->name.c_str()); + for (auto &it : cell->connections()) { + if (cell->output(it.first)) { + RTLIL::SigSpec other_sig = r.first->second->getPort(it.first); + log_debug(" Redirecting output %s: %s = %s\n", it.first.c_str(), + log_signal(it.second), log_signal(other_sig)); + module->connect(RTLIL::SigSig(it.second, other_sig)); + assign_map.add(it.second, other_sig); + + if (it.first == ID(Q) && (cell->type.begins_with("$dff") || cell->type.begins_with("$dlatch") || + cell->type.begins_with("$_DFF") || cell->type.begins_with("$_DLATCH") || cell->type.begins_with("$_SR_") || + cell->type.in("$adff", "$sr", "$ff", "$_FF_"))) { + for (auto c : it.second.chunks()) { + auto jt = c.wire->attributes.find(ID(init)); + if (jt == c.wire->attributes.end()) + continue; + for (int i = c.offset; i < c.offset + c.width; i++) + jt->second[i] = State::Sx; + } + dff_init_map.add(it.second, Const(State::Sx, GetSize(it.second))); } - dff_init_map.add(it.second, Const(State::Sx, GetSize(it.second))); } } + log_debug(" Removing %s cell `%s' from module `%s'.\n", cell->type.c_str(), cell->name.c_str(), module->name.c_str()); + module->remove(cell); + total_count++; } - log_debug(" Removing %s cell `%s' from module `%s'.\n", cell->type.c_str(), cell->name.c_str(), module->name.c_str()); -#ifdef USE_CELL_HASH_CACHE - cell_hash_cache.erase(cell); -#endif - module->remove(cell); - total_count++; - } else { - sharemap[cell] = cell; } } } diff --git a/tests/opt/opt_merge_init.ys b/tests/opt/opt_merge_init.ys index a29c29df6..0176f09c7 100644 --- a/tests/opt/opt_merge_init.ys +++ b/tests/opt/opt_merge_init.ys @@ -20,6 +20,7 @@ endmodule EOT opt_merge +select -assert-count 1 t:$dff select -assert-count 1 a:init=1'0 @@ -46,4 +47,31 @@ endmodule EOT opt_merge +select -assert-count 1 t:$dff select -assert-count 1 a:init=2'bx1 + + +design -reset +read_verilog -icells <