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.
20 #include "kernel/log.h"
21 #include "kernel/register.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/consteval.h"
24 #include "kernel/celltypes.h"
29 PRIVATE_NAMESPACE_BEGIN
35 RTLIL::Module
*module
;
37 void opt_unreachable_states()
41 std::set
<int> unreachable_states
;
42 std::vector
<FsmData::transition_t
> new_transition_table
;
43 std::vector
<RTLIL::Const
> new_state_table
;
44 std::map
<int, int> old_to_new_state
;
46 for (int i
= 0; i
< GetSize(fsm_data
.state_table
); i
++)
47 if (i
!= fsm_data
.reset_state
)
48 unreachable_states
.insert(i
);
50 for (auto &trans
: fsm_data
.transition_table
)
51 unreachable_states
.erase(trans
.state_out
);
53 if (unreachable_states
.empty())
56 for (int i
= 0; i
< GetSize(fsm_data
.state_table
); i
++) {
57 if (unreachable_states
.count(i
)) {
58 log(" Removing unreachable state %s.\n", log_signal(fsm_data
.state_table
[i
]));
61 old_to_new_state
[i
] = GetSize(new_state_table
);
62 new_state_table
.push_back(fsm_data
.state_table
[i
]);
65 for (auto trans
: fsm_data
.transition_table
) {
66 if (unreachable_states
.count(trans
.state_in
))
68 trans
.state_in
= old_to_new_state
.at(trans
.state_in
);
69 trans
.state_out
= old_to_new_state
.at(trans
.state_out
);
70 new_transition_table
.push_back(trans
);
73 new_transition_table
.swap(fsm_data
.transition_table
);
74 new_state_table
.swap(fsm_data
.state_table
);
75 fsm_data
.reset_state
= old_to_new_state
.at(fsm_data
.reset_state
);
79 bool signal_is_unused(RTLIL::SigSpec sig
)
81 RTLIL::SigBit bit
= sig
.as_bit();
83 if (bit
.wire
== NULL
|| bit
.wire
->attributes
.count("\\unused_bits") == 0)
86 char *str
= strdup(bit
.wire
->attributes
["\\unused_bits"].decode_string().c_str());
87 for (char *tok
= strtok(str
, " "); tok
!= NULL
; tok
= strtok(NULL
, " ")) {
88 if (tok
[0] && bit
.offset
== atoi(tok
)) {
98 void opt_const_and_unused_inputs()
100 RTLIL::SigSpec ctrl_in
= cell
->getPort("\\CTRL_IN");
101 std::vector
<bool> ctrl_in_used(ctrl_in
.size());
103 std::vector
<FsmData::transition_t
> new_transition_table
;
104 for (auto &tr
: fsm_data
.transition_table
) {
105 for (int i
= 0; i
< ctrl_in
.size(); i
++) {
106 RTLIL::SigSpec ctrl_bit
= ctrl_in
.extract(i
, 1);
107 if (ctrl_bit
.is_fully_const()) {
108 if (tr
.ctrl_in
.bits
[i
] <= RTLIL::State::S1
&& RTLIL::SigSpec(tr
.ctrl_in
.bits
[i
]) != ctrl_bit
)
109 goto delete_this_transition
;
112 if (tr
.ctrl_in
.bits
[i
] <= RTLIL::State::S1
)
113 ctrl_in_used
[i
] = true;
115 new_transition_table
.push_back(tr
);
116 delete_this_transition
:;
119 for (int i
= int(ctrl_in_used
.size())-1; i
>= 0; i
--) {
120 if (!ctrl_in_used
[i
]) {
121 log(" Removing unused input signal %s.\n", log_signal(cell
->getPort("\\CTRL_IN").extract(i
, 1)));
122 for (auto &tr
: new_transition_table
) {
123 RTLIL::SigSpec
tmp(tr
.ctrl_in
);
125 tr
.ctrl_in
= tmp
.as_const();
127 RTLIL::SigSpec new_ctrl_in
= cell
->getPort("\\CTRL_IN");
128 new_ctrl_in
.remove(i
, 1);
129 cell
->setPort("\\CTRL_IN", new_ctrl_in
);
130 fsm_data
.num_inputs
--;
134 fsm_data
.transition_table
.swap(new_transition_table
);
135 new_transition_table
.clear();
138 void opt_unused_outputs()
140 for (int i
= 0; i
< fsm_data
.num_outputs
; i
++) {
141 RTLIL::SigSpec sig
= cell
->getPort("\\CTRL_OUT").extract(i
, 1);
142 if (signal_is_unused(sig
)) {
143 log(" Removing unused output signal %s.\n", log_signal(sig
));
144 RTLIL::SigSpec new_ctrl_out
= cell
->getPort("\\CTRL_OUT");
145 new_ctrl_out
.remove(i
, 1);
146 cell
->setPort("\\CTRL_OUT", new_ctrl_out
);
147 for (auto &tr
: fsm_data
.transition_table
) {
148 RTLIL::SigSpec
tmp(tr
.ctrl_out
);
150 tr
.ctrl_out
= tmp
.as_const();
152 fsm_data
.num_outputs
--;
158 void opt_alias_inputs()
160 RTLIL::SigSpec
&ctrl_in
= cell
->connections_
["\\CTRL_IN"];
162 for (int i
= 0; i
< ctrl_in
.size(); i
++)
163 for (int j
= i
+1; j
< ctrl_in
.size(); j
++)
164 if (ctrl_in
.extract(i
, 1) == ctrl_in
.extract(j
, 1))
166 log(" Optimize handling of signal %s that is connected to inputs %d and %d.\n", log_signal(ctrl_in
.extract(i
, 1)), i
, j
);
167 std::vector
<FsmData::transition_t
> new_transition_table
;
169 for (auto tr
: fsm_data
.transition_table
)
171 RTLIL::State
&si
= tr
.ctrl_in
.bits
[i
];
172 RTLIL::State
&sj
= tr
.ctrl_in
.bits
[j
];
174 if (si
> RTLIL::State::S1
)
176 else if (sj
> RTLIL::State::S1
)
180 RTLIL::SigSpec
tmp(tr
.ctrl_in
);
182 tr
.ctrl_in
= tmp
.as_const();
183 new_transition_table
.push_back(tr
);
187 ctrl_in
.remove(j
--, 1);
188 fsm_data
.num_inputs
--;
190 fsm_data
.transition_table
.swap(new_transition_table
);
191 new_transition_table
.clear();
195 void opt_feedback_inputs()
197 RTLIL::SigSpec
&ctrl_in
= cell
->connections_
["\\CTRL_IN"];
198 RTLIL::SigSpec
&ctrl_out
= cell
->connections_
["\\CTRL_OUT"];
200 for (int j
= 0; j
< ctrl_out
.size(); j
++)
201 for (int i
= 0; i
< ctrl_in
.size(); i
++)
202 if (ctrl_in
.extract(i
, 1) == ctrl_out
.extract(j
, 1))
204 log(" Optimize handling of signal %s that is connected to input %d and output %d.\n", log_signal(ctrl_in
.extract(i
, 1)), i
, j
);
205 std::vector
<FsmData::transition_t
> new_transition_table
;
207 for (auto tr
: fsm_data
.transition_table
)
209 RTLIL::State
&si
= tr
.ctrl_in
.bits
[i
];
210 RTLIL::State
&sj
= tr
.ctrl_out
.bits
[j
];
212 if (si
> RTLIL::State::S1
|| si
== sj
) {
213 RTLIL::SigSpec
tmp(tr
.ctrl_in
);
215 tr
.ctrl_in
= tmp
.as_const();
216 new_transition_table
.push_back(tr
);
220 ctrl_in
.remove(i
--, 1);
221 fsm_data
.num_inputs
--;
223 fsm_data
.transition_table
.swap(new_transition_table
);
224 new_transition_table
.clear();
228 void opt_find_dont_care_worker(std::set
<RTLIL::Const
> &set
, int bit
, FsmData::transition_t
&tr
, bool &did_something
)
230 std::set
<RTLIL::Const
> new_set
;
232 for (auto &pattern
: set
)
234 if (pattern
.bits
[bit
] > RTLIL::State::S1
) {
235 new_set
.insert(pattern
);
239 RTLIL::Const other_pattern
= pattern
;
241 if (pattern
.bits
[bit
] == RTLIL::State::S1
)
242 other_pattern
.bits
[bit
] = RTLIL::State::S0
;
244 other_pattern
.bits
[bit
] = RTLIL::State::S1
;
246 if (set
.count(other_pattern
) > 0) {
247 log(" Merging pattern %s and %s from group (%d %d %s).\n", log_signal(pattern
), log_signal(other_pattern
),
248 tr
.state_in
, tr
.state_out
, log_signal(tr
.ctrl_out
));
249 other_pattern
.bits
[bit
] = RTLIL::State::Sa
;
250 new_set
.insert(other_pattern
);
251 did_something
= true;
255 new_set
.insert(pattern
);
261 void opt_find_dont_care()
263 typedef std::pair
<std::pair
<int, int>, RTLIL::Const
> group_t
;
264 std::map
<group_t
, std::set
<RTLIL::Const
>> transitions_by_group
;
266 for (auto &tr
: fsm_data
.transition_table
) {
267 group_t
group(std::pair
<int, int>(tr
.state_in
, tr
.state_out
), tr
.ctrl_out
);
268 transitions_by_group
[group
].insert(tr
.ctrl_in
);
271 fsm_data
.transition_table
.clear();
272 for (auto &it
: transitions_by_group
)
274 FsmData::transition_t tr
;
275 tr
.state_in
= it
.first
.first
.first
;
276 tr
.state_out
= it
.first
.first
.second
;
277 tr
.ctrl_out
= it
.first
.second
;
279 bool did_something
= true;
280 while (did_something
) {
281 did_something
= false;
282 for (int i
= 0; i
< fsm_data
.num_inputs
; i
++)
283 opt_find_dont_care_worker(it
.second
, i
, tr
, did_something
);
286 for (auto &ci
: it
.second
) {
288 fsm_data
.transition_table
.push_back(tr
);
293 FsmOpt(RTLIL::Cell
*cell
, RTLIL::Module
*module
)
295 log("Optimizing FSM `%s' from module `%s'.\n", cell
->name
.c_str(), module
->name
.c_str());
297 fsm_data
.copy_from_cell(cell
);
299 this->module
= module
;
301 opt_unreachable_states();
303 opt_unused_outputs();
306 opt_feedback_inputs();
307 opt_find_dont_care();
309 opt_const_and_unused_inputs();
311 fsm_data
.copy_to_cell(cell
);
315 PRIVATE_NAMESPACE_END
317 void YOSYS_NAMESPACE_PREFIX
FsmData::optimize_fsm(RTLIL::Cell
*cell
, RTLIL::Module
*module
)
319 FsmOpt
fsmopt(cell
, module
);
322 PRIVATE_NAMESPACE_BEGIN
324 struct FsmOptPass
: public Pass
{
325 FsmOptPass() : Pass("fsm_opt", "optimize finite state machines") { }
328 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
330 log(" fsm_opt [selection]\n");
332 log("This pass optimizes FSM cells. It detects which output signals are actually\n");
333 log("not used and removes them from the FSM. This pass is usually used in\n");
334 log("combination with the 'opt_clean' pass (see also 'help fsm').\n");
337 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
339 log_header(design
, "Executing FSM_OPT pass (simple optimizations of FSMs).\n");
340 extra_args(args
, 1, design
);
342 for (auto &mod_it
: design
->modules_
) {
343 if (design
->selected(mod_it
.second
))
344 for (auto &cell_it
: mod_it
.second
->cells_
)
345 if (cell_it
.second
->type
== "$fsm" && design
->selected(mod_it
.second
, cell_it
.second
))
346 FsmData::optimize_fsm(cell_it
.second
, mod_it
.second
);
351 PRIVATE_NAMESPACE_END