714470ee5e6c4e58586874f3517d69bbae1e2b54
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
38 vector
<pair
<IdString
, Const
>> parameters
;
39 vector
<pair
<IdString
, int>> port_sizes
;
40 vector
<tuple
<IdString
, int, SigBit
>> connections
;
42 bool operator==(const merge_key_t
&other
) const {
43 return type
== other
.type
&& connections
== other
.connections
&&
44 parameters
== other
.parameters
&& port_sizes
== other
.port_sizes
;
47 unsigned int hash() const {
48 unsigned int h
= mkhash_init
;
49 h
= mkhash(h
, mkhash(type
));
50 h
= mkhash(h
, mkhash(parameters
));
51 h
= mkhash(h
, mkhash(connections
));
56 dict
<merge_key_t
, pool
<IdString
>> merge_cache
;
57 pool
<merge_key_t
> fwd_merge_cache
, bwd_merge_cache
;
59 void merge_cell_pair(Cell
*cell_a
, Cell
*cell_b
)
64 SigSpec inputs_a
, inputs_b
;
65 vector
<string
> input_names
;
67 for (auto &port_a
: cell_a
->connections())
69 SigSpec bits_a
= sigmap(port_a
.second
);
70 SigSpec bits_b
= sigmap(cell_b
->getPort(port_a
.first
));
72 log_assert(GetSize(bits_a
) == GetSize(bits_b
));
74 if (!cell_a
->output(port_a
.first
))
75 for (int i
= 0; i
< GetSize(bits_a
); i
++)
76 if (bits_a
[i
] != bits_b
[i
]) {
77 inputs_a
.append(bits_a
[i
]);
78 inputs_b
.append(bits_b
[i
]);
79 input_names
.push_back(GetSize(bits_a
) == 1 ? port_a
.first
.str() :
80 stringf("%s[%d]", log_id(port_a
.first
), i
));
84 for (int i
= 0; i
< GetSize(inputs_a
); i
++) {
85 SigBit bit_a
= inputs_a
[i
], bit_b
= inputs_b
[i
];
86 SigBit bit_y
= module
->addWire(NEW_ID
);
87 log(" New $equiv for input %s: A: %s, B: %s, Y: %s\n",
88 input_names
[i
].c_str(), log_signal(bit_a
), log_signal(bit_b
), log_signal(bit_y
));
89 module
->addEquiv(NEW_ID
, bit_a
, bit_b
, bit_y
);
90 merged_map
.add(bit_a
, bit_y
);
91 merged_map
.add(bit_b
, bit_y
);
94 std::vector
<IdString
> outport_names
, inport_names
;
96 for (auto &port_a
: cell_a
->connections())
97 if (cell_a
->output(port_a
.first
))
98 outport_names
.push_back(port_a
.first
);
100 inport_names
.push_back(port_a
.first
);
102 for (auto &pn
: inport_names
)
103 cell_a
->setPort(pn
, merged_map(sigmap(cell_a
->getPort(pn
))));
105 for (auto &pn
: outport_names
) {
106 SigSpec sig_a
= cell_a
->getPort(pn
);
107 SigSpec sig_b
= cell_b
->getPort(pn
);
108 module
->connect(sig_b
, sig_a
);
111 auto merged_attr
= cell_b
->get_strpool_attribute("\\equiv_merged");
112 merged_attr
.insert(log_id(cell_b
));
113 cell_a
->add_strpool_attribute("\\equiv_merged", merged_attr
);
114 module
->remove(cell_b
);
117 EquivStructWorker(Module
*module
, bool mode_fwd
, bool mode_icells
, int iter_num
) :
118 module(module
), sigmap(module
), equiv_bits(module
),
119 mode_fwd(mode_fwd
), mode_icells(mode_icells
), merge_count(0)
121 log(" Starting iteration %d.\n", iter_num
);
123 pool
<SigBit
> equiv_inputs
;
124 pool
<IdString
> cells
;
126 for (auto cell
: module
->selected_cells())
127 if (cell
->type
== "$equiv") {
128 SigBit sig_a
= sigmap(cell
->getPort("\\A").as_bit());
129 SigBit sig_b
= sigmap(cell
->getPort("\\B").as_bit());
130 equiv_bits
.add(sig_b
, sig_a
);
131 equiv_inputs
.insert(sig_a
);
132 equiv_inputs
.insert(sig_b
);
133 cells
.insert(cell
->name
);
135 if (mode_icells
|| module
->design
->module(cell
->type
))
136 cells
.insert(cell
->name
);
139 for (auto cell
: module
->selected_cells())
140 if (cell
->type
== "$equiv") {
141 SigBit sig_a
= sigmap(cell
->getPort("\\A").as_bit());
142 SigBit sig_b
= sigmap(cell
->getPort("\\B").as_bit());
143 SigBit sig_y
= sigmap(cell
->getPort("\\Y").as_bit());
144 if (sig_a
== sig_b
&& equiv_inputs
.count(sig_y
)) {
145 log(" Purging redundant $equiv cell %s.\n", log_id(cell
));
146 module
->connect(sig_y
, sig_a
);
147 module
->remove(cell
);
155 for (auto cell_name
: cells
)
158 vector
<tuple
<IdString
, int, SigBit
>> fwd_connections
;
160 Cell
*cell
= module
->cell(cell_name
);
161 key
.type
= cell
->type
;
163 for (auto &it
: cell
->parameters
)
164 key
.parameters
.push_back(it
);
165 std::sort(key
.parameters
.begin(), key
.parameters
.end());
167 for (auto &it
: cell
->connections())
168 key
.port_sizes
.push_back(make_pair(it
.first
, GetSize(it
.second
)));
169 std::sort(key
.port_sizes
.begin(), key
.port_sizes
.end());
171 for (auto &conn
: cell
->connections())
173 if (cell
->input(conn
.first
)) {
174 SigSpec sig
= sigmap(conn
.second
);
175 for (int i
= 0; i
< GetSize(sig
); i
++)
176 fwd_connections
.push_back(make_tuple(conn
.first
, i
, sig
[i
]));
179 if (cell
->output(conn
.first
)) {
180 SigSpec sig
= equiv_bits(conn
.second
);
181 for (int i
= 0; i
< GetSize(sig
); i
++) {
182 key
.connections
.clear();
183 key
.connections
.push_back(make_tuple(conn
.first
, i
, sig
[i
]));
185 if (merge_cache
.count(key
))
186 bwd_merge_cache
.insert(key
);
187 merge_cache
[key
].insert(cell_name
);
192 std::sort(fwd_connections
.begin(), fwd_connections
.end());
193 key
.connections
.swap(fwd_connections
);
195 if (merge_cache
.count(key
))
196 fwd_merge_cache
.insert(key
);
197 merge_cache
[key
].insert(cell_name
);
200 for (int phase
= 0; phase
< 2; phase
++)
202 auto &queue
= phase
? bwd_merge_cache
: fwd_merge_cache
;
204 for (auto &key
: queue
)
206 const char *strategy
= nullptr;
207 vector
<Cell
*> gold_cells
, gate_cells
, other_cells
;
208 vector
<pair
<Cell
*, Cell
*>> cell_pairs
;
211 for (auto cell_name
: merge_cache
[key
]) {
212 Cell
*c
= module
->cell(cell_name
);
214 string n
= cell_name
.str();
215 cells_type
= c
->type
;
216 if (GetSize(n
) > 5 && n
.substr(GetSize(n
)-5) == "_gold")
217 gold_cells
.push_back(c
);
218 else if (GetSize(n
) > 5 && n
.substr(GetSize(n
)-5) == "_gate")
219 gate_cells
.push_back(c
);
221 other_cells
.push_back(c
);
225 if (phase
&& cells_type
== "$equiv")
228 if (GetSize(gold_cells
) > 1 || GetSize(gate_cells
) > 1 || GetSize(other_cells
) > 1)
230 strategy
= "deduplicate";
231 for (int i
= 0; i
+1 < GetSize(gold_cells
); i
+= 2)
232 cell_pairs
.push_back(make_pair(gold_cells
[i
], gold_cells
[i
+1]));
233 for (int i
= 0; i
+1 < GetSize(gate_cells
); i
+= 2)
234 cell_pairs
.push_back(make_pair(gate_cells
[i
], gate_cells
[i
+1]));
235 for (int i
= 0; i
+1 < GetSize(other_cells
); i
+= 2)
236 cell_pairs
.push_back(make_pair(other_cells
[i
], other_cells
[i
+1]));
240 if (GetSize(gold_cells
) == 1 && GetSize(gate_cells
) == 1)
242 strategy
= "gold-gate-pairs";
243 cell_pairs
.push_back(make_pair(gold_cells
[0], gate_cells
[0]));
247 if (GetSize(gold_cells
) == 1 && GetSize(other_cells
) == 1)
249 strategy
= "gold-guess";
250 cell_pairs
.push_back(make_pair(gold_cells
[0], other_cells
[0]));
254 if (GetSize(other_cells
) == 1 && GetSize(gate_cells
) == 1)
256 strategy
= "gate-guess";
257 cell_pairs
.push_back(make_pair(other_cells
[0], gate_cells
[0]));
261 log_assert(GetSize(gold_cells
) + GetSize(gate_cells
) + GetSize(other_cells
) < 2);
265 int total_group_size
= GetSize(gold_cells
) + GetSize(gate_cells
) + GetSize(other_cells
);
266 log(" %s merging %d %s cells (from group of %d) using strategy %s:\n", phase
? "Bwd" : "Fwd",
267 2*GetSize(cell_pairs
), log_id(cells_type
), total_group_size
, strategy
);
268 for (auto it
: cell_pairs
) {
269 log(" Merging cells %s and %s.\n", log_id(it
.first
), log_id(it
.second
));
270 merge_cell_pair(it
.first
, it
.second
);
278 log(" Nothing to merge.\n");
282 struct EquivStructPass
: public Pass
{
283 EquivStructPass() : Pass("equiv_struct", "structural equivalence checking") { }
286 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
288 log(" equiv_struct [options] [selection]\n");
290 log("This command adds additional $equiv cells based on the assumption that the\n");
291 log("gold and gate circuit are structurally equivalent. Note that this can introduce\n");
292 log("bad $equiv cells in cases where the netlists are not structurally equivalent,\n");
293 log("for example when analyzing circuits with cells with commutative inputs. This\n");
294 log("command will also de-duplicate gates.\n");
297 log(" by default this command performans forward sweeps until nothing can\n");
298 log(" be merged by forwards sweeps, the backward sweeps until forward\n");
299 log(" sweeps are effective again. with this option set only forward sweeps\n");
300 log(" are performed.\n");
303 log(" by default, the internal RTL and gate cell types are ignored. add\n");
304 log(" this option to also process those cell types with this command.\n");
306 log(" -maxiter <N>\n");
307 log(" maximum number of iterations to run before aborting\n");
310 virtual void execute(std::vector
<std::string
> args
, Design
*design
)
312 bool mode_icells
= false;
313 bool mode_fwd
= false;
316 log_header("Executing EQUIV_STRUCT pass.\n");
319 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
320 if (args
[argidx
] == "-fwd") {
324 if (args
[argidx
] == "-icells") {
328 if (args
[argidx
] == "-maxiter" && argidx
+1 < args
.size()) {
329 max_iter
= atoi(args
[++argidx
].c_str());
334 extra_args(args
, argidx
, design
);
336 for (auto module
: design
->selected_modules()) {
337 int module_merge_count
= 0;
338 log("Running equiv_struct on module %s:\n", log_id(module
));
339 for (int iter
= 0;; iter
++) {
340 if (iter
== max_iter
) {
341 log(" Reached iteration limit of %d.\n", iter
);
344 EquivStructWorker
worker(module
, mode_fwd
, mode_icells
, iter
+1);
345 if (worker
.merge_count
== 0)
347 module_merge_count
+= worker
.merge_count
;
349 if (module_merge_count
)
350 log(" Performed a total of %d merges in module %s.\n", module_merge_count
, log_id(module
));
355 PRIVATE_NAMESPACE_END