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
31 static bool pattern_is_subset(const RTLIL::Const
&super_pattern
, const RTLIL::Const
&sub_pattern
)
33 log_assert(GetSize(super_pattern
.bits
) == GetSize(sub_pattern
.bits
));
34 for (int i
= 0; i
< GetSize(super_pattern
.bits
); i
++)
35 if (sub_pattern
.bits
[i
] == RTLIL::State::S0
|| sub_pattern
.bits
[i
] == RTLIL::State::S1
) {
36 if (super_pattern
.bits
[i
] == RTLIL::State::S0
|| super_pattern
.bits
[i
] == RTLIL::State::S1
) {
37 if (super_pattern
.bits
[i
] != sub_pattern
.bits
[i
])
45 static void implement_pattern_cache(RTLIL::Module
*module
, std::map
<RTLIL::Const
, std::set
<int>> &pattern_cache
, std::set
<int> &fullstate_cache
, int num_states
, RTLIL::Wire
*state_onehot
, RTLIL::SigSpec
&ctrl_in
, RTLIL::SigSpec output
)
47 RTLIL::SigSpec cases_vector
;
49 for (int in_state
: fullstate_cache
)
50 cases_vector
.append(RTLIL::SigSpec(state_onehot
, in_state
));
52 for (auto &it
: pattern_cache
)
54 RTLIL::Const pattern
= it
.first
;
55 RTLIL::SigSpec eq_sig_a
, eq_sig_b
, or_sig
;
57 for (size_t j
= 0; j
< pattern
.bits
.size(); j
++)
58 if (pattern
.bits
[j
] == RTLIL::State::S0
|| pattern
.bits
[j
] == RTLIL::State::S1
) {
59 eq_sig_a
.append(ctrl_in
.extract(j
, 1));
60 eq_sig_b
.append(RTLIL::SigSpec(pattern
.bits
[j
]));
63 for (int in_state
: it
.second
)
64 if (fullstate_cache
.count(in_state
) == 0)
65 or_sig
.append(RTLIL::SigSpec(state_onehot
, in_state
));
67 if (or_sig
.size() == 0)
70 RTLIL::SigSpec and_sig
;
72 if (eq_sig_a
.size() > 0)
74 RTLIL::Wire
*eq_wire
= module
->addWire(NEW_ID
);
75 and_sig
.append(RTLIL::SigSpec(eq_wire
));
77 RTLIL::Cell
*eq_cell
= module
->addCell(NEW_ID
, "$eq");
78 eq_cell
->setPort("\\A", eq_sig_a
);
79 eq_cell
->setPort("\\B", eq_sig_b
);
80 eq_cell
->setPort("\\Y", RTLIL::SigSpec(eq_wire
));
81 eq_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(false);
82 eq_cell
->parameters
["\\B_SIGNED"] = RTLIL::Const(false);
83 eq_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(eq_sig_a
.size());
84 eq_cell
->parameters
["\\B_WIDTH"] = RTLIL::Const(eq_sig_b
.size());
85 eq_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
88 std::set
<int> complete_in_state_cache
= it
.second
;
90 for (auto &it2
: pattern_cache
)
91 if (pattern_is_subset(pattern
, it2
.first
))
92 complete_in_state_cache
.insert(it2
.second
.begin(), it2
.second
.end());
94 if (GetSize(complete_in_state_cache
) < num_states
)
96 if (or_sig
.size() == 1)
98 and_sig
.append(or_sig
);
102 RTLIL::Wire
*or_wire
= module
->addWire(NEW_ID
);
103 and_sig
.append(RTLIL::SigSpec(or_wire
));
105 RTLIL::Cell
*or_cell
= module
->addCell(NEW_ID
, "$reduce_or");
106 or_cell
->setPort("\\A", or_sig
);
107 or_cell
->setPort("\\Y", RTLIL::SigSpec(or_wire
));
108 or_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(false);
109 or_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(or_sig
.size());
110 or_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
114 switch (and_sig
.size())
118 RTLIL::Wire
*and_wire
= module
->addWire(NEW_ID
);
119 cases_vector
.append(RTLIL::SigSpec(and_wire
));
121 RTLIL::Cell
*and_cell
= module
->addCell(NEW_ID
, "$and");
122 and_cell
->setPort("\\A", and_sig
.extract(0, 1));
123 and_cell
->setPort("\\B", and_sig
.extract(1, 1));
124 and_cell
->setPort("\\Y", RTLIL::SigSpec(and_wire
));
125 and_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(false);
126 and_cell
->parameters
["\\B_SIGNED"] = RTLIL::Const(false);
127 and_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(1);
128 and_cell
->parameters
["\\B_WIDTH"] = RTLIL::Const(1);
129 and_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
133 cases_vector
.append(and_sig
);
136 cases_vector
.append(State::S1
);
143 if (cases_vector
.size() > 1) {
144 RTLIL::Cell
*or_cell
= module
->addCell(NEW_ID
, "$reduce_or");
145 or_cell
->setPort("\\A", cases_vector
);
146 or_cell
->setPort("\\Y", output
);
147 or_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(false);
148 or_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(cases_vector
.size());
149 or_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
150 } else if (cases_vector
.size() == 1) {
151 module
->connect(RTLIL::SigSig(output
, cases_vector
));
153 module
->connect(RTLIL::SigSig(output
, State::S0
));
157 static void map_fsm(RTLIL::Cell
*fsm_cell
, RTLIL::Module
*module
)
159 log("Mapping FSM `%s' from module `%s'.\n", fsm_cell
->name
.c_str(), module
->name
.c_str());
162 fsm_data
.copy_from_cell(fsm_cell
);
164 RTLIL::SigSpec ctrl_in
= fsm_cell
->getPort("\\CTRL_IN");
165 RTLIL::SigSpec ctrl_out
= fsm_cell
->getPort("\\CTRL_OUT");
167 // create state register
169 RTLIL::Wire
*state_wire
= module
->addWire(module
->uniquify(fsm_cell
->parameters
["\\NAME"].decode_string()), fsm_data
.state_bits
);
170 RTLIL::Wire
*next_state_wire
= module
->addWire(NEW_ID
, fsm_data
.state_bits
);
172 RTLIL::Cell
*state_dff
= module
->addCell(NEW_ID
, "");
173 if (fsm_cell
->getPort("\\ARST").is_fully_const()) {
174 state_dff
->type
= "$dff";
176 state_dff
->type
= "$adff";
177 state_dff
->parameters
["\\ARST_POLARITY"] = fsm_cell
->parameters
["\\ARST_POLARITY"];
178 state_dff
->parameters
["\\ARST_VALUE"] = fsm_data
.state_table
[fsm_data
.reset_state
];
179 for (auto &bit
: state_dff
->parameters
["\\ARST_VALUE"].bits
)
180 if (bit
!= RTLIL::State::S1
)
181 bit
= RTLIL::State::S0
;
182 state_dff
->setPort("\\ARST", fsm_cell
->getPort("\\ARST"));
184 state_dff
->parameters
["\\WIDTH"] = RTLIL::Const(fsm_data
.state_bits
);
185 state_dff
->parameters
["\\CLK_POLARITY"] = fsm_cell
->parameters
["\\CLK_POLARITY"];
186 state_dff
->setPort("\\CLK", fsm_cell
->getPort("\\CLK"));
187 state_dff
->setPort("\\D", RTLIL::SigSpec(next_state_wire
));
188 state_dff
->setPort("\\Q", RTLIL::SigSpec(state_wire
));
190 // decode state register
192 bool encoding_is_onehot
= true;
194 RTLIL::Wire
*state_onehot
= module
->addWire(NEW_ID
, fsm_data
.state_table
.size());
196 for (size_t i
= 0; i
< fsm_data
.state_table
.size(); i
++)
198 RTLIL::Const state
= fsm_data
.state_table
[i
];
199 RTLIL::SigSpec sig_a
, sig_b
;
201 for (size_t j
= 0; j
< state
.bits
.size(); j
++)
202 if (state
.bits
[j
] == RTLIL::State::S0
|| state
.bits
[j
] == RTLIL::State::S1
) {
203 sig_a
.append(RTLIL::SigSpec(state_wire
, j
));
204 sig_b
.append(RTLIL::SigSpec(state
.bits
[j
]));
207 if (sig_b
== RTLIL::SigSpec(RTLIL::State::S1
))
209 module
->connect(RTLIL::SigSig(RTLIL::SigSpec(state_onehot
, i
), sig_a
));
213 encoding_is_onehot
= false;
215 RTLIL::Cell
*eq_cell
= module
->addCell(NEW_ID
, "$eq");
216 eq_cell
->setPort("\\A", sig_a
);
217 eq_cell
->setPort("\\B", sig_b
);
218 eq_cell
->setPort("\\Y", RTLIL::SigSpec(state_onehot
, i
));
219 eq_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(false);
220 eq_cell
->parameters
["\\B_SIGNED"] = RTLIL::Const(false);
221 eq_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(sig_a
.size());
222 eq_cell
->parameters
["\\B_WIDTH"] = RTLIL::Const(sig_b
.size());
223 eq_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
227 if (encoding_is_onehot
)
228 state_wire
->set_bool_attribute("\\onehot");
230 // generate next_state signal
232 if (GetSize(fsm_data
.state_table
) == 1)
234 module
->connect(next_state_wire
, fsm_data
.state_table
.front());
238 RTLIL::Wire
*next_state_onehot
= module
->addWire(NEW_ID
, fsm_data
.state_table
.size());
240 for (size_t i
= 0; i
< fsm_data
.state_table
.size(); i
++)
242 std::map
<RTLIL::Const
, std::set
<int>> pattern_cache
;
243 std::set
<int> fullstate_cache
;
245 for (size_t j
= 0; j
< fsm_data
.state_table
.size(); j
++)
246 fullstate_cache
.insert(j
);
248 for (auto &tr
: fsm_data
.transition_table
) {
249 if (tr
.state_out
== int(i
))
250 pattern_cache
[tr
.ctrl_in
].insert(tr
.state_in
);
252 fullstate_cache
.erase(tr
.state_in
);
255 implement_pattern_cache(module
, pattern_cache
, fullstate_cache
, fsm_data
.state_table
.size(), state_onehot
, ctrl_in
, RTLIL::SigSpec(next_state_onehot
, i
));
258 if (encoding_is_onehot
)
260 RTLIL::SigSpec
next_state_sig(RTLIL::State::Sm
, next_state_wire
->width
);
261 for (size_t i
= 0; i
< fsm_data
.state_table
.size(); i
++) {
262 RTLIL::Const state
= fsm_data
.state_table
[i
];
264 for (size_t j
= 0; j
< state
.bits
.size(); j
++)
265 if (state
.bits
[j
] == RTLIL::State::S1
)
268 next_state_sig
.replace(bit_idx
, RTLIL::SigSpec(next_state_onehot
, i
));
270 log_assert(!next_state_sig
.has_marked_bits());
271 module
->connect(RTLIL::SigSig(next_state_wire
, next_state_sig
));
275 RTLIL::SigSpec
sig_a(RTLIL::State::Sx
, next_state_wire
->width
);
276 RTLIL::SigSpec sig_b
, sig_s
;
278 for (size_t i
= 0; i
< fsm_data
.state_table
.size(); i
++) {
279 RTLIL::Const state
= fsm_data
.state_table
[i
];
280 if (int(i
) == fsm_data
.reset_state
) {
281 sig_a
= RTLIL::SigSpec(state
);
283 sig_b
.append(RTLIL::SigSpec(state
));
284 sig_s
.append(RTLIL::SigSpec(next_state_onehot
, i
));
288 RTLIL::Cell
*mux_cell
= module
->addCell(NEW_ID
, "$pmux");
289 mux_cell
->setPort("\\A", sig_a
);
290 mux_cell
->setPort("\\B", sig_b
);
291 mux_cell
->setPort("\\S", sig_s
);
292 mux_cell
->setPort("\\Y", RTLIL::SigSpec(next_state_wire
));
293 mux_cell
->parameters
["\\WIDTH"] = RTLIL::Const(sig_a
.size());
294 mux_cell
->parameters
["\\S_WIDTH"] = RTLIL::Const(sig_s
.size());
298 // Generate ctrl_out signal
300 for (int i
= 0; i
< fsm_data
.num_outputs
; i
++)
302 std::map
<RTLIL::Const
, std::set
<int>> pattern_cache
;
303 std::set
<int> fullstate_cache
;
305 for (size_t j
= 0; j
< fsm_data
.state_table
.size(); j
++)
306 fullstate_cache
.insert(j
);
308 for (auto &tr
: fsm_data
.transition_table
) {
309 if (tr
.ctrl_out
.bits
[i
] == RTLIL::State::S1
)
310 pattern_cache
[tr
.ctrl_in
].insert(tr
.state_in
);
312 fullstate_cache
.erase(tr
.state_in
);
315 implement_pattern_cache(module
, pattern_cache
, fullstate_cache
, fsm_data
.state_table
.size(), state_onehot
, ctrl_in
, ctrl_out
.extract(i
, 1));
320 module
->remove(fsm_cell
);
323 struct FsmMapPass
: public Pass
{
324 FsmMapPass() : Pass("fsm_map", "mapping FSMs to basic logic") { }
325 void help() YS_OVERRIDE
327 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
329 log(" fsm_map [selection]\n");
331 log("This pass translates FSM cells to flip-flops and logic.\n");
334 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
336 log_header(design
, "Executing FSM_MAP pass (mapping FSMs to basic logic).\n");
337 extra_args(args
, 1, design
);
339 for (auto &mod_it
: design
->modules_
) {
340 if (!design
->selected(mod_it
.second
))
342 std::vector
<RTLIL::Cell
*> fsm_cells
;
343 for (auto &cell_it
: mod_it
.second
->cells_
)
344 if (cell_it
.second
->type
== "$fsm" && design
->selected(mod_it
.second
, cell_it
.second
))
345 fsm_cells
.push_back(cell_it
.second
);
346 for (auto cell
: fsm_cells
)
347 map_fsm(cell
, mod_it
.second
);
352 PRIVATE_NAMESPACE_END