projects / yosys.git / blob
? search:


714470ee5e6c4e58586874f3517d69bbae1e2b54
[yosys.git] / passes / equiv / equiv_struct.cc
1 /*
2 * yosys -- Yosys Open SYnthesis Suite
3 *
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 *
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.
9 *
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.
17 *
18 */
19
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
22
23 USING_YOSYS_NAMESPACE
24 PRIVATE_NAMESPACE_BEGIN
25
26 struct EquivStructWorker
27 {
28 Module *module;
29 SigMap sigmap;
30 SigMap equiv_bits;
31 bool mode_fwd;
32 bool mode_icells;
33 int merge_count;
34
35 struct merge_key_t
36 {
37 IdString type;
38 vector<pair<IdString, Const>> parameters;
39 vector<pair<IdString, int>> port_sizes;
40 vector<tuple<IdString, int, SigBit>> connections;
41
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;
45 }
46
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));
52 return h;
53 }
54 };
55
56 dict<merge_key_t, pool<IdString>> merge_cache;
57 pool<merge_key_t> fwd_merge_cache, bwd_merge_cache;
58
59 void merge_cell_pair(Cell *cell_a, Cell *cell_b)
60 {
61 SigMap merged_map;
62 merge_count++;
63
64 SigSpec inputs_a, inputs_b;
65 vector<string> input_names;
66
67 for (auto &port_a : cell_a->connections())
68 {
69 SigSpec bits_a = sigmap(port_a.second);
70 SigSpec bits_b = sigmap(cell_b->getPort(port_a.first));
71
72 log_assert(GetSize(bits_a) == GetSize(bits_b));
73
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));
81 }
82 }
83
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);
92 }
93
94 std::vector<IdString> outport_names, inport_names;
95
96 for (auto &port_a : cell_a->connections())
97 if (cell_a->output(port_a.first))
98 outport_names.push_back(port_a.first);
99 else
100 inport_names.push_back(port_a.first);
101
102 for (auto &pn : inport_names)
103 cell_a->setPort(pn, merged_map(sigmap(cell_a->getPort(pn))));
104
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);
109 }
110
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);
115 }
116
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)
120 {
121 log(" Starting iteration %d.\n", iter_num);
122
123 pool<SigBit> equiv_inputs;
124 pool<IdString> cells;
125
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);
134 } else {
135 if (mode_icells || module->design->module(cell->type))
136 cells.insert(cell->name);
137 }
138
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);
148 merge_count++;
149 }
150 }
151
152 if (merge_count > 0)
153 return;
154
155 for (auto cell_name : cells)
156 {
157 merge_key_t key;
158 vector<tuple<IdString, int, SigBit>> fwd_connections;
159
160 Cell *cell = module->cell(cell_name);
161 key.type = cell->type;
162
163 for (auto &it : cell->parameters)
164 key.parameters.push_back(it);
165 std::sort(key.parameters.begin(), key.parameters.end());
166
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());
170
171 for (auto &conn : cell->connections())
172 {
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]));
177 }
178
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]));
184
185 if (merge_cache.count(key))
186 bwd_merge_cache.insert(key);
187 merge_cache[key].insert(cell_name);
188 }
189 }
190 }
191
192 std::sort(fwd_connections.begin(), fwd_connections.end());
193 key.connections.swap(fwd_connections);
194
195 if (merge_cache.count(key))
196 fwd_merge_cache.insert(key);
197 merge_cache[key].insert(cell_name);
198 }
199
200 for (int phase = 0; phase < 2; phase++)
201 {
202 auto &queue = phase ? bwd_merge_cache : fwd_merge_cache;
203
204 for (auto &key : queue)
205 {
206 const char *strategy = nullptr;
207 vector<Cell*> gold_cells, gate_cells, other_cells;
208 vector<pair<Cell*, Cell*>> cell_pairs;
209 IdString cells_type;
210
211 for (auto cell_name : merge_cache[key]) {
212 Cell *c = module->cell(cell_name);
213 if (c != nullptr) {
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);
220 else
221 other_cells.push_back(c);
222 }
223 }
224
225 if (phase && cells_type == "$equiv")
226 continue;
227
228 if (GetSize(gold_cells) > 1 || GetSize(gate_cells) > 1 || GetSize(other_cells) > 1)
229 {
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]));
237 goto run_strategy;
238 }
239
240 if (GetSize(gold_cells) == 1 && GetSize(gate_cells) == 1)
241 {
242 strategy = "gold-gate-pairs";
243 cell_pairs.push_back(make_pair(gold_cells[0], gate_cells[0]));
244 goto run_strategy;
245 }
246
247 if (GetSize(gold_cells) == 1 && GetSize(other_cells) == 1)
248 {
249 strategy = "gold-guess";
250 cell_pairs.push_back(make_pair(gold_cells[0], other_cells[0]));
251 goto run_strategy;
252 }
253
254 if (GetSize(other_cells) == 1 && GetSize(gate_cells) == 1)
255 {
256 strategy = "gate-guess";
257 cell_pairs.push_back(make_pair(other_cells[0], gate_cells[0]));
258 goto run_strategy;
259 }
260
261 log_assert(GetSize(gold_cells) + GetSize(gate_cells) + GetSize(other_cells) < 2);
262 continue;
263
264 run_strategy:
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);
271 }
272 }
273
274 if (merge_count > 0)
275 return;
276 }
277
278 log(" Nothing to merge.\n");
279 }
280 };
281
282 struct EquivStructPass : public Pass {
283 EquivStructPass() : Pass("equiv_struct", "structural equivalence checking") { }
284 virtual void help()
285 {
286 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
287 log("\n");
288 log(" equiv_struct [options] [selection]\n");
289 log("\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");
295 log("\n");
296 log(" -fwd\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");
301 log("\n");
302 log(" -icells\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");
305 log("\n");
306 log(" -maxiter <N>\n");
307 log(" maximum number of iterations to run before aborting\n");
308 log("\n");
309 }
310 virtual void execute(std::vector<std::string> args, Design *design)
311 {
312 bool mode_icells = false;
313 bool mode_fwd = false;
314 int max_iter = -1;
315
316 log_header("Executing EQUIV_STRUCT pass.\n");
317
318 size_t argidx;
319 for (argidx = 1; argidx < args.size(); argidx++) {
320 if (args[argidx] == "-fwd") {
321 mode_fwd = true;
322 continue;
323 }
324 if (args[argidx] == "-icells") {
325 mode_icells = true;
326 continue;
327 }
328 if (args[argidx] == "-maxiter" && argidx+1 < args.size()) {
329 max_iter = atoi(args[++argidx].c_str());
330 continue;
331 }
332 break;
333 }
334 extra_args(args, argidx, design);
335
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);
342 break;
343 }
344 EquivStructWorker worker(module, mode_fwd, mode_icells, iter+1);
345 if (worker.merge_count == 0)
346 break;
347 module_merge_count += worker.merge_count;
348 }
349 if (module_merge_count)
350 log(" Performed a total of %d merges in module %s.\n", module_merge_count, log_id(module));
351 }
352 }
353 } EquivStructPass;
354
355 PRIVATE_NAMESPACE_END