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"
24 #include "libs/sha1/sha1.h"
29 #define USE_CELL_HASH_CACHE
32 PRIVATE_NAMESPACE_BEGIN
36 RTLIL::Design
*design
;
37 RTLIL::Module
*module
;
44 #ifdef USE_CELL_HASH_CACHE
45 dict
<const RTLIL::Cell
*, std::string
> cell_hash_cache
;
48 static void sort_pmux_conn(dict
<RTLIL::IdString
, RTLIL::SigSpec
> &conn
)
50 SigSpec sig_s
= conn
.at("\\S");
51 SigSpec sig_b
= conn
.at("\\B");
53 int s_width
= GetSize(sig_s
);
54 int width
= GetSize(sig_b
) / s_width
;
56 vector
<pair
<SigBit
, SigSpec
>> sb_pairs
;
57 for (int i
= 0; i
< s_width
; i
++)
58 sb_pairs
.push_back(pair
<SigBit
, SigSpec
>(sig_s
[i
], sig_b
.extract(i
*width
, width
)));
60 std::sort(sb_pairs
.begin(), sb_pairs
.end());
62 conn
["\\S"] = SigSpec();
63 conn
["\\B"] = SigSpec();
65 for (auto &it
: sb_pairs
) {
66 conn
["\\S"].append(it
.first
);
67 conn
["\\B"].append(it
.second
);
71 #ifdef USE_CELL_HASH_CACHE
72 std::string
int_to_hash_string(unsigned int v
)
78 str
+= 'a' + (v
& 15);
84 std::string
hash_cell_parameters_and_connections(const RTLIL::Cell
*cell
)
86 if (cell_hash_cache
.count(cell
) > 0)
87 return cell_hash_cache
[cell
];
89 std::string hash_string
= cell
->type
.str() + "\n";
91 for (auto &it
: cell
->parameters
)
92 hash_string
+= "P " + it
.first
.str() + "=" + it
.second
.as_string() + "\n";
94 const dict
<RTLIL::IdString
, RTLIL::SigSpec
> *conn
= &cell
->connections();
95 dict
<RTLIL::IdString
, RTLIL::SigSpec
> alt_conn
;
97 if (cell
->type
== "$and" || cell
->type
== "$or" || cell
->type
== "$xor" || cell
->type
== "$xnor" || cell
->type
== "$add" || cell
->type
== "$mul" ||
98 cell
->type
== "$logic_and" || cell
->type
== "$logic_or" || cell
->type
== "$_AND_" || cell
->type
== "$_OR_" || cell
->type
== "$_XOR_") {
100 if (assign_map(alt_conn
.at("\\A")) < assign_map(alt_conn
.at("\\B"))) {
101 alt_conn
["\\A"] = conn
->at("\\B");
102 alt_conn
["\\B"] = conn
->at("\\A");
106 if (cell
->type
== "$reduce_xor" || cell
->type
== "$reduce_xnor") {
108 assign_map
.apply(alt_conn
.at("\\A"));
109 alt_conn
.at("\\A").sort();
112 if (cell
->type
== "$reduce_and" || cell
->type
== "$reduce_or" || cell
->type
== "$reduce_bool") {
114 assign_map
.apply(alt_conn
.at("\\A"));
115 alt_conn
.at("\\A").sort_and_unify();
118 if (cell
->type
== "$pmux") {
120 assign_map
.apply(alt_conn
.at("\\A"));
121 assign_map
.apply(alt_conn
.at("\\B"));
122 assign_map
.apply(alt_conn
.at("\\S"));
123 sort_pmux_conn(alt_conn
);
127 vector
<string
> hash_conn_strings
;
129 for (auto &it
: *conn
) {
130 if (cell
->output(it
.first
))
132 RTLIL::SigSpec sig
= it
.second
;
133 assign_map
.apply(sig
);
134 string s
= "C " + it
.first
.str() + "=";
135 for (auto &chunk
: sig
.chunks()) {
137 s
+= "{" + chunk
.wire
->name
.str() + " " +
138 int_to_hash_string(chunk
.offset
) + " " +
139 int_to_hash_string(chunk
.width
) + "}";
141 s
+= RTLIL::Const(chunk
.data
).as_string();
143 hash_conn_strings
.push_back(s
+ "\n");
146 std::sort(hash_conn_strings
.begin(), hash_conn_strings
.end());
148 for (auto it
: hash_conn_strings
)
151 cell_hash_cache
[cell
] = sha1(hash_string
);
152 return cell_hash_cache
[cell
];
156 bool compare_cell_parameters_and_connections(const RTLIL::Cell
*cell1
, const RTLIL::Cell
*cell2
, bool <
)
158 #ifdef USE_CELL_HASH_CACHE
159 std::string hash1
= hash_cell_parameters_and_connections(cell1
);
160 std::string hash2
= hash_cell_parameters_and_connections(cell2
);
162 if (hash1
!= hash2
) {
168 if (cell1
->parameters
!= cell2
->parameters
) {
169 std::map
<RTLIL::IdString
, RTLIL::Const
> p1(cell1
->parameters
.begin(), cell1
->parameters
.end());
170 std::map
<RTLIL::IdString
, RTLIL::Const
> p2(cell2
->parameters
.begin(), cell2
->parameters
.end());
175 dict
<RTLIL::IdString
, RTLIL::SigSpec
> conn1
= cell1
->connections();
176 dict
<RTLIL::IdString
, RTLIL::SigSpec
> conn2
= cell2
->connections();
178 for (auto &it
: conn1
) {
179 if (cell1
->output(it
.first
))
180 it
.second
= RTLIL::SigSpec();
182 assign_map
.apply(it
.second
);
185 for (auto &it
: conn2
) {
186 if (cell2
->output(it
.first
))
187 it
.second
= RTLIL::SigSpec();
189 assign_map
.apply(it
.second
);
192 if (cell1
->type
== "$and" || cell1
->type
== "$or" || cell1
->type
== "$xor" || cell1
->type
== "$xnor" || cell1
->type
== "$add" || cell1
->type
== "$mul" ||
193 cell1
->type
== "$logic_and" || cell1
->type
== "$logic_or" || cell1
->type
== "$_AND_" || cell1
->type
== "$_OR_" || cell1
->type
== "$_XOR_") {
194 if (conn1
.at("\\A") < conn1
.at("\\B")) {
195 RTLIL::SigSpec tmp
= conn1
["\\A"];
196 conn1
["\\A"] = conn1
["\\B"];
199 if (conn2
.at("\\A") < conn2
.at("\\B")) {
200 RTLIL::SigSpec tmp
= conn2
["\\A"];
201 conn2
["\\A"] = conn2
["\\B"];
205 if (cell1
->type
== "$reduce_xor" || cell1
->type
== "$reduce_xnor") {
209 if (cell1
->type
== "$reduce_and" || cell1
->type
== "$reduce_or" || cell1
->type
== "$reduce_bool") {
210 conn1
["\\A"].sort_and_unify();
211 conn2
["\\A"].sort_and_unify();
213 if (cell1
->type
== "$pmux") {
214 sort_pmux_conn(conn1
);
215 sort_pmux_conn(conn2
);
218 if (conn1
!= conn2
) {
219 std::map
<RTLIL::IdString
, RTLIL::SigSpec
> c1(conn1
.begin(), conn1
.end());
220 std::map
<RTLIL::IdString
, RTLIL::SigSpec
> c2(conn2
.begin(), conn2
.end());
225 if (cell1
->type
.substr(0, 1) == "$" && conn1
.count("\\Q") != 0) {
226 std::vector
<RTLIL::SigBit
> q1
= dff_init_map(cell1
->getPort("\\Q")).to_sigbit_vector();
227 std::vector
<RTLIL::SigBit
> q2
= dff_init_map(cell2
->getPort("\\Q")).to_sigbit_vector();
228 for (size_t i
= 0; i
< q1
.size(); i
++)
229 if ((q1
.at(i
).wire
== NULL
|| q2
.at(i
).wire
== NULL
) && q1
.at(i
) != q2
.at(i
)) {
230 lt
= q1
.at(i
) < q2
.at(i
);
238 bool compare_cells(const RTLIL::Cell
*cell1
, const RTLIL::Cell
*cell2
)
240 if (cell1
->type
!= cell2
->type
)
241 return cell1
->type
< cell2
->type
;
243 if ((!mode_share_all
&& !ct
.cell_known(cell1
->type
)) || !cell1
->known())
244 return cell1
< cell2
;
246 if (cell1
->has_keep_attr() || cell2
->has_keep_attr())
247 return cell1
< cell2
;
250 if (compare_cell_parameters_and_connections(cell1
, cell2
, lt
))
256 struct CompareCells
{
257 OptMergeWorker
*that
;
258 CompareCells(OptMergeWorker
*that
) : that(that
) {}
259 bool operator()(const RTLIL::Cell
*cell1
, const RTLIL::Cell
*cell2
) const {
260 return that
->compare_cells(cell1
, cell2
);
264 OptMergeWorker(RTLIL::Design
*design
, RTLIL::Module
*module
, bool mode_nomux
, bool mode_share_all
) :
265 design(design
), module(module
), assign_map(module
), mode_share_all(mode_share_all
)
268 ct
.setup_internals();
269 ct
.setup_internals_mem();
271 ct
.setup_stdcells_mem();
274 ct
.cell_types
.erase("$mux");
275 ct
.cell_types
.erase("$pmux");
278 ct
.cell_types
.erase("$tribuf");
279 ct
.cell_types
.erase("$_TBUF_");
280 ct
.cell_types
.erase("$anyseq");
281 ct
.cell_types
.erase("$anyconst");
282 ct
.cell_types
.erase("$allseq");
283 ct
.cell_types
.erase("$allconst");
285 log("Finding identical cells in module `%s'.\n", module
->name
.c_str());
286 assign_map
.set(module
);
288 dff_init_map
.set(module
);
289 for (auto &it
: module
->wires_
)
290 if (it
.second
->attributes
.count("\\init") != 0) {
291 Const initval
= it
.second
->attributes
.at("\\init");
292 for (int i
= 0; i
< GetSize(initval
) && i
< GetSize(it
.second
); i
++)
293 if (initval
[i
] == State::S0
|| initval
[i
] == State::S1
)
294 dff_init_map
.add(SigBit(it
.second
, i
), initval
[i
]);
297 bool did_something
= true;
298 while (did_something
)
300 #ifdef USE_CELL_HASH_CACHE
301 cell_hash_cache
.clear();
303 std::vector
<RTLIL::Cell
*> cells
;
304 cells
.reserve(module
->cells_
.size());
305 for (auto &it
: module
->cells_
) {
306 if (!design
->selected(module
, it
.second
))
308 if (ct
.cell_known(it
.second
->type
) || (mode_share_all
&& it
.second
->known()))
309 cells
.push_back(it
.second
);
312 did_something
= false;
313 std::map
<RTLIL::Cell
*, RTLIL::Cell
*, CompareCells
> sharemap(CompareCells(this));
314 for (auto cell
: cells
)
316 if (sharemap
.count(cell
) > 0) {
317 did_something
= true;
318 log_debug(" Cell `%s' is identical to cell `%s'.\n", cell
->name
.c_str(), sharemap
[cell
]->name
.c_str());
319 for (auto &it
: cell
->connections()) {
320 if (cell
->output(it
.first
)) {
321 RTLIL::SigSpec other_sig
= sharemap
[cell
]->getPort(it
.first
);
322 log_debug(" Redirecting output %s: %s = %s\n", it
.first
.c_str(),
323 log_signal(it
.second
), log_signal(other_sig
));
324 module
->connect(RTLIL::SigSig(it
.second
, other_sig
));
325 assign_map
.add(it
.second
, other_sig
);
328 log_debug(" Removing %s cell `%s' from module `%s'.\n", cell
->type
.c_str(), cell
->name
.c_str(), module
->name
.c_str());
329 #ifdef USE_CELL_HASH_CACHE
330 cell_hash_cache
.erase(cell
);
332 module
->remove(cell
);
335 sharemap
[cell
] = cell
;
344 struct OptMergePass
: public Pass
{
345 OptMergePass() : Pass("opt_merge", "consolidate identical cells") { }
346 void help() YS_OVERRIDE
348 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
350 log(" opt_merge [options] [selection]\n");
352 log("This pass identifies cells with identical type and input signals. Such cells\n");
353 log("are then merged to one cell.\n");
356 log(" Do not merge MUX cells.\n");
358 log(" -share_all\n");
359 log(" Operate on all cell types, not just built-in types.\n");
362 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
364 log_header(design
, "Executing OPT_MERGE pass (detect identical cells).\n");
366 bool mode_nomux
= false;
367 bool mode_share_all
= false;
370 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
371 std::string arg
= args
[argidx
];
372 if (arg
== "-nomux") {
376 if (arg
== "-share_all") {
377 mode_share_all
= true;
382 extra_args(args
, argidx
, design
);
385 for (auto module
: design
->selected_modules()) {
386 OptMergeWorker
worker(design
, module
, mode_nomux
, mode_share_all
);
387 total_count
+= worker
.total_count
;
391 design
->scratchpad_set_bool("opt.did_something", true);
392 log("Removed a total of %d cells.\n", total_count
);
396 PRIVATE_NAMESPACE_END