Add doc

[yosys.git] / passes / opt / muxpack.cc

diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc
index b060389e3e7befbb4135017982c178445dedb0ee..c8b226c78e916a8ecc76582437facc570069de5e 100644 (file)
--- a/passes/opt/muxpack.cc
+++ b/passes/opt/muxpack.cc
@@ -24,6 +24,64 @@
 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
 
+struct ExclusiveDatabase
+{
+       Module *module;
+       const SigMap &sigmap;
+
+       dict<SigBit, std::pair<SigSpec,Const>> sig_cmp_prev;
+
+       ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap)
+       {
+               SigSpec const_sig, nonconst_sig, y_port;
+               for (auto cell : module->cells()) {
+                       if (cell->type == "$eq") {
+                               nonconst_sig = sigmap(cell->getPort("\\A"));
+                               const_sig = sigmap(cell->getPort("\\B"));
+                               if (!const_sig.is_fully_const()) {
+                                       if (!nonconst_sig.is_fully_const())
+                                               continue;
+                                       std::swap(nonconst_sig, const_sig);
+                               }
+                               y_port = sigmap(cell->getPort("\\Y"));
+                       }
+                       else if (cell->type == "$logic_not") {
+                               nonconst_sig = sigmap(cell->getPort("\\A"));
+                               const_sig = Const(RTLIL::S0, GetSize(nonconst_sig));
+                               y_port = sigmap(cell->getPort("\\Y"));
+                       }
+                       else continue;
+
+                        log_assert(!nonconst_sig.empty());
+                        log_assert(!const_sig.empty());
+                        sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,const_sig.as_const());
+                }
+        }
+
+        bool query(const SigSpec &sig) const
+        {
+                SigSpec nonconst_sig;
+                pool<Const> const_values;
+
+                for (auto bit : sig.bits()) {
+                        auto it = sig_cmp_prev.find(bit);
+                        if (it == sig_cmp_prev.end())
+                                return false;
+
+                        if (nonconst_sig.empty())
+                                nonconst_sig = it->second.first;
+                        else if (nonconst_sig != it->second.first)
+                                return false;
+
+                        if (!const_values.insert(it->second.second).second)
+                                return false;
+                }
+
+               return true;
+       }
+};
+
+
 struct MuxpackWorker
 {
        Module *module;
@@ -39,6 +97,8 @@ struct MuxpackWorker
        pool<Cell*> chain_start_cells;
        pool<Cell*> candidate_cells;
 
+       ExclusiveDatabase excl_db;
+
        void make_sig_chain_next_prev()
        {
                for (auto wire : module->wires())
@@ -109,15 +169,16 @@ struct MuxpackWorker
                        }
                        else log_abort();
 
-                       {
-                               for (auto bit : a_sig.bits())
-                                       if (sigbit_with_non_chain_users.count(bit))
-                                               goto start_cell;
-
-                               Cell *c1 = sig_chain_prev.at(a_sig);
-                               Cell *c2 = cell;
+                       for (auto bit : a_sig.bits())
+                               if (sigbit_with_non_chain_users.count(bit))
+                                       goto start_cell;
 
-                               if (c1->getParam("\\WIDTH") != c2->getParam("\\WIDTH"))
+                       {
+                               Cell *prev_cell = sig_chain_prev.at(a_sig);
+                               log_assert(prev_cell);
+                               SigSpec s_sig = sigmap(cell->getPort("\\S"));
+                               s_sig.append(sigmap(prev_cell->getPort("\\S")));
+                               if (!excl_db.query(s_sig))
                                        goto start_cell;
                        }
 
@@ -188,6 +249,7 @@ struct MuxpackWorker
                                        s_sig.append(cursor_cell->getPort("\\S"));
                                }
                                else {
+                                       log_assert(cursor_cell->type == "$mux");
                                        b_sig.append(cursor_cell->getPort("\\A"));
                                        s_sig.append(module->LogicNot(NEW_ID, cursor_cell->getPort("\\S")));
                                }
@@ -216,7 +278,7 @@ struct MuxpackWorker
        }
 
        MuxpackWorker(Module *module) :
-                       module(module), sigmap(module), mux_count(0), pmux_count(0)
+                       module(module), sigmap(module), mux_count(0), pmux_count(0), excl_db(module, sigmap)
        {
                make_sig_chain_next_prev();
                find_chain_start_cells();
@@ -239,8 +301,12 @@ struct MuxpackPass : public Pass {
                log("    muxpack [selection]\n");
                log("\n");
                log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n");
-               log("constructs) and $mux cells (e.g. those created by if-else constructs) into \n");
-               log("into $pmux cells.\n");
+               log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n");
+               log("$pmux cells.\n");
+               log("\n");
+               log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n");
+               log("whose select lines are driven by '$eq' cells with other such cells if it can be\n");
+               log("certain that their select inputs are mutually exclusive.\n");
                log("\n");
        }
        void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE