passes/fsm/fsm_detect.cc

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