1 // OpenSTA, Static Timing Analyzer
2 // Copyright (c) 2021, Parallax Software, Inc.
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <https://www.gnu.org/licenses/>.
16
17 #include "ExceptionPath.hh"
18
19 #include <algorithm>
20
21 #include "DisallowCopyAssign.hh"
22 #include "MinMax.hh"
23 #include "TimingRole.hh"
24 #include "Units.hh"
25 #include "Transition.hh"
26 #include "PortDirection.hh"
27 #include "Network.hh"
28 #include "NetworkCmp.hh"
29 #include "Clock.hh"
30
31 namespace sta {
32
33 static bool
34 thrusIntersectPts(ExceptionThruSeq *thrus1,
35 ExceptionThruSeq *thrus2);
36 static void
37 insertPinPairsThruHierPin(const Pin *hpin,
38 const Network *network,
39 PinPairSet *pairs);
40 static void
41 insertPinPairsThruNet(Net *net,
42 const Network *network,
43 PinPairSet *pairs);
44 static void
45 deletePinPairsThruHierPin(const Pin *hpin,
46 const Network *network,
47 PinPairSet *pairs);
48 static int
setNameCmp(PinSet * set1,PinSet * set2,const Network * network)49 setNameCmp(PinSet *set1,
50 PinSet *set2,
51 const Network *network)
52 {
53 size_t size1 = set1 ? set1->size() : 0;
54 size_t size2 = set2 ? set2->size() : 0;
55 if (size1 == size2) {
56 PinSet::ConstIterator iter1(set1);
57 PinSet::ConstIterator iter2(set2);
58 while (iter1.hasNext() && iter2.hasNext()) {
59 Pin *pin1 = iter1.next();
60 Pin *pin2 = iter2.next();
61 const char *name1 = network->pathName(pin1);
62 const char *name2 = network->pathName(pin2);
63 int cmp = strcmp(name1, name2);
64 if (cmp != 0)
65 return cmp;
66 }
67 // Sets are equal.
68 return 0;
69 }
70 else
71 return (size1 > size2) ? 1 : -1;
72 }
73
74 static int
setNameCmp(ClockSet * set1,ClockSet * set2)75 setNameCmp(ClockSet *set1,
76 ClockSet *set2)
77 {
78 size_t size1 = set1 ? set1->size() : 0;
79 size_t size2 = set2 ? set2->size() : 0;
80 if (size1 == size2) {
81 ClockSet::ConstIterator iter1(set1);
82 ClockSet::ConstIterator iter2(set2);
83 while (iter1.hasNext() && iter2.hasNext()) {
84 Clock *clk1 = iter1.next();
85 Clock *clk2 = iter2.next();
86 int cmp = clk1->index() - clk2->index();
87 if (cmp != 0)
88 return cmp;
89 }
90 // Sets are equal.
91 return 0;
92 }
93 else
94 return (size1 > size2) ? 1 : -1;
95 }
96
97 static int
setNameCmp(InstanceSet * set1,InstanceSet * set2,const Network * network)98 setNameCmp(InstanceSet *set1,
99 InstanceSet *set2,
100 const Network *network)
101 {
102 size_t size1 = set1 ? set1->size() : 0;
103 size_t size2 = set2 ? set2->size() : 0;
104 if (size1 == size2) {
105 InstanceSet::ConstIterator iter1(set1);
106 InstanceSet::ConstIterator iter2(set2);
107 while (iter1.hasNext() && iter2.hasNext()) {
108 Instance *inst1 = iter1.next();
109 Instance *inst2 = iter2.next();
110 const char *name1 = network->pathName(inst1);
111 const char *name2 = network->pathName(inst2);
112 int cmp = strcmp(name1, name2);
113 if (cmp != 0)
114 return cmp;
115 }
116 // Sets are equal.
117 return 0;
118 }
119 else
120 return (size1 > size2) ? 1 : -1;
121 }
122
123 static int
setNameCmp(NetSet * set1,NetSet * set2,const Network * network)124 setNameCmp(NetSet *set1,
125 NetSet *set2,
126 const Network *network)
127 {
128 size_t size1 = set1 ? set1->size() : 0;
129 size_t size2 = set2 ? set2->size() : 0;
130 if (size1 == size2) {
131 NetSet::ConstIterator iter1(set1);
132 NetSet::ConstIterator iter2(set2);
133 while (iter1.hasNext() && iter2.hasNext()) {
134 Net *net1 = iter1.next();
135 Net *net2 = iter2.next();
136 const char *name1 = network->pathName(net1);
137 const char *name2 = network->pathName(net2);
138 int cmp = strcmp(name1, name2);
139 if (cmp != 0)
140 return cmp;
141 }
142 // Sets are equal.
143 return 0;
144 }
145 else
146 return (size1 > size2) ? 1 : -1;
147 }
148
149 ////////////////////////////////////////////////////////////////
150
151 const char *
what() const152 EmptyExpceptionPt::what() const noexcept
153 {
154 return "empty exception from/through/to.";
155 }
156
157 void
checkFromThrusTo(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to)158 checkFromThrusTo(ExceptionFrom *from,
159 ExceptionThruSeq *thrus,
160 ExceptionTo *to)
161 {
162 bool found_empty = ((from && !from->hasObjects())
163 || (to
164 && (!to->hasObjects()
165 && to->transition()
166 == RiseFallBoth::riseFall()
167 && (to->endTransition()
168 == RiseFallBoth::riseFall()))));
169 if (thrus) {
170 ExceptionThruSeq::Iterator thru_iter(thrus);
171 while (thru_iter.hasNext()) {
172 ExceptionThru *thru = thru_iter.next();
173 if (!thru->hasObjects())
174 found_empty = true;
175 }
176 }
177 if (found_empty)
178 throw EmptyExpceptionPt();
179 }
180
ExceptionPath(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMaxAll * min_max,bool own_pts,int priority,const char * comment)181 ExceptionPath::ExceptionPath(ExceptionFrom *from,
182 ExceptionThruSeq *thrus,
183 ExceptionTo *to,
184 const MinMaxAll *min_max,
185 bool own_pts,
186 int priority,
187 const char *comment) :
188 SdcCmdComment(comment),
189 from_(from),
190 thrus_(thrus),
191 to_(to),
192 min_max_(min_max),
193 own_pts_(own_pts),
194 priority_(priority)
195 {
196 makeStates();
197 }
198
~ExceptionPath()199 ExceptionPath::~ExceptionPath()
200 {
201 if (own_pts_) {
202 delete from_;
203 delete to_;
204 if (thrus_) {
205 thrus_->deleteContents();
206 delete thrus_;
207 }
208 }
209 ExceptionState *state, *next_state;
210 for (state = states_; state; state = next_state) {
211 next_state = state->nextState();
212 delete state;
213 }
214 }
215
216 const char *
asString(const Network * network) const217 ExceptionPath::asString(const Network *network) const
218 {
219 const char *from_thru_to = fromThruToString(network);
220 const char *type = typeString();
221 size_t length = strlen(type) + strlen(from_thru_to) + 1;
222 char *result = makeTmpString(length);
223 char *r = result;
224 stringAppend(r, type);
225 stringAppend(r, from_thru_to);
226 return result;
227 }
228
229 ExceptionPt *
firstPt()230 ExceptionPath::firstPt()
231 {
232 if (from_)
233 return from_;
234 else if (thrus_ && !thrus_->empty())
235 return (*thrus_)[0];
236 else if (to_)
237 return to_;
238 else
239 return nullptr;
240 }
241
242 bool
matchesFirstPt(const RiseFall * to_rf,const MinMax * min_max)243 ExceptionPath::matchesFirstPt(const RiseFall *to_rf,
244 const MinMax *min_max)
245 {
246 ExceptionPt *first_pt = firstPt();
247 return first_pt->transition()->matches(to_rf)
248 && matches(min_max, false);
249 }
250
251 bool
matches(const MinMax * min_max,bool) const252 ExceptionPath::matches(const MinMax *min_max,
253 bool) const
254 {
255 return min_max_->matches(min_max);
256 }
257
258 void
setPriority(int priority)259 ExceptionPath::setPriority(int priority)
260 {
261 priority_ = priority;
262 }
263
264 ////////////////////////////////////////////////////////////////
265 // Exception precedence relative to from/thru/to pins/clocks:
266 // Priority order:
267 // 1) -from pin/instance/port
268 // 2) -to pin/instance/port
269 // 3) -through pin
270 // 4) -from clock
271 // 5) -to clock
272 //
273 // Foreach priority level (from 1 to 5)
274 // If the exception has this type of qualifier, it takes
275 // priority over an exception without this type of qualifier.
276 int
fromThruToPriority(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to)277 ExceptionPath::fromThruToPriority(ExceptionFrom *from,
278 ExceptionThruSeq *thrus,
279 ExceptionTo *to)
280 {
281 int priority = 0;
282 if (from && (from->hasPins() || from->hasInstances()))
283 priority |= (1 << 6);
284 if (to && (to->hasPins() || to->hasInstances()))
285 priority |= (1 << 5);
286 if (thrus && !thrus->empty())
287 priority |= (1 << 4);
288 if (from && from->hasClocks())
289 priority |= (1 << 3);
290 if (to && to->hasClocks())
291 priority |= (1 << 2);
292 // Leave room for minMaxPriority() which uses bits 0 and 1.
293 return priority;
294 }
295
296 size_t
hash() const297 ExceptionPath::hash() const
298 {
299 return hash(nullptr);
300 }
301
302 size_t
hash(ExceptionPt * missing_pt) const303 ExceptionPath::hash(ExceptionPt *missing_pt) const
304 {
305 size_t hash = typePriority();
306 int pot = 32;
307 ExceptionPtIterator pt_iter(this);
308 while (pt_iter.hasNext()) {
309 ExceptionPt *pt = pt_iter.next();
310 if (pt != missing_pt)
311 hash += pt->hash() * (pot - 1);
312 pot *= 2;
313 }
314 return hash;
315 }
316
317 bool
mergeable(ExceptionPath * exception) const318 ExceptionPath::mergeable(ExceptionPath *exception) const
319 {
320 return stringEqualIf(comment_, exception->comment());
321 }
322
323 bool
mergeablePts(ExceptionPath * exception) const324 ExceptionPath::mergeablePts(ExceptionPath *exception) const
325 {
326 ExceptionPt *ignore;
327 return mergeablePts(exception, nullptr, ignore);
328 }
329
330 bool
mergeablePts(ExceptionPath * exception2,ExceptionPt * missing_pt2,ExceptionPt * & missing_pt) const331 ExceptionPath::mergeablePts(ExceptionPath *exception2,
332 ExceptionPt *missing_pt2,
333 ExceptionPt *&missing_pt) const
334 {
335 missing_pt = nullptr;
336 ExceptionFrom *from2 = exception2->from();
337 if ((from_ && from2
338 && !(from_->transition() == from2->transition()
339 && (from2 == missing_pt2
340 || from_->equal(from2))))
341 || (from_ && from2 == nullptr)
342 || (from_ == nullptr && from2))
343 return false;
344 if (from2 == missing_pt2)
345 missing_pt = from_;
346
347 ExceptionThruSeq::Iterator thru_iter(thrus_);
348 ExceptionThruSeq::Iterator thru_iter2(exception2->thrus());
349 while (thru_iter.hasNext()
350 && thru_iter2.hasNext()) {
351 ExceptionThru *thru = thru_iter.next();
352 ExceptionThru *thru2 = thru_iter2.next();
353 if (!(thru->transition() == thru2->transition()
354 && (thru2 == missing_pt2
355 || thru->equal(thru))))
356 return false;
357 if (thru2 == missing_pt2)
358 missing_pt = thru;
359 }
360 if (thru_iter.hasNext()
361 || thru_iter2.hasNext())
362 return false;
363
364 ExceptionTo *to2 = exception2->to();
365 if ((to_ && to2
366 && !(to_->transition() == to2->transition()
367 && to_->endTransition() == to2->endTransition()
368 && (to2 == missing_pt2
369 || to_->equal(to2))))
370 || (to_ && to2 == nullptr)
371 || (to_ == nullptr && to2))
372 return false;
373 if (to2 == missing_pt2)
374 missing_pt = to_;
375 return true;
376 }
377
378 bool
intersectsPts(ExceptionPath * exception) const379 ExceptionPath::intersectsPts(ExceptionPath *exception) const
380 {
381 ExceptionFrom *from2 = exception->from();
382 ExceptionThruSeq *thrus2 = exception->thrus();
383 ExceptionTo *to2 = exception->to();
384 if (((from_ == nullptr && from2 == nullptr)
385 || (from_ && from2 && from_->intersectsPts(from2)))
386 && ((thrus_ == nullptr && thrus2 == nullptr)
387 || (thrus_ && thrus2 && thrus_->size() == thrus2->size()))
388 && ((to_ == nullptr && to2 == nullptr)
389 || (to_ && to2 && to_->intersectsPts(to2)))) {
390 ExceptionThruSeq::Iterator thrus_iter1(thrus_);
391 ExceptionThruSeq::Iterator thrus_iter2(thrus2);
392 while (thrus_iter1.hasNext() && thrus_iter2.hasNext()) {
393 ExceptionThru *thru1 = thrus_iter1.next();
394 ExceptionThru *thru2 = thrus_iter2.next();
395 if (!thru1->intersectsPts(thru2))
396 return false;
397 }
398 return true;
399 }
400 return false;
401 }
402
403 const char *
fromThruToString(const Network * network) const404 ExceptionPath::fromThruToString(const Network *network) const
405 {
406 string str;
407 if (min_max_ != MinMaxAll::all()) {
408 str += " -";
409 str += min_max_->asString();
410 }
411
412 if (from_)
413 str += from_->asString(network);
414
415 if (thrus_) {
416 str += " -thru";
417 bool first_thru = true;
418 ExceptionThruSeq::Iterator thru_iter(thrus_);
419 while (thru_iter.hasNext()) {
420 ExceptionThru *thru = thru_iter.next();
421 if (!first_thru)
422 str += " &&";
423 str += " {";
424 str += thru->asString(network);
425 str += "}";
426 first_thru = false;
427 }
428 }
429
430 if (to_)
431 str += to_->asString(network);
432
433 char *result = makeTmpString(str.size() + 1);
434 strcpy(result, str.c_str());
435 return result;
436 }
437
438 ExceptionState *
firstState()439 ExceptionPath::firstState()
440 {
441 return states_;
442 }
443
444 void
makeStates()445 ExceptionPath::makeStates()
446 {
447 if (thrus_) {
448 ExceptionState *prev_state = nullptr;
449 ExceptionThruSeq::Iterator thru_iter(thrus_);
450 bool first = true;
451 int index = 0;
452 while (thru_iter.hasNext()) {
453 ExceptionThru *thru = thru_iter.next();
454 // No state for first -thru if no -from,since it kicks off the exception.
455 if (!(from_ == nullptr && first)) {
456 ExceptionState *state = new ExceptionState(this, thru, index);
457 if (prev_state)
458 prev_state->setNextState(state);
459 else
460 states_ = state;
461 prev_state = state;
462 }
463 first = false;
464 index++;
465 }
466 // Last state indicates all the thrus have been traversed.
467 ExceptionState *state = new ExceptionState(this, nullptr, index);
468 if (prev_state)
469 prev_state->setNextState(state);
470 else
471 states_ = state;
472 }
473 else
474 states_ = new ExceptionState(this, nullptr, 0);
475 }
476
477 bool
resetMatch(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMaxAll * min_max)478 ExceptionPath::resetMatch(ExceptionFrom *from,
479 ExceptionThruSeq *thrus,
480 ExceptionTo *to,
481 const MinMaxAll *min_max)
482 {
483 // Only the reset expception points need to match.
484 // For example, if the reset is -from, it matches any
485 // exceptions that match the -from even if they are more specific.
486 // -from
487 return ((from && from_
488 && thrus == nullptr
489 && to == nullptr
490 && from_->intersectsPts(from))
491 // -thru
492 || (from == nullptr
493 && thrus && thrus_
494 && to == nullptr
495 && thrusIntersectPts(thrus_, thrus))
496 // -to
497 || (from == nullptr
498 && thrus == nullptr
499 && to && to_
500 && to_->intersectsPts(to))
501 // -from -thru
502 || (from && from_
503 && thrus && thrus_
504 && to == nullptr
505 && from_->intersectsPts(from)
506 && thrusIntersectPts(thrus_, thrus))
507 // -from -to
508 || (from && from_
509 && thrus == nullptr
510 && to && to_
511 && from_->intersectsPts(from)
512 && to_->intersectsPts(to))
513 // -thru -to
514 || (from == nullptr
515 && thrus && thrus_
516 && to && to_
517 && thrusIntersectPts(thrus_, thrus)
518 && to_->intersectsPts(to))
519 // -from -thru -to
520 || (from && from_
521 && thrus && thrus_
522 && to && to_
523 && from_->intersectsPts(from)
524 && thrusIntersectPts(thrus_, thrus)
525 && to_->intersectsPts(to)))
526 && (min_max == MinMaxAll::all()
527 || min_max_ == min_max);
528 }
529
530 static bool
thrusIntersectPts(ExceptionThruSeq * thrus1,ExceptionThruSeq * thrus2)531 thrusIntersectPts(ExceptionThruSeq *thrus1,
532 ExceptionThruSeq *thrus2)
533 {
534 ExceptionThruSeq::Iterator thrus_iter1(thrus1);
535 ExceptionThruSeq::Iterator thrus_iter2(thrus2);
536 while (thrus_iter1.hasNext() && thrus_iter2.hasNext()) {
537 ExceptionThru *thru1 = thrus_iter1.next();
538 ExceptionThru *thru2 = thrus_iter2.next();
539 if (!thru1->intersectsPts(thru2))
540 return false;
541 }
542 return true;
543 }
544
545 ////////////////////////////////////////////////////////////////
546
PathDelay(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMax * min_max,bool ignore_clk_latency,float delay,bool own_pts,const char * comment)547 PathDelay::PathDelay(ExceptionFrom *from,
548 ExceptionThruSeq *thrus,
549 ExceptionTo *to,
550 const MinMax *min_max,
551 bool ignore_clk_latency,
552 float delay,
553 bool own_pts,
554 const char *comment) :
555 ExceptionPath(from, thrus, to, min_max->asMinMaxAll(), own_pts,
556 pathDelayPriority() + fromThruToPriority(from, thrus, to),
557 comment),
558 ignore_clk_latency_(ignore_clk_latency),
559 delay_(delay)
560 {
561 }
562
563 ExceptionPath *
clone(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)564 PathDelay::clone(ExceptionFrom *from,
565 ExceptionThruSeq *thrus,
566 ExceptionTo *to,
567 bool own_pts)
568 {
569 return new PathDelay(from, thrus, to, min_max_->asMinMax(),
570 ignore_clk_latency_, delay_, own_pts,
571 comment_);
572 }
573
574 int
typePriority() const575 PathDelay::typePriority() const
576 {
577 return pathDelayPriority();
578 }
579
580 bool
tighterThan(ExceptionPath * exception) const581 PathDelay::tighterThan(ExceptionPath *exception) const
582 {
583 if (min_max_->asMinMax() == MinMax::min())
584 return delay_ > exception->delay();
585 else
586 return delay_ < exception->delay();
587 }
588
589 const char *
asString(const Network * network) const590 PathDelay::asString(const Network *network) const
591 {
592 const char *from_thru_to = fromThruToString(network);
593 const char *result = stringPrintTmp("PathDelay %.3fns%s",
594 delay_ * 1E+9F,
595 from_thru_to);
596 return result;
597 }
598
599 const char *
typeString() const600 PathDelay::typeString() const
601 {
602 return "Path";
603 }
604
605 bool
mergeable(ExceptionPath * exception) const606 PathDelay::mergeable(ExceptionPath *exception) const
607 {
608 return ExceptionPath::mergeable(exception)
609 && overrides(exception)
610 && exception->ignoreClkLatency() == ignore_clk_latency_
611 && exception->delay() == delay_;
612 }
613
614 bool
overrides(ExceptionPath * exception) const615 PathDelay::overrides(ExceptionPath *exception) const
616 {
617 return exception->isPathDelay()
618 && exception->priority() == priority_
619 && exception->minMax() == min_max_;
620 }
621
622 ////////////////////////////////////////////////////////////////
623
FalsePath(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMaxAll * min_max,bool own_pts,const char * comment)624 FalsePath::FalsePath(ExceptionFrom *from,
625 ExceptionThruSeq *thrus,
626 ExceptionTo *to,
627 const MinMaxAll *min_max,
628 bool own_pts,
629 const char *comment) :
630 ExceptionPath(from, thrus, to, min_max, own_pts,
631 falsePathPriority() + fromThruToPriority(from, thrus, to),
632 comment)
633 {
634 }
635
FalsePath(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMaxAll * min_max,bool own_pts,int priority,const char * comment)636 FalsePath::FalsePath(ExceptionFrom *from,
637 ExceptionThruSeq *thrus,
638 ExceptionTo *to,
639 const MinMaxAll *min_max,
640 bool own_pts,
641 int priority,
642 const char *comment) :
643 ExceptionPath(from, thrus, to, min_max, own_pts, priority, comment)
644 {
645 }
646
647 ExceptionPath *
clone(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)648 FalsePath::clone(ExceptionFrom *from,
649 ExceptionThruSeq *thrus,
650 ExceptionTo *to,
651 bool own_pts)
652 {
653 return new FalsePath(from, thrus, to, min_max_, own_pts, comment_);
654 }
655
656 int
typePriority() const657 FalsePath::typePriority() const
658 {
659 return falsePathPriority();
660 }
661
662 bool
tighterThan(ExceptionPath *) const663 FalsePath::tighterThan(ExceptionPath *) const
664 {
665 return false;
666 }
667
668 const char *
typeString() const669 FalsePath::typeString() const
670 {
671 return "False";
672 }
673
674 bool
mergeable(ExceptionPath * exception) const675 FalsePath::mergeable(ExceptionPath *exception) const
676 {
677 return ExceptionPath::mergeable(exception)
678 && overrides(exception);
679 }
680
681 bool
overrides(ExceptionPath * exception) const682 FalsePath::overrides(ExceptionPath *exception) const
683 {
684 return exception->priority() == priority()
685 && exception->minMax() == min_max_;
686 }
687
688 ////////////////////////////////////////////////////////////////
689
LoopPath(ExceptionThruSeq * thrus,bool own_pts)690 LoopPath::LoopPath(ExceptionThruSeq *thrus, bool own_pts) :
691 FalsePath(nullptr, thrus, nullptr, MinMaxAll::all(), own_pts,
692 falsePathPriority() + fromThruToPriority(nullptr, thrus, nullptr),
693 nullptr)
694 {
695 }
696
697 const char *
typeString() const698 LoopPath::typeString() const
699 {
700 return "Loop";
701 }
702
703 bool
mergeable(ExceptionPath *) const704 LoopPath::mergeable(ExceptionPath *) const
705 {
706 return false;
707 }
708
709 ////////////////////////////////////////////////////////////////
710
MultiCyclePath(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,const MinMaxAll * min_max,bool use_end_clk,int path_multiplier,bool own_pts,const char * comment)711 MultiCyclePath::MultiCyclePath(ExceptionFrom *from,
712 ExceptionThruSeq *thrus,
713 ExceptionTo *to,
714 const MinMaxAll *min_max,
715 bool use_end_clk,
716 int path_multiplier,
717 bool own_pts,
718 const char *comment) :
719 ExceptionPath(from, thrus, to, min_max, own_pts,
720 multiCyclePathPriority() + fromThruToPriority(from, thrus, to),
721 comment),
722 use_end_clk_(use_end_clk),
723 path_multiplier_(path_multiplier)
724 {
725 }
726
727 ExceptionPath *
clone(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)728 MultiCyclePath::clone(ExceptionFrom *from,
729 ExceptionThruSeq *thrus,
730 ExceptionTo *to,
731 bool own_pts)
732 {
733 return new MultiCyclePath(from, thrus, to, min_max_, use_end_clk_,
734 path_multiplier_, own_pts, comment_);
735 }
736
737 int
pathMultiplier(const MinMax * min_max) const738 MultiCyclePath::pathMultiplier(const MinMax *min_max) const
739 {
740 if (min_max_ == MinMaxAll::all()
741 && min_max == MinMax::min())
742 // Path multiplier is zero if no -setup/-hold is specified.
743 return 0;
744 else
745 return path_multiplier_;
746 }
747
748 int
priority(const MinMax * min_max) const749 MultiCyclePath::priority(const MinMax *min_max) const
750 {
751 if (min_max_ == MinMaxAll::all())
752 return priority_ + 1;
753 else if (min_max_->asMinMax() == min_max)
754 return priority_ + 2;
755 else
756 return priority_;
757 }
758
759 int
typePriority() const760 MultiCyclePath::typePriority() const
761 {
762 return multiCyclePathPriority();
763 }
764
765 bool
tighterThan(ExceptionPath * exception) const766 MultiCyclePath::tighterThan(ExceptionPath *exception) const
767 {
768 return path_multiplier_ < exception->pathMultiplier();
769 }
770
771 bool
matches(const MinMax * min_max,bool exactly) const772 MultiCyclePath::matches(const MinMax *min_max,
773 bool exactly) const
774 {
775 return min_max_->matches(min_max)
776 // set_multicycle_path -setup determines hold check accounting,
777 // so they must be propagated for min (hold) paths.
778 || (!exactly && min_max == MinMax::min());
779 }
780
781 const char *
asString(const Network * network) const782 MultiCyclePath::asString(const Network *network) const
783 {
784 const char *from_thru_to = fromThruToString(network);
785 const char *result = stringPrintTmp("Multicycle %s %d%s",
786 (use_end_clk_) ? "-end" : "-start",
787 path_multiplier_,
788 from_thru_to);
789 return result;
790 }
791
792 const char *
typeString() const793 MultiCyclePath::typeString() const
794 {
795 return "Multicycle";
796 }
797
798 bool
mergeable(ExceptionPath * exception) const799 MultiCyclePath::mergeable(ExceptionPath *exception) const
800 {
801 return ExceptionPath::mergeable(exception)
802 && overrides(exception)
803 && exception->pathMultiplier() == path_multiplier_;
804 }
805
806 bool
overrides(ExceptionPath * exception) const807 MultiCyclePath::overrides(ExceptionPath *exception) const
808 {
809 return exception->isMultiCycle()
810 && exception->priority() == priority()
811 && exception->minMax() == min_max_;
812 }
813
814 ////////////////////////////////////////////////////////////////
815
FilterPath(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)816 FilterPath::FilterPath(ExceptionFrom *from,
817 ExceptionThruSeq *thrus,
818 ExceptionTo *to,
819 bool own_pts) :
820 ExceptionPath(from, thrus, to, MinMaxAll::all(), own_pts,
821 filterPathPriority() + fromThruToPriority(from, thrus, to),
822 nullptr)
823 {
824 }
825
826 const char *
typeString() const827 FilterPath::typeString() const
828 {
829 return "Filter";
830 }
831
832 ExceptionPath *
clone(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)833 FilterPath::clone(ExceptionFrom *from,
834 ExceptionThruSeq *thrus,
835 ExceptionTo *to,
836 bool own_pts)
837 {
838 return new FilterPath(from, thrus, to, own_pts);
839 }
840
841 int
typePriority() const842 FilterPath::typePriority() const
843 {
844 return filterPathPriority();
845 }
846
847 bool
tighterThan(ExceptionPath *) const848 FilterPath::tighterThan(ExceptionPath *) const
849 {
850 return false;
851 }
852
853 // Filter paths are used for report -from/-thru/-to as well as
854 // generated clock insertion delays so do not let them merge.
855 bool
mergeable(ExceptionPath *) const856 FilterPath::mergeable(ExceptionPath *) const
857 {
858 return false;
859 }
860
861 bool
overrides(ExceptionPath *) const862 FilterPath::overrides(ExceptionPath *) const
863 {
864 return false;
865 }
866
867 bool
resetMatch(ExceptionFrom *,ExceptionThruSeq *,ExceptionTo *,const MinMaxAll *)868 FilterPath::resetMatch(ExceptionFrom *,
869 ExceptionThruSeq *,
870 ExceptionTo *,
871 const MinMaxAll *)
872 {
873 return false;
874 }
875
876 ////////////////////////////////////////////////////////////////
877
GroupPath(const char * name,bool is_default,ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts,const char * comment)878 GroupPath::GroupPath(const char *name,
879 bool is_default,
880 ExceptionFrom *from,
881 ExceptionThruSeq *thrus,
882 ExceptionTo *to,
883 bool own_pts,
884 const char *comment) :
885 ExceptionPath(from, thrus, to, MinMaxAll::all(), own_pts,
886 groupPathPriority() + fromThruToPriority(from, thrus, to),
887 comment),
888 name_(stringCopy(name)),
889 is_default_(is_default)
890 {
891 }
892
~GroupPath()893 GroupPath::~GroupPath()
894 {
895 stringDelete(name_);
896 }
897
898 const char *
typeString() const899 GroupPath::typeString() const
900 {
901 return "Group";
902 }
903
904 ExceptionPath *
clone(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool own_pts)905 GroupPath::clone(ExceptionFrom *from,
906 ExceptionThruSeq *thrus,
907 ExceptionTo *to,
908 bool own_pts)
909 {
910 return new GroupPath(name_, is_default_, from, thrus, to, own_pts,
911 comment_);
912 }
913
914 int
typePriority() const915 GroupPath::typePriority() const
916 {
917 return groupPathPriority();
918 }
919
920 bool
tighterThan(ExceptionPath *) const921 GroupPath::tighterThan(ExceptionPath *) const
922 {
923 return false;
924 }
925
926 bool
mergeable(ExceptionPath * exception) const927 GroupPath::mergeable(ExceptionPath *exception) const
928 {
929 return ExceptionPath::mergeable(exception)
930 && overrides(exception);
931 }
932
933 bool
overrides(ExceptionPath * exception) const934 GroupPath::overrides(ExceptionPath *exception) const
935 {
936 return exception->isGroupPath()
937 && is_default_ == exception->isDefault()
938 && stringEqIf(name_, exception->name());
939 }
940
941 ////////////////////////////////////////////////////////////////
942
943 const int ExceptionPt::as_string_max_objects_ = 20;
944
ExceptionPt(const RiseFallBoth * rf,bool own_pts)945 ExceptionPt::ExceptionPt(const RiseFallBoth *rf,
946 bool own_pts) :
947 rf_(rf),
948 own_pts_(own_pts),
949 hash_(0)
950 {
951 }
952
953 // ExceptionPt initialization functions set hash_ and incrementally
954 // maintain the value.
955 size_t
hash() const956 ExceptionPt::hash() const
957 {
958 return hash_;
959 }
960
ExceptionFromTo(PinSet * pins,ClockSet * clks,InstanceSet * insts,const RiseFallBoth * rf,bool own_pts)961 ExceptionFromTo::ExceptionFromTo(PinSet *pins,
962 ClockSet *clks,
963 InstanceSet *insts,
964 const RiseFallBoth *rf,
965 bool own_pts) :
966 ExceptionPt(rf, own_pts),
967 pins_(pins),
968 clks_(clks),
969 insts_(insts)
970 {
971 // Delete empty sets.
972 if (pins_ && pins_->empty()) {
973 if (own_pts)
974 delete pins_;
975 pins_ = nullptr;
976 }
977 if (clks_ && clks_->empty()) {
978 if (own_pts)
979 delete clks_;
980 clks_ = nullptr;
981 }
982 if (insts_ && insts_->empty()) {
983 if (own_pts)
984 delete insts_;
985 insts_ = nullptr;
986 }
987 findHash();
988 }
989
~ExceptionFromTo()990 ExceptionFromTo::~ExceptionFromTo()
991 {
992 if (own_pts_) {
993 delete pins_;
994 delete clks_;
995 delete insts_;
996 }
997 }
998
999 bool
hasPins() const1000 ExceptionFromTo::hasPins() const
1001 {
1002 return pins_ != nullptr && !pins_->empty();
1003 }
1004
1005 bool
hasClocks() const1006 ExceptionFromTo::hasClocks() const
1007 {
1008 return clks_ != nullptr && !clks_->empty();
1009 }
1010
1011 bool
hasInstances() const1012 ExceptionFromTo::hasInstances() const
1013 {
1014 return insts_ != nullptr && !insts_->empty();
1015 }
1016
1017 bool
hasObjects() const1018 ExceptionFromTo::hasObjects() const
1019 {
1020 return hasPins() || hasClocks() || hasInstances();
1021 }
1022
1023 void
allPins(const Network * network,PinSet * pins)1024 ExceptionFromTo::allPins(const Network *network,
1025 PinSet *pins)
1026 {
1027 if (pins_) {
1028 PinSet::Iterator pin_iter(pins_);
1029 while (pin_iter.hasNext()) {
1030 Pin *pin = pin_iter.next();
1031 pins->insert(pin);
1032 }
1033 }
1034 if (insts_) {
1035 InstanceSet::Iterator inst_iter(insts_);
1036 while (inst_iter.hasNext()) {
1037 Instance *inst = inst_iter.next();
1038 InstancePinIterator *pin_iter = network->pinIterator(inst);
1039 while (pin_iter->hasNext()) {
1040 Pin *pin = pin_iter->next();
1041 pins->insert(pin);
1042 }
1043 delete pin_iter;
1044 }
1045 }
1046 }
1047
1048 void
findHash()1049 ExceptionFromTo::findHash()
1050 {
1051 hash_ = 0;
1052 if (pins_) {
1053 size_t hash = 0;
1054 PinSet::Iterator pin_iter(pins_);
1055 while (pin_iter.hasNext()) {
1056 const Pin *pin = pin_iter.next();
1057 hash += hashPtr(pin);
1058 }
1059 hash_ += hash * hash_pin;
1060 }
1061 if (clks_) {
1062 size_t hash = 0;
1063 ClockSet::Iterator clk_iter(clks_);
1064 while (clk_iter.hasNext()) {
1065 Clock *clk = clk_iter.next();
1066 hash += clk->index();
1067 }
1068 hash_ += hash * hash_clk;
1069 }
1070 if (insts_) {
1071 size_t hash = 0;
1072 InstanceSet::Iterator inst_iter(insts_);
1073 while (inst_iter.hasNext()) {
1074 Instance *inst = inst_iter.next();
1075 hash += hashPtr(inst);
1076 }
1077 hash_ += hash * hash_inst;
1078 }
1079 }
1080
1081 bool
equal(ExceptionFromTo * from_to) const1082 ExceptionFromTo::equal(ExceptionFromTo *from_to) const
1083 {
1084 return PinSet::equal(from_to->pins_, pins_)
1085 && ClockSet::equal(from_to->clks_, clks_)
1086 && InstanceSet::equal(from_to->insts_, insts_)
1087 && from_to->transition() == rf_;
1088 }
1089
1090 int
nameCmp(ExceptionPt * pt2,const Network * network) const1091 ExceptionFromTo::nameCmp(ExceptionPt *pt2,
1092 const Network *network) const
1093 {
1094 int priority_cmp = typePriority() - pt2->typePriority();
1095 if (priority_cmp == 0) {
1096 int pin_cmp = setNameCmp(pins_, pt2->pins(), network);
1097 if (pin_cmp == 0) {
1098 int clk_cmp = setNameCmp(clks_, pt2->clks());
1099 if (clk_cmp == 0) {
1100 int inst_cmp = setNameCmp(insts_, pt2->instances(), network);
1101 if (inst_cmp == 0)
1102 return rf_->index() - pt2->transition()->index();
1103 else
1104 return inst_cmp;
1105 }
1106 else
1107 return clk_cmp;
1108 }
1109 else
1110 return pin_cmp;
1111 }
1112 else
1113 return priority_cmp;
1114 }
1115
1116 void
mergeInto(ExceptionPt * pt)1117 ExceptionFromTo::mergeInto(ExceptionPt *pt)
1118 {
1119 if (pins_) {
1120 PinSet::Iterator pin_iter(pins_);
1121 while (pin_iter.hasNext()) {
1122 Pin *pin = pin_iter.next();
1123 pt->addPin(pin);
1124 }
1125 }
1126 if (clks_) {
1127 ClockSet::Iterator clk_iter(clks_);
1128 while (clk_iter.hasNext()) {
1129 Clock *clk = clk_iter.next();
1130 pt->addClock(clk);
1131 }
1132 }
1133 if (insts_) {
1134 InstanceSet::Iterator inst_iter(insts_);
1135 while (inst_iter.hasNext()) {
1136 Instance *inst = inst_iter.next();
1137 pt->addInstance(inst);
1138 }
1139 }
1140 }
1141
1142 void
deleteObjects(ExceptionFromTo * pt)1143 ExceptionFromTo::deleteObjects(ExceptionFromTo *pt)
1144 {
1145 PinSet *pins = pt->pins();
1146 if (pins && pins_) {
1147 PinSet::Iterator pin_iter(pins);
1148 while (pin_iter.hasNext()) {
1149 Pin *pin = pin_iter.next();
1150 deletePin(pin);
1151 }
1152 }
1153 ClockSet *clks = pt->clks();
1154 if (clks && clks_) {
1155 ClockSet::Iterator clk_iter(clks);
1156 while (clk_iter.hasNext()) {
1157 Clock *clk = clk_iter.next();
1158 deleteClock(clk);
1159 }
1160 }
1161 InstanceSet *insts = pt->instances();
1162 if (insts && insts_) {
1163 InstanceSet::Iterator inst_iter(insts);
1164 while (inst_iter.hasNext()) {
1165 Instance *inst = inst_iter.next();
1166 deleteInstance(inst);
1167 }
1168 }
1169 }
1170
1171 void
addPin(Pin * pin)1172 ExceptionFromTo::addPin(Pin *pin)
1173 {
1174 if (pins_ == nullptr)
1175 pins_ = new PinSet;
1176 if (!pins_->hasKey(pin)) {
1177 pins_->insert(pin);
1178 // Incrementally update hash.
1179 hash_ += hashPtr(pin) * hash_pin;
1180 }
1181 }
1182
1183 void
addClock(Clock * clk)1184 ExceptionFromTo::addClock(Clock *clk)
1185 {
1186 if (clks_ == nullptr)
1187 clks_ = new ClockSet;
1188 if (!clks_->hasKey(clk)) {
1189 clks_->insert(clk);
1190 // Incrementally update hash.
1191 hash_ += clk->index() * hash_clk;
1192 }
1193 }
1194
1195 void
addInstance(Instance * inst)1196 ExceptionFromTo::addInstance(Instance *inst)
1197 {
1198 if (insts_ == nullptr)
1199 insts_ = new InstanceSet;
1200 if (!insts_->hasKey(inst)) {
1201 insts_->insert(inst);
1202 // Incrementally update hash.
1203 hash_ += hashPtr(inst) * hash_inst;
1204 }
1205 }
1206
1207 void
deletePin(Pin * pin)1208 ExceptionFromTo::deletePin(Pin *pin)
1209 {
1210 if (pins_) {
1211 pins_->erase(pin);
1212 // Incrementally update hash.
1213 hash_ -= hashPtr(pin) * hash_pin;
1214 }
1215 }
1216
1217 void
deleteClock(Clock * clk)1218 ExceptionFromTo::deleteClock(Clock *clk)
1219 {
1220 if (clks_) {
1221 clks_->erase(clk);
1222 // Incrementally update hash.
1223 hash_ -= clk->index() * hash_clk;
1224 }
1225 }
1226
1227 void
deleteInstance(Instance * inst)1228 ExceptionFromTo::deleteInstance(Instance *inst)
1229 {
1230 if (insts_) {
1231 insts_->erase(inst);
1232 // Incrementally update hash.
1233 hash_ -= hashPtr(inst) * hash_inst;
1234 }
1235 }
1236
1237 const char *
asString(const Network * network) const1238 ExceptionFromTo::asString(const Network *network) const
1239 {
1240 string str;
1241 str += " ";
1242 str += cmdKeyword();
1243 str += " {";
1244
1245 int obj_count = 0;
1246 bool first = true;
1247 if (pins_) {
1248 PinSeq pins;
1249 sortPinSet(pins_, network, pins);
1250 PinSeq::Iterator pin_iter(pins);
1251 while (pin_iter.hasNext()
1252 && obj_count < as_string_max_objects_) {
1253 const Pin *pin = pin_iter.next();
1254 if (!first)
1255 str += ", ";
1256 str += network->pathName(pin);
1257 first = false;
1258 obj_count++;
1259 }
1260 }
1261 if (clks_) {
1262 ClockSeq clks;
1263 sortClockSet(clks_, clks);
1264 ClockSeq::Iterator clk_iter(clks);
1265 while (clk_iter.hasNext()
1266 && obj_count < as_string_max_objects_) {
1267 Clock *clk = clk_iter.next();
1268 if (!first)
1269 str += ", ";
1270 str += clk->name();
1271 first = false;
1272 obj_count++;
1273 }
1274 }
1275 if (insts_) {
1276 InstanceSeq insts;
1277 sortInstanceSet(insts_, network, insts);
1278 InstanceSeq::Iterator inst_iter(insts);
1279 while (inst_iter.hasNext()
1280 && obj_count < as_string_max_objects_) {
1281 if (!first)
1282 str += ", ";
1283 Instance *inst = inst_iter.next();
1284 str += network->pathName(inst);
1285 first = false;
1286 obj_count++;
1287 }
1288 }
1289 if (obj_count == as_string_max_objects_)
1290 str += ", ...";
1291
1292 str += "}";
1293
1294 char *result = makeTmpString(str.size() + 1);
1295 strcpy(result, str.c_str());
1296 return result;
1297 }
1298
1299 size_t
objectCount() const1300 ExceptionFromTo::objectCount() const
1301 {
1302 size_t count = 0;
1303 if (pins_)
1304 count += pins_->size();
1305 if (clks_)
1306 count += clks_->size();
1307 if (insts_)
1308 count += insts_->size();
1309 return count;
1310 }
1311
1312 ////////////////////////////////////////////////////////////////
1313
ExceptionFrom(PinSet * pins,ClockSet * clks,InstanceSet * insts,const RiseFallBoth * rf,bool own_pts)1314 ExceptionFrom::ExceptionFrom(PinSet *pins,
1315 ClockSet *clks,
1316 InstanceSet *insts,
1317 const RiseFallBoth *rf,
1318 bool own_pts) :
1319 ExceptionFromTo(pins, clks, insts, rf, own_pts)
1320 {
1321 }
1322
1323 void
findHash()1324 ExceptionFrom::findHash()
1325 {
1326 ExceptionFromTo::findHash();
1327 hash_ += rf_->index() * 31 + 29;
1328 }
1329
1330 ExceptionFrom *
clone()1331 ExceptionFrom::clone()
1332 {
1333 PinSet *pins = nullptr;
1334 if (pins_)
1335 pins = new PinSet(*pins_);
1336 ClockSet *clks = nullptr;
1337 if (clks_)
1338 clks = new ClockSet(*clks_);
1339 InstanceSet *insts = nullptr;
1340 if (insts_)
1341 insts = new InstanceSet(*insts_);
1342 return new ExceptionFrom(pins, clks, insts, rf_, true);
1343 }
1344
1345 bool
intersectsPts(ExceptionFrom * from) const1346 ExceptionFrom::intersectsPts(ExceptionFrom *from) const
1347 {
1348 return from->transition() == rf_
1349 && ((pins_ && PinSet::intersects(pins_, from->pins()))
1350 || (clks_ && ClockSet::intersects(clks_, from->clks()))
1351 || (insts_ && InstanceSet::intersects(insts_, from->instances())));
1352 }
1353
1354 const char *
cmdKeyword() const1355 ExceptionFrom::cmdKeyword() const
1356 {
1357 if (rf_ == RiseFallBoth::rise())
1358 return "-rise_from";
1359 else if (rf_ == RiseFallBoth::fall())
1360 return "-fall_from";
1361 else
1362 return "-from";
1363 }
1364
1365 ////////////////////////////////////////////////////////////////
1366
ExceptionTo(PinSet * pins,ClockSet * clks,InstanceSet * insts,const RiseFallBoth * rf,const RiseFallBoth * end_rf,bool own_pts)1367 ExceptionTo::ExceptionTo(PinSet *pins,
1368 ClockSet *clks,
1369 InstanceSet *insts,
1370 const RiseFallBoth *rf,
1371 const RiseFallBoth *end_rf,
1372 bool own_pts) :
1373 ExceptionFromTo(pins, clks, insts, rf, own_pts),
1374 end_rf_(end_rf)
1375 {
1376 }
1377
1378 ExceptionTo *
clone()1379 ExceptionTo::clone()
1380 {
1381 PinSet *pins = nullptr;
1382 if (pins_)
1383 pins = new PinSet(*pins_);
1384 ClockSet *clks = nullptr;
1385 if (clks_)
1386 clks = new ClockSet(*clks_);
1387 InstanceSet *insts = nullptr;
1388 if (insts_)
1389 insts = new InstanceSet(*insts_);
1390 return new ExceptionTo(pins, clks, insts, rf_, end_rf_, true);
1391 }
1392
1393 const char *
asString(const Network * network) const1394 ExceptionTo::asString(const Network *network) const
1395 {
1396 string str;
1397 if (hasObjects())
1398 str += ExceptionFromTo::asString(network);
1399
1400 if (end_rf_ != RiseFallBoth::riseFall())
1401 str += (end_rf_ == RiseFallBoth::rise()) ? " -rise" : " -fall";
1402
1403 char *result = makeTmpString(str.size() + 1);
1404 strcpy(result, str.c_str());
1405 return result;
1406 }
1407
1408 bool
intersectsPts(ExceptionTo * to) const1409 ExceptionTo::intersectsPts(ExceptionTo *to) const
1410 {
1411 return to->transition() == rf_
1412 && to->endTransition() == end_rf_
1413 && ((pins_ && PinSet::intersects(pins_, to->pins()))
1414 || (clks_ && ClockSet::intersects(clks_, to->clks()))
1415 || (insts_ && InstanceSet::intersects(insts_, to->instances())));
1416 }
1417
1418 bool
matchesFilter(const Pin * pin,const ClockEdge * clk_edge,const RiseFall * end_rf,const Network * network) const1419 ExceptionTo::matchesFilter(const Pin *pin,
1420 const ClockEdge *clk_edge,
1421 const RiseFall *end_rf,
1422 const Network *network) const
1423 {
1424 // "report -to reg" does match clock pins.
1425 return matches(pin, clk_edge, end_rf, true, network);
1426 }
1427
1428 bool
matches(const Pin * pin,const ClockEdge * clk_edge,const RiseFall * end_rf,const Network * network) const1429 ExceptionTo::matches(const Pin *pin,
1430 const ClockEdge *clk_edge,
1431 const RiseFall *end_rf,
1432 const Network *network) const
1433 {
1434 // "exception -to reg" does not match reg clock pins.
1435 return matches(pin, clk_edge, end_rf, false, network);
1436 }
1437
1438 bool
matches(const Pin * pin,const ClockEdge * clk_edge,const RiseFall * end_rf,bool inst_matches_reg_clk_pin,const Network * network) const1439 ExceptionTo::matches(const Pin *pin,
1440 const ClockEdge *clk_edge,
1441 const RiseFall *end_rf,
1442 bool inst_matches_reg_clk_pin,
1443 const Network *network) const
1444
1445 {
1446 return (pins_
1447 && pins_->hasKey(const_cast<Pin*>(pin))
1448 && rf_->matches(end_rf)
1449 && end_rf_->matches(end_rf))
1450 || (clk_edge
1451 && clks_
1452 && clks_->hasKey(const_cast<Clock*>(clk_edge->clock()))
1453 && rf_->matches(clk_edge->transition())
1454 && end_rf_->matches(end_rf))
1455 || (insts_
1456 && (inst_matches_reg_clk_pin
1457 || !network->isRegClkPin(pin))
1458 && insts_->hasKey(network->instance(pin))
1459 && network->direction(pin)->isAnyInput()
1460 && rf_->matches(end_rf)
1461 && end_rf_->matches(end_rf))
1462 || (pins_ == nullptr
1463 && clks_ == nullptr
1464 && insts_ == nullptr
1465 && end_rf_->matches(end_rf));
1466 }
1467
1468 bool
matches(const Pin * pin,const RiseFall * end_rf) const1469 ExceptionTo::matches(const Pin *pin,
1470 const RiseFall *end_rf) const
1471 {
1472 return (pins_
1473 && pins_->hasKey(const_cast<Pin*>(pin))
1474 && rf_->matches(end_rf)
1475 && end_rf_->matches(end_rf))
1476 || (pins_ == nullptr
1477 && clks_ == nullptr
1478 && insts_ == nullptr
1479 && end_rf_->matches(end_rf));
1480 }
1481
1482 bool
matches(const Clock * clk) const1483 ExceptionTo::matches(const Clock *clk) const
1484 {
1485 return clks_
1486 && clks_->hasKey(const_cast<Clock*>(clk));
1487 }
1488
1489 const char *
cmdKeyword() const1490 ExceptionTo::cmdKeyword() const
1491 {
1492 if (rf_ == RiseFallBoth::rise())
1493 return "-rise_to";
1494 else if (rf_ == RiseFallBoth::fall())
1495 return "-fall_to";
1496 else
1497 return "-to";
1498 }
1499
1500 int
nameCmp(ExceptionPt * pt2,const Network * network) const1501 ExceptionTo::nameCmp(ExceptionPt *pt2,
1502 const Network *network) const
1503 {
1504 ExceptionTo *to2 = dynamic_cast<ExceptionTo*>(pt2);
1505 int cmp = ExceptionFromTo::nameCmp(pt2, network);
1506 if (cmp == 0)
1507 return end_rf_->index() - to2->endTransition()->index();
1508 else
1509 return cmp;
1510 }
1511
1512 ////////////////////////////////////////////////////////////////
1513
ExceptionThru(PinSet * pins,NetSet * nets,InstanceSet * insts,const RiseFallBoth * rf,bool own_pts,const Network * network)1514 ExceptionThru::ExceptionThru(PinSet *pins,
1515 NetSet *nets,
1516 InstanceSet *insts,
1517 const RiseFallBoth *rf,
1518 bool own_pts,
1519 const Network *network) :
1520 ExceptionPt(rf, own_pts),
1521 pins_(pins),
1522 edges_(nullptr),
1523 nets_(nets),
1524 insts_(insts)
1525 {
1526 // Delete empty sets.
1527 if (pins_ && pins_->empty()) {
1528 if (own_pts)
1529 delete pins_;
1530 pins_ = nullptr;
1531 }
1532 if (nets_ && nets_->empty()) {
1533 if (own_pts)
1534 delete nets_;
1535 nets_ = nullptr;
1536 }
1537 if (insts_ && insts_->empty()) {
1538 if (own_pts)
1539 delete insts_;
1540 insts_ = nullptr;
1541 }
1542 makeAllEdges(network);
1543 findHash();
1544 }
1545
1546 void
makeAllEdges(const Network * network)1547 ExceptionThru::makeAllEdges(const Network *network)
1548 {
1549 if (pins_)
1550 makePinEdges(network);
1551 if (nets_)
1552 makeNetEdges(network);
1553 if (insts_)
1554 makeInstEdges(network);
1555 }
1556
1557 void
makePinEdges(const Network * network)1558 ExceptionThru::makePinEdges(const Network *network)
1559 {
1560 PinSet::Iterator pin_iter(pins_);
1561 while (pin_iter.hasNext()) {
1562 Pin *pin = pin_iter.next();
1563 if (network->isHierarchical(pin))
1564 makeHpinEdges(pin, network);
1565 }
1566 }
1567
1568 // Call after the pin has been deleted from pins_,
1569 // but before the pin has been deleted from the netlist.
1570 void
deletePinEdges(Pin * pin,Network * network)1571 ExceptionThru::deletePinEdges(Pin *pin,
1572 Network *network)
1573 {
1574 // Incrementally delete only edges through (hier) or from/to (leaf) the pin.
1575 if (edges_ && network->net(pin)) {
1576 if (network->isHierarchical(pin)) {
1577 // Use driver lookup to minimize potentially expensive calls to
1578 // deletePinPairsThruHierPin.
1579 PinSet *drvrs = network->drivers(pin);
1580 if (drvrs) {
1581 // Some edges originating at drvrs may not actually go through pin, so
1582 // still must use deletePinPairsThruHierPin to identify specific edges.
1583 EdgePinsSet::Iterator edge_iter(edges_);
1584 while (edge_iter.hasNext()) {
1585 EdgePins *edge_pins = edge_iter.next();
1586 Pin *p_first = edge_pins->first;
1587 if (drvrs->hasKey(p_first)) {
1588 deletePinPairsThruHierPin(pin, network, edges_);
1589 break;
1590 }
1591 }
1592 }
1593 }
1594 else {
1595 EdgePinsSet::Iterator edge_iter(edges_);
1596 while (edge_iter.hasNext()) {
1597 EdgePins *edge_pins = edge_iter.next();
1598 if (edge_pins->first == pin
1599 || edge_pins->second == pin) {
1600 edges_->erase(edge_pins);
1601 delete edge_pins;
1602 }
1603 }
1604 }
1605 }
1606 }
1607
1608 void
makeHpinEdges(const Pin * pin,const Network * network)1609 ExceptionThru::makeHpinEdges(const Pin *pin,
1610 const Network *network)
1611 {
1612 if (edges_ == nullptr)
1613 edges_ = new EdgePinsSet;
1614 // Add edges thru pin to edges_.
1615 insertPinPairsThruHierPin(pin, network, edges_);
1616 }
1617
1618 void
makeNetEdges(const Network * network)1619 ExceptionThru::makeNetEdges(const Network *network)
1620 {
1621 NetSet::Iterator net_iter(nets_);
1622 while (net_iter.hasNext()) {
1623 Net *net = net_iter.next();
1624 if (edges_ == nullptr)
1625 edges_ = new EdgePinsSet;
1626 // Add edges thru pin to edges_.
1627 insertPinPairsThruNet(net, network, edges_);
1628 }
1629 }
1630
1631 void
makeNetEdges(Net * net,const Network * network)1632 ExceptionThru::makeNetEdges(Net *net,
1633 const Network *network)
1634 {
1635 if (edges_ == nullptr)
1636 edges_ = new EdgePinsSet;
1637 // Add edges thru pin to edges_.
1638 insertPinPairsThruNet(net, network, edges_);
1639 }
1640
1641 void
makeInstEdges(const Network * network)1642 ExceptionThru::makeInstEdges(const Network *network)
1643 {
1644 InstanceSet::Iterator inst_iter(insts_);
1645 while (inst_iter.hasNext()) {
1646 Instance *inst = inst_iter.next();
1647 if (network->isHierarchical(inst)) {
1648 InstancePinIterator *pin_iter = network->pinIterator(inst);
1649 while (pin_iter->hasNext()) {
1650 Pin *pin = pin_iter->next();
1651 makeHpinEdges(pin, network);
1652 }
1653 delete pin_iter;
1654 }
1655 }
1656 }
1657
1658 void
makeInstEdges(Instance * inst,Network * network)1659 ExceptionThru::makeInstEdges(Instance *inst,
1660 Network *network)
1661 {
1662 if (network->isHierarchical(inst)) {
1663 InstancePinIterator *pin_iter = network->pinIterator(inst);
1664 while (pin_iter->hasNext()) {
1665 Pin *pin = pin_iter->next();
1666 makeHpinEdges(pin, network);
1667 }
1668 delete pin_iter;
1669 }
1670 }
1671
1672 // Call after the inst has been deleted from insts_,
1673 // but before the inst has been deleted from the netlist.
1674 void
deleteInstEdges(Instance * inst,Network * network)1675 ExceptionThru::deleteInstEdges(Instance *inst,
1676 Network *network)
1677 {
1678 // Incrementally delete edges through each hier pin.
1679 if (edges_) {
1680 InstancePinIterator *pin_iter = network->pinIterator(inst);
1681 while (pin_iter->hasNext()) {
1682 Pin *pin = pin_iter->next();
1683 deletePinEdges(pin, network);
1684 }
1685 delete pin_iter;
1686 }
1687 }
1688
~ExceptionThru()1689 ExceptionThru::~ExceptionThru()
1690 {
1691 if (own_pts_) {
1692 delete pins_;
1693 delete nets_;
1694 delete insts_;
1695 if (edges_) {
1696 edges_->deleteContents();
1697 delete edges_;
1698 }
1699 }
1700 }
1701
1702 const char *
asString(const Network * network) const1703 ExceptionThru::asString(const Network *network) const
1704 {
1705 string str;
1706 bool first = true;
1707 int obj_count = 0;
1708 if (pins_) {
1709 PinSeq pins;
1710 sortPinSet(pins_, network, pins);
1711 PinSeq::Iterator pin_iter(pins);
1712 while (pin_iter.hasNext()
1713 && obj_count < as_string_max_objects_) {
1714 const Pin *pin = pin_iter.next();
1715 if (!first)
1716 str += ", ";
1717 str += network->pathName(pin);
1718 first = false;
1719 obj_count++;
1720 }
1721 }
1722 if (nets_) {
1723 NetSeq nets;
1724 sortNetSet(nets_, network, nets);
1725 NetSeq::Iterator net_iter(nets);
1726 while (net_iter.hasNext()
1727 && obj_count < as_string_max_objects_) {
1728 const Net *net = net_iter.next();
1729 if (!first)
1730 str += ", ";
1731 str += network->pathName(net);
1732 first = false;
1733 obj_count++;
1734 }
1735 }
1736 if (insts_) {
1737 InstanceSeq insts;
1738 sortInstanceSet(insts_, network, insts);
1739 InstanceSeq::Iterator inst_iter(insts);
1740 while (inst_iter.hasNext()
1741 && obj_count < as_string_max_objects_) {
1742 if (!first)
1743 str += ", ";
1744 Instance *inst = inst_iter.next();
1745 str += network->pathName(inst);
1746 first = false;
1747 obj_count++;
1748 }
1749 }
1750 if (obj_count == as_string_max_objects_)
1751 str += ", ...";
1752 if (rf_ == RiseFallBoth::rise())
1753 str += " rise";
1754 else if (rf_ == RiseFallBoth::fall())
1755 str += " fall";
1756
1757 char *result = makeTmpString(str.size() + 1);
1758 strcpy(result, str.c_str());
1759 return result;
1760 }
1761
1762 ExceptionThruSeq *
exceptionThrusClone(ExceptionThruSeq * thrus,const Network * network)1763 exceptionThrusClone(ExceptionThruSeq *thrus,
1764 const Network *network)
1765 {
1766 if (thrus) {
1767 ExceptionThruSeq *thrus_cpy = new ExceptionThruSeq;
1768 ExceptionThruSeq::Iterator thru_iter(thrus);
1769 while (thru_iter.hasNext()) {
1770 ExceptionThru *thru = thru_iter.next();
1771 ExceptionThru *thru_cpy = thru->clone(network);
1772 thrus_cpy->push_back(thru_cpy);
1773 }
1774 return thrus_cpy;
1775 }
1776 else
1777 return nullptr;
1778 }
1779
1780 ExceptionThru *
clone(const Network * network)1781 ExceptionThru::clone(const Network *network)
1782 {
1783 PinSet *pins = nullptr;
1784 if (pins_)
1785 pins = new PinSet(*pins_);
1786 NetSet *nets = nullptr;
1787 if (nets_)
1788 nets = new NetSet(*nets_);
1789 InstanceSet *insts = nullptr;
1790 if (insts_)
1791 insts = new InstanceSet(*insts_);
1792 return new ExceptionThru(pins, nets, insts, rf_, true, network);
1793 }
1794
1795 bool
hasObjects() const1796 ExceptionThru::hasObjects() const
1797 {
1798 return (pins_ != nullptr && !pins_->empty())
1799 || (nets_ != nullptr && !nets_->empty())
1800 || (insts_ != nullptr && !insts_->empty());
1801 }
1802
1803
1804 void
addPin(Pin * pin)1805 ExceptionThru::addPin(Pin *pin)
1806 {
1807 if (pins_ == nullptr)
1808 pins_ = new PinSet;
1809 if (!pins_->hasKey(pin)) {
1810 pins_->insert(pin);
1811 // Incrementally update hash.
1812 hash_ += hashPtr(pin) * hash_pin;
1813 }
1814 }
1815
1816 void
addNet(Net * net)1817 ExceptionThru::addNet(Net *net)
1818 {
1819 if (nets_ == nullptr)
1820 nets_ = new NetSet;
1821 if (!nets_->hasKey(net)) {
1822 nets_->insert(net);
1823 // Incrementally update hash.
1824 hash_ += hashPtr(net) * hash_net;
1825 }
1826 }
1827
1828 void
addInstance(Instance * inst)1829 ExceptionThru::addInstance(Instance *inst)
1830 {
1831 if (insts_ == nullptr)
1832 insts_ = new InstanceSet;
1833 if (!insts_->hasKey(inst)) {
1834 insts_->insert(inst);
1835 // Incrementally update hash.
1836 hash_ += hashPtr(inst) * hash_inst;
1837 }
1838 }
1839
1840 void
addEdge(EdgePins * edge)1841 ExceptionThru::addEdge(EdgePins *edge)
1842 {
1843 if (edges_ == nullptr)
1844 edges_ = new EdgePinsSet;
1845 edges_->insert(edge);
1846 // Hash is unchanged because edges are derived from hierarchical pins.
1847 }
1848
1849 void
deletePin(Pin * pin)1850 ExceptionThru::deletePin(Pin *pin)
1851 {
1852 if (pins_) {
1853 pins_->erase(pin);
1854 // Incrementally update hash.
1855 hash_ -= hashPtr(pin) * hash_pin;
1856 }
1857 }
1858
1859 void
deleteNet(Net * net)1860 ExceptionThru::deleteNet(Net *net)
1861 {
1862 if (nets_) {
1863 nets_->erase(net);
1864 // Incrementally update hash.
1865 hash_ -= hashPtr(net) * hash_net;
1866 }
1867 }
1868
1869 void
deleteInstance(Instance * inst)1870 ExceptionThru::deleteInstance(Instance *inst)
1871 {
1872 if (insts_) {
1873 insts_->erase(inst);
1874 // Incrementally update hash.
1875 hash_ -= hashPtr(inst) * hash_inst;
1876 }
1877 }
1878
1879 void
deleteEdge(EdgePins * edge)1880 ExceptionThru::deleteEdge(EdgePins *edge)
1881 {
1882 if (edges_) {
1883 edges_->erase(edge);
1884 // Hash is unchanged because edges are derived from hierarchical pins.
1885 }
1886 }
1887
1888 void
allPins(const Network * network,PinSet * pins)1889 ExceptionThru::allPins(const Network *network,
1890 PinSet *pins)
1891 {
1892 if (pins_) {
1893 PinSet::Iterator pin_iter(pins_);
1894 while (pin_iter.hasNext()) {
1895 Pin *pin = pin_iter.next();
1896 pins->insert(pin);
1897 }
1898 }
1899 if (insts_) {
1900 InstanceSet::Iterator inst_iter(insts_);
1901 while (inst_iter.hasNext()) {
1902 Instance *inst = inst_iter.next();
1903 InstancePinIterator *pin_iter = network->pinIterator(inst);
1904 while (pin_iter->hasNext()) {
1905 Pin *pin = pin_iter->next();
1906 pins->insert(pin);
1907 }
1908 delete pin_iter;
1909 }
1910 }
1911 if (nets_) {
1912 NetSet::Iterator net_iter(nets_);
1913 while (net_iter.hasNext()) {
1914 Net *net = net_iter.next();
1915 NetConnectedPinIterator *pin_iter = network->connectedPinIterator(net);
1916 while (pin_iter->hasNext()) {
1917 Pin *pin = pin_iter->next();
1918 pins->insert(pin);
1919 }
1920 delete pin_iter;
1921 }
1922 }
1923 }
1924
1925 bool
matches(const Pin * from_pin,const Pin * to_pin,const RiseFall * to_rf,const Network * network)1926 ExceptionThru::matches(const Pin *from_pin,
1927 const Pin *to_pin,
1928 const RiseFall *to_rf,
1929 const Network *network)
1930 {
1931 EdgePins edge_pins(const_cast<Pin*>(from_pin), const_cast<Pin*>(to_pin));
1932 return ((pins_ && pins_->hasKey(const_cast<Pin*>(to_pin)))
1933 || (edges_ && edges_->hasKey(&edge_pins))
1934 || (nets_ && to_pin && nets_->hasKey(network->net(to_pin)))
1935 || (insts_ && to_pin && insts_->hasKey(network->instance(to_pin))))
1936 && rf_->matches(to_rf);
1937 }
1938
1939 void
findHash()1940 ExceptionThru::findHash()
1941 {
1942 hash_ = 0;
1943 if (pins_) {
1944 size_t hash = 0;
1945 PinSet::Iterator pin_iter(pins_);
1946 while (pin_iter.hasNext()) {
1947 const Pin *pin = pin_iter.next();
1948 hash += hashPtr(pin);
1949 }
1950 hash_ += hash * hash_pin;
1951 }
1952 if (nets_) {
1953 size_t hash = 0;
1954 NetSet::Iterator net_iter(nets_);
1955 while (net_iter.hasNext()) {
1956 Net *net = net_iter.next();
1957 hash += hashPtr(net);
1958 }
1959 hash_ += hash * hash_net;
1960 }
1961 if (insts_) {
1962 size_t hash = 0;
1963 InstanceSet::Iterator inst_iter(insts_);
1964 while (inst_iter.hasNext()) {
1965 Instance *inst = inst_iter.next();
1966 hash += hashPtr(inst);
1967 }
1968 hash_ += hash * hash_inst;
1969 }
1970 hash_ += rf_->index() * 13;
1971 }
1972
1973 bool
equal(ExceptionThru * thru) const1974 ExceptionThru::equal(ExceptionThru *thru) const
1975 {
1976 // Edges_ are derived from pins_ so matching pins is sufficient.
1977 return PinSet::equal(thru->pins_, pins_)
1978 && NetSet::equal(thru->nets_, nets_)
1979 && InstanceSet::equal(thru->insts_, insts_)
1980 && rf_ == thru->rf_;
1981 }
1982
1983 int
nameCmp(ExceptionPt * pt2,const Network * network) const1984 ExceptionThru::nameCmp(ExceptionPt *pt2,
1985 const Network *network) const
1986 {
1987 int priority_cmp = typePriority() - pt2->typePriority();
1988 if (priority_cmp == 0) {
1989 int pin_cmp = setNameCmp(pins_, pt2->pins(), network);
1990 if (pin_cmp == 0) {
1991 int net_cmp = setNameCmp(nets_, pt2->nets(), network);
1992 if (net_cmp == 0) {
1993 int inst_cmp = setNameCmp(insts_, pt2->instances(), network);
1994 if (inst_cmp == 0)
1995 return rf_->index() - pt2->transition()->index();
1996 else
1997 return inst_cmp;
1998 }
1999 else
2000 return net_cmp;
2001 }
2002 else
2003 return pin_cmp;
2004 }
2005 else
2006 return priority_cmp;
2007 }
2008
2009 void
mergeInto(ExceptionPt * pt)2010 ExceptionThru::mergeInto(ExceptionPt *pt)
2011 {
2012 if (pins_) {
2013 PinSet::Iterator pin_iter(pins_);
2014 while (pin_iter.hasNext()) {
2015 Pin *pin = pin_iter.next();
2016 pt->addPin(pin);
2017 }
2018 }
2019 if (edges_) {
2020 EdgePinsSet::Iterator edge_iter(edges_);
2021 while (edge_iter.hasNext()) {
2022 EdgePins *edge = edge_iter.next();
2023 pt->addEdge(edge);
2024 }
2025 // EdgePins are now owned by acquirer.
2026 edges_->clear();
2027 }
2028 if (nets_) {
2029 NetSet::Iterator net_iter(nets_);
2030 while (net_iter.hasNext()) {
2031 Net *net = net_iter.next();
2032 pt->addNet(net);
2033 }
2034 }
2035 if (insts_) {
2036 InstanceSet::Iterator inst_iter(insts_);
2037 while (inst_iter.hasNext()) {
2038 Instance *inst = inst_iter.next();
2039 pt->addInstance(inst);
2040 }
2041 }
2042 }
2043
2044 void
deleteObjects(ExceptionThru * pt)2045 ExceptionThru::deleteObjects(ExceptionThru *pt)
2046 {
2047 PinSet *pins = pt->pins();
2048 if (pins && pins_) {
2049 PinSet::Iterator pin_iter(pins);
2050 while (pin_iter.hasNext()) {
2051 Pin *pin = pin_iter.next();
2052 deletePin(pin);
2053 }
2054 }
2055 EdgePinsSet *edges = pt->edges();
2056 if (edges && edges_) {
2057 EdgePinsSet::Iterator edge_iter(edges);
2058 while (edge_iter.hasNext()) {
2059 EdgePins *edge = edge_iter.next();
2060 deleteEdge(edge);
2061 }
2062 }
2063 NetSet *nets = pt->nets();
2064 if (nets && nets_) {
2065 NetSet::Iterator net_iter(nets);
2066 while (net_iter.hasNext()) {
2067 Net *net = net_iter.next();
2068 deleteNet(net);
2069 }
2070 }
2071 InstanceSet *insts = pt->instances();
2072 if (insts && insts_) {
2073 InstanceSet::Iterator inst_iter(insts);
2074 while (inst_iter.hasNext()) {
2075 Instance *inst = inst_iter.next();
2076 deleteInstance(inst);
2077 }
2078 }
2079 }
2080
2081 bool
intersectsPts(ExceptionThru * thru) const2082 ExceptionThru::intersectsPts(ExceptionThru *thru) const
2083 {
2084 return thru->transition() == rf_
2085 && ((pins_ && PinSet::intersects(pins_, thru->pins()))
2086 || (nets_ && NetSet::intersects(nets_, thru->nets()))
2087 || (insts_ && InstanceSet::intersects(insts_, thru->instances())));
2088 }
2089
2090 size_t
objectCount() const2091 ExceptionThru::objectCount() const
2092 {
2093 size_t count = 0;
2094 if (pins_)
2095 count += pins_->size();
2096 if (nets_)
2097 count += nets_->size();
2098 if (insts_)
2099 count += insts_->size();
2100 return count;
2101 }
2102
2103 void
connectPinAfter(PinSet * drvrs,Network * network)2104 ExceptionThru::connectPinAfter(PinSet *drvrs,
2105 Network *network)
2106 {
2107 // - Tricky to detect exactly what needs to be updated. In theory,
2108 // at most, only edges starting/ending (pin is leaf) or spanning
2109 // (pin is hier) the pin may need to be added. Trick is avoiding
2110 // adding edges through the newly connected pin that don't belong.
2111 // - some examples:
2112 // a. leaf driver connected, with downstream hnet in nets_, only
2113 // the edges from pin through hier_net should be added.
2114 // b. hpin connected, but only some other hpin/hnet along the overall
2115 // net resides in pins_/nets_, only add edges through those other
2116 // hpin/hnets.
2117 // c. hier inst resides in insts_, it gets a new pin added/connected, so
2118 // should add new edges through that pin.
2119
2120 // Use driver lookups to minimize potentially expensive calls that
2121 // traverse hier pins.
2122
2123 // No enabled edges if no driver.
2124 if (drvrs && !drvrs->empty()) {
2125 PinSet::Iterator pin_iter(pins_);
2126 while (pin_iter.hasNext()) {
2127 Pin *thru_pin = pin_iter.next();
2128 if (network->isHierarchical(thru_pin)) {
2129 PinSet *thru_pin_drvrs = network->drivers(thru_pin);
2130 if (PinSet::intersects(drvrs, thru_pin_drvrs))
2131 makePinEdges(thru_pin, network);
2132 }
2133 }
2134 InstanceSet::Iterator inst_iter(insts_);
2135 while (inst_iter.hasNext()) {
2136 Instance *inst = inst_iter.next();
2137 if (network->isHierarchical(inst)) {
2138 InstancePinIterator *inst_pin_iter = network->pinIterator(inst);
2139 while (inst_pin_iter->hasNext()) {
2140 Pin *inst_pin = inst_pin_iter->next();
2141 PinSet *inst_pin_drvrs = network->drivers(inst_pin);
2142 if (PinSet::intersects(drvrs, inst_pin_drvrs))
2143 makePinEdges(inst_pin, network);
2144 }
2145 delete inst_pin_iter;
2146 }
2147 }
2148 NetSet::Iterator net_iter(nets_);
2149 while (net_iter.hasNext()) {
2150 Net *net = net_iter.next();
2151 PinSet *net_drvrs = network->drivers(net);
2152 if (PinSet::intersects(drvrs, net_drvrs))
2153 makeNetEdges(net, network);
2154 }
2155 }
2156 }
2157
2158 void
makePinEdges(Pin * pin,const Network * network)2159 ExceptionThru::makePinEdges(Pin *pin,
2160 const Network *network)
2161 {
2162 if (network->isHierarchical(pin))
2163 makeHpinEdges(pin, network);
2164 }
2165
2166 void
disconnectPinBefore(Pin * pin,Network * network)2167 ExceptionThru::disconnectPinBefore(Pin *pin,
2168 Network *network)
2169 {
2170 // Remove edges from/to leaf pin and through hier pin.
2171 deletePinEdges(pin, network);
2172 }
2173
2174 ////////////////////////////////////////////////////////////////
2175
ExceptionPtIterator(const ExceptionPath * exception)2176 ExceptionPtIterator::ExceptionPtIterator(const ExceptionPath *exception) :
2177 exception_(exception),
2178 from_done_(false),
2179 to_done_(false)
2180 {
2181 if (exception->thrus())
2182 thru_iter_.init(exception->thrus());
2183 }
2184
2185 bool
hasNext()2186 ExceptionPtIterator::hasNext()
2187 {
2188 return (!from_done_ && exception_->from())
2189 || thru_iter_.hasNext()
2190 || (!to_done_ && exception_->to());
2191 }
2192
2193
2194 ExceptionPt *
next()2195 ExceptionPtIterator::next()
2196 {
2197 if (!from_done_ && exception_->from()) {
2198 from_done_ = true;
2199 return exception_->from();
2200 }
2201 else if (thru_iter_.hasNext())
2202 return thru_iter_.next();
2203 else {
2204 to_done_ = true;
2205 return exception_->to();
2206 }
2207 }
2208
2209 ////////////////////////////////////////////////////////////////
2210
ExpandedExceptionVisitor(ExceptionPath * exception,const Network * network)2211 ExpandedExceptionVisitor::ExpandedExceptionVisitor(ExceptionPath *exception,
2212 const Network *network) :
2213 exception_(exception),
2214 network_(network)
2215 {
2216 }
2217
2218 void
visitExpansions()2219 ExpandedExceptionVisitor::visitExpansions()
2220 {
2221 ExceptionFrom *from = exception_->from();
2222 if (from) {
2223 const RiseFallBoth *rf = from->transition();
2224 PinSet::Iterator pin_iter(from->pins());
2225 while (pin_iter.hasNext()) {
2226 Pin *pin = pin_iter.next();
2227 PinSet pins;
2228 pins.insert(pin);
2229 ExceptionFrom expanded_from(&pins, nullptr, nullptr, rf, false);
2230 expandThrus(&expanded_from);
2231 }
2232 ClockSet::Iterator clk_iter(from->clks());
2233 while (clk_iter.hasNext()) {
2234 Clock *clk = clk_iter.next();
2235 ClockSet clks;
2236 clks.insert(clk);
2237 ExceptionFrom expanded_from(nullptr, &clks, nullptr, rf, false);
2238 expandThrus(&expanded_from);
2239 }
2240 InstanceSet::Iterator inst_iter(from->instances());
2241 while (inst_iter.hasNext()) {
2242 Instance *inst = inst_iter.next();
2243 InstanceSet insts;
2244 insts.insert(inst);
2245 ExceptionFrom expanded_from(nullptr, nullptr, &insts, rf, false);
2246 expandThrus(&expanded_from);
2247 }
2248 }
2249 else
2250 expandThrus(0);
2251 }
2252
2253 void
expandThrus(ExceptionFrom * expanded_from)2254 ExpandedExceptionVisitor::expandThrus(ExceptionFrom *expanded_from)
2255 {
2256 ExceptionThruSeq *thrus = exception_->thrus();
2257 if (thrus) {
2258 // Use tail recursion to expand the exception points in the thrus.
2259 ExceptionThruSeq::Iterator thru_iter(thrus);
2260 ExceptionThruSeq expanded_thrus;
2261 expandThru(expanded_from, thru_iter, &expanded_thrus);
2262 }
2263 else
2264 expandTo(expanded_from, nullptr);
2265 }
2266
2267 void
expandThru(ExceptionFrom * expanded_from,ExceptionThruSeq::Iterator & thru_iter,ExceptionThruSeq * expanded_thrus)2268 ExpandedExceptionVisitor::expandThru(ExceptionFrom *expanded_from,
2269 ExceptionThruSeq::Iterator &thru_iter,
2270 ExceptionThruSeq *expanded_thrus)
2271 {
2272 if (thru_iter.hasNext()) {
2273 ExceptionThru *thru = thru_iter.next();
2274 const RiseFallBoth *rf = thru->transition();
2275 PinSet::Iterator pin_iter(thru->pins());
2276 while (pin_iter.hasNext()) {
2277 Pin *pin = pin_iter.next();
2278 PinSet pins;
2279 pins.insert(pin);
2280 ExceptionThru expanded_thru(&pins, nullptr, nullptr, rf, false, network_);
2281 expanded_thrus->push_back(&expanded_thru);
2282 expandThru(expanded_from, thru_iter, expanded_thrus);
2283 expanded_thrus->pop_back();
2284 }
2285 NetSet::Iterator net_iter(thru->nets());
2286 while (net_iter.hasNext()) {
2287 Net *net = net_iter.next();
2288 NetSet nets;
2289 nets.insert(net);
2290 ExceptionThru expanded_thru(nullptr, &nets, nullptr, rf, false, network_);
2291 expanded_thrus->push_back(&expanded_thru);
2292 expandThru(expanded_from, thru_iter, expanded_thrus);
2293 expanded_thrus->pop_back();
2294 }
2295 InstanceSet::Iterator inst_iter(thru->instances());
2296 while (inst_iter.hasNext()) {
2297 Instance *inst = inst_iter.next();
2298 InstanceSet insts;
2299 insts.insert(inst);
2300 ExceptionThru expanded_thru(nullptr, nullptr, &insts, rf, false, network_);
2301 expanded_thrus->push_back(&expanded_thru);
2302 expandThru(expanded_from, thru_iter, expanded_thrus);
2303 expanded_thrus->pop_back();
2304 }
2305 }
2306 else
2307 // End of thrus tail recursion.
2308 expandTo(expanded_from, expanded_thrus);
2309 }
2310
2311 void
expandTo(ExceptionFrom * expanded_from,ExceptionThruSeq * expanded_thrus)2312 ExpandedExceptionVisitor::expandTo(ExceptionFrom *expanded_from,
2313 ExceptionThruSeq *expanded_thrus)
2314 {
2315 ExceptionTo *to = exception_->to();
2316 if (to) {
2317 const RiseFallBoth *rf = to->transition();
2318 const RiseFallBoth *end_rf = to->endTransition();
2319 PinSet::Iterator pin_iter(to->pins());
2320 while (pin_iter.hasNext()) {
2321 Pin *pin = pin_iter.next();
2322 PinSet pins;
2323 pins.insert(pin);
2324 ExceptionTo expanded_to(&pins, nullptr, nullptr, rf, end_rf, false);
2325 visit(expanded_from, expanded_thrus, &expanded_to);
2326 }
2327 ClockSet::Iterator clk_iter(to->clks());
2328 while (clk_iter.hasNext()) {
2329 Clock *clk = clk_iter.next();
2330 ClockSet clks;
2331 clks.insert(clk);
2332 ExceptionTo expanded_to(nullptr, &clks, nullptr, rf, end_rf, false);
2333 visit(expanded_from, expanded_thrus, &expanded_to);
2334 }
2335 InstanceSet::Iterator inst_iter(to->instances());
2336 while (inst_iter.hasNext()) {
2337 Instance *inst = inst_iter.next();
2338 InstanceSet insts;
2339 insts.insert(inst);
2340 ExceptionTo expanded_to(nullptr, nullptr, &insts, rf, end_rf, false);
2341 visit(expanded_from, expanded_thrus, &expanded_to);
2342 }
2343 }
2344 else
2345 visit(expanded_from, expanded_thrus, nullptr);
2346 }
2347
2348 ////////////////////////////////////////////////////////////////
2349
ExceptionState(ExceptionPath * exception,ExceptionThru * next_thru,int index)2350 ExceptionState::ExceptionState(ExceptionPath *exception,
2351 ExceptionThru *next_thru,
2352 int index) :
2353 exception_(exception),
2354 next_thru_(next_thru),
2355 next_state_(nullptr),
2356 index_(index)
2357 {
2358 }
2359
2360 void
setNextState(ExceptionState * next_state)2361 ExceptionState::setNextState(ExceptionState *next_state)
2362 {
2363 next_state_ = next_state;
2364 }
2365
2366 bool
matchesNextThru(const Pin * from_pin,const Pin * to_pin,const RiseFall * to_rf,const MinMax * min_max,const Network * network) const2367 ExceptionState::matchesNextThru(const Pin *from_pin,
2368 const Pin *to_pin,
2369 const RiseFall *to_rf,
2370 const MinMax *min_max,
2371 const Network *network) const
2372 {
2373 // Don't advance the state if the exception is complete (no next_thru_).
2374 return next_thru_
2375 && exception_->matches(min_max, false)
2376 && next_thru_->matches(from_pin, to_pin, to_rf, network);
2377 }
2378
2379 bool
isComplete() const2380 ExceptionState::isComplete() const
2381 {
2382 return next_thru_ == nullptr
2383 && exception_->to() == nullptr;
2384 }
2385
2386 size_t
hash() const2387 ExceptionState::hash() const
2388 {
2389 return hashSum(exception_->hash(), index_);
2390 }
2391
2392 ////////////////////////////////////////////////////////////////
2393
2394 class ExceptionLess
2395 {
2396 public:
2397 explicit ExceptionLess(const Network *network);
2398 bool operator()(ExceptionPath *except1,
2399 ExceptionPath *except2);
2400
2401 private:
2402 const Network *network_;
2403 };
2404
ExceptionLess(const Network * network)2405 ExceptionLess::ExceptionLess(const Network *network) :
2406 network_(network)
2407 {
2408 }
2409
2410 bool
operator ()(ExceptionPath * except1,ExceptionPath * except2)2411 ExceptionLess::operator()(ExceptionPath *except1,
2412 ExceptionPath *except2)
2413 {
2414 int priority1 = except1->typePriority() + except1->minMax()->index();
2415 int priority2 = except2->typePriority() + except2->minMax()->index();
2416 if (priority1 == priority2) {
2417 ExceptionPtIterator pt_iter1(except1);
2418 ExceptionPtIterator pt_iter2(except2);
2419 while (pt_iter1.hasNext() && pt_iter2.hasNext()) {
2420 ExceptionPt *pt1 = pt_iter1.next();
2421 ExceptionPt *pt2 = pt_iter2.next();
2422 int cmp = pt1->nameCmp(pt2, network_);
2423 if (cmp != 0)
2424 return cmp < 0;
2425 }
2426 // Lesser has fewer exception pts.
2427 return !pt_iter1.hasNext() && pt_iter2.hasNext();
2428 }
2429 else
2430 return (priority1 < priority2);
2431 }
2432
2433 void
sortExceptions(ExceptionPathSet * set,ExceptionPathSeq & exceptions,Network * network)2434 sortExceptions(ExceptionPathSet *set,
2435 ExceptionPathSeq &exceptions,
2436 Network *network)
2437 {
2438 ExceptionPathSet::Iterator except_iter(set);
2439 while (except_iter.hasNext()) {
2440 ExceptionPath *exception = except_iter.next();
2441 exceptions.push_back(exception);
2442 }
2443 sort(exceptions, ExceptionLess(network));
2444 }
2445
2446 ////////////////////////////////////////////////////////////////
2447
2448 class InsertPinPairsThru : public HierPinThruVisitor
2449 {
2450 public:
2451 InsertPinPairsThru(PinPairSet *pairs,
2452 const Network *network);
2453
2454 protected:
2455 virtual void visit(Pin *drvr,
2456 Pin *load);
2457
2458 PinPairSet *pairs_;
2459 const Network *network_;
2460
2461 private:
2462 DISALLOW_COPY_AND_ASSIGN(InsertPinPairsThru);
2463 };
2464
InsertPinPairsThru(PinPairSet * pairs,const Network * network)2465 InsertPinPairsThru::InsertPinPairsThru(PinPairSet *pairs,
2466 const Network *network) :
2467 HierPinThruVisitor(),
2468 pairs_(pairs),
2469 network_(network)
2470 {
2471 }
2472
2473 void
visit(Pin * drvr,Pin * load)2474 InsertPinPairsThru::visit(Pin *drvr,
2475 Pin *load)
2476 {
2477 PinPair probe(drvr, load);
2478 if (!pairs_->hasKey(&probe)) {
2479 PinPair *pair = new PinPair(drvr, load);
2480 pairs_->insert(pair);
2481 }
2482 }
2483
2484 static void
insertPinPairsThruHierPin(const Pin * hpin,const Network * network,PinPairSet * pairs)2485 insertPinPairsThruHierPin(const Pin *hpin,
2486 const Network *network,
2487 PinPairSet *pairs)
2488 {
2489 InsertPinPairsThru visitor(pairs, network);
2490 visitDrvrLoadsThruHierPin(hpin, network, &visitor);
2491 }
2492
2493 static void
insertPinPairsThruNet(Net * net,const Network * network,PinPairSet * pairs)2494 insertPinPairsThruNet(Net *net,
2495 const Network *network,
2496 PinPairSet *pairs)
2497 {
2498 InsertPinPairsThru visitor(pairs, network);
2499 visitDrvrLoadsThruNet(net, network, &visitor);
2500 }
2501
2502 class DeletePinPairsThru : public HierPinThruVisitor
2503 {
2504 public:
2505 DeletePinPairsThru(PinPairSet *pairs,
2506 const Network *network);
2507
2508 protected:
2509 virtual void visit(Pin *drvr,
2510 Pin *load);
2511
2512 PinPairSet *pairs_;
2513 const Network *network_;
2514
2515 private:
2516 DISALLOW_COPY_AND_ASSIGN(DeletePinPairsThru);
2517 };
2518
DeletePinPairsThru(PinPairSet * pairs,const Network * network)2519 DeletePinPairsThru::DeletePinPairsThru(PinPairSet *pairs,
2520 const Network *network) :
2521 HierPinThruVisitor(),
2522 pairs_(pairs),
2523 network_(network)
2524 {
2525 }
2526
2527 void
visit(Pin * drvr,Pin * load)2528 DeletePinPairsThru::visit(Pin *drvr,
2529 Pin *load)
2530 {
2531 PinPair probe(drvr, load);
2532 pairs_->erase(&probe);
2533 }
2534
2535 static void
deletePinPairsThruHierPin(const Pin * hpin,const Network * network,PinPairSet * pairs)2536 deletePinPairsThruHierPin(const Pin *hpin,
2537 const Network *network,
2538 PinPairSet *pairs)
2539 {
2540 DeletePinPairsThru visitor(pairs, network);
2541 visitDrvrLoadsThruHierPin(hpin, network, &visitor);
2542 }
2543
2544 } // namespace
2545