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"
24 PRIVATE_NAMESPACE_BEGIN
26 struct EquivStructWorker
35 const pool
<IdString
> &fwonly_cells
;
40 vector
<pair
<IdString
, Const
>> parameters
;
41 vector
<pair
<IdString
, int>> port_sizes
;
42 vector
<tuple
<IdString
, int, SigBit
>> connections
;
44 bool operator==(const merge_key_t
&other
) const {
45 return type
== other
.type
&& connections
== other
.connections
&&
46 parameters
== other
.parameters
&& port_sizes
== other
.port_sizes
;
49 unsigned int hash() const {
50 unsigned int h
= mkhash_init
;
51 h
= mkhash(h
, mkhash(type
));
52 h
= mkhash(h
, mkhash(parameters
));
53 h
= mkhash(h
, mkhash(connections
));
58 dict
<merge_key_t
, pool
<IdString
>> merge_cache
;
59 pool
<merge_key_t
> fwd_merge_cache
, bwd_merge_cache
;
61 void merge_cell_pair(Cell
*cell_a
, Cell
*cell_b
)
66 SigSpec inputs_a
, inputs_b
;
67 vector
<string
> input_names
;
69 for (auto &port_a
: cell_a
->connections())
71 SigSpec bits_a
= sigmap(port_a
.second
);
72 SigSpec bits_b
= sigmap(cell_b
->getPort(port_a
.first
));
74 log_assert(GetSize(bits_a
) == GetSize(bits_b
));
76 if (!cell_a
->output(port_a
.first
))
77 for (int i
= 0; i
< GetSize(bits_a
); i
++)
78 if (bits_a
[i
] != bits_b
[i
]) {
79 inputs_a
.append(bits_a
[i
]);
80 inputs_b
.append(bits_b
[i
]);
81 input_names
.push_back(GetSize(bits_a
) == 1 ? port_a
.first
.str() :
82 stringf("%s[%d]", log_id(port_a
.first
), i
));
86 for (int i
= 0; i
< GetSize(inputs_a
); i
++) {
87 SigBit bit_a
= inputs_a
[i
], bit_b
= inputs_b
[i
];
88 SigBit bit_y
= module
->addWire(NEW_ID
);
89 log(" New $equiv for input %s: A: %s, B: %s, Y: %s\n",
90 input_names
[i
].c_str(), log_signal(bit_a
), log_signal(bit_b
), log_signal(bit_y
));
91 module
->addEquiv(NEW_ID
, bit_a
, bit_b
, bit_y
);
92 merged_map
.add(bit_a
, bit_y
);
93 merged_map
.add(bit_b
, bit_y
);
96 std::vector
<IdString
> outport_names
, inport_names
;
98 for (auto &port_a
: cell_a
->connections())
99 if (cell_a
->output(port_a
.first
))
100 outport_names
.push_back(port_a
.first
);
102 inport_names
.push_back(port_a
.first
);
104 for (auto &pn
: inport_names
)
105 cell_a
->setPort(pn
, merged_map(sigmap(cell_a
->getPort(pn
))));
107 for (auto &pn
: outport_names
) {
108 SigSpec sig_a
= cell_a
->getPort(pn
);
109 SigSpec sig_b
= cell_b
->getPort(pn
);
110 module
->connect(sig_b
, sig_a
);
113 auto merged_attr
= cell_b
->get_strpool_attribute(ID::equiv_merged
);
114 merged_attr
.insert(log_id(cell_b
));
115 cell_a
->add_strpool_attribute(ID::equiv_merged
, merged_attr
);
116 module
->remove(cell_b
);
119 EquivStructWorker(Module
*module
, bool mode_fwd
, bool mode_icells
, const pool
<IdString
> &fwonly_cells
, int iter_num
) :
120 module(module
), sigmap(module
), equiv_bits(module
),
121 mode_fwd(mode_fwd
), mode_icells(mode_icells
), merge_count(0), fwonly_cells(fwonly_cells
)
123 log(" Starting iteration %d.\n", iter_num
);
125 pool
<SigBit
> equiv_inputs
;
126 pool
<IdString
> cells
;
128 for (auto cell
: module
->selected_cells())
129 if (cell
->type
== ID($equiv
)) {
130 SigBit sig_a
= sigmap(cell
->getPort(ID::A
).as_bit());
131 SigBit sig_b
= sigmap(cell
->getPort(ID::B
).as_bit());
132 equiv_bits
.add(sig_b
, sig_a
);
133 equiv_inputs
.insert(sig_a
);
134 equiv_inputs
.insert(sig_b
);
135 cells
.insert(cell
->name
);
137 if (mode_icells
|| module
->design
->module(cell
->type
))
138 cells
.insert(cell
->name
);
141 for (auto cell
: module
->selected_cells())
142 if (cell
->type
== ID($equiv
)) {
143 SigBit sig_a
= sigmap(cell
->getPort(ID::A
).as_bit());
144 SigBit sig_b
= sigmap(cell
->getPort(ID::B
).as_bit());
145 SigBit sig_y
= sigmap(cell
->getPort(ID::Y
).as_bit());
146 if (sig_a
== sig_b
&& equiv_inputs
.count(sig_y
)) {
147 log(" Purging redundant $equiv cell %s.\n", log_id(cell
));
148 module
->connect(sig_y
, sig_a
);
149 module
->remove(cell
);
157 for (auto cell_name
: cells
)
160 vector
<tuple
<IdString
, int, SigBit
>> fwd_connections
;
162 Cell
*cell
= module
->cell(cell_name
);
163 key
.type
= cell
->type
;
165 for (auto &it
: cell
->parameters
)
166 key
.parameters
.push_back(it
);
167 std::sort(key
.parameters
.begin(), key
.parameters
.end());
169 for (auto &it
: cell
->connections())
170 key
.port_sizes
.push_back(make_pair(it
.first
, GetSize(it
.second
)));
171 std::sort(key
.port_sizes
.begin(), key
.port_sizes
.end());
173 for (auto &conn
: cell
->connections())
175 if (cell
->input(conn
.first
)) {
176 SigSpec sig
= sigmap(conn
.second
);
177 for (int i
= 0; i
< GetSize(sig
); i
++)
178 fwd_connections
.push_back(make_tuple(conn
.first
, i
, sig
[i
]));
181 if (cell
->output(conn
.first
)) {
182 SigSpec sig
= equiv_bits(conn
.second
);
183 for (int i
= 0; i
< GetSize(sig
); i
++) {
184 key
.connections
.clear();
185 key
.connections
.push_back(make_tuple(conn
.first
, i
, sig
[i
]));
187 if (merge_cache
.count(key
))
188 bwd_merge_cache
.insert(key
);
189 merge_cache
[key
].insert(cell_name
);
194 std::sort(fwd_connections
.begin(), fwd_connections
.end());
195 key
.connections
.swap(fwd_connections
);
197 if (merge_cache
.count(key
))
198 fwd_merge_cache
.insert(key
);
199 merge_cache
[key
].insert(cell_name
);
202 for (int phase
= 0; phase
< 2; phase
++)
204 auto &queue
= phase
? bwd_merge_cache
: fwd_merge_cache
;
206 for (auto &key
: queue
)
208 const char *strategy
= nullptr;
209 vector
<Cell
*> gold_cells
, gate_cells
, other_cells
;
210 vector
<pair
<Cell
*, Cell
*>> cell_pairs
;
213 for (auto cell_name
: merge_cache
[key
]) {
214 Cell
*c
= module
->cell(cell_name
);
216 string n
= cell_name
.str();
217 cells_type
= c
->type
;
218 if (GetSize(n
) > 5 && n
.compare(GetSize(n
)-5, std::string::npos
, "_gold") == 0)
219 gold_cells
.push_back(c
);
220 else if (GetSize(n
) > 5 && n
.compare(GetSize(n
)-5, std::string::npos
, "_gate") == 0)
221 gate_cells
.push_back(c
);
223 other_cells
.push_back(c
);
227 if (phase
&& fwonly_cells
.count(cells_type
))
230 if (GetSize(gold_cells
) > 1 || GetSize(gate_cells
) > 1 || GetSize(other_cells
) > 1)
232 strategy
= "deduplicate";
233 for (int i
= 0; i
+1 < GetSize(gold_cells
); i
+= 2)
234 cell_pairs
.push_back(make_pair(gold_cells
[i
], gold_cells
[i
+1]));
235 for (int i
= 0; i
+1 < GetSize(gate_cells
); i
+= 2)
236 cell_pairs
.push_back(make_pair(gate_cells
[i
], gate_cells
[i
+1]));
237 for (int i
= 0; i
+1 < GetSize(other_cells
); i
+= 2)
238 cell_pairs
.push_back(make_pair(other_cells
[i
], other_cells
[i
+1]));
242 if (GetSize(gold_cells
) == 1 && GetSize(gate_cells
) == 1)
244 strategy
= "gold-gate-pairs";
245 cell_pairs
.push_back(make_pair(gold_cells
[0], gate_cells
[0]));
249 if (GetSize(gold_cells
) == 1 && GetSize(other_cells
) == 1)
251 strategy
= "gold-guess";
252 cell_pairs
.push_back(make_pair(gold_cells
[0], other_cells
[0]));
256 if (GetSize(other_cells
) == 1 && GetSize(gate_cells
) == 1)
258 strategy
= "gate-guess";
259 cell_pairs
.push_back(make_pair(other_cells
[0], gate_cells
[0]));
263 log_assert(GetSize(gold_cells
) + GetSize(gate_cells
) + GetSize(other_cells
) < 2);
267 int total_group_size
= GetSize(gold_cells
) + GetSize(gate_cells
) + GetSize(other_cells
);
268 log(" %s merging %d %s cells (from group of %d) using strategy %s:\n", phase
? "Bwd" : "Fwd",
269 2*GetSize(cell_pairs
), log_id(cells_type
), total_group_size
, strategy
);
270 for (auto it
: cell_pairs
) {
271 log(" Merging cells %s and %s.\n", log_id(it
.first
), log_id(it
.second
));
272 merge_cell_pair(it
.first
, it
.second
);
280 log(" Nothing to merge.\n");
284 struct EquivStructPass
: public Pass
{
285 EquivStructPass() : Pass("equiv_struct", "structural equivalence checking") { }
286 void help() YS_OVERRIDE
288 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
290 log(" equiv_struct [options] [selection]\n");
292 log("This command adds additional $equiv cells based on the assumption that the\n");
293 log("gold and gate circuit are structurally equivalent. Note that this can introduce\n");
294 log("bad $equiv cells in cases where the netlists are not structurally equivalent,\n");
295 log("for example when analyzing circuits with cells with commutative inputs. This\n");
296 log("command will also de-duplicate gates.\n");
299 log(" by default this command performans forward sweeps until nothing can\n");
300 log(" be merged by forwards sweeps, then backward sweeps until forward\n");
301 log(" sweeps are effective again. with this option set only forward sweeps\n");
302 log(" are performed.\n");
304 log(" -fwonly <cell_type>\n");
305 log(" add the specified cell type to the list of cell types that are only\n");
306 log(" merged in forward sweeps and never in backward sweeps. $equiv is in\n");
307 log(" this list automatically.\n");
310 log(" by default, the internal RTL and gate cell types are ignored. add\n");
311 log(" this option to also process those cell types with this command.\n");
313 log(" -maxiter <N>\n");
314 log(" maximum number of iterations to run before aborting\n");
317 void execute(std::vector
<std::string
> args
, Design
*design
) YS_OVERRIDE
319 pool
<IdString
> fwonly_cells({ ID($equiv
) });
320 bool mode_icells
= false;
321 bool mode_fwd
= false;
324 log_header(design
, "Executing EQUIV_STRUCT pass.\n");
327 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
328 if (args
[argidx
] == "-fwd") {
332 if (args
[argidx
] == "-icells") {
336 if (args
[argidx
] == "-fwonly" && argidx
+1 < args
.size()) {
337 fwonly_cells
.insert(RTLIL::escape_id(args
[++argidx
]));
340 if (args
[argidx
] == "-maxiter" && argidx
+1 < args
.size()) {
341 max_iter
= atoi(args
[++argidx
].c_str());
346 extra_args(args
, argidx
, design
);
348 for (auto module
: design
->selected_modules()) {
349 int module_merge_count
= 0;
350 log("Running equiv_struct on module %s:\n", log_id(module
));
351 for (int iter
= 0;; iter
++) {
352 if (iter
== max_iter
) {
353 log(" Reached iteration limit of %d.\n", iter
);
356 EquivStructWorker
worker(module
, mode_fwd
, mode_icells
, fwonly_cells
, iter
+1);
357 if (worker
.merge_count
== 0)
359 module_merge_count
+= worker
.merge_count
;
361 if (module_merge_count
)
362 log(" Performed a total of %d merges in module %s.\n", module_merge_count
, log_id(module
));
367 PRIVATE_NAMESPACE_END