2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 * 2019 Eddie Hung <eddie@fpgeh.com>
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 #include "kernel/yosys.h"
22 #include "kernel/sigtools.h"
25 PRIVATE_NAMESPACE_BEGIN
27 struct ExclusiveDatabase
32 dict
<SigBit
, std::pair
<SigSpec
,std::vector
<Const
>>> sig_cmp_prev
;
34 ExclusiveDatabase(Module
*module
, const SigMap
&sigmap
) : module(module
), sigmap(sigmap
)
36 SigSpec const_sig
, nonconst_sig
;
38 pool
<Cell
*> reduce_or
;
39 for (auto cell
: module
->cells()) {
40 if (cell
->type
== ID($eq
)) {
41 nonconst_sig
= sigmap(cell
->getPort(ID::A
));
42 const_sig
= sigmap(cell
->getPort(ID::B
));
43 if (!const_sig
.is_fully_const()) {
44 if (!nonconst_sig
.is_fully_const())
46 std::swap(nonconst_sig
, const_sig
);
48 y_port
= sigmap(cell
->getPort(ID::Y
));
50 else if (cell
->type
== ID($logic_not
)) {
51 nonconst_sig
= sigmap(cell
->getPort(ID::A
));
52 const_sig
= Const(State::S0
, GetSize(nonconst_sig
));
53 y_port
= sigmap(cell
->getPort(ID::Y
));
55 else if (cell
->type
== ID($reduce_or
)) {
56 reduce_or
.insert(cell
);
61 log_assert(!nonconst_sig
.empty());
62 log_assert(!const_sig
.empty());
63 sig_cmp_prev
[y_port
] = std::make_pair(nonconst_sig
,std::vector
<Const
>{const_sig
.as_const()});
66 for (auto cell
: reduce_or
) {
67 nonconst_sig
= SigSpec();
68 std::vector
<Const
> values
;
69 SigSpec a_port
= sigmap(cell
->getPort(ID::A
));
70 for (auto bit
: a_port
) {
71 auto it
= sig_cmp_prev
.find(bit
);
72 if (it
== sig_cmp_prev
.end()) {
73 nonconst_sig
= SigSpec();
76 if (nonconst_sig
.empty())
77 nonconst_sig
= it
->second
.first
;
78 else if (nonconst_sig
!= it
->second
.first
) {
79 nonconst_sig
= SigSpec();
82 for (auto value
: it
->second
.second
)
83 values
.push_back(value
);
85 if (nonconst_sig
.empty())
87 y_port
= sigmap(cell
->getPort(ID::Y
));
88 sig_cmp_prev
[y_port
] = std::make_pair(nonconst_sig
,std::move(values
));
92 bool query(const SigSpec
&sig
) const
95 pool
<Const
> const_values
;
97 for (auto bit
: sig
.bits()) {
98 auto it
= sig_cmp_prev
.find(bit
);
99 if (it
== sig_cmp_prev
.end())
102 if (nonconst_sig
.empty())
103 nonconst_sig
= it
->second
.first
;
104 else if (nonconst_sig
!= it
->second
.first
)
107 for (auto value
: it
->second
.second
)
108 if (!const_values
.insert(value
).second
)
122 int mux_count
, pmux_count
;
124 pool
<Cell
*> remove_cells
;
126 dict
<SigSpec
, Cell
*> sig_chain_next
;
127 dict
<SigSpec
, Cell
*> sig_chain_prev
;
128 pool
<SigBit
> sigbit_with_non_chain_users
;
129 pool
<Cell
*> chain_start_cells
;
130 pool
<Cell
*> candidate_cells
;
132 ExclusiveDatabase excl_db
;
134 void make_sig_chain_next_prev()
136 for (auto wire
: module
->wires())
138 if (wire
->port_output
|| wire
->get_bool_attribute(ID::keep
)) {
139 for (auto bit
: sigmap(wire
))
140 sigbit_with_non_chain_users
.insert(bit
);
144 for (auto cell
: module
->cells())
146 if (cell
->type
.in(ID($mux
), ID($pmux
)) && !cell
->get_bool_attribute(ID::keep
))
148 SigSpec a_sig
= sigmap(cell
->getPort(ID::A
));
150 if (cell
->type
== ID($mux
))
151 b_sig
= sigmap(cell
->getPort(ID::B
));
152 SigSpec y_sig
= sigmap(cell
->getPort(ID::Y
));
154 if (sig_chain_next
.count(a_sig
))
155 for (auto a_bit
: a_sig
.bits())
156 sigbit_with_non_chain_users
.insert(a_bit
);
158 sig_chain_next
[a_sig
] = cell
;
159 candidate_cells
.insert(cell
);
162 if (!b_sig
.empty()) {
163 if (sig_chain_next
.count(b_sig
))
164 for (auto b_bit
: b_sig
.bits())
165 sigbit_with_non_chain_users
.insert(b_bit
);
167 sig_chain_next
[b_sig
] = cell
;
168 candidate_cells
.insert(cell
);
172 sig_chain_prev
[y_sig
] = cell
;
176 for (auto conn
: cell
->connections())
177 if (cell
->input(conn
.first
))
178 for (auto bit
: sigmap(conn
.second
))
179 sigbit_with_non_chain_users
.insert(bit
);
183 void find_chain_start_cells()
185 for (auto cell
: candidate_cells
)
187 log_debug("Considering %s (%s)\n", log_id(cell
), log_id(cell
->type
));
189 SigSpec a_sig
= sigmap(cell
->getPort(ID::A
));
190 if (cell
->type
== ID($mux
)) {
191 SigSpec b_sig
= sigmap(cell
->getPort(ID::B
));
192 if (sig_chain_prev
.count(a_sig
) + sig_chain_prev
.count(b_sig
) != 1)
195 if (!sig_chain_prev
.count(a_sig
))
198 else if (cell
->type
== ID($pmux
)) {
199 if (!sig_chain_prev
.count(a_sig
))
204 for (auto bit
: a_sig
.bits())
205 if (sigbit_with_non_chain_users
.count(bit
))
209 Cell
*prev_cell
= sig_chain_prev
.at(a_sig
);
210 log_assert(prev_cell
);
211 SigSpec s_sig
= sigmap(cell
->getPort(ID::S
));
212 s_sig
.append(sigmap(prev_cell
->getPort(ID::S
)));
213 if (!excl_db
.query(s_sig
))
220 chain_start_cells
.insert(cell
);
224 vector
<Cell
*> create_chain(Cell
*start_cell
)
228 Cell
*c
= start_cell
;
233 SigSpec y_sig
= sigmap(c
->getPort(ID::Y
));
235 if (sig_chain_next
.count(y_sig
) == 0)
238 c
= sig_chain_next
.at(y_sig
);
239 if (chain_start_cells
.count(c
) != 0)
246 void process_chain(vector
<Cell
*> &chain
)
248 if (GetSize(chain
) < 2)
252 while (cursor
< GetSize(chain
))
254 int cases
= GetSize(chain
) - cursor
;
256 Cell
*first_cell
= chain
[cursor
];
257 dict
<int, SigBit
> taps_dict
;
264 Cell
*last_cell
= chain
[cursor
+cases
-1];
266 log("Converting %s.%s ... %s.%s to a pmux with %d cases.\n",
267 log_id(module
), log_id(first_cell
), log_id(module
), log_id(last_cell
), cases
);
272 first_cell
->type
= ID($pmux
);
273 SigSpec b_sig
= first_cell
->getPort(ID::B
);
274 SigSpec s_sig
= first_cell
->getPort(ID::S
);
276 for (int i
= 1; i
< cases
; i
++) {
277 Cell
* prev_cell
= chain
[cursor
+i
-1];
278 Cell
* cursor_cell
= chain
[cursor
+i
];
279 if (sigmap(prev_cell
->getPort(ID::Y
)) == sigmap(cursor_cell
->getPort(ID::A
))) {
280 b_sig
.append(cursor_cell
->getPort(ID::B
));
281 s_sig
.append(cursor_cell
->getPort(ID::S
));
284 log_assert(cursor_cell
->type
== ID($mux
));
285 b_sig
.append(cursor_cell
->getPort(ID::A
));
286 s_sig
.append(module
->LogicNot(NEW_ID
, cursor_cell
->getPort(ID::S
)));
288 remove_cells
.insert(cursor_cell
);
291 first_cell
->setPort(ID::B
, b_sig
);
292 first_cell
->setPort(ID::S
, s_sig
);
293 first_cell
->setParam(ID::S_WIDTH
, GetSize(s_sig
));
294 first_cell
->setPort(ID::Y
, last_cell
->getPort(ID::Y
));
302 for (auto cell
: remove_cells
)
303 module
->remove(cell
);
305 remove_cells
.clear();
306 sig_chain_next
.clear();
307 sig_chain_prev
.clear();
308 chain_start_cells
.clear();
309 candidate_cells
.clear();
312 MuxpackWorker(Module
*module
) :
313 module(module
), sigmap(module
), mux_count(0), pmux_count(0), excl_db(module
, sigmap
)
315 make_sig_chain_next_prev();
316 find_chain_start_cells();
318 for (auto c
: chain_start_cells
) {
319 vector
<Cell
*> chain
= create_chain(c
);
320 process_chain(chain
);
327 struct MuxpackPass
: public Pass
{
328 MuxpackPass() : Pass("muxpack", "$mux/$pmux cascades to $pmux") { }
331 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
333 log(" muxpack [selection]\n");
335 log("This pass converts cascaded chains of $pmux cells (e.g. those create from case\n");
336 log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n");
337 log("$pmux cells.\n");
339 log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n");
340 log("whose select lines are driven by '$eq' cells with other such cells if it can be\n");
341 log("certain that their select inputs are mutually exclusive.\n");
344 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) override
346 log_header(design
, "Executing MUXPACK pass ($mux cell cascades to $pmux).\n");
349 for (argidx
= 1; argidx
< args
.size(); argidx
++)
353 extra_args(args
, argidx
, design
);
358 for (auto module
: design
->selected_modules()) {
359 MuxpackWorker
worker(module
);
360 mux_count
+= worker
.mux_count
;
361 pmux_count
+= worker
.pmux_count
;
364 log("Converted %d (p)mux cells into %d pmux cells.\n", mux_count
, pmux_count
);
368 PRIVATE_NAMESPACE_END