summaryrefslogtreecommitdiff
path: root/passes/fsm/fsm_extract.cc
diff options
context:
space:
mode:
authorClifford Wolf <clifford@clifford.at>2013-01-05 11:13:26 +0100
committerClifford Wolf <clifford@clifford.at>2013-01-05 11:13:26 +0100
commit7764d0ba1dcf064ae487ee985c43083a0909e7f4 (patch)
tree18c05b8729df381af71b707748ce1d605e0df764 /passes/fsm/fsm_extract.cc
initial import
Diffstat (limited to 'passes/fsm/fsm_extract.cc')
-rw-r--r--passes/fsm/fsm_extract.cc359
1 files changed, 359 insertions, 0 deletions
diff --git a/passes/fsm/fsm_extract.cc b/passes/fsm/fsm_extract.cc
new file mode 100644
index 00000000..bdcb1d45
--- /dev/null
+++ b/passes/fsm/fsm_extract.cc
@@ -0,0 +1,359 @@
+/*
+ * yosys -- Yosys Open SYnthesis Suite
+ *
+ * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "kernel/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+
+static RTLIL::Module *module;
+static SigMap assign_map;
+typedef std::pair<RTLIL::Cell*,std::string> sig2driver_entry_t;
+static SigSet<sig2driver_entry_t> sig2driver, sig2trigger;
+
+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)
+{
+ sig.extend(dff_out.width, false);
+
+ if (sig == dff_out)
+ return true;
+
+ assign_map.apply(sig);
+ if (sig.is_fully_const()) {
+ sig.optimize();
+ assert(sig.chunks.size() == 1);
+ if (states.count(sig.chunks[0].data) == 0) {
+ log(" found state code: %s\n", log_signal(sig));
+ states[sig.chunks[0].data] = -1;
+ }
+ return true;
+ }
+
+ std::set<sig2driver_entry_t> cellport_list;
+ sig2driver.find(sig, cellport_list);
+ for (auto &cellport : cellport_list) {
+ if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux" && cellport.first->type != "$safe_pmux") || cellport.second != "\\Y") {
+ log(" unexpected cell type %s (%s) found in state selection tree.\n",
+ cellport.first->type.c_str(), cellport.first->name.c_str());
+ return false;
+ }
+ RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]);
+ RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]);
+ RTLIL::SigSpec sig_s = assign_map(cellport.first->connections["\\S"]);
+ if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef())
+ do {
+ if (sig_a.is_fully_def())
+ *reset_state = sig_a.as_const();
+ else if (sig_b.is_fully_def())
+ *reset_state = sig_b.as_const();
+ else
+ break;
+ log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state));
+ } while (0);
+ if (ctrl.extract(sig_s).width == 0) {
+ log(" found ctrl input: %s\n", log_signal(sig_s));
+ ctrl.append(sig_s);
+ }
+ if (!find_states(sig_a, dff_out, ctrl, states))
+ return false;
+ for (int i = 0; i < sig_b.width/sig_a.width; i++) {
+ if (!find_states(sig_b.extract(i*sig_a.width, sig_a.width), dff_out, ctrl, states))
+ return false;
+ }
+ }
+
+ return true;
+}
+
+static RTLIL::Const sig2const(ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care = RTLIL::SigSpec())
+{
+ if (dont_care.width > 0) {
+ sig.expand();
+ for (auto &chunk : sig.chunks) {
+ assert(chunk.width == 1);
+ if (dont_care.extract(chunk).width > 0)
+ chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state);
+ }
+ sig.optimize();
+ }
+
+ ce.assign_map.apply(sig);
+ ce.values_map.apply(sig);
+
+ sig.expand();
+ for (auto &chunk : sig.chunks) {
+ assert(chunk.width == 1);
+ if (chunk.wire != NULL)
+ chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state);
+ }
+ sig.optimize();
+
+ if (sig.width == 0)
+ return RTLIL::Const();
+ assert(sig.chunks.size() == 1 && sig.chunks[0].wire == NULL);
+ return sig.chunks[0].data;
+}
+
+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)
+{
+ RTLIL::SigSpec undef, constval;
+
+ if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef)) {
+ assert(ctrl_out.is_fully_const() && dff_in.is_fully_const());
+ FsmData::transition_t tr;
+ tr.state_in = state_in;
+ tr.state_out = states[ce.values_map(ce.assign_map(dff_in)).as_const()];
+ tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care);
+ tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx);
+ RTLIL::Const log_state_in = RTLIL::Const(RTLIL::State::Sx, fsm_data.state_bits);
+ if (state_in >= 0)
+ log_state_in = fsm_data.state_table[tr.state_in];
+ if (dff_in.is_fully_def()) {
+ fsm_data.transition_table.push_back(tr);
+ log(" transition: %10s %s -> %10s %s\n",
+ log_signal(log_state_in), log_signal(tr.ctrl_in),
+ log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
+ } else {
+ log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n",
+ log_signal(log_state_in), log_signal(tr.ctrl_in),
+ log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
+ }
+ return;
+ }
+
+ assert(undef.width > 0);
+ assert(ce.stop_signals.check_all(undef));
+
+ undef = undef.extract(0, 1);
+ constval = undef;
+
+ if (ce_nostop.eval(constval))
+ {
+ ce.push();
+ dont_care.append(undef);
+ ce.set(undef, constval.as_const());
+ find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+ ce.pop();
+ }
+ else
+ {
+ ce.push(), ce_nostop.push();
+ ce.set(undef, RTLIL::Const(0, 1));
+ ce_nostop.set(undef, RTLIL::Const(0, 1));
+ find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+ ce.pop(), ce_nostop.pop();
+
+ ce.push(), ce_nostop.push();
+ ce.set(undef, RTLIL::Const(1, 1));
+ ce_nostop.set(undef, RTLIL::Const(1, 1));
+ find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+ ce.pop(), ce_nostop.pop();
+ }
+}
+
+static void extract_fsm(RTLIL::Wire *wire)
+{
+ log("Extracting FSM `%s' from module `%s'.\n", wire->name.c_str(), module->name.c_str());
+
+ // get input and output signals for state ff
+
+ RTLIL::SigSpec dff_out = assign_map(RTLIL::SigSpec(wire));
+ RTLIL::SigSpec dff_in(RTLIL::State::Sm, wire->width);
+ RTLIL::Const reset_state(RTLIL::State::Sx, wire->width);
+
+ RTLIL::SigSpec clk = RTLIL::SigSpec(0, 1);
+ RTLIL::SigSpec arst = RTLIL::SigSpec(0, 1);
+ bool clk_polarity = true;
+ bool arst_polarity = true;
+
+ std::set<sig2driver_entry_t> cellport_list;
+ sig2driver.find(dff_out, cellport_list);
+ for (auto &cellport : cellport_list) {
+ if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
+ continue;
+ log(" found %s cell for state register: %s\n", cellport.first->type.c_str(), cellport.first->name.c_str());
+ RTLIL::SigSpec sig_q = assign_map(cellport.first->connections["\\Q"]);
+ RTLIL::SigSpec sig_d = assign_map(cellport.first->connections["\\D"]);
+ clk = cellport.first->connections["\\CLK"];
+ clk_polarity = cellport.first->parameters["\\CLK_POLARITY"].as_bool();
+ if (cellport.first->type == "$adff") {
+ arst = cellport.first->connections["\\ARST"];
+ arst_polarity = cellport.first->parameters["\\ARST_POLARITY"].as_bool();
+ reset_state = cellport.first->parameters["\\ARST_VALUE"];
+ }
+ sig_q.replace(dff_out, sig_d, &dff_in);
+ break;
+ }
+
+ log(" root of input selection tree: %s\n", log_signal(dff_in));
+ if (dff_in.has_marked_bits()) {
+ log(" fsm extraction failed: incomplete input selection tree root.\n");
+ return;
+ }
+
+ // find states and control inputs
+
+ RTLIL::SigSpec ctrl_in;
+ std::map<RTLIL::Const, int> states;
+ if (!arst.is_fully_const()) {
+ log(" found reset state: %s (from async reset)\n", log_signal(reset_state));
+ states[reset_state] = -1;
+ }
+ if (!find_states(dff_in, dff_out, ctrl_in, states, &reset_state)) {
+ log(" fsm extraction failed: state selection tree is not closed.\n");
+ return;
+ }
+
+ // find control outputs
+ // (add the state signals to the list of control outputs. if everything goes right, this signals
+ // become unused and can then be removed from the fsm control output)
+
+ RTLIL::SigSpec ctrl_out = dff_in;
+ cellport_list.clear();
+ sig2trigger.find(dff_out, cellport_list);
+ for (auto &cellport : cellport_list) {
+ RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]);
+ RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]);
+ RTLIL::SigSpec sig_y = assign_map(cellport.first->connections["\\Y"]);
+ if (cellport.second == "\\A" && !sig_b.is_fully_const())
+ continue;
+ if (cellport.second == "\\B" && !sig_a.is_fully_const())
+ continue;
+ log(" found ctrl output: %s\n", log_signal(sig_y));
+ ctrl_out.append(sig_y);
+ }
+ ctrl_in.remove(ctrl_out);
+
+ log(" ctrl inputs: %s\n", log_signal(ctrl_in));
+ log(" ctrl outputs: %s\n", log_signal(ctrl_out));
+
+ // Initialize fsm data struct
+
+ FsmData fsm_data;
+ fsm_data.num_inputs = ctrl_in.width;
+ fsm_data.num_outputs = ctrl_out.width;
+ fsm_data.state_bits = wire->width;
+ fsm_data.reset_state = -1;
+ for (auto &it : states) {
+ it.second = fsm_data.state_table.size();
+ fsm_data.state_table.push_back(it.first);
+ }
+ if (!arst.is_fully_const() || RTLIL::SigSpec(reset_state).is_fully_def())
+ fsm_data.reset_state = states[reset_state];
+
+ // Create transition table
+
+ ConstEval ce(module), ce_nostop(module);
+ ce.stop(ctrl_in);
+ for (int state_idx = 0; state_idx < int(fsm_data.state_table.size()); state_idx++) {
+ ce.push(), ce_nostop.push();
+ ce.set(dff_out, fsm_data.state_table[state_idx]);
+ ce_nostop.set(dff_out, fsm_data.state_table[state_idx]);
+ find_transitions(ce, ce_nostop, fsm_data, states, state_idx, ctrl_in, ctrl_out, dff_in, RTLIL::SigSpec());
+ ce.pop(), ce_nostop.pop();
+ }
+
+ // create fsm cell
+
+ RTLIL::Cell *fsm_cell = new RTLIL::Cell;
+ fsm_cell->name = stringf("$fsm$%s$%d", wire->name.c_str(), RTLIL::autoidx++);
+ fsm_cell->type = "$fsm";
+ fsm_cell->connections["\\CLK"] = clk;
+ fsm_cell->connections["\\ARST"] = arst;
+ fsm_cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity ? 1 : 0, 1);
+ fsm_cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity ? 1 : 0, 1);
+ fsm_cell->connections["\\CTRL_IN"] = ctrl_in;
+ fsm_cell->connections["\\CTRL_OUT"] = ctrl_out;
+ fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name);
+ fsm_data.copy_to_cell(fsm_cell);
+ module->cells[fsm_cell->name] = fsm_cell;
+
+ // rename original state wire
+
+ module->wires.erase(wire->name);
+ wire->attributes.erase("\\fsm_encoding");
+ wire->name = stringf("$fsm$oldstate%s", wire->name.c_str());
+ module->wires[wire->name] = wire;
+
+ // unconnect control outputs from old drivers
+
+ cellport_list.clear();
+ sig2driver.find(ctrl_out, cellport_list);
+ for (auto &cellport : cellport_list) {
+ RTLIL::SigSpec port_sig = assign_map(cellport.first->connections[cellport.second]);
+ RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out);
+ RTLIL::Wire *unconn_wire = new RTLIL::Wire;
+ unconn_wire->name = stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), RTLIL::autoidx++);
+ unconn_wire->width = unconn_sig.width;
+ module->wires[unconn_wire->name] = unconn_wire;
+ port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cellport.first->connections[cellport.second]);
+ }
+}
+
+struct FsmExtractPass : public Pass {
+ FsmExtractPass() : Pass("fsm_extract") { }
+ virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+ {
+ log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
+ extra_args(args, 1, design);
+
+ CellTypes ct;
+ ct.setup_internals();
+ ct.setup_internals_mem();
+ ct.setup_stdcells();
+ ct.setup_stdcells_mem();
+
+ for (auto &mod_it : design->modules)
+ {
+ module = mod_it.second;
+ assign_map.set(module);
+
+ sig2driver.clear();
+ sig2trigger.clear();
+ for (auto &cell_it : module->cells)
+ for (auto &conn_it : cell_it.second->connections) {
+ if (ct.cell_output(cell_it.second->type, conn_it.first)) {
+ RTLIL::SigSpec sig = conn_it.second;
+ assign_map.apply(sig);
+ sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+ }
+ if (ct.cell_input(cell_it.second->type, conn_it.first) && cell_it.second->connections.count("\\Y") > 0 &&
+ cell_it.second->connections["\\Y"].width == 1 && (conn_it.first == "\\A" || conn_it.first == "\\B")) {
+ RTLIL::SigSpec sig = conn_it.second;
+ assign_map.apply(sig);
+ sig2trigger.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+ }
+ }
+
+ std::vector<RTLIL::Wire*> wire_list;
+ for (auto &wire_it : module->wires)
+ if (wire_it.second->attributes.count("\\fsm_encoding") > 0 && wire_it.second->attributes["\\fsm_encoding"].str != "none")
+ wire_list.push_back(wire_it.second);
+ for (auto wire : wire_list)
+ extract_fsm(wire);
+ }
+
+ assign_map.clear();
+ sig2driver.clear();
+ sig2trigger.clear();
+ }
+} FsmExtractPass;
+