2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Claire Xenia Wolf <claire@yosyshq.com>
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/ffinit.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/log.h"
24 #include "kernel/celltypes.h"
25 #include "libs/sha1/sha1.h"
32 PRIVATE_NAMESPACE_BEGIN
36 RTLIL::Design
*design
;
37 RTLIL::Module
*module
;
46 static void sort_pmux_conn(dict
<RTLIL::IdString
, RTLIL::SigSpec
> &conn
)
48 SigSpec sig_s
= conn
.at(ID::S
);
49 SigSpec sig_b
= conn
.at(ID::B
);
51 int s_width
= GetSize(sig_s
);
52 int width
= GetSize(sig_b
) / s_width
;
54 vector
<pair
<SigBit
, SigSpec
>> sb_pairs
;
55 for (int i
= 0; i
< s_width
; i
++)
56 sb_pairs
.push_back(pair
<SigBit
, SigSpec
>(sig_s
[i
], sig_b
.extract(i
*width
, width
)));
58 std::sort(sb_pairs
.begin(), sb_pairs
.end());
60 conn
[ID::S
] = SigSpec();
61 conn
[ID::B
] = SigSpec();
63 for (auto &it
: sb_pairs
) {
64 conn
[ID::S
].append(it
.first
);
65 conn
[ID::B
].append(it
.second
);
69 std::string
int_to_hash_string(unsigned int v
)
75 str
+= 'a' + (v
& 15);
81 std::string
hash_cell_parameters_and_connections(const RTLIL::Cell
*cell
)
83 vector
<string
> hash_conn_strings
;
84 std::string hash_string
= cell
->type
.str() + "\n";
86 const dict
<RTLIL::IdString
, RTLIL::SigSpec
> *conn
= &cell
->connections();
87 dict
<RTLIL::IdString
, RTLIL::SigSpec
> alt_conn
;
89 if (cell
->type
.in(ID($
and), ID($
or), ID($
xor), ID($xnor
), ID($add
), ID($mul
),
90 ID($logic_and
), ID($logic_or
), ID($_AND_
), ID($_OR_
), ID($_XOR_
))) {
92 if (assign_map(alt_conn
.at(ID::A
)) < assign_map(alt_conn
.at(ID::B
))) {
93 alt_conn
[ID::A
] = conn
->at(ID::B
);
94 alt_conn
[ID::B
] = conn
->at(ID::A
);
98 if (cell
->type
.in(ID($reduce_xor
), ID($reduce_xnor
))) {
100 assign_map
.apply(alt_conn
.at(ID::A
));
101 alt_conn
.at(ID::A
).sort();
104 if (cell
->type
.in(ID($reduce_and
), ID($reduce_or
), ID($reduce_bool
))) {
106 assign_map
.apply(alt_conn
.at(ID::A
));
107 alt_conn
.at(ID::A
).sort_and_unify();
110 if (cell
->type
== ID($pmux
)) {
112 assign_map
.apply(alt_conn
.at(ID::A
));
113 assign_map
.apply(alt_conn
.at(ID::B
));
114 assign_map
.apply(alt_conn
.at(ID::S
));
115 sort_pmux_conn(alt_conn
);
119 for (auto &it
: *conn
) {
121 if (cell
->output(it
.first
)) {
122 if (it
.first
== ID::Q
&& RTLIL::builtin_ff_cell_types().count(cell
->type
)) {
123 // For the 'Q' output of state elements,
124 // use its (* init *) attribute value
125 sig
= initvals(it
.second
);
131 sig
= assign_map(it
.second
);
132 string s
= "C " + it
.first
.str() + "=";
133 for (auto &chunk
: sig
.chunks()) {
135 s
+= "{" + chunk
.wire
->name
.str() + " " +
136 int_to_hash_string(chunk
.offset
) + " " +
137 int_to_hash_string(chunk
.width
) + "}";
139 s
+= RTLIL::Const(chunk
.data
).as_string();
141 hash_conn_strings
.push_back(s
+ "\n");
144 for (auto &it
: cell
->parameters
)
145 hash_conn_strings
.push_back("P " + it
.first
.str() + "=" + it
.second
.as_string() + "\n");
147 std::sort(hash_conn_strings
.begin(), hash_conn_strings
.end());
149 for (auto it
: hash_conn_strings
)
152 checksum
.update(hash_string
);
153 return checksum
.final();
156 bool compare_cell_parameters_and_connections(const RTLIL::Cell
*cell1
, const RTLIL::Cell
*cell2
)
158 log_assert(cell1
!= cell2
);
159 if (cell1
->type
!= cell2
->type
) return false;
161 if (cell1
->parameters
!= cell2
->parameters
)
164 if (cell1
->connections_
.size() != cell2
->connections_
.size())
166 for (const auto &it
: cell1
->connections_
)
167 if (!cell2
->connections_
.count(it
.first
))
170 decltype(Cell::connections_
) conn1
, conn2
;
171 conn1
.reserve(cell1
->connections_
.size());
172 conn2
.reserve(cell1
->connections_
.size());
174 for (const auto &it
: cell1
->connections_
) {
175 if (cell1
->output(it
.first
)) {
176 if (it
.first
== ID::Q
&& RTLIL::builtin_ff_cell_types().count(cell1
->type
)) {
177 // For the 'Q' output of state elements,
178 // use the (* init *) attribute value
179 conn1
[it
.first
] = initvals(it
.second
);
180 conn2
[it
.first
] = initvals(cell2
->getPort(it
.first
));
183 conn1
[it
.first
] = RTLIL::SigSpec();
184 conn2
[it
.first
] = RTLIL::SigSpec();
188 conn1
[it
.first
] = assign_map(it
.second
);
189 conn2
[it
.first
] = assign_map(cell2
->getPort(it
.first
));
193 if (cell1
->type
== ID($
and) || cell1
->type
== ID($
or) || cell1
->type
== ID($
xor) || cell1
->type
== ID($xnor
) || cell1
->type
== ID($add
) || cell1
->type
== ID($mul
) ||
194 cell1
->type
== ID($logic_and
) || cell1
->type
== ID($logic_or
) || cell1
->type
== ID($_AND_
) || cell1
->type
== ID($_OR_
) || cell1
->type
== ID($_XOR_
)) {
195 if (conn1
.at(ID::A
) < conn1
.at(ID::B
)) {
196 RTLIL::SigSpec tmp
= conn1
[ID::A
];
197 conn1
[ID::A
] = conn1
[ID::B
];
200 if (conn2
.at(ID::A
) < conn2
.at(ID::B
)) {
201 RTLIL::SigSpec tmp
= conn2
[ID::A
];
202 conn2
[ID::A
] = conn2
[ID::B
];
206 if (cell1
->type
== ID($reduce_xor
) || cell1
->type
== ID($reduce_xnor
)) {
210 if (cell1
->type
== ID($reduce_and
) || cell1
->type
== ID($reduce_or
) || cell1
->type
== ID($reduce_bool
)) {
211 conn1
[ID::A
].sort_and_unify();
212 conn2
[ID::A
].sort_and_unify();
214 if (cell1
->type
== ID($pmux
)) {
215 sort_pmux_conn(conn1
);
216 sort_pmux_conn(conn2
);
219 return conn1
== conn2
;
222 OptMergeWorker(RTLIL::Design
*design
, RTLIL::Module
*module
, bool mode_nomux
, bool mode_share_all
) :
223 design(design
), module(module
), assign_map(module
), mode_share_all(mode_share_all
)
226 ct
.setup_internals();
227 ct
.setup_internals_mem();
229 ct
.setup_stdcells_mem();
232 ct
.cell_types
.erase(ID($mux
));
233 ct
.cell_types
.erase(ID($pmux
));
236 ct
.cell_types
.erase(ID($tribuf
));
237 ct
.cell_types
.erase(ID($_TBUF_
));
238 ct
.cell_types
.erase(ID($anyseq
));
239 ct
.cell_types
.erase(ID($anyconst
));
240 ct
.cell_types
.erase(ID($allseq
));
241 ct
.cell_types
.erase(ID($allconst
));
243 log("Finding identical cells in module `%s'.\n", module
->name
.c_str());
244 assign_map
.set(module
);
246 initvals
.set(&assign_map
, module
);
248 bool did_something
= true;
249 while (did_something
)
251 std::vector
<RTLIL::Cell
*> cells
;
252 cells
.reserve(module
->cells_
.size());
253 for (auto &it
: module
->cells_
) {
254 if (!design
->selected(module
, it
.second
))
256 if (ct
.cell_known(it
.second
->type
) || (mode_share_all
&& it
.second
->known()))
257 cells
.push_back(it
.second
);
260 did_something
= false;
261 dict
<std::string
, RTLIL::Cell
*> sharemap
;
262 for (auto cell
: cells
)
264 if ((!mode_share_all
&& !ct
.cell_known(cell
->type
)) || !cell
->known())
267 auto hash
= hash_cell_parameters_and_connections(cell
);
268 auto r
= sharemap
.insert(std::make_pair(hash
, cell
));
270 if (compare_cell_parameters_and_connections(cell
, r
.first
->second
)) {
271 if (cell
->has_keep_attr()) {
272 if (r
.first
->second
->has_keep_attr())
274 std::swap(r
.first
->second
, cell
);
278 did_something
= true;
279 log_debug(" Cell `%s' is identical to cell `%s'.\n", cell
->name
.c_str(), r
.first
->second
->name
.c_str());
280 for (auto &it
: cell
->connections()) {
281 if (cell
->output(it
.first
)) {
282 RTLIL::SigSpec other_sig
= r
.first
->second
->getPort(it
.first
);
283 log_debug(" Redirecting output %s: %s = %s\n", it
.first
.c_str(),
284 log_signal(it
.second
), log_signal(other_sig
));
285 module
->connect(RTLIL::SigSig(it
.second
, other_sig
));
286 assign_map
.add(it
.second
, other_sig
);
288 if (it
.first
== ID::Q
&& RTLIL::builtin_ff_cell_types().count(cell
->type
))
289 initvals
.remove_init(it
.second
);
292 log_debug(" Removing %s cell `%s' from module `%s'.\n", cell
->type
.c_str(), cell
->name
.c_str(), module
->name
.c_str());
293 module
->remove(cell
);
304 struct OptMergePass
: public Pass
{
305 OptMergePass() : Pass("opt_merge", "consolidate identical cells") { }
308 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
310 log(" opt_merge [options] [selection]\n");
312 log("This pass identifies cells with identical type and input signals. Such cells\n");
313 log("are then merged to one cell.\n");
316 log(" Do not merge MUX cells.\n");
318 log(" -share_all\n");
319 log(" Operate on all cell types, not just built-in types.\n");
322 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) override
324 log_header(design
, "Executing OPT_MERGE pass (detect identical cells).\n");
326 bool mode_nomux
= false;
327 bool mode_share_all
= false;
330 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
331 std::string arg
= args
[argidx
];
332 if (arg
== "-nomux") {
336 if (arg
== "-share_all") {
337 mode_share_all
= true;
342 extra_args(args
, argidx
, design
);
345 for (auto module
: design
->selected_modules()) {
346 OptMergeWorker
worker(design
, module
, mode_nomux
, mode_share_all
);
347 total_count
+= worker
.total_count
;
351 design
->scratchpad_set_bool("opt.did_something", true);
352 log("Removed a total of %d cells.\n", total_count
);
356 PRIVATE_NAMESPACE_END