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