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/celltypes.h"
22 #include "kernel/consteval.h"
23 #include "kernel/sigtools.h"
24 #include "kernel/log.h"
25 #include "kernel/satgen.h"
32 PRIVATE_NAMESPACE_BEGIN
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
;
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
;
52 return drv
< other
.drv
;
53 return bit
< other
.bit
;
60 std::map
<RTLIL::SigBit
, int> &cache
;
62 CountBitUsage(SigMap
&sigmap
, std::map
<RTLIL::SigBit
, int> &cache
) : sigmap(sigmap
), cache(cache
) { }
64 void operator()(RTLIL::SigSpec
&sig
) {
65 std::vector
<RTLIL::SigBit
> vec
= sigmap(sig
).to_sigbit_vector();
71 struct FindReducedInputs
77 std::set
<RTLIL::Cell
*> ez_cells
;
80 std::map
<RTLIL::SigBit
, int> sat_pi
;
81 std::vector
<int> sat_pi_uniq_bitvec
;
83 FindReducedInputs(SigMap
&sigmap
, drivers_t
&drivers
) :
84 sigmap(sigmap
), drivers(drivers
), satgen(ez
.get(), &sigmap
)
86 satgen
.model_undef
= true;
92 for (int i
= 8*sizeof(int); val
; i
= i
>> 1)
100 void register_pi_bit(RTLIL::SigBit bit
)
102 if (sat_pi
.count(bit
) != 0)
105 satgen
.setContext(&sigmap
, "A");
106 int sat_a
= satgen
.importSigSpec(bit
).front();
107 ez
->assume(ez
->NOT(satgen
.importUndefSigSpec(bit
).front()));
109 satgen
.setContext(&sigmap
, "B");
110 int sat_b
= satgen
.importSigSpec(bit
).front();
111 ez
->assume(ez
->NOT(satgen
.importUndefSigSpec(bit
).front()));
113 int idx
= sat_pi
.size();
114 size_t idx_bits
= get_bits(idx
);
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())));
121 log_assert(sat_pi_uniq_bitvec
.size() == idx_bits
);
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
]));
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
])));
130 ez
->assume(ez
->OR(ez
->NOT(sat_pi
[bit
]), sat_pi_uniq_bitvec
[i
]));
133 void register_cone_worker(std::set
<RTLIL::SigBit
> &pi
, std::set
<RTLIL::SigBit
> &sigdone
, RTLIL::SigBit out
)
135 if (out
.wire
== NULL
)
137 if (sigdone
.count(out
) != 0)
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
))
150 ez_cells
.insert(drv
.first
);
152 for (auto &bit
: drv
.second
)
153 register_cone_worker(pi
, sigdone
, bit
);
155 register_pi_bit(out
);
160 void register_cone(std::vector
<RTLIL::SigBit
> &pi
, RTLIL::SigBit out
)
162 std::set
<RTLIL::SigBit
> pi_set
, sigdone
;
163 register_cone_worker(pi_set
, sigdone
, out
);
165 pi
.insert(pi
.end(), pi_set
.begin(), pi_set
.end());
168 void analyze(std::vector
<RTLIL::SigBit
> &reduced_inputs
, RTLIL::SigBit output
, int prec
)
170 if (verbose_level
>= 1)
171 log("[%2d%%] Analyzing input cone for signal %s:\n", prec
, log_signal(output
));
173 std::vector
<RTLIL::SigBit
> pi
;
174 register_cone(pi
, output
);
176 if (verbose_level
>= 1)
177 log(" Found %d input signals and %d cells.\n", int(pi
.size()), int(ez_cells
.size()));
179 satgen
.setContext(&sigmap
, "A");
180 int output_a
= satgen
.importSigSpec(output
).front();
181 int output_undef_a
= satgen
.importUndefSigSpec(output
).front();
183 satgen
.setContext(&sigmap
, "B");
184 int output_b
= satgen
.importSigSpec(output
).front();
185 int output_undef_b
= satgen
.importUndefSigSpec(output
).front();
187 std::set
<int> unused_pi_idx
;
189 for (size_t i
= 0; i
< pi
.size(); i
++)
190 unused_pi_idx
.insert(i
);
194 std::vector
<int> model_pi_idx
;
195 std::vector
<int> model_expr
;
196 std::vector
<bool> model
;
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
]));
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
)))
208 for (size_t i
= 0; i
< model_pi_idx
.size(); 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
]);
215 log_assert(found_count
== 1);
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
]);
222 if (verbose_level
>= 1)
223 log(" Reduced input cone contains %d inputs.\n", int(reduced_inputs
.size()));
227 struct PerformReduction
231 std::set
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>> &inv_pairs
;
232 pool
<SigBit
> recursion_guard
;
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
;
243 int register_cone_worker(std::set
<RTLIL::Cell
*> &celldone
, std::map
<RTLIL::SigBit
, int> &sigdepth
, RTLIL::SigBit out
)
245 if (out
.wire
== NULL
)
247 if (sigdepth
.count(out
) != 0)
248 return sigdepth
.at(out
);
250 if (recursion_guard
.count(out
)) {
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());
257 recursion_guard
.insert(out
);
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
);
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;
271 pi_bits
.push_back(out
);
272 sat_pi
.push_back(satgen
.importSigSpec(out
).front());
273 ez
->assume(ez
->NOT(satgen
.importUndefSigSpec(out
).front()));
277 recursion_guard
.erase(out
);
278 return sigdepth
.at(out
);
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
)
284 satgen
.model_undef
= true;
286 std::set
<RTLIL::Cell
*> celldone
;
287 std::map
<RTLIL::SigBit
, int> sigdepth
;
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()));
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
]);
302 out_inverted
= std::vector
<bool>(sat_out
.size(), false);
305 void analyze_const(std::vector
<std::vector
<equiv_bit_t
>> &results
, int idx
)
307 if (verbose_level
== 1)
308 log(" Finding const value for %s.\n", log_signal(out_bits
[idx
]));
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
);
314 RTLIL::SigBit
value(RTLIL::State::Sx
);
316 value
= RTLIL::State::S1
;
318 value
= RTLIL::State::S0
;
319 if (verbose_level
== 1)
320 log(" Constant value for this signal: %s\n", log_signal(value
));
323 for (size_t i
= 0; i
< results
.size(); i
++) {
324 if (results
[i
].front().bit
== value
) {
330 if (result_idx
== -1) {
331 result_idx
= results
.size();
332 results
.push_back(std::vector
<equiv_bit_t
>());
335 bit
.inverted
= false;
338 results
.back().push_back(bit
);
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
);
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
)
351 std::string indent
= indent1
+ indent2
;
352 const char *indt
= indent
.c_str();
354 if (bucket
.size() <= 1)
357 if (verbose_level
== 1)
358 log("%s Trying to shatter bucket with %d signals.\n", indt
, int(bucket
.size()));
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
));
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
]));
373 std::vector
<int> modelVars
= sat_out
;
374 std::vector
<bool> model
;
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());
380 if (ez
->solve(modelVars
, model
, ez
->expression(ezSAT::OpOr
, sat_set_list
), ez
->expression(ezSAT::OpOr
, sat_clr_list
)))
386 sat_set_list
.clear();
387 sat_clr_list
.clear();
389 std::vector
<int> sat_def_list
;
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
]));
396 sat_def_list
.push_back(sat_def
[idx
]);
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
)))
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
])
413 log("%s After %d iterations: %d set vs. %d clr vs %d undef\n", indt
, iter_count
, count_set
, count_clr
, count_undef
);
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
]));
424 std::vector
<int> buckets_a
;
425 std::vector
<int> buckets_b
;
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
);
433 analyze(results
, results_map
, buckets_a
, indent1
+ ".", indent2
+ " ");
434 analyze(results
, results_map
, buckets_b
, indent1
+ "x", indent2
+ " ");
438 std::vector
<int> undef_slaves
;
440 for (int idx
: bucket
) {
441 std::vector
<int> sat_def_list
;
442 for (int idx2
: bucket
)
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
);
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
456 for (int idx
: undef_slaves
)
457 out_depth
[idx
] = std::numeric_limits
<int>::max();
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
]));
467 for (int idx
: bucket
) {
468 if (results_map
.count(idx
) == 0)
470 if (result_idx
== -1) {
471 result_idx
= results_map
.at(idx
);
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();
481 if (result_idx
== -1) {
482 result_idx
= results
.size();
483 results
.push_back(std::set
<int>());
486 results
[result_idx
].insert(bucket
.begin(), bucket
.end());
490 void analyze(std::vector
<std::vector
<equiv_bit_t
>> &results
, int perc
)
492 std::vector
<int> bucket
;
493 for (size_t i
= 0; i
< sat_out
.size(); i
++)
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
), "");
500 for (auto &r
: results_buf
)
505 if (verbose_level
>= 1) {
506 std::vector
<RTLIL::SigBit
> r_sigbits
;
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
));
512 std::vector
<int> undef_slaves
;
515 std::vector
<int> sat_def_list
;
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
);
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
530 for (int idx
: undef_slaves
)
531 out_depth
[idx
] = std::numeric_limits
<int>::max();
533 std::vector
<equiv_bit_t
> result
;
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
);
544 std::sort(result
.begin(), result
.end());
546 if (result
.front().inverted
)
547 for (auto &bit
: result
)
548 bit
.inverted
= !bit
.inverted
;
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
);
556 if (result
.size() > 1)
557 results
.push_back(result
);
564 RTLIL::Design
*design
;
565 RTLIL::Module
*module
;
569 std::set
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>> inv_pairs
;
571 FreduceWorker(RTLIL::Design
*design
, RTLIL::Module
*module
) : design(design
), module(module
), sigmap(module
)
575 bool find_bit_in_cone(std::set
<RTLIL::Cell
*> &celldone
, RTLIL::SigBit needle
, RTLIL::SigBit haystack
)
577 if (needle
== haystack
)
579 if (haystack
.wire
== NULL
|| needle
.wire
== NULL
|| drivers
.count(haystack
) == 0)
582 std::pair
<RTLIL::Cell
*, std::set
<RTLIL::SigBit
>> &drv
= drivers
.at(haystack
);
584 if (celldone
.count(drv
.first
))
586 celldone
.insert(drv
.first
);
588 for (auto &bit
: drv
.second
)
589 if (find_bit_in_cone(celldone
, needle
, bit
))
594 bool find_bit_in_cone(RTLIL::SigBit needle
, RTLIL::SigBit haystack
)
596 std::set
<RTLIL::Cell
*> celldone
;
597 return find_bit_in_cone(celldone
, needle
, haystack
);
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() : ""));
609 log("Running functional reduction on module %s:\n", RTLIL::id2cstr(module
->name
));
612 ct
.setup_internals();
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
;
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());
630 inputs
.insert(bits
.begin(), bits
.end());
632 std::pair
<RTLIL::Cell
*, std::set
<RTLIL::SigBit
>> drv(it
.second
, inputs
);
633 for (auto &bit
: outputs
)
635 batches
.push_back(outputs
);
636 bits_full_total
+= outputs
.size();
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"))));
643 int bits_full_count
= 0;
644 std::map
<std::vector
<RTLIL::SigBit
>, std::vector
<RTLIL::SigBit
>> buckets
;
645 for (auto &batch
: batches
)
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();
654 log(" Finding reduced input cone for signal batch %s%c\n",
655 log_signal(batch
), verbose_level
? ':' : '.');
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
);
666 log(" Sorted %d signal bits into %d buckets.\n", bits_count
, int(buckets
.size()));
668 int bucket_count
= 0;
669 std::vector
<std::vector
<equiv_bit_t
>> equiv
;
670 for (auto &bucket
: buckets
)
674 if (bucket
.second
.size() == 1)
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
);
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));
689 std::map
<RTLIL::SigBit
, int> bitusage
;
690 CountBitUsage
bitusage_worker(sigmap
, bitusage
);
691 module
->rewrite_sigspecs(bitusage_worker
);
693 if (!dump_prefix
.empty())
696 log(" Rewiring %d equivalent groups:\n", int(equiv
.size()));
697 int rewired_sigbits
= 0;
698 for (auto &grp
: equiv
)
700 log(" [%05d] Using as master for group: %s\n", ++reduce_counter
, log_signal(grp
.front().bit
));
702 RTLIL::SigSpec inv_sig
;
703 for (size_t i
= 1; i
< grp
.size(); i
++)
705 if (!design
->selected(module
, grp
[i
].bit
.wire
)) {
706 log(" Skipping not-selected slave: %s\n", log_signal(grp
[i
].bit
));
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
));
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
));
720 log(" Connect slave%s: %s\n", grp
[i
].inverted
? " using inverter" : "", log_signal(grp
[i
].bit
));
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
);
730 if (inv_sig
.size() == 0)
732 inv_sig
= module
->addWire(NEW_ID
);
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
);
739 module
->connect(RTLIL::SigSig(grp
[i
].bit
, inv_sig
));
742 module
->connect(RTLIL::SigSig(grp
[i
].bit
, grp
[0].bit
));
747 if (!dump_prefix
.empty())
750 if (reduce_counter
== reduce_stop_at
) {
751 log(" Reached limit passed using -stop option. Skipping all further reductions.\n");
756 log(" Rewired a total of %d signal bits in module %s.\n", rewired_sigbits
, RTLIL::id2cstr(module
->name
));
757 return rewired_sigbits
;
761 struct FreducePass
: public Pass
{
762 FreducePass() : Pass("freduce", "perform functional reduction") { }
763 void help() YS_OVERRIDE
765 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
767 log(" freduce [options] [selection]\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");
774 log(" enable verbose or very verbose output\n");
777 log(" enable explicit handling of inverted signals\n");
780 log(" stop after <n> reduction operations. this is mostly used for\n");
781 log(" debugging the freduce command itself.\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");
787 log("This pass is undef-aware, i.e. it considers don't-care values for detecting\n");
788 log("equivalent nodes.\n");
790 log("All selected wires are considered for rewiring. The selected cells cover the\n");
791 log("circuit that is analyzed.\n");
794 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
800 dump_prefix
= std::string();
802 log_header(design
, "Executing FREDUCE pass (perform functional reduction).\n");
805 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
806 if (args
[argidx
] == "-v") {
810 if (args
[argidx
] == "-vv") {
814 if (args
[argidx
] == "-inv") {
818 if (args
[argidx
] == "-stop" && argidx
+1 < args
.size()) {
819 reduce_stop_at
= atoi(args
[++argidx
].c_str());
822 if (args
[argidx
] == "-dump" && argidx
+1 < args
.size()) {
823 dump_prefix
= args
[++argidx
];
828 extra_args(args
, argidx
, design
);
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();
837 log("Rewired a total of %d signal bits.\n", bitcount
);
841 PRIVATE_NAMESPACE_END