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, pool<Cell*> &recursion_monitor)
  38 {
  39         if (sig.is_fully_const() || old_sig == sig) {
  40                 return true;
  41         }
  42
  43         if (sig_at_port.check_any(assign_map(sig))) {
  44                 return false;
  45         }
  46
  47         std::set<sig2driver_entry_t> cellport_list;
  48         sig2driver.find(sig, cellport_list);
  49         for (auto &cellport : cellport_list)
  50         {
  51                 if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux") || cellport.second != "\\Y") {
  52                         return false;
  53                 }
  54
  55                 if (recursion_monitor.count(cellport.first)) {
  56                         log_warning("logic loop in mux tree at signal %s in module %s.\n",
  57                                         log_signal(sig), RTLIL::id2cstr(module->name));
  58                         return false;
  59                 }
  60
  61                 recursion_monitor.insert(cellport.first);
  62
  63                 RTLIL::SigSpec sig_a = assign_map(cellport.first->getPort("\\A"));
  64                 RTLIL::SigSpec sig_b = assign_map(cellport.first->getPort("\\B"));
  65
  66                 if (!check_state_mux_tree(old_sig, sig_a, recursion_monitor)) {
  67                         recursion_monitor.erase(cellport.first);
  68                         return false;
  69                 }
  70
  71                 for (int i = 0; i < sig_b.size(); i += sig_a.size())
  72                         if (!check_state_mux_tree(old_sig, sig_b.extract(i, sig_a.size()), recursion_monitor)) {
  73                                 recursion_monitor.erase(cellport.first);
  74                                 return false;
  75                         }
  76
  77                 recursion_monitor.erase(cellport.first);
  78                 muxtree_cells.insert(cellport.first);
  79         }
  80
  81         return true;
  82 }
  83
  84 static bool check_state_users(RTLIL::SigSpec sig)
  85 {
  86         if (sig_at_port.check_any(assign_map(sig)))
  87                 return false;
  88
  89         std::set<sig2driver_entry_t> cellport_list;
  90         sig2user.find(sig, cellport_list);
  91         for (auto &cellport : cellport_list) {
  92                 RTLIL::Cell *cell = cellport.first;
  93                 if (muxtree_cells.count(cell) > 0)
  94                         continue;
  95                 if (cell->type == "$logic_not" && assign_map(cell->getPort("\\A")) == sig)
  96                         continue;
  97                 if (cellport.second != "\\A" && cellport.second != "\\B")
  98                         return false;
  99                 if (!cell->hasPort("\\A") || !cell->hasPort("\\B") || !cell->hasPort("\\Y"))
 100                         return false;
 101                 for (auto &port_it : cell->connections())
 102                         if (port_it.first != "\\A" && port_it.first != "\\B" && port_it.first != "\\Y")
 103                                 return false;
 104                 if (assign_map(cell->getPort("\\A")) == sig && cell->getPort("\\B").is_fully_const())
 105                         continue;
 106                 if (assign_map(cell->getPort("\\B")) == sig && cell->getPort("\\A").is_fully_const())
 107                         continue;
 108                 return false;
 109         }
 110
 111         return true;
 112 }
 113
 114 static void detect_fsm(RTLIL::Wire *wire)
 115 {
 116         bool has_fsm_encoding_attr = wire->attributes.count("\\fsm_encoding") > 0 && wire->attributes.at("\\fsm_encoding").decode_string() != "none";
 117         bool has_fsm_encoding_none = wire->attributes.count("\\fsm_encoding") > 0 && wire->attributes.at("\\fsm_encoding").decode_string() == "none";
 118         bool has_init_attr = wire->attributes.count("\\init") > 0;
 119         bool is_module_port = sig_at_port.check_any(assign_map(RTLIL::SigSpec(wire)));
 120         bool looks_like_state_reg = false, looks_like_good_state_reg = false;
 121         bool is_self_resetting = false;
 122
 123         if (has_fsm_encoding_none)
 124                 return;
 125
 126         if (wire->width <= 1) {
 127                 if (has_fsm_encoding_attr) {
 128                         log_warning("Removing fsm_encoding attribute from 1-bit net: %s.%s\n", log_id(wire->module), log_id(wire));
 129                         wire->attributes.erase("\\fsm_encoding");
 130                 }
 131                 return;
 132         }
 133
 134         std::set<sig2driver_entry_t> cellport_list;
 135         sig2driver.find(RTLIL::SigSpec(wire), cellport_list);
 136
 137         for (auto &cellport : cellport_list)
 138         {
 139                 if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
 140                         continue;
 141
 142                 muxtree_cells.clear();
 143                 pool<Cell*> recursion_monitor;
 144                 RTLIL::SigSpec sig_q = assign_map(cellport.first->getPort("\\Q"));
 145                 RTLIL::SigSpec sig_d = assign_map(cellport.first->getPort("\\D"));
 146
 147                 if (sig_q != assign_map(wire))
 148                         continue;
 149
 150                 looks_like_state_reg = check_state_mux_tree(sig_q, sig_d, recursion_monitor);
 151                 looks_like_good_state_reg = check_state_users(sig_q);
 152
 153                 if (!looks_like_state_reg)
 154                         break;
 155
 156                 ConstEval ce(wire->module);
 157
 158                 std::set<sig2driver_entry_t> cellport_list;
 159                 sig2user.find(sig_q, cellport_list);
 160
 161                 for (auto &cellport : cellport_list)
 162                 {
 163                         RTLIL::Cell *cell = cellport.first;
 164                         bool set_output = false, clr_output = false;
 165
 166                         if (cell->type == "$ne")
 167                                 set_output = true;
 168
 169                         if (cell->type == "$eq")
 170                                 clr_output = true;
 171
 172                         if (!set_output && !clr_output) {
 173                                 clr_output = true;
 174                                 for (auto &port_it : cell->connections())
 175                                         if (port_it.first != "\\A" || port_it.first != "\\Y")
 176                                                 clr_output = false;
 177                         }
 178
 179                         if (set_output || clr_output) {
 180                                 for (auto &port_it : cell->connections())
 181                                         if (cell->output(port_it.first)) {
 182                                                 SigSpec sig = assign_map(port_it.second);
 183                                                 Const val(set_output ? State::S1 : State::S0, GetSize(sig));
 184                                                 ce.set(sig, val);
 185                                         }
 186                         }
 187                 }
 188
 189                 SigSpec sig_y = sig_d, sig_undef;
 190                 if (ce.eval(sig_y, sig_undef))
 191                         is_self_resetting = true;
 192         }
 193
 194         if (has_fsm_encoding_attr)
 195         {
 196                 vector<string> warnings;
 197
 198                 if (is_module_port)
 199                         warnings.push_back("Forcing FSM recoding on module port might result in larger circuit.\n");
 200
 201                 if (!looks_like_good_state_reg)
 202                         warnings.push_back("Users of state reg look like FSM recoding might result in larger circuit.\n");
 203
 204                 if (has_init_attr)
 205                         warnings.push_back("Initialization value on FSM state register is ignored. Possible simulation-synthesis mismatch!\n");
 206
 207                 if (!looks_like_state_reg)
 208                         warnings.push_back("Doesn't look like a proper FSM. Possible simulation-synthesis mismatch!\n");
 209
 210                 if (is_self_resetting)
 211                         warnings.push_back("FSM seems to be self-resetting. Possible simulation-synthesis mismatch!\n");
 212
 213                 if (!warnings.empty()) {
 214                         string warnmsg = stringf("Regarding the user-specified fsm_encoding attribute on %s.%s:\n", log_id(wire->module), log_id(wire));
 215                         for (auto w : warnings) warnmsg += "    " + w;
 216                         log_warning("%s", warnmsg.c_str());
 217                 } else {
 218                         log("FSM state register %s.%s already has fsm_encoding attribute.\n", log_id(wire->module), log_id(wire));
 219                 }
 220         }
 221         else
 222         if (looks_like_state_reg && looks_like_good_state_reg && !has_init_attr && !is_module_port && !is_self_resetting)
 223         {
 224                 log("Found FSM state register %s.%s.\n", log_id(wire->module), log_id(wire));
 225                 wire->attributes["\\fsm_encoding"] = RTLIL::Const("auto");
 226         }
 227         else
 228         if (looks_like_state_reg)
 229         {
 230                 log("Not marking %s.%s as FSM state register:\n", log_id(wire->module), log_id(wire));
 231
 232                 if (is_module_port)
 233                         log("    Register is connected to module port.\n");
 234
 235                 if (!looks_like_good_state_reg)
 236                         log("    Users of register don't seem to benefit from recoding.\n");
 237
 238                 if (has_init_attr)
 239                         log("    Register has an initialization value.\n");
 240
 241                 if (is_self_resetting)
 242                         log("    Circuit seems to be self-resetting.\n");
 243         }
 244 }
 245
 246 struct FsmDetectPass : public Pass {
 247         FsmDetectPass() : Pass("fsm_detect", "finding FSMs in design") { }
 248         void help() YS_OVERRIDE
 249         {
 250                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 251                 log("\n");
 252                 log("    fsm_detect [selection]\n");
 253                 log("\n");
 254                 log("This pass detects finite state machines by identifying the state signal.\n");
 255                 log("The state signal is then marked by setting the attribute 'fsm_encoding'\n");
 256                 log("on the state signal to \"auto\".\n");
 257                 log("\n");
 258                 log("Existing 'fsm_encoding' attributes are not changed by this pass.\n");
 259                 log("\n");
 260                 log("Signals can be protected from being detected by this pass by setting the\n");
 261                 log("'fsm_encoding' attribute to \"none\".\n");
 262                 log("\n");
 263         }
 264         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 265         {
 266                 log_header(design, "Executing FSM_DETECT pass (finding FSMs in design).\n");
 267                 extra_args(args, 1, design);
 268
 269                 CellTypes ct;
 270                 ct.setup_internals();
 271                 ct.setup_internals_mem();
 272                 ct.setup_stdcells();
 273                 ct.setup_stdcells_mem();
 274
 275                 for (auto &mod_it : design->modules_)
 276                 {
 277                         if (!design->selected(mod_it.second))
 278                                 continue;
 279
 280                         module = mod_it.second;
 281                         assign_map.set(module);
 282
 283                         sig2driver.clear();
 284                         sig2user.clear();
 285                         sig_at_port.clear();
 286                         for (auto &cell_it : module->cells_)
 287                                 for (auto &conn_it : cell_it.second->connections()) {
 288                                         if (ct.cell_output(cell_it.second->type, conn_it.first) || !ct.cell_known(cell_it.second->type)) {
 289                                                 RTLIL::SigSpec sig = conn_it.second;
 290                                                 assign_map.apply(sig);
 291                                                 sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
 292                                         }
 293                                         if (!ct.cell_known(cell_it.second->type) || ct.cell_input(cell_it.second->type, conn_it.first)) {
 294                                                 RTLIL::SigSpec sig = conn_it.second;
 295                                                 assign_map.apply(sig);
 296                                                 sig2user.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
 297                                         }
 298                                 }
 299
 300                         for (auto &wire_it : module->wires_)
 301                                 if (wire_it.second->port_id != 0)
 302                                         sig_at_port.add(assign_map(RTLIL::SigSpec(wire_it.second)));
 303
 304                         for (auto &wire_it : module->wires_)
 305                                 if (design->selected(module, wire_it.second))
 306                                         detect_fsm(wire_it.second);
 307                 }
 308
 309                 assign_map.clear();
 310                 sig2driver.clear();
 311                 sig2user.clear();
 312                 muxtree_cells.clear();
 313         }
 314 } FsmDetectPass;
 315
 316 PRIVATE_NAMESPACE_END