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(ID::A
));
47 sig_a
.sort_and_unify();
48 pool
<RTLIL::SigBit
> new_sig_a_bits
;
50 for (auto &bit
: sig_a
)
52 if (bit
== RTLIL::State::S0
) {
53 if (cell
->type
== ID($reduce_and
)) {
54 new_sig_a_bits
.clear();
55 new_sig_a_bits
.insert(RTLIL::State::S0
);
60 if (bit
== RTLIL::State::S1
) {
61 if (cell
->type
== ID($reduce_or
)) {
62 new_sig_a_bits
.clear();
63 new_sig_a_bits
.insert(RTLIL::State::S1
);
68 if (bit
.wire
== NULL
) {
69 new_sig_a_bits
.insert(bit
);
73 bool imported_children
= false;
74 for (auto child_cell
: drivers
.find(bit
)) {
75 if (child_cell
->type
== cell
->type
) {
76 opt_reduce(cells
, drivers
, child_cell
);
77 if (child_cell
->getPort(ID::Y
)[0] == bit
) {
78 pool
<RTLIL::SigBit
> child_sig_a_bits
= assign_map(child_cell
->getPort(ID::A
)).to_sigbit_pool();
79 new_sig_a_bits
.insert(child_sig_a_bits
.begin(), child_sig_a_bits
.end());
81 new_sig_a_bits
.insert(RTLIL::State::S0
);
82 imported_children
= true;
85 if (!imported_children
)
86 new_sig_a_bits
.insert(bit
);
89 RTLIL::SigSpec
new_sig_a(new_sig_a_bits
);
90 new_sig_a
.sort_and_unify();
92 if (new_sig_a
!= sig_a
|| sig_a
.size() != cell
->getPort(ID::A
).size()) {
93 log(" New input vector for %s cell %s: %s\n", cell
->type
.c_str(), cell
->name
.c_str(), log_signal(new_sig_a
));
98 cell
->setPort(ID::A
, new_sig_a
);
99 cell
->parameters
[ID(A_WIDTH
)] = RTLIL::Const(new_sig_a
.size());
103 void opt_mux(RTLIL::Cell
*cell
)
105 RTLIL::SigSpec sig_a
= assign_map(cell
->getPort(ID::A
));
106 RTLIL::SigSpec sig_b
= assign_map(cell
->getPort(ID::B
));
107 RTLIL::SigSpec sig_s
= assign_map(cell
->getPort(ID(S
)));
109 RTLIL::SigSpec new_sig_b
, new_sig_s
;
110 pool
<RTLIL::SigSpec
> handled_sig
;
112 handled_sig
.insert(sig_a
);
113 for (int i
= 0; i
< sig_s
.size(); i
++)
115 RTLIL::SigSpec this_b
= sig_b
.extract(i
*sig_a
.size(), sig_a
.size());
116 if (handled_sig
.count(this_b
) > 0)
119 RTLIL::SigSpec this_s
= sig_s
.extract(i
, 1);
120 for (int j
= i
+1; j
< sig_s
.size(); j
++) {
121 RTLIL::SigSpec that_b
= sig_b
.extract(j
*sig_a
.size(), sig_a
.size());
122 if (this_b
== that_b
)
123 this_s
.append(sig_s
.extract(j
, 1));
126 if (this_s
.size() > 1)
128 RTLIL::Cell
*reduce_or_cell
= module
->addCell(NEW_ID
, ID($reduce_or
));
129 reduce_or_cell
->setPort(ID::A
, this_s
);
130 reduce_or_cell
->parameters
[ID(A_SIGNED
)] = RTLIL::Const(0);
131 reduce_or_cell
->parameters
[ID(A_WIDTH
)] = RTLIL::Const(this_s
.size());
132 reduce_or_cell
->parameters
[ID(Y_WIDTH
)] = RTLIL::Const(1);
134 RTLIL::Wire
*reduce_or_wire
= module
->addWire(NEW_ID
);
135 this_s
= RTLIL::SigSpec(reduce_or_wire
);
136 reduce_or_cell
->setPort(ID::Y
, this_s
);
139 new_sig_b
.append(this_b
);
140 new_sig_s
.append(this_s
);
141 handled_sig
.insert(this_b
);
144 if (new_sig_s
.size() != sig_s
.size()) {
145 log(" New ctrl vector for %s cell %s: %s\n", cell
->type
.c_str(), cell
->name
.c_str(), log_signal(new_sig_s
));
146 did_something
= true;
150 if (new_sig_s
.size() == 0)
152 module
->connect(RTLIL::SigSig(cell
->getPort(ID::Y
), cell
->getPort(ID::A
)));
153 assign_map
.add(cell
->getPort(ID::Y
), cell
->getPort(ID::A
));
154 module
->remove(cell
);
158 cell
->setPort(ID::B
, new_sig_b
);
159 cell
->setPort(ID(S
), new_sig_s
);
160 if (new_sig_s
.size() > 1) {
161 cell
->parameters
[ID(S_WIDTH
)] = RTLIL::Const(new_sig_s
.size());
163 cell
->type
= ID($mux
);
164 cell
->parameters
.erase(ID(S_WIDTH
));
169 void opt_mux_bits(RTLIL::Cell
*cell
)
171 std::vector
<RTLIL::SigBit
> sig_a
= assign_map(cell
->getPort(ID::A
)).to_sigbit_vector();
172 std::vector
<RTLIL::SigBit
> sig_b
= assign_map(cell
->getPort(ID::B
)).to_sigbit_vector();
173 std::vector
<RTLIL::SigBit
> sig_y
= assign_map(cell
->getPort(ID::Y
)).to_sigbit_vector();
175 std::vector
<RTLIL::SigBit
> new_sig_y
;
176 RTLIL::SigSig old_sig_conn
;
178 std::vector
<std::vector
<RTLIL::SigBit
>> consolidated_in_tuples
;
179 std::map
<std::vector
<RTLIL::SigBit
>, RTLIL::SigBit
> consolidated_in_tuples_map
;
181 for (int i
= 0; i
< int(sig_y
.size()); i
++)
183 std::vector
<RTLIL::SigBit
> in_tuple
;
184 bool all_tuple_bits_same
= true;
186 in_tuple
.push_back(sig_a
.at(i
));
187 for (int j
= i
; j
< int(sig_b
.size()); j
+= int(sig_a
.size())) {
188 if (sig_b
.at(j
) != sig_a
.at(i
))
189 all_tuple_bits_same
= false;
190 in_tuple
.push_back(sig_b
.at(j
));
193 if (all_tuple_bits_same
)
195 old_sig_conn
.first
.append_bit(sig_y
.at(i
));
196 old_sig_conn
.second
.append_bit(sig_a
.at(i
));
198 else if (consolidated_in_tuples_map
.count(in_tuple
))
200 old_sig_conn
.first
.append_bit(sig_y
.at(i
));
201 old_sig_conn
.second
.append_bit(consolidated_in_tuples_map
.at(in_tuple
));
205 consolidated_in_tuples_map
[in_tuple
] = sig_y
.at(i
);
206 consolidated_in_tuples
.push_back(in_tuple
);
207 new_sig_y
.push_back(sig_y
.at(i
));
211 if (new_sig_y
.size() != sig_y
.size())
213 log(" Consolidated identical input bits for %s cell %s:\n", cell
->type
.c_str(), cell
->name
.c_str());
214 log(" Old ports: A=%s, B=%s, Y=%s\n", log_signal(cell
->getPort(ID::A
)),
215 log_signal(cell
->getPort(ID::B
)), log_signal(cell
->getPort(ID::Y
)));
217 cell
->setPort(ID::A
, RTLIL::SigSpec());
218 for (auto &in_tuple
: consolidated_in_tuples
) {
219 RTLIL::SigSpec new_a
= cell
->getPort(ID::A
);
220 new_a
.append(in_tuple
.at(0));
221 cell
->setPort(ID::A
, new_a
);
224 cell
->setPort(ID::B
, RTLIL::SigSpec());
225 for (int i
= 1; i
<= cell
->getPort(ID(S
)).size(); i
++)
226 for (auto &in_tuple
: consolidated_in_tuples
) {
227 RTLIL::SigSpec new_b
= cell
->getPort(ID::B
);
228 new_b
.append(in_tuple
.at(i
));
229 cell
->setPort(ID::B
, new_b
);
232 cell
->parameters
[ID(WIDTH
)] = RTLIL::Const(new_sig_y
.size());
233 cell
->setPort(ID::Y
, new_sig_y
);
235 log(" New ports: A=%s, B=%s, Y=%s\n", log_signal(cell
->getPort(ID::A
)),
236 log_signal(cell
->getPort(ID::B
)), log_signal(cell
->getPort(ID::Y
)));
237 log(" New connections: %s = %s\n", log_signal(old_sig_conn
.first
), log_signal(old_sig_conn
.second
));
239 module
->connect(old_sig_conn
);
241 did_something
= true;
246 OptReduceWorker(RTLIL::Design
*design
, RTLIL::Module
*module
, bool do_fine
) :
247 design(design
), module(module
), assign_map(module
)
249 log(" Optimizing cells in module %s.\n", module
->name
.c_str());
252 did_something
= true;
254 SigPool mem_wren_sigs
;
255 for (auto &cell_it
: module
->cells_
) {
256 RTLIL::Cell
*cell
= cell_it
.second
;
257 if (cell
->type
== ID($mem
))
258 mem_wren_sigs
.add(assign_map(cell
->getPort(ID(WR_EN
))));
259 if (cell
->type
== ID($memwr
))
260 mem_wren_sigs
.add(assign_map(cell
->getPort(ID(EN
))));
262 for (auto &cell_it
: module
->cells_
) {
263 RTLIL::Cell
*cell
= cell_it
.second
;
264 if (cell
->type
== ID($dff
) && mem_wren_sigs
.check_any(assign_map(cell
->getPort(ID(Q
)))))
265 mem_wren_sigs
.add(assign_map(cell
->getPort(ID(D
))));
268 bool keep_expanding_mem_wren_sigs
= true;
269 while (keep_expanding_mem_wren_sigs
) {
270 keep_expanding_mem_wren_sigs
= false;
271 for (auto &cell_it
: module
->cells_
) {
272 RTLIL::Cell
*cell
= cell_it
.second
;
273 if (cell
->type
== ID($mux
) && mem_wren_sigs
.check_any(assign_map(cell
->getPort(ID::Y
)))) {
274 if (!mem_wren_sigs
.check_all(assign_map(cell
->getPort(ID::A
))) ||
275 !mem_wren_sigs
.check_all(assign_map(cell
->getPort(ID::B
))))
276 keep_expanding_mem_wren_sigs
= true;
277 mem_wren_sigs
.add(assign_map(cell
->getPort(ID::A
)));
278 mem_wren_sigs
.add(assign_map(cell
->getPort(ID::B
)));
283 while (did_something
)
285 did_something
= false;
287 // merge trees of reduce_* cells to one single cell and unify input vectors
288 // (only handle reduce_and and reduce_or for various reasons)
290 const IdString type_list
[] = { ID($reduce_or
), ID($reduce_and
) };
291 for (auto type
: type_list
)
293 SigSet
<RTLIL::Cell
*> drivers
;
294 pool
<RTLIL::Cell
*> cells
;
296 for (auto &cell_it
: module
->cells_
) {
297 RTLIL::Cell
*cell
= cell_it
.second
;
298 if (cell
->type
!= type
|| !design
->selected(module
, cell
))
300 drivers
.insert(assign_map(cell
->getPort(ID::Y
)), cell
);
304 while (cells
.size() > 0) {
305 RTLIL::Cell
*cell
= *cells
.begin();
306 opt_reduce(cells
, drivers
, cell
);
310 // merge identical inputs on $mux and $pmux cells
312 std::vector
<RTLIL::Cell
*> cells
;
314 for (auto &it
: module
->cells_
)
315 if ((it
.second
->type
== ID($mux
) || it
.second
->type
== ID($pmux
)) && design
->selected(module
, it
.second
))
316 cells
.push_back(it
.second
);
318 for (auto cell
: cells
)
320 // this optimization is to aggressive for most coarse-grain applications.
321 // but we always want it for multiplexers driving write enable ports.
322 if (do_fine
|| mem_wren_sigs
.check_any(assign_map(cell
->getPort(ID::Y
))))
333 struct OptReducePass
: public Pass
{
334 OptReducePass() : Pass("opt_reduce", "simplify large MUXes and AND/OR gates") { }
335 void help() YS_OVERRIDE
337 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
339 log(" opt_reduce [options] [selection]\n");
341 log("This pass performs two interlinked optimizations:\n");
343 log("1. it consolidates trees of large AND gates or OR gates and eliminates\n");
344 log("duplicated inputs.\n");
346 log("2. it identifies duplicated inputs to MUXes and replaces them with a single\n");
347 log("input with the original control signals OR'ed together.\n");
350 log(" perform fine-grain optimizations\n");
353 log(" alias for -fine\n");
356 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
358 bool do_fine
= false;
360 log_header(design
, "Executing OPT_REDUCE pass (consolidate $*mux and $reduce_* inputs).\n");
363 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
364 if (args
[argidx
] == "-fine") {
368 if (args
[argidx
] == "-full") {
374 extra_args(args
, argidx
, design
);
377 for (auto module
: design
->selected_modules())
379 OptReduceWorker
worker(design
, module
, do_fine
);
380 total_count
+= worker
.total_count
;
381 if (worker
.total_count
== 0)
386 design
->scratchpad_set_bool("opt.did_something", true);
387 log("Performed a total of %d changes.\n", total_count
);
391 PRIVATE_NAMESPACE_END