passes/fsm/fsm_detect.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   5  *
   6  *  Permission to use, copy, modify, and/or distribute this software for any
   7  *  purpose with or without fee is hereby granted, provided that the above
   8  *  copyright notice and this permission notice appear in all copies.
   9  *
  10  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  */
  19
  20 #include "kernel/log.h"
  21 #include "kernel/register.h"
  22 #include "kernel/sigtools.h"
  23 #include "kernel/consteval.h"
  24 #include "kernel/celltypes.h"
  25 #include "fsmdata.h"
  26
  27 USING_YOSYS_NAMESPACE
  28 PRIVATE_NAMESPACE_BEGIN
  29
  30 static RTLIL::Module *module;
  31 static SigMap assign_map;
  32 typedef std::pair<RTLIL::Cell*, RTLIL::IdString> sig2driver_entry_t;
  33 static SigSet<sig2driver_entry_t> sig2driver, sig2user;
  34 static std::set<RTLIL::Cell*> muxtree_cells;
  35 static SigPool sig_at_port;
  36
  37 static bool check_state_mux_tree(RTLIL::SigSpec old_sig, RTLIL::SigSpec sig, SigPool &recursion_monitor)
  38 {
  39         if (sig_at_port.check_any(assign_map(sig)))
  40                 return false;
  41
  42         if (sig.is_fully_const() || old_sig == sig)
  43                 return true;
  44
  45         if (recursion_monitor.check_any(sig)) {
  46                 log_warning("logic loop in mux tree at signal %s in module %s.\n",
  47                                 log_signal(sig), RTLIL::id2cstr(module->name));
  48                 return false;
  49         }
  50
  51         recursion_monitor.add(sig);
  52
  53         std::set<sig2driver_entry_t> cellport_list;
  54         sig2driver.find(sig, cellport_list);
  55         for (auto &cellport : cellport_list) {
  56                 if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux") || cellport.second != "\\Y")
  57                         return false;
  58                 RTLIL::SigSpec sig_a = assign_map(cellport.first->getPort("\\A"));
  59                 RTLIL::SigSpec sig_b = assign_map(cellport.first->getPort("\\B"));
  60                 if (!check_state_mux_tree(old_sig, sig_a, recursion_monitor))
  61                         return false;
  62                 for (int i = 0; i < sig_b.size(); i += sig_a.size())
  63                         if (!check_state_mux_tree(old_sig, sig_b.extract(i, sig_a.size()), recursion_monitor))
  64                                 return false;
  65                 muxtree_cells.insert(cellport.first);
  66         }
  67
  68         recursion_monitor.del(sig);
  69
  70         return true;
  71 }
  72
  73 static bool check_state_users(RTLIL::SigSpec sig)
  74 {
  75         if (sig_at_port.check_any(assign_map(sig)))
  76                 return false;
  77
  78         std::set<sig2driver_entry_t> cellport_list;
  79         sig2user.find(sig, cellport_list);
  80         for (auto &cellport : cellport_list) {
  81                 RTLIL::Cell *cell = cellport.first;
  82                 if (muxtree_cells.count(cell) > 0)
  83                         continue;
  84                 if (cellport.second != "\\A" && cellport.second != "\\B")
  85                         return false;
  86                 if (!cell->hasPort("\\A") || !cell->hasPort("\\B") || !cell->hasPort("\\Y"))
  87                         return false;
  88                 for (auto &port_it : cell->connections())
  89                         if (port_it.first != "\\A" && port_it.first != "\\B" && port_it.first != "\\Y")
  90                                 return false;
  91                 if (assign_map(cell->getPort("\\A")) == sig && cell->getPort("\\B").is_fully_const())
  92                         continue;
  93                 if (assign_map(cell->getPort("\\B")) == sig && cell->getPort("\\A").is_fully_const())
  94                         continue;
  95                 return false;
  96         }
  97
  98         return true;
  99 }
 100
 101 static void detect_fsm(RTLIL::Wire *wire)
 102 {
 103         if (wire->attributes.count("\\fsm_encoding") > 0 || wire->width <= 1)
 104                 return;
 105         if (sig_at_port.check_any(assign_map(RTLIL::SigSpec(wire))))
 106                 return;
 107
 108         std::set<sig2driver_entry_t> cellport_list;
 109         sig2driver.find(RTLIL::SigSpec(wire), cellport_list);
 110         for (auto &cellport : cellport_list) {
 111                 if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
 112                         continue;
 113                 muxtree_cells.clear();
 114                 SigPool recursion_monitor;
 115                 RTLIL::SigSpec sig_q = assign_map(cellport.first->getPort("\\Q"));
 116                 RTLIL::SigSpec sig_d = assign_map(cellport.first->getPort("\\D"));
 117                 if (sig_q == RTLIL::SigSpec(wire) && check_state_mux_tree(sig_q, sig_d, recursion_monitor) && check_state_users(sig_q)) {
 118                         log("Found FSM state register %s in module %s.\n", wire->name.c_str(), module->name.c_str());
 119                         wire->attributes["\\fsm_encoding"] = RTLIL::Const("auto");
 120                         return;
 121                 }
 122         }
 123 }
 124
 125 struct FsmDetectPass : public Pass {
 126         FsmDetectPass() : Pass("fsm_detect", "finding FSMs in design") { }
 127         virtual void help()
 128         {
 129                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 130                 log("\n");
 131                 log("    fsm_detect [selection]\n");
 132                 log("\n");
 133                 log("This pass detects finite state machines by identifying the state signal.\n");
 134                 log("The state signal is then marked by setting the attribute 'fsm_encoding'\n");
 135                 log("on the state signal to \"auto\".\n");
 136                 log("\n");
 137                 log("Existing 'fsm_encoding' attributes are not changed by this pass.\n");
 138                 log("\n");
 139                 log("Signals can be protected from being detected by this pass by setting the\n");
 140                 log("'fsm_encoding' attribute to \"none\".\n");
 141                 log("\n");
 142         }
 143         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 144         {
 145                 log_header("Executing FSM_DETECT pass (finding FSMs in design).\n");
 146                 extra_args(args, 1, design);
 147
 148                 CellTypes ct;
 149                 ct.setup_internals();
 150                 ct.setup_internals_mem();
 151                 ct.setup_stdcells();
 152                 ct.setup_stdcells_mem();
 153
 154                 for (auto &mod_it : design->modules_)
 155                 {
 156                         if (!design->selected(mod_it.second))
 157                                 continue;
 158
 159                         module = mod_it.second;
 160                         assign_map.set(module);
 161
 162                         sig2driver.clear();
 163                         sig2user.clear();
 164                         sig_at_port.clear();
 165                         for (auto &cell_it : module->cells_)
 166                                 for (auto &conn_it : cell_it.second->connections()) {
 167                                         if (ct.cell_output(cell_it.second->type, conn_it.first) || !ct.cell_known(cell_it.second->type)) {
 168                                                 RTLIL::SigSpec sig = conn_it.second;
 169                                                 assign_map.apply(sig);
 170                                                 sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
 171                                         }
 172                                         if (!ct.cell_known(cell_it.second->type) || ct.cell_input(cell_it.second->type, conn_it.first)) {
 173                                                 RTLIL::SigSpec sig = conn_it.second;
 174                                                 assign_map.apply(sig);
 175                                                 sig2user.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
 176                                         }
 177                                 }
 178
 179                         for (auto &wire_it : module->wires_)
 180                                 if (wire_it.second->port_id != 0)
 181                                         sig_at_port.add(assign_map(RTLIL::SigSpec(wire_it.second)));
 182
 183                         for (auto &wire_it : module->wires_)
 184                                 if (design->selected(module, wire_it.second))
 185                                         detect_fsm(wire_it.second);
 186                 }
 187
 188                 assign_map.clear();
 189                 sig2driver.clear();
 190                 sig2user.clear();
 191                 muxtree_cells.clear();
 192         }
 193 } FsmDetectPass;
 194
 195 PRIVATE_NAMESPACE_END