ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
rrrOptimizer.h
Go to the documentation of this file.
1#pragma once
2
3#include <map>
4#include <iterator>
5#include <random>
6#include <numeric>
7
8#include "rrrParameter.h"
9#include "rrrUtils.h"
10
11ABC_NAMESPACE_CXX_HEADER_START
12
13namespace rrr {
14
15 // it is assumed that removing redundancy never degrades the cost in this optimizer
16 template <typename Ntk, typename Ana>
17 class Optimizer {
18 private:
19 // aliases
20 using itr = std::vector<int>::iterator;
21 using citr = std::vector<int>::const_iterator;
22 using ritr = std::vector<int>::reverse_iterator;
23 using critr = std::vector<int>::const_reverse_iterator;
24
25 // pointer to network
26 Ntk *pNtk;
27
28 // parameters
29 int nVerbose;
30 std::function<double(Ntk *)> CostFunction;
31 int nSortTypeOriginal;
32 int nSortType;
33 int nFlow;
34 int nDistance;
35 bool fCompatible;
36 bool fGreedy;
37 seconds nTimeout; // assigned upon Run
38 std::function<void(std::string)> PrintLine;
39
40 // data
41 Ana ana;
42 std::mt19937 rng;
43 std::vector<int> vTmp;
44 std::map<int, std::set<int>> mapNewFanins;
45 time_point start;
46
47 // fanin sorting data
48 std::vector<int> vRandPiOrder;
49 std::vector<double> vRandCosts;
50
51 // marks
52 int target;
53 std::vector<bool> vTfoMarks;
54
55 // statistics
56 struct Stats;
57 std::map<std::string, Stats> stats;
58 Stats statsLocal;
59
60 // print
61 template<typename... Args>
62 void Print(int nVerboseLevel, Args... args);
63
64 // callback
65 void ActionCallback(Action const &action);
66
67 // topology
68 void MarkTfo(int id);
69
70 // time
71 bool Timeout();
72
73 // sort fanins
74 void SetRandPiOrder();
75 void SetRandCosts();
76 void SortFanins(int id);
77 void SortFanins();
78
79 // reduce fanins
80 bool ReduceFanins(int id, bool fRemoveUnused = false);
81 bool ReduceFaninsOneRandom(int id, bool fRemoveUnused = false);
82
83 // reduce
84 bool Reduce(bool fSubRoutine = false);
85 void ReduceRandom();
86
87 // remove redundancy
88 bool RemoveRedundancy();
89 void RemoveRedundancyRandom();
90
91 // addition
92 template <typename T>
93 T SingleAdd(int id, T begin, T end);
94 int MultiAdd(int id, std::vector<int> const &vCands, int nMax = 0);
95 void Undo();
96
97 // resub
98 void SingleResub(int id, std::vector<int> const &vCands);
99 void MultiResub(int id, std::vector<int> const &vCands, int nMax = 0);
100
101 // resub stop
102 bool SingleResubStop(int id, std::vector<int> const &vCands);
103 bool MultiResubStop(int id, std::vector<int> const &vCands, int nMax = 0);
104
105 // multi-target resub
106 bool MultiTargetResub(std::vector<int> vTargets, int nMax = 0);
107
108 // apply
109 void ApplyReverseTopologically(std::function<void(int)> const &func);
110 void ApplyRandomlyStop(std::function<bool(int)> const &func);
111 void ApplyCombinationRandomlyStop(int k, std::function<bool(std::vector<int> const &)> const &func);
112 void ApplyCombinationSampledRandomlyStop(int k, int nSamples, std::function<bool(std::vector<int> const &)> const &func);
113
114 public:
115 // constructors
116 Optimizer(Parameter const *pPar, std::function<double(Ntk *)> CostFunction);
117 void AssignNetwork(Ntk *pNtk_, bool fReuse = false);
118 void SetPrintLine(std::function<void(std::string)> const &PrintLine_);
119
120 // run
121 void Run(int iSeed = 0, seconds nTimeout_ = 0);
122
123 // summary
124 void ResetSummary();
125 summary<int> GetStatsSummary() const;
126 summary<double> GetTimesSummary() const;
127 };
128
129 /* {{{ Stats */
130
131 template <typename Ntk, typename Ana>
132 struct Optimizer<Ntk, Ana>::Stats {
133 int nTriedFis = 0;
134 int nAddedFis = 0;
135 int nTried = 0;
136 int nAdded = 0;
137 int nChanged = 0;
138 int nUps = 0;
139 int nEqs = 0;
140 int nDowns = 0;
141 double durationAdd = 0;
142 double durationReduce = 0;
143
144 void Reset() {
145 nTriedFis = 0;
146 nAddedFis = 0;
147 nTried = 0;
148 nAdded = 0;
149 nChanged = 0;
150 nUps = 0;
151 nEqs = 0;
152 nDowns = 0;
153 durationAdd = 0;
154 durationReduce = 0;
155 }
156
157 Stats& operator+=(Stats const &other) {
158 this->nTriedFis += other.nTriedFis;
159 this->nAddedFis += other.nAddedFis;
160 this->nTried += other.nTried;
161 this->nAdded += other.nAdded;
162 this->nChanged += other.nChanged;
163 this->nUps += other.nUps;
164 this->nEqs += other.nEqs;
165 this->nDowns += other.nDowns;
166 this->durationAdd += other.durationAdd;
167 this->durationReduce += other.durationReduce;
168 return *this;
169 }
170
171 std::string GetString() const {
172 std::stringstream ss;
173 PrintNext(ss, "tried node/fanin", "=", nTried, "/", nTriedFis, ",", "added node/fanin", "=", nAdded, "/", nAddedFis, ",", "changed", "=", nChanged, ",", "up/eq/dn", "=", nUps, "/", nEqs, "/", nDowns);
174 return ss.str();
175 }
176 };
177
178 /* }}} */
179
180 /* {{{ Print */
181
182 template <typename Ntk, typename Ana>
183 template <typename... Args>
184 inline void Optimizer<Ntk, Ana>::Print(int nVerboseLevel, Args... args) {
185 if(nVerbose > nVerboseLevel) {
186 std::stringstream ss;
187 for(int i = 0; i < nVerboseLevel; i++) {
188 ss << "\t";
189 }
190 PrintNext(ss, args...);
191 PrintLine(ss.str());
192 }
193 }
194
195 /* }}} */
196
197 /* {{{ Callback */
198
199 template <typename Ntk, typename Ana>
200 void Optimizer<Ntk, Ana>::ActionCallback(Action const &action) {
201 if(nVerbose > 4) {
202 std::stringstream ss = GetActionDescription(action);
203 std::string str;
204 std::getline(ss, str);
205 Print(4, str);
206 while(std::getline(ss, str)) {
207 Print(5, str);
208 }
209 }
210 switch(action.type) {
211 case REMOVE_FANIN:
212 if(action.id != target) {
213 target = -1;
214 }
215 break;
216 case REMOVE_UNUSED:
217 break;
218 case REMOVE_BUFFER:
219 case REMOVE_CONST:
220 if(action.id == target) {
221 target = -1;
222 }
223 break;
224 case ADD_FANIN:
225 if(action.id != target) {
226 target = -1;
227 }
228 break;
229 case TRIVIAL_COLLAPSE:
230 break;
231 case TRIVIAL_DECOMPOSE:
232 target = -1;
233 break;
234 case SORT_FANINS:
235 break;
236 case READ:
237 target = -1;
238 break;
239 case SAVE:
240 break;
241 case LOAD:
242 //target = -1; // this is not always needed, so do it manually
243 break;
244 case POP_BACK:
245 break;
246 default:
247 assert(0);
248 }
249 }
250
251 /* }}} */
252
253 /* {{{ Topology */
254
255 template <typename Ntk, typename Ana>
256 inline void Optimizer<Ntk, Ana>::MarkTfo(int id) {
257 // includes id itself
258 if(id == target) {
259 return;
260 }
261 target = id;
262 vTfoMarks.clear();
263 vTfoMarks.resize(pNtk->GetNumNodes());
264 vTfoMarks[id] = true;
265 pNtk->ForEachTfo(id, false, [&](int fo) {
266 vTfoMarks[fo] = true;
267 });
268 }
269
270 /* }}} */
271
272 /* {{{ Time */
273
274 template <typename Ntk, typename Ana>
275 inline bool Optimizer<Ntk, Ana>::Timeout() {
276 if(nTimeout) {
277 time_point current = GetCurrentTime();
278 if(DurationInSeconds(start, current) > nTimeout) {
279 return true;
280 }
281 }
282 return false;
283 }
284
285 /* }}} */
286
287 /* {{{ Sort fanins */
288
289 template <typename Ntk, typename Ana>
290 inline void Optimizer<Ntk, Ana>::SetRandPiOrder() {
291 if(int_size(vRandPiOrder) != pNtk->GetNumPis()) {
292 vRandPiOrder.clear();
293 vRandPiOrder.resize(pNtk->GetNumPis());
294 std::iota(vRandPiOrder.begin(), vRandPiOrder.end(), 0);
295 std::shuffle(vRandPiOrder.begin(), vRandPiOrder.end(), rng);
296 }
297 }
298
299 template <typename Ntk, typename Ana>
300 inline void Optimizer<Ntk, Ana>::SetRandCosts() {
301 std::uniform_real_distribution<> dis(std::numeric_limits<double>::lowest(), std::numeric_limits<double>::max());
302 while(int_size(vRandCosts) < pNtk->GetNumNodes()) {
303 vRandCosts.push_back(dis(rng));
304 }
305 }
306
307 template <typename Ntk, typename Ana>
308 inline void Optimizer<Ntk, Ana>::SortFanins(int id) {
309 switch(nSortType) {
310 case 0: // no sorting
311 break;
312 case 1: // prioritize internals
313 pNtk->SortFanins(id, [&](int i, int j) {
314 return !pNtk->IsPi(i) && pNtk->IsPi(j);
315 });
316 break;
317 case 2: // prioritize internals with (reversely) sorted PIs
318 pNtk->SortFanins(id, [&](int i, int j) {
319 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
320 return pNtk->GetPiIndex(i) > pNtk->GetPiIndex(j);
321 }
322 return pNtk->IsPi(j);
323 });
324 break;
325 case 3: // prioritize internals with random PI order
326 SetRandPiOrder();
327 pNtk->SortFanins(id, [&](int i, int j) {
328 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
329 return vRandPiOrder[pNtk->GetPiIndex(i)] > vRandPiOrder[pNtk->GetPiIndex(j)];
330 }
331 return pNtk->IsPi(j);
332 });
333 break;
334 case 4: // smaller fanout takes larger cost
335 pNtk->SortFanins(id, [&](int i, int j) {
336 return pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j);
337 });
338 break;
339 case 5: // fanout + PI
340 pNtk->SortFanins(id, [&](int i, int j) {
341 if(pNtk->IsPi(i) && !pNtk->IsPi(j)) {
342 return false;
343 }
344 if(!pNtk->IsPi(i) && pNtk->IsPi(j)) {
345 return true;
346 }
347 return pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j);
348 });
349 break;
350 case 6: // fanout + sorted PI
351 pNtk->SortFanins(id, [&](int i, int j) {
352 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
353 return pNtk->GetPiIndex(i) > pNtk->GetPiIndex(j);
354 }
355 if(pNtk->IsPi(i)) {
356 return false;
357 }
358 if(pNtk->IsPi(j)) {
359 return true;
360 }
361 return pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j);
362 });
363 break;
364 case 7: // fanout + random PI
365 SetRandPiOrder();
366 pNtk->SortFanins(id, [&](int i, int j) {
367 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
368 return vRandPiOrder[pNtk->GetPiIndex(i)] > vRandPiOrder[pNtk->GetPiIndex(j)];
369 }
370 if(pNtk->IsPi(i)) {
371 return false;
372 }
373 if(pNtk->IsPi(j)) {
374 return true;
375 }
376 return pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j);
377 });
378 break;
379 case 8: // reverse topological order + PI
380 pNtk->SortFanins(id, [&](int i, int j) {
381 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
382 return false;
383 }
384 if(pNtk->IsPi(i)) {
385 return false;
386 }
387 if(pNtk->IsPi(j)) {
388 return true;
389 }
390 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
391 });
392 break;
393 case 9: // reverse topological order + sorted PI
394 pNtk->SortFanins(id, [&](int i, int j) {
395 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
396 return pNtk->GetPiIndex(i) > pNtk->GetPiIndex(j);
397 }
398 if(pNtk->IsPi(i)) {
399 return false;
400 }
401 if(pNtk->IsPi(j)) {
402 return true;
403 }
404 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
405 });
406 break;
407 case 10: // reverse topological order + random PI
408 SetRandPiOrder();
409 pNtk->SortFanins(id, [&](int i, int j) {
410 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
411 return vRandPiOrder[pNtk->GetPiIndex(i)] > vRandPiOrder[pNtk->GetPiIndex(j)];
412 }
413 if(pNtk->IsPi(i)) {
414 return false;
415 }
416 if(pNtk->IsPi(j)) {
417 return true;
418 }
419 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
420 });
421 break;
422 case 11: // topo + fanout + PI
423 pNtk->SortFanins(id, [&](int i, int j) {
424 if(pNtk->IsPi(i) && !pNtk->IsPi(j)) {
425 return false;
426 }
427 if(!pNtk->IsPi(i) && pNtk->IsPi(j)) {
428 return true;
429 }
430 if(pNtk->GetNumFanouts(i) > pNtk->GetNumFanouts(j)) {
431 return false;
432 }
433 if(pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j)) {
434 return true;
435 }
436 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
437 return false;
438 }
439 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
440 });
441 break;
442 case 12: // topo + fanout + sorted PI
443 pNtk->SortFanins(id, [&](int i, int j) {
444 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
445 return pNtk->GetPiIndex(i) > pNtk->GetPiIndex(j);
446 }
447 if(pNtk->IsPi(i)) {
448 return false;
449 }
450 if(pNtk->IsPi(j)) {
451 return true;
452 }
453 if(pNtk->GetNumFanouts(i) > pNtk->GetNumFanouts(j)) {
454 return false;
455 }
456 if(pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j)) {
457 return true;
458 }
459 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
460 });
461 break;
462 case 13: // topo + fanout + random PI
463 SetRandPiOrder();
464 pNtk->SortFanins(id, [&](int i, int j) {
465 if(pNtk->IsPi(i) && pNtk->IsPi(j)) {
466 return vRandPiOrder[pNtk->GetPiIndex(i)] > vRandPiOrder[pNtk->GetPiIndex(j)];
467 }
468 if(pNtk->IsPi(i)) {
469 return false;
470 }
471 if(pNtk->IsPi(j)) {
472 return true;
473 }
474 if(pNtk->GetNumFanouts(i) > pNtk->GetNumFanouts(j)) {
475 return false;
476 }
477 if(pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j)) {
478 return true;
479 }
480 return pNtk->GetIntIndex(i) > pNtk->GetIntIndex(j);
481 });
482 break;
483 case 14: // random order
484 SetRandCosts();
485 pNtk->SortFanins(id, [&](int i, int j) {
486 return vRandCosts[i] > vRandCosts[j];
487 });
488 break;
489 case 15: // random + PI
490 SetRandCosts();
491 pNtk->SortFanins(id, [&](int i, int j) {
492 if(pNtk->IsPi(i) && !pNtk->IsPi(j)) {
493 return false;
494 }
495 if(!pNtk->IsPi(i) && pNtk->IsPi(j)) {
496 return true;
497 }
498 return vRandCosts[i] > vRandCosts[j];
499 });
500 break;
501 case 16: // random + fanout
502 SetRandCosts();
503 pNtk->SortFanins(id, [&](int i, int j) {
504 if(pNtk->GetNumFanouts(i) > pNtk->GetNumFanouts(j)) {
505 return false;
506 }
507 if(pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j)) {
508 return true;
509 }
510 return vRandCosts[i] > vRandCosts[j];
511 });
512 break;
513 case 17: // random + fanout + PI
514 SetRandCosts();
515 pNtk->SortFanins(id, [&](int i, int j) {
516 if(pNtk->IsPi(i) && !pNtk->IsPi(j)) {
517 return false;
518 }
519 if(!pNtk->IsPi(i) && pNtk->IsPi(j)) {
520 return true;
521 }
522 if(pNtk->GetNumFanouts(i) > pNtk->GetNumFanouts(j)) {
523 return false;
524 }
525 if(pNtk->GetNumFanouts(i) < pNtk->GetNumFanouts(j)) {
526 return true;
527 }
528 return vRandCosts[i] > vRandCosts[j];
529 });
530 break;
531 default:
532 assert(0);
533 }
534 }
535
536 template <typename Ntk, typename Ana>
537 inline void Optimizer<Ntk, Ana>::SortFanins() {
538 pNtk->ForEachInt([&](int id) {
539 SortFanins(id);
540 });
541 }
542
543 /* }}} */
544
545 /* {{{ Reduce fanins */
546
547 template <typename Ntk, typename Ana>
548 inline bool Optimizer<Ntk, Ana>::ReduceFanins(int id, bool fRemoveUnused) {
549 assert(pNtk->GetNumFanouts(id) > 0);
550 bool fReduced = false;
551 for(int idx = 0; idx < pNtk->GetNumFanins(id); idx++) {
552 // skip fanins that were just added
553 if(mapNewFanins.count(id)) {
554 int fi = pNtk->GetFanin(id, idx);
555 if(mapNewFanins[id].count(fi)) {
556 continue;
557 }
558 }
559 // reduce
560 if(ana.CheckRedundancy(id, idx)) {
561 int fi = pNtk->GetFanin(id, idx);
562 pNtk->RemoveFanin(id, idx);
563 fReduced = true;
564 idx--;
565 if(fRemoveUnused && pNtk->GetNumFanouts(fi) == 0) {
566 pNtk->RemoveUnused(fi, true);
567 }
568 }
569 }
570 return fReduced;
571 }
572
573 /*
574 template <typename Ntk, typename Ana>
575 inline bool Optimizer<Ntk, Ana>::ReduceFaninsOneRandom(int id, bool fRemoveUnused) {
576 assert(pNtk->GetNumFanouts(id) > 0);
577 // generate random order
578 vTmp.resize(pNtk->GetNumFanins(id));
579 std::iota(vTmp.begin(), vTmp.end(), 0);
580 std::shuffle(vTmp.begin(), vTmp.end(), rng);
581 for(int idx: vTmp) {
582 // skip fanins that were just added
583 if(mapNewFanins.count(id)) {
584 int fi = pNtk->GetFanin(id, idx);
585 if(mapNewFanins[id].count(fi)) {
586 continue;
587 }
588 }
589 // reduce
590 if(ana.CheckRedundancy(id, idx)) {
591 int fi = pNtk->GetFanin(id, idx);
592 pNtk->RemoveFanin(id, idx);
593 if(fRemoveUnused && pNtk->GetNumFanouts(fi) == 0) {
594 pNtk->RemoveUnused(fi, true);
595 }
596 return true;
597 }
598 }
599 return false;
600 }
601 */
602
603 // TODO: add a method to minimize the size of fanins (check singles, pairs, trios, and so on)?
604
605 /* }}} */
606
607 /* {{{ Reduce */
608
609 template <typename Ntk, typename Ana>
610 bool Optimizer<Ntk, Ana>::Reduce(bool fSubRoutine) {
611 time_point timeStart = GetCurrentTime();
612 bool fReduced = false;
613 std::vector<int> vInts = pNtk->GetInts();
614 for(critr it = vInts.rbegin(); it != vInts.rend(); it++) {
615 if(!pNtk->IsInt(*it)) {
616 continue;
617 }
618 if(pNtk->GetNumFanouts(*it) == 0) {
619 pNtk->RemoveUnused(*it);
620 continue;
621 }
622 fReduced |= ReduceFanins(*it);
623 if(pNtk->GetNumFanins(*it) <= 1) {
624 pNtk->Propagate(*it);
625 }
626 }
627 if(!fSubRoutine) {
628 time_point timeEnd = GetCurrentTime();
629 statsLocal.durationReduce += Duration(timeStart, timeEnd);
630 }
631 return fReduced;
632 }
633
634 /*
635 template <typename Ntk, typename Ana>
636 void Optimizer<Ntk, Ana>::ReduceRandom() {
637 pNtk->Sweep(false);
638 std::vector<int> vInts = pNtk->GetInts();
639 std::shuffle(vInts.begin(), vInts.end(), rng);
640 for(citr it = vInts.begin(); it != vInts.end(); it++) {
641 if(!pNtk->IsInt(*it)) {
642 continue;
643 }
644 if(pNtk->GetNumFanouts(*it) == 0) {
645 pNtk->RemoveUnused(*it);
646 continue;
647 }
648 ReduceFanins(*it, true);
649 if(pNtk->GetNumFanins(*it) <= 1) {
650 pNtk->Propagate(*it);
651 }
652 }
653 }
654 */
655
656 /* }}} */
657
658 /* {{{ Redundancy removal */
659
660 template <typename Ntk, typename Ana>
661 bool Optimizer<Ntk, Ana>::RemoveRedundancy() {
662 time_point timeStart = GetCurrentTime();
663 bool fReduced = false;
664 if(fCompatible) {
665 while(Reduce(true)) {
666 fReduced = true;
667 SortFanins();
668 }
669 } else {
670 std::vector<int> vInts = pNtk->GetInts();
671 for(critr it = vInts.rbegin(); it != vInts.rend();) {
672 if(!pNtk->IsInt(*it)) {
673 it++;
674 continue;
675 }
676 if(pNtk->GetNumFanouts(*it) == 0) {
677 pNtk->RemoveUnused(*it);
678 it++;
679 continue;
680 }
681 SortFanins(*it);
682 bool fReduced_ = ReduceFanins(*it);
683 fReduced |= fReduced_;
684 if(pNtk->GetNumFanins(*it) <= 1) {
685 pNtk->Propagate(*it);
686 }
687 if(fReduced_) {
688 it = vInts.rbegin();
689 } else {
690 it++;
691 }
692 }
693 }
694 time_point timeEnd = GetCurrentTime();
695 statsLocal.durationReduce += Duration(timeStart, timeEnd);
696 return fReduced;
697 }
698
699 /*
700 template <typename Ntk, typename Ana>
701 void Optimizer<Ntk, Ana>::RemoveRedundancyRandom() {
702 pNtk->Sweep(false);
703 std::vector<int> vInts = pNtk->GetInts();
704 std::shuffle(vInts.begin(), vInts.end(), rng);
705 for(citr it = vInts.begin(); it != vInts.end();) {
706 if(!pNtk->IsInt(*it)) {
707 it++;
708 continue;
709 }
710 if(pNtk->GetNumFanouts(*it) == 0) {
711 pNtk->RemoveUnused(*it);
712 it++;
713 continue;
714 }
715 bool fReduced = ReduceFaninsOneRandom(*it, true);
716 if(pNtk->GetNumFanins(*it) <= 1) {
717 pNtk->Propagate(*it);
718 }
719 if(fReduced) {
720 std::shuffle(vInts.begin(), vInts.end(), rng);
721 it = vInts.begin();
722 } else {
723 it++;
724 }
725 }
726 }
727 */
728
729 /* }}} */
730
731 /* {{{ Addition */
732
733 template <typename Ntk, typename Ana>
734 template <typename T>
735 T Optimizer<Ntk, Ana>::SingleAdd(int id, T begin, T end) {
736 time_point timeStart = GetCurrentTime();
737 MarkTfo(id);
738 pNtk->ForEachFanin(id, [&](int fi) {
739 vTfoMarks[fi] = true;
740 });
741 T it = begin;
742 for(; it != end; it++) {
743 if(!pNtk->IsInt(*it) && !pNtk->IsPi(*it)) {
744 continue;
745 }
746 if(vTfoMarks[*it]) {
747 continue;
748 }
749 statsLocal.nTriedFis++;
750 if(ana.CheckFeasibility(id, *it, false)) {
751 pNtk->AddFanin(id, *it, false);
752 statsLocal.nAddedFis++;
753 } else if(pNtk->UseComplementedEdges() && ana.CheckFeasibility(id, *it, true)) {
754 pNtk->AddFanin(id, *it, true);
755 statsLocal.nAddedFis++;
756 } else {
757 continue;
758 }
759 mapNewFanins[id].insert(*it);
760 break;
761 }
762 pNtk->ForEachFanin(id, [&](int fi) {
763 vTfoMarks[fi] = false;
764 });
765 time_point timeEnd = GetCurrentTime();
766 statsLocal.durationAdd += Duration(timeStart, timeEnd);
767 return it;
768 }
769
770 template <typename Ntk, typename Ana>
771 int Optimizer<Ntk, Ana>::MultiAdd(int id, std::vector<int> const &vCands, int nMax) {
772 time_point timeStart = GetCurrentTime();
773 MarkTfo(id);
774 pNtk->ForEachFanin(id, [&](int fi) {
775 vTfoMarks[fi] = true;
776 });
777 int nAddedFis_ = 0;
778 for(int cand: vCands) {
779 if(!pNtk->IsInt(cand) && !pNtk->IsPi(cand)) {
780 continue;
781 }
782 if(vTfoMarks[cand]) {
783 continue;
784 }
785 statsLocal.nTriedFis++;
786 if(ana.CheckFeasibility(id, cand, false)) {
787 pNtk->AddFanin(id, cand, false);
788 statsLocal.nAddedFis++;
789 } else if(pNtk->UseComplementedEdges() && ana.CheckFeasibility(id, cand, true)) {
790 pNtk->AddFanin(id, cand, true);
791 statsLocal.nAddedFis++;
792 } else {
793 continue;
794 }
795 mapNewFanins[id].insert(cand);
796 nAddedFis_++;
797 if(nAddedFis_ == nMax) {
798 break;
799 }
800 }
801 pNtk->ForEachFanin(id, [&](int fi) {
802 vTfoMarks[fi] = false;
803 });
804 time_point timeEnd = GetCurrentTime();
805 statsLocal.durationAdd += Duration(timeStart, timeEnd);
806 return nAddedFis_;
807 }
808
809 template <typename Ntk, typename Ana>
810 void Optimizer<Ntk, Ana>::Undo() {
811 for(auto const &entry: mapNewFanins) {
812 int id = entry.first;
813 for(int fi: entry.second) {
814 int idx = pNtk->FindFanin(id, fi);
815 pNtk->RemoveFanin(id, idx);
816 }
817 }
818 }
819
820 /* }}} */
821
822 /* {{{ Resub */
823
824 template <typename Ntk, typename Ana>
825 void Optimizer<Ntk, Ana>::SingleResub(int id, std::vector<int> const &vCands) {
826 // NOTE: this assumes trivial collapse/decompose does not change cost
827 // let us assume the node is not trivially redundant for now
828 assert(pNtk->GetNumFanouts(id) != 0);
829 assert(pNtk->GetNumFanins(id) > 1);
830 // collapse
831 pNtk->TrivialCollapse(id);
832 // save if wanted
833 int slot = -2;
834 if(fGreedy || fCompatible) {
835 slot = pNtk->Save();
836 }
837 // main loop
838 double cost = CostFunction(pNtk);
839 bool fTried = false, fAdded = false;
840 for(citr it = vCands.begin(); it != vCands.end(); it++) {
841 if(Timeout()) {
842 break;
843 }
844 if(!pNtk->IsInt(id)) {
845 break;
846 }
847 fTried = true;
848 it = SingleAdd<citr>(id, it, vCands.end());
849 if(it == vCands.end()) {
850 break;
851 }
852 fAdded = true;
853 Print(2, "cand", *it, "(", int_distance(vCands.begin(), it) + 1, "/", int_size(vCands), ")", ":", "cost", "=", cost);
854 if(RemoveRedundancy()) {
855 double costNew = CostFunction(pNtk);
856 // stats
857 statsLocal.nChanged++;
858 if(costNew < cost) {
859 statsLocal.nDowns++;
860 } else if (costNew == cost) {
861 statsLocal.nEqs++;
862 } else {
863 statsLocal.nUps++;
864 }
865 // greedy
866 if(fGreedy) {
867 if(costNew <= cost) {
868 pNtk->Save(slot);
869 cost = costNew;
870 } else {
871 pNtk->Load(slot);
872 }
873 } else {
874 cost = costNew;
875 }
876 } else {
877 // assuming addition only always increases cost
878 if(fCompatible) {
879 pNtk->Load(slot);
880 } else {
881 Undo();
882 }
883 }
884 mapNewFanins.clear();
885 }
886 if(pNtk->IsInt(id)) {
887 pNtk->TrivialDecompose(id);
888 SortFanins();
889 if(fCompatible) {
890 RemoveRedundancy();
891 }
892 }
893 if(fGreedy || fCompatible) {
894 pNtk->PopBack();
895 }
896 if(fTried) {
897 statsLocal.nTried++;
898 }
899 if(fAdded) {
900 statsLocal.nAdded++;
901 }
902 }
903
904 template <typename Ntk, typename Ana>
905 void Optimizer<Ntk, Ana>::MultiResub(int id, std::vector<int> const &vCands, int nMax) {
906 // NOTE: this assumes trivial collapse/decompose does not change cost
907 // let us assume the node is not trivially redundant for now
908 assert(pNtk->GetNumFanouts(id) != 0);
909 assert(pNtk->GetNumFanins(id) > 1);
910 statsLocal.nTried++;
911 // save if wanted
912 int slot = -2;
913 if(fGreedy || fCompatible) {
914 slot = pNtk->Save();
915 }
916 // collapse
917 pNtk->TrivialCollapse(id);
918 // resub
919 double cost = CostFunction(pNtk);
920 if(MultiAdd(id, vCands, nMax)) {
921 statsLocal.nAdded++;
922 if(RemoveRedundancy()) {
923 mapNewFanins.clear();
924 RemoveRedundancy();
925 double costNew = CostFunction(pNtk);
926 // stats
927 statsLocal.nChanged++;
928 if(costNew < cost) {
929 statsLocal.nDowns++;
930 } else if (costNew == cost) {
931 statsLocal.nEqs++;
932 } else {
933 statsLocal.nUps++;
934 }
935 // greedy
936 if(fGreedy && costNew > cost) {
937 pNtk->Load(slot);
938 }
939 } else {
940 if(fCompatible) {
941 pNtk->Load(slot);
942 } else {
943 Undo();
944 }
945 mapNewFanins.clear();
946 }
947 }
948 if(pNtk->IsInt(id)) {
949 pNtk->TrivialDecompose(id);
950 SortFanins();
951 if(fCompatible) {
952 RemoveRedundancy();
953 }
954 }
955 if(fGreedy || fCompatible) {
956 pNtk->PopBack();
957 }
958 }
959
960 /* }}} */
961
962 /* {{{ Resub stop */
963
964 template <typename Ntk, typename Ana>
965 bool Optimizer<Ntk, Ana>::SingleResubStop(int id, std::vector<int> const &vCands) {
966 // stop whenever structure has changed without increasing cost and return true
967 // return false if no candidates are effective
968 // NOTE: this assumes trivial collapse/decompose does not change cost
969 // let us assume the node is not trivially redundant for now
970 assert(pNtk->GetNumFanouts(id) != 0);
971 assert(pNtk->GetNumFanins(id) > 1);
972 Print(2, "method", "=", "single");
973 // collapse
974 pNtk->TrivialCollapse(id);
975 // save
976 int slot = pNtk->Save();
977 // remember fanins
978 std::set<int> sFanins = pNtk->GetExtendedFanins(id);
979 Print(3, "extended fanins", ":", sFanins);
980 // main loop
981 bool fChanged = false;
982 double cost = CostFunction(pNtk);
983 bool fTried = false, fAdded = false;
984 for(citr it = vCands.begin(); it != vCands.end(); it++) {
985 if(Timeout()) {
986 break;
987 }
988 assert(pNtk->IsInt(id));
989 fTried = true;
990 it = SingleAdd<citr>(id, it, vCands.end());
991 if(it == vCands.end()) {
992 break;
993 }
994 fAdded = true;
995 Print(3, "cand", *it, "(", int_distance(vCands.begin(), it) + 1, "/", int_size(vCands), ")", ":", "cost", "=", cost);
996 if(RemoveRedundancy()) {
997 mapNewFanins.clear();
998 double costNew = CostFunction(pNtk);
999 if(costNew <= cost) {
1000 fChanged = false;
1001 if(costNew < cost || !pNtk->IsInt(id)) {
1002 fChanged = true;
1003 } else {
1004 std::set<int> sNewFanins = pNtk->GetExtendedFanins(id);
1005 Print(3, "new extended fanins", ":", sNewFanins);
1006 if(sFanins != sNewFanins) {
1007 fChanged = true;
1008 }
1009 }
1010 if(fChanged) {
1011 statsLocal.nChanged++;
1012 if(costNew < cost) {
1013 statsLocal.nDowns++;
1014 } else if (costNew == cost) {
1015 statsLocal.nEqs++;
1016 } else {
1017 statsLocal.nUps++;
1018 }
1019 break;
1020 }
1021 }
1022 pNtk->Load(slot);
1023 } else {
1024 if(fCompatible) {
1025 pNtk->Load(slot);
1026 } else {
1027 Undo();
1028 }
1029 mapNewFanins.clear();
1030 }
1031 }
1032 if(pNtk->IsInt(id)) {
1033 pNtk->TrivialDecompose(id);
1034 }
1035 pNtk->PopBack();
1036 if(fTried) {
1037 statsLocal.nTried++;
1038 }
1039 if(fAdded) {
1040 statsLocal.nAdded++;
1041 }
1042 return fChanged;
1043 }
1044
1045 template <typename Ntk, typename Ana>
1046 bool Optimizer<Ntk, Ana>::MultiResubStop(int id, std::vector<int> const &vCands, int nMax) {
1047 // if structure has changed without increasing cost, return true
1048 // otherwise, return false
1049 // NOTE: this assumes trivial collapse/decompose does not change cost
1050 // let us assume the node is not trivially redundant for now
1051 assert(pNtk->GetNumFanouts(id) != 0);
1052 assert(pNtk->GetNumFanins(id) > 1);
1053 Print(2, "method", "=", "multi");
1054 statsLocal.nTried++;
1055 // save
1056 int slot = pNtk->Save();
1057 // remember fanins
1058 std::set<int> sFanins = pNtk->GetExtendedFanins(id);
1059 Print(3, "extended fanins", ":", sFanins);
1060 // collapse
1061 pNtk->TrivialCollapse(id);
1062 // resub
1063 bool fChanged = false;
1064 double cost = CostFunction(pNtk);
1065 if(MultiAdd(id, vCands, nMax)) {
1066 statsLocal.nAdded++;
1067 if(RemoveRedundancy()) {
1068 mapNewFanins.clear();
1069 RemoveRedundancy();
1070 double costNew = CostFunction(pNtk);
1071 if(!fGreedy || costNew <= cost) {
1072 fChanged = false;
1073 if(costNew < cost || !pNtk->IsInt(id)) {
1074 fChanged = true;
1075 } else {
1076 std::set<int> sNewFanins = pNtk->GetExtendedFanins(id);
1077 Print(3, "new extended fanins", ":", sNewFanins);
1078 if(sFanins != sNewFanins) {
1079 fChanged = true;
1080 }
1081 }
1082 if(fChanged) {
1083 statsLocal.nChanged++;
1084 if(costNew < cost) {
1085 statsLocal.nDowns++;
1086 } else if (costNew == cost) {
1087 statsLocal.nEqs++;
1088 } else {
1089 statsLocal.nUps++;
1090 }
1091 }
1092 }
1093 } else {
1094 mapNewFanins.clear();
1095 }
1096 }
1097 if(fChanged) {
1098 if(pNtk->IsInt(id)) {
1099 pNtk->TrivialDecompose(id);
1100 }
1101 } else {
1102 pNtk->Load(slot);
1103 }
1104 pNtk->PopBack();
1105 return fChanged;
1106 }
1107
1108 /* }}} */
1109
1110 /* {{{ Multi-target resub */
1111
1112 template <typename Ntk, typename Ana>
1113 bool Optimizer<Ntk, Ana>::MultiTargetResub(std::vector<int> vTargets, int nMax) {
1114 // save
1115 int slot = pNtk->Save();
1116 double dCost = CostFunction(pNtk);
1117 // remove targets that are trivially collapsed together
1118 for(int id: vTargets) {
1119 if(pNtk->IsInt(id)) {
1120 pNtk->TrivialCollapse(id);
1121 }
1122 }
1123 for(itr it = vTargets.begin(); it != vTargets.end();) {
1124 if(!pNtk->IsInt(*it)) {
1125 it = vTargets.erase(it);
1126 } else {
1127 it++;
1128 }
1129 }
1130 // add while remembering extended fanins
1131 Print(2, "targets", ":", vTargets);
1132 std::vector<std::set<int>> vsFanins;
1133 for(int id: vTargets) {
1134 // get candidates
1135 std::vector<int> vCands;
1136 if(nDistance) {
1137 vCands = pNtk->GetNeighbors(id, true, nDistance);
1138 } else {
1139 vCands = pNtk->GetPisInts();
1140 }
1141 std::shuffle(vCands.begin(), vCands.end(), rng);
1142 // remember fanins
1143 std::set<int> sFanins = pNtk->GetExtendedFanins(id);
1144 Print(3, "extended fanins", ":", sFanins);
1145 vsFanins.push_back(std::move(sFanins));
1146 // add
1147 MultiAdd(id, vCands, nMax);
1148 }
1149 // reduce
1150 RemoveRedundancy();
1151 mapNewFanins.clear();
1152 // TODO: we could quit here if nothing has been removed
1153 RemoveRedundancy();
1154 double dNewCost = CostFunction(pNtk);
1155 Print(2, "cost =", dCost, "->", dNewCost);
1156 if(!fGreedy || dNewCost <= dCost) {
1157 bool fChanged = false;
1158 if(dNewCost < dCost) {
1159 fChanged = true;
1160 } else {
1161 for(int id: vTargets) {
1162 if(!pNtk->IsInt(id)) {
1163 fChanged = true;
1164 break;
1165 }
1166 }
1167 for(int i = 0; !fChanged && i < int_size(vTargets); i++) {
1168 std::set<int> sNewFanins = pNtk->GetExtendedFanins(vTargets[i]);
1169 Print(3, "new extended fanins", ":", sNewFanins);
1170 if(vsFanins[i] != sNewFanins) {
1171 fChanged = true;
1172 }
1173 }
1174 }
1175 if(fChanged) {
1176 for(int id: vTargets) {
1177 if(pNtk->IsInt(id)) {
1178 pNtk->TrivialDecompose(id);
1179 }
1180 }
1181 pNtk->PopBack();
1182 return true;
1183 }
1184 }
1185 pNtk->Load(slot);
1186 pNtk->PopBack();
1187 return false;
1188 }
1189
1190 /* }}} */
1191
1192 /* {{{ Apply */
1193
1194 template <typename Ntk, typename Ana>
1195 void Optimizer<Ntk, Ana>::ApplyReverseTopologically(std::function<void(int)> const &func) {
1196 std::vector<int> vInts = pNtk->GetInts();
1197 for(critr it = vInts.rbegin(); it != vInts.rend(); it++) {
1198 if(Timeout()) {
1199 break;
1200 }
1201 if(!pNtk->IsInt(*it)) {
1202 continue;
1203 }
1204 Print(1, "node", *it, "(", int_distance(vInts.crbegin(), it) + 1, "/", int_size(vInts), ")", ":", "cost", "=", CostFunction(pNtk));
1205 func(*it);
1206 }
1207 }
1208
1209 template <typename Ntk, typename Ana>
1210 void Optimizer<Ntk, Ana>::ApplyRandomlyStop(std::function<bool(int)> const &func) {
1211 std::vector<int> vInts = pNtk->GetInts();
1212 std::shuffle(vInts.begin(), vInts.end(), rng);
1213 for(citr it = vInts.begin(); it != vInts.end(); it++) {
1214 if(Timeout()) {
1215 break;
1216 }
1217 if(!pNtk->IsInt(*it)) {
1218 continue;
1219 }
1220 Print(1, "node", *it, "(", int_distance(vInts.cbegin(), it) + 1, "/", int_size(vInts), ")", ":", "cost", "=", CostFunction(pNtk));
1221 if(func(*it)) {
1222 break;
1223 }
1224 }
1225 }
1226
1227 template <typename Ntk, typename Ana>
1228 void Optimizer<Ntk, Ana>::ApplyCombinationRandomlyStop(int k, std::function<bool(std::vector<int> const &)> const &func) {
1229 std::vector<int> vInts = pNtk->GetInts();
1230 std::shuffle(vInts.begin(), vInts.end(), rng); // order is decided here, so it's not truely exhaustive
1231 int nTried_ = 0;
1232 int nCombs = k * (k - 1) / 2;
1233 ForEachCombinationStop(int_size(vInts), k, [&](std::vector<int> const &vIdxs) {
1234 Print(1, "comb", vIdxs, "(", ++nTried_, "/", nCombs, ")");
1235 assert(int_size(vIdxs) == k);
1236 if(Timeout()) {
1237 return true;
1238 }
1239 std::vector<int> vTargets(k);
1240 for(int i = 0; i < k; i++) {
1241 vTargets[i] = vInts[vIdxs[i]];
1242 }
1243 return func(vTargets);
1244 });
1245 }
1246
1247 template <typename Ntk, typename Ana>
1248 void Optimizer<Ntk, Ana>::ApplyCombinationSampledRandomlyStop(int k, int nSamples, std::function<bool(std::vector<int> const &)> const &func) {
1249 std::vector<int> vInts = pNtk->GetInts();
1250 for(int i = 0; i < nSamples; i++) {
1251 if(Timeout()) {
1252 break;
1253 }
1254 std::set<int> sIdxs;
1255 while(int_size(sIdxs) < k) {
1256 int idx = rng() % pNtk->GetNumInts();
1257 sIdxs.insert(idx);
1258 }
1259 std::vector<int> vIdxs(sIdxs.begin(), sIdxs.end());
1260 std::shuffle(vIdxs.begin(), vIdxs.end(), rng);
1261 Print(1, "comb", vIdxs, "(", i + 1, "/", nSamples, ")");
1262 std::vector<int> vTargets(k);
1263 for(int i = 0; i < k; i++) {
1264 vTargets[i] = vInts[vIdxs[i]];
1265 }
1266 if(func(vTargets)) {
1267 break;
1268 }
1269 }
1270 }
1271
1272 /* }}} */
1273
1274 /* {{{ Constructors */
1275
1276 template <typename Ntk, typename Ana>
1277 Optimizer<Ntk, Ana>::Optimizer(Parameter const *pPar, std::function<double(Ntk *)> CostFunction) :
1278 pNtk(NULL),
1279 nVerbose(pPar->nOptimizerVerbose),
1280 CostFunction(CostFunction),
1281 nSortTypeOriginal(pPar->nSortType),
1282 nSortType(pPar->nSortType),
1283 nFlow(pPar->nOptimizerFlow),
1284 nDistance(pPar->nDistance),
1285 fCompatible(pPar->fUseBddCspf),
1286 fGreedy(pPar->fGreedy),
1287 ana(pPar),
1288 target(-1) {
1289 }
1290
1291 template <typename Ntk, typename Ana>
1292 void Optimizer<Ntk, Ana>::AssignNetwork(Ntk *pNtk_, bool fReuse) {
1293 pNtk = pNtk_;
1294 target = -1;
1295 pNtk->AddCallback(std::bind(&Optimizer<Ntk, Ana>::ActionCallback, this, std::placeholders::_1));
1296 ana.AssignNetwork(pNtk, fReuse);
1297 }
1298
1299 template <typename Ntk, typename Ana>
1300 void Optimizer<Ntk, Ana>::SetPrintLine(std::function<void(std::string)> const &PrintLine_) {
1301 PrintLine = PrintLine_;
1302 }
1303
1304 /* }}} */
1305
1306 /* {{{ Run */
1307
1308 template <typename Ntk, typename Ana>
1309 void Optimizer<Ntk, Ana>::Run(int iSeed, seconds nTimeout_) {
1310 rng.seed(iSeed);
1311 vRandPiOrder.clear();
1312 vRandCosts.clear();
1313 if(nSortTypeOriginal < 0) {
1314 nSortType = rng() % 18;
1315 Print(0, "fanin cost function =", nSortType);
1316 }
1317 nTimeout = nTimeout_;
1318 start = GetCurrentTime();
1319 switch(nFlow) {
1320 case 0:
1321 RemoveRedundancy();
1322 statsLocal.Reset();
1323 ApplyReverseTopologically([&](int id) {
1324 std::vector<int> vCands;
1325 if(nDistance) {
1326 vCands = pNtk->GetNeighbors(id, true, nDistance);
1327 } else {
1328 vCands = pNtk->GetPisInts();
1329 }
1330 SingleResub(id, vCands);
1331 });
1332 stats["single"] += statsLocal;
1333 Print(0, statsLocal.GetString());
1334 break;
1335 case 1:
1336 RemoveRedundancy();
1337 statsLocal.Reset();
1338 ApplyReverseTopologically([&](int id) {
1339 std::vector<int> vCands;
1340 if(nDistance) {
1341 vCands = pNtk->GetNeighbors(id, true, nDistance);
1342 } else {
1343 vCands = pNtk->GetPisInts();
1344 }
1345 MultiResub(id, vCands);
1346 });
1347 stats["multi"] += statsLocal;
1348 Print(0, statsLocal.GetString());
1349 break;
1350 case 2: {
1351 RemoveRedundancy();
1352 double dCost = CostFunction(pNtk);
1353 while(true) {
1354 statsLocal.Reset();
1355 ApplyReverseTopologically([&](int id) {
1356 std::vector<int> vCands;
1357 if(nDistance) {
1358 vCands = pNtk->GetNeighbors(id, true, nDistance);
1359 } else {
1360 vCands = pNtk->GetPisInts();
1361 }
1362 SingleResub(id, vCands);
1363 });
1364 stats["single"] += statsLocal;
1365 Print(0, "single", ":", "cost", "=", CostFunction(pNtk), ",", statsLocal.GetString());
1366 statsLocal.Reset();
1367 ApplyReverseTopologically([&](int id) {
1368 std::vector<int> vCands;
1369 if(nDistance) {
1370 vCands = pNtk->GetNeighbors(id, true, nDistance);
1371 } else {
1372 vCands = pNtk->GetPisInts();
1373 // vCands = pNtk->GetInts();
1374 }
1375 MultiResub(id, vCands);
1376 });
1377 stats["multi"] += statsLocal;
1378 Print(0, "multi ", ":", "cost", "=", CostFunction(pNtk), ",", statsLocal.GetString());
1379 double dNewCost = CostFunction(pNtk);
1380 if(dNewCost < dCost) {
1381 dCost = dNewCost;
1382 } else {
1383 break;
1384 }
1385 }
1386 break;
1387 }
1388 case 3: {
1389 RemoveRedundancy();
1390 std::vector<int> vCands;
1391 if(!nDistance) {
1392 vCands = pNtk->GetPisInts();
1393 std::shuffle(vCands.begin(), vCands.end(), rng);
1394 }
1395 Stats statsSingle, statsMulti;
1396 ApplyRandomlyStop([&](int id) {
1397 statsLocal.Reset();
1398 if(nDistance) {
1399 vCands = pNtk->GetNeighbors(id, true, nDistance);
1400 std::shuffle(vCands.begin(), vCands.end(), rng);
1401 }
1402 bool fChanged;
1403 if(rng() & 1) {
1404 fChanged = SingleResubStop(id, vCands);
1405 statsSingle += statsLocal;
1406 } else {
1407 fChanged = MultiResubStop(id, vCands);
1408 statsMulti += statsLocal;
1409 }
1410 return fChanged;
1411 });
1412 stats["single"] += statsSingle;
1413 stats["multi"] += statsMulti;
1414 Print(0, "single", ":", statsSingle.GetString());
1415 Print(0, "multi ", ":", statsMulti.GetString());
1416 break;
1417 }
1418 case 4: {
1419 RemoveRedundancy();
1420 ApplyCombinationSampledRandomlyStop(3, 100, [&](std::vector<int> const &vTargets) {
1421 return MultiTargetResub(vTargets);
1422 });
1423 break;
1424 }
1425 default:
1426 assert(0);
1427 }
1428 }
1429
1430 /* }}} */
1431
1432 /* {{{ Summary */
1433
1434 template <typename Ntk, typename Ana>
1435 void Optimizer<Ntk, Ana>::ResetSummary() {
1436 stats.clear();
1437 ana.ResetSummary();
1438 }
1439
1440 template <typename Ntk, typename Ana>
1441 summary<int> Optimizer<Ntk, Ana>::GetStatsSummary() const {
1442 summary<int> v;
1443 for(auto const &entry: stats) {
1444 v.emplace_back("opt " + entry.first + " tried node", entry.second.nTried);
1445 v.emplace_back("opt " + entry.first + " tried fanin", entry.second.nTriedFis);
1446 v.emplace_back("opt " + entry.first + " added node", entry.second.nAdded);
1447 v.emplace_back("opt " + entry.first + " added fanin", entry.second.nAddedFis);
1448 v.emplace_back("opt " + entry.first + " changed", entry.second.nChanged);
1449 v.emplace_back("opt " + entry.first + " up", entry.second.nUps);
1450 v.emplace_back("opt " + entry.first + " eq", entry.second.nEqs);
1451 v.emplace_back("opt " + entry.first + " dn", entry.second.nDowns);
1452 }
1453 summary<int> v2 = ana.GetStatsSummary();
1454 v.insert(v.end(), v2.begin(), v2.end());
1455 return v;
1456 }
1457
1458 template <typename Ntk, typename Ana>
1459 summary<double> Optimizer<Ntk, Ana>::GetTimesSummary() const {
1460 summary<double> v;
1461 for(auto const &entry: stats) {
1462 v.emplace_back("opt " + entry.first + " add", entry.second.durationAdd);
1463 v.emplace_back("opt " + entry.first + " reduce", entry.second.durationReduce);
1464 }
1465 summary<double> v2 = ana.GetTimesSummary();
1466 v.insert(v.end(), v2.begin(), v2.end());
1467 return v;
1468 }
1469
1470 /* }}} */
1471
1472}
1473
1474ABC_NAMESPACE_CXX_HEADER_END
ABC_NAMESPACE_CXX_HEADER_START
#define ABC_NAMESPACE_CXX_HEADER_START
Definition abc_namespaces.h:52
ABC_NAMESPACE_CXX_HEADER_END
#define ABC_NAMESPACE_CXX_HEADER_END
Definition abc_namespaces.h:53
rrr::Optimizer::GetTimesSummary
summary< double > GetTimesSummary() const
Definition rrrOptimizer.h:1459
rrr::Optimizer::AssignNetwork
void AssignNetwork(Ntk *pNtk_, bool fReuse=false)
Definition rrrOptimizer.h:1292
rrr::Optimizer::SetPrintLine
void SetPrintLine(std::function< void(std::string)> const &PrintLine_)
Definition rrrOptimizer.h:1300
rrr::Optimizer::Run
void Run(int iSeed=0, seconds nTimeout_=0)
Definition rrrOptimizer.h:1309
rrr::Optimizer::GetStatsSummary
summary< int > GetStatsSummary() const
Definition rrrOptimizer.h:1441
rrr::Optimizer::Optimizer
Optimizer(Parameter const *pPar, std::function< double(Ntk *)> CostFunction)
Definition rrrOptimizer.h:1277
rrr
Definition rrr.h:16
rrr::seconds
int64_t seconds
Definition rrrTypes.h:61
rrr::summary
std::vector< std::pair< std::string, T > > summary
Definition rrrTypes.h:66
rrr::POP_BACK
@ POP_BACK
Definition rrrTypes.h:45
rrr::REMOVE_BUFFER
@ REMOVE_BUFFER
Definition rrrTypes.h:36
rrr::REMOVE_UNUSED
@ REMOVE_UNUSED
Definition rrrTypes.h:35
rrr::TRIVIAL_DECOMPOSE
@ TRIVIAL_DECOMPOSE
Definition rrrTypes.h:40
rrr::TRIVIAL_COLLAPSE
@ TRIVIAL_COLLAPSE
Definition rrrTypes.h:39
rrr::SAVE
@ SAVE
Definition rrrTypes.h:43
rrr::REMOVE_CONST
@ REMOVE_CONST
Definition rrrTypes.h:37
rrr::LOAD
@ LOAD
Definition rrrTypes.h:44
rrr::SORT_FANINS
@ SORT_FANINS
Definition rrrTypes.h:41
rrr::REMOVE_FANIN
@ REMOVE_FANIN
Definition rrrTypes.h:34
rrr::ADD_FANIN
@ ADD_FANIN
Definition rrrTypes.h:38
rrr::READ
@ READ
Definition rrrTypes.h:42
rrr::PrintNext
void PrintNext(std::ostream &os, T t)
Definition rrrUtils.h:218
rrr::time_point
std::chrono::time_point< clock_type > time_point
Definition rrrTypes.h:63
rrr::Optimizer::Stats::GetString
std::string GetString() const
Definition rrrOptimizer.h:171
rrr::Optimizer::Stats::operator+=
Stats & operator+=(Stats const &other)
Definition rrrOptimizer.h:157
assert
#define assert(ex)
Definition util_old.h:213