projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Merge pull request #985 from YosysHQ/clifford/fix981
[yosys.git] / passes / opt / opt_muxtree.cc
1 /*
2 * yosys -- Yosys Open SYnthesis Suite
3 *
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 *
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.
9 *
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.
17 *
18 */
19
20 #include "kernel/register.h"
21 #include "kernel/sigtools.h"
22 #include "kernel/log.h"
23 #include "kernel/celltypes.h"
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <set>
27
28 USING_YOSYS_NAMESPACE
29 PRIVATE_NAMESPACE_BEGIN
30
31 using RTLIL::id2cstr;
32
33 struct OptMuxtreeWorker
34 {
35 RTLIL::Design *design;
36 RTLIL::Module *module;
37 SigMap assign_map;
38 int removed_count;
39 int glob_abort_cnt = 100000;
40
41 struct bitinfo_t {
42 bool seen_non_mux;
43 pool<int> mux_users;
44 pool<int> mux_drivers;
45 };
46
47 idict<SigBit> bit2num;
48 vector<bitinfo_t> bit2info;
49
50 struct portinfo_t {
51 int ctrl_sig;
52 pool<int> input_sigs;
53 pool<int> input_muxes;
54 bool const_activated;
55 bool const_deactivated;
56 bool enabled;
57 };
58
59 struct muxinfo_t {
60 RTLIL::Cell *cell;
61 vector<portinfo_t> ports;
62 };
63
64 vector<muxinfo_t> mux2info;
65 vector<bool> root_muxes;
66 vector<bool> root_enable_muxes;
67 pool<int> root_mux_rerun;
68
69 OptMuxtreeWorker(RTLIL::Design *design, RTLIL::Module *module) :
70 design(design), module(module), assign_map(module), removed_count(0)
71 {
72 log("Running muxtree optimizer on module %s..\n", module->name.c_str());
73
74 log(" Creating internal representation of mux trees.\n");
75
76 // Populate bit2info[]:
77 // .seen_non_mux
78 // .mux_users
79 // .mux_drivers
80 // Populate mux2info[].ports[]:
81 // .ctrl_sig
82 // .input_sigs
83 // .const_activated
84 // .const_deactivated
85 for (auto cell : module->cells())
86 {
87 if (cell->type == "$mux" || cell->type == "$pmux")
88 {
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");
93
94 muxinfo_t muxinfo;
95 muxinfo.cell = cell;
96
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));
100 portinfo_t portinfo;
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);
105 }
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);
110 }
111
112 portinfo_t portinfo;
113 for (int idx : sig2bits(sig_a)) {
114 bit2info[idx].mux_users.insert(GetSize(mux2info));
115 portinfo.input_sigs.insert(idx);
116 }
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);
122
123 for (int idx : sig2bits(sig_y))
124 bit2info[idx].mux_drivers.insert(GetSize(mux2info));
125
126 for (int idx : sig2bits(sig_s))
127 bit2info[idx].seen_non_mux = true;
128
129 mux2info.push_back(muxinfo);
130 }
131 else
132 {
133 for (auto &it : cell->connections()) {
134 for (int idx : sig2bits(it.second))
135 bit2info[idx].seen_non_mux = true;
136 }
137 }
138 }
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;
143 }
144
145 if (mux2info.empty()) {
146 log(" No muxes found in this module.\n");
147 return;
148 }
149
150 // Populate mux2info[].ports[]:
151 // .input_muxes
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);
158 }
159
160 log(" Evaluating internal representation of mux trees.\n");
161
162 dict<int, pool<int>> mux_to_users;
163 root_muxes.resize(GetSize(mux2info));
164 root_enable_muxes.resize(GetSize(mux2info));
165
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)
171 continue;
172 for (int mux_idx : bi.mux_drivers) {
173 root_muxes.at(mux_idx) = true;
174 root_enable_muxes.at(mux_idx) = true;
175 }
176 }
177
178 for (auto &it : mux_to_users)
179 if (GetSize(it.second) > 1)
180 root_muxes.at(it.first) = true;
181
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 }
188
189 while (!root_mux_rerun.empty()) {
190 int mux_idx = *root_mux_rerun.begin();
191 log_debug(" 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);
195 }
196
197 log(" Analyzing evaluation results.\n");
198
199 for (auto &mi : mux2info)
200 {
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];
204 if (pi.enabled) {
205 live_ports.push_back(port_idx);
206 } else {
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());
209 removed_count++;
210 }
211 }
212
213 if (GetSize(live_ports) == GetSize(mi.ports))
214 continue;
215
216 if (live_ports.empty()) {
217 module->remove(mi.cell);
218 continue;
219 }
220
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");
225
226 RTLIL::SigSpec sig_ports = sig_b;
227 sig_ports.append(sig_a);
228
229 if (GetSize(live_ports) == 1)
230 {
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);
234 }
235 else
236 {
237 RTLIL::SigSpec new_sig_a, new_sig_b, new_sig_s;
238
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) {
242 new_sig_a = sig_in;
243 } else {
244 new_sig_b.append(sig_in);
245 new_sig_s.append(sig_s.extract(live_ports[i], 1));
246 }
247 }
248
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");
255 } else {
256 mi.cell->parameters["\\S_WIDTH"] = RTLIL::Const(GetSize(new_sig_s));
257 }
258 }
259 }
260 }
261
262 vector<int> sig2bits(RTLIL::SigSpec sig, bool skip_non_wires = true)
263 {
264 vector<int> results;
265 assign_map.apply(sig);
266 for (auto &bit : sig)
267 if (bit.wire != NULL) {
268 if (bit2num.count(bit) == 0) {
269 bitinfo_t info;
270 info.seen_non_mux = false;
271 bit2num.expect(bit, GetSize(bit2info));
272 bit2info.push_back(info);
273 }
274 results.push_back(bit2num.at(bit));
275 } else if (!skip_non_wires)
276 results.push_back(-1);
277 return results;
278 }
279
280 struct knowledge_t
281 {
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;
286
287 // database of known active signals
288 vector<int> known_active;
289
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;
293 };
294
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)
296 {
297 if (glob_abort_cnt == 0)
298 return;
299
300 muxinfo_t &muxinfo = mux2info[mux_idx];
301
302 if (do_enable_ports)
303 muxinfo.ports[port_idx].enabled = true;
304
305 for (int i = 0; i < GetSize(muxinfo.ports); i++) {
306 if (i == port_idx)
307 continue;
308 if (muxinfo.ports[i].ctrl_sig >= 0)
309 knowledge.known_inactive.at(muxinfo.ports[i].ctrl_sig)++;
310 }
311
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)++;
314
315 vector<int> parent_muxes;
316 for (int m : muxinfo.ports[port_idx].input_muxes) {
317 if (knowledge.visited_muxes[m])
318 continue;
319 knowledge.visited_muxes[m] = true;
320 parent_muxes.push_back(m);
321 }
322 for (int m : parent_muxes) {
323 if (root_enable_muxes.at(m))
324 continue;
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_debug(" Removing pure flag from root mux %s.\n", log_id(mux2info[m].cell));
330 } else
331 eval_mux(knowledge, m, false, do_enable_ports, abort_count - 1);
332 } else
333 eval_mux(knowledge, m, do_replace_known, do_enable_ports, abort_count);
334 if (glob_abort_cnt == 0)
335 return;
336 }
337 for (int m : parent_muxes)
338 knowledge.visited_muxes[m] = false;
339
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)--;
342
343 for (int i = 0; i < GetSize(muxinfo.ports); i++) {
344 if (i == port_idx)
345 continue;
346 if (muxinfo.ports[i].ctrl_sig >= 0)
347 knowledge.known_inactive.at(muxinfo.ports[i].ctrl_sig)--;
348 }
349 }
350
351 void replace_known(knowledge_t &knowledge, muxinfo_t &muxinfo, IdString portname)
352 {
353 SigSpec sig = muxinfo.cell->getPort(portname);
354 bool did_something = false;
355
356 int width = 0;
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))
361 ctrl_bits(bit);
362
363 int port_idx = 0, port_off = 0;
364 vector<int> bits = sig2bits(sig, false);
365 for (int i = 0; i < GetSize(bits); i++) {
366 if (bits[i] < 0)
367 continue;
368 if (knowledge.known_inactive.at(bits[i])) {
369 sig[i] = State::S0;
370 did_something = true;
371 } else
372 if (knowledge.known_active.at(bits[i])) {
373 sig[i] = State::S1;
374 did_something = true;
375 }
376 if (width) {
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;
380 }
381 if (++port_off == width)
382 port_idx++, port_off=0;
383 } else {
384 if (ctrl_bits.count(bits[i])) {
385 sig[i] = State::S0;
386 did_something = true;
387 }
388 }
389 }
390
391 if (did_something) {
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);
395 }
396 }
397
398 void eval_mux(knowledge_t &knowledge, int mux_idx, bool do_replace_known, bool do_enable_ports, int abort_count)
399 {
400 if (glob_abort_cnt == 0) {
401 log(" Giving up (too many iterations)\n");
402 return;
403 }
404 glob_abort_cnt--;
405
406 muxinfo_t &muxinfo = mux2info[mux_idx];
407
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");
412 }
413
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++)
416 {
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);
420 return;
421 }
422 }
423
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++)
428 {
429 portinfo_t &portinfo = muxinfo.ports[port_idx];
430 if (portinfo.const_deactivated)
431 continue;
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);
434 return;
435 }
436 }
437
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++)
441 {
442 portinfo_t &portinfo = muxinfo.ports[port_idx];
443 if (portinfo.const_deactivated)
444 continue;
445 if (port_idx < GetSize(muxinfo.ports)-1)
446 if (knowledge.known_inactive.at(portinfo.ctrl_sig))
447 continue;
448 eval_mux_port(knowledge, mux_idx, port_idx, do_replace_known, do_enable_ports, abort_count);
449
450 if (glob_abort_cnt == 0)
451 return;
452 }
453 }
454
455 void eval_root_mux(int mux_idx)
456 {
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);
463 }
464 };
465
466 struct OptMuxtreePass : public Pass {
467 OptMuxtreePass() : Pass("opt_muxtree", "eliminate dead trees in multiplexer trees") { }
468 void help() YS_OVERRIDE
469 {
470 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
471 log("\n");
472 log(" opt_muxtree [selection]\n");
473 log("\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");
477 log("\n");
478 log("This pass only operates on completely selected modules without processes.\n");
479 log("\n");
480 }
481 void execute(vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
482 {
483 log_header(design, "Executing OPT_MUXTREE pass (detect dead branches in mux trees).\n");
484 extra_args(args, 1, design);
485
486 int total_count = 0;
487 for (auto module : design->selected_whole_modules_warn()) {
488 if (module->has_processes_warn())
489 continue;
490 OptMuxtreeWorker worker(design, module);
491 total_count += worker.removed_count;
492 }
493 if (total_count)
494 design->scratchpad_set_bool("opt.did_something", true);
495 log("Removed %d multiplexer ports.\n", total_count);
496 }
497 } OptMuxtreePass;
498
499 PRIVATE_NAMESPACE_END