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(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
);
59 for (auto &cellport
: cellport_list
)
61 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
62 if ((cell
->type
!= "$mux" && cell
->type
!= "$pmux") || cellport
.second
!= "\\Y") {
63 log(" unexpected cell type %s (%s) found in state selection tree.\n", cell
->type
.c_str(), cell
->name
.c_str());
67 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
68 RTLIL::SigSpec sig_b
= assign_map(cell
->getPort("\\B"));
69 RTLIL::SigSpec sig_s
= assign_map(cell
->getPort("\\S"));
70 RTLIL::SigSpec sig_y
= assign_map(cell
->getPort("\\Y"));
72 RTLIL::SigSpec sig_aa
= sig
;
73 sig_aa
.replace(sig_y
, sig_a
);
75 RTLIL::SigSpec sig_bb
;
76 for (int i
= 0; i
< GetSize(sig_b
)/GetSize(sig_a
); i
++) {
77 RTLIL::SigSpec s
= sig
;
78 s
.replace(sig_y
, sig_b
.extract(i
*GetSize(sig_a
), GetSize(sig_a
)));
82 if (reset_state
&& RTLIL::SigSpec(*reset_state
).is_fully_undef())
84 if (sig_aa
.is_fully_def())
85 *reset_state
= sig_aa
.as_const();
86 else if (sig_bb
.is_fully_def())
87 *reset_state
= sig_bb
.as_const();
90 log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state
));
93 if (ctrl
.extract(sig_s
).size() == 0) {
94 log(" found ctrl input: %s\n", log_signal(sig_s
));
98 if (!find_states(sig_aa
, dff_out
, ctrl
, states
))
101 for (int i
= 0; i
< GetSize(sig_bb
)/GetSize(sig_aa
); i
++) {
102 if (!find_states(sig_bb
.extract(i
*GetSize(sig_aa
), GetSize(sig_aa
)), dff_out
, ctrl
, states
))
110 static RTLIL::Const
sig2const(ConstEval
&ce
, RTLIL::SigSpec sig
, RTLIL::State noconst_state
, RTLIL::SigSpec dont_care
= RTLIL::SigSpec())
112 if (dont_care
.size() > 0) {
113 for (int i
= 0; i
< GetSize(sig
); i
++)
114 if (dont_care
.extract(sig
[i
]).size() > 0)
115 sig
[i
] = noconst_state
;
118 ce
.assign_map
.apply(sig
);
119 ce
.values_map
.apply(sig
);
121 for (int i
= 0; i
< GetSize(sig
); i
++)
122 if (sig
[i
].wire
!= NULL
)
123 sig
[i
] = noconst_state
;
125 return sig
.as_const();
128 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
)
130 bool undef_bit_in_next_state_mode
= false;
131 RTLIL::SigSpec undef
, constval
;
133 if (ce
.eval(ctrl_out
, undef
) && ce
.eval(dff_in
, undef
))
136 undef_bit_in_next_state
:
137 for (auto &bit
: dff_in
)
138 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
139 for (auto &bit
: ctrl_out
)
140 if (bit
.wire
!= nullptr) bit
= RTLIL::Sm
;
141 undef_bit_in_next_state_mode
= true;
144 log_assert(ctrl_out
.is_fully_const() && dff_in
.is_fully_const());
146 FsmData::transition_t tr
;
147 tr
.ctrl_in
= sig2const(ce
, ctrl_in
, RTLIL::State::Sa
, dont_care
);
148 tr
.ctrl_out
= sig2const(ce
, ctrl_out
, RTLIL::State::Sx
);
150 std::map
<RTLIL::SigBit
, int> ctrl_in_bit_indices
;
151 for (int i
= 0; i
< GetSize(ctrl_in
); i
++)
152 ctrl_in_bit_indices
[ctrl_in
[i
]] = i
;
154 for (auto &it
: ctrl_in_bit_indices
)
155 if (tr
.ctrl_in
.bits
.at(it
.second
) == RTLIL::S1
&& exclusive_ctrls
.count(it
.first
) != 0)
156 for (auto &dc_bit
: exclusive_ctrls
.at(it
.first
))
157 if (ctrl_in_bit_indices
.count(dc_bit
))
158 tr
.ctrl_in
.bits
.at(ctrl_in_bit_indices
.at(dc_bit
)) = RTLIL::State::Sa
;
160 RTLIL::Const log_state_in
= RTLIL::Const(RTLIL::State::Sx
, fsm_data
.state_bits
);
162 log_state_in
= fsm_data
.state_table
.at(state_in
);
164 if (states
.count(ce
.values_map(ce
.assign_map(dff_in
)).as_const()) == 0) {
165 log(" transition: %10s %s -> INVALID_STATE(%s) %s <ignored invalid transistion!>%s\n",
166 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
167 log_signal(ce
.values_map(ce
.assign_map(dff_in
))), log_signal(tr
.ctrl_out
),
168 undef_bit_in_next_state_mode
? " SHORTENED" : "");
172 tr
.state_in
= state_in
;
173 tr
.state_out
= states
.at(ce
.values_map(ce
.assign_map(dff_in
)).as_const());
175 if (dff_in
.is_fully_def()) {
176 fsm_data
.transition_table
.push_back(tr
);
177 log(" transition: %10s %s -> %10s %s\n",
178 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
179 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
181 log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n",
182 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
183 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
188 for (auto &bit
: dff_in
)
189 if (bit
== RTLIL::Sx
)
190 goto undef_bit_in_next_state
;
192 log_assert(undef
.size() > 0);
193 log_assert(ce
.stop_signals
.check_all(undef
));
195 undef
= undef
.extract(0, 1);
198 if (ce_nostop
.eval(constval
))
201 dont_care
.append(undef
);
202 ce
.set(undef
, constval
.as_const());
203 if (exclusive_ctrls
.count(undef
) && constval
== RTLIL::S1
)
204 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
205 RTLIL::SigSpec bitval
= bit
;
206 if (ce
.eval(bitval
) && bitval
!= RTLIL::S0
)
207 goto found_contradiction_1
;
209 ce
.set(bit
, RTLIL::S0
);
211 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
212 found_contradiction_1
:
217 ce
.push(), ce_nostop
.push();
218 ce
.set(undef
, RTLIL::S0
);
219 ce_nostop
.set(undef
, RTLIL::S0
);
220 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
221 ce
.pop(), ce_nostop
.pop();
223 ce
.push(), ce_nostop
.push();
224 ce
.set(undef
, RTLIL::S1
);
225 ce_nostop
.set(undef
, RTLIL::S1
);
226 if (exclusive_ctrls
.count(undef
))
227 for (auto &bit
: exclusive_ctrls
.at(undef
)) {
228 RTLIL::SigSpec bitval
= bit
;
229 if ((ce
.eval(bitval
) || ce_nostop
.eval(bitval
)) && bitval
!= RTLIL::S0
)
230 goto found_contradiction_2
;
232 ce
.set(bit
, RTLIL::S0
), ce_nostop
.set(bit
, RTLIL::S0
);
234 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
235 found_contradiction_2
:
236 ce
.pop(), ce_nostop
.pop();
240 static void extract_fsm(RTLIL::Wire
*wire
)
242 log("Extracting FSM `%s' from module `%s'.\n", wire
->name
.c_str(), module
->name
.c_str());
244 // get input and output signals for state ff
246 RTLIL::SigSpec dff_out
= assign_map(RTLIL::SigSpec(wire
));
247 RTLIL::SigSpec
dff_in(RTLIL::State::Sm
, wire
->width
);
248 RTLIL::Const
reset_state(RTLIL::State::Sx
, wire
->width
);
250 RTLIL::SigSpec clk
= RTLIL::S0
;
251 RTLIL::SigSpec arst
= RTLIL::S0
;
252 bool clk_polarity
= true;
253 bool arst_polarity
= true;
255 std::set
<sig2driver_entry_t
> cellport_list
;
256 sig2driver
.find(dff_out
, cellport_list
);
257 for (auto &cellport
: cellport_list
) {
258 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
259 if ((cell
->type
!= "$dff" && cell
->type
!= "$adff") || cellport
.second
!= "\\Q")
261 log(" found %s cell for state register: %s\n", cell
->type
.c_str(), cell
->name
.c_str());
262 RTLIL::SigSpec sig_q
= assign_map(cell
->getPort("\\Q"));
263 RTLIL::SigSpec sig_d
= assign_map(cell
->getPort("\\D"));
264 clk
= cell
->getPort("\\CLK");
265 clk_polarity
= cell
->parameters
["\\CLK_POLARITY"].as_bool();
266 if (cell
->type
== "$adff") {
267 arst
= cell
->getPort("\\ARST");
268 arst_polarity
= cell
->parameters
["\\ARST_POLARITY"].as_bool();
269 reset_state
= cell
->parameters
["\\ARST_VALUE"];
271 sig_q
.replace(dff_out
, sig_d
, &dff_in
);
275 log(" root of input selection tree: %s\n", log_signal(dff_in
));
276 if (dff_in
.has_marked_bits()) {
277 log(" fsm extraction failed: incomplete input selection tree root.\n");
281 // find states and control inputs
283 RTLIL::SigSpec ctrl_in
;
284 std::map
<RTLIL::Const
, int> states
;
285 if (!arst
.is_fully_const()) {
286 log(" found reset state: %s (from async reset)\n", log_signal(reset_state
));
287 states
[reset_state
] = -1;
289 if (!find_states(dff_in
, dff_out
, ctrl_in
, states
, &reset_state
)) {
290 log(" fsm extraction failed: state selection tree is not closed.\n");
293 if (GetSize(states
) <= 1) {
294 log(" fsm extraction failed: at least two states are required.\n");
298 // find control outputs
299 // (add the state signals to the list of control outputs. if everything goes right, this signals
300 // become unused and can then be removed from the fsm control output)
302 RTLIL::SigSpec ctrl_out
= dff_in
;
303 cellport_list
.clear();
304 sig2trigger
.find(dff_out
, cellport_list
);
305 for (auto &cellport
: cellport_list
) {
306 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
307 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
308 RTLIL::SigSpec sig_b
= assign_map(cell
->getPort("\\B"));
309 RTLIL::SigSpec sig_y
= assign_map(cell
->getPort("\\Y"));
310 if (cellport
.second
== "\\A" && !sig_b
.is_fully_const())
312 if (cellport
.second
== "\\B" && !sig_a
.is_fully_const())
314 log(" found ctrl output: %s\n", log_signal(sig_y
));
315 ctrl_out
.append(sig_y
);
317 ctrl_in
.remove(ctrl_out
);
319 ctrl_in
.sort_and_unify();
320 ctrl_out
.sort_and_unify();
322 log(" ctrl inputs: %s\n", log_signal(ctrl_in
));
323 log(" ctrl outputs: %s\n", log_signal(ctrl_out
));
325 // Initialize fsm data struct
328 fsm_data
.num_inputs
= ctrl_in
.size();
329 fsm_data
.num_outputs
= ctrl_out
.size();
330 fsm_data
.state_bits
= wire
->width
;
331 fsm_data
.reset_state
= -1;
332 for (auto &it
: states
) {
333 it
.second
= fsm_data
.state_table
.size();
334 fsm_data
.state_table
.push_back(it
.first
);
336 if (!arst
.is_fully_const() || RTLIL::SigSpec(reset_state
).is_fully_def())
337 fsm_data
.reset_state
= states
[reset_state
];
339 // Create transition table
341 ConstEval
ce(module
), ce_nostop(module
);
343 for (int state_idx
= 0; state_idx
< int(fsm_data
.state_table
.size()); state_idx
++) {
344 ce
.push(), ce_nostop
.push();
345 ce
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
346 ce_nostop
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
347 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_idx
, ctrl_in
, ctrl_out
, dff_in
, RTLIL::SigSpec());
348 ce
.pop(), ce_nostop
.pop();
353 RTLIL::Cell
*fsm_cell
= module
->addCell(stringf("$fsm$%s$%d", wire
->name
.c_str(), autoidx
++), "$fsm");
354 fsm_cell
->setPort("\\CLK", clk
);
355 fsm_cell
->setPort("\\ARST", arst
);
356 fsm_cell
->parameters
["\\CLK_POLARITY"] = clk_polarity
? RTLIL::S1
: RTLIL::S0
;
357 fsm_cell
->parameters
["\\ARST_POLARITY"] = arst_polarity
? RTLIL::S1
: RTLIL::S0
;
358 fsm_cell
->setPort("\\CTRL_IN", ctrl_in
);
359 fsm_cell
->setPort("\\CTRL_OUT", ctrl_out
);
360 fsm_cell
->parameters
["\\NAME"] = RTLIL::Const(wire
->name
.str());
361 fsm_cell
->attributes
= wire
->attributes
;
362 fsm_data
.copy_to_cell(fsm_cell
);
364 // rename original state wire
366 module
->wires_
.erase(wire
->name
);
367 wire
->attributes
.erase("\\fsm_encoding");
368 wire
->name
= stringf("$fsm$oldstate%s", wire
->name
.c_str());
369 module
->wires_
[wire
->name
] = wire
;
371 // unconnect control outputs from old drivers
373 cellport_list
.clear();
374 sig2driver
.find(ctrl_out
, cellport_list
);
375 for (auto &cellport
: cellport_list
) {
376 RTLIL::Cell
*cell
= module
->cells_
.at(cellport
.first
);
377 RTLIL::SigSpec port_sig
= assign_map(cell
->getPort(cellport
.second
));
378 RTLIL::SigSpec unconn_sig
= port_sig
.extract(ctrl_out
);
379 RTLIL::Wire
*unconn_wire
= module
->addWire(stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig
), autoidx
++), unconn_sig
.size());
380 port_sig
.replace(unconn_sig
, RTLIL::SigSpec(unconn_wire
), &cell
->connections_
[cellport
.second
]);
384 struct FsmExtractPass
: public Pass
{
385 FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
388 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
390 log(" fsm_extract [selection]\n");
392 log("This pass operates on all signals marked as FSM state signals using the\n");
393 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
394 log("and uses the state signal to generate control signal and replaces it with an\n");
397 log("The generated FSM cell still generates the original state signal with its\n");
398 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
399 log("'opt_clean' pass to eliminate this signal.\n");
402 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
404 log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
405 extra_args(args
, 1, design
);
408 ct
.setup_internals();
409 ct
.setup_internals_mem();
411 ct
.setup_stdcells_mem();
413 for (auto &mod_it
: design
->modules_
)
415 if (!design
->selected(mod_it
.second
))
418 module
= mod_it
.second
;
419 assign_map
.set(module
);
423 exclusive_ctrls
.clear();
424 for (auto cell
: module
->cells()) {
425 for (auto &conn_it
: cell
->connections()) {
426 if (ct
.cell_output(cell
->type
, conn_it
.first
) || !ct
.cell_known(cell
->type
)) {
427 RTLIL::SigSpec sig
= conn_it
.second
;
428 assign_map
.apply(sig
);
429 sig2driver
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
431 if (ct
.cell_input(cell
->type
, conn_it
.first
) && cell
->hasPort("\\Y") &&
432 cell
->getPort("\\Y").size() == 1 && (conn_it
.first
== "\\A" || conn_it
.first
== "\\B")) {
433 RTLIL::SigSpec sig
= conn_it
.second
;
434 assign_map
.apply(sig
);
435 sig2trigger
.insert(sig
, sig2driver_entry_t(cell
->name
, conn_it
.first
));
438 if (cell
->type
== "$pmux") {
439 RTLIL::SigSpec sel_sig
= assign_map(cell
->getPort("\\S"));
440 for (auto &bit1
: sel_sig
)
441 for (auto &bit2
: sel_sig
)
443 exclusive_ctrls
[bit1
].insert(bit2
);
447 std::vector
<RTLIL::Wire
*> wire_list
;
448 for (auto &wire_it
: module
->wires_
)
449 if (wire_it
.second
->attributes
.count("\\fsm_encoding") > 0 && wire_it
.second
->attributes
["\\fsm_encoding"].decode_string() != "none")
450 if (design
->selected(module
, wire_it
.second
))
451 wire_list
.push_back(wire_it
.second
);
452 for (auto wire
: wire_list
)
462 PRIVATE_NAMESPACE_END