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/sigtools.h"
22 #include "kernel/log.h"
23 #include "kernel/celltypes.h"
29 PRIVATE_NAMESPACE_BEGIN
33 struct OptMuxtreeWorker
35 RTLIL::Design
*design
;
36 RTLIL::Module
*module
;
39 int glob_abort_cnt
= 100000;
44 pool
<int> mux_drivers
;
47 idict
<SigBit
> bit2num
;
48 vector
<bitinfo_t
> bit2info
;
53 pool
<int> input_muxes
;
55 bool const_deactivated
;
61 vector
<portinfo_t
> ports
;
64 vector
<muxinfo_t
> mux2info
;
65 vector
<bool> root_muxes
;
66 vector
<bool> root_enable_muxes
;
67 pool
<int> root_mux_rerun
;
69 OptMuxtreeWorker(RTLIL::Design
*design
, RTLIL::Module
*module
) :
70 design(design
), module(module
), assign_map(module
), removed_count(0)
72 log("Running muxtree optimizer on module %s..\n", module
->name
.c_str());
74 log(" Creating internal representation of mux trees.\n");
76 // Populate bit2info[]:
80 // Populate mux2info[].ports[]:
85 for (auto cell
: module
->cells())
87 if (cell
->type
== "$mux" || cell
->type
== "$pmux")
89 RTLIL::SigSpec sig_a
= cell
->getPort("\\A");
90 RTLIL::SigSpec sig_b
= cell
->getPort("\\B");
91 RTLIL::SigSpec sig_s
= cell
->getPort("\\S");
92 RTLIL::SigSpec sig_y
= cell
->getPort("\\Y");
97 for (int i
= 0; i
< GetSize(sig_s
); i
++) {
98 RTLIL::SigSpec sig
= sig_b
.extract(i
*GetSize(sig_a
), GetSize(sig_a
));
99 RTLIL::SigSpec ctrl_sig
= assign_map(sig_s
.extract(i
, 1));
101 portinfo
.ctrl_sig
= sig2bits(ctrl_sig
, false).front();
102 for (int idx
: sig2bits(sig
)) {
103 bit2info
[idx
].mux_users
.insert(GetSize(mux2info
));
104 portinfo
.input_sigs
.insert(idx
);
106 portinfo
.const_activated
= ctrl_sig
.is_fully_const() && ctrl_sig
.as_bool();
107 portinfo
.const_deactivated
= ctrl_sig
.is_fully_const() && !ctrl_sig
.as_bool();
108 portinfo
.enabled
= false;
109 muxinfo
.ports
.push_back(portinfo
);
113 for (int idx
: sig2bits(sig_a
)) {
114 bit2info
[idx
].mux_users
.insert(GetSize(mux2info
));
115 portinfo
.input_sigs
.insert(idx
);
117 portinfo
.ctrl_sig
= -1;
118 portinfo
.const_activated
= false;
119 portinfo
.const_deactivated
= false;
120 portinfo
.enabled
= false;
121 muxinfo
.ports
.push_back(portinfo
);
123 for (int idx
: sig2bits(sig_y
))
124 bit2info
[idx
].mux_drivers
.insert(GetSize(mux2info
));
126 for (int idx
: sig2bits(sig_s
))
127 bit2info
[idx
].seen_non_mux
= true;
129 mux2info
.push_back(muxinfo
);
133 for (auto &it
: cell
->connections()) {
134 for (int idx
: sig2bits(it
.second
))
135 bit2info
[idx
].seen_non_mux
= true;
139 for (auto wire
: module
->wires()) {
140 if (wire
->port_output
|| wire
->get_bool_attribute("\\keep"))
141 for (int idx
: sig2bits(RTLIL::SigSpec(wire
)))
142 bit2info
[idx
].seen_non_mux
= true;
145 if (mux2info
.empty()) {
146 log(" No muxes found in this module.\n");
150 // Populate mux2info[].ports[]:
152 for (int i
= 0; i
< GetSize(bit2info
); i
++)
153 for (int j
: bit2info
[i
].mux_users
)
154 for (auto &p
: mux2info
[j
].ports
) {
155 if (p
.input_sigs
.count(i
))
156 for (int k
: bit2info
[i
].mux_drivers
)
157 p
.input_muxes
.insert(k
);
160 log(" Evaluating internal representation of mux trees.\n");
162 dict
<int, pool
<int>> mux_to_users
;
163 root_muxes
.resize(GetSize(mux2info
));
164 root_enable_muxes
.resize(GetSize(mux2info
));
166 for (auto &bi
: bit2info
) {
167 for (int i
: bi
.mux_drivers
)
168 for (int j
: bi
.mux_users
)
169 mux_to_users
[i
].insert(j
);
170 if (!bi
.seen_non_mux
)
172 for (int mux_idx
: bi
.mux_drivers
) {
173 root_muxes
.at(mux_idx
) = true;
174 root_enable_muxes
.at(mux_idx
) = true;
178 for (auto &it
: mux_to_users
)
179 if (GetSize(it
.second
) > 1)
180 root_muxes
.at(it
.first
) = true;
182 for (int mux_idx
= 0; mux_idx
< GetSize(root_muxes
); mux_idx
++)
183 if (root_muxes
.at(mux_idx
)) {
184 log(" Root of a mux tree: %s%s\n", log_id(mux2info
[mux_idx
].cell
), root_enable_muxes
.at(mux_idx
) ? " (pure)" : "");
185 root_mux_rerun
.erase(mux_idx
);
186 eval_root_mux(mux_idx
);
189 while (!root_mux_rerun
.empty()) {
190 int mux_idx
= *root_mux_rerun
.begin();
191 log(" Root of a mux tree: %s (rerun as non-pure)\n", log_id(mux2info
[mux_idx
].cell
));
192 log_assert(root_enable_muxes
.at(mux_idx
));
193 root_mux_rerun
.erase(mux_idx
);
194 eval_root_mux(mux_idx
);
197 log(" Analyzing evaluation results.\n");
199 for (auto &mi
: mux2info
)
201 vector
<int> live_ports
;
202 for (int port_idx
= 0; port_idx
< GetSize(mi
.ports
); port_idx
++) {
203 portinfo_t
&pi
= mi
.ports
[port_idx
];
205 live_ports
.push_back(port_idx
);
207 log(" dead port %d/%d on %s %s.\n", port_idx
+1, GetSize(mi
.ports
),
208 mi
.cell
->type
.c_str(), mi
.cell
->name
.c_str());
213 if (GetSize(live_ports
) == GetSize(mi
.ports
))
216 if (live_ports
.empty()) {
217 module
->remove(mi
.cell
);
221 RTLIL::SigSpec sig_a
= mi
.cell
->getPort("\\A");
222 RTLIL::SigSpec sig_b
= mi
.cell
->getPort("\\B");
223 RTLIL::SigSpec sig_s
= mi
.cell
->getPort("\\S");
224 RTLIL::SigSpec sig_y
= mi
.cell
->getPort("\\Y");
226 RTLIL::SigSpec sig_ports
= sig_b
;
227 sig_ports
.append(sig_a
);
229 if (GetSize(live_ports
) == 1)
231 RTLIL::SigSpec sig_in
= sig_ports
.extract(live_ports
[0]*GetSize(sig_a
), GetSize(sig_a
));
232 module
->connect(RTLIL::SigSig(sig_y
, sig_in
));
233 module
->remove(mi
.cell
);
237 RTLIL::SigSpec new_sig_a
, new_sig_b
, new_sig_s
;
239 for (int i
= 0; i
< GetSize(live_ports
); i
++) {
240 RTLIL::SigSpec sig_in
= sig_ports
.extract(live_ports
[i
]*GetSize(sig_a
), GetSize(sig_a
));
241 if (i
== GetSize(live_ports
)-1) {
244 new_sig_b
.append(sig_in
);
245 new_sig_s
.append(sig_s
.extract(live_ports
[i
], 1));
249 mi
.cell
->setPort("\\A", new_sig_a
);
250 mi
.cell
->setPort("\\B", new_sig_b
);
251 mi
.cell
->setPort("\\S", new_sig_s
);
252 if (GetSize(new_sig_s
) == 1) {
253 mi
.cell
->type
= "$mux";
254 mi
.cell
->parameters
.erase("\\S_WIDTH");
256 mi
.cell
->parameters
["\\S_WIDTH"] = RTLIL::Const(GetSize(new_sig_s
));
262 vector
<int> sig2bits(RTLIL::SigSpec sig
, bool skip_non_wires
= true)
265 assign_map
.apply(sig
);
266 for (auto &bit
: sig
)
267 if (bit
.wire
!= NULL
) {
268 if (bit2num
.count(bit
) == 0) {
270 info
.seen_non_mux
= false;
271 bit2num
.expect(bit
, GetSize(bit2info
));
272 bit2info
.push_back(info
);
274 results
.push_back(bit2num
.at(bit
));
275 } else if (!skip_non_wires
)
276 results
.push_back(-1);
282 // database of known inactive signals
283 // the payload is a reference counter used to manage the
284 // list. when it is non-zero the signal in known to be inactive
285 vector
<int> known_inactive
;
287 // database of known active signals
288 vector
<int> known_active
;
290 // this is just used to keep track of visited muxes in order to prohibit
291 // endless recursion in mux loops
292 vector
<bool> visited_muxes
;
295 void eval_mux_port(knowledge_t
&knowledge
, int mux_idx
, int port_idx
, bool do_replace_known
, bool do_enable_ports
, int abort_count
)
297 if (glob_abort_cnt
== 0)
300 muxinfo_t
&muxinfo
= mux2info
[mux_idx
];
303 muxinfo
.ports
[port_idx
].enabled
= true;
305 for (int i
= 0; i
< GetSize(muxinfo
.ports
); i
++) {
308 if (muxinfo
.ports
[i
].ctrl_sig
>= 0)
309 knowledge
.known_inactive
.at(muxinfo
.ports
[i
].ctrl_sig
)++;
312 if (port_idx
< GetSize(muxinfo
.ports
)-1 && !muxinfo
.ports
[port_idx
].const_activated
)
313 knowledge
.known_active
.at(muxinfo
.ports
[port_idx
].ctrl_sig
)++;
315 vector
<int> parent_muxes
;
316 for (int m
: muxinfo
.ports
[port_idx
].input_muxes
) {
317 if (knowledge
.visited_muxes
[m
])
319 knowledge
.visited_muxes
[m
] = true;
320 parent_muxes
.push_back(m
);
322 for (int m
: parent_muxes
) {
323 if (root_enable_muxes
.at(m
))
325 else if (root_muxes
.at(m
)) {
326 if (abort_count
== 0) {
327 root_mux_rerun
.insert(m
);
328 root_enable_muxes
.at(m
) = true;
329 log(" Removing pure flag from root mux %s.\n", log_id(mux2info
[m
].cell
));
331 eval_mux(knowledge
, m
, false, do_enable_ports
, abort_count
- 1);
333 eval_mux(knowledge
, m
, do_replace_known
, do_enable_ports
, abort_count
);
334 if (glob_abort_cnt
== 0)
337 for (int m
: parent_muxes
)
338 knowledge
.visited_muxes
[m
] = false;
340 if (port_idx
< GetSize(muxinfo
.ports
)-1 && !muxinfo
.ports
[port_idx
].const_activated
)
341 knowledge
.known_active
.at(muxinfo
.ports
[port_idx
].ctrl_sig
)--;
343 for (int i
= 0; i
< GetSize(muxinfo
.ports
); i
++) {
346 if (muxinfo
.ports
[i
].ctrl_sig
>= 0)
347 knowledge
.known_inactive
.at(muxinfo
.ports
[i
].ctrl_sig
)--;
351 void replace_known(knowledge_t
&knowledge
, muxinfo_t
&muxinfo
, IdString portname
)
353 SigSpec sig
= muxinfo
.cell
->getPort(portname
);
354 bool did_something
= false;
357 idict
<int> ctrl_bits
;
358 if (portname
== "\\B")
359 width
= GetSize(muxinfo
.cell
->getPort("\\A"));
360 for (int bit
: sig2bits(muxinfo
.cell
->getPort("\\S"), false))
363 int port_idx
= 0, port_off
= 0;
364 vector
<int> bits
= sig2bits(sig
, false);
365 for (int i
= 0; i
< GetSize(bits
); i
++) {
368 if (knowledge
.known_inactive
.at(bits
[i
])) {
370 did_something
= true;
372 if (knowledge
.known_active
.at(bits
[i
])) {
374 did_something
= true;
377 if (ctrl_bits
.count(bits
[i
])) {
378 sig
[i
] = ctrl_bits
.at(bits
[i
]) == port_idx
? State::S1
: State::S0
;
379 did_something
= true;
381 if (++port_off
== width
)
382 port_idx
++, port_off
=0;
384 if (ctrl_bits
.count(bits
[i
])) {
386 did_something
= true;
392 log(" Replacing known input bits on port %s of cell %s: %s -> %s\n", log_id(portname
),
393 log_id(muxinfo
.cell
), log_signal(muxinfo
.cell
->getPort(portname
)), log_signal(sig
));
394 muxinfo
.cell
->setPort(portname
, sig
);
398 void eval_mux(knowledge_t
&knowledge
, int mux_idx
, bool do_replace_known
, bool do_enable_ports
, int abort_count
)
400 if (glob_abort_cnt
== 0) {
401 log(" Giving up (too many iterations)\n");
406 muxinfo_t
&muxinfo
= mux2info
[mux_idx
];
408 // set input ports to constants if we find known active or inactive signals
409 if (do_replace_known
) {
410 replace_known(knowledge
, muxinfo
, "\\A");
411 replace_known(knowledge
, muxinfo
, "\\B");
414 // if there is a constant activated port we just use it
415 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
); port_idx
++)
417 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
418 if (portinfo
.const_activated
) {
419 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
424 // compare ports with known_active signals. if we find a match, only this
425 // port can be active. do not include the last port (its the default port
426 // that has no control signals).
427 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
)-1; port_idx
++)
429 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
430 if (portinfo
.const_deactivated
)
432 if (knowledge
.known_active
.at(portinfo
.ctrl_sig
)) {
433 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
438 // eval all ports that could be activated (control signal is not in
439 // known_inactive or const_deactivated).
440 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
); port_idx
++)
442 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
443 if (portinfo
.const_deactivated
)
445 if (port_idx
< GetSize(muxinfo
.ports
)-1)
446 if (knowledge
.known_inactive
.at(portinfo
.ctrl_sig
))
448 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
450 if (glob_abort_cnt
== 0)
455 void eval_root_mux(int mux_idx
)
457 knowledge_t knowledge
;
458 knowledge
.known_inactive
.resize(GetSize(bit2info
));
459 knowledge
.known_active
.resize(GetSize(bit2info
));
460 knowledge
.visited_muxes
.resize(GetSize(mux2info
));
461 knowledge
.visited_muxes
[mux_idx
] = true;
462 eval_mux(knowledge
, mux_idx
, true, root_enable_muxes
.at(mux_idx
), 3);
466 struct OptMuxtreePass
: public Pass
{
467 OptMuxtreePass() : Pass("opt_muxtree", "eliminate dead trees in multiplexer trees") { }
468 void help() YS_OVERRIDE
470 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
472 log(" opt_muxtree [selection]\n");
474 log("This pass analyzes the control signals for the multiplexer trees in the design\n");
475 log("and identifies inputs that can never be active. It then removes this dead\n");
476 log("branches from the multiplexer trees.\n");
478 log("This pass only operates on completely selected modules without processes.\n");
481 void execute(vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
483 log_header(design
, "Executing OPT_MUXTREE pass (detect dead branches in mux trees).\n");
484 extra_args(args
, 1, design
);
487 for (auto module
: design
->selected_whole_modules_warn()) {
488 if (module
->has_processes_warn())
490 OptMuxtreeWorker
worker(design
, module
);
491 total_count
+= worker
.removed_count
;
494 design
->scratchpad_set_bool("opt.did_something", true);
495 log("Removed %d multiplexer ports.\n", total_count
);
499 PRIVATE_NAMESPACE_END