projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Fix "tee" handling of log_streams
[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 if (glob_abort_cnt == 0) {
188 log(" Giving up (too many iterations)\n");
189 return;
190 }
191 }
192
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");
201 return;
202 }
203 }
204
205 log(" Analyzing evaluation results.\n");
206 log_assert(glob_abort_cnt > 0);
207
208 for (auto &mi : mux2info)
209 {
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];
213 if (pi.enabled) {
214 live_ports.push_back(port_idx);
215 } else {
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());
218 removed_count++;
219 }
220 }
221
222 if (GetSize(live_ports) == GetSize(mi.ports))
223 continue;
224
225 if (live_ports.empty()) {
226 module->remove(mi.cell);
227 continue;
228 }
229
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");
234
235 RTLIL::SigSpec sig_ports = sig_b;
236 sig_ports.append(sig_a);
237
238 if (GetSize(live_ports) == 1)
239 {
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);
243 }
244 else
245 {
246 RTLIL::SigSpec new_sig_a, new_sig_b, new_sig_s;
247
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) {
251 new_sig_a = sig_in;
252 } else {
253 new_sig_b.append(sig_in);
254 new_sig_s.append(sig_s.extract(live_ports[i], 1));
255 }
256 }
257
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");
264 } else {
265 mi.cell->parameters["\\S_WIDTH"] = RTLIL::Const(GetSize(new_sig_s));
266 }
267 }
268 }
269 }
270
271 vector<int> sig2bits(RTLIL::SigSpec sig, bool skip_non_wires = true)
272 {
273 vector<int> results;
274 assign_map.apply(sig);
275 for (auto &bit : sig)
276 if (bit.wire != NULL) {
277 if (bit2num.count(bit) == 0) {
278 bitinfo_t info;
279 info.seen_non_mux = false;
280 bit2num.expect(bit, GetSize(bit2info));
281 bit2info.push_back(info);
282 }
283 results.push_back(bit2num.at(bit));
284 } else if (!skip_non_wires)
285 results.push_back(-1);
286 return results;
287 }
288
289 struct knowledge_t
290 {
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;
295
296 // database of known active signals
297 vector<int> known_active;
298
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;
302 };
303
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)
305 {
306 if (glob_abort_cnt == 0)
307 return;
308
309 muxinfo_t &muxinfo = mux2info[mux_idx];
310
311 if (do_enable_ports)
312 muxinfo.ports[port_idx].enabled = true;
313
314 for (int i = 0; i < GetSize(muxinfo.ports); i++) {
315 if (i == port_idx)
316 continue;
317 if (muxinfo.ports[i].ctrl_sig >= 0)
318 knowledge.known_inactive.at(muxinfo.ports[i].ctrl_sig)++;
319 }
320
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)++;
323
324 vector<int> parent_muxes;
325 for (int m : muxinfo.ports[port_idx].input_muxes) {
326 if (knowledge.visited_muxes[m])
327 continue;
328 knowledge.visited_muxes[m] = true;
329 parent_muxes.push_back(m);
330 }
331 for (int m : parent_muxes) {
332 if (root_enable_muxes.at(m))
333 continue;
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));
339 } else
340 eval_mux(knowledge, m, false, do_enable_ports, abort_count - 1);
341 } else
342 eval_mux(knowledge, m, do_replace_known, do_enable_ports, abort_count);
343 if (glob_abort_cnt == 0)
344 return;
345 }
346 for (int m : parent_muxes)
347 knowledge.visited_muxes[m] = false;
348
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)--;
351
352 for (int i = 0; i < GetSize(muxinfo.ports); i++) {
353 if (i == port_idx)
354 continue;
355 if (muxinfo.ports[i].ctrl_sig >= 0)
356 knowledge.known_inactive.at(muxinfo.ports[i].ctrl_sig)--;
357 }
358 }
359
360 void replace_known(knowledge_t &knowledge, muxinfo_t &muxinfo, IdString portname)
361 {
362 SigSpec sig = muxinfo.cell->getPort(portname);
363 bool did_something = false;
364
365 int width = 0;
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))
370 ctrl_bits(bit);
371
372 int port_idx = 0, port_off = 0;
373 vector<int> bits = sig2bits(sig, false);
374 for (int i = 0; i < GetSize(bits); i++) {
375 if (bits[i] < 0)
376 continue;
377 if (knowledge.known_inactive.at(bits[i])) {
378 sig[i] = State::S0;
379 did_something = true;
380 } else
381 if (knowledge.known_active.at(bits[i])) {
382 sig[i] = State::S1;
383 did_something = true;
384 }
385 if (width) {
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;
389 }
390 if (++port_off == width)
391 port_idx++, port_off=0;
392 } else {
393 if (ctrl_bits.count(bits[i])) {
394 sig[i] = State::S0;
395 did_something = true;
396 }
397 }
398 }
399
400 if (did_something) {
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);
404 }
405 }
406
407 void eval_mux(knowledge_t &knowledge, int mux_idx, bool do_replace_known, bool do_enable_ports, int abort_count)
408 {
409 if (glob_abort_cnt == 0)
410 return;
411 glob_abort_cnt--;
412
413 muxinfo_t &muxinfo = mux2info[mux_idx];
414
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");
419 }
420
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++)
423 {
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);
427 return;
428 }
429 }
430
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++)
435 {
436 portinfo_t &portinfo = muxinfo.ports[port_idx];
437 if (portinfo.const_deactivated)
438 continue;
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);
441 return;
442 }
443 }
444
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++)
448 {
449 portinfo_t &portinfo = muxinfo.ports[port_idx];
450 if (portinfo.const_deactivated)
451 continue;
452 if (port_idx < GetSize(muxinfo.ports)-1)
453 if (knowledge.known_inactive.at(portinfo.ctrl_sig))
454 continue;
455 eval_mux_port(knowledge, mux_idx, port_idx, do_replace_known, do_enable_ports, abort_count);
456
457 if (glob_abort_cnt == 0)
458 return;
459 }
460 }
461
462 void eval_root_mux(int mux_idx)
463 {
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);
471 }
472 };
473
474 struct OptMuxtreePass : public Pass {
475 OptMuxtreePass() : Pass("opt_muxtree", "eliminate dead trees in multiplexer trees") { }
476 void help() YS_OVERRIDE
477 {
478 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
479 log("\n");
480 log(" opt_muxtree [selection]\n");
481 log("\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");
485 log("\n");
486 log("This pass only operates on completely selected modules without processes.\n");
487 log("\n");
488 }
489 void execute(vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
490 {
491 log_header(design, "Executing OPT_MUXTREE pass (detect dead branches in mux trees).\n");
492 extra_args(args, 1, design);
493
494 int total_count = 0;
495 for (auto module : design->selected_whole_modules_warn()) {
496 if (module->has_processes_warn())
497 continue;
498 OptMuxtreeWorker worker(design, module);
499 total_count += worker.removed_count;
500 }
501 if (total_count)
502 design->scratchpad_set_bool("opt.did_something", true);
503 log("Removed %d multiplexer ports.\n", total_count);
504 }
505 } OptMuxtreePass;
506
507 PRIVATE_NAMESPACE_END