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"
32 static RTLIL::Module
*module
;
33 static SigMap assign_map
;
34 typedef std::pair
<RTLIL::Cell
*,std::string
> sig2driver_entry_t
;
35 static SigSet
<sig2driver_entry_t
> sig2driver
, sig2trigger
;
37 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
)
39 sig
.extend(dff_out
.width
, false);
44 assign_map
.apply(sig
);
45 if (sig
.is_fully_const()) {
47 assert(sig
.chunks
.size() == 1);
48 if (states
.count(sig
.chunks
[0].data
) == 0) {
49 log(" found state code: %s\n", log_signal(sig
));
50 states
[sig
.chunks
[0].data
] = -1;
55 std::set
<sig2driver_entry_t
> cellport_list
;
56 sig2driver
.find(sig
, cellport_list
);
57 for (auto &cellport
: cellport_list
) {
58 if ((cellport
.first
->type
!= "$mux" && cellport
.first
->type
!= "$pmux" && cellport
.first
->type
!= "$safe_pmux") || cellport
.second
!= "\\Y") {
59 log(" unexpected cell type %s (%s) found in state selection tree.\n",
60 cellport
.first
->type
.c_str(), cellport
.first
->name
.c_str());
63 RTLIL::SigSpec sig_a
= assign_map(cellport
.first
->connections
["\\A"]);
64 RTLIL::SigSpec sig_b
= assign_map(cellport
.first
->connections
["\\B"]);
65 RTLIL::SigSpec sig_s
= assign_map(cellport
.first
->connections
["\\S"]);
66 if (reset_state
&& RTLIL::SigSpec(*reset_state
).is_fully_undef())
68 if (sig_a
.is_fully_def())
69 *reset_state
= sig_a
.as_const();
70 else if (sig_b
.is_fully_def())
71 *reset_state
= sig_b
.as_const();
74 log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state
));
76 if (ctrl
.extract(sig_s
).width
== 0) {
77 log(" found ctrl input: %s\n", log_signal(sig_s
));
80 if (!find_states(sig_a
, dff_out
, ctrl
, states
))
82 for (int i
= 0; i
< sig_b
.width
/sig_a
.width
; i
++) {
83 if (!find_states(sig_b
.extract(i
*sig_a
.width
, sig_a
.width
), dff_out
, ctrl
, states
))
91 static RTLIL::Const
sig2const(ConstEval
&ce
, RTLIL::SigSpec sig
, RTLIL::State noconst_state
, RTLIL::SigSpec dont_care
= RTLIL::SigSpec())
93 if (dont_care
.width
> 0) {
95 for (auto &chunk
: sig
.chunks
) {
96 assert(chunk
.width
== 1);
97 if (dont_care
.extract(chunk
).width
> 0)
98 chunk
.wire
= NULL
, chunk
.data
= RTLIL::Const(noconst_state
);
103 ce
.assign_map
.apply(sig
);
104 ce
.values_map
.apply(sig
);
107 for (auto &chunk
: sig
.chunks
) {
108 assert(chunk
.width
== 1);
109 if (chunk
.wire
!= NULL
)
110 chunk
.wire
= NULL
, chunk
.data
= RTLIL::Const(noconst_state
);
115 return RTLIL::Const();
116 assert(sig
.chunks
.size() == 1 && sig
.chunks
[0].wire
== NULL
);
117 return sig
.chunks
[0].data
;
120 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
)
122 RTLIL::SigSpec undef
, constval
;
124 if (ce
.eval(ctrl_out
, undef
) && ce
.eval(dff_in
, undef
)) {
125 assert(ctrl_out
.is_fully_const() && dff_in
.is_fully_const());
126 FsmData::transition_t tr
;
127 tr
.state_in
= state_in
;
128 tr
.state_out
= states
[ce
.values_map(ce
.assign_map(dff_in
)).as_const()];
129 tr
.ctrl_in
= sig2const(ce
, ctrl_in
, RTLIL::State::Sa
, dont_care
);
130 tr
.ctrl_out
= sig2const(ce
, ctrl_out
, RTLIL::State::Sx
);
131 RTLIL::Const log_state_in
= RTLIL::Const(RTLIL::State::Sx
, fsm_data
.state_bits
);
133 log_state_in
= fsm_data
.state_table
[tr
.state_in
];
134 if (dff_in
.is_fully_def()) {
135 fsm_data
.transition_table
.push_back(tr
);
136 log(" transition: %10s %s -> %10s %s\n",
137 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
138 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
140 log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n",
141 log_signal(log_state_in
), log_signal(tr
.ctrl_in
),
142 log_signal(fsm_data
.state_table
[tr
.state_out
]), log_signal(tr
.ctrl_out
));
147 assert(undef
.width
> 0);
148 assert(ce
.stop_signals
.check_all(undef
));
150 undef
= undef
.extract(0, 1);
153 if (ce_nostop
.eval(constval
))
156 dont_care
.append(undef
);
157 ce
.set(undef
, constval
.as_const());
158 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
163 ce
.push(), ce_nostop
.push();
164 ce
.set(undef
, RTLIL::Const(0, 1));
165 ce_nostop
.set(undef
, RTLIL::Const(0, 1));
166 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
167 ce
.pop(), ce_nostop
.pop();
169 ce
.push(), ce_nostop
.push();
170 ce
.set(undef
, RTLIL::Const(1, 1));
171 ce_nostop
.set(undef
, RTLIL::Const(1, 1));
172 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_in
, ctrl_in
, ctrl_out
, dff_in
, dont_care
);
173 ce
.pop(), ce_nostop
.pop();
177 static void extract_fsm(RTLIL::Wire
*wire
)
179 log("Extracting FSM `%s' from module `%s'.\n", wire
->name
.c_str(), module
->name
.c_str());
181 // get input and output signals for state ff
183 RTLIL::SigSpec dff_out
= assign_map(RTLIL::SigSpec(wire
));
184 RTLIL::SigSpec
dff_in(RTLIL::State::Sm
, wire
->width
);
185 RTLIL::Const
reset_state(RTLIL::State::Sx
, wire
->width
);
187 RTLIL::SigSpec clk
= RTLIL::SigSpec(0, 1);
188 RTLIL::SigSpec arst
= RTLIL::SigSpec(0, 1);
189 bool clk_polarity
= true;
190 bool arst_polarity
= true;
192 std::set
<sig2driver_entry_t
> cellport_list
;
193 sig2driver
.find(dff_out
, cellport_list
);
194 for (auto &cellport
: cellport_list
) {
195 if ((cellport
.first
->type
!= "$dff" && cellport
.first
->type
!= "$adff") || cellport
.second
!= "\\Q")
197 log(" found %s cell for state register: %s\n", cellport
.first
->type
.c_str(), cellport
.first
->name
.c_str());
198 RTLIL::SigSpec sig_q
= assign_map(cellport
.first
->connections
["\\Q"]);
199 RTLIL::SigSpec sig_d
= assign_map(cellport
.first
->connections
["\\D"]);
200 clk
= cellport
.first
->connections
["\\CLK"];
201 clk_polarity
= cellport
.first
->parameters
["\\CLK_POLARITY"].as_bool();
202 if (cellport
.first
->type
== "$adff") {
203 arst
= cellport
.first
->connections
["\\ARST"];
204 arst_polarity
= cellport
.first
->parameters
["\\ARST_POLARITY"].as_bool();
205 reset_state
= cellport
.first
->parameters
["\\ARST_VALUE"];
207 sig_q
.replace(dff_out
, sig_d
, &dff_in
);
211 log(" root of input selection tree: %s\n", log_signal(dff_in
));
212 if (dff_in
.has_marked_bits()) {
213 log(" fsm extraction failed: incomplete input selection tree root.\n");
217 // find states and control inputs
219 RTLIL::SigSpec ctrl_in
;
220 std::map
<RTLIL::Const
, int> states
;
221 if (!arst
.is_fully_const()) {
222 log(" found reset state: %s (from async reset)\n", log_signal(reset_state
));
223 states
[reset_state
] = -1;
225 if (!find_states(dff_in
, dff_out
, ctrl_in
, states
, &reset_state
)) {
226 log(" fsm extraction failed: state selection tree is not closed.\n");
230 // find control outputs
231 // (add the state signals to the list of control outputs. if everything goes right, this signals
232 // become unused and can then be removed from the fsm control output)
234 RTLIL::SigSpec ctrl_out
= dff_in
;
235 cellport_list
.clear();
236 sig2trigger
.find(dff_out
, cellport_list
);
237 for (auto &cellport
: cellport_list
) {
238 RTLIL::SigSpec sig_a
= assign_map(cellport
.first
->connections
["\\A"]);
239 RTLIL::SigSpec sig_b
= assign_map(cellport
.first
->connections
["\\B"]);
240 RTLIL::SigSpec sig_y
= assign_map(cellport
.first
->connections
["\\Y"]);
241 if (cellport
.second
== "\\A" && !sig_b
.is_fully_const())
243 if (cellport
.second
== "\\B" && !sig_a
.is_fully_const())
245 log(" found ctrl output: %s\n", log_signal(sig_y
));
246 ctrl_out
.append(sig_y
);
248 ctrl_in
.remove(ctrl_out
);
250 ctrl_in
.sort_and_unify();
251 ctrl_out
.sort_and_unify();
253 log(" ctrl inputs: %s\n", log_signal(ctrl_in
));
254 log(" ctrl outputs: %s\n", log_signal(ctrl_out
));
256 // Initialize fsm data struct
259 fsm_data
.num_inputs
= ctrl_in
.width
;
260 fsm_data
.num_outputs
= ctrl_out
.width
;
261 fsm_data
.state_bits
= wire
->width
;
262 fsm_data
.reset_state
= -1;
263 for (auto &it
: states
) {
264 it
.second
= fsm_data
.state_table
.size();
265 fsm_data
.state_table
.push_back(it
.first
);
267 if (!arst
.is_fully_const() || RTLIL::SigSpec(reset_state
).is_fully_def())
268 fsm_data
.reset_state
= states
[reset_state
];
270 // Create transition table
272 ConstEval
ce(module
), ce_nostop(module
);
274 for (int state_idx
= 0; state_idx
< int(fsm_data
.state_table
.size()); state_idx
++) {
275 ce
.push(), ce_nostop
.push();
276 ce
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
277 ce_nostop
.set(dff_out
, fsm_data
.state_table
[state_idx
]);
278 find_transitions(ce
, ce_nostop
, fsm_data
, states
, state_idx
, ctrl_in
, ctrl_out
, dff_in
, RTLIL::SigSpec());
279 ce
.pop(), ce_nostop
.pop();
284 RTLIL::Cell
*fsm_cell
= new RTLIL::Cell
;
285 fsm_cell
->name
= stringf("$fsm$%s$%d", wire
->name
.c_str(), RTLIL::autoidx
++);
286 fsm_cell
->type
= "$fsm";
287 fsm_cell
->connections
["\\CLK"] = clk
;
288 fsm_cell
->connections
["\\ARST"] = arst
;
289 fsm_cell
->parameters
["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity
? 1 : 0, 1);
290 fsm_cell
->parameters
["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity
? 1 : 0, 1);
291 fsm_cell
->connections
["\\CTRL_IN"] = ctrl_in
;
292 fsm_cell
->connections
["\\CTRL_OUT"] = ctrl_out
;
293 fsm_cell
->parameters
["\\NAME"] = RTLIL::Const(wire
->name
);
294 fsm_cell
->attributes
= wire
->attributes
;
295 fsm_data
.copy_to_cell(fsm_cell
);
296 module
->cells
[fsm_cell
->name
] = fsm_cell
;
298 // rename original state wire
300 module
->wires
.erase(wire
->name
);
301 wire
->attributes
.erase("\\fsm_encoding");
302 wire
->name
= stringf("$fsm$oldstate%s", wire
->name
.c_str());
303 module
->wires
[wire
->name
] = wire
;
305 // unconnect control outputs from old drivers
307 cellport_list
.clear();
308 sig2driver
.find(ctrl_out
, cellport_list
);
309 for (auto &cellport
: cellport_list
) {
310 RTLIL::SigSpec port_sig
= assign_map(cellport
.first
->connections
[cellport
.second
]);
311 RTLIL::SigSpec unconn_sig
= port_sig
.extract(ctrl_out
);
312 RTLIL::Wire
*unconn_wire
= new RTLIL::Wire
;
313 unconn_wire
->name
= stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig
), RTLIL::autoidx
++);
314 unconn_wire
->width
= unconn_sig
.width
;
315 module
->wires
[unconn_wire
->name
] = unconn_wire
;
316 port_sig
.replace(unconn_sig
, RTLIL::SigSpec(unconn_wire
), &cellport
.first
->connections
[cellport
.second
]);
320 struct FsmExtractPass
: public Pass
{
321 FsmExtractPass() : Pass("fsm_extract", "extracting FSMs in design") { }
324 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
326 log(" fsm_extract [selection]\n");
328 log("This pass operates on all signals marked as FSM state signals using the\n");
329 log("'fsm_encoding' attribute. It consumes the logic that creates the state signal\n");
330 log("and uses the state signal to generate control signal and replaces it with an\n");
333 log("The generated FSM cell still generates the original state signal with its\n");
334 log("original encoding. The 'fsm_opt' pass can be used in combination with the\n");
335 log("'opt_clean' pass to eliminate this signal.\n");
338 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
340 log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
341 extra_args(args
, 1, design
);
344 ct
.setup_internals();
345 ct
.setup_internals_mem();
347 ct
.setup_stdcells_mem();
349 for (auto &mod_it
: design
->modules
)
351 if (!design
->selected(mod_it
.second
))
354 module
= mod_it
.second
;
355 assign_map
.set(module
);
359 for (auto &cell_it
: module
->cells
)
360 for (auto &conn_it
: cell_it
.second
->connections
) {
361 if (ct
.cell_output(cell_it
.second
->type
, conn_it
.first
)) {
362 RTLIL::SigSpec sig
= conn_it
.second
;
363 assign_map
.apply(sig
);
364 sig2driver
.insert(sig
, sig2driver_entry_t(cell_it
.second
, conn_it
.first
));
366 if (ct
.cell_input(cell_it
.second
->type
, conn_it
.first
) && cell_it
.second
->connections
.count("\\Y") > 0 &&
367 cell_it
.second
->connections
["\\Y"].width
== 1 && (conn_it
.first
== "\\A" || conn_it
.first
== "\\B")) {
368 RTLIL::SigSpec sig
= conn_it
.second
;
369 assign_map
.apply(sig
);
370 sig2trigger
.insert(sig
, sig2driver_entry_t(cell_it
.second
, conn_it
.first
));
374 std::vector
<RTLIL::Wire
*> wire_list
;
375 for (auto &wire_it
: module
->wires
)
376 if (wire_it
.second
->attributes
.count("\\fsm_encoding") > 0 && wire_it
.second
->attributes
["\\fsm_encoding"].str
!= "none")
377 if (design
->selected(module
, wire_it
.second
))
378 wire_list
.push_back(wire_it
.second
);
379 for (auto wire
: wire_list
)