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
36 dict
<Module
*, bool> cache
;
38 void reset(Design
*design
= nullptr)
40 this->design
= design
;
44 bool query(Module
*module
)
46 log_assert(design
!= nullptr);
48 if (module
== nullptr)
51 if (cache
.count(module
))
52 return cache
.at(module
);
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 */)) {
62 cache
[module
] = found_keep
;
68 bool query(Cell
*cell
, bool ignore_specify
= false)
70 if (cell
->type
.in(ID($memwr
), ID($meminit
), ID($
assert), ID($assume
), ID($live
), ID($fair
), ID($cover
)))
73 if (!ignore_specify
&& cell
->type
.in(ID($specify2
), ID($specify3
), ID($specrule
)))
76 if (cell
->has_keep_attr())
79 if (cell
->module
&& cell
->module
->design
)
80 return query(cell
->module
->design
->module(cell
->type
));
86 keep_cache_t keep_cache
;
87 CellTypes ct_reg
, ct_all
;
88 int count_rm_cells
, count_rm_wires
;
90 void rmunused_module_cells(Module
*module
, bool verbose
)
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
;
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
]);
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
))
111 for (auto raw_bit
: it2
.second
) {
112 if (raw_bit
.wire
== nullptr)
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
);
123 if (keep_cache
.query(cell
))
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
));
140 while (!queue
.empty())
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
))
150 for (auto bit
: bits
)
151 for (auto c
: wire2driver
[bit
])
153 queue
.insert(c
), unused
.erase(c
);
156 unused
.sort(RTLIL::sort_by_name_id
<RTLIL::Cell
>());
158 for (auto cell
: unused
) {
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
);
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
))
171 for (auto raw_bit
: raw_sigmap(it2
.second
))
172 used_raw_bits
.insert(raw_bit
);
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());
183 int count_nontrivial_wire_attrs(RTLIL::Wire
*w
)
185 int count
= w
->attributes
.size();
186 count
-= w
->attributes
.count(ID::src
);
187 count
-= w
->attributes
.count(ID::unused_bits
);
191 bool compare_signals(RTLIL::SigBit
&s1
, RTLIL::SigBit
&s2
, SigPool
®s
, SigPool
&conns
, pool
<RTLIL::Wire
*> &direct_wires
)
193 RTLIL::Wire
*w1
= s1
.wire
;
194 RTLIL::Wire
*w2
= s2
.wire
;
196 if (w1
== NULL
|| w2
== NULL
)
199 if (w1
->port_input
!= w2
->port_input
)
200 return w2
->port_input
;
202 if ((w1
->port_input
&& w1
->port_output
) != (w2
->port_input
&& w2
->port_output
))
203 return !(w2
->port_input
&& w2
->port_output
);
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
);
214 if (w1
->port_output
!= w2
->port_output
)
215 return w2
->port_output
;
217 if (w1
->name
[0] != w2
->name
[0])
218 return w2
->name
[0] == '\\';
220 int attrs1
= count_nontrivial_wire_attrs(w1
);
221 int attrs2
= count_nontrivial_wire_attrs(w2
);
223 if (attrs1
!= attrs2
)
224 return attrs2
> attrs1
;
226 return strcmp(w2
->name
.c_str(), w1
->name
.c_str()) < 0;
229 bool check_public_name(RTLIL::IdString id
)
231 if (id
.begins_with("$"))
233 const std::string
&id_str
= id
.str();
234 if (id
.begins_with("\\_") && (id
.ends_with("_") || id_str
.find("_[") != std::string::npos
))
236 if (id_str
.find(".$") != std::string::npos
)
241 bool rmunused_module_signals(RTLIL::Module
*module
, bool purge_mode
, bool verbose
)
243 SigPool register_signals
;
244 SigPool connected_signals
;
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
);
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
));
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
);
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
))
281 module
->connections_
.clear();
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
);
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
);
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
);
313 pool
<RTLIL::Wire
*> del_wires_queue
;
314 for (auto wire
: module
->wires())
316 SigSpec s1
= SigSpec(wire
), s2
= assign_map(s1
);
317 log_assert(GetSize(s1
) == GetSize(s2
));
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
);
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
;
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
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
338 if (!raw_used_signals
.check_any(s1
)) {
339 // delete wires that aren't used by anything directly
340 goto delete_this_wire
;
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
;
350 del_wires_queue
.insert(wire
);
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
)) {
359 initval
[i
] = State::Sx
;
361 new_conn
.first
.append(s1
[i
]);
362 new_conn
.second
.append(s2
[i
]);
364 if (new_conn
.first
.size() > 0) {
365 if (initval
.is_fully_undef())
366 wire
->attributes
.erase(ID::init
);
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
);
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
)
379 if (!used_signals_nodrivers
.check(s2
[i
])) {
380 if (!unused_bits
.empty())
382 unused_bits
+= stringf("%d", i
);
385 if (unused_bits
.empty() || wire
->port_id
!= 0)
386 wire
->attributes
.erase(ID::unused_bits
);
388 wire
->attributes
[ID::unused_bits
] = RTLIL::Const(unused_bits
);
390 wire
->attributes
.erase(ID::unused_bits
);
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());
400 del_temp_wires_count
++;
403 module
->remove(del_wires_queue
);
404 count_rm_wires
+= GetSize(del_wires_queue
);
406 if (verbose
&& del_temp_wires_count
)
407 log_debug(" removed %d unused temporary wires.\n", del_temp_wires_count
);
409 if (!del_wires_queue
.empty())
410 module
->design
->scratchpad_set_bool("opt.did_something", true);
412 return !del_wires_queue
.empty();
415 bool rmunused_module_init(RTLIL::Module
*module
, bool verbose
)
417 bool did_something
= false;
419 fftypes
.setup_internals_mem();
421 SigMap
sigmap(module
);
422 dict
<SigBit
, State
> qbits
;
424 for (auto cell
: module
->cells())
425 if (fftypes
.cell_known(cell
->type
) && cell
->hasPort(ID::Q
))
427 SigSpec sig
= cell
->getPort(ID::Q
);
429 for (int i
= 0; i
< GetSize(sig
); i
++)
433 if (bit
.wire
== nullptr || bit
.wire
->attributes
.count(ID::init
) == 0)
436 Const init
= bit
.wire
->attributes
.at(ID::init
);
438 if (i
>= GetSize(init
) || init
[i
] == State::Sx
|| init
[i
] == State::Sz
)
442 qbits
[bit
] = init
[i
];
446 for (auto wire
: module
->wires())
448 if (wire
->attributes
.count(ID::init
) == 0)
451 Const init
= wire
->attributes
.at(ID::init
);
453 for (int i
= 0; i
< GetSize(wire
) && i
< GetSize(init
); i
++)
455 if (init
[i
] == State::Sx
|| init
[i
] == State::Sz
)
458 SigBit wire_bit
= SigBit(wire
, i
);
459 SigBit mapped_wire_bit
= sigmap(wire_bit
);
461 if (wire_bit
== mapped_wire_bit
)
464 if (mapped_wire_bit
.wire
) {
465 if (qbits
.count(mapped_wire_bit
) == 0)
468 if (qbits
.at(mapped_wire_bit
) != init
[i
])
472 if (mapped_wire_bit
== State::Sx
|| mapped_wire_bit
== State::Sz
)
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
]));
483 log_debug(" removing redundant init attribute on %s.\n", log_id(wire
));
485 wire
->attributes
.erase(ID::init
);
486 did_something
= true;
491 module
->design
->scratchpad_set_bool("opt.did_something", true);
493 return did_something
;
496 void rmunused_module(RTLIL::Module
*module
, bool purge_mode
, bool verbose
, bool rminit
)
499 log("Finding unused cells or wires in module %s..\n", module
->name
.c_str());
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
);
511 for (auto cell
: delcells
) {
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
);
517 if (!delcells
.empty())
518 module
->design
->scratchpad_set_bool("opt.did_something", true);
520 rmunused_module_cells(module
, verbose
);
521 while (rmunused_module_signals(module
, purge_mode
, verbose
)) { }
523 if (rminit
&& rmunused_module_init(module
, verbose
))
524 while (rmunused_module_signals(module
, purge_mode
, verbose
)) { }
527 struct OptCleanPass
: public Pass
{
528 OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
529 void help() YS_OVERRIDE
531 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
533 log(" opt_clean [options] [selection]\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");
540 log("This pass only operates on completely selected modules without processes.\n");
543 log(" also remove internal nets if they have a public name\n");
546 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
548 bool purge_mode
= false;
550 log_header(design
, "Executing OPT_CLEAN pass (remove unused cells and wires).\n");
554 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
555 if (args
[argidx
] == "-purge") {
561 extra_args(args
, argidx
, design
);
563 keep_cache
.reset(design
);
565 ct_reg
.setup_internals_mem();
566 ct_reg
.setup_stdcells_mem();
568 ct_all
.setup(design
);
573 for (auto module
: design
->selected_whole_modules_warn()) {
574 if (module
->has_processes_warn())
576 rmunused_module(module
, purge_mode
, true, true);
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
);
593 struct CleanPass
: public Pass
{
594 CleanPass() : Pass("clean", "remove unused cells and wires") { }
595 void help() YS_OVERRIDE
597 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
599 log(" clean [options] [selection]\n");
601 log("This is identical to 'opt_clean', but less verbose.\n");
603 log("When commands are separated using the ';;' token, this command will be executed\n");
604 log("between the commands.\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");
610 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
612 bool purge_mode
= false;
615 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
616 if (args
[argidx
] == "-purge") {
622 extra_args(args
, argidx
, design
);
624 keep_cache
.reset(design
);
626 ct_reg
.setup_internals_mem();
627 ct_reg
.setup_stdcells_mem();
629 ct_all
.setup(design
);
634 for (auto module
: design
->selected_whole_modules()) {
635 if (module
->has_processes())
637 rmunused_module(module
, purge_mode
, ys_debug(), true);
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
);
654 PRIVATE_NAMESPACE_END