From 2faef8973830e553b1730c07d327c8d76d412e1c Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 9 Aug 2014 14:49:51 +0200 Subject: [PATCH] Some improvements in fsm_opt and fsm_map for FSM with unreachable states --- passes/fsm/fsm_map.cc | 107 ++++++++++++++++++++++-------------------- passes/fsm/fsm_opt.cc | 44 +++++++++++++++++ tests/fsm/run-test.sh | 3 +- 3 files changed, 103 insertions(+), 51 deletions(-) diff --git a/passes/fsm/fsm_map.cc b/passes/fsm/fsm_map.cc index 99b736c1b..b3750de08 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> pattern_cache; - std::set 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> pattern_cache; + std::set 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 bcaa89bf0..a0e1885ec 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 unreachable_states; + std::vector new_transition_table; + std::vector new_state_table; + std::map 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 f5299c092..3d0ff7573 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 -- 2.30.2