diff options
author | Clifford Wolf <clifford@clifford.at> | 2019-06-20 11:30:27 +0200 |
---|---|---|
committer | Eddie Hung <eddie@fpgeh.com> | 2019-06-20 19:47:59 -0700 |
commit | 891ea6512e5254803b36a2a22121bc2733ac8b9e (patch) | |
tree | c809394631ddc13dfaa70b6d8237be950cb1b8d7 /passes/techmap | |
parent | 844c42cef8c7c04fa67653f998ccab0e90532d28 (diff) | |
download | yosys-891ea6512e5254803b36a2a22121bc2733ac8b9e.tar.gz yosys-891ea6512e5254803b36a2a22121bc2733ac8b9e.tar.bz2 yosys-891ea6512e5254803b36a2a22121bc2733ac8b9e.zip |
Improvements in muxcover
- Slightly under-estimate cost of decoder muxes
- Prefer larger muxes at tree root at same cost
- Don't double-count input cost for partial muxes
- Add debug log output
Diffstat (limited to 'passes/techmap')
-rw-r--r-- | passes/techmap/muxcover.cc | 93 |
1 files changed, 55 insertions, 38 deletions
diff --git a/passes/techmap/muxcover.cc b/passes/techmap/muxcover.cc index 78272b0c4..e952b04b6 100644 --- a/passes/techmap/muxcover.cc +++ b/passes/techmap/muxcover.cc @@ -178,7 +178,7 @@ struct MuxcoverWorker if (A == State::Sx || B == State::Sx) return 0; - return cost_mux2 / GetSize(std::get<1>(entry)); + return std::max((cost_mux2 / GetSize(std::get<1>(entry))) - 1, 1); } void implement_decode_mux(SigBit ctrl_bit) @@ -206,6 +206,23 @@ struct MuxcoverWorker std::get<2>(entry) = true; } + void find_best_covers(tree_t &tree, const vector<SigBit> &bits) + { + for (auto bit : bits) + find_best_cover(tree, bit); + } + + int sum_best_covers(tree_t &tree, const vector<SigBit> &bits) + { + int sum = 0; + for (auto bit : pool<SigBit>(bits.begin(), bits.end())) { + int cost = tree.newmuxes.at(bit).cost; + log_debug(" Best cost for %s: %d\n", log_signal(bit), cost); + sum += cost; + } + return sum; + } + int find_best_cover(tree_t &tree, SigBit bit) { if (tree.newmuxes.count(bit)) { @@ -236,9 +253,13 @@ struct MuxcoverWorker mux.inputs.push_back(B); mux.selects.push_back(S1); + find_best_covers(tree, mux.inputs); + log_debug(" Decode cost for mux2 at %s: %d\n", log_signal(bit), mux.cost); + mux.cost += cost_mux2; - mux.cost += find_best_cover(tree, A); - mux.cost += find_best_cover(tree, B); + mux.cost += sum_best_covers(tree, mux.inputs); + + log_debug(" Cost of mux2 at %s: %d\n", log_signal(bit), mux.cost); best_mux = mux; } @@ -274,13 +295,15 @@ struct MuxcoverWorker mux.selects.push_back(S1); mux.selects.push_back(T1); + find_best_covers(tree, mux.inputs); + log_debug(" Decode cost for mux4 at %s: %d\n", log_signal(bit), mux.cost); + mux.cost += cost_mux4; - mux.cost += find_best_cover(tree, A); - mux.cost += find_best_cover(tree, B); - mux.cost += find_best_cover(tree, C); - mux.cost += find_best_cover(tree, D); + mux.cost += sum_best_covers(tree, mux.inputs); - if (best_mux.cost > mux.cost) + log_debug(" Cost of mux4 at %s: %d\n", log_signal(bit), mux.cost); + + if (best_mux.cost >= mux.cost) best_mux = mux; } } @@ -337,17 +360,15 @@ struct MuxcoverWorker mux.selects.push_back(T1); mux.selects.push_back(U1); + find_best_covers(tree, mux.inputs); + log_debug(" Decode cost for mux8 at %s: %d\n", log_signal(bit), mux.cost); + mux.cost += cost_mux8; - mux.cost += find_best_cover(tree, A); - mux.cost += find_best_cover(tree, B); - mux.cost += find_best_cover(tree, C); - mux.cost += find_best_cover(tree, D); - mux.cost += find_best_cover(tree, E); - mux.cost += find_best_cover(tree, F); - mux.cost += find_best_cover(tree, G); - mux.cost += find_best_cover(tree, H); - - if (best_mux.cost > mux.cost) + mux.cost += sum_best_covers(tree, mux.inputs); + + log_debug(" Cost of mux8 at %s: %d\n", log_signal(bit), mux.cost); + + if (best_mux.cost >= mux.cost) best_mux = mux; } } @@ -441,25 +462,15 @@ struct MuxcoverWorker mux.selects.push_back(U1); mux.selects.push_back(V1); + find_best_covers(tree, mux.inputs); + log_debug(" Decode cost for mux16 at %s: %d\n", log_signal(bit), mux.cost); + mux.cost += cost_mux16; - mux.cost += find_best_cover(tree, A); - mux.cost += find_best_cover(tree, B); - mux.cost += find_best_cover(tree, C); - mux.cost += find_best_cover(tree, D); - mux.cost += find_best_cover(tree, E); - mux.cost += find_best_cover(tree, F); - mux.cost += find_best_cover(tree, G); - mux.cost += find_best_cover(tree, H); - mux.cost += find_best_cover(tree, I); - mux.cost += find_best_cover(tree, J); - mux.cost += find_best_cover(tree, K); - mux.cost += find_best_cover(tree, L); - mux.cost += find_best_cover(tree, M); - mux.cost += find_best_cover(tree, N); - mux.cost += find_best_cover(tree, O); - mux.cost += find_best_cover(tree, P); - - if (best_mux.cost > mux.cost) + mux.cost += sum_best_covers(tree, mux.inputs); + + log_debug(" Cost of mux16 at %s: %d\n", log_signal(bit), mux.cost); + + if (best_mux.cost >= mux.cost) best_mux = mux; } } @@ -555,6 +566,7 @@ struct MuxcoverWorker void treecover(tree_t &tree) { int count_muxes_by_type[4] = {0, 0, 0, 0}; + log_debug(" Searching for best cover for tree at %s.\n", log_signal(tree.root)); find_best_cover(tree, tree.root); implement_best_cover(tree, tree.root, count_muxes_by_type); log(" Replaced tree at %s: %d MUX2, %d MUX4, %d MUX8, %d MUX16\n", log_signal(tree.root), @@ -571,12 +583,13 @@ struct MuxcoverWorker log(" Covering trees:\n"); - // pre-fill cache of decoder muxes - if (!nodecode) + if (!nodecode) { + log_debug(" Populating cache of decoder muxes.\n"); for (auto &tree : tree_list) { find_best_cover(tree, tree.root); tree.newmuxes.clear(); } + } for (auto &tree : tree_list) treecover(tree); @@ -607,6 +620,10 @@ struct MuxcoverPass : public Pass { log(" substitutions, but guarantees that the resulting circuit is not\n"); log(" less efficient than the original circuit.\n"); log("\n"); + log(" -nopartial\n"); + log(" Do not consider mappings that use $_MUX<N>_ to select from less\n"); + log(" than <N> different signals.\n"); + log("\n"); } void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE { |