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/yosys.h"
21 #include "kernel/sigtools.h"
22 #include "kernel/modtools.h"
25 using namespace RTLIL
;
27 PRIVATE_NAMESPACE_BEGIN
31 pool
<IdString
> supported_cell_types
;
35 supported_cell_types
= pool
<IdString
>({
36 "$not", "$pos", "$neg",
37 "$and", "$or", "$xor", "$xnor",
38 "$shl", "$shr", "$sshl", "$sshr", "$shift", "$shiftx",
39 "$lt", "$le", "$eq", "$ne", "$eqx", "$nex", "$ge", "$gt",
40 "$add", "$sub", "$mul", // "$div", "$mod", "$pow",
49 WreduceConfig
*config
;
53 std::set
<Cell
*, IdString::compare_ptr_by_name
<Cell
>> work_queue_cells
;
54 std::set
<SigBit
> work_queue_bits
;
55 pool
<SigBit
> keep_bits
;
56 dict
<SigBit
, State
> init_bits
;
57 pool
<SigBit
> remove_init_bits
;
59 WreduceWorker(WreduceConfig
*config
, Module
*module
) :
60 config(config
), module(module
), mi(module
) { }
62 void run_cell_mux(Cell
*cell
)
64 // Reduce size of MUX if inputs agree on a value for a bit or a output bit is unused
66 SigSpec sig_a
= mi
.sigmap(cell
->getPort("\\A"));
67 SigSpec sig_b
= mi
.sigmap(cell
->getPort("\\B"));
68 SigSpec sig_s
= mi
.sigmap(cell
->getPort("\\S"));
69 SigSpec sig_y
= mi
.sigmap(cell
->getPort("\\Y"));
70 std::vector
<SigBit
> bits_removed
;
72 if (sig_y
.has_const())
75 for (int i
= GetSize(sig_y
)-1; i
>= 0; i
--)
77 auto info
= mi
.query(sig_y
[i
]);
78 if (!info
->is_output
&& GetSize(info
->ports
) <= 1 && !keep_bits
.count(mi
.sigmap(sig_y
[i
]))) {
79 bits_removed
.push_back(Sx
);
83 SigBit ref
= sig_a
[i
];
84 for (int k
= 0; k
< GetSize(sig_s
); k
++) {
85 if (ref
!= Sx
&& sig_b
[k
*GetSize(sig_a
) + i
] != Sx
&& ref
!= sig_b
[k
*GetSize(sig_a
) + i
])
87 if (sig_b
[k
*GetSize(sig_a
) + i
] != Sx
)
88 ref
= sig_b
[k
*GetSize(sig_a
) + i
];
93 bits_removed
.push_back(ref
);
96 if (bits_removed
.empty())
100 for (int i
= GetSize(bits_removed
)-1; i
>= 0; i
--)
101 sig_removed
.append_bit(bits_removed
[i
]);
103 if (GetSize(bits_removed
) == GetSize(sig_y
)) {
104 log("Removed cell %s.%s (%s).\n", log_id(module
), log_id(cell
), log_id(cell
->type
));
105 module
->connect(sig_y
, sig_removed
);
106 module
->remove(cell
);
110 log("Removed top %d bits (of %d) from mux cell %s.%s (%s).\n",
111 GetSize(sig_removed
), GetSize(sig_y
), log_id(module
), log_id(cell
), log_id(cell
->type
));
113 int n_removed
= GetSize(sig_removed
);
114 int n_kept
= GetSize(sig_y
) - GetSize(sig_removed
);
116 SigSpec new_work_queue_bits
;
117 new_work_queue_bits
.append(sig_a
.extract(n_kept
, n_removed
));
118 new_work_queue_bits
.append(sig_y
.extract(n_kept
, n_removed
));
120 SigSpec new_sig_a
= sig_a
.extract(0, n_kept
);
121 SigSpec new_sig_y
= sig_y
.extract(0, n_kept
);
124 for (int k
= 0; k
< GetSize(sig_s
); k
++) {
125 new_sig_b
.append(sig_b
.extract(k
*GetSize(sig_a
), n_kept
));
126 new_work_queue_bits
.append(sig_b
.extract(k
*GetSize(sig_a
) + n_kept
, n_removed
));
129 for (auto bit
: new_work_queue_bits
)
130 work_queue_bits
.insert(bit
);
132 cell
->setPort("\\A", new_sig_a
);
133 cell
->setPort("\\B", new_sig_b
);
134 cell
->setPort("\\Y", new_sig_y
);
135 cell
->fixup_parameters();
137 module
->connect(sig_y
.extract(n_kept
, n_removed
), sig_removed
);
140 void run_cell_dff(Cell
*cell
)
142 // Reduce size of FF if inputs are just sign/zero extended or output bit is not used
144 SigSpec sig_d
= mi
.sigmap(cell
->getPort("\\D"));
145 SigSpec sig_q
= mi
.sigmap(cell
->getPort("\\Q"));
148 int width_before
= GetSize(sig_q
);
150 if (width_before
== 0)
153 bool zero_ext
= sig_d
[GetSize(sig_d
)-1] == State::S0
;
154 bool sign_ext
= !zero_ext
;
156 for (int i
= 0; i
< GetSize(sig_q
); i
++) {
157 SigBit bit
= sig_q
[i
];
158 if (init_bits
.count(bit
))
159 initval
.bits
.push_back(init_bits
.at(bit
));
161 initval
.bits
.push_back(State::Sx
);
164 for (int i
= GetSize(sig_q
)-1; i
>= 0; i
--)
166 if (zero_ext
&& sig_d
[i
] == State::S0
&& (initval
[i
] == State::S0
|| initval
[i
] == State::Sx
)) {
167 module
->connect(sig_q
[i
], State::S0
);
168 remove_init_bits
.insert(sig_q
[i
]);
174 if (sign_ext
&& i
> 0 && sig_d
[i
] == sig_d
[i
-1] && initval
[i
] == initval
[i
-1]) {
175 module
->connect(sig_q
[i
], sig_q
[i
-1]);
176 remove_init_bits
.insert(sig_q
[i
]);
182 auto info
= mi
.query(sig_q
[i
]);
185 if (!info
->is_output
&& GetSize(info
->ports
) == 1 && !keep_bits
.count(mi
.sigmap(sig_q
[i
]))) {
186 remove_init_bits
.insert(sig_q
[i
]);
197 if (width_before
== GetSize(sig_q
))
200 if (GetSize(sig_q
) == 0) {
201 log("Removed cell %s.%s (%s).\n", log_id(module
), log_id(cell
), log_id(cell
->type
));
202 module
->remove(cell
);
206 log("Removed top %d bits (of %d) from FF cell %s.%s (%s).\n", width_before
- GetSize(sig_q
), width_before
,
207 log_id(module
), log_id(cell
), log_id(cell
->type
));
209 for (auto bit
: sig_d
)
210 work_queue_bits
.insert(bit
);
212 for (auto bit
: sig_q
)
213 work_queue_bits
.insert(bit
);
215 // Narrow ARST_VALUE parameter to new size.
216 if (cell
->parameters
.count("\\ARST_VALUE")) {
217 Const arst_value
= cell
->getParam("\\ARST_VALUE");
218 arst_value
.bits
.resize(GetSize(sig_q
));
219 cell
->setParam("\\ARST_VALUE", arst_value
);
222 cell
->setPort("\\D", sig_d
);
223 cell
->setPort("\\Q", sig_q
);
224 cell
->fixup_parameters();
227 void run_reduce_inport(Cell
*cell
, char port
, int max_port_size
, bool &port_signed
, bool &did_something
)
229 port_signed
= cell
->getParam(stringf("\\%c_SIGNED", port
)).as_bool();
230 SigSpec sig
= mi
.sigmap(cell
->getPort(stringf("\\%c", port
)));
232 if (port
== 'B' && cell
->type
.in("$shl", "$shr", "$sshl", "$sshr"))
235 int bits_removed
= 0;
236 if (GetSize(sig
) > max_port_size
) {
237 bits_removed
= GetSize(sig
) - max_port_size
;
238 for (auto bit
: sig
.extract(max_port_size
, bits_removed
))
239 work_queue_bits
.insert(bit
);
240 sig
= sig
.extract(0, max_port_size
);
244 while (GetSize(sig
) > 1 && sig
[GetSize(sig
)-1] == sig
[GetSize(sig
)-2])
245 work_queue_bits
.insert(sig
[GetSize(sig
)-1]), sig
.remove(GetSize(sig
)-1), bits_removed
++;
247 while (GetSize(sig
) > 1 && sig
[GetSize(sig
)-1] == S0
)
248 work_queue_bits
.insert(sig
[GetSize(sig
)-1]), sig
.remove(GetSize(sig
)-1), bits_removed
++;
252 log("Removed top %d bits (of %d) from port %c of cell %s.%s (%s).\n",
253 bits_removed
, GetSize(sig
) + bits_removed
, port
, log_id(module
), log_id(cell
), log_id(cell
->type
));
254 cell
->setPort(stringf("\\%c", port
), sig
);
255 did_something
= true;
259 void run_cell(Cell
*cell
)
261 bool did_something
= false;
263 if (!cell
->type
.in(config
->supported_cell_types
))
266 if (cell
->type
.in("$mux", "$pmux"))
267 return run_cell_mux(cell
);
269 if (cell
->type
.in("$dff", "$adff"))
270 return run_cell_dff(cell
);
272 SigSpec sig
= mi
.sigmap(cell
->getPort("\\Y"));
278 // Reduce size of ports A and B based on constant input bits and size of output port
280 int max_port_a_size
= cell
->hasPort("\\A") ? GetSize(cell
->getPort("\\A")) : -1;
281 int max_port_b_size
= cell
->hasPort("\\B") ? GetSize(cell
->getPort("\\B")) : -1;
283 if (cell
->type
.in("$not", "$pos", "$neg", "$and", "$or", "$xor", "$add", "$sub")) {
284 max_port_a_size
= min(max_port_a_size
, GetSize(sig
));
285 max_port_b_size
= min(max_port_b_size
, GetSize(sig
));
288 bool port_a_signed
= false;
289 bool port_b_signed
= false;
291 if (max_port_a_size
>= 0 && cell
->type
!= "$shiftx")
292 run_reduce_inport(cell
, 'A', max_port_a_size
, port_a_signed
, did_something
);
294 if (max_port_b_size
>= 0)
295 run_reduce_inport(cell
, 'B', max_port_b_size
, port_b_signed
, did_something
);
297 if (cell
->hasPort("\\A") && cell
->hasPort("\\B") && port_a_signed
&& port_b_signed
) {
298 SigSpec sig_a
= mi
.sigmap(cell
->getPort("\\A")), sig_b
= mi
.sigmap(cell
->getPort("\\B"));
299 if (GetSize(sig_a
) > 0 && sig_a
[GetSize(sig_a
)-1] == State::S0
&&
300 GetSize(sig_b
) > 0 && sig_b
[GetSize(sig_b
)-1] == State::S0
) {
301 log("Converting cell %s.%s (%s) from signed to unsigned.\n",
302 log_id(module
), log_id(cell
), log_id(cell
->type
));
303 cell
->setParam("\\A_SIGNED", 0);
304 cell
->setParam("\\B_SIGNED", 0);
305 port_a_signed
= false;
306 port_b_signed
= false;
307 did_something
= true;
311 if (cell
->hasPort("\\A") && !cell
->hasPort("\\B") && port_a_signed
) {
312 SigSpec sig_a
= mi
.sigmap(cell
->getPort("\\A"));
313 if (GetSize(sig_a
) > 0 && sig_a
[GetSize(sig_a
)-1] == State::S0
) {
314 log("Converting cell %s.%s (%s) from signed to unsigned.\n",
315 log_id(module
), log_id(cell
), log_id(cell
->type
));
316 cell
->setParam("\\A_SIGNED", 0);
317 port_a_signed
= false;
318 did_something
= true;
323 // Reduce size of port Y based on sizes for A and B and unused bits in Y
325 int bits_removed
= 0;
326 if (port_a_signed
&& cell
->type
== "$shr") {
327 // do not reduce size of output on $shr cells with signed A inputs
329 while (GetSize(sig
) > 0)
331 auto bit
= sig
[GetSize(sig
)-1];
332 if (keep_bits
.count(bit
))
335 auto info
= mi
.query(bit
);
336 if (info
->is_output
|| GetSize(info
->ports
) > 1)
339 sig
.remove(GetSize(sig
)-1);
344 if (cell
->type
.in("$pos", "$add", "$mul", "$and", "$or", "$xor"))
346 bool is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
348 int a_size
= 0, b_size
= 0;
349 if (cell
->hasPort("\\A")) a_size
= GetSize(cell
->getPort("\\A"));
350 if (cell
->hasPort("\\B")) b_size
= GetSize(cell
->getPort("\\B"));
352 int max_y_size
= max(a_size
, b_size
);
354 if (cell
->type
== "$add")
357 if (cell
->type
== "$mul")
358 max_y_size
= a_size
+ b_size
;
360 while (GetSize(sig
) > 1 && GetSize(sig
) > max_y_size
) {
361 module
->connect(sig
[GetSize(sig
)-1], is_signed
? sig
[GetSize(sig
)-2] : S0
);
362 sig
.remove(GetSize(sig
)-1);
367 if (GetSize(sig
) == 0) {
368 log("Removed cell %s.%s (%s).\n", log_id(module
), log_id(cell
), log_id(cell
->type
));
369 module
->remove(cell
);
374 log("Removed top %d bits (of %d) from port Y of cell %s.%s (%s).\n",
375 bits_removed
, GetSize(sig
) + bits_removed
, log_id(module
), log_id(cell
), log_id(cell
->type
));
376 cell
->setPort("\\Y", sig
);
377 did_something
= true;
381 cell
->fixup_parameters();
386 static int count_nontrivial_wire_attrs(RTLIL::Wire
*w
)
388 int count
= w
->attributes
.size();
389 count
-= w
->attributes
.count("\\src");
390 count
-= w
->attributes
.count("\\unused_bits");
396 // create a copy as mi.sigmap will be updated as we process the module
397 SigMap init_attr_sigmap
= mi
.sigmap
;
399 for (auto w
: module
->wires()) {
400 if (w
->get_bool_attribute("\\keep"))
401 for (auto bit
: mi
.sigmap(w
))
402 keep_bits
.insert(bit
);
403 if (w
->attributes
.count("\\init")) {
404 Const initval
= w
->attributes
.at("\\init");
405 SigSpec initsig
= init_attr_sigmap(w
);
406 int width
= std::min(GetSize(initval
), GetSize(initsig
));
407 for (int i
= 0; i
< width
; i
++)
408 init_bits
[initsig
[i
]] = initval
[i
];
412 for (auto c
: module
->selected_cells())
413 work_queue_cells
.insert(c
);
415 while (!work_queue_cells
.empty())
417 work_queue_bits
.clear();
418 for (auto c
: work_queue_cells
)
421 work_queue_cells
.clear();
422 for (auto bit
: work_queue_bits
)
423 for (auto port
: mi
.query_ports(bit
))
424 if (module
->selected(port
.cell
))
425 work_queue_cells
.insert(port
.cell
);
428 pool
<SigSpec
> complete_wires
;
429 for (auto w
: module
->wires())
430 complete_wires
.insert(mi
.sigmap(w
));
432 for (auto w
: module
->selected_wires())
434 int unused_top_bits
= 0;
436 if (w
->port_id
> 0 || count_nontrivial_wire_attrs(w
) > 0)
439 for (int i
= GetSize(w
)-1; i
>= 0; i
--) {
441 auto info
= mi
.query(bit
);
442 if (info
&& (info
->is_input
|| info
->is_output
|| GetSize(info
->ports
) > 0))
447 if (unused_top_bits
== 0 || unused_top_bits
== GetSize(w
))
450 if (complete_wires
[mi
.sigmap(w
).extract(0, GetSize(w
) - unused_top_bits
)])
453 log("Removed top %d bits (of %d) from wire %s.%s.\n", unused_top_bits
, GetSize(w
), log_id(module
), log_id(w
));
454 Wire
*nw
= module
->addWire(NEW_ID
, GetSize(w
) - unused_top_bits
);
455 module
->connect(nw
, SigSpec(w
).extract(0, GetSize(nw
)));
456 module
->swap_names(w
, nw
);
459 if (!remove_init_bits
.empty()) {
460 for (auto w
: module
->wires()) {
461 if (w
->attributes
.count("\\init")) {
462 Const initval
= w
->attributes
.at("\\init");
463 Const
new_initval(State::Sx
, GetSize(w
));
464 SigSpec initsig
= init_attr_sigmap(w
);
465 int width
= std::min(GetSize(initval
), GetSize(initsig
));
466 for (int i
= 0; i
< width
; i
++) {
467 if (!remove_init_bits
.count(initsig
[i
]))
468 new_initval
[i
] = initval
[i
];
470 w
->attributes
.at("\\init") = new_initval
;
477 struct WreducePass
: public Pass
{
478 WreducePass() : Pass("wreduce", "reduce the word size of operations if possible") { }
479 void help() YS_OVERRIDE
481 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
483 log(" wreduce [options] [selection]\n");
485 log("This command reduces the word size of operations. For example it will replace\n");
486 log("the 32 bit adders in the following code with adders of more appropriate widths:\n");
488 log(" module test(input [3:0] a, b, c, output [7:0] y);\n");
489 log(" assign y = a + b + c + 1;\n");
495 log(" Do not change the width of memory address ports. Use this options in\n");
496 log(" flows that use the 'memory_memx' pass.\n");
499 void execute(std::vector
<std::string
> args
, Design
*design
) YS_OVERRIDE
501 WreduceConfig config
;
502 bool opt_memx
= false;
504 log_header(design
, "Executing WREDUCE pass (reducing word size of cells).\n");
507 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
508 if (args
[argidx
] == "-memx") {
514 extra_args(args
, argidx
, design
);
516 for (auto module
: design
->selected_modules())
518 if (module
->has_processes_warn())
521 for (auto c
: module
->selected_cells())
523 if (c
->type
.in("$reduce_and", "$reduce_or", "$reduce_xor", "$reduce_xnor", "$reduce_bool",
524 "$lt", "$le", "$eq", "$ne", "$eqx", "$nex", "$ge", "$gt",
525 "$logic_not", "$logic_and", "$logic_or") && GetSize(c
->getPort("\\Y")) > 1) {
526 SigSpec sig
= c
->getPort("\\Y");
527 if (!sig
.has_const()) {
528 c
->setPort("\\Y", sig
[0]);
529 c
->setParam("\\Y_WIDTH", 1);
531 module
->connect(sig
, Const(0, GetSize(sig
)));
535 if (c
->type
.in("$div", "$mod", "$pow"))
537 SigSpec A
= c
->getPort("\\A");
538 int original_a_width
= GetSize(A
);
539 if (c
->getParam("\\A_SIGNED").as_bool()) {
540 while (GetSize(A
) > 1 && A
[GetSize(A
)-1] == State::S0
&& A
[GetSize(A
)-2] == State::S0
)
541 A
.remove(GetSize(A
)-1, 1);
543 while (GetSize(A
) > 0 && A
[GetSize(A
)-1] == State::S0
)
544 A
.remove(GetSize(A
)-1, 1);
546 if (original_a_width
!= GetSize(A
)) {
547 log("Removed top %d bits (of %d) from port A of cell %s.%s (%s).\n",
548 original_a_width
-GetSize(A
), original_a_width
, log_id(module
), log_id(c
), log_id(c
->type
));
549 c
->setPort("\\A", A
);
550 c
->setParam("\\A_WIDTH", GetSize(A
));
553 SigSpec B
= c
->getPort("\\B");
554 int original_b_width
= GetSize(B
);
555 if (c
->getParam("\\B_SIGNED").as_bool()) {
556 while (GetSize(B
) > 1 && B
[GetSize(B
)-1] == State::S0
&& B
[GetSize(B
)-2] == State::S0
)
557 B
.remove(GetSize(B
)-1, 1);
559 while (GetSize(B
) > 0 && B
[GetSize(B
)-1] == State::S0
)
560 B
.remove(GetSize(B
)-1, 1);
562 if (original_b_width
!= GetSize(B
)) {
563 log("Removed top %d bits (of %d) from port B of cell %s.%s (%s).\n",
564 original_b_width
-GetSize(B
), original_b_width
, log_id(module
), log_id(c
), log_id(c
->type
));
565 c
->setPort("\\B", B
);
566 c
->setParam("\\B_WIDTH", GetSize(B
));
570 if (!opt_memx
&& c
->type
.in("$memrd", "$memwr", "$meminit")) {
571 IdString memid
= c
->getParam("\\MEMID").decode_string();
572 RTLIL::Memory
*mem
= module
->memories
.at(memid
);
573 if (mem
->start_offset
>= 0) {
574 int cur_addrbits
= c
->getParam("\\ABITS").as_int();
575 int max_addrbits
= ceil_log2(mem
->start_offset
+ mem
->size
);
576 if (cur_addrbits
> max_addrbits
) {
577 log("Removed top %d address bits (of %d) from memory %s port %s.%s (%s).\n",
578 cur_addrbits
-max_addrbits
, cur_addrbits
,
579 c
->type
== "$memrd" ? "read" : c
->type
== "$memwr" ? "write" : "init",
580 log_id(module
), log_id(c
), log_id(memid
));
581 c
->setParam("\\ABITS", max_addrbits
);
582 c
->setPort("\\ADDR", c
->getPort("\\ADDR").extract(0, max_addrbits
));
588 WreduceWorker
worker(&config
, module
);
594 PRIVATE_NAMESPACE_END