Add doc

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

diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc
index f01d5474d854fc2f372da97067336a9a1bf850a7..c8b226c78e916a8ecc76582437facc570069de5e 100644 (file)
--- a/passes/opt/muxpack.cc
+++ b/passes/opt/muxpack.cc
@@ -29,54 +29,53 @@ struct ExclusiveDatabase
        Module *module;
        const SigMap &sigmap;
 
-       dict<SigBit, SigSpec> sig_cmp_prev;
-       dict<SigSpec, pool<SigSpec>> sig_exclusive;
+       dict<SigBit, std::pair<SigSpec,Const>> sig_cmp_prev;
 
        ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap)
        {
-               SigSpec a_port, b_port, y_port;
+               SigSpec const_sig, nonconst_sig, y_port;
                for (auto cell : module->cells()) {
                        if (cell->type == "$eq") {
-                               a_port = sigmap(cell->getPort("\\A"));
-                               b_port = sigmap(cell->getPort("\\B"));
-                               if (!b_port.is_fully_const()) {
-                                       if (!a_port.is_fully_const())
+                               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(a_port, b_port);
+                                       std::swap(nonconst_sig, const_sig);
                                }
                                y_port = sigmap(cell->getPort("\\Y"));
                        }
                        else if (cell->type == "$logic_not") {
-                               a_port = sigmap(cell->getPort("\\A"));
-                               b_port = Const(RTLIL::S0, GetSize(a_port));
+                               nonconst_sig = sigmap(cell->getPort("\\A"));
+                               const_sig = Const(RTLIL::S0, GetSize(nonconst_sig));
                                y_port = sigmap(cell->getPort("\\Y"));
                        }
                        else continue;
 
-                       auto r = sig_exclusive[a_port].insert(b_port.as_const());
-                       if (!r.second)
-                               continue;
-                       sig_cmp_prev[y_port] = a_port;
-               }
-       }
+                        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& sig1, const SigSpec& sig2) const
-       {
-               // FIXME: O(N^2)
-               for (auto bit1 : sig1.bits()) {
-                       auto it = sig_cmp_prev.find(bit1);
-                       if (it == sig_cmp_prev.end())
-                               return false;
-
-                       for (auto bit2 : sig2.bits()) {
-                               auto jt = sig_cmp_prev.find(bit2);
-                               if (jt == sig_cmp_prev.end())
-                                       return false;
-
-                               if (it->second != jt->second)
-                                       return false;
-                       }
-               }
+        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;
        }
@@ -178,8 +177,8 @@ struct MuxpackWorker
                                Cell *prev_cell = sig_chain_prev.at(a_sig);
                                log_assert(prev_cell);
                                SigSpec s_sig = sigmap(cell->getPort("\\S"));
-                               SigSpec next_s_sig = sigmap(prev_cell->getPort("\\S"));
-                               if (!excl_db.query(s_sig, next_s_sig))
+                               s_sig.append(sigmap(prev_cell->getPort("\\S")));
+                               if (!excl_db.query(s_sig))
                                        goto start_cell;
                        }
 
@@ -302,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