projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Merge pull request #1085 from YosysHQ/eddie/shregmap_improve
[yosys.git] / passes / sat / freduce.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/register.h"
21 #include "kernel/celltypes.h"
22 #include "kernel/consteval.h"
23 #include "kernel/sigtools.h"
24 #include "kernel/log.h"
25 #include "kernel/satgen.h"
26 #include <stdlib.h>
27 #include <stdio.h>
28 #include <string.h>
29 #include <algorithm>
30
31 USING_YOSYS_NAMESPACE
32 PRIVATE_NAMESPACE_BEGIN
33
34 bool inv_mode;
35 int verbose_level, reduce_counter, reduce_stop_at;
36 typedef std::map<RTLIL::SigBit, std::pair<RTLIL::Cell*, std::set<RTLIL::SigBit>>> drivers_t;
37 std::string dump_prefix;
38
39 struct equiv_bit_t
40 {
41 int depth;
42 bool inverted;
43 RTLIL::Cell *drv;
44 RTLIL::SigBit bit;
45
46 bool operator<(const equiv_bit_t &other) const {
47 if (depth != other.depth)
48 return depth < other.depth;
49 if (inverted != other.inverted)
50 return inverted < other.inverted;
51 if (drv != other.drv)
52 return drv < other.drv;
53 return bit < other.bit;
54 }
55 };
56
57 struct CountBitUsage
58 {
59 SigMap &sigmap;
60 std::map<RTLIL::SigBit, int> &cache;
61
62 CountBitUsage(SigMap &sigmap, std::map<RTLIL::SigBit, int> &cache) : sigmap(sigmap), cache(cache) { }
63
64 void operator()(RTLIL::SigSpec &sig) {
65 std::vector<RTLIL::SigBit> vec = sigmap(sig).to_sigbit_vector();
66 for (auto &bit : vec)
67 cache[bit]++;
68 }
69 };
70
71 struct FindReducedInputs
72 {
73 SigMap &sigmap;
74 drivers_t &drivers;
75
76 ezSatPtr ez;
77 std::set<RTLIL::Cell*> ez_cells;
78 SatGen satgen;
79
80 std::map<RTLIL::SigBit, int> sat_pi;
81 std::vector<int> sat_pi_uniq_bitvec;
82
83 FindReducedInputs(SigMap &sigmap, drivers_t &drivers) :
84 sigmap(sigmap), drivers(drivers), satgen(ez.get(), &sigmap)
85 {
86 satgen.model_undef = true;
87 }
88
89 int get_bits(int val)
90 {
91 int bits = 0;
92 for (int i = 8*sizeof(int); val; i = i >> 1)
93 if (val >> (i-1)) {
94 bits += i;
95 val = val >> i;
96 }
97 return bits;
98 }
99
100 void register_pi_bit(RTLIL::SigBit bit)
101 {
102 if (sat_pi.count(bit) != 0)
103 return;
104
105 satgen.setContext(&sigmap, "A");
106 int sat_a = satgen.importSigSpec(bit).front();
107 ez->assume(ez->NOT(satgen.importUndefSigSpec(bit).front()));
108
109 satgen.setContext(&sigmap, "B");
110 int sat_b = satgen.importSigSpec(bit).front();
111 ez->assume(ez->NOT(satgen.importUndefSigSpec(bit).front()));
112
113 int idx = sat_pi.size();
114 size_t idx_bits = get_bits(idx);
115
116 if (sat_pi_uniq_bitvec.size() != idx_bits) {
117 sat_pi_uniq_bitvec.push_back(ez->frozen_literal(stringf("uniq_%d", int(idx_bits)-1)));
118 for (auto &it : sat_pi)
119 ez->assume(ez->OR(ez->NOT(it.second), ez->NOT(sat_pi_uniq_bitvec.back())));
120 }
121 log_assert(sat_pi_uniq_bitvec.size() == idx_bits);
122
123 sat_pi[bit] = ez->frozen_literal(stringf("p, falsei_%s", log_signal(bit)));
124 ez->assume(ez->IFF(ez->XOR(sat_a, sat_b), sat_pi[bit]));
125
126 for (size_t i = 0; i < idx_bits; i++)
127 if ((idx & (1 << i)) == 0)
128 ez->assume(ez->OR(ez->NOT(sat_pi[bit]), ez->NOT(sat_pi_uniq_bitvec[i])));
129 else
130 ez->assume(ez->OR(ez->NOT(sat_pi[bit]), sat_pi_uniq_bitvec[i]));
131 }
132
133 void register_cone_worker(std::set<RTLIL::SigBit> &pi, std::set<RTLIL::SigBit> &sigdone, RTLIL::SigBit out)
134 {
135 if (out.wire == NULL)
136 return;
137 if (sigdone.count(out) != 0)
138 return;
139 sigdone.insert(out);
140
141 if (drivers.count(out) != 0) {
142 std::pair<RTLIL::Cell*, std::set<RTLIL::SigBit>> &drv = drivers.at(out);
143 if (ez_cells.count(drv.first) == 0) {
144 satgen.setContext(&sigmap, "A");
145 if (!satgen.importCell(drv.first))
146 log_error("Can't create SAT model for cell %s (%s)!\n", RTLIL::id2cstr(drv.first->name), RTLIL::id2cstr(drv.first->type));
147 satgen.setContext(&sigmap, "B");
148 if (!satgen.importCell(drv.first))
149 log_abort();
150 ez_cells.insert(drv.first);
151 }
152 for (auto &bit : drv.second)
153 register_cone_worker(pi, sigdone, bit);
154 } else {
155 register_pi_bit(out);
156 pi.insert(out);
157 }
158 }
159
160 void register_cone(std::vector<RTLIL::SigBit> &pi, RTLIL::SigBit out)
161 {
162 std::set<RTLIL::SigBit> pi_set, sigdone;
163 register_cone_worker(pi_set, sigdone, out);
164 pi.clear();
165 pi.insert(pi.end(), pi_set.begin(), pi_set.end());
166 }
167
168 void analyze(std::vector<RTLIL::SigBit> &reduced_inputs, RTLIL::SigBit output, int prec)
169 {
170 if (verbose_level >= 1)
171 log("[%2d%%] Analyzing input cone for signal %s:\n", prec, log_signal(output));
172
173 std::vector<RTLIL::SigBit> pi;
174 register_cone(pi, output);
175
176 if (verbose_level >= 1)
177 log(" Found %d input signals and %d cells.\n", int(pi.size()), int(ez_cells.size()));
178
179 satgen.setContext(&sigmap, "A");
180 int output_a = satgen.importSigSpec(output).front();
181 int output_undef_a = satgen.importUndefSigSpec(output).front();
182
183 satgen.setContext(&sigmap, "B");
184 int output_b = satgen.importSigSpec(output).front();
185 int output_undef_b = satgen.importUndefSigSpec(output).front();
186
187 std::set<int> unused_pi_idx;
188
189 for (size_t i = 0; i < pi.size(); i++)
190 unused_pi_idx.insert(i);
191
192 while (1)
193 {
194 std::vector<int> model_pi_idx;
195 std::vector<int> model_expr;
196 std::vector<bool> model;
197
198 for (size_t i = 0; i < pi.size(); i++)
199 if (unused_pi_idx.count(i) != 0) {
200 model_pi_idx.push_back(i);
201 model_expr.push_back(sat_pi.at(pi[i]));
202 }
203
204 if (!ez->solve(model_expr, model, ez->expression(ezSAT::OpOr, model_expr), ez->XOR(output_a, output_b), ez->NOT(output_undef_a), ez->NOT(output_undef_b)))
205 break;
206
207 int found_count = 0;
208 for (size_t i = 0; i < model_pi_idx.size(); i++)
209 if (model[i]) {
210 if (verbose_level >= 2)
211 log(" Found relevant input: %s\n", log_signal(pi[model_pi_idx[i]]));
212 unused_pi_idx.erase(model_pi_idx[i]);
213 found_count++;
214 }
215 log_assert(found_count == 1);
216 }
217
218 for (size_t i = 0; i < pi.size(); i++)
219 if (unused_pi_idx.count(i) == 0)
220 reduced_inputs.push_back(pi[i]);
221
222 if (verbose_level >= 1)
223 log(" Reduced input cone contains %d inputs.\n", int(reduced_inputs.size()));
224 }
225 };
226
227 struct PerformReduction
228 {
229 SigMap &sigmap;
230 drivers_t &drivers;
231 std::set<std::pair<RTLIL::SigBit, RTLIL::SigBit>> &inv_pairs;
232 pool<SigBit> recursion_guard;
233
234 ezSatPtr ez;
235 SatGen satgen;
236
237 std::vector<int> sat_pi, sat_out, sat_def;
238 std::vector<RTLIL::SigBit> out_bits, pi_bits;
239 std::vector<bool> out_inverted;
240 std::vector<int> out_depth;
241 int cone_size;
242
243 int register_cone_worker(std::set<RTLIL::Cell*> &celldone, std::map<RTLIL::SigBit, int> &sigdepth, RTLIL::SigBit out)
244 {
245 if (out.wire == NULL)
246 return 0;
247 if (sigdepth.count(out) != 0)
248 return sigdepth.at(out);
249
250 if (recursion_guard.count(out)) {
251 string loop_signals;
252 for (auto loop_bit : recursion_guard)
253 loop_signals += string(" ") + log_signal(loop_bit);
254 log_error("Found logic loop:%s\n", loop_signals.c_str());
255 }
256
257 recursion_guard.insert(out);
258
259 if (drivers.count(out) != 0) {
260 std::pair<RTLIL::Cell*, std::set<RTLIL::SigBit>> &drv = drivers.at(out);
261 if (celldone.count(drv.first) == 0) {
262 if (!satgen.importCell(drv.first))
263 log_error("Can't create SAT model for cell %s (%s)!\n", RTLIL::id2cstr(drv.first->name), RTLIL::id2cstr(drv.first->type));
264 celldone.insert(drv.first);
265 }
266 int max_child_depth = 0;
267 for (auto &bit : drv.second)
268 max_child_depth = max(register_cone_worker(celldone, sigdepth, bit), max_child_depth);
269 sigdepth[out] = max_child_depth + 1;
270 } else {
271 pi_bits.push_back(out);
272 sat_pi.push_back(satgen.importSigSpec(out).front());
273 ez->assume(ez->NOT(satgen.importUndefSigSpec(out).front()));
274 sigdepth[out] = 0;
275 }
276
277 recursion_guard.erase(out);
278 return sigdepth.at(out);
279 }
280
281 PerformReduction(SigMap &sigmap, drivers_t &drivers, std::set<std::pair<RTLIL::SigBit, RTLIL::SigBit>> &inv_pairs, std::vector<RTLIL::SigBit> &bits, int cone_size) :
282 sigmap(sigmap), drivers(drivers), inv_pairs(inv_pairs), satgen(ez.get(), &sigmap), out_bits(bits), cone_size(cone_size)
283 {
284 satgen.model_undef = true;
285
286 std::set<RTLIL::Cell*> celldone;
287 std::map<RTLIL::SigBit, int> sigdepth;
288
289 for (auto &bit : bits) {
290 out_depth.push_back(register_cone_worker(celldone, sigdepth, bit));
291 sat_out.push_back(satgen.importSigSpec(bit).front());
292 sat_def.push_back(ez->NOT(satgen.importUndefSigSpec(bit).front()));
293 }
294
295 if (inv_mode && cone_size > 0) {
296 if (!ez->solve(sat_out, out_inverted, ez->expression(ezSAT::OpAnd, sat_def)))
297 log_error("Solving for initial model failed!\n");
298 for (size_t i = 0; i < sat_out.size(); i++)
299 if (out_inverted.at(i))
300 sat_out[i] = ez->NOT(sat_out[i]);
301 } else
302 out_inverted = std::vector<bool>(sat_out.size(), false);
303 }
304
305 void analyze_const(std::vector<std::vector<equiv_bit_t>> &results, int idx)
306 {
307 if (verbose_level == 1)
308 log(" Finding const value for %s.\n", log_signal(out_bits[idx]));
309
310 bool can_be_set = ez->solve(ez->AND(sat_out[idx], sat_def[idx]));
311 bool can_be_clr = ez->solve(ez->AND(ez->NOT(sat_out[idx]), sat_def[idx]));
312 log_assert(!can_be_set || !can_be_clr);
313
314 RTLIL::SigBit value(RTLIL::State::Sx);
315 if (can_be_set)
316 value = RTLIL::State::S1;
317 if (can_be_clr)
318 value = RTLIL::State::S0;
319 if (verbose_level == 1)
320 log(" Constant value for this signal: %s\n", log_signal(value));
321
322 int result_idx = -1;
323 for (size_t i = 0; i < results.size(); i++) {
324 if (results[i].front().bit == value) {
325 result_idx = i;
326 break;
327 }
328 }
329
330 if (result_idx == -1) {
331 result_idx = results.size();
332 results.push_back(std::vector<equiv_bit_t>());
333 equiv_bit_t bit;
334 bit.depth = 0;
335 bit.inverted = false;
336 bit.drv = NULL;
337 bit.bit = value;
338 results.back().push_back(bit);
339 }
340
341 equiv_bit_t bit;
342 bit.depth = 1;
343 bit.inverted = false;
344 bit.drv = drivers.count(out_bits[idx]) ? drivers.at(out_bits[idx]).first : NULL;
345 bit.bit = out_bits[idx];
346 results[result_idx].push_back(bit);
347 }
348
349 void analyze(std::vector<std::set<int>> &results, std::map<int, int> &results_map, std::vector<int> &bucket, std::string indent1, std::string indent2)
350 {
351 std::string indent = indent1 + indent2;
352 const char *indt = indent.c_str();
353
354 if (bucket.size() <= 1)
355 return;
356
357 if (verbose_level == 1)
358 log("%s Trying to shatter bucket with %d signals.\n", indt, int(bucket.size()));
359
360 if (verbose_level > 1) {
361 std::vector<RTLIL::SigBit> bucket_sigbits;
362 for (int idx : bucket)
363 bucket_sigbits.push_back(out_bits[idx]);
364 log("%s Trying to shatter bucket with %d signals: %s\n", indt, int(bucket.size()), log_signal(bucket_sigbits));
365 }
366
367 std::vector<int> sat_set_list, sat_clr_list;
368 for (int idx : bucket) {
369 sat_set_list.push_back(ez->AND(sat_out[idx], sat_def[idx]));
370 sat_clr_list.push_back(ez->AND(ez->NOT(sat_out[idx]), sat_def[idx]));
371 }
372
373 std::vector<int> modelVars = sat_out;
374 std::vector<bool> model;
375
376 modelVars.insert(modelVars.end(), sat_def.begin(), sat_def.end());
377 if (verbose_level >= 2)
378 modelVars.insert(modelVars.end(), sat_pi.begin(), sat_pi.end());
379
380 if (ez->solve(modelVars, model, ez->expression(ezSAT::OpOr, sat_set_list), ez->expression(ezSAT::OpOr, sat_clr_list)))
381 {
382 int iter_count = 1;
383
384 while (1)
385 {
386 sat_set_list.clear();
387 sat_clr_list.clear();
388
389 std::vector<int> sat_def_list;
390
391 for (int idx : bucket)
392 if (!model[sat_out.size() + idx]) {
393 sat_set_list.push_back(ez->AND(sat_out[idx], sat_def[idx]));
394 sat_clr_list.push_back(ez->AND(ez->NOT(sat_out[idx]), sat_def[idx]));
395 } else {
396 sat_def_list.push_back(sat_def[idx]);
397 }
398
399 if (!ez->solve(modelVars, model, ez->expression(ezSAT::OpOr, sat_set_list), ez->expression(ezSAT::OpOr, sat_clr_list), ez->expression(ezSAT::OpAnd, sat_def_list)))
400 break;
401 iter_count++;
402 }
403
404 if (verbose_level >= 1) {
405 int count_set = 0, count_clr = 0, count_undef = 0;
406 for (int idx : bucket)
407 if (!model[sat_out.size() + idx])
408 count_undef++;
409 else if (model[idx])
410 count_set++;
411 else
412 count_clr++;
413 log("%s After %d iterations: %d set vs. %d clr vs %d undef\n", indt, iter_count, count_set, count_clr, count_undef);
414 }
415
416 if (verbose_level >= 2) {
417 for (size_t i = 0; i < pi_bits.size(); i++)
418 log("%s -> PI %c == %s\n", indt, model[2*sat_out.size() + i] ? '1' : '0', log_signal(pi_bits[i]));
419 for (int idx : bucket)
420 log("%s -> OUT %c == %s%s\n", indt, model[sat_out.size() + idx] ? model[idx] ? '1' : '0' : 'x',
421 out_inverted.at(idx) ? "~" : "", log_signal(out_bits[idx]));
422 }
423
424 std::vector<int> buckets_a;
425 std::vector<int> buckets_b;
426
427 for (int idx : bucket) {
428 if (!model[sat_out.size() + idx] || model[idx])
429 buckets_a.push_back(idx);
430 if (!model[sat_out.size() + idx] || !model[idx])
431 buckets_b.push_back(idx);
432 }
433 analyze(results, results_map, buckets_a, indent1 + ".", indent2 + " ");
434 analyze(results, results_map, buckets_b, indent1 + "x", indent2 + " ");
435 }
436 else
437 {
438 std::vector<int> undef_slaves;
439
440 for (int idx : bucket) {
441 std::vector<int> sat_def_list;
442 for (int idx2 : bucket)
443 if (idx != idx2)
444 sat_def_list.push_back(sat_def[idx2]);
445 if (ez->solve(ez->NOT(sat_def[idx]), ez->expression(ezSAT::OpOr, sat_def_list)))
446 undef_slaves.push_back(idx);
447 }
448
449 if (undef_slaves.size() == bucket.size()) {
450 if (verbose_level >= 1)
451 log("%s Complex undef overlap. None of the signals covers the others.\n", indt);
452 // FIXME: We could try to further shatter a group with complex undef overlaps
453 return;
454 }
455
456 for (int idx : undef_slaves)
457 out_depth[idx] = std::numeric_limits<int>::max();
458
459 if (verbose_level >= 1) {
460 log("%s Found %d equivalent signals:", indt, int(bucket.size()));
461 for (int idx : bucket)
462 log("%s%s%s", idx == bucket.front() ? " " : ", ", out_inverted[idx] ? "~" : "", log_signal(out_bits[idx]));
463 log("\n");
464 }
465
466 int result_idx = -1;
467 for (int idx : bucket) {
468 if (results_map.count(idx) == 0)
469 continue;
470 if (result_idx == -1) {
471 result_idx = results_map.at(idx);
472 continue;
473 }
474 int result_idx2 = results_map.at(idx);
475 results[result_idx].insert(results[result_idx2].begin(), results[result_idx2].end());
476 for (int idx2 : results[result_idx2])
477 results_map[idx2] = result_idx;
478 results[result_idx2].clear();
479 }
480
481 if (result_idx == -1) {
482 result_idx = results.size();
483 results.push_back(std::set<int>());
484 }
485
486 results[result_idx].insert(bucket.begin(), bucket.end());
487 }
488 }
489
490 void analyze(std::vector<std::vector<equiv_bit_t>> &results, int perc)
491 {
492 std::vector<int> bucket;
493 for (size_t i = 0; i < sat_out.size(); i++)
494 bucket.push_back(i);
495
496 std::vector<std::set<int>> results_buf;
497 std::map<int, int> results_map;
498 analyze(results_buf, results_map, bucket, stringf("[%2d%%] %d ", perc, cone_size), "");
499
500 for (auto &r : results_buf)
501 {
502 if (r.size() <= 1)
503 continue;
504
505 if (verbose_level >= 1) {
506 std::vector<RTLIL::SigBit> r_sigbits;
507 for (int idx : r)
508 r_sigbits.push_back(out_bits[idx]);
509 log(" Found group of %d equivalent signals: %s\n", int(r.size()), log_signal(r_sigbits));
510 }
511
512 std::vector<int> undef_slaves;
513
514 for (int idx : r) {
515 std::vector<int> sat_def_list;
516 for (int idx2 : r)
517 if (idx != idx2)
518 sat_def_list.push_back(sat_def[idx2]);
519 if (ez->solve(ez->NOT(sat_def[idx]), ez->expression(ezSAT::OpOr, sat_def_list)))
520 undef_slaves.push_back(idx);
521 }
522
523 if (undef_slaves.size() == bucket.size()) {
524 if (verbose_level >= 1)
525 log(" Complex undef overlap. None of the signals covers the others.\n");
526 // FIXME: We could try to further shatter a group with complex undef overlaps
527 return;
528 }
529
530 for (int idx : undef_slaves)
531 out_depth[idx] = std::numeric_limits<int>::max();
532
533 std::vector<equiv_bit_t> result;
534
535 for (int idx : r) {
536 equiv_bit_t bit;
537 bit.depth = out_depth[idx];
538 bit.inverted = out_inverted[idx];
539 bit.drv = drivers.count(out_bits[idx]) ? drivers.at(out_bits[idx]).first : NULL;
540 bit.bit = out_bits[idx];
541 result.push_back(bit);
542 }
543
544 std::sort(result.begin(), result.end());
545
546 if (result.front().inverted)
547 for (auto &bit : result)
548 bit.inverted = !bit.inverted;
549
550 for (size_t i = 1; i < result.size(); i++) {
551 std::pair<RTLIL::SigBit, RTLIL::SigBit> p(result[0].bit, result[i].bit);
552 if (inv_pairs.count(p) != 0)
553 result.erase(result.begin() + i);
554 }
555
556 if (result.size() > 1)
557 results.push_back(result);
558 }
559 }
560 };
561
562 struct FreduceWorker
563 {
564 RTLIL::Design *design;
565 RTLIL::Module *module;
566
567 SigMap sigmap;
568 drivers_t drivers;
569 std::set<std::pair<RTLIL::SigBit, RTLIL::SigBit>> inv_pairs;
570
571 FreduceWorker(RTLIL::Design *design, RTLIL::Module *module) : design(design), module(module), sigmap(module)
572 {
573 }
574
575 bool find_bit_in_cone(std::set<RTLIL::Cell*> &celldone, RTLIL::SigBit needle, RTLIL::SigBit haystack)
576 {
577 if (needle == haystack)
578 return true;
579 if (haystack.wire == NULL || needle.wire == NULL || drivers.count(haystack) == 0)
580 return false;
581
582 std::pair<RTLIL::Cell*, std::set<RTLIL::SigBit>> &drv = drivers.at(haystack);
583
584 if (celldone.count(drv.first))
585 return false;
586 celldone.insert(drv.first);
587
588 for (auto &bit : drv.second)
589 if (find_bit_in_cone(celldone, needle, bit))
590 return true;
591 return false;
592 }
593
594 bool find_bit_in_cone(RTLIL::SigBit needle, RTLIL::SigBit haystack)
595 {
596 std::set<RTLIL::Cell*> celldone;
597 return find_bit_in_cone(celldone, needle, haystack);
598 }
599
600 void dump()
601 {
602 std::string filename = stringf("%s_%s_%05d.il", dump_prefix.c_str(), RTLIL::id2cstr(module->name), reduce_counter);
603 log("%s Writing dump file `%s'.\n", reduce_counter ? " " : "", filename.c_str());
604 Pass::call(design, stringf("dump -outfile %s %s", filename.c_str(), design->selected_active_module.empty() ? module->name.c_str() : ""));
605 }
606
607 int run()
608 {
609 log("Running functional reduction on module %s:\n", RTLIL::id2cstr(module->name));
610
611 CellTypes ct;
612 ct.setup_internals();
613 ct.setup_stdcells();
614
615 int bits_full_total = 0;
616 std::vector<std::set<RTLIL::SigBit>> batches;
617 for (auto &it : module->wires_)
618 if (it.second->port_input) {
619 batches.push_back(sigmap(it.second).to_sigbit_set());
620 bits_full_total += it.second->width;
621 }
622 for (auto &it : module->cells_) {
623 if (ct.cell_known(it.second->type)) {
624 std::set<RTLIL::SigBit> inputs, outputs;
625 for (auto &port : it.second->connections()) {
626 std::vector<RTLIL::SigBit> bits = sigmap(port.second).to_sigbit_vector();
627 if (ct.cell_output(it.second->type, port.first))
628 outputs.insert(bits.begin(), bits.end());
629 else
630 inputs.insert(bits.begin(), bits.end());
631 }
632 std::pair<RTLIL::Cell*, std::set<RTLIL::SigBit>> drv(it.second, inputs);
633 for (auto &bit : outputs)
634 drivers[bit] = drv;
635 batches.push_back(outputs);
636 bits_full_total += outputs.size();
637 }
638 if (inv_mode && it.second->type == "$_NOT_")
639 inv_pairs.insert(std::pair<RTLIL::SigBit, RTLIL::SigBit>(sigmap(it.second->getPort("\\A")), sigmap(it.second->getPort("\\Y"))));
640 }
641
642 int bits_count = 0;
643 int bits_full_count = 0;
644 std::map<std::vector<RTLIL::SigBit>, std::vector<RTLIL::SigBit>> buckets;
645 for (auto &batch : batches)
646 {
647 for (auto &bit : batch)
648 if (bit.wire != NULL && design->selected(module, bit.wire))
649 goto found_selected_wire;
650 bits_full_count += batch.size();
651 continue;
652
653 found_selected_wire:
654 log(" Finding reduced input cone for signal batch %s%c\n",
655 log_signal(batch), verbose_level ? ':' : '.');
656
657 FindReducedInputs infinder(sigmap, drivers);
658 for (auto &bit : batch) {
659 std::vector<RTLIL::SigBit> inputs;
660 infinder.analyze(inputs, bit, 100 * bits_full_count / bits_full_total);
661 buckets[inputs].push_back(bit);
662 bits_full_count++;
663 bits_count++;
664 }
665 }
666 log(" Sorted %d signal bits into %d buckets.\n", bits_count, int(buckets.size()));
667
668 int bucket_count = 0;
669 std::vector<std::vector<equiv_bit_t>> equiv;
670 for (auto &bucket : buckets)
671 {
672 bucket_count++;
673
674 if (bucket.second.size() == 1)
675 continue;
676
677 if (bucket.first.size() == 0) {
678 log(" Finding const values for bucket %s%c\n", log_signal(bucket.second), verbose_level ? ':' : '.');
679 PerformReduction worker(sigmap, drivers, inv_pairs, bucket.second, bucket.first.size());
680 for (size_t idx = 0; idx < bucket.second.size(); idx++)
681 worker.analyze_const(equiv, idx);
682 } else {
683 log(" Trying to shatter bucket %s%c\n", log_signal(bucket.second), verbose_level ? ':' : '.');
684 PerformReduction worker(sigmap, drivers, inv_pairs, bucket.second, bucket.first.size());
685 worker.analyze(equiv, 100 * bucket_count / (buckets.size() + 1));
686 }
687 }
688
689 std::map<RTLIL::SigBit, int> bitusage;
690 CountBitUsage bitusage_worker(sigmap, bitusage);
691 module->rewrite_sigspecs(bitusage_worker);
692
693 if (!dump_prefix.empty())
694 dump();
695
696 log(" Rewiring %d equivalent groups:\n", int(equiv.size()));
697 int rewired_sigbits = 0;
698 for (auto &grp : equiv)
699 {
700 log(" [%05d] Using as master for group: %s\n", ++reduce_counter, log_signal(grp.front().bit));
701
702 RTLIL::SigSpec inv_sig;
703 for (size_t i = 1; i < grp.size(); i++)
704 {
705 if (!design->selected(module, grp[i].bit.wire)) {
706 log(" Skipping not-selected slave: %s\n", log_signal(grp[i].bit));
707 continue;
708 }
709
710 if (grp[i].bit.wire->port_id == 0 && bitusage[grp[i].bit] <= 1) {
711 log(" Skipping unused slave: %s\n", log_signal(grp[i].bit));
712 continue;
713 }
714
715 if (find_bit_in_cone(grp[i].bit, grp.front().bit)) {
716 log(" Skipping dependency of master: %s\n", log_signal(grp[i].bit));
717 continue;
718 }
719
720 log(" Connect slave%s: %s\n", grp[i].inverted ? " using inverter" : "", log_signal(grp[i].bit));
721
722 RTLIL::Cell *drv = drivers.at(grp[i].bit).first;
723 RTLIL::Wire *dummy_wire = module->addWire(NEW_ID);
724 for (auto &port : drv->connections_)
725 if (ct.cell_output(drv->type, port.first))
726 sigmap(port.second).replace(grp[i].bit, dummy_wire, &port.second);
727
728 if (grp[i].inverted)
729 {
730 if (inv_sig.size() == 0)
731 {
732 inv_sig = module->addWire(NEW_ID);
733
734 RTLIL::Cell *inv_cell = module->addCell(NEW_ID, "$_NOT_");
735 inv_cell->setPort("\\A", grp[0].bit);
736 inv_cell->setPort("\\Y", inv_sig);
737 }
738
739 module->connect(RTLIL::SigSig(grp[i].bit, inv_sig));
740 }
741 else
742 module->connect(RTLIL::SigSig(grp[i].bit, grp[0].bit));
743
744 rewired_sigbits++;
745 }
746
747 if (!dump_prefix.empty())
748 dump();
749
750 if (reduce_counter == reduce_stop_at) {
751 log(" Reached limit passed using -stop option. Skipping all further reductions.\n");
752 break;
753 }
754 }
755
756 log(" Rewired a total of %d signal bits in module %s.\n", rewired_sigbits, RTLIL::id2cstr(module->name));
757 return rewired_sigbits;
758 }
759 };
760
761 struct FreducePass : public Pass {
762 FreducePass() : Pass("freduce", "perform functional reduction") { }
763 void help() YS_OVERRIDE
764 {
765 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
766 log("\n");
767 log(" freduce [options] [selection]\n");
768 log("\n");
769 log("This pass performs functional reduction in the circuit. I.e. if two nodes are\n");
770 log("equivalent, they are merged to one node and one of the redundant drivers is\n");
771 log("disconnected. A subsequent call to 'clean' will remove the redundant drivers.\n");
772 log("\n");
773 log(" -v, -vv\n");
774 log(" enable verbose or very verbose output\n");
775 log("\n");
776 log(" -inv\n");
777 log(" enable explicit handling of inverted signals\n");
778 log("\n");
779 log(" -stop <n>\n");
780 log(" stop after <n> reduction operations. this is mostly used for\n");
781 log(" debugging the freduce command itself.\n");
782 log("\n");
783 log(" -dump <prefix>\n");
784 log(" dump the design to <prefix>_<module>_<num>.il after each reduction\n");
785 log(" operation. this is mostly used for debugging the freduce command.\n");
786 log("\n");
787 log("This pass is undef-aware, i.e. it considers don't-care values for detecting\n");
788 log("equivalent nodes.\n");
789 log("\n");
790 log("All selected wires are considered for rewiring. The selected cells cover the\n");
791 log("circuit that is analyzed.\n");
792 log("\n");
793 }
794 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
795 {
796 reduce_counter = 0;
797 reduce_stop_at = 0;
798 verbose_level = 0;
799 inv_mode = false;
800 dump_prefix = std::string();
801
802 log_header(design, "Executing FREDUCE pass (perform functional reduction).\n");
803
804 size_t argidx;
805 for (argidx = 1; argidx < args.size(); argidx++) {
806 if (args[argidx] == "-v") {
807 verbose_level = 1;
808 continue;
809 }
810 if (args[argidx] == "-vv") {
811 verbose_level = 2;
812 continue;
813 }
814 if (args[argidx] == "-inv") {
815 inv_mode = true;
816 continue;
817 }
818 if (args[argidx] == "-stop" && argidx+1 < args.size()) {
819 reduce_stop_at = atoi(args[++argidx].c_str());
820 continue;
821 }
822 if (args[argidx] == "-dump" && argidx+1 < args.size()) {
823 dump_prefix = args[++argidx];
824 continue;
825 }
826 break;
827 }
828 extra_args(args, argidx, design);
829
830 int bitcount = 0;
831 for (auto &mod_it : design->modules_) {
832 RTLIL::Module *module = mod_it.second;
833 if (design->selected(module))
834 bitcount += FreduceWorker(design, module).run();
835 }
836
837 log("Rewired a total of %d signal bits.\n", bitcount);
838 }
839 } FreducePass;
840
841 PRIVATE_NAMESPACE_END