2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
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.
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.
21 // Yiqiong Shi; Chan Wai Ting; Bah-Hwee Gwee; Ye Ren, "A highly efficient method for extracting FSMs from flattened gate-level netlist,"
22 // Circuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on , vol., no., pp.2610,2613, May 30 2010-June 2 2010
23 // doi: 10.1109/ISCAS.2010.5537093
25 #include "kernel/log.h"
26 #include "kernel/register.h"
27 #include "kernel/sigtools.h"
28 #include "kernel/consteval.h"
29 #include "kernel/celltypes.h"
33 PRIVATE_NAMESPACE_BEGIN
35 static RTLIL::Module
*module
;
36 static SigMap assign_map
;
37 typedef std::pair
<RTLIL::IdString
, RTLIL::IdString
> sig2driver_entry_t
;
38 static SigSet
<sig2driver_entry_t
> sig2driver
, sig2trigger
;
39 static std::map
<RTLIL::SigBit
, std::set
<RTLIL::SigBit
>> exclusive_ctrls
;
41 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
)
43 sig
.extend_u0(dff_out
.size(), false);
48 assign_map
.apply(sig
);
49 if (sig
.is_fully_const()) {
50 if (sig
.is_fully_def() && states
.count(sig
.as_const()) == 0) {
51 log(" found state code: %s\n", log_signal(sig
));
52 states
[sig
.as_const()] = -1;
57 std::set
<sig2driver_entry_t
> cellport_list
;
58 sig2driver
.find(sig
, cellport_list
);
60 if (GetSize(cellport_list
) > 1) {
61 log(" found %d combined drivers for state signal %s.\n", GetSize(cellport_list
), log_signal(sig
));
65 if (GetSize(cellport_list
) < 1) {
66 log(" found no driver for state signal %s.\n", log_signal(sig
));
70 for (auto &cellport
: cellport_list
)
72 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
73 if ((cell
->type
!= "$mux" && cell
->type
!= "$pmux") || cellport
.second
!= "\\Y") {
74 log(" unexpected cell type %s (%s) found in state selection tree.\n", cell
->type
.c_str(), cell
->name
.c_str());
78 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
79 RTLIL::SigSpec sig_b
= assign_map(cell
->getPort("\\B"));
80 RTLIL::SigSpec sig_s
= assign_map(cell
->getPort("\\S"));
81 RTLIL::SigSpec sig_y
= assign_map(cell
->getPort("\\Y"));
83 RTLIL::SigSpec sig_aa
= sig
;
84 sig_aa
.replace(sig_y
, sig_a
);
86 RTLIL::SigSpec sig_bb
;
87 for (int i
= 0; i
< GetSize(sig_b
)/GetSize(sig_a
); i
++) {
88 RTLIL::SigSpec s
= sig
;
89 s
.replace(sig_y
, sig_b
.extract(i
*GetSize(sig_a
), GetSize(sig_a
)));
93 if (reset_state
&& RTLIL::SigSpec(*reset_state
).is_fully_undef())
95 SigSpec new_reset_state
;
96 if (sig_aa
.is_fully_def())
97 new_reset_state
= sig_aa
.as_const();
98 else if (sig_bb
.is_fully_def())
99 new_reset_state
= sig_bb
.as_const();
102 new_reset_state
.extend_u0(GetSize(*reset_state
));
103 *reset_state
= new_reset_state
.as_const();
104 log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state
));
107 for (auto sig_s_bit
: sig_s
) {
108 if (ctrl
.extract(sig_s_bit
).empty()) {
109 log(" found ctrl input: %s\n", log_signal(sig_s_bit
));
110 ctrl
.append(sig_s_bit
);
114 if (!find_states(sig_aa
, dff_out
, ctrl
, states
))
117 for (int i
= 0; i
< GetSize(sig_bb
)/GetSize(sig_aa
); i
++) {
118 if (!find_states(sig_bb
.extract(i
*GetSize(sig_aa
), GetSize(sig_aa
)), dff_out
, ctrl
, states
))
126 static RTLIL::Const
sig2const(ConstEval
&ce
, RTLIL::SigSpec sig
, RTLIL::State noconst_state
, RTLIL::SigSpec dont_care
= RTLIL::SigSpec())
128 if (dont_care
.size() > 0) {
129 for (int i
= 0; i
< GetSize(sig
); i
++)
130 if (dont_care
.extract(sig
[i
]).size() > 0)
131 sig
[i
] = noconst_state
;
134 ce
.assign_map
.apply(sig
);
135 ce
.values_map
.apply(sig
);
137 for (int i
= 0; i
< GetSize(sig
); i
++)
138 if (sig
[i
].wire
!= NULL
)
139 sig
[i
] = noconst_state
;
141 return sig
.as_const();
144 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
)
146 bool undef_bit_in_next_state_mode
= false;
147 RTLIL::SigSpec undef
, constval
;
149 if (ce
.eval(ctrl_out
, undef
) && ce
.eval(dff_in
, undef
))
152 undef_bit_in_next_state
:
153 for (auto &bit
: dff_in
)
154 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
155 for (auto &bit
: ctrl_out
)
156 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
157 undef_bit_in_next_state_mode
= true;
160 log_assert(ctrl_out
.is_fully_const() && dff_in
.is_fully_const());
162 FsmData::transition_t tr
;
163 tr
.ctrl_in
= sig2const(ce
, ctrl_in
, RTLIL::State::Sa
, dont_care
);
164 tr
.ctrl_out
= sig2const(ce
, ctrl_out
, RTLIL::State::Sx
);
166 std::map
<RTLIL::SigBit
, int> ctrl_in_bit_indices
;
167 for (int i
= 0; i
< GetSize(ctrl_in
); i
++)
168 ctrl_in_bit_indices
[ctrl_in
[i
]] = i
;
170 for (auto &it
: ctrl_in_bit_indices
)
171 if (tr
.ctrl_in
.bits
.at(it
.second
) == RTLIL::S1
&& exclusive_ctrls
.count(it
.first
) != 0)
172 for (auto &dc_bit
: exclusive_ctrls
.at(it
.first
))
173 if (ctrl_in_bit_indices
.count(dc_bit
))
174 tr
.ctrl_in
.bits
.at(ctrl_in_bit_indices
.at(dc_bit
)) = RTLIL::State::Sa
;
176 RTLIL::Const log_state_in
= RTLIL::Const(RTLIL::State::Sx
, fsm_data
.state_bits
);
178 log_state_in
= fsm_data
.state_table
.at(state_in
);
180 if (states
.count(ce
.values_map(ce
.assign_map(dff_in
)).as_const()) == 0) {
181 log(" transition: %10s %s -> INVALID_STATE(%s) %s <ignored invalid transistion!>%s\n",
182 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
183 log_signal(ce
.values_map(ce
.assign_map(dff_in
))), log_signal(tr
.ctrl_out
),
184 undef_bit_in_next_state_mode
? " SHORTENED" : "");
188 tr
.state_in
= state_in
;
189 tr
.state_out
= states
.at(ce
.values_map(ce
.assign_map(dff_in
)).as_const());
191 if (dff_in
.is_fully_def()) {
192 fsm_data
.transition_table
.push_back(tr
);
193 log(" transition: %10s %s -> %10s %s\n",
194 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
195 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
197 log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n",
198 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
199 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
204 for (auto &bit
: dff_in
)
205 if (bit
== RTLIL::Sx
)
206 goto undef_bit_in_next_state
;
208 log_assert(undef
.size() > 0);
209 log_assert(ce
.stop_signals
.check_all(undef
));
211 undef
= undef
.extract(0, 1);
214 if (ce_nostop
.eval(constval
))
217 dont_care
.append(undef
);
218 ce
.set(undef
, constval
.as_const());
219 if (exclusive_ctrls
.count(undef
) && constval
== RTLIL::S1
)
220 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
221 RTLIL::SigSpec bitval
= bit
;
222 if (ce
.eval(bitval
) && bitval
!= RTLIL::S0
)
223 goto found_contradiction_1
;
225 ce
.set(bit
, RTLIL::S0
);
227 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
228 found_contradiction_1
:
233 ce
.push(), ce_nostop
.push();
234 ce
.set(undef
, RTLIL::S0
);
235 ce_nostop
.set(undef
, RTLIL::S0
);
236 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
237 ce
.pop(), ce_nostop
.pop();
239 ce
.push(), ce_nostop
.push();
240 ce
.set(undef
, RTLIL::S1
);
241 ce_nostop
.set(undef
, RTLIL::S1
);
242 if (exclusive_ctrls
.count(undef
))
243 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
244 RTLIL::SigSpec bitval
= bit
;
245 if ((ce
.eval(bitval
) || ce_nostop
.eval(bitval
)) && bitval
!= RTLIL::S0
)
246 goto found_contradiction_2
;
248 ce
.set(bit
, RTLIL::S0
), ce_nostop
.set(bit
, RTLIL::S0
);
250 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
251 found_contradiction_2
:
252 ce
.pop(), ce_nostop
.pop();
256 static void extract_fsm(RTLIL::Wire
*wire
)
258 log("Extracting FSM `%s' from module `%s'.\n", wire
->name
.c_str(), module
->name
.c_str());
260 // get input and output signals for state ff
262 RTLIL::SigSpec dff_out
= assign_map(RTLIL::SigSpec(wire
));
263 RTLIL::SigSpec
dff_in(RTLIL::State::Sm
, wire
->width
);
264 RTLIL::Const
reset_state(RTLIL::State::Sx
, wire
->width
);
266 RTLIL::SigSpec clk
= RTLIL::S0
;
267 RTLIL::SigSpec arst
= RTLIL::S0
;
268 bool clk_polarity
= true;
269 bool arst_polarity
= true;
271 std::set
<sig2driver_entry_t
> cellport_list
;
272 sig2driver
.find(dff_out
, cellport_list
);
273 for (auto &cellport
: cellport_list
) {
274 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
275 if ((cell
->type
!= "$dff" && cell
->type
!= "$adff") || cellport
.second
!= "\\Q")
277 log(" found %s cell for state register: %s\n", cell
->type
.c_str(), cell
->name
.c_str());
278 RTLIL::SigSpec sig_q
= assign_map(cell
->getPort("\\Q"));
279 RTLIL::SigSpec sig_d
= assign_map(cell
->getPort("\\D"));
280 clk
= cell
->getPort("\\CLK");
281 clk_polarity
= cell
->parameters
["\\CLK_POLARITY"].as_bool();
282 if (cell
->type
== "$adff") {
283 arst
= cell
->getPort("\\ARST");
284 arst_polarity
= cell
->parameters
["\\ARST_POLARITY"].as_bool();
285 reset_state
= cell
->parameters
["\\ARST_VALUE"];
287 sig_q
.replace(dff_out
, sig_d
, &dff_in
);
291 log(" root of input selection tree: %s\n", log_signal(dff_in
));
292 if (dff_in
.has_marked_bits()) {
293 log(" fsm extraction failed: incomplete input selection tree root.\n");
297 // find states and control inputs
299 RTLIL::SigSpec ctrl_in
;
300 std::map
<RTLIL::Const
, int> states
;
301 if (!arst
.is_fully_const()) {
302 log(" found reset state: %s (from async reset)\n", log_signal(reset_state
));
303 states
[reset_state
] = -1;
305 if (!find_states(dff_in
, dff_out
, ctrl_in
, states
, &reset_state
)) {
306 log(" fsm extraction failed: state selection tree is not closed.\n");
309 if (GetSize(states
) <= 1) {
310 log(" fsm extraction failed: at least two states are required.\n");
314 // find control outputs
315 // (add the state signals to the list of control outputs. if everything goes right, this signals
316 // become unused and can then be removed from the fsm control output)
318 RTLIL::SigSpec ctrl_out
= dff_in
;
319 cellport_list
.clear();
320 sig2trigger
.find(dff_out
, cellport_list
);
321 for (auto &cellport
: cellport_list
) {
322 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
323 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
324 RTLIL::SigSpec sig_b
;
325 if (cell
->hasPort("\\B"))
326 sig_b
= assign_map(cell
->getPort("\\B"));
327 RTLIL::SigSpec sig_y
= assign_map(cell
->getPort("\\Y"));
328 if (cellport
.second
== "\\A" && !sig_b
.is_fully_const())
330 if (cellport
.second
== "\\B" && !sig_a
.is_fully_const())
332 log(" found ctrl output: %s\n", log_signal(sig_y
));
333 ctrl_out
.append(sig_y
);
335 ctrl_in
.remove(ctrl_out
);
337 ctrl_in
.sort_and_unify();
338 ctrl_out
.sort_and_unify();
340 log(" ctrl inputs: %s\n", log_signal(ctrl_in
));
341 log(" ctrl outputs: %s\n", log_signal(ctrl_out
));
343 // Initialize fsm data struct
346 fsm_data
.num_inputs
= ctrl_in
.size();
347 fsm_data
.num_outputs
= ctrl_out
.size();
348 fsm_data
.state_bits
= wire
->width
;
349 fsm_data
.reset_state
= -1;
350 for (auto &it
: states
) {
351 it
.second
= fsm_data
.state_table
.size();
352 fsm_data
.state_table
.push_back(it
.first
);
354 if (!arst
.is_fully_const() || RTLIL::SigSpec(reset_state
).is_fully_def())
355 fsm_data
.reset_state
= states
[reset_state
];
357 // Create transition table
359 ConstEval
ce(module
), ce_nostop(module
);
361 for (int state_idx
= 0; state_idx
< int(fsm_data
.state_table
.size()); state_idx
++) {
362 ce
.push(), ce_nostop
.push();
363 ce
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
364 ce_nostop
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
365 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_idx
, ctrl_in
, ctrl_out
, dff_in
, RTLIL::SigSpec());
366 ce
.pop(), ce_nostop
.pop();
371 RTLIL::Cell
*fsm_cell
= module
->addCell(stringf("$fsm$%s$%d", wire
->name
.c_str(), autoidx
++), "$fsm");
372 fsm_cell
->setPort("\\CLK", clk
);
373 fsm_cell
->setPort("\\ARST", arst
);
374 fsm_cell
->parameters
["\\CLK_POLARITY"] = clk_polarity
? RTLIL::S1
: RTLIL::S0
;
375 fsm_cell
->parameters
["\\ARST_POLARITY"] = arst_polarity
? RTLIL::S1
: RTLIL::S0
;
376 fsm_cell
->setPort("\\CTRL_IN", ctrl_in
);
377 fsm_cell
->setPort("\\CTRL_OUT", ctrl_out
);
378 fsm_cell
->parameters
["\\NAME"] = RTLIL::Const(wire
->name
.str());
379 fsm_cell
->attributes
= wire
->attributes
;
380 fsm_data
.copy_to_cell(fsm_cell
);
382 // rename original state wire
384 module
->wires_
.erase(wire
->name
);
385 wire
->attributes
.erase("\\fsm_encoding");
386 wire
->name
= stringf("$fsm$oldstate%s", wire
->name
.c_str());
387 module
->wires_
[wire
->name
] = wire
;
389 // unconnect control outputs from old drivers
391 cellport_list
.clear();
392 sig2driver
.find(ctrl_out
, cellport_list
);
393 for (auto &cellport
: cellport_list
) {
394 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
395 RTLIL::SigSpec port_sig
= assign_map(cell
->getPort(cellport
.second
));
396 RTLIL::SigSpec unconn_sig
= port_sig
.extract(ctrl_out
);
397 RTLIL::Wire
*unconn_wire
= module
->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig
), autoidx
++), unconn_sig
.size());
398 port_sig
.replace(unconn_sig
, RTLIL::SigSpec(unconn_wire
), &cell
->connections_
[cellport
.second
]);
402 struct FsmExtractPass
: public Pass
{
403 FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
406 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
408 log(" fsm_extract [selection]\n");
410 log("This pass operates on all signals marked as FSM state signals using the\n");
411 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
412 log("and uses the state signal to generate control signal and replaces it with an\n");
415 log("The generated FSM cell still generates the original state signal with its\n");
416 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
417 log("'opt_clean' pass to eliminate this signal.\n");
420 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
422 log_header(design
, "Executing FSM_EXTRACT pass (extracting FSM from design).\n");
423 extra_args(args
, 1, design
);
426 ct
.setup_internals();
427 ct
.setup_internals_mem();
429 ct
.setup_stdcells_mem();
431 for (auto &mod_it
: design
->modules_
)
433 if (!design
->selected(mod_it
.second
))
436 module
= mod_it
.second
;
437 assign_map
.set(module
);
441 exclusive_ctrls
.clear();
442 for (auto cell
: module
->cells()) {
443 for (auto &conn_it
: cell
->connections()) {
444 if (ct
.cell_output(cell
->type
, conn_it
.first
) || !ct
.cell_known(cell
->type
)) {
445 RTLIL::SigSpec sig
= conn_it
.second
;
446 assign_map
.apply(sig
);
447 sig2driver
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
449 if (ct
.cell_input(cell
->type
, conn_it
.first
) && cell
->hasPort("\\Y") &&
450 cell
->getPort("\\Y").size() == 1 && (conn_it
.first
== "\\A" || conn_it
.first
== "\\B")) {
451 RTLIL::SigSpec sig
= conn_it
.second
;
452 assign_map
.apply(sig
);
453 sig2trigger
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
456 if (cell
->type
== "$pmux") {
457 RTLIL::SigSpec sel_sig
= assign_map(cell
->getPort("\\S"));
458 for (auto &bit1
: sel_sig
)
459 for (auto &bit2
: sel_sig
)
461 exclusive_ctrls
[bit1
].insert(bit2
);
465 std::vector
<RTLIL::Wire
*> wire_list
;
466 for (auto &wire_it
: module
->wires_
)
467 if (wire_it
.second
->attributes
.count("\\fsm_encoding") > 0 && wire_it
.second
->attributes
["\\fsm_encoding"].decode_string() != "none")
468 if (design
->selected(module
, wire_it
.second
))
469 wire_list
.push_back(wire_it
.second
);
470 for (auto wire
: wire_list
)
480 PRIVATE_NAMESPACE_END