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
33 RTLIL::Module
*module
;
34 RTLIL::Cell
*fsm_cell
;
38 SigSet
<RTLIL::Cell
*, RTLIL::sort_by_name_id
<RTLIL::Cell
>> sig2driver
, sig2user
;
41 std::set
<RTLIL::Cell
*, RTLIL::sort_by_name_id
<RTLIL::Cell
>> merged_set
;
42 std::set
<RTLIL::Cell
*, RTLIL::sort_by_name_id
<RTLIL::Cell
>> current_set
;
43 std::set
<RTLIL::Cell
*, RTLIL::sort_by_name_id
<RTLIL::Cell
>> no_candidate_set
;
45 bool already_optimized
;
46 int limit_transitions
;
48 bool is_cell_merge_candidate(RTLIL::Cell
*cell
)
50 if (full_mode
|| cell
->type
== "$_MUX_")
53 if (cell
->type
== "$mux" || cell
->type
== "$pmux")
54 if (cell
->getPort("\\A").size() < 2)
58 RTLIL::SigSpec new_signals
;
60 if (cell
->hasPort("\\A")) {
61 in_bits
+= GetSize(cell
->getPort("\\A"));
62 new_signals
.append(assign_map(cell
->getPort("\\A")));
65 if (cell
->hasPort("\\B")) {
66 in_bits
+= GetSize(cell
->getPort("\\B"));
67 new_signals
.append(assign_map(cell
->getPort("\\B")));
70 if (cell
->hasPort("\\S")) {
71 in_bits
+= GetSize(cell
->getPort("\\S"));
72 new_signals
.append(assign_map(cell
->getPort("\\S")));
78 if (cell
->hasPort("\\Y"))
79 new_signals
.append(assign_map(cell
->getPort("\\Y")));
81 new_signals
.sort_and_unify();
82 new_signals
.remove_const();
84 new_signals
.remove(assign_map(fsm_cell
->getPort("\\CTRL_IN")));
85 new_signals
.remove(assign_map(fsm_cell
->getPort("\\CTRL_OUT")));
87 if (new_signals
.size() > 3)
93 void create_current_set()
95 std::vector
<RTLIL::Cell
*> cell_list
;
97 for (auto c
: sig2driver
.find(assign_map(fsm_cell
->getPort("\\CTRL_IN"))))
98 cell_list
.push_back(c
);
100 for (auto c
: sig2user
.find(assign_map(fsm_cell
->getPort("\\CTRL_OUT"))))
101 cell_list
.push_back(c
);
104 for (auto c
: cell_list
)
106 if (merged_set
.count(c
) > 0 || current_set
.count(c
) > 0 || no_candidate_set
.count(c
) > 0)
108 for (auto &p
: c
->connections()) {
109 if (p
.first
!= "\\A" && p
.first
!= "\\B" && p
.first
!= "\\S" && p
.first
!= "\\Y")
112 if (!is_cell_merge_candidate(c
)) {
113 no_candidate_set
.insert(c
);
116 current_set
.insert(c
);
121 void optimze_as_needed()
123 if (already_optimized
)
126 int trans_num
= fsm_cell
->parameters
["\\TRANS_NUM"].as_int();
127 if (trans_num
> limit_transitions
)
129 log(" grown transition table to %d entries -> optimize.\n", trans_num
);
130 FsmData::optimize_fsm(fsm_cell
, module
);
131 already_optimized
= true;
133 trans_num
= fsm_cell
->parameters
["\\TRANS_NUM"].as_int();
134 log(" transition table size after optimizaton: %d\n", trans_num
);
135 limit_transitions
= 16 * trans_num
;
139 void merge_cell_into_fsm(RTLIL::Cell
*cell
)
143 log(" merging %s cell %s.\n", cell
->type
.c_str(), cell
->name
.c_str());
144 merged_set
.insert(cell
);
145 already_optimized
= false;
147 RTLIL::SigSpec input_sig
, output_sig
;
149 for (auto &p
: cell
->connections())
150 if (ct
.cell_output(cell
->type
, p
.first
))
151 output_sig
.append(assign_map(p
.second
));
153 input_sig
.append(assign_map(p
.second
));
154 input_sig
.sort_and_unify();
155 input_sig
.remove_const();
157 std::vector
<RTLIL::Const
> truth_tab
;
159 for (int i
= 0; i
< (1 << input_sig
.size()); i
++) {
160 RTLIL::Const
in_val(i
, input_sig
.size());
161 RTLIL::SigSpec A
, B
, S
;
162 if (cell
->hasPort("\\A"))
163 A
= assign_map(cell
->getPort("\\A"));
164 if (cell
->hasPort("\\B"))
165 B
= assign_map(cell
->getPort("\\B"));
166 if (cell
->hasPort("\\S"))
167 S
= assign_map(cell
->getPort("\\S"));
168 A
.replace(input_sig
, RTLIL::SigSpec(in_val
));
169 B
.replace(input_sig
, RTLIL::SigSpec(in_val
));
170 S
.replace(input_sig
, RTLIL::SigSpec(in_val
));
171 log_assert(A
.is_fully_const());
172 log_assert(B
.is_fully_const());
173 log_assert(S
.is_fully_const());
174 truth_tab
.push_back(ct
.eval(cell
, A
.as_const(), B
.as_const(), S
.as_const()));
178 fsm_data
.copy_from_cell(fsm_cell
);
180 fsm_data
.num_inputs
+= input_sig
.size();
181 RTLIL::SigSpec new_ctrl_in
= fsm_cell
->getPort("\\CTRL_IN");
182 new_ctrl_in
.append(input_sig
);
183 fsm_cell
->setPort("\\CTRL_IN", new_ctrl_in
);
185 fsm_data
.num_outputs
+= output_sig
.size();
186 RTLIL::SigSpec new_ctrl_out
= fsm_cell
->getPort("\\CTRL_OUT");
187 new_ctrl_out
.append(output_sig
);
188 fsm_cell
->setPort("\\CTRL_OUT", new_ctrl_out
);
190 if (GetSize(input_sig
) > 10)
191 log_warning("Cell %s.%s (%s) has %d input bits, merging into FSM %s.%s might be problematic.\n",
192 log_id(cell
->module
), log_id(cell
), log_id(cell
->type
),
193 GetSize(input_sig
), log_id(fsm_cell
->module
), log_id(fsm_cell
));
195 if (GetSize(fsm_data
.transition_table
) > 10000)
196 log_warning("Transition table for FSM %s.%s already has %d rows, merging more cells "
197 "into this FSM might be problematic.\n", log_id(fsm_cell
->module
), log_id(fsm_cell
),
198 GetSize(fsm_data
.transition_table
));
200 std::vector
<FsmData::transition_t
> new_transition_table
;
201 for (auto &tr
: fsm_data
.transition_table
) {
202 for (int i
= 0; i
< (1 << input_sig
.size()); i
++) {
203 FsmData::transition_t new_tr
= tr
;
204 RTLIL::Const
in_val(i
, input_sig
.size());
205 RTLIL::Const out_val
= truth_tab
[i
];
206 RTLIL::SigSpec ctrl_in
= new_tr
.ctrl_in
;
207 RTLIL::SigSpec ctrl_out
= new_tr
.ctrl_out
;
208 ctrl_in
.append(in_val
);
209 ctrl_out
.append(out_val
);
210 new_tr
.ctrl_in
= ctrl_in
.as_const();
211 new_tr
.ctrl_out
= ctrl_out
.as_const();
212 new_transition_table
.push_back(new_tr
);
215 fsm_data
.transition_table
.swap(new_transition_table
);
216 new_transition_table
.clear();
218 fsm_data
.copy_to_cell(fsm_cell
);
221 FsmExpand(RTLIL::Cell
*cell
, RTLIL::Design
*design
, RTLIL::Module
*mod
, bool full
)
227 assign_map
.set(module
);
228 ct
.setup_internals();
231 for (auto &cell_it
: module
->cells_
) {
232 RTLIL::Cell
*c
= cell_it
.second
;
233 if (ct
.cell_known(c
->type
) && design
->selected(mod
, c
))
234 for (auto &p
: c
->connections()) {
235 if (ct
.cell_output(c
->type
, p
.first
))
236 sig2driver
.insert(assign_map(p
.second
), c
);
238 sig2user
.insert(assign_map(p
.second
), c
);
246 log("Expanding FSM `%s' from module `%s':\n", fsm_cell
->name
.c_str(), module
->name
.c_str());
248 already_optimized
= false;
249 limit_transitions
= 16 * fsm_cell
->parameters
["\\TRANS_NUM"].as_int();
251 for (create_current_set(); current_set
.size() > 0; create_current_set()) {
252 for (auto c
: current_set
)
253 merge_cell_into_fsm(c
);
256 for (auto c
: merged_set
)
259 if (merged_set
.size() > 0 && !already_optimized
)
260 FsmData::optimize_fsm(fsm_cell
, module
);
262 log(" merged %d cells into FSM.\n", GetSize(merged_set
));
266 struct FsmExpandPass
: public Pass
{
267 FsmExpandPass() : Pass("fsm_expand", "expand FSM cells by merging logic into it") { }
268 void help() YS_OVERRIDE
270 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
272 log(" fsm_expand [-full] [selection]\n");
274 log("The fsm_extract pass is conservative about the cells that belong to a finite\n");
275 log("state machine. This pass can be used to merge additional auxiliary gates into\n");
276 log("the finite state machine.\n");
278 log("By default, fsm_expand is still a bit conservative regarding merging larger\n");
279 log("word-wide cells. Call with -full to consider all cells for merging.\n");
282 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
284 bool full_mode
= false;
286 log_header(design
, "Executing FSM_EXPAND pass (merging auxiliary logic into FSMs).\n");
289 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
290 if (args
[argidx
] == "-full") {
296 extra_args(args
, argidx
, design
);
298 for (auto &mod_it
: design
->modules_
) {
299 if (!design
->selected(mod_it
.second
))
301 std::vector
<RTLIL::Cell
*> fsm_cells
;
302 for (auto &cell_it
: mod_it
.second
->cells_
)
303 if (cell_it
.second
->type
== "$fsm" && design
->selected(mod_it
.second
, cell_it
.second
))
304 fsm_cells
.push_back(cell_it
.second
);
305 for (auto c
: fsm_cells
) {
306 FsmExpand
fsm_expand(c
, design
, mod_it
.second
, full_mode
);
307 fsm_expand
.execute();
313 PRIVATE_NAMESPACE_END