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_debug(" 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
);
187 if (glob_abort_cnt
== 0) {
188 log(" Giving up (too many iterations)\n");
193 while (!root_mux_rerun
.empty()) {
194 int mux_idx
= *root_mux_rerun
.begin();
195 log_debug(" Root of a mux tree: %s (rerun as non-pure)\n", log_id(mux2info
[mux_idx
].cell
));
196 log_assert(root_enable_muxes
.at(mux_idx
));
197 root_mux_rerun
.erase(mux_idx
);
198 eval_root_mux(mux_idx
);
199 if (glob_abort_cnt
== 0) {
200 log(" Giving up (too many iterations)\n");
205 log(" Analyzing evaluation results.\n");
206 log_assert(glob_abort_cnt
> 0);
208 for (auto &mi
: mux2info
)
210 vector
<int> live_ports
;
211 for (int port_idx
= 0; port_idx
< GetSize(mi
.ports
); port_idx
++) {
212 portinfo_t
&pi
= mi
.ports
[port_idx
];
214 live_ports
.push_back(port_idx
);
216 log(" dead port %d/%d on %s %s.\n", port_idx
+1, GetSize(mi
.ports
),
217 mi
.cell
->type
.c_str(), mi
.cell
->name
.c_str());
222 if (GetSize(live_ports
) == GetSize(mi
.ports
))
225 if (live_ports
.empty()) {
226 module
->remove(mi
.cell
);
230 RTLIL::SigSpec sig_a
= mi
.cell
->getPort("\\A");
231 RTLIL::SigSpec sig_b
= mi
.cell
->getPort("\\B");
232 RTLIL::SigSpec sig_s
= mi
.cell
->getPort("\\S");
233 RTLIL::SigSpec sig_y
= mi
.cell
->getPort("\\Y");
235 RTLIL::SigSpec sig_ports
= sig_b
;
236 sig_ports
.append(sig_a
);
238 if (GetSize(live_ports
) == 1)
240 RTLIL::SigSpec sig_in
= sig_ports
.extract(live_ports
[0]*GetSize(sig_a
), GetSize(sig_a
));
241 module
->connect(RTLIL::SigSig(sig_y
, sig_in
));
242 module
->remove(mi
.cell
);
246 RTLIL::SigSpec new_sig_a
, new_sig_b
, new_sig_s
;
248 for (int i
= 0; i
< GetSize(live_ports
); i
++) {
249 RTLIL::SigSpec sig_in
= sig_ports
.extract(live_ports
[i
]*GetSize(sig_a
), GetSize(sig_a
));
250 if (i
== GetSize(live_ports
)-1) {
253 new_sig_b
.append(sig_in
);
254 new_sig_s
.append(sig_s
.extract(live_ports
[i
], 1));
258 mi
.cell
->setPort("\\A", new_sig_a
);
259 mi
.cell
->setPort("\\B", new_sig_b
);
260 mi
.cell
->setPort("\\S", new_sig_s
);
261 if (GetSize(new_sig_s
) == 1) {
262 mi
.cell
->type
= "$mux";
263 mi
.cell
->parameters
.erase("\\S_WIDTH");
265 mi
.cell
->parameters
["\\S_WIDTH"] = RTLIL::Const(GetSize(new_sig_s
));
271 vector
<int> sig2bits(RTLIL::SigSpec sig
, bool skip_non_wires
= true)
274 assign_map
.apply(sig
);
275 for (auto &bit
: sig
)
276 if (bit
.wire
!= NULL
) {
277 if (bit2num
.count(bit
) == 0) {
279 info
.seen_non_mux
= false;
280 bit2num
.expect(bit
, GetSize(bit2info
));
281 bit2info
.push_back(info
);
283 results
.push_back(bit2num
.at(bit
));
284 } else if (!skip_non_wires
)
285 results
.push_back(-1);
291 // database of known inactive signals
292 // the payload is a reference counter used to manage the
293 // list. when it is non-zero the signal in known to be inactive
294 vector
<int> known_inactive
;
296 // database of known active signals
297 vector
<int> known_active
;
299 // this is just used to keep track of visited muxes in order to prohibit
300 // endless recursion in mux loops
301 vector
<bool> visited_muxes
;
304 void eval_mux_port(knowledge_t
&knowledge
, int mux_idx
, int port_idx
, bool do_replace_known
, bool do_enable_ports
, int abort_count
)
306 if (glob_abort_cnt
== 0)
309 muxinfo_t
&muxinfo
= mux2info
[mux_idx
];
312 muxinfo
.ports
[port_idx
].enabled
= true;
314 for (int i
= 0; i
< GetSize(muxinfo
.ports
); i
++) {
317 if (muxinfo
.ports
[i
].ctrl_sig
>= 0)
318 knowledge
.known_inactive
.at(muxinfo
.ports
[i
].ctrl_sig
)++;
321 if (port_idx
< GetSize(muxinfo
.ports
)-1 && !muxinfo
.ports
[port_idx
].const_activated
)
322 knowledge
.known_active
.at(muxinfo
.ports
[port_idx
].ctrl_sig
)++;
324 vector
<int> parent_muxes
;
325 for (int m
: muxinfo
.ports
[port_idx
].input_muxes
) {
326 if (knowledge
.visited_muxes
[m
])
328 knowledge
.visited_muxes
[m
] = true;
329 parent_muxes
.push_back(m
);
331 for (int m
: parent_muxes
) {
332 if (root_enable_muxes
.at(m
))
334 else if (root_muxes
.at(m
)) {
335 if (abort_count
== 0) {
336 root_mux_rerun
.insert(m
);
337 root_enable_muxes
.at(m
) = true;
338 log_debug(" Removing pure flag from root mux %s.\n", log_id(mux2info
[m
].cell
));
340 eval_mux(knowledge
, m
, false, do_enable_ports
, abort_count
- 1);
342 eval_mux(knowledge
, m
, do_replace_known
, do_enable_ports
, abort_count
);
343 if (glob_abort_cnt
== 0)
346 for (int m
: parent_muxes
)
347 knowledge
.visited_muxes
[m
] = false;
349 if (port_idx
< GetSize(muxinfo
.ports
)-1 && !muxinfo
.ports
[port_idx
].const_activated
)
350 knowledge
.known_active
.at(muxinfo
.ports
[port_idx
].ctrl_sig
)--;
352 for (int i
= 0; i
< GetSize(muxinfo
.ports
); i
++) {
355 if (muxinfo
.ports
[i
].ctrl_sig
>= 0)
356 knowledge
.known_inactive
.at(muxinfo
.ports
[i
].ctrl_sig
)--;
360 void replace_known(knowledge_t
&knowledge
, muxinfo_t
&muxinfo
, IdString portname
)
362 SigSpec sig
= muxinfo
.cell
->getPort(portname
);
363 bool did_something
= false;
366 idict
<int> ctrl_bits
;
367 if (portname
== "\\B")
368 width
= GetSize(muxinfo
.cell
->getPort("\\A"));
369 for (int bit
: sig2bits(muxinfo
.cell
->getPort("\\S"), false))
372 int port_idx
= 0, port_off
= 0;
373 vector
<int> bits
= sig2bits(sig
, false);
374 for (int i
= 0; i
< GetSize(bits
); i
++) {
377 if (knowledge
.known_inactive
.at(bits
[i
])) {
379 did_something
= true;
381 if (knowledge
.known_active
.at(bits
[i
])) {
383 did_something
= true;
386 if (ctrl_bits
.count(bits
[i
])) {
387 sig
[i
] = ctrl_bits
.at(bits
[i
]) == port_idx
? State::S1
: State::S0
;
388 did_something
= true;
390 if (++port_off
== width
)
391 port_idx
++, port_off
=0;
393 if (ctrl_bits
.count(bits
[i
])) {
395 did_something
= true;
401 log(" Replacing known input bits on port %s of cell %s: %s -> %s\n", log_id(portname
),
402 log_id(muxinfo
.cell
), log_signal(muxinfo
.cell
->getPort(portname
)), log_signal(sig
));
403 muxinfo
.cell
->setPort(portname
, sig
);
407 void eval_mux(knowledge_t
&knowledge
, int mux_idx
, bool do_replace_known
, bool do_enable_ports
, int abort_count
)
409 if (glob_abort_cnt
== 0)
413 muxinfo_t
&muxinfo
= mux2info
[mux_idx
];
415 // set input ports to constants if we find known active or inactive signals
416 if (do_replace_known
) {
417 replace_known(knowledge
, muxinfo
, "\\A");
418 replace_known(knowledge
, muxinfo
, "\\B");
421 // if there is a constant activated port we just use it
422 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
); port_idx
++)
424 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
425 if (portinfo
.const_activated
) {
426 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
431 // compare ports with known_active signals. if we find a match, only this
432 // port can be active. do not include the last port (its the default port
433 // that has no control signals).
434 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
)-1; port_idx
++)
436 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
437 if (portinfo
.const_deactivated
)
439 if (knowledge
.known_active
.at(portinfo
.ctrl_sig
)) {
440 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
445 // eval all ports that could be activated (control signal is not in
446 // known_inactive or const_deactivated).
447 for (int port_idx
= 0; port_idx
< GetSize(muxinfo
.ports
); port_idx
++)
449 portinfo_t
&portinfo
= muxinfo
.ports
[port_idx
];
450 if (portinfo
.const_deactivated
)
452 if (port_idx
< GetSize(muxinfo
.ports
)-1)
453 if (knowledge
.known_inactive
.at(portinfo
.ctrl_sig
))
455 eval_mux_port(knowledge
, mux_idx
, port_idx
, do_replace_known
, do_enable_ports
, abort_count
);
457 if (glob_abort_cnt
== 0)
462 void eval_root_mux(int mux_idx
)
464 log_assert(glob_abort_cnt
> 0);
465 knowledge_t knowledge
;
466 knowledge
.known_inactive
.resize(GetSize(bit2info
));
467 knowledge
.known_active
.resize(GetSize(bit2info
));
468 knowledge
.visited_muxes
.resize(GetSize(mux2info
));
469 knowledge
.visited_muxes
[mux_idx
] = true;
470 eval_mux(knowledge
, mux_idx
, true, root_enable_muxes
.at(mux_idx
), 3);
474 struct OptMuxtreePass
: public Pass
{
475 OptMuxtreePass() : Pass("opt_muxtree", "eliminate dead trees in multiplexer trees") { }
476 void help() YS_OVERRIDE
478 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
480 log(" opt_muxtree [selection]\n");
482 log("This pass analyzes the control signals for the multiplexer trees in the design\n");
483 log("and identifies inputs that can never be active. It then removes this dead\n");
484 log("branches from the multiplexer trees.\n");
486 log("This pass only operates on completely selected modules without processes.\n");
489 void execute(vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
491 log_header(design
, "Executing OPT_MUXTREE pass (detect dead branches in mux trees).\n");
492 extra_args(args
, 1, design
);
495 for (auto module
: design
->selected_whole_modules_warn()) {
496 if (module
->has_processes_warn())
498 OptMuxtreeWorker
worker(design
, module
);
499 total_count
+= worker
.removed_count
;
502 design
->scratchpad_set_bool("opt.did_something", true);
503 log("Removed %d multiplexer ports.\n", total_count
);
507 PRIVATE_NAMESPACE_END