#include "kernel/log.h"
#include "kernel/register.h"
#include "kernel/sigtools.h"
#include "kernel/consteval.h"
#include "kernel/celltypes.h"
#include "fsmdata.h"

Include dependency graph for fsm_extract.cc:

Go to the source code of this file.

Data Structures
struct	FsmExtractPass

Typedefs
typedef std::pair < RTLIL::IdString, RTLIL::IdString >	sig2driver_entry_t

Functions
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)

static RTLIL::Const	sig2const (ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care=RTLIL::SigSpec())

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)

static void	extract_fsm (RTLIL::Wire *wire)

Variables
USING_YOSYS_NAMESPACE static PRIVATE_NAMESPACE_BEGIN RTLIL::Module *	module

static SigMap	assign_map

static SigSet< sig2driver_entry_t >	sig2driver

static SigSet< sig2driver_entry_t >	sig2trigger

static std::map< RTLIL::SigBit, std::set< RTLIL::SigBit > >	exclusive_ctrls

FsmExtractPass	FsmExtractPass

Typedef Documentation

typedef std::pair<RTLIL::IdString, RTLIL::IdString> sig2driver_entry_t

Definition at line 37 of file fsm_extract.cc.

Function Documentation

static void extract_fsm ( RTLIL::Wire * wire )

static

Definition at line 240 of file fsm_extract.cc.

 {
     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::S0;
     RTLIL::SigSpec arst = RTLIL::S0;
     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) {
         RTLIL::Cell *cell = module->cells_.at(cellport.first);
         if ((cell->type != "$dff" && cell->type != "$adff") || cellport.second != "\\Q")
             continue;
         log("  found %s cell for state register: %s\n", cell->type.c_str(), cell->name.c_str());
         RTLIL::SigSpec sig_q = assign_map(cell->getPort("\\Q"));
         RTLIL::SigSpec sig_d = assign_map(cell->getPort("\\D"));
         clk = cell->getPort("\\CLK");
         clk_polarity = cell->parameters["\\CLK_POLARITY"].as_bool();
         if (cell->type == "$adff") {
             arst = cell->getPort("\\ARST");
             arst_polarity = cell->parameters["\\ARST_POLARITY"].as_bool();
             reset_state = cell->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;
     }
     if (GetSize(states) <= 1) {
         log("  fsm extraction failed: at least two states are required.\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::Cell *cell = module->cells_.at(cellport.first);
         RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
         RTLIL::SigSpec sig_b = assign_map(cell->getPort("\\B"));
         RTLIL::SigSpec sig_y = assign_map(cell->getPort("\\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);
 
     ctrl_in.sort_and_unify();
     ctrl_out.sort_and_unify();
 
     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.size();
     fsm_data.num_outputs = ctrl_out.size();
     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 = module->addCell(stringf("$fsm$%s$%d", wire->name.c_str(), autoidx++), "$fsm");
     fsm_cell->setPort("\\CLK", clk);
     fsm_cell->setPort("\\ARST", arst);
     fsm_cell->parameters["\\CLK_POLARITY"] = clk_polarity ? RTLIL::S1 : RTLIL::S0;
     fsm_cell->parameters["\\ARST_POLARITY"] = arst_polarity ? RTLIL::S1 : RTLIL::S0;
     fsm_cell->setPort("\\CTRL_IN", ctrl_in);
     fsm_cell->setPort("\\CTRL_OUT", ctrl_out);
     fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name.str());
     fsm_cell->attributes = wire->attributes;
     fsm_data.copy_to_cell(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::Cell *cell = module->cells_.at(cellport.first);
         RTLIL::SigSpec port_sig = assign_map(cell->getPort(cellport.second));
         RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out);
         RTLIL::Wire *unconn_wire = module->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), autoidx++), unconn_sig.size());
         port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cell->connections_[cellport.second]);
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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`
	)

static

Definition at line 41 of file fsm_extract.cc.

 {
     sig.extend(dff_out.size(), false);
 
     if (sig == dff_out)
         return true;
 
     assign_map.apply(sig);
     if (sig.is_fully_const()) {
         if (sig.is_fully_def() && states.count(sig.as_const()) == 0) {
             log("  found state code: %s\n", log_signal(sig));
             states[sig.as_const()] = -1;
         }
         return true;
     }
 
     std::set<sig2driver_entry_t> cellport_list;
     sig2driver.find(sig, cellport_list);
     for (auto &cellport : cellport_list)
     {
         RTLIL::Cell *cell = module->cells_.at(cellport.first);
         if ((cell->type != "$mux" && cell->type != "$pmux") || cellport.second != "\\Y") {
             log("  unexpected cell type %s (%s) found in state selection tree.\n", cell->type.c_str(), cell->name.c_str());
             return false;
         }
 
         RTLIL::SigSpec sig_a = assign_map(cell->getPort("\\A"));
         RTLIL::SigSpec sig_b = assign_map(cell->getPort("\\B"));
         RTLIL::SigSpec sig_s = assign_map(cell->getPort("\\S"));
         RTLIL::SigSpec sig_y = assign_map(cell->getPort("\\Y"));
 
         RTLIL::SigSpec sig_aa = sig;
         sig_aa.replace(sig_y, sig_a);
 
         RTLIL::SigSpec sig_bb;
         for (int i = 0; i < GetSize(sig_b)/GetSize(sig_a); i++) {
             RTLIL::SigSpec s = sig;
             s.replace(sig_y, sig_b.extract(i*GetSize(sig_a), GetSize(sig_a)));
             sig_bb.append(s);
         }
 
         if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef())
             do {
                 if (sig_aa.is_fully_def())
                     *reset_state = sig_aa.as_const();
                 else if (sig_bb.is_fully_def())
                     *reset_state = sig_bb.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).size() == 0) {
             log("  found ctrl input: %s\n", log_signal(sig_s));
             ctrl.append(sig_s);
         }
 
         if (!find_states(sig_aa, dff_out, ctrl, states))
             return false;
 
         for (int i = 0; i < GetSize(sig_bb)/GetSize(sig_aa); i++) {
             if (!find_states(sig_bb.extract(i*GetSize(sig_aa), GetSize(sig_aa)), dff_out, ctrl, states))
                 return false;
         }
     }
 
     return true;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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
	)

static

Definition at line 128 of file fsm_extract.cc.

 {
     bool undef_bit_in_next_state_mode = false;
     RTLIL::SigSpec undef, constval;
 
     if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef))
     {
         if (0) {
 undef_bit_in_next_state:
             for (auto &bit : dff_in)
                 if (bit.wire != nullptr) bit = RTLIL::Sm;
             for (auto &bit : ctrl_out)
                 if (bit.wire != nullptr) bit = RTLIL::Sm;
             undef_bit_in_next_state_mode = true;
         }
 
         log_assert(ctrl_out.is_fully_const() && dff_in.is_fully_const());
 
         FsmData::transition_t tr;
         tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care);
         tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx);
 
         std::map<RTLIL::SigBit, int> ctrl_in_bit_indices;
         for (int i = 0; i < GetSize(ctrl_in); i++)
             ctrl_in_bit_indices[ctrl_in[i]] = i;
 
         for (auto &it : ctrl_in_bit_indices)
             if (tr.ctrl_in.bits.at(it.second) == RTLIL::S1 && exclusive_ctrls.count(it.first) != 0)
                 for (auto &dc_bit : exclusive_ctrls.at(it.first))
                     if (ctrl_in_bit_indices.count(dc_bit))
                         tr.ctrl_in.bits.at(ctrl_in_bit_indices.at(dc_bit)) = RTLIL::State::Sa;
 
         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.at(state_in);
 
         if (states.count(ce.values_map(ce.assign_map(dff_in)).as_const()) == 0) {
             log("  transition: %10s %s -> INVALID_STATE(%s) %s  <ignored invalid transistion!>%s\n",
                     log_signal(log_state_in), log_signal(tr.ctrl_in),
                     log_signal(ce.values_map(ce.assign_map(dff_in))), log_signal(tr.ctrl_out),
                     undef_bit_in_next_state_mode ? " SHORTENED" : "");
             return;
         }
 
         tr.state_in = state_in;
         tr.state_out = states.at(ce.values_map(ce.assign_map(dff_in)).as_const());
 
         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;
     }
 
     for (auto &bit : dff_in)
         if (bit == RTLIL::Sx)
             goto undef_bit_in_next_state;
 
     log_assert(undef.size() > 0);
     log_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());
         if (exclusive_ctrls.count(undef) && constval == RTLIL::S1)
             for (auto &bit : exclusive_ctrls.at(undef)) {
                 RTLIL::SigSpec bitval = bit;
                 if (ce.eval(bitval) && bitval != RTLIL::S0)
                     goto found_contradiction_1;
                 else
                     ce.set(bit, RTLIL::S0);
             }
         find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
     found_contradiction_1:
         ce.pop();
     }
     else
     {
         ce.push(), ce_nostop.push();
         ce.set(undef, RTLIL::S0);
         ce_nostop.set(undef, RTLIL::S0);
         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::S1);
         ce_nostop.set(undef, RTLIL::S1);
         if (exclusive_ctrls.count(undef))
             for (auto &bit : exclusive_ctrls.at(undef)) {
                 RTLIL::SigSpec bitval = bit;
                 if ((ce.eval(bitval) || ce_nostop.eval(bitval)) && bitval != RTLIL::S0)
                     goto found_contradiction_2;
                 else
                     ce.set(bit, RTLIL::S0), ce_nostop.set(bit, RTLIL::S0);
             }
         find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
     found_contradiction_2:
         ce.pop(), ce_nostop.pop();
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

static RTLIL::Const sig2const	(	ConstEval &	ce,
		RTLIL::SigSpec	sig,
		RTLIL::State	noconst_state,
		RTLIL::SigSpec	dont_care = `RTLIL::SigSpec()`
	)

static

Definition at line 110 of file fsm_extract.cc.

 {
     if (dont_care.size() > 0) {
         for (int i = 0; i < GetSize(sig); i++)
             if (dont_care.extract(sig[i]).size() > 0)
                 sig[i] = noconst_state;
     }
 
     ce.assign_map.apply(sig);
     ce.values_map.apply(sig);
 
     for (int i = 0; i < GetSize(sig); i++)
         if (sig[i].wire != NULL)
             sig[i] = noconst_state;
 
     return sig.as_const();
 }