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