summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorClifford Wolf <clifford@clifford.at>2014-08-09 14:49:51 +0200
committerClifford Wolf <clifford@clifford.at>2014-08-09 14:49:51 +0200
commit2faef8973830e553b1730c07d327c8d76d412e1c (patch)
tree5ad43e1f7d86c4c257a1b111e342ccd2b70e0d87
parent51aa5544fbda97c6b49bfba55696083ba47d4cef (diff)
Some improvements in fsm_opt and fsm_map for FSM with unreachable states
-rw-r--r--passes/fsm/fsm_map.cc107
-rw-r--r--passes/fsm/fsm_opt.cc44
-rwxr-xr-xtests/fsm/run-test.sh3
3 files changed, 103 insertions, 51 deletions
diff --git a/passes/fsm/fsm_map.cc b/passes/fsm/fsm_map.cc
index 99b736c1..b3750de0 100644
--- a/passes/fsm/fsm_map.cc
+++ b/passes/fsm/fsm_map.cc
@@ -207,65 +207,72 @@ static void map_fsm(RTLIL::Cell *fsm_cell, RTLIL::Module *module)
// generate next_state signal
- RTLIL::Wire *next_state_onehot = module->addWire(NEW_ID, fsm_data.state_table.size());
-
- for (size_t i = 0; i < fsm_data.state_table.size(); i++)
+ if (SIZE(fsm_data.state_table) == 1)
{
- std::map<RTLIL::Const, std::set<int>> pattern_cache;
- std::set<int> fullstate_cache;
+ module->connect(next_state_wire, fsm_data.state_table.front());
+ }
+ else
+ {
+ RTLIL::Wire *next_state_onehot = module->addWire(NEW_ID, fsm_data.state_table.size());
- for (size_t j = 0; j < fsm_data.state_table.size(); j++)
- fullstate_cache.insert(j);
+ for (size_t i = 0; i < fsm_data.state_table.size(); i++)
+ {
+ std::map<RTLIL::Const, std::set<int>> pattern_cache;
+ std::set<int> fullstate_cache;
- for (auto &tr : fsm_data.transition_table) {
- if (tr.state_out == int(i))
- pattern_cache[tr.ctrl_in].insert(tr.state_in);
- else
- fullstate_cache.erase(tr.state_in);
- }
+ for (size_t j = 0; j < fsm_data.state_table.size(); j++)
+ fullstate_cache.insert(j);
- implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, i));
- }
+ for (auto &tr : fsm_data.transition_table) {
+ if (tr.state_out == int(i))
+ pattern_cache[tr.ctrl_in].insert(tr.state_in);
+ else
+ fullstate_cache.erase(tr.state_in);
+ }
- if (encoding_is_onehot)
- {
- RTLIL::SigSpec next_state_sig(RTLIL::State::Sm, next_state_wire->width);
- for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
- RTLIL::Const state = fsm_data.state_table[i];
- int bit_idx = -1;
- for (size_t j = 0; j < state.bits.size(); j++)
- if (state.bits[j] == RTLIL::State::S1)
- bit_idx = j;
- if (bit_idx >= 0)
- next_state_sig.replace(bit_idx, RTLIL::SigSpec(next_state_onehot, i));
+ implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, i));
}
- log_assert(!next_state_sig.has_marked_bits());
- module->connect(RTLIL::SigSig(next_state_wire, next_state_sig));
- }
- else
- {
- RTLIL::SigSpec sig_a, sig_b, sig_s;
- int reset_state = fsm_data.reset_state;
- if (reset_state < 0)
- reset_state = 0;
-
- for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
- RTLIL::Const state = fsm_data.state_table[i];
- if (int(i) == fsm_data.reset_state) {
- sig_a = RTLIL::SigSpec(state);
- } else {
- sig_b.append(RTLIL::SigSpec(state));
- sig_s.append(RTLIL::SigSpec(next_state_onehot, i));
+
+ if (encoding_is_onehot)
+ {
+ RTLIL::SigSpec next_state_sig(RTLIL::State::Sm, next_state_wire->width);
+ for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
+ RTLIL::Const state = fsm_data.state_table[i];
+ int bit_idx = -1;
+ for (size_t j = 0; j < state.bits.size(); j++)
+ if (state.bits[j] == RTLIL::State::S1)
+ bit_idx = j;
+ if (bit_idx >= 0)
+ next_state_sig.replace(bit_idx, RTLIL::SigSpec(next_state_onehot, i));
}
+ log_assert(!next_state_sig.has_marked_bits());
+ module->connect(RTLIL::SigSig(next_state_wire, next_state_sig));
}
+ else
+ {
+ RTLIL::SigSpec sig_a, sig_b, sig_s;
+ int reset_state = fsm_data.reset_state;
+ if (reset_state < 0)
+ reset_state = 0;
+
+ for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
+ RTLIL::Const state = fsm_data.state_table[i];
+ if (int(i) == fsm_data.reset_state) {
+ sig_a = RTLIL::SigSpec(state);
+ } else {
+ sig_b.append(RTLIL::SigSpec(state));
+ sig_s.append(RTLIL::SigSpec(next_state_onehot, i));
+ }
+ }
- RTLIL::Cell *mux_cell = module->addCell(NEW_ID, "$safe_pmux");
- mux_cell->setPort("\\A", sig_a);
- mux_cell->setPort("\\B", sig_b);
- mux_cell->setPort("\\S", sig_s);
- mux_cell->setPort("\\Y", RTLIL::SigSpec(next_state_wire));
- mux_cell->parameters["\\WIDTH"] = RTLIL::Const(sig_a.size());
- mux_cell->parameters["\\S_WIDTH"] = RTLIL::Const(sig_s.size());
+ RTLIL::Cell *mux_cell = module->addCell(NEW_ID, "$safe_pmux");
+ mux_cell->setPort("\\A", sig_a);
+ mux_cell->setPort("\\B", sig_b);
+ mux_cell->setPort("\\S", sig_s);
+ mux_cell->setPort("\\Y", RTLIL::SigSpec(next_state_wire));
+ mux_cell->parameters["\\WIDTH"] = RTLIL::Const(sig_a.size());
+ mux_cell->parameters["\\S_WIDTH"] = RTLIL::Const(sig_s.size());
+ }
}
// Generate ctrl_out signal
diff --git a/passes/fsm/fsm_opt.cc b/passes/fsm/fsm_opt.cc
index bcaa89bf..a0e1885e 100644
--- a/passes/fsm/fsm_opt.cc
+++ b/passes/fsm/fsm_opt.cc
@@ -30,6 +30,48 @@ struct FsmOpt
FsmData fsm_data;
RTLIL::Cell *cell;
RTLIL::Module *module;
+
+ void opt_unreachable_states()
+ {
+ while (1)
+ {
+ std::set<int> unreachable_states;
+ std::vector<FsmData::transition_t> new_transition_table;
+ std::vector<RTLIL::Const> new_state_table;
+ std::map<int, int> old_to_new_state;
+
+ for (int i = 0; i < SIZE(fsm_data.state_table); i++)
+ if (i != fsm_data.reset_state)
+ unreachable_states.insert(i);
+
+ for (auto &trans : fsm_data.transition_table)
+ unreachable_states.erase(trans.state_out);
+
+ if (unreachable_states.empty())
+ break;
+
+ for (int i = 0; i < SIZE(fsm_data.state_table); i++) {
+ if (unreachable_states.count(i)) {
+ log(" Removing unreachable state %s.\n", log_signal(fsm_data.state_table[i]));
+ continue;
+ }
+ old_to_new_state[i] = SIZE(new_state_table);
+ new_state_table.push_back(fsm_data.state_table[i]);
+ }
+
+ for (auto trans : fsm_data.transition_table) {
+ if (unreachable_states.count(trans.state_in))
+ continue;
+ trans.state_in = old_to_new_state.at(trans.state_in);
+ trans.state_out = old_to_new_state.at(trans.state_out);
+ new_transition_table.push_back(trans);
+ }
+
+ new_transition_table.swap(fsm_data.transition_table);
+ new_state_table.swap(fsm_data.state_table);
+ fsm_data.reset_state = old_to_new_state.at(fsm_data.reset_state);
+ }
+ }
bool signal_is_unused(RTLIL::SigSpec sig)
{
@@ -253,6 +295,8 @@ struct FsmOpt
this->cell = cell;
this->module = module;
+ opt_unreachable_states();
+
opt_unused_outputs();
opt_alias_inputs();
diff --git a/tests/fsm/run-test.sh b/tests/fsm/run-test.sh
index f5299c09..3d0ff757 100755
--- a/tests/fsm/run-test.sh
+++ b/tests/fsm/run-test.sh
@@ -17,7 +17,8 @@ python generate.py
idx=$( printf "%05d" $i )
echo "temp/uut_${idx}.log: temp/uut_${idx}.ys temp/uut_${idx}.v"
echo " @echo -n '[$i]'"
- echo " @../../yosys -ql temp/uut_${idx}.log temp/uut_${idx}.ys"
+ echo " @../../yosys -ql temp/uut_${idx}.out temp/uut_${idx}.ys"
+ echo " @mv temp/uut_${idx}.out temp/uut_${idx}.log"
echo " @grep -q 'SAT proof finished' temp/uut_${idx}.log && echo -n K || echo -n T"
all_targets="$all_targets temp/uut_${idx}.log"
done