passes/fsm/fsm_extract.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 // [[CITE]]
  21 // Yiqiong Shi; Chan Wai Ting; Bah-Hwee Gwee; Ye Ren, "A highly efficient method for extracting FSMs from flattened gate-level netlist,"
  22 // Circuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on , vol., no., pp.2610,2613, May 30 2010-June 2 2010
  23 // doi: 10.1109/ISCAS.2010.5537093
  24
  25 #include "kernel/log.h"
  26 #include "kernel/register.h"
  27 #include "kernel/sigtools.h"
  28 #include "kernel/consteval.h"
  29 #include "kernel/celltypes.h"
  30 #include "fsmdata.h"
  31
  32 static RTLIL::Module *module;
  33 static SigMap assign_map;
  34 typedef std::pair<std::string, std::string> sig2driver_entry_t;
  35 static SigSet<sig2driver_entry_t> sig2driver, sig2trigger;
  36
  37 static bool find_states(RTLIL::SigSpec sig, const RTLIL::SigSpec &dff_out, RTLIL::SigSpec &ctrl, std::map<RTLIL::Const, int> &states, RTLIL::Const *reset_state = NULL)
  38 {
  39         sig.extend(dff_out.size(), false);
  40
  41         if (sig == dff_out)
  42                 return true;
  43
  44         assign_map.apply(sig);
  45         if (sig.is_fully_const()) {
  46                 if (states.count(sig.as_const()) == 0) {
  47                         log("  found state code: %s\n", log_signal(sig));
  48                         states[sig.as_const()] = -1;
  49                 }
  50                 return true;
  51         }
  52
  53         std::set<sig2driver_entry_t> cellport_list;
  54         sig2driver.find(sig, cellport_list);
  55         for (auto &cellport : cellport_list) {
  56                 RTLIL::Cell *cell = module->cells.at(cellport.first);
  57                 if ((cell->type != "$mux" && cell->type != "$pmux" && cell->type != "$safe_pmux") || cellport.second != "\\Y") {
  58                         log("  unexpected cell type %s (%s) found in state selection tree.\n", cell->type.c_str(), cell->name.c_str());
  59                         return false;
  60                 }
  61                 RTLIL::SigSpec sig_a = assign_map(cell->get("\\A"));
  62                 RTLIL::SigSpec sig_b = assign_map(cell->get("\\B"));
  63                 RTLIL::SigSpec sig_s = assign_map(cell->get("\\S"));
  64                 if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef())
  65                         do {
  66                                 if (sig_a.is_fully_def())
  67                                         *reset_state = sig_a.as_const();
  68                                 else if (sig_b.is_fully_def())
  69                                         *reset_state = sig_b.as_const();
  70                                 else
  71                                         break;
  72                                 log("  found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state));
  73                         } while (0);
  74                 if (ctrl.extract(sig_s).size() == 0) {
  75                         log("  found ctrl input: %s\n", log_signal(sig_s));
  76                         ctrl.append(sig_s);
  77                 }
  78                 if (!find_states(sig_a, dff_out, ctrl, states))
  79                         return false;
  80                 for (int i = 0; i < sig_b.size()/sig_a.size(); i++) {
  81                         if (!find_states(sig_b.extract(i*sig_a.size(), sig_a.size()), dff_out, ctrl, states))
  82                                 return false;
  83                 }
  84         }
  85
  86         return true;
  87 }
  88
  89 static RTLIL::Const sig2const(ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care = RTLIL::SigSpec())
  90 {
  91         if (dont_care.size() > 0) {
  92                 for (int i = 0; i < SIZE(sig); i++)
  93                         if (dont_care.extract(sig[i]).size() > 0)
  94                                 sig[i] = noconst_state;
  95         }
  96
  97         ce.assign_map.apply(sig);
  98         ce.values_map.apply(sig);
  99
 100         for (int i = 0; i < SIZE(sig); i++)
 101                 if (sig[i].wire != NULL)
 102                         sig[i] = noconst_state;
 103
 104         return sig.as_const();
 105 }
 106
 107 static void find_transitions(ConstEval &ce, ConstEval &ce_nostop, FsmData &fsm_data, std::map<RTLIL::Const, int> &states, int state_in, RTLIL::SigSpec ctrl_in, RTLIL::SigSpec ctrl_out, RTLIL::SigSpec dff_in, RTLIL::SigSpec dont_care)
 108 {
 109         RTLIL::SigSpec undef, constval;
 110
 111         if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef)) {
 112                 assert(ctrl_out.is_fully_const() && dff_in.is_fully_const());
 113                 FsmData::transition_t tr;
 114                 tr.state_in = state_in;
 115                 tr.state_out = states[ce.values_map(ce.assign_map(dff_in)).as_const()];
 116                 tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care);
 117                 tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx);
 118                 RTLIL::Const log_state_in = RTLIL::Const(RTLIL::State::Sx, fsm_data.state_bits);
 119                 if (state_in >= 0)
 120                         log_state_in = fsm_data.state_table[tr.state_in];
 121                 if (dff_in.is_fully_def()) {
 122                         fsm_data.transition_table.push_back(tr);
 123                         log("  transition: %10s %s -> %10s %s\n",
 124                                         log_signal(log_state_in), log_signal(tr.ctrl_in),
 125                                         log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
 126                 } else {
 127                         log("  transition: %10s %s -> %10s %s  <ignored undef transistion!>\n",
 128                                         log_signal(log_state_in), log_signal(tr.ctrl_in),
 129                                         log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
 130                 }
 131                 return;
 132         }
 133
 134         log_assert(undef.size() > 0);
 135         log_assert(ce.stop_signals.check_all(undef));
 136
 137         undef = undef.extract(0, 1);
 138         constval = undef;
 139
 140         if (ce_nostop.eval(constval))
 141         {
 142                 ce.push();
 143                 dont_care.append(undef);
 144                 ce.set(undef, constval.as_const());
 145                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 146                 ce.pop();
 147         }
 148         else
 149         {
 150                 ce.push(), ce_nostop.push();
 151                 ce.set(undef, RTLIL::Const(0, 1));
 152                 ce_nostop.set(undef, RTLIL::Const(0, 1));
 153                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 154                 ce.pop(), ce_nostop.pop();
 155
 156                 ce.push(), ce_nostop.push();
 157                 ce.set(undef, RTLIL::Const(1, 1));
 158                 ce_nostop.set(undef, RTLIL::Const(1, 1));
 159                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 160                 ce.pop(), ce_nostop.pop();
 161         }
 162 }
 163
 164 static void extract_fsm(RTLIL::Wire *wire)
 165 {
 166         log("Extracting FSM `%s' from module `%s'.\n", wire->name.c_str(), module->name.c_str());
 167
 168         // get input and output signals for state ff
 169
 170         RTLIL::SigSpec dff_out = assign_map(RTLIL::SigSpec(wire));
 171         RTLIL::SigSpec dff_in(RTLIL::State::Sm, wire->width);
 172         RTLIL::Const reset_state(RTLIL::State::Sx, wire->width);
 173
 174         RTLIL::SigSpec clk = RTLIL::SigSpec(0, 1);
 175         RTLIL::SigSpec arst = RTLIL::SigSpec(0, 1);
 176         bool clk_polarity = true;
 177         bool arst_polarity = true;
 178
 179         std::set<sig2driver_entry_t> cellport_list;
 180         sig2driver.find(dff_out, cellport_list);
 181         for (auto &cellport : cellport_list) {
 182                 RTLIL::Cell *cell = module->cells.at(cellport.first);
 183                 if ((cell->type != "$dff" && cell->type != "$adff") || cellport.second != "\\Q")
 184                         continue;
 185                 log("  found %s cell for state register: %s\n", cell->type.c_str(), cell->name.c_str());
 186                 RTLIL::SigSpec sig_q = assign_map(cell->get("\\Q"));
 187                 RTLIL::SigSpec sig_d = assign_map(cell->get("\\D"));
 188                 clk = cell->get("\\CLK");
 189                 clk_polarity = cell->parameters["\\CLK_POLARITY"].as_bool();
 190                 if (cell->type == "$adff") {
 191                         arst = cell->get("\\ARST");
 192                         arst_polarity = cell->parameters["\\ARST_POLARITY"].as_bool();
 193                         reset_state = cell->parameters["\\ARST_VALUE"];
 194                 }
 195                 sig_q.replace(dff_out, sig_d, &dff_in);
 196                 break;
 197         }
 198
 199         log("  root of input selection tree: %s\n", log_signal(dff_in));
 200         if (dff_in.has_marked_bits()) {
 201                 log("  fsm extraction failed: incomplete input selection tree root.\n");
 202                 return;
 203         }
 204
 205         // find states and control inputs
 206
 207         RTLIL::SigSpec ctrl_in;
 208         std::map<RTLIL::Const, int> states;
 209         if (!arst.is_fully_const()) {
 210                 log("  found reset state: %s (from async reset)\n", log_signal(reset_state));
 211                 states[reset_state] = -1;
 212         }
 213         if (!find_states(dff_in, dff_out, ctrl_in, states, &reset_state)) {
 214                 log("  fsm extraction failed: state selection tree is not closed.\n");
 215                 return;
 216         }
 217
 218         // find control outputs
 219         // (add the state signals to the list of control outputs. if everything goes right, this signals
 220         // become unused and can then be removed from the fsm control output)
 221
 222         RTLIL::SigSpec ctrl_out = dff_in;
 223         cellport_list.clear();
 224         sig2trigger.find(dff_out, cellport_list);
 225         for (auto &cellport : cellport_list) {
 226                 RTLIL::Cell *cell = module->cells.at(cellport.first);
 227                 RTLIL::SigSpec sig_a = assign_map(cell->get("\\A"));
 228                 RTLIL::SigSpec sig_b = assign_map(cell->get("\\B"));
 229                 RTLIL::SigSpec sig_y = assign_map(cell->get("\\Y"));
 230                 if (cellport.second == "\\A" && !sig_b.is_fully_const())
 231                         continue;
 232                 if (cellport.second == "\\B" && !sig_a.is_fully_const())
 233                         continue;
 234                 log("  found ctrl output: %s\n", log_signal(sig_y));
 235                 ctrl_out.append(sig_y);
 236         }
 237         ctrl_in.remove(ctrl_out);
 238
 239         ctrl_in.sort_and_unify();
 240         ctrl_out.sort_and_unify();
 241
 242         log("  ctrl inputs: %s\n", log_signal(ctrl_in));
 243         log("  ctrl outputs: %s\n", log_signal(ctrl_out));
 244
 245         // Initialize fsm data struct
 246
 247         FsmData fsm_data;
 248         fsm_data.num_inputs = ctrl_in.size();
 249         fsm_data.num_outputs = ctrl_out.size();
 250         fsm_data.state_bits = wire->width;
 251         fsm_data.reset_state = -1;
 252         for (auto &it : states) {
 253                 it.second = fsm_data.state_table.size();
 254                 fsm_data.state_table.push_back(it.first);
 255         }
 256         if (!arst.is_fully_const() || RTLIL::SigSpec(reset_state).is_fully_def())
 257                 fsm_data.reset_state = states[reset_state];
 258
 259         // Create transition table
 260
 261         ConstEval ce(module), ce_nostop(module);
 262         ce.stop(ctrl_in);
 263         for (int state_idx = 0; state_idx < int(fsm_data.state_table.size()); state_idx++) {
 264                 ce.push(), ce_nostop.push();
 265                 ce.set(dff_out, fsm_data.state_table[state_idx]);
 266                 ce_nostop.set(dff_out, fsm_data.state_table[state_idx]);
 267                 find_transitions(ce, ce_nostop, fsm_data, states, state_idx, ctrl_in, ctrl_out, dff_in, RTLIL::SigSpec());
 268                 ce.pop(), ce_nostop.pop();
 269         }
 270
 271         // create fsm cell
 272
 273         RTLIL::Cell *fsm_cell = module->addCell(stringf("$fsm$%s$%d", wire->name.c_str(), RTLIL::autoidx++), "$fsm");
 274         fsm_cell->set("\\CLK", clk);
 275         fsm_cell->set("\\ARST", arst);
 276         fsm_cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity ? 1 : 0, 1);
 277         fsm_cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity ? 1 : 0, 1);
 278         fsm_cell->set("\\CTRL_IN", ctrl_in);
 279         fsm_cell->set("\\CTRL_OUT", ctrl_out);
 280         fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name);
 281         fsm_cell->attributes = wire->attributes;
 282         fsm_data.copy_to_cell(fsm_cell);
 283
 284         // rename original state wire
 285
 286         module->wires_.erase(wire->name);
 287         wire->attributes.erase("\\fsm_encoding");
 288         wire->name = stringf("$fsm$oldstate%s", wire->name.c_str());
 289         module->wires_[wire->name] = wire;
 290
 291         // unconnect control outputs from old drivers
 292
 293         cellport_list.clear();
 294         sig2driver.find(ctrl_out, cellport_list);
 295         for (auto &cellport : cellport_list) {
 296                 RTLIL::Cell *cell = module->cells.at(cellport.first);
 297                 RTLIL::SigSpec port_sig = assign_map(cell->get(cellport.second));
 298                 RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out);
 299                 RTLIL::Wire *unconn_wire = module->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), RTLIL::autoidx++), unconn_sig.size());
 300                 port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cell->connections_[cellport.second]);
 301         }
 302 }
 303
 304 struct FsmExtractPass : public Pass {
 305         FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
 306         virtual void help()
 307         {
 308                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 309                 log("\n");
 310                 log("    fsm_extract [selection]\n");
 311                 log("\n");
 312                 log("This pass operates on all signals marked as FSM state signals using the\n");
 313                 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
 314                 log("and uses the state signal to generate control signal and replaces it with an\n");
 315                 log("FSM cell.\n");
 316                 log("\n");
 317                 log("The generated FSM cell still generates the original state signal with its\n");
 318                 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
 319                 log("'opt_clean' pass to eliminate this signal.\n");
 320                 log("\n");
 321         }
 322         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 323         {
 324                 log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
 325                 extra_args(args, 1, design);
 326
 327                 CellTypes ct;
 328                 ct.setup_internals();
 329                 ct.setup_internals_mem();
 330                 ct.setup_stdcells();
 331                 ct.setup_stdcells_mem();
 332
 333                 for (auto &mod_it : design->modules)
 334                 {
 335                         if (!design->selected(mod_it.second))
 336                                 continue;
 337
 338                         module = mod_it.second;
 339                         assign_map.set(module);
 340
 341                         sig2driver.clear();
 342                         sig2trigger.clear();
 343                         for (auto &cell_it : module->cells)
 344                                 for (auto &conn_it : cell_it.second->connections()) {
 345                                         if (ct.cell_output(cell_it.second->type, conn_it.first) || !ct.cell_known(cell_it.second->type)) {
 346                                                 RTLIL::SigSpec sig = conn_it.second;
 347                                                 assign_map.apply(sig);
 348                                                 sig2driver.insert(sig, sig2driver_entry_t(cell_it.first, conn_it.first));
 349                                         }
 350                                         if (ct.cell_input(cell_it.second->type, conn_it.first) && cell_it.second->has("\\Y") &&
 351                                                         cell_it.second->get("\\Y").size() == 1 && (conn_it.first == "\\A" || conn_it.first == "\\B")) {
 352                                                 RTLIL::SigSpec sig = conn_it.second;
 353                                                 assign_map.apply(sig);
 354                                                 sig2trigger.insert(sig, sig2driver_entry_t(cell_it.first, conn_it.first));
 355                                         }
 356                                 }
 357
 358                         std::vector<RTLIL::Wire*> wire_list;
 359                         for (auto &wire_it : module->wires_)
 360                                 if (wire_it.second->attributes.count("\\fsm_encoding") > 0 && wire_it.second->attributes["\\fsm_encoding"].decode_string() != "none")
 361                                         if (design->selected(module, wire_it.second))
 362                                                 wire_list.push_back(wire_it.second);
 363                         for (auto wire : wire_list)
 364                                 extract_fsm(wire);
 365                 }
 366
 367                 assign_map.clear();
 368                 sig2driver.clear();
 369                 sig2trigger.clear();
 370         }
 371 } FsmExtractPass;
 372