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 if (sig_aa
.is_fully_def())
96 *reset_state
= sig_aa
.as_const();
97 else if (sig_bb
.is_fully_def())
98 *reset_state
= sig_bb
.as_const();
101 log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state
));
104 for (auto sig_s_bit
: sig_s
) {
105 if (ctrl
.extract(sig_s_bit
).empty()) {
106 log(" found ctrl input: %s\n", log_signal(sig_s_bit
));
107 ctrl
.append(sig_s_bit
);
111 if (!find_states(sig_aa
, dff_out
, ctrl
, states
))
114 for (int i
= 0; i
< GetSize(sig_bb
)/GetSize(sig_aa
); i
++) {
115 if (!find_states(sig_bb
.extract(i
*GetSize(sig_aa
), GetSize(sig_aa
)), dff_out
, ctrl
, states
))
123 static RTLIL::Const
sig2const(ConstEval
&ce
, RTLIL::SigSpec sig
, RTLIL::State noconst_state
, RTLIL::SigSpec dont_care
= RTLIL::SigSpec())
125 if (dont_care
.size() > 0) {
126 for (int i
= 0; i
< GetSize(sig
); i
++)
127 if (dont_care
.extract(sig
[i
]).size() > 0)
128 sig
[i
] = noconst_state
;
131 ce
.assign_map
.apply(sig
);
132 ce
.values_map
.apply(sig
);
134 for (int i
= 0; i
< GetSize(sig
); i
++)
135 if (sig
[i
].wire
!= NULL
)
136 sig
[i
] = noconst_state
;
138 return sig
.as_const();
141 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
)
143 bool undef_bit_in_next_state_mode
= false;
144 RTLIL::SigSpec undef
, constval
;
146 if (ce
.eval(ctrl_out
, undef
) && ce
.eval(dff_in
, undef
))
149 undef_bit_in_next_state
:
150 for (auto &bit
: dff_in
)
151 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
152 for (auto &bit
: ctrl_out
)
153 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
154 undef_bit_in_next_state_mode
= true;
157 log_assert(ctrl_out
.is_fully_const() && dff_in
.is_fully_const());
159 FsmData::transition_t tr
;
160 tr
.ctrl_in
= sig2const(ce
, ctrl_in
, RTLIL::State::Sa
, dont_care
);
161 tr
.ctrl_out
= sig2const(ce
, ctrl_out
, RTLIL::State::Sx
);
163 std::map
<RTLIL::SigBit
, int> ctrl_in_bit_indices
;
164 for (int i
= 0; i
< GetSize(ctrl_in
); i
++)
165 ctrl_in_bit_indices
[ctrl_in
[i
]] = i
;
167 for (auto &it
: ctrl_in_bit_indices
)
168 if (tr
.ctrl_in
.bits
.at(it
.second
) == RTLIL::S1
&& exclusive_ctrls
.count(it
.first
) != 0)
169 for (auto &dc_bit
: exclusive_ctrls
.at(it
.first
))
170 if (ctrl_in_bit_indices
.count(dc_bit
))
171 tr
.ctrl_in
.bits
.at(ctrl_in_bit_indices
.at(dc_bit
)) = RTLIL::State::Sa
;
173 RTLIL::Const log_state_in
= RTLIL::Const(RTLIL::State::Sx
, fsm_data
.state_bits
);
175 log_state_in
= fsm_data
.state_table
.at(state_in
);
177 if (states
.count(ce
.values_map(ce
.assign_map(dff_in
)).as_const()) == 0) {
178 log(" transition: %10s %s -> INVALID_STATE(%s) %s <ignored invalid transistion!>%s\n",
179 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
180 log_signal(ce
.values_map(ce
.assign_map(dff_in
))), log_signal(tr
.ctrl_out
),
181 undef_bit_in_next_state_mode
? " SHORTENED" : "");
185 tr
.state_in
= state_in
;
186 tr
.state_out
= states
.at(ce
.values_map(ce
.assign_map(dff_in
)).as_const());
188 if (dff_in
.is_fully_def()) {
189 fsm_data
.transition_table
.push_back(tr
);
190 log(" transition: %10s %s -> %10s %s\n",
191 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
192 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
194 log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n",
195 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
196 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
201 for (auto &bit
: dff_in
)
202 if (bit
== RTLIL::Sx
)
203 goto undef_bit_in_next_state
;
205 log_assert(undef
.size() > 0);
206 log_assert(ce
.stop_signals
.check_all(undef
));
208 undef
= undef
.extract(0, 1);
211 if (ce_nostop
.eval(constval
))
214 dont_care
.append(undef
);
215 ce
.set(undef
, constval
.as_const());
216 if (exclusive_ctrls
.count(undef
) && constval
== RTLIL::S1
)
217 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
218 RTLIL::SigSpec bitval
= bit
;
219 if (ce
.eval(bitval
) && bitval
!= RTLIL::S0
)
220 goto found_contradiction_1
;
222 ce
.set(bit
, RTLIL::S0
);
224 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
225 found_contradiction_1
:
230 ce
.push(), ce_nostop
.push();
231 ce
.set(undef
, RTLIL::S0
);
232 ce_nostop
.set(undef
, RTLIL::S0
);
233 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
234 ce
.pop(), ce_nostop
.pop();
236 ce
.push(), ce_nostop
.push();
237 ce
.set(undef
, RTLIL::S1
);
238 ce_nostop
.set(undef
, RTLIL::S1
);
239 if (exclusive_ctrls
.count(undef
))
240 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
241 RTLIL::SigSpec bitval
= bit
;
242 if ((ce
.eval(bitval
) || ce_nostop
.eval(bitval
)) && bitval
!= RTLIL::S0
)
243 goto found_contradiction_2
;
245 ce
.set(bit
, RTLIL::S0
), ce_nostop
.set(bit
, RTLIL::S0
);
247 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
248 found_contradiction_2
:
249 ce
.pop(), ce_nostop
.pop();
253 static void extract_fsm(RTLIL::Wire
*wire
)
255 log("Extracting FSM `%s' from module `%s'.\n", wire
->name
.c_str(), module
->name
.c_str());
257 // get input and output signals for state ff
259 RTLIL::SigSpec dff_out
= assign_map(RTLIL::SigSpec(wire
));
260 RTLIL::SigSpec
dff_in(RTLIL::State::Sm
, wire
->width
);
261 RTLIL::Const
reset_state(RTLIL::State::Sx
, wire
->width
);
263 RTLIL::SigSpec clk
= RTLIL::S0
;
264 RTLIL::SigSpec arst
= RTLIL::S0
;
265 bool clk_polarity
= true;
266 bool arst_polarity
= true;
268 std::set
<sig2driver_entry_t
> cellport_list
;
269 sig2driver
.find(dff_out
, cellport_list
);
270 for (auto &cellport
: cellport_list
) {
271 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
272 if ((cell
->type
!= "$dff" && cell
->type
!= "$adff") || cellport
.second
!= "\\Q")
274 log(" found %s cell for state register: %s\n", cell
->type
.c_str(), cell
->name
.c_str());
275 RTLIL::SigSpec sig_q
= assign_map(cell
->getPort("\\Q"));
276 RTLIL::SigSpec sig_d
= assign_map(cell
->getPort("\\D"));
277 clk
= cell
->getPort("\\CLK");
278 clk_polarity
= cell
->parameters
["\\CLK_POLARITY"].as_bool();
279 if (cell
->type
== "$adff") {
280 arst
= cell
->getPort("\\ARST");
281 arst_polarity
= cell
->parameters
["\\ARST_POLARITY"].as_bool();
282 reset_state
= cell
->parameters
["\\ARST_VALUE"];
284 sig_q
.replace(dff_out
, sig_d
, &dff_in
);
288 log(" root of input selection tree: %s\n", log_signal(dff_in
));
289 if (dff_in
.has_marked_bits()) {
290 log(" fsm extraction failed: incomplete input selection tree root.\n");
294 // find states and control inputs
296 RTLIL::SigSpec ctrl_in
;
297 std::map
<RTLIL::Const
, int> states
;
298 if (!arst
.is_fully_const()) {
299 log(" found reset state: %s (from async reset)\n", log_signal(reset_state
));
300 states
[reset_state
] = -1;
302 if (!find_states(dff_in
, dff_out
, ctrl_in
, states
, &reset_state
)) {
303 log(" fsm extraction failed: state selection tree is not closed.\n");
306 if (GetSize(states
) <= 1) {
307 log(" fsm extraction failed: at least two states are required.\n");
311 // find control outputs
312 // (add the state signals to the list of control outputs. if everything goes right, this signals
313 // become unused and can then be removed from the fsm control output)
315 RTLIL::SigSpec ctrl_out
= dff_in
;
316 cellport_list
.clear();
317 sig2trigger
.find(dff_out
, cellport_list
);
318 for (auto &cellport
: cellport_list
) {
319 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
320 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
321 RTLIL::SigSpec sig_b
;
322 if (cell
->hasPort("\\B"))
323 sig_b
= assign_map(cell
->getPort("\\B"));
324 RTLIL::SigSpec sig_y
= assign_map(cell
->getPort("\\Y"));
325 if (cellport
.second
== "\\A" && !sig_b
.is_fully_const())
327 if (cellport
.second
== "\\B" && !sig_a
.is_fully_const())
329 log(" found ctrl output: %s\n", log_signal(sig_y
));
330 ctrl_out
.append(sig_y
);
332 ctrl_in
.remove(ctrl_out
);
334 ctrl_in
.sort_and_unify();
335 ctrl_out
.sort_and_unify();
337 log(" ctrl inputs: %s\n", log_signal(ctrl_in
));
338 log(" ctrl outputs: %s\n", log_signal(ctrl_out
));
340 // Initialize fsm data struct
343 fsm_data
.num_inputs
= ctrl_in
.size();
344 fsm_data
.num_outputs
= ctrl_out
.size();
345 fsm_data
.state_bits
= wire
->width
;
346 fsm_data
.reset_state
= -1;
347 for (auto &it
: states
) {
348 it
.second
= fsm_data
.state_table
.size();
349 fsm_data
.state_table
.push_back(it
.first
);
351 if (!arst
.is_fully_const() || RTLIL::SigSpec(reset_state
).is_fully_def())
352 fsm_data
.reset_state
= states
[reset_state
];
354 // Create transition table
356 ConstEval
ce(module
), ce_nostop(module
);
358 for (int state_idx
= 0; state_idx
< int(fsm_data
.state_table
.size()); state_idx
++) {
359 ce
.push(), ce_nostop
.push();
360 ce
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
361 ce_nostop
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
362 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_idx
, ctrl_in
, ctrl_out
, dff_in
, RTLIL::SigSpec());
363 ce
.pop(), ce_nostop
.pop();
368 RTLIL::Cell
*fsm_cell
= module
->addCell(stringf("$fsm$%s$%d", wire
->name
.c_str(), autoidx
++), "$fsm");
369 fsm_cell
->setPort("\\CLK", clk
);
370 fsm_cell
->setPort("\\ARST", arst
);
371 fsm_cell
->parameters
["\\CLK_POLARITY"] = clk_polarity
? RTLIL::S1
: RTLIL::S0
;
372 fsm_cell
->parameters
["\\ARST_POLARITY"] = arst_polarity
? RTLIL::S1
: RTLIL::S0
;
373 fsm_cell
->setPort("\\CTRL_IN", ctrl_in
);
374 fsm_cell
->setPort("\\CTRL_OUT", ctrl_out
);
375 fsm_cell
->parameters
["\\NAME"] = RTLIL::Const(wire
->name
.str());
376 fsm_cell
->attributes
= wire
->attributes
;
377 fsm_data
.copy_to_cell(fsm_cell
);
379 // rename original state wire
381 module
->wires_
.erase(wire
->name
);
382 wire
->attributes
.erase("\\fsm_encoding");
383 wire
->name
= stringf("$fsm$oldstate%s", wire
->name
.c_str());
384 module
->wires_
[wire
->name
] = wire
;
386 // unconnect control outputs from old drivers
388 cellport_list
.clear();
389 sig2driver
.find(ctrl_out
, cellport_list
);
390 for (auto &cellport
: cellport_list
) {
391 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
392 RTLIL::SigSpec port_sig
= assign_map(cell
->getPort(cellport
.second
));
393 RTLIL::SigSpec unconn_sig
= port_sig
.extract(ctrl_out
);
394 RTLIL::Wire
*unconn_wire
= module
->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig
), autoidx
++), unconn_sig
.size());
395 port_sig
.replace(unconn_sig
, RTLIL::SigSpec(unconn_wire
), &cell
->connections_
[cellport
.second
]);
399 struct FsmExtractPass
: public Pass
{
400 FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
403 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
405 log(" fsm_extract [selection]\n");
407 log("This pass operates on all signals marked as FSM state signals using the\n");
408 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
409 log("and uses the state signal to generate control signal and replaces it with an\n");
412 log("The generated FSM cell still generates the original state signal with its\n");
413 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
414 log("'opt_clean' pass to eliminate this signal.\n");
417 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
419 log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
420 extra_args(args
, 1, design
);
423 ct
.setup_internals();
424 ct
.setup_internals_mem();
426 ct
.setup_stdcells_mem();
428 for (auto &mod_it
: design
->modules_
)
430 if (!design
->selected(mod_it
.second
))
433 module
= mod_it
.second
;
434 assign_map
.set(module
);
438 exclusive_ctrls
.clear();
439 for (auto cell
: module
->cells()) {
440 for (auto &conn_it
: cell
->connections()) {
441 if (ct
.cell_output(cell
->type
, conn_it
.first
) || !ct
.cell_known(cell
->type
)) {
442 RTLIL::SigSpec sig
= conn_it
.second
;
443 assign_map
.apply(sig
);
444 sig2driver
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
446 if (ct
.cell_input(cell
->type
, conn_it
.first
) && cell
->hasPort("\\Y") &&
447 cell
->getPort("\\Y").size() == 1 && (conn_it
.first
== "\\A" || conn_it
.first
== "\\B")) {
448 RTLIL::SigSpec sig
= conn_it
.second
;
449 assign_map
.apply(sig
);
450 sig2trigger
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
453 if (cell
->type
== "$pmux") {
454 RTLIL::SigSpec sel_sig
= assign_map(cell
->getPort("\\S"));
455 for (auto &bit1
: sel_sig
)
456 for (auto &bit2
: sel_sig
)
458 exclusive_ctrls
[bit1
].insert(bit2
);
462 std::vector
<RTLIL::Wire
*> wire_list
;
463 for (auto &wire_it
: module
->wires_
)
464 if (wire_it
.second
->attributes
.count("\\fsm_encoding") > 0 && wire_it
.second
->attributes
["\\fsm_encoding"].decode_string() != "none")
465 if (design
->selected(module
, wire_it
.second
))
466 wire_list
.push_back(wire_it
.second
);
467 for (auto wire
: wire_list
)
477 PRIVATE_NAMESPACE_END