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
31 struct OptReduceWorker
33 RTLIL::Design
*design
;
34 RTLIL::Module
*module
;
40 void opt_reduce(pool
<RTLIL::Cell
*> &cells
, SigSet
<RTLIL::Cell
*> &drivers
, RTLIL::Cell
*cell
)
42 if (cells
.count(cell
) == 0)
46 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
47 pool
<RTLIL::SigBit
> new_sig_a_bits
;
49 for (auto &bit
: sig_a
.to_sigbit_set())
51 if (bit
== RTLIL::State::S0
) {
52 if (cell
->type
== "$reduce_and") {
53 new_sig_a_bits
.clear();
54 new_sig_a_bits
.insert(RTLIL::State::S0
);
59 if (bit
== RTLIL::State::S1
) {
60 if (cell
->type
== "$reduce_or") {
61 new_sig_a_bits
.clear();
62 new_sig_a_bits
.insert(RTLIL::State::S1
);
67 if (bit
.wire
== NULL
) {
68 new_sig_a_bits
.insert(bit
);
72 bool imported_children
= false;
73 for (auto child_cell
: drivers
.find(bit
)) {
74 if (child_cell
->type
== cell
->type
) {
75 opt_reduce(cells
, drivers
, child_cell
);
76 if (child_cell
->getPort("\\Y")[0] == bit
) {
77 pool
<RTLIL::SigBit
> child_sig_a_bits
= assign_map(child_cell
->getPort("\\A")).to_sigbit_pool();
78 new_sig_a_bits
.insert(child_sig_a_bits
.begin(), child_sig_a_bits
.end());
80 new_sig_a_bits
.insert(RTLIL::State::S0
);
81 imported_children
= true;
84 if (!imported_children
)
85 new_sig_a_bits
.insert(bit
);
88 RTLIL::SigSpec
new_sig_a(new_sig_a_bits
);
90 if (new_sig_a
!= sig_a
|| sig_a
.size() != cell
->getPort("\\A").size()) {
91 log(" New input vector for %s cell %s: %s\n", cell
->type
.c_str(), cell
->name
.c_str(), log_signal(new_sig_a
));
96 cell
->setPort("\\A", new_sig_a
);
97 cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(new_sig_a
.size());
101 void opt_mux(RTLIL::Cell
*cell
)
103 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort("\\A"));
104 RTLIL::SigSpec sig_b
= assign_map(cell
->getPort("\\B"));
105 RTLIL::SigSpec sig_s
= assign_map(cell
->getPort("\\S"));
107 RTLIL::SigSpec new_sig_b
, new_sig_s
;
108 pool
<RTLIL::SigSpec
> handled_sig
;
110 handled_sig
.insert(sig_a
);
111 for (int i
= 0; i
< sig_s
.size(); i
++)
113 RTLIL::SigSpec this_b
= sig_b
.extract(i
*sig_a
.size(), sig_a
.size());
114 if (handled_sig
.count(this_b
) > 0)
117 RTLIL::SigSpec this_s
= sig_s
.extract(i
, 1);
118 for (int j
= i
+1; j
< sig_s
.size(); j
++) {
119 RTLIL::SigSpec that_b
= sig_b
.extract(j
*sig_a
.size(), sig_a
.size());
120 if (this_b
== that_b
)
121 this_s
.append(sig_s
.extract(j
, 1));
124 if (this_s
.size() > 1)
126 RTLIL::Cell
*reduce_or_cell
= module
->addCell(NEW_ID
, "$reduce_or");
127 reduce_or_cell
->setPort("\\A", this_s
);
128 reduce_or_cell
->parameters
["\\A_SIGNED"] = RTLIL::Const(0);
129 reduce_or_cell
->parameters
["\\A_WIDTH"] = RTLIL::Const(this_s
.size());
130 reduce_or_cell
->parameters
["\\Y_WIDTH"] = RTLIL::Const(1);
132 RTLIL::Wire
*reduce_or_wire
= module
->addWire(NEW_ID
);
133 this_s
= RTLIL::SigSpec(reduce_or_wire
);
134 reduce_or_cell
->setPort("\\Y", this_s
);
137 new_sig_b
.append(this_b
);
138 new_sig_s
.append(this_s
);
139 handled_sig
.insert(this_b
);
142 if (new_sig_s
.size() != sig_s
.size()) {
143 log(" New ctrl vector for %s cell %s: %s\n", cell
->type
.c_str(), cell
->name
.c_str(), log_signal(new_sig_s
));
144 did_something
= true;
148 if (new_sig_s
.size() == 0)
150 module
->connect(RTLIL::SigSig(cell
->getPort("\\Y"), cell
->getPort("\\A")));
151 assign_map
.add(cell
->getPort("\\Y"), cell
->getPort("\\A"));
152 module
->remove(cell
);
156 cell
->setPort("\\B", new_sig_b
);
157 cell
->setPort("\\S", new_sig_s
);
158 if (new_sig_s
.size() > 1) {
159 cell
->parameters
["\\S_WIDTH"] = RTLIL::Const(new_sig_s
.size());
162 cell
->parameters
.erase("\\S_WIDTH");
167 void opt_mux_bits(RTLIL::Cell
*cell
)
169 std::vector
<RTLIL::SigBit
> sig_a
= assign_map(cell
->getPort("\\A")).to_sigbit_vector();
170 std::vector
<RTLIL::SigBit
> sig_b
= assign_map(cell
->getPort("\\B")).to_sigbit_vector();
171 std::vector
<RTLIL::SigBit
> sig_y
= assign_map(cell
->getPort("\\Y")).to_sigbit_vector();
173 std::vector
<RTLIL::SigBit
> new_sig_y
;
174 RTLIL::SigSig old_sig_conn
;
176 std::vector
<std::vector
<RTLIL::SigBit
>> consolidated_in_tuples
;
177 std::map
<std::vector
<RTLIL::SigBit
>, RTLIL::SigBit
> consolidated_in_tuples_map
;
179 for (int i
= 0; i
< int(sig_y
.size()); i
++)
181 std::vector
<RTLIL::SigBit
> in_tuple
;
182 bool all_tuple_bits_same
= true;
184 in_tuple
.push_back(sig_a
.at(i
));
185 for (int j
= i
; j
< int(sig_b
.size()); j
+= int(sig_a
.size())) {
186 if (sig_b
.at(j
) != sig_a
.at(i
))
187 all_tuple_bits_same
= false;
188 in_tuple
.push_back(sig_b
.at(j
));
191 if (all_tuple_bits_same
)
193 old_sig_conn
.first
.append_bit(sig_y
.at(i
));
194 old_sig_conn
.second
.append_bit(sig_a
.at(i
));
196 else if (consolidated_in_tuples_map
.count(in_tuple
))
198 old_sig_conn
.first
.append_bit(sig_y
.at(i
));
199 old_sig_conn
.second
.append_bit(consolidated_in_tuples_map
.at(in_tuple
));
203 consolidated_in_tuples_map
[in_tuple
] = sig_y
.at(i
);
204 consolidated_in_tuples
.push_back(in_tuple
);
205 new_sig_y
.push_back(sig_y
.at(i
));
209 if (new_sig_y
.size() != sig_y
.size())
211 log(" Consolidated identical input bits for %s cell %s:\n", cell
->type
.c_str(), cell
->name
.c_str());
212 log(" Old ports: A=%s, B=%s, Y=%s\n", log_signal(cell
->getPort("\\A")),
213 log_signal(cell
->getPort("\\B")), log_signal(cell
->getPort("\\Y")));
215 cell
->setPort("\\A", RTLIL::SigSpec());
216 for (auto &in_tuple
: consolidated_in_tuples
) {
217 RTLIL::SigSpec new_a
= cell
->getPort("\\A");
218 new_a
.append(in_tuple
.at(0));
219 cell
->setPort("\\A", new_a
);
222 cell
->setPort("\\B", RTLIL::SigSpec());
223 for (int i
= 1; i
<= cell
->getPort("\\S").size(); i
++)
224 for (auto &in_tuple
: consolidated_in_tuples
) {
225 RTLIL::SigSpec new_b
= cell
->getPort("\\B");
226 new_b
.append(in_tuple
.at(i
));
227 cell
->setPort("\\B", new_b
);
230 cell
->parameters
["\\WIDTH"] = RTLIL::Const(new_sig_y
.size());
231 cell
->setPort("\\Y", new_sig_y
);
233 log(" New ports: A=%s, B=%s, Y=%s\n", log_signal(cell
->getPort("\\A")),
234 log_signal(cell
->getPort("\\B")), log_signal(cell
->getPort("\\Y")));
235 log(" New connections: %s = %s\n", log_signal(old_sig_conn
.first
), log_signal(old_sig_conn
.second
));
237 module
->connect(old_sig_conn
);
240 did_something
= true;
245 OptReduceWorker(RTLIL::Design
*design
, RTLIL::Module
*module
, bool do_fine
) :
246 design(design
), module(module
), assign_map(module
)
248 log(" Optimizing cells in module %s.\n", module
->name
.c_str());
251 did_something
= true;
253 SigPool mem_wren_sigs
;
254 for (auto &cell_it
: module
->cells_
) {
255 RTLIL::Cell
*cell
= cell_it
.second
;
256 if (cell
->type
== "$mem")
257 mem_wren_sigs
.add(assign_map(cell
->getPort("\\WR_EN")));
258 if (cell
->type
== "$memwr")
259 mem_wren_sigs
.add(assign_map(cell
->getPort("\\EN")));
261 for (auto &cell_it
: module
->cells_
) {
262 RTLIL::Cell
*cell
= cell_it
.second
;
263 if (cell
->type
== "$dff" && mem_wren_sigs
.check_any(assign_map(cell
->getPort("\\Q"))))
264 mem_wren_sigs
.add(assign_map(cell
->getPort("\\D")));
267 bool keep_expanding_mem_wren_sigs
= true;
268 while (keep_expanding_mem_wren_sigs
) {
269 keep_expanding_mem_wren_sigs
= false;
270 for (auto &cell_it
: module
->cells_
) {
271 RTLIL::Cell
*cell
= cell_it
.second
;
272 if (cell
->type
== "$mux" && mem_wren_sigs
.check_any(assign_map(cell
->getPort("\\Y")))) {
273 if (!mem_wren_sigs
.check_all(assign_map(cell
->getPort("\\A"))) ||
274 !mem_wren_sigs
.check_all(assign_map(cell
->getPort("\\B"))))
275 keep_expanding_mem_wren_sigs
= true;
276 mem_wren_sigs
.add(assign_map(cell
->getPort("\\A")));
277 mem_wren_sigs
.add(assign_map(cell
->getPort("\\B")));
282 while (did_something
)
284 did_something
= false;
286 // merge trees of reduce_* cells to one single cell and unify input vectors
287 // (only handle reduce_and and reduce_or for various reasons)
289 const char *type_list
[] = { "$reduce_or", "$reduce_and" };
290 for (auto type
: type_list
)
292 SigSet
<RTLIL::Cell
*> drivers
;
293 pool
<RTLIL::Cell
*> cells
;
295 for (auto &cell_it
: module
->cells_
) {
296 RTLIL::Cell
*cell
= cell_it
.second
;
297 if (cell
->type
!= type
|| !design
->selected(module
, cell
))
299 drivers
.insert(assign_map(cell
->getPort("\\Y")), cell
);
303 while (cells
.size() > 0) {
304 RTLIL::Cell
*cell
= *cells
.begin();
305 opt_reduce(cells
, drivers
, cell
);
309 // merge identical inputs on $mux and $pmux cells
311 std::vector
<RTLIL::Cell
*> cells
;
313 for (auto &it
: module
->cells_
)
314 if ((it
.second
->type
== "$mux" || it
.second
->type
== "$pmux") && design
->selected(module
, it
.second
))
315 cells
.push_back(it
.second
);
317 for (auto cell
: cells
)
319 // this optimization is to aggressive for most coarse-grain applications.
320 // but we always want it for multiplexers driving write enable ports.
321 if (do_fine
|| mem_wren_sigs
.check_any(assign_map(cell
->getPort("\\Y"))))
330 struct OptReducePass
: public Pass
{
331 OptReducePass() : Pass("opt_reduce", "simplify large MUXes and AND/OR gates") { }
332 void help() YS_OVERRIDE
334 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
336 log(" opt_reduce [options] [selection]\n");
338 log("This pass performs two interlinked optimizations:\n");
340 log("1. it consolidates trees of large AND gates or OR gates and eliminates\n");
341 log("duplicated inputs.\n");
343 log("2. it identifies duplicated inputs to MUXes and replaces them with a single\n");
344 log("input with the original control signals OR'ed together.\n");
347 log(" perform fine-grain optimizations\n");
350 log(" alias for -fine\n");
353 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
355 bool do_fine
= false;
357 log_header(design
, "Executing OPT_REDUCE pass (consolidate $*mux and $reduce_* inputs).\n");
360 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
361 if (args
[argidx
] == "-fine") {
365 if (args
[argidx
] == "-full") {
371 extra_args(args
, argidx
, design
);
374 for (auto module
: design
->selected_modules())
376 OptReduceWorker
worker(design
, module
, do_fine
);
377 total_count
+= worker
.total_count
;
378 if (worker
.total_count
== 0)
383 design
->scratchpad_set_bool("opt.did_something", true);
384 log("Performed a total of %d changes.\n", total_count
);
388 PRIVATE_NAMESPACE_END