Add "wreduce -keepdc", fixes #1016
[yosys.git] / passes / opt / opt_clean.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 keep_cache_t
34 {
35 Design *design;
36 dict<Module*, bool> cache;
37
38 void reset(Design *design = nullptr)
39 {
40 this->design = design;
41 cache.clear();
42 }
43
44 bool query(Module *module)
45 {
46 log_assert(design != nullptr);
47
48 if (module == nullptr)
49 return false;
50
51 if (cache.count(module))
52 return cache.at(module);
53
54 cache[module] = true;
55 if (!module->get_bool_attribute("\\keep")) {
56 bool found_keep = false;
57 for (auto cell : module->cells())
58 if (query(cell)) found_keep = true;
59 cache[module] = found_keep;
60 }
61
62 return cache[module];
63 }
64
65 bool query(Cell *cell)
66 {
67 if (cell->type.in("$memwr", "$meminit", "$assert", "$assume", "$live", "$fair", "$cover", "$specify2", "$specify3", "$specrule"))
68 return true;
69
70 if (cell->has_keep_attr())
71 return true;
72
73 if (cell->module && cell->module->design)
74 return query(cell->module->design->module(cell->type));
75
76 return false;
77 }
78 };
79
80 keep_cache_t keep_cache;
81 CellTypes ct_reg, ct_all;
82 int count_rm_cells, count_rm_wires;
83
84 void rmunused_module_cells(Module *module, bool verbose)
85 {
86 SigMap sigmap(module);
87 pool<Cell*> queue, unused;
88 pool<SigBit> used_raw_bits;
89 dict<SigBit, pool<Cell*>> wire2driver;
90 dict<SigBit, vector<string>> driver_driver_logs;
91
92 SigMap raw_sigmap;
93 for (auto &it : module->connections_) {
94 for (int i = 0; i < GetSize(it.second); i++) {
95 if (it.second[i].wire != nullptr)
96 raw_sigmap.add(it.first[i], it.second[i]);
97 }
98 }
99
100 for (auto &it : module->cells_) {
101 Cell *cell = it.second;
102 for (auto &it2 : cell->connections()) {
103 if (ct_all.cell_known(cell->type) && !ct_all.cell_output(cell->type, it2.first))
104 continue;
105 for (auto raw_bit : it2.second) {
106 if (raw_bit.wire == nullptr)
107 continue;
108 auto bit = sigmap(raw_bit);
109 if (bit.wire == nullptr)
110 driver_driver_logs[raw_sigmap(raw_bit)].push_back(stringf("Driver-driver conflict "
111 "for %s between cell %s.%s and constant %s in %s: Resolved using constant.",
112 log_signal(raw_bit), log_id(cell), log_id(it2.first), log_signal(bit), log_id(module)));
113 if (bit.wire != nullptr)
114 wire2driver[bit].insert(cell);
115 }
116 }
117 if (keep_cache.query(cell))
118 queue.insert(cell);
119 else
120 unused.insert(cell);
121 }
122
123 for (auto &it : module->wires_) {
124 Wire *wire = it.second;
125 if (wire->port_output || wire->get_bool_attribute("\\keep")) {
126 for (auto bit : sigmap(wire))
127 for (auto c : wire2driver[bit])
128 queue.insert(c), unused.erase(c);
129 for (auto raw_bit : SigSpec(wire))
130 used_raw_bits.insert(raw_sigmap(raw_bit));
131 }
132 }
133
134 while (!queue.empty())
135 {
136 pool<SigBit> bits;
137 for (auto cell : queue)
138 for (auto &it : cell->connections())
139 if (!ct_all.cell_known(cell->type) || ct_all.cell_input(cell->type, it.first))
140 for (auto bit : sigmap(it.second))
141 bits.insert(bit);
142
143 queue.clear();
144 for (auto bit : bits)
145 for (auto c : wire2driver[bit])
146 if (unused.count(c))
147 queue.insert(c), unused.erase(c);
148 }
149
150 unused.sort(RTLIL::sort_by_name_id<RTLIL::Cell>());
151
152 for (auto cell : unused) {
153 if (verbose)
154 log_debug(" removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str());
155 module->design->scratchpad_set_bool("opt.did_something", true);
156 module->remove(cell);
157 count_rm_cells++;
158 }
159
160 for (auto &it : module->cells_) {
161 Cell *cell = it.second;
162 for (auto &it2 : cell->connections()) {
163 if (ct_all.cell_known(cell->type) && !ct_all.cell_input(cell->type, it2.first))
164 continue;
165 for (auto raw_bit : raw_sigmap(it2.second))
166 used_raw_bits.insert(raw_bit);
167 }
168 }
169
170 for (auto it : driver_driver_logs) {
171 if (used_raw_bits.count(it.first))
172 for (auto msg : it.second)
173 log_warning("%s\n", msg.c_str());
174 }
175 }
176
177 int count_nontrivial_wire_attrs(RTLIL::Wire *w)
178 {
179 int count = w->attributes.size();
180 count -= w->attributes.count("\\src");
181 count -= w->attributes.count("\\unused_bits");
182 return count;
183 }
184
185 bool compare_signals(RTLIL::SigBit &s1, RTLIL::SigBit &s2, SigPool &regs, SigPool &conns, pool<RTLIL::Wire*> &direct_wires)
186 {
187 RTLIL::Wire *w1 = s1.wire;
188 RTLIL::Wire *w2 = s2.wire;
189
190 if (w1 == NULL || w2 == NULL)
191 return w2 == NULL;
192
193 if (w1->port_input != w2->port_input)
194 return w2->port_input;
195
196 if ((w1->port_input && w1->port_output) != (w2->port_input && w2->port_output))
197 return !(w2->port_input && w2->port_output);
198
199 if (w1->name[0] == '\\' && w2->name[0] == '\\') {
200 if (regs.check_any(s1) != regs.check_any(s2))
201 return regs.check_any(s2);
202 if (direct_wires.count(w1) != direct_wires.count(w2))
203 return direct_wires.count(w2) != 0;
204 if (conns.check_any(s1) != conns.check_any(s2))
205 return conns.check_any(s2);
206 }
207
208 if (w1->port_output != w2->port_output)
209 return w2->port_output;
210
211 if (w1->name[0] != w2->name[0])
212 return w2->name[0] == '\\';
213
214 int attrs1 = count_nontrivial_wire_attrs(w1);
215 int attrs2 = count_nontrivial_wire_attrs(w2);
216
217 if (attrs1 != attrs2)
218 return attrs2 > attrs1;
219
220 return strcmp(w2->name.c_str(), w1->name.c_str()) < 0;
221 }
222
223 bool check_public_name(RTLIL::IdString id)
224 {
225 const std::string &id_str = id.str();
226 if (id_str[0] == '$')
227 return false;
228 if (id_str.substr(0, 2) == "\\_" && (id_str[id_str.size()-1] == '_' || id_str.find("_[") != std::string::npos))
229 return false;
230 if (id_str.find(".$") != std::string::npos)
231 return false;
232 return true;
233 }
234
235 bool rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbose)
236 {
237 SigPool register_signals;
238 SigPool connected_signals;
239
240 if (!purge_mode)
241 for (auto &it : module->cells_) {
242 RTLIL::Cell *cell = it.second;
243 if (ct_reg.cell_known(cell->type))
244 for (auto &it2 : cell->connections())
245 if (ct_reg.cell_output(cell->type, it2.first))
246 register_signals.add(it2.second);
247 for (auto &it2 : cell->connections())
248 connected_signals.add(it2.second);
249 }
250
251 SigMap assign_map(module);
252 pool<RTLIL::SigSpec> direct_sigs;
253 pool<RTLIL::Wire*> direct_wires;
254 for (auto &it : module->cells_) {
255 RTLIL::Cell *cell = it.second;
256 if (ct_all.cell_known(cell->type))
257 for (auto &it2 : cell->connections())
258 if (ct_all.cell_output(cell->type, it2.first))
259 direct_sigs.insert(assign_map(it2.second));
260 }
261 for (auto &it : module->wires_) {
262 if (direct_sigs.count(assign_map(it.second)) || it.second->port_input)
263 direct_wires.insert(it.second);
264 }
265
266 for (auto &it : module->wires_) {
267 RTLIL::Wire *wire = it.second;
268 for (int i = 0; i < wire->width; i++) {
269 RTLIL::SigBit s1 = RTLIL::SigBit(wire, i), s2 = assign_map(s1);
270 if (!compare_signals(s1, s2, register_signals, connected_signals, direct_wires))
271 assign_map.add(s1);
272 }
273 }
274
275 module->connections_.clear();
276
277 SigPool used_signals;
278 SigPool raw_used_signals;
279 SigPool used_signals_nodrivers;
280 for (auto &it : module->cells_) {
281 RTLIL::Cell *cell = it.second;
282 for (auto &it2 : cell->connections_) {
283 assign_map.apply(it2.second);
284 raw_used_signals.add(it2.second);
285 used_signals.add(it2.second);
286 if (!ct_all.cell_output(cell->type, it2.first))
287 used_signals_nodrivers.add(it2.second);
288 }
289 }
290 for (auto &it : module->wires_) {
291 RTLIL::Wire *wire = it.second;
292 if (wire->port_id > 0) {
293 RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
294 raw_used_signals.add(sig);
295 assign_map.apply(sig);
296 used_signals.add(sig);
297 if (!wire->port_input)
298 used_signals_nodrivers.add(sig);
299 }
300 if (wire->get_bool_attribute("\\keep")) {
301 RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
302 assign_map.apply(sig);
303 used_signals.add(sig);
304 }
305 }
306
307 pool<RTLIL::Wire*> del_wires_queue;
308 for (auto wire : module->wires())
309 {
310 SigSpec s1 = SigSpec(wire), s2 = assign_map(s1);
311 log_assert(GetSize(s1) == GetSize(s2));
312
313 Const initval;
314 if (wire->attributes.count("\\init"))
315 initval = wire->attributes.at("\\init");
316 if (GetSize(initval) != GetSize(wire))
317 initval.bits.resize(GetSize(wire), State::Sx);
318 if (initval.is_fully_undef())
319 wire->attributes.erase("\\init");
320
321 if (GetSize(wire) == 0) {
322 // delete zero-width wires
323 goto delete_this_wire;
324 } else
325 if (wire->port_id != 0 || wire->get_bool_attribute("\\keep") || !initval.is_fully_undef()) {
326 // do not delete anything with "keep" or module ports or initialized wires
327 } else
328 if (!purge_mode && check_public_name(wire->name)) {
329 // do not get rid of public names unless in purge mode
330 } else
331 if (!raw_used_signals.check_any(s1)) {
332 // delete wires that aren't used by anything directly
333 goto delete_this_wire;
334 } else
335 if (!used_signals.check_any(s2)) {
336 // delete wires that aren't used by anything indirectly, even though other wires may alias it
337 goto delete_this_wire;
338 }
339
340 if (0)
341 {
342 delete_this_wire:
343 del_wires_queue.insert(wire);
344 }
345 else
346 {
347 RTLIL::SigSig new_conn;
348 for (int i = 0; i < GetSize(s1); i++)
349 if (s1[i] != s2[i]) {
350 if (s2[i] == State::Sx && (initval[i] == State::S0 || initval[i] == State::S1)) {
351 s2[i] = initval[i];
352 initval[i] = State::Sx;
353 }
354 new_conn.first.append_bit(s1[i]);
355 new_conn.second.append_bit(s2[i]);
356 }
357 if (new_conn.first.size() > 0) {
358 if (initval.is_fully_undef())
359 wire->attributes.erase("\\init");
360 else
361 wire->attributes.at("\\init") = initval;
362 used_signals.add(new_conn.first);
363 used_signals.add(new_conn.second);
364 module->connect(new_conn);
365 }
366
367 if (!used_signals_nodrivers.check_all(s2)) {
368 std::string unused_bits;
369 for (int i = 0; i < GetSize(s2); i++) {
370 if (s2[i].wire == NULL)
371 continue;
372 if (!used_signals_nodrivers.check(s2[i])) {
373 if (!unused_bits.empty())
374 unused_bits += " ";
375 unused_bits += stringf("%d", i);
376 }
377 }
378 if (unused_bits.empty() || wire->port_id != 0)
379 wire->attributes.erase("\\unused_bits");
380 else
381 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
382 } else {
383 wire->attributes.erase("\\unused_bits");
384 }
385 }
386 }
387
388 int del_temp_wires_count = 0;
389 for (auto wire : del_wires_queue) {
390 if (ys_debug() || (check_public_name(wire->name) && verbose))
391 log_debug(" removing unused non-port wire %s.\n", wire->name.c_str());
392 else
393 del_temp_wires_count++;
394 }
395
396 module->remove(del_wires_queue);
397 count_rm_wires += GetSize(del_wires_queue);
398
399 if (verbose && del_temp_wires_count)
400 log_debug(" removed %d unused temporary wires.\n", del_temp_wires_count);
401
402 return !del_wires_queue.empty();
403 }
404
405 bool rmunused_module_init(RTLIL::Module *module, bool purge_mode, bool verbose)
406 {
407 bool did_something = false;
408 CellTypes fftypes;
409 fftypes.setup_internals_mem();
410
411 SigMap sigmap(module);
412 dict<SigBit, State> qbits;
413
414 for (auto cell : module->cells())
415 if (fftypes.cell_known(cell->type) && cell->hasPort("\\Q"))
416 {
417 SigSpec sig = cell->getPort("\\Q");
418
419 for (int i = 0; i < GetSize(sig); i++)
420 {
421 SigBit bit = sig[i];
422
423 if (bit.wire == nullptr || bit.wire->attributes.count("\\init") == 0)
424 continue;
425
426 Const init = bit.wire->attributes.at("\\init");
427
428 if (i >= GetSize(init) || init[i] == State::Sx || init[i] == State::Sz)
429 continue;
430
431 sigmap.add(bit);
432 qbits[bit] = init[i];
433 }
434 }
435
436 for (auto wire : module->wires())
437 {
438 if (!purge_mode && wire->name[0] == '\\')
439 continue;
440
441 if (wire->attributes.count("\\init") == 0)
442 continue;
443
444 Const init = wire->attributes.at("\\init");
445
446 for (int i = 0; i < GetSize(wire) && i < GetSize(init); i++)
447 {
448 if (init[i] == State::Sx || init[i] == State::Sz)
449 continue;
450
451 SigBit wire_bit = SigBit(wire, i);
452 SigBit mapped_wire_bit = sigmap(wire_bit);
453
454 if (wire_bit == mapped_wire_bit)
455 goto next_wire;
456
457 if (qbits.count(sigmap(SigBit(wire, i))) == 0)
458 goto next_wire;
459
460 if (qbits.at(sigmap(SigBit(wire, i))) != init[i])
461 goto next_wire;
462 }
463
464 if (verbose)
465 log_debug(" removing redundant init attribute on %s.\n", log_id(wire));
466
467 wire->attributes.erase("\\init");
468 did_something = true;
469 next_wire:;
470 }
471
472 return did_something;
473 }
474
475 void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose, bool rminit)
476 {
477 if (verbose)
478 log("Finding unused cells or wires in module %s..\n", module->name.c_str());
479
480 std::vector<RTLIL::Cell*> delcells;
481 for (auto cell : module->cells())
482 if (cell->type.in("$pos", "$_BUF_")) {
483 bool is_signed = cell->type == "$pos" && cell->getParam("\\A_SIGNED").as_bool();
484 RTLIL::SigSpec a = cell->getPort("\\A");
485 RTLIL::SigSpec y = cell->getPort("\\Y");
486 a.extend_u0(GetSize(y), is_signed);
487 module->connect(y, a);
488 delcells.push_back(cell);
489 }
490 for (auto cell : delcells) {
491 if (verbose)
492 log_debug(" removing buffer cell `%s': %s = %s\n", cell->name.c_str(),
493 log_signal(cell->getPort("\\Y")), log_signal(cell->getPort("\\A")));
494 module->remove(cell);
495 }
496 if (!delcells.empty())
497 module->design->scratchpad_set_bool("opt.did_something", true);
498
499 rmunused_module_cells(module, verbose);
500 while (rmunused_module_signals(module, purge_mode, verbose)) { }
501
502 if (rminit && rmunused_module_init(module, purge_mode, verbose))
503 while (rmunused_module_signals(module, purge_mode, verbose)) { }
504 }
505
506 struct OptCleanPass : public Pass {
507 OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
508 void help() YS_OVERRIDE
509 {
510 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
511 log("\n");
512 log(" opt_clean [options] [selection]\n");
513 log("\n");
514 log("This pass identifies wires and cells that are unused and removes them. Other\n");
515 log("passes often remove cells but leave the wires in the design or reconnect the\n");
516 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
517 log("after the passes that do the actual work.\n");
518 log("\n");
519 log("This pass only operates on completely selected modules without processes.\n");
520 log("\n");
521 log(" -purge\n");
522 log(" also remove internal nets if they have a public name\n");
523 log("\n");
524 }
525 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
526 {
527 bool purge_mode = false;
528
529 log_header(design, "Executing OPT_CLEAN pass (remove unused cells and wires).\n");
530 log_push();
531
532 size_t argidx;
533 for (argidx = 1; argidx < args.size(); argidx++) {
534 if (args[argidx] == "-purge") {
535 purge_mode = true;
536 continue;
537 }
538 break;
539 }
540 extra_args(args, argidx, design);
541
542 keep_cache.reset(design);
543
544 ct_reg.setup_internals_mem();
545 ct_reg.setup_stdcells_mem();
546
547 ct_all.setup(design);
548
549 count_rm_cells = 0;
550 count_rm_wires = 0;
551
552 for (auto module : design->selected_whole_modules_warn()) {
553 if (module->has_processes_warn())
554 continue;
555 rmunused_module(module, purge_mode, true, true);
556 }
557
558 if (count_rm_cells > 0 || count_rm_wires > 0)
559 log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
560
561 design->optimize();
562 design->sort();
563 design->check();
564
565 keep_cache.reset();
566 ct_reg.clear();
567 ct_all.clear();
568 log_pop();
569 }
570 } OptCleanPass;
571
572 struct CleanPass : public Pass {
573 CleanPass() : Pass("clean", "remove unused cells and wires") { }
574 void help() YS_OVERRIDE
575 {
576 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
577 log("\n");
578 log(" clean [options] [selection]\n");
579 log("\n");
580 log("This is identical to 'opt_clean', but less verbose.\n");
581 log("\n");
582 log("When commands are separated using the ';;' token, this command will be executed\n");
583 log("between the commands.\n");
584 log("\n");
585 log("When commands are separated using the ';;;' token, this command will be executed\n");
586 log("in -purge mode between the commands.\n");
587 log("\n");
588 }
589 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
590 {
591 bool purge_mode = false;
592
593 size_t argidx;
594 for (argidx = 1; argidx < args.size(); argidx++) {
595 if (args[argidx] == "-purge") {
596 purge_mode = true;
597 continue;
598 }
599 break;
600 }
601 if (argidx < args.size())
602 extra_args(args, argidx, design);
603
604 keep_cache.reset(design);
605
606 ct_reg.setup_internals_mem();
607 ct_reg.setup_stdcells_mem();
608
609 ct_all.setup(design);
610
611 count_rm_cells = 0;
612 count_rm_wires = 0;
613
614 for (auto module : design->selected_whole_modules()) {
615 if (module->has_processes())
616 continue;
617 rmunused_module(module, purge_mode, ys_debug(), false);
618 }
619
620 log_suppressed();
621 if (count_rm_cells > 0 || count_rm_wires > 0)
622 log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
623
624 design->optimize();
625 design->sort();
626 design->check();
627
628 keep_cache.reset();
629 ct_reg.clear();
630 ct_all.clear();
631 }
632 } CleanPass;
633
634 PRIVATE_NAMESPACE_END