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/register.h"
21 #include "kernel/bitpattern.h"
22 #include "kernel/log.h"
28 PRIVATE_NAMESPACE_BEGIN
32 idict
<SigSpec
> sigidx
;
33 dict
<SigBit
, int> bit2snippet
;
36 void insert(SigSpec sig
)
41 int key
= sigidx(sig
);
42 if (snippets
.count(key
))
47 for (int i
= 0; i
< GetSize(sig
); i
++)
49 int other_key
= bit2snippet
.at(sig
[i
], -1);
52 new_sig
.append(sig
[i
]);
56 if (!new_sig
.empty()) {
57 int new_key
= sigidx(new_sig
);
58 snippets
.insert(new_key
);
59 for (auto bit
: new_sig
)
60 bit2snippet
[bit
] = new_key
;
64 SigSpec other_sig
= sigidx
[other_key
];
67 while (other_sig
[k
] != sig
[i
]) {
69 log_assert(k
< GetSize(other_sig
));
72 while (i
+n
< GetSize(sig
) && k
+n
< GetSize(other_sig
) && sig
[i
+n
] == other_sig
[k
+n
])
75 SigSpec sig1
= other_sig
.extract(0, k
);
76 SigSpec sig2
= other_sig
.extract(k
, n
);
77 SigSpec sig3
= other_sig
.extract(k
+n
, GetSize(other_sig
)-k
-n
);
79 for (auto bit
: other_sig
)
80 bit2snippet
.erase(bit
);
81 snippets
.erase(other_key
);
90 if (!new_sig
.empty()) {
91 int new_key
= sigidx(new_sig
);
92 snippets
.insert(new_key
);
93 for (auto bit
: new_sig
)
94 bit2snippet
[bit
] = new_key
;
98 void insert(const RTLIL::CaseRule
*cs
)
100 for (auto &action
: cs
->actions
)
101 insert(action
.first
);
103 for (auto sw
: cs
->switches
)
104 for (auto cs2
: sw
->cases
)
109 struct SnippetSwCache
111 dict
<RTLIL::SwitchRule
*, pool
<RTLIL::SigBit
>, hash_ptr_ops
> full_case_bits_cache
;
112 dict
<RTLIL::SwitchRule
*, pool
<int>, hash_ptr_ops
> cache
;
113 const SigSnippets
*snippets
;
116 bool check(RTLIL::SwitchRule
*sw
)
118 return cache
[sw
].count(current_snippet
) != 0;
121 void insert(const RTLIL::CaseRule
*cs
, vector
<RTLIL::SwitchRule
*> &sw_stack
)
123 for (auto &action
: cs
->actions
)
124 for (auto bit
: action
.first
) {
125 int sn
= snippets
->bit2snippet
.at(bit
, -1);
128 for (auto sw
: sw_stack
)
129 cache
[sw
].insert(sn
);
132 for (auto sw
: cs
->switches
) {
133 sw_stack
.push_back(sw
);
134 for (auto cs2
: sw
->cases
)
135 insert(cs2
, sw_stack
);
140 void insert(const RTLIL::CaseRule
*cs
)
142 vector
<RTLIL::SwitchRule
*> sw_stack
;
143 insert(cs
, sw_stack
);
147 RTLIL::SigSpec
gen_cmp(RTLIL::Module
*mod
, const RTLIL::SigSpec
&signal
, const std::vector
<RTLIL::SigSpec
> &compare
, RTLIL::SwitchRule
*sw
, bool ifxmode
)
149 std::stringstream sstr
;
150 sstr
<< "$procmux$" << (autoidx
++);
152 RTLIL::Wire
*cmp_wire
= mod
->addWire(sstr
.str() + "_CMP", 0);
154 for (auto comp
: compare
)
156 RTLIL::SigSpec sig
= signal
;
158 // get rid of don't-care bits
159 log_assert(sig
.size() == comp
.size());
160 for (int i
= 0; i
< comp
.size(); i
++)
161 if (comp
[i
] == RTLIL::State::Sa
) {
165 if (comp
.size() == 0)
166 return RTLIL::SigSpec();
168 if (sig
.size() == 1 && comp
== RTLIL::SigSpec(1,1) && !ifxmode
)
170 mod
->connect(RTLIL::SigSig(RTLIL::SigSpec(cmp_wire
, cmp_wire
->width
++), sig
));
174 // create compare cell
175 RTLIL::Cell
*eq_cell
= mod
->addCell(stringf("%s_CMP%d", sstr
.str().c_str(), cmp_wire
->width
), ifxmode
? "$eqx" : "$eq");
176 eq_cell
->attributes
= sw
->attributes
;
178 eq_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(0);
179 eq_cell
->parameters
["\\B_SIGNED"] = RTLIL::Const(0);
181 eq_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(sig
.size());
182 eq_cell
->parameters
["\\B_WIDTH"] = RTLIL::Const(comp
.size());
183 eq_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
185 eq_cell
->setPort("\\A", sig
);
186 eq_cell
->setPort("\\B", comp
);
187 eq_cell
->setPort("\\Y", RTLIL::SigSpec(cmp_wire
, cmp_wire
->width
++));
191 RTLIL::Wire
*ctrl_wire
;
192 if (cmp_wire
->width
== 1)
194 ctrl_wire
= cmp_wire
;
198 ctrl_wire
= mod
->addWire(sstr
.str() + "_CTRL");
200 // reduce cmp vector to one logic signal
201 RTLIL::Cell
*any_cell
= mod
->addCell(sstr
.str() + "_ANY", "$reduce_or");
202 any_cell
->attributes
= sw
->attributes
;
204 any_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(0);
205 any_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(cmp_wire
->width
);
206 any_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
208 any_cell
->setPort("\\A", cmp_wire
);
209 any_cell
->setPort("\\Y", RTLIL::SigSpec(ctrl_wire
));
212 return RTLIL::SigSpec(ctrl_wire
);
215 RTLIL::SigSpec
gen_mux(RTLIL::Module
*mod
, const RTLIL::SigSpec
&signal
, const std::vector
<RTLIL::SigSpec
> &compare
, RTLIL::SigSpec when_signal
, RTLIL::SigSpec else_signal
, RTLIL::Cell
*&last_mux_cell
, RTLIL::SwitchRule
*sw
, bool ifxmode
)
217 log_assert(when_signal
.size() == else_signal
.size());
219 std::stringstream sstr
;
220 sstr
<< "$procmux$" << (autoidx
++);
223 if (compare
.size() == 0 || when_signal
== else_signal
)
227 RTLIL::SigSpec ctrl_sig
= gen_cmp(mod
, signal
, compare
, sw
, ifxmode
);
228 if (ctrl_sig
.size() == 0)
230 log_assert(ctrl_sig
.size() == 1);
232 // prepare multiplexer output signal
233 RTLIL::Wire
*result_wire
= mod
->addWire(sstr
.str() + "_Y", when_signal
.size());
235 // create the multiplexer itself
236 RTLIL::Cell
*mux_cell
= mod
->addCell(sstr
.str(), "$mux");
237 mux_cell
->attributes
= sw
->attributes
;
239 mux_cell
->parameters
["\\WIDTH"] = RTLIL::Const(when_signal
.size());
240 mux_cell
->setPort("\\A", else_signal
);
241 mux_cell
->setPort("\\B", when_signal
);
242 mux_cell
->setPort("\\S", ctrl_sig
);
243 mux_cell
->setPort("\\Y", RTLIL::SigSpec(result_wire
));
245 last_mux_cell
= mux_cell
;
246 return RTLIL::SigSpec(result_wire
);
249 void append_pmux(RTLIL::Module
*mod
, const RTLIL::SigSpec
&signal
, const std::vector
<RTLIL::SigSpec
> &compare
, RTLIL::SigSpec when_signal
, RTLIL::Cell
*last_mux_cell
, RTLIL::SwitchRule
*sw
, bool ifxmode
)
251 log_assert(last_mux_cell
!= NULL
);
252 log_assert(when_signal
.size() == last_mux_cell
->getPort("\\A").size());
254 if (when_signal
== last_mux_cell
->getPort("\\A"))
257 RTLIL::SigSpec ctrl_sig
= gen_cmp(mod
, signal
, compare
, sw
, ifxmode
);
258 log_assert(ctrl_sig
.size() == 1);
259 last_mux_cell
->type
= "$pmux";
261 RTLIL::SigSpec new_s
= last_mux_cell
->getPort("\\S");
262 new_s
.append(ctrl_sig
);
263 last_mux_cell
->setPort("\\S", new_s
);
265 RTLIL::SigSpec new_b
= last_mux_cell
->getPort("\\B");
266 new_b
.append(when_signal
);
267 last_mux_cell
->setPort("\\B", new_b
);
269 last_mux_cell
->parameters
["\\S_WIDTH"] = last_mux_cell
->getPort("\\S").size();
272 const pool
<SigBit
> &get_full_case_bits(SnippetSwCache
&swcache
, RTLIL::SwitchRule
*sw
)
274 if (!swcache
.full_case_bits_cache
.count(sw
))
278 if (sw
->get_bool_attribute("\\full_case"))
280 bool first_case
= true;
282 for (auto cs
: sw
->cases
)
284 pool
<SigBit
> case_bits
;
286 for (auto it
: cs
->actions
) {
287 for (auto bit
: it
.first
)
288 case_bits
.insert(bit
);
291 for (auto it
: cs
->switches
) {
292 for (auto bit
: get_full_case_bits(swcache
, it
))
293 case_bits
.insert(bit
);
300 pool
<SigBit
> new_bits
;
301 for (auto bit
: bits
)
302 if (case_bits
.count(bit
))
303 new_bits
.insert(bit
);
309 bits
.swap(swcache
.full_case_bits_cache
[sw
]);
312 return swcache
.full_case_bits_cache
.at(sw
);
315 RTLIL::SigSpec
signal_to_mux_tree(RTLIL::Module
*mod
, SnippetSwCache
&swcache
, dict
<RTLIL::SwitchRule
*, bool, hash_ptr_ops
> &swpara
,
316 RTLIL::CaseRule
*cs
, const RTLIL::SigSpec
&sig
, const RTLIL::SigSpec
&defval
, bool ifxmode
)
318 RTLIL::SigSpec result
= defval
;
320 for (auto &action
: cs
->actions
) {
321 sig
.replace(action
.first
, action
.second
, &result
);
322 action
.first
.remove2(sig
, &action
.second
);
325 for (auto sw
: cs
->switches
)
327 if (!swcache
.check(sw
))
330 // detect groups of parallel cases
331 std::vector
<int> pgroups(sw
->cases
.size());
332 bool is_simple_parallel_case
= true;
334 if (!sw
->get_bool_attribute("\\parallel_case")) {
335 if (!swpara
.count(sw
)) {
336 pool
<Const
> case_values
;
337 for (size_t i
= 0; i
< sw
->cases
.size(); i
++) {
338 RTLIL::CaseRule
*cs2
= sw
->cases
[i
];
339 for (auto pat
: cs2
->compare
) {
340 if (!pat
.is_fully_def())
341 goto not_simple_parallel_case
;
342 Const cpat
= pat
.as_const();
343 if (case_values
.count(cpat
))
344 goto not_simple_parallel_case
;
345 case_values
.insert(cpat
);
349 not_simple_parallel_case
:
350 is_simple_parallel_case
= false;
351 swpara
[sw
] = is_simple_parallel_case
;
353 is_simple_parallel_case
= swpara
.at(sw
);
357 if (!is_simple_parallel_case
) {
358 BitPatternPool
pool(sw
->signal
.size());
359 bool extra_group_for_next_case
= false;
360 for (size_t i
= 0; i
< sw
->cases
.size(); i
++) {
361 RTLIL::CaseRule
*cs2
= sw
->cases
[i
];
363 pgroups
[i
] = pgroups
[i
-1];
364 if (extra_group_for_next_case
) {
365 pgroups
[i
] = pgroups
[i
-1]+1;
366 extra_group_for_next_case
= false;
368 for (auto pat
: cs2
->compare
)
369 if (!pat
.is_fully_const() || !pool
.has_all(pat
))
370 pgroups
[i
] = pgroups
[i
-1]+1;
371 if (cs2
->compare
.empty())
372 pgroups
[i
] = pgroups
[i
-1]+1;
373 if (pgroups
[i
] != pgroups
[i
-1])
374 pool
= BitPatternPool(sw
->signal
.size());
376 for (auto pat
: cs2
->compare
)
377 if (!pat
.is_fully_const())
378 extra_group_for_next_case
= true;
384 // mask default bits that are irrelevant because the output is driven by a full case
385 const pool
<SigBit
> &full_case_bits
= get_full_case_bits(swcache
, sw
);
386 for (int i
= 0; i
< GetSize(sig
); i
++)
387 if (full_case_bits
.count(sig
[i
]))
388 result
[i
] = State::Sx
;
390 // evaluate in reverse order to give the first entry the top priority
391 RTLIL::SigSpec initial_val
= result
;
392 RTLIL::Cell
*last_mux_cell
= NULL
;
393 for (size_t i
= 0; i
< sw
->cases
.size(); i
++) {
394 int case_idx
= sw
->cases
.size() - i
- 1;
395 RTLIL::CaseRule
*cs2
= sw
->cases
[case_idx
];
396 RTLIL::SigSpec value
= signal_to_mux_tree(mod
, swcache
, swpara
, cs2
, sig
, initial_val
, ifxmode
);
397 if (last_mux_cell
&& pgroups
[case_idx
] == pgroups
[case_idx
+1])
398 append_pmux(mod
, sw
->signal
, cs2
->compare
, value
, last_mux_cell
, sw
, ifxmode
);
400 result
= gen_mux(mod
, sw
->signal
, cs2
->compare
, value
, result
, last_mux_cell
, sw
, ifxmode
);
407 void proc_mux(RTLIL::Module
*mod
, RTLIL::Process
*proc
, bool ifxmode
)
409 log("Creating decoders for process `%s.%s'.\n", mod
->name
.c_str(), proc
->name
.c_str());
412 sigsnip
.insert(&proc
->root_case
);
414 SnippetSwCache swcache
;
415 swcache
.snippets
= &sigsnip
;
416 swcache
.insert(&proc
->root_case
);
418 dict
<RTLIL::SwitchRule
*, bool, hash_ptr_ops
> swpara
;
421 for (int idx
: sigsnip
.snippets
)
423 swcache
.current_snippet
= idx
;
424 RTLIL::SigSpec sig
= sigsnip
.sigidx
[idx
];
426 log("%6d/%d: %s\n", ++cnt
, GetSize(sigsnip
.snippets
), log_signal(sig
));
428 RTLIL::SigSpec value
= signal_to_mux_tree(mod
, swcache
, swpara
, &proc
->root_case
, sig
, RTLIL::SigSpec(RTLIL::State::Sx
, sig
.size()), ifxmode
);
429 mod
->connect(RTLIL::SigSig(sig
, value
));
433 struct ProcMuxPass
: public Pass
{
434 ProcMuxPass() : Pass("proc_mux", "convert decision trees to multiplexers") { }
435 void help() YS_OVERRIDE
437 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
439 log(" proc_mux [options] [selection]\n");
441 log("This pass converts the decision trees in processes (originating from if-else\n");
442 log("and case statements) to trees of multiplexer cells.\n");
445 log(" Use Verilog simulation behavior with respect to undef values in\n");
446 log(" 'case' expressions and 'if' conditions.\n");
449 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
451 bool ifxmode
= false;
452 log_header(design
, "Executing PROC_MUX pass (convert decision trees to multiplexers).\n");
455 for (argidx
= 1; argidx
< args
.size(); argidx
++)
457 if (args
[argidx
] == "-ifx") {
463 extra_args(args
, argidx
, design
);
465 for (auto mod
: design
->modules())
466 if (design
->selected(mod
))
467 for (auto &proc_it
: mod
->processes
)
468 if (design
->selected(mod
, proc_it
.second
))
469 proc_mux(mod
, proc_it
.second
, ifxmode
);
473 PRIVATE_NAMESPACE_END