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 USING_YOSYS_NAMESPACE
  33 PRIVATE_NAMESPACE_BEGIN
  34
  35 static RTLIL::Module *module;
  36 static SigMap assign_map;
  37 typedef std::pair<RTLIL::IdString, RTLIL::IdString> sig2driver_entry_t;
  38 static SigSet<sig2driver_entry_t> sig2driver, sig2trigger;
  39 static std::map<RTLIL::SigBit, std::set<RTLIL::SigBit>> exclusive_ctrls;
  40
  41 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)
  42 {
  43         sig.extend_u0(dff_out.size(), false);
  44
  45         if (sig == dff_out)
  46                 return true;
  47
  48         assign_map.apply(sig);
  49         if (sig.is_fully_const()) {
  50                 if (sig.is_fully_def() && states.count(sig.as_const()) == 0) {
  51                         log("  found state code: %s\n", log_signal(sig));
  52                         states[sig.as_const()] = -1;
  53                 }
  54                 return true;
  55         }
  56
  57         std::set<sig2driver_entry_t> cellport_list;
  58         sig2driver.find(sig, cellport_list);
  59
  60         if (GetSize(cellport_list) > 1) {
  61                 log("  found %d combined drivers for state signal %s.\n", GetSize(cellport_list), log_signal(sig));
  62                 return false;
  63         }
  64
  65         if (GetSize(cellport_list) < 1) {
  66                 log("  found no driver for state signal %s.\n", log_signal(sig));
  67                 return false;
  68         }
  69
  70         for (auto &cellport : cellport_list)
  71         {
  72                 RTLIL::Cell *cell = module->cells_.at(cellport.first);
  73                 if ((cell->type != "$mux" && cell->type != "$pmux") || cellport.second != "\\Y") {
  74                         log("  unexpected cell type %s (%s) found in state selection tree.\n", cell->type.c_str(), cell->name.c_str());
  75                         return false;
  76                 }
  77
  78                 RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
  79                 RTLIL::SigSpec sig_b = assign_map(cell->getPort("\\B"));
  80                 RTLIL::SigSpec sig_s = assign_map(cell->getPort("\\S"));
  81                 RTLIL::SigSpec sig_y = assign_map(cell->getPort("\\Y"));
  82
  83                 RTLIL::SigSpec sig_aa = sig;
  84                 sig_aa.replace(sig_y, sig_a);
  85
  86                 RTLIL::SigSpec sig_bb;
  87                 for (int i = 0; i < GetSize(sig_b)/GetSize(sig_a); i++) {
  88                         RTLIL::SigSpec s = sig;
  89                         s.replace(sig_y, sig_b.extract(i*GetSize(sig_a), GetSize(sig_a)));
  90                         sig_bb.append(s);
  91                 }
  92
  93                 if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef())
  94                         do {
  95                                 if (sig_aa.is_fully_def())
  96                                         *reset_state = sig_aa.as_const();
  97                                 else if (sig_bb.is_fully_def())
  98                                         *reset_state = sig_bb.as_const();
  99                                 else
 100                                         break;
 101                                 log("  found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state));
 102                         } while (0);
 103
 104                 for (auto sig_s_bit : sig_s) {
 105                         if (ctrl.extract(sig_s_bit).empty()) {
 106                                 log("  found ctrl input: %s\n", log_signal(sig_s_bit));
 107                                 ctrl.append(sig_s_bit);
 108                         }
 109                 }
 110
 111                 if (!find_states(sig_aa, dff_out, ctrl, states))
 112                         return false;
 113
 114                 for (int i = 0; i < GetSize(sig_bb)/GetSize(sig_aa); i++) {
 115                         if (!find_states(sig_bb.extract(i*GetSize(sig_aa), GetSize(sig_aa)), dff_out, ctrl, states))
 116                                 return false;
 117                 }
 118         }
 119
 120         return true;
 121 }
 122
 123 static RTLIL::Const sig2const(ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care = RTLIL::SigSpec())
 124 {
 125         if (dont_care.size() > 0) {
 126                 for (int i = 0; i < GetSize(sig); i++)
 127                         if (dont_care.extract(sig[i]).size() > 0)
 128                                 sig[i] = noconst_state;
 129         }
 130
 131         ce.assign_map.apply(sig);
 132         ce.values_map.apply(sig);
 133
 134         for (int i = 0; i < GetSize(sig); i++)
 135                 if (sig[i].wire != NULL)
 136                         sig[i] = noconst_state;
 137
 138         return sig.as_const();
 139 }
 140
 141 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)
 142 {
 143         bool undef_bit_in_next_state_mode = false;
 144         RTLIL::SigSpec undef, constval;
 145
 146         if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef))
 147         {
 148                 if (0) {
 149 undef_bit_in_next_state:
 150                         for (auto &bit : dff_in)
 151                                 if (bit.wire != nullptr) bit = RTLIL::Sm;
 152                         for (auto &bit : ctrl_out)
 153                                 if (bit.wire != nullptr) bit = RTLIL::Sm;
 154                         undef_bit_in_next_state_mode = true;
 155                 }
 156
 157                 log_assert(ctrl_out.is_fully_const() && dff_in.is_fully_const());
 158
 159                 FsmData::transition_t tr;
 160                 tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care);
 161                 tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx);
 162
 163                 std::map<RTLIL::SigBit, int> ctrl_in_bit_indices;
 164                 for (int i = 0; i < GetSize(ctrl_in); i++)
 165                         ctrl_in_bit_indices[ctrl_in[i]] = i;
 166
 167                 for (auto &it : ctrl_in_bit_indices)
 168                         if (tr.ctrl_in.bits.at(it.second) == RTLIL::S1 && exclusive_ctrls.count(it.first) != 0)
 169                                 for (auto &dc_bit : exclusive_ctrls.at(it.first))
 170                                         if (ctrl_in_bit_indices.count(dc_bit))
 171                                                 tr.ctrl_in.bits.at(ctrl_in_bit_indices.at(dc_bit)) = RTLIL::State::Sa;
 172
 173                 RTLIL::Const log_state_in = RTLIL::Const(RTLIL::State::Sx, fsm_data.state_bits);
 174                 if (state_in >= 0)
 175                         log_state_in = fsm_data.state_table.at(state_in);
 176
 177                 if (states.count(ce.values_map(ce.assign_map(dff_in)).as_const()) == 0) {
 178                         log("  transition: %10s %s -> INVALID_STATE(%s) %s  <ignored invalid transistion!>%s\n",
 179                                         log_signal(log_state_in), log_signal(tr.ctrl_in),
 180                                         log_signal(ce.values_map(ce.assign_map(dff_in))), log_signal(tr.ctrl_out),
 181                                         undef_bit_in_next_state_mode ? " SHORTENED" : "");
 182                         return;
 183                 }
 184
 185                 tr.state_in = state_in;
 186                 tr.state_out = states.at(ce.values_map(ce.assign_map(dff_in)).as_const());
 187
 188                 if (dff_in.is_fully_def()) {
 189                         fsm_data.transition_table.push_back(tr);
 190                         log("  transition: %10s %s -> %10s %s\n",
 191                                         log_signal(log_state_in), log_signal(tr.ctrl_in),
 192                                         log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
 193                 } else {
 194                         log("  transition: %10s %s -> %10s %s  <ignored undef transistion!>\n",
 195                                         log_signal(log_state_in), log_signal(tr.ctrl_in),
 196                                         log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
 197                 }
 198                 return;
 199         }
 200
 201         for (auto &bit : dff_in)
 202                 if (bit == RTLIL::Sx)
 203                         goto undef_bit_in_next_state;
 204
 205         log_assert(undef.size() > 0);
 206         log_assert(ce.stop_signals.check_all(undef));
 207
 208         undef = undef.extract(0, 1);
 209         constval = undef;
 210
 211         if (ce_nostop.eval(constval))
 212         {
 213                 ce.push();
 214                 dont_care.append(undef);
 215                 ce.set(undef, constval.as_const());
 216                 if (exclusive_ctrls.count(undef) && constval == RTLIL::S1)
 217                         for (auto &bit : exclusive_ctrls.at(undef)) {
 218                                 RTLIL::SigSpec bitval = bit;
 219                                 if (ce.eval(bitval) && bitval != RTLIL::S0)
 220                                         goto found_contradiction_1;
 221                                 else
 222                                         ce.set(bit, RTLIL::S0);
 223                         }
 224                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 225         found_contradiction_1:
 226                 ce.pop();
 227         }
 228         else
 229         {
 230                 ce.push(), ce_nostop.push();
 231                 ce.set(undef, RTLIL::S0);
 232                 ce_nostop.set(undef, RTLIL::S0);
 233                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 234                 ce.pop(), ce_nostop.pop();
 235
 236                 ce.push(), ce_nostop.push();
 237                 ce.set(undef, RTLIL::S1);
 238                 ce_nostop.set(undef, RTLIL::S1);
 239                 if (exclusive_ctrls.count(undef))
 240                         for (auto &bit : exclusive_ctrls.at(undef)) {
 241                                 RTLIL::SigSpec bitval = bit;
 242                                 if ((ce.eval(bitval) || ce_nostop.eval(bitval)) && bitval != RTLIL::S0)
 243                                         goto found_contradiction_2;
 244                                 else
 245                                         ce.set(bit, RTLIL::S0), ce_nostop.set(bit, RTLIL::S0);
 246                         }
 247                 find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
 248         found_contradiction_2:
 249                 ce.pop(), ce_nostop.pop();
 250         }
 251 }
 252
 253 static void extract_fsm(RTLIL::Wire *wire)
 254 {
 255         log("Extracting FSM `%s' from module `%s'.\n", wire->name.c_str(), module->name.c_str());
 256
 257         // get input and output signals for state ff
 258
 259         RTLIL::SigSpec dff_out = assign_map(RTLIL::SigSpec(wire));
 260         RTLIL::SigSpec dff_in(RTLIL::State::Sm, wire->width);
 261         RTLIL::Const reset_state(RTLIL::State::Sx, wire->width);
 262
 263         RTLIL::SigSpec clk = RTLIL::S0;
 264         RTLIL::SigSpec arst = RTLIL::S0;
 265         bool clk_polarity = true;
 266         bool arst_polarity = true;
 267
 268         std::set<sig2driver_entry_t> cellport_list;
 269         sig2driver.find(dff_out, cellport_list);
 270         for (auto &cellport : cellport_list) {
 271                 RTLIL::Cell *cell = module->cells_.at(cellport.first);
 272                 if ((cell->type != "$dff" && cell->type != "$adff") || cellport.second != "\\Q")
 273                         continue;
 274                 log("  found %s cell for state register: %s\n", cell->type.c_str(), cell->name.c_str());
 275                 RTLIL::SigSpec sig_q = assign_map(cell->getPort("\\Q"));
 276                 RTLIL::SigSpec sig_d = assign_map(cell->getPort("\\D"));
 277                 clk = cell->getPort("\\CLK");
 278                 clk_polarity = cell->parameters["\\CLK_POLARITY"].as_bool();
 279                 if (cell->type == "$adff") {
 280                         arst = cell->getPort("\\ARST");
 281                         arst_polarity = cell->parameters["\\ARST_POLARITY"].as_bool();
 282                         reset_state = cell->parameters["\\ARST_VALUE"];
 283                 }
 284                 sig_q.replace(dff_out, sig_d, &dff_in);
 285                 break;
 286         }
 287
 288         log("  root of input selection tree: %s\n", log_signal(dff_in));
 289         if (dff_in.has_marked_bits()) {
 290                 log("  fsm extraction failed: incomplete input selection tree root.\n");
 291                 return;
 292         }
 293
 294         // find states and control inputs
 295
 296         RTLIL::SigSpec ctrl_in;
 297         std::map<RTLIL::Const, int> states;
 298         if (!arst.is_fully_const()) {
 299                 log("  found reset state: %s (from async reset)\n", log_signal(reset_state));
 300                 states[reset_state] = -1;
 301         }
 302         if (!find_states(dff_in, dff_out, ctrl_in, states, &reset_state)) {
 303                 log("  fsm extraction failed: state selection tree is not closed.\n");
 304                 return;
 305         }
 306         if (GetSize(states) <= 1) {
 307                 log("  fsm extraction failed: at least two states are required.\n");
 308                 return;
 309         }
 310
 311         // find control outputs
 312         // (add the state signals to the list of control outputs. if everything goes right, this signals
 313         // become unused and can then be removed from the fsm control output)
 314
 315         RTLIL::SigSpec ctrl_out = dff_in;
 316         cellport_list.clear();
 317         sig2trigger.find(dff_out, cellport_list);
 318         for (auto &cellport : cellport_list) {
 319                 RTLIL::Cell *cell = module->cells_.at(cellport.first);
 320                 RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
 321                 RTLIL::SigSpec sig_b;
 322                 if (cell->hasPort("\\B"))
 323                         sig_b = assign_map(cell->getPort("\\B"));
 324                 RTLIL::SigSpec sig_y = assign_map(cell->getPort("\\Y"));
 325                 if (cellport.second == "\\A" && !sig_b.is_fully_const())
 326                         continue;
 327                 if (cellport.second == "\\B" && !sig_a.is_fully_const())
 328                         continue;
 329                 log("  found ctrl output: %s\n", log_signal(sig_y));
 330                 ctrl_out.append(sig_y);
 331         }
 332         ctrl_in.remove(ctrl_out);
 333
 334         ctrl_in.sort_and_unify();
 335         ctrl_out.sort_and_unify();
 336
 337         log("  ctrl inputs: %s\n", log_signal(ctrl_in));
 338         log("  ctrl outputs: %s\n", log_signal(ctrl_out));
 339
 340         // Initialize fsm data struct
 341
 342         FsmData fsm_data;
 343         fsm_data.num_inputs = ctrl_in.size();
 344         fsm_data.num_outputs = ctrl_out.size();
 345         fsm_data.state_bits = wire->width;
 346         fsm_data.reset_state = -1;
 347         for (auto &it : states) {
 348                 it.second = fsm_data.state_table.size();
 349                 fsm_data.state_table.push_back(it.first);
 350         }
 351         if (!arst.is_fully_const() || RTLIL::SigSpec(reset_state).is_fully_def())
 352                 fsm_data.reset_state = states[reset_state];
 353
 354         // Create transition table
 355
 356         ConstEval ce(module), ce_nostop(module);
 357         ce.stop(ctrl_in);
 358         for (int state_idx = 0; state_idx < int(fsm_data.state_table.size()); state_idx++) {
 359                 ce.push(), ce_nostop.push();
 360                 ce.set(dff_out, fsm_data.state_table[state_idx]);
 361                 ce_nostop.set(dff_out, fsm_data.state_table[state_idx]);
 362                 find_transitions(ce, ce_nostop, fsm_data, states, state_idx, ctrl_in, ctrl_out, dff_in, RTLIL::SigSpec());
 363                 ce.pop(), ce_nostop.pop();
 364         }
 365
 366         // create fsm cell
 367
 368         RTLIL::Cell *fsm_cell = module->addCell(stringf("$fsm$%s$%d", wire->name.c_str(), autoidx++), "$fsm");
 369         fsm_cell->setPort("\\CLK", clk);
 370         fsm_cell->setPort("\\ARST", arst);
 371         fsm_cell->parameters["\\CLK_POLARITY"] = clk_polarity ? RTLIL::S1 : RTLIL::S0;
 372         fsm_cell->parameters["\\ARST_POLARITY"] = arst_polarity ? RTLIL::S1 : RTLIL::S0;
 373         fsm_cell->setPort("\\CTRL_IN", ctrl_in);
 374         fsm_cell->setPort("\\CTRL_OUT", ctrl_out);
 375         fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name.str());
 376         fsm_cell->attributes = wire->attributes;
 377         fsm_data.copy_to_cell(fsm_cell);
 378
 379         // rename original state wire
 380
 381         module->wires_.erase(wire->name);
 382         wire->attributes.erase("\\fsm_encoding");
 383         wire->name = stringf("$fsm$oldstate%s", wire->name.c_str());
 384         module->wires_[wire->name] = wire;
 385
 386         // unconnect control outputs from old drivers
 387
 388         cellport_list.clear();
 389         sig2driver.find(ctrl_out, cellport_list);
 390         for (auto &cellport : cellport_list) {
 391                 RTLIL::Cell *cell = module->cells_.at(cellport.first);
 392                 RTLIL::SigSpec port_sig = assign_map(cell->getPort(cellport.second));
 393                 RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out);
 394                 RTLIL::Wire *unconn_wire = module->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), autoidx++), unconn_sig.size());
 395                 port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cell->connections_[cellport.second]);
 396         }
 397 }
 398
 399 struct FsmExtractPass : public Pass {
 400         FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
 401         virtual void help()
 402         {
 403                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 404                 log("\n");
 405                 log("    fsm_extract [selection]\n");
 406                 log("\n");
 407                 log("This pass operates on all signals marked as FSM state signals using the\n");
 408                 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
 409                 log("and uses the state signal to generate control signal and replaces it with an\n");
 410                 log("FSM cell.\n");
 411                 log("\n");
 412                 log("The generated FSM cell still generates the original state signal with its\n");
 413                 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
 414                 log("'opt_clean' pass to eliminate this signal.\n");
 415                 log("\n");
 416         }
 417         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 418         {
 419                 log_header(design, "Executing FSM_EXTRACT pass (extracting FSM from design).\n");
 420                 extra_args(args, 1, design);
 421
 422                 CellTypes ct;
 423                 ct.setup_internals();
 424                 ct.setup_internals_mem();
 425                 ct.setup_stdcells();
 426                 ct.setup_stdcells_mem();
 427
 428                 for (auto &mod_it : design->modules_)
 429                 {
 430                         if (!design->selected(mod_it.second))
 431                                 continue;
 432
 433                         module = mod_it.second;
 434                         assign_map.set(module);
 435
 436                         sig2driver.clear();
 437                         sig2trigger.clear();
 438                         exclusive_ctrls.clear();
 439                         for (auto cell : module->cells()) {
 440                                 for (auto &conn_it : cell->connections()) {
 441                                         if (ct.cell_output(cell->type, conn_it.first) || !ct.cell_known(cell->type)) {
 442                                                 RTLIL::SigSpec sig = conn_it.second;
 443                                                 assign_map.apply(sig);
 444                                                 sig2driver.insert(sig, sig2driver_entry_t(cell->name, conn_it.first));
 445                                         }
 446                                         if (ct.cell_input(cell->type, conn_it.first) && cell->hasPort("\\Y") &&
 447                                                         cell->getPort("\\Y").size() == 1 && (conn_it.first == "\\A" || conn_it.first == "\\B")) {
 448                                                 RTLIL::SigSpec sig = conn_it.second;
 449                                                 assign_map.apply(sig);
 450                                                 sig2trigger.insert(sig, sig2driver_entry_t(cell->name, conn_it.first));
 451                                         }
 452                                 }
 453                                 if (cell->type == "$pmux") {
 454                                         RTLIL::SigSpec sel_sig = assign_map(cell->getPort("\\S"));
 455                                         for (auto &bit1 : sel_sig)
 456                                         for (auto &bit2 : sel_sig)
 457                                                 if (bit1 != bit2)
 458                                                         exclusive_ctrls[bit1].insert(bit2);
 459                                 }
 460                         }
 461
 462                         std::vector<RTLIL::Wire*> wire_list;
 463                         for (auto &wire_it : module->wires_)
 464                                 if (wire_it.second->attributes.count("\\fsm_encoding") > 0 && wire_it.second->attributes["\\fsm_encoding"].decode_string() != "none")
 465                                         if (design->selected(module, wire_it.second))
 466                                                 wire_list.push_back(wire_it.second);
 467                         for (auto wire : wire_list)
 468                                 extract_fsm(wire);
 469                 }
 470
 471                 assign_map.clear();
 472                 sig2driver.clear();
 473                 sig2trigger.clear();
 474         }
 475 } FsmExtractPass;
 476
 477 PRIVATE_NAMESPACE_END