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 "Search.hh"
18
19 #include <algorithm>
20 #include <cmath> // abs
21
22 #include "DisallowCopyAssign.hh"
23 #include "Mutex.hh"
24 #include "Report.hh"
25 #include "Debug.hh"
26 #include "Error.hh"
27 #include "Stats.hh"
28 #include "Fuzzy.hh"
29 #include "TimingRole.hh"
30 #include "FuncExpr.hh"
31 #include "TimingArc.hh"
32 #include "Sequential.hh"
33 #include "Units.hh"
34 #include "Liberty.hh"
35 #include "Network.hh"
36 #include "PortDirection.hh"
37 #include "Graph.hh"
38 #include "GraphCmp.hh"
39 #include "PortDelay.hh"
40 #include "Clock.hh"
41 #include "CycleAccting.hh"
42 #include "ExceptionPath.hh"
43 #include "DataCheck.hh"
44 #include "Sdc.hh"
45 #include "DcalcAnalysisPt.hh"
46 #include "SearchPred.hh"
47 #include "Levelize.hh"
48 #include "Bfs.hh"
49 #include "Corner.hh"
50 #include "Sim.hh"
51 #include "PathVertex.hh"
52 #include "PathVertexRep.hh"
53 #include "PathRef.hh"
54 #include "ClkInfo.hh"
55 #include "Tag.hh"
56 #include "TagGroup.hh"
57 #include "PathEnd.hh"
58 #include "PathGroup.hh"
59 #include "PathAnalysisPt.hh"
60 #include "VisitPathEnds.hh"
61 #include "GatedClk.hh"
62 #include "WorstSlack.hh"
63 #include "Latches.hh"
64 #include "Crpr.hh"
65 #include "Genclks.hh"
66
67 namespace sta {
68
69 using std::min;
70 using std::max;
71 using std::abs;
72
73 ////////////////////////////////////////////////////////////////
74
EvalPred(const StaState * sta)75 EvalPred::EvalPred(const StaState *sta) :
76 SearchPred0(sta),
77 search_thru_latches_(true)
78 {
79 }
80
81 void
setSearchThruLatches(bool thru_latches)82 EvalPred::setSearchThruLatches(bool thru_latches)
83 {
84 search_thru_latches_ = thru_latches;
85 }
86
87 bool
searchThru(Edge * edge)88 EvalPred::searchThru(Edge *edge)
89 {
90 const Sdc *sdc = sta_->sdc();
91 TimingRole *role = edge->role();
92 return SearchPred0::searchThru(edge)
93 && (sdc->dynamicLoopBreaking()
94 || !edge->isDisabledLoop())
95 && !role->isTimingCheck()
96 && (search_thru_latches_
97 || role != TimingRole::latchDtoQ()
98 || sta_->latches()->latchDtoQState(edge) == LatchEnableState::open);
99 }
100
101 bool
searchTo(const Vertex * to_vertex)102 EvalPred::searchTo(const Vertex *to_vertex)
103 {
104 const Sdc *sdc = sta_->sdc();
105 const Pin *pin = to_vertex->pin();
106 return SearchPred0::searchTo(to_vertex)
107 && !(sdc->isLeafPinClock(pin)
108 && !sdc->isPathDelayInternalEndpoint(pin));
109 }
110
111 ////////////////////////////////////////////////////////////////
112
DynLoopSrchPred(TagGroupBldr * tag_bldr)113 DynLoopSrchPred::DynLoopSrchPred(TagGroupBldr *tag_bldr) :
114 tag_bldr_(tag_bldr)
115 {
116 }
117
118 bool
loopEnabled(Edge * edge,const Sdc * sdc,const Graph * graph,Search * search)119 DynLoopSrchPred::loopEnabled(Edge *edge,
120 const Sdc *sdc,
121 const Graph *graph,
122 Search *search)
123 {
124 return !edge->isDisabledLoop()
125 || (sdc->dynamicLoopBreaking()
126 && hasPendingLoopPaths(edge, graph, search));
127 }
128
129 bool
hasPendingLoopPaths(Edge * edge,const Graph * graph,Search * search)130 DynLoopSrchPred::hasPendingLoopPaths(Edge *edge,
131 const Graph *graph,
132 Search *search)
133 {
134 if (tag_bldr_
135 && tag_bldr_->hasLoopTag()) {
136 Corners *corners = search->corners();
137 Vertex *from_vertex = edge->from(graph);
138 TagGroup *prev_tag_group = search->tagGroup(from_vertex);
139 ArrivalMap::Iterator arrival_iter(tag_bldr_->arrivalMap());
140 while (arrival_iter.hasNext()) {
141 Tag *from_tag;
142 int arrival_index;
143 arrival_iter.next(from_tag, arrival_index);
144 if (from_tag->isLoop()) {
145 // Loop false path exceptions apply to rise/fall edges so to_rf
146 // does not matter.
147 PathAPIndex path_ap_index = from_tag->pathAPIndex();
148 PathAnalysisPt *path_ap = corners->findPathAnalysisPt(path_ap_index);
149 Tag *to_tag = search->thruTag(from_tag, edge, RiseFall::rise(),
150 path_ap->pathMinMax(), path_ap);
151 if (to_tag
152 && (prev_tag_group == nullptr
153 || !prev_tag_group->hasTag(from_tag)))
154 return true;
155 }
156 }
157 }
158 return false;
159 }
160
161 // EvalPred unless
162 // latch D->Q edge
163 class SearchThru : public EvalPred, public DynLoopSrchPred
164 {
165 public:
166 SearchThru(TagGroupBldr *tag_bldr,
167 const StaState *sta);
168 virtual bool searchThru(Edge *edge);
169
170 private:
171 DISALLOW_COPY_AND_ASSIGN(SearchThru);
172 };
173
SearchThru(TagGroupBldr * tag_bldr,const StaState * sta)174 SearchThru::SearchThru(TagGroupBldr *tag_bldr,
175 const StaState *sta) :
176 EvalPred(sta),
177 DynLoopSrchPred(tag_bldr)
178 {
179 }
180
181 bool
searchThru(Edge * edge)182 SearchThru::searchThru(Edge *edge)
183 {
184 const Graph *graph = sta_->graph();
185 const Sdc *sdc = sta_->sdc();
186 Search *search = sta_->search();
187 return EvalPred::searchThru(edge)
188 // Only search thru latch D->Q if it is always open.
189 // Enqueue thru latches is handled explicitly by search.
190 && (edge->role() != TimingRole::latchDtoQ()
191 || sta_->latches()->latchDtoQState(edge) == LatchEnableState::open)
192 && loopEnabled(edge, sdc, graph, search);
193 }
194
ClkArrivalSearchPred(const StaState * sta)195 ClkArrivalSearchPred::ClkArrivalSearchPred(const StaState *sta) :
196 EvalPred(sta)
197 {
198 }
199
200 bool
searchThru(Edge * edge)201 ClkArrivalSearchPred::searchThru(Edge *edge)
202 {
203 const TimingRole *role = edge->role();
204 return (role->isWire()
205 || role == TimingRole::combinational())
206 && EvalPred::searchThru(edge);
207 }
208
209 ////////////////////////////////////////////////////////////////
210
Search(StaState * sta)211 Search::Search(StaState *sta) :
212 StaState(sta)
213 {
214 init(sta);
215 }
216
217 void
init(StaState * sta)218 Search::init(StaState *sta)
219 {
220 initVars();
221
222 search_adj_ = new SearchThru(nullptr, sta);
223 eval_pred_ = new EvalPred(sta);
224 check_crpr_ = new CheckCrpr(sta);
225 genclks_ = new Genclks(sta);
226 arrival_visitor_ = new ArrivalVisitor(sta);
227 clk_arrivals_valid_ = false;
228 arrivals_exist_ = false;
229 arrivals_at_endpoints_exist_ = false;
230 arrivals_seeded_ = false;
231 requireds_exist_ = false;
232 requireds_seeded_ = false;
233 tns_exists_ = false;
234 worst_slacks_ = nullptr;
235 arrival_iter_ = new BfsFwdIterator(BfsIndex::arrival, nullptr, sta);
236 required_iter_ = new BfsBkwdIterator(BfsIndex::required, search_adj_, sta);
237 tag_capacity_ = 127;
238 tag_set_ = new TagHashSet(tag_capacity_, false);
239 clk_info_set_ = new ClkInfoSet(ClkInfoLess(sta));
240 tag_next_ = 0;
241 tags_ = new Tag*[tag_capacity_];
242 tag_group_capacity_ = 127;
243 tag_groups_ = new TagGroup*[tag_group_capacity_];
244 tag_group_next_ = 0;
245 tag_group_set_ = new TagGroupSet(tag_group_capacity_, false);
246 visit_path_ends_ = new VisitPathEnds(this);
247 gated_clk_ = new GatedClk(this);
248 path_groups_ = nullptr;
249 endpoints_ = nullptr;
250 invalid_endpoints_ = nullptr;
251 filter_ = nullptr;
252 filter_from_ = nullptr;
253 filter_to_ = nullptr;
254 found_downstream_clk_pins_ = false;
255 }
256
257 // Init "options".
258 void
initVars()259 Search::initVars()
260 {
261 unconstrained_paths_ = false;
262 crpr_path_pruning_enabled_ = true;
263 crpr_approx_missing_requireds_ = true;
264 }
265
~Search()266 Search::~Search()
267 {
268 deletePaths();
269 deleteTags();
270 delete tag_set_;
271 delete clk_info_set_;
272 delete [] tags_;
273 delete [] tag_groups_;
274 delete tag_group_set_;
275 delete search_adj_;
276 delete eval_pred_;
277 delete arrival_visitor_;
278 delete arrival_iter_;
279 delete required_iter_;
280 delete endpoints_;
281 delete invalid_endpoints_;
282 delete visit_path_ends_;
283 delete gated_clk_;
284 delete worst_slacks_;
285 delete check_crpr_;
286 delete genclks_;
287 deleteFilter();
288 deletePathGroups();
289 }
290
291 void
clear()292 Search::clear()
293 {
294 initVars();
295
296 clk_arrivals_valid_ = false;
297 arrivals_at_endpoints_exist_ = false;
298 arrivals_seeded_ = false;
299 requireds_exist_ = false;
300 requireds_seeded_ = false;
301 tns_exists_ = false;
302 clearWorstSlack();
303 invalid_arrivals_.clear();
304 arrival_iter_->clear();
305 invalid_requireds_.clear();
306 invalid_tns_.clear();
307 required_iter_->clear();
308 endpointsInvalid();
309 deletePathGroups();
310 deletePaths();
311 deleteTags();
312 clearPendingLatchOutputs();
313 deleteFilter();
314 genclks_->clear();
315 found_downstream_clk_pins_ = false;
316 }
317
318 bool
crprPathPruningEnabled() const319 Search::crprPathPruningEnabled() const
320 {
321 return crpr_path_pruning_enabled_;
322 }
323
324 void
setCrprpathPruningEnabled(bool enabled)325 Search::setCrprpathPruningEnabled(bool enabled)
326 {
327 crpr_path_pruning_enabled_ = enabled;
328 }
329
330 bool
crprApproxMissingRequireds() const331 Search::crprApproxMissingRequireds() const
332 {
333 return crpr_approx_missing_requireds_;
334 }
335
336 void
setCrprApproxMissingRequireds(bool enabled)337 Search::setCrprApproxMissingRequireds(bool enabled)
338 {
339 crpr_approx_missing_requireds_ = enabled;
340 }
341
342 void
deleteTags()343 Search::deleteTags()
344 {
345 for (TagGroupIndex i = 0; i < tag_group_next_; i++) {
346 TagGroup *group = tag_groups_[i];
347 delete group;
348 }
349 tag_group_next_ = 0;
350 tag_group_set_->clear();
351 tag_group_free_indices_.clear();
352
353 tag_next_ = 0;
354 tag_set_->deleteContentsClear();
355 tag_free_indices_.clear();
356
357 clk_info_set_->deleteContentsClear();
358 }
359
360 void
deleteFilter()361 Search::deleteFilter()
362 {
363 if (filter_) {
364 sdc_->deleteException(filter_);
365 filter_ = nullptr;
366 filter_from_ = nullptr;
367 }
368 else {
369 // Filter owns filter_from_ if it exists.
370 delete filter_from_;
371 filter_from_ = nullptr;
372 }
373 delete filter_to_;
374 filter_to_ = nullptr;
375 }
376
377 void
copyState(const StaState * sta)378 Search::copyState(const StaState *sta)
379 {
380 StaState::copyState(sta);
381 // Notify sub-components.
382 arrival_iter_->copyState(sta);
383 required_iter_->copyState(sta);
384 visit_path_ends_->copyState(sta);
385 gated_clk_->copyState(sta);
386 check_crpr_->copyState(sta);
387 genclks_->copyState(sta);
388 }
389
390 ////////////////////////////////////////////////////////////////
391
392 void
deletePaths()393 Search::deletePaths()
394 {
395 debugPrint(debug_, "search", 1, "delete paths");
396 if (arrivals_exist_) {
397 VertexIterator vertex_iter(graph_);
398 while (vertex_iter.hasNext()) {
399 Vertex *vertex = vertex_iter.next();
400 vertex->deletePaths();
401 }
402 graph_->clearArrivals();
403 graph_->clearPrevPaths();
404 arrivals_exist_ = false;
405 }
406 }
407
408 void
deletePaths(Vertex * vertex)409 Search::deletePaths(Vertex *vertex)
410 {
411 tnsNotifyBefore(vertex);
412 if (worst_slacks_)
413 worst_slacks_->worstSlackNotifyBefore(vertex);
414 vertex->deletePaths();
415 }
416
417 ////////////////////////////////////////////////////////////////
418
419 // from/thrus/to are owned and deleted by Search.
420 // Returned sequence is owned by the caller.
421 // PathEnds are owned by Search PathGroups and deleted on next call.
422 PathEndSeq *
findPathEnds(ExceptionFrom * from,ExceptionThruSeq * thrus,ExceptionTo * to,bool unconstrained,const Corner * corner,const MinMaxAll * min_max,int group_count,int endpoint_count,bool unique_pins,float slack_min,float slack_max,bool sort_by_slack,PathGroupNameSet * group_names,bool setup,bool hold,bool recovery,bool removal,bool clk_gating_setup,bool clk_gating_hold)423 Search::findPathEnds(ExceptionFrom *from,
424 ExceptionThruSeq *thrus,
425 ExceptionTo *to,
426 bool unconstrained,
427 const Corner *corner,
428 const MinMaxAll *min_max,
429 int group_count,
430 int endpoint_count,
431 bool unique_pins,
432 float slack_min,
433 float slack_max,
434 bool sort_by_slack,
435 PathGroupNameSet *group_names,
436 bool setup,
437 bool hold,
438 bool recovery,
439 bool removal,
440 bool clk_gating_setup,
441 bool clk_gating_hold)
442 {
443 unconstrained_paths_ = unconstrained;
444 // Delete results from last findPathEnds.
445 // Filtered arrivals are deleted by Sta::searchPreamble.
446 deletePathGroups();
447 checkFromThrusTo(from, thrus, to);
448 filter_from_ = from;
449 filter_to_ = to;
450 if ((from
451 && (from->pins()
452 || from->instances()))
453 || thrus) {
454 filter_ = sdc_->makeFilterPath(from, thrus, nullptr);
455 findFilteredArrivals();
456 }
457 else
458 // These cases do not require filtered arrivals.
459 // -from clocks
460 // -to
461 findAllArrivals();
462 if (!sdc_->recoveryRemovalChecksEnabled())
463 recovery = removal = false;
464 if (!sdc_->gatedClkChecksEnabled())
465 clk_gating_setup = clk_gating_hold = false;
466 path_groups_ = makePathGroups(group_count, endpoint_count, unique_pins,
467 slack_min, slack_max,
468 group_names, setup, hold,
469 recovery, removal,
470 clk_gating_setup, clk_gating_hold);
471 ensureDownstreamClkPins();
472 PathEndSeq *path_ends = path_groups_->makePathEnds(to, unconstrained_paths_,
473 corner, min_max,
474 sort_by_slack);
475 sdc_->reportClkToClkMaxCycleWarnings();
476 return path_ends;
477 }
478
479 // From/thrus/to are used to make a filter exception. If the last
480 // search used a filter arrival/required times were only found for a
481 // subset of the paths. Delete the paths that have a filter
482 // exception state.
483 void
deleteFilteredArrivals()484 Search::deleteFilteredArrivals()
485 {
486 if (filter_) {
487 ExceptionFrom *from = filter_->from();
488 ExceptionThruSeq *thrus = filter_->thrus();
489 if ((from
490 && (from->pins()
491 || from->instances()))
492 || thrus) {
493 VertexIterator vertex_iter(graph_);
494 while (vertex_iter.hasNext()) {
495 Vertex *vertex = vertex_iter.next();
496 TagGroup *tag_group = tagGroup(vertex);
497 if (tag_group
498 && tag_group->hasFilterTag()) {
499 // Vertex's tag_group will be deleted.
500 deletePaths(vertex);
501 arrivalInvalid(vertex);
502 requiredInvalid(vertex);
503 }
504 }
505 deleteFilterTagGroups();
506 deleteFilterClkInfos();
507 deleteFilterTags();
508 }
509 }
510 deleteFilter();
511 }
512
513 void
deleteFilterTagGroups()514 Search::deleteFilterTagGroups()
515 {
516 for (TagGroupIndex i = 0; i < tag_group_next_; i++) {
517 TagGroup *group = tag_groups_[i];
518 if (group
519 && group->hasFilterTag()) {
520 tag_group_set_->erase(group);
521 tag_groups_[group->index()] = nullptr;
522 tag_group_free_indices_.push_back(i);
523 delete group;
524 }
525 }
526 }
527
528 void
deleteFilterTags()529 Search::deleteFilterTags()
530 {
531 for (TagIndex i = 0; i < tag_next_; i++) {
532 Tag *tag = tags_[i];
533 if (tag
534 && tag->isFilter()) {
535 tags_[i] = nullptr;
536 tag_set_->erase(tag);
537 delete tag;
538 tag_free_indices_.push_back(i);
539 }
540 }
541 }
542
543 void
deleteFilterClkInfos()544 Search::deleteFilterClkInfos()
545 {
546 ClkInfoSet::Iterator clk_info_iter(clk_info_set_);
547 while (clk_info_iter.hasNext()) {
548 ClkInfo *clk_info = clk_info_iter.next();
549 if (clk_info->refsFilter(this)) {
550 clk_info_set_->erase(clk_info);
551 delete clk_info;
552 }
553 }
554 }
555
556 void
findFilteredArrivals()557 Search::findFilteredArrivals()
558 {
559 findArrivals1();
560 seedFilterStarts();
561 Level max_level = levelize_->maxLevel();
562 // Search always_to_endpoint to search from exisiting arrivals at
563 // fanin startpoints to reach -thru/-to endpoints.
564 arrival_visitor_->init(true);
565 // Iterate until data arrivals at all latches stop changing.
566 for (int pass = 1; pass <= 2 || havePendingLatchOutputs() ; pass++) {
567 enqueuePendingLatchOutputs();
568 debugPrint(debug_, "search", 1, "find arrivals pass %d", pass);
569 int arrival_count = arrival_iter_->visitParallel(max_level,
570 arrival_visitor_);
571 debugPrint(debug_, "search", 1, "found %d arrivals", arrival_count);
572 }
573 arrivals_exist_ = true;
574 }
575
576 class SeedFaninsThruHierPin : public HierPinThruVisitor
577 {
578 public:
579 SeedFaninsThruHierPin(Graph *graph,
580 Search *search);
581
582 protected:
583 virtual void visit(Pin *drvr,
584 Pin *load);
585
586 Graph *graph_;
587 Search *search_;
588
589 private:
590 DISALLOW_COPY_AND_ASSIGN(SeedFaninsThruHierPin);
591 };
592
SeedFaninsThruHierPin(Graph * graph,Search * search)593 SeedFaninsThruHierPin::SeedFaninsThruHierPin(Graph *graph,
594 Search *search) :
595 HierPinThruVisitor(),
596 graph_(graph),
597 search_(search)
598 {
599 }
600
601 void
visit(Pin * drvr,Pin *)602 SeedFaninsThruHierPin::visit(Pin *drvr,
603 Pin *)
604 {
605 Vertex *vertex, *bidirect_drvr_vertex;
606 graph_->pinVertices(drvr, vertex, bidirect_drvr_vertex);
607 search_->seedArrival(vertex);
608 if (bidirect_drvr_vertex)
609 search_->seedArrival(bidirect_drvr_vertex);
610 }
611
612 void
seedFilterStarts()613 Search::seedFilterStarts()
614 {
615 ExceptionPt *first_pt = filter_->firstPt();
616 PinSet first_pins;
617 first_pt->allPins(network_, &first_pins);
618 for (Pin *pin : first_pins) {
619 if (network_->isHierarchical(pin)) {
620 SeedFaninsThruHierPin visitor(graph_, this);
621 visitDrvrLoadsThruHierPin(pin, network_, &visitor);
622 }
623 else {
624 Vertex *vertex, *bidirect_drvr_vertex;
625 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
626 seedArrival(vertex);
627 if (bidirect_drvr_vertex)
628 seedArrival(bidirect_drvr_vertex);
629 }
630 }
631 }
632
633 ////////////////////////////////////////////////////////////////
634
635 void
deleteVertexBefore(Vertex * vertex)636 Search::deleteVertexBefore(Vertex *vertex)
637 {
638 if (arrivals_exist_) {
639 deletePaths(vertex);
640 arrival_iter_->deleteVertexBefore(vertex);
641 invalid_arrivals_.erase(vertex);
642 }
643 if (requireds_exist_) {
644 required_iter_->deleteVertexBefore(vertex);
645 invalid_requireds_.erase(vertex);
646 invalid_tns_.erase(vertex);
647 }
648 if (endpoints_)
649 endpoints_->erase(vertex);
650 if (invalid_endpoints_)
651 invalid_endpoints_->erase(vertex);
652 }
653
654 bool
arrivalsValid()655 Search::arrivalsValid()
656 {
657 return arrivals_exist_
658 && invalid_requireds_.empty();
659 }
660
661 void
arrivalsInvalid()662 Search::arrivalsInvalid()
663 {
664 if (arrivals_exist_) {
665 debugPrint(debug_, "search", 1, "arrivals invalid");
666 // Delete paths to make sure no state is left over.
667 // For example, set_disable_timing strands a vertex, which means
668 // the search won't revisit it to clear the previous arrival.
669 deletePaths();
670 deleteTags();
671 genclks_->clear();
672 deleteFilter();
673 arrivals_at_endpoints_exist_ = false;
674 arrivals_seeded_ = false;
675 requireds_exist_ = false;
676 requireds_seeded_ = false;
677 clk_arrivals_valid_ = false;
678 arrival_iter_->clear();
679 required_iter_->clear();
680 // No need to keep track of incremental updates any more.
681 invalid_arrivals_.clear();
682 invalid_requireds_.clear();
683 tns_exists_ = false;
684 clearWorstSlack();
685 invalid_tns_.clear();
686 }
687 }
688
689 void
requiredsInvalid()690 Search::requiredsInvalid()
691 {
692 debugPrint(debug_, "search", 1, "requireds invalid");
693 requireds_exist_ = false;
694 requireds_seeded_ = false;
695 invalid_requireds_.clear();
696 tns_exists_ = false;
697 clearWorstSlack();
698 invalid_tns_.clear();
699 }
700
701 void
arrivalInvalid(Vertex * vertex)702 Search::arrivalInvalid(Vertex *vertex)
703 {
704 if (arrivals_exist_) {
705 debugPrint(debug_, "search", 2, "arrival invalid %s",
706 vertex->name(sdc_network_));
707 if (!arrival_iter_->inQueue(vertex)) {
708 // Lock for StaDelayCalcObserver called by delay calc threads.
709 UniqueLock lock(invalid_arrivals_lock_);
710 invalid_arrivals_.insert(vertex);
711 }
712 tnsInvalid(vertex);
713 }
714 }
715
716 void
arrivalInvalidDelete(Vertex * vertex)717 Search::arrivalInvalidDelete(Vertex *vertex)
718 {
719 arrivalInvalid(vertex);
720 vertex->deletePaths();
721 }
722
723 void
levelChangedBefore(Vertex * vertex)724 Search::levelChangedBefore(Vertex *vertex)
725 {
726 if (arrivals_exist_) {
727 arrival_iter_->remove(vertex);
728 required_iter_->remove(vertex);
729 search_->arrivalInvalid(vertex);
730 search_->requiredInvalid(vertex);
731 }
732 }
733
734 void
arrivalInvalid(const Pin * pin)735 Search::arrivalInvalid(const Pin *pin)
736 {
737 if (graph_) {
738 Vertex *vertex, *bidirect_drvr_vertex;
739 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
740 arrivalInvalid(vertex);
741 if (bidirect_drvr_vertex)
742 arrivalInvalid(bidirect_drvr_vertex);
743 }
744 }
745
746 void
requiredInvalid(Instance * inst)747 Search::requiredInvalid(Instance *inst)
748 {
749 if (graph_) {
750 InstancePinIterator *pin_iter = network_->pinIterator(inst);
751 while (pin_iter->hasNext()) {
752 Pin *pin = pin_iter->next();
753 requiredInvalid(pin);
754 }
755 delete pin_iter;
756 }
757 }
758
759 void
requiredInvalid(const Pin * pin)760 Search::requiredInvalid(const Pin *pin)
761 {
762 if (graph_) {
763 Vertex *vertex, *bidirect_drvr_vertex;
764 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
765 requiredInvalid(vertex);
766 if (bidirect_drvr_vertex)
767 requiredInvalid(bidirect_drvr_vertex);
768 }
769 }
770
771 void
requiredInvalid(Vertex * vertex)772 Search::requiredInvalid(Vertex *vertex)
773 {
774 if (requireds_exist_) {
775 debugPrint(debug_, "search", 2, "required invalid %s",
776 vertex->name(sdc_network_));
777 if (!required_iter_->inQueue(vertex)) {
778 // Lock for StaDelayCalcObserver called by delay calc threads.
779 UniqueLock lock(invalid_arrivals_lock_);
780 invalid_requireds_.insert(vertex);
781 }
782 tnsInvalid(vertex);
783 }
784 }
785
786 ////////////////////////////////////////////////////////////////
787
788 void
findClkArrivals()789 Search::findClkArrivals()
790 {
791 if (!clk_arrivals_valid_) {
792 genclks_->ensureInsertionDelays();
793 Stats stats(debug_, report_);
794 debugPrint(debug_, "search", 1, "find clk arrivals");
795 arrival_iter_->clear();
796 seedClkVertexArrivals();
797 ClkArrivalSearchPred search_clk(this);
798 arrival_visitor_->init(false, &search_clk);
799 arrival_iter_->visitParallel(levelize_->maxLevel(), arrival_visitor_);
800 arrivals_exist_ = true;
801 stats.report("Find clk arrivals");
802 }
803 clk_arrivals_valid_ = true;
804 }
805
806 void
seedClkVertexArrivals()807 Search::seedClkVertexArrivals()
808 {
809 PinSet clk_pins;
810 findClkVertexPins(clk_pins);
811 for (Pin *pin : clk_pins) {
812 Vertex *vertex, *bidirect_drvr_vertex;
813 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
814 seedClkVertexArrivals(pin, vertex);
815 if (bidirect_drvr_vertex)
816 seedClkVertexArrivals(pin, bidirect_drvr_vertex);
817 }
818 }
819
820 void
seedClkVertexArrivals(const Pin * pin,Vertex * vertex)821 Search::seedClkVertexArrivals(const Pin *pin,
822 Vertex *vertex)
823 {
824 TagGroupBldr tag_bldr(true, this);
825 tag_bldr.init(vertex);
826 genclks_->copyGenClkSrcPaths(vertex, &tag_bldr);
827 seedClkArrivals(pin, vertex, &tag_bldr);
828 setVertexArrivals(vertex, &tag_bldr);
829 }
830
831 Arrival
clockInsertion(const Clock * clk,const Pin * pin,const RiseFall * rf,const MinMax * min_max,const EarlyLate * early_late,const PathAnalysisPt * path_ap) const832 Search::clockInsertion(const Clock *clk,
833 const Pin *pin,
834 const RiseFall *rf,
835 const MinMax *min_max,
836 const EarlyLate *early_late,
837 const PathAnalysisPt *path_ap) const
838 {
839 float insert;
840 bool exists;
841 sdc_->clockInsertion(clk, pin, rf, min_max, early_late, insert, exists);
842 if (exists)
843 return insert;
844 else if (clk->isGeneratedWithPropagatedMaster())
845 return genclks_->insertionDelay(clk, pin, rf, early_late, path_ap);
846 else
847 return 0.0;
848 }
849
850 ////////////////////////////////////////////////////////////////
851
852 void
visitStartpoints(VertexVisitor * visitor)853 Search::visitStartpoints(VertexVisitor *visitor)
854 {
855 Instance *top_inst = network_->topInstance();
856 InstancePinIterator *pin_iter = network_->pinIterator(top_inst);
857 while (pin_iter->hasNext()) {
858 Pin *pin = pin_iter->next();
859 if (network_->direction(pin)->isAnyInput()) {
860 Vertex *vertex = graph_->pinDrvrVertex(pin);
861 visitor->visit(vertex);
862 }
863 }
864 delete pin_iter;
865
866 for (auto iter : sdc_->inputDelayPinMap()) {
867 const Pin *pin = iter.first;
868 // Already hit these.
869 if (!network_->isTopLevelPort(pin)) {
870 Vertex *vertex = graph_->pinDrvrVertex(pin);
871 if (vertex)
872 visitor->visit(vertex);
873 }
874 }
875
876 for (Clock *clk : sdc_->clks()) {
877 for (Pin *pin : clk->leafPins()) {
878 // Already hit these.
879 if (!network_->isTopLevelPort(pin)) {
880 Vertex *vertex = graph_->pinDrvrVertex(pin);
881 visitor->visit(vertex);
882 }
883 }
884 }
885
886 // Register clk pins.
887 for (Vertex *vertex : *graph_->regClkVertices())
888 visitor->visit(vertex);
889
890 auto startpoints = sdc_->pathDelayInternalStartpoints();
891 if (startpoints) {
892 for (Pin *pin : *startpoints) {
893 Vertex *vertex = graph_->pinDrvrVertex(pin);
894 visitor->visit(vertex);
895 }
896 }
897 }
898
899 void
visitEndpoints(VertexVisitor * visitor)900 Search::visitEndpoints(VertexVisitor *visitor)
901 {
902 for (Vertex *end : *endpoints()) {
903 Pin *pin = end->pin();
904 // Filter register clock pins (fails on set_max_delay -from clk_src).
905 if (!network_->isRegClkPin(pin)
906 || sdc_->isPathDelayInternalEndpoint(pin))
907 visitor->visit(end);
908 }
909 }
910
911 ////////////////////////////////////////////////////////////////
912
913 void
findAllArrivals()914 Search::findAllArrivals()
915 {
916 arrival_visitor_->init(false);
917 findAllArrivals(arrival_visitor_);
918 }
919
920 void
findAllArrivals(VertexVisitor * arrival_visitor)921 Search::findAllArrivals(VertexVisitor *arrival_visitor)
922 {
923 // Iterate until data arrivals at all latches stop changing.
924 for (int pass = 1; pass == 1 || havePendingLatchOutputs(); pass++) {
925 enqueuePendingLatchOutputs();
926 debugPrint(debug_, "search", 1, "find arrivals pass %d", pass);
927 findArrivals(levelize_->maxLevel(), arrival_visitor);
928 }
929 }
930
931 bool
havePendingLatchOutputs()932 Search::havePendingLatchOutputs()
933 {
934 return pending_latch_outputs_.size() > 0;
935 }
936
937 void
clearPendingLatchOutputs()938 Search::clearPendingLatchOutputs()
939 {
940 pending_latch_outputs_.clear();
941 }
942
943 void
enqueuePendingLatchOutputs()944 Search::enqueuePendingLatchOutputs()
945 {
946 for (Vertex *latch_vertex : pending_latch_outputs_)
947 arrival_iter_->enqueue(latch_vertex);
948 clearPendingLatchOutputs();
949 }
950
951 void
findArrivals()952 Search::findArrivals()
953 {
954 findArrivals(levelize_->maxLevel());
955 }
956
957 void
findArrivals(Level level)958 Search::findArrivals(Level level)
959 {
960 arrival_visitor_->init(false);
961 findArrivals(level, arrival_visitor_);
962 }
963
964 void
findArrivals(Level level,VertexVisitor * arrival_visitor)965 Search::findArrivals(Level level,
966 VertexVisitor *arrival_visitor)
967 {
968 debugPrint(debug_, "search", 1, "find arrivals to level %d", level);
969 findArrivals1();
970 Stats stats(debug_, report_);
971 int arrival_count = arrival_iter_->visitParallel(level, arrival_visitor);
972 stats.report("Find arrivals");
973 if (arrival_iter_->empty()
974 && invalid_arrivals_.empty()) {
975 clk_arrivals_valid_ = true;
976 arrivals_at_endpoints_exist_ = true;
977 }
978 arrivals_exist_ = true;
979 debugPrint(debug_, "search", 1, "found %u arrivals", arrival_count);
980 }
981
982 void
findArrivals1()983 Search::findArrivals1()
984 {
985 if (!arrivals_seeded_) {
986 genclks_->ensureInsertionDelays();
987 arrival_iter_->clear();
988 required_iter_->clear();
989 seedArrivals();
990 arrivals_seeded_ = true;
991 }
992 else {
993 arrival_iter_->ensureSize();
994 required_iter_->ensureSize();
995 }
996 seedInvalidArrivals();
997 }
998
999 ////////////////////////////////////////////////////////////////
1000
ArrivalVisitor(const StaState * sta)1001 ArrivalVisitor::ArrivalVisitor(const StaState *sta) :
1002 PathVisitor(nullptr, sta)
1003 {
1004 init0();
1005 init(true);
1006 }
1007
1008 // Copy constructor.
ArrivalVisitor(bool always_to_endpoints,SearchPred * pred,const StaState * sta)1009 ArrivalVisitor::ArrivalVisitor(bool always_to_endpoints,
1010 SearchPred *pred,
1011 const StaState *sta) :
1012 PathVisitor(pred, sta)
1013 {
1014 init0();
1015 init(always_to_endpoints, pred);
1016 }
1017
1018 void
init0()1019 ArrivalVisitor::init0()
1020 {
1021 tag_bldr_ = new TagGroupBldr(true, sta_);
1022 tag_bldr_no_crpr_ = new TagGroupBldr(false, sta_);
1023 adj_pred_ = new SearchThru(tag_bldr_, sta_);
1024 }
1025
1026 void
init(bool always_to_endpoints)1027 ArrivalVisitor::init(bool always_to_endpoints)
1028 {
1029 Search *search = sta_->search();
1030 init(always_to_endpoints, search ? search->evalPred() : nullptr);
1031 }
1032
1033 void
init(bool always_to_endpoints,SearchPred * pred)1034 ArrivalVisitor::init(bool always_to_endpoints,
1035 SearchPred *pred)
1036 {
1037 always_to_endpoints_ = always_to_endpoints;
1038 pred_ = pred;
1039 crpr_active_ = sta_->sdc()->crprActive();
1040 }
1041
1042
1043 VertexVisitor *
copy()1044 ArrivalVisitor::copy()
1045 {
1046 return new ArrivalVisitor(always_to_endpoints_, pred_, sta_);
1047 }
1048
~ArrivalVisitor()1049 ArrivalVisitor::~ArrivalVisitor()
1050 {
1051 delete tag_bldr_;
1052 delete tag_bldr_no_crpr_;
1053 delete adj_pred_;
1054 }
1055
1056 void
setAlwaysToEndpoints(bool to_endpoints)1057 ArrivalVisitor::setAlwaysToEndpoints(bool to_endpoints)
1058 {
1059 always_to_endpoints_ = to_endpoints;
1060 }
1061
1062 void
visit(Vertex * vertex)1063 ArrivalVisitor::visit(Vertex *vertex)
1064 {
1065 const Debug *debug = sta_->debug();
1066 const Network *network = sta_->network();
1067 const Network *sdc_network = sta_->sdcNetwork();
1068 const Graph *graph = sta_->graph();
1069 const Sdc *sdc = sta_->sdc();
1070 Search *search = sta_->search();
1071 debugPrint(debug, "search", 2, "find arrivals %s",
1072 vertex->name(sdc_network));
1073 Pin *pin = vertex->pin();
1074 // Don't clobber clock sources.
1075 if (!sdc->isLeafPinClock(pin)
1076 // Unless it is an internal path delay endpoint.
1077 || sdc->isPathDelayInternalEndpoint(pin)) {
1078 tag_bldr_->init(vertex);
1079 has_fanin_one_ = graph->hasFaninOne(vertex);
1080 if (crpr_active_
1081 && !has_fanin_one_)
1082 tag_bldr_no_crpr_->init(vertex);
1083
1084 visitFaninPaths(vertex);
1085 if (crpr_active_
1086 && search->crprPathPruningEnabled()
1087 && !vertex->crprPathPruningDisabled()
1088 && !has_fanin_one_)
1089 pruneCrprArrivals();
1090
1091 // Insert paths that originate here but
1092 if (!network->isTopLevelPort(pin)
1093 && sdc->hasInputDelay(pin))
1094 // set_input_delay on internal pin.
1095 search->seedInputSegmentArrival(pin, vertex, tag_bldr_);
1096 if (sdc->isPathDelayInternalStartpoint(pin))
1097 // set_min/max_delay on internal pin.
1098 search->makeUnclkedPaths(vertex, true, tag_bldr_);
1099 if (sdc->isPathDelayInternalEndpoint(pin)
1100 && sdc->isLeafPinClock(pin))
1101 // set_min/max_delay on internal pin also a clock src. Bizzaroland.
1102 // Re-seed the clock arrivals on top of the propagated paths.
1103 search->seedClkArrivals(pin, vertex, tag_bldr_);
1104 // Register/latch clock pin that is not connected to a declared clock.
1105 // Seed with unclocked tag, zero arrival and allow search thru reg
1106 // clk->q edges.
1107 // These paths are required to report path delays from unclocked registers
1108 // For example, "set_max_delay -to" from an unclocked source register.
1109 bool is_clk = tag_bldr_->hasClkTag();
1110 if (vertex->isRegClk() && !is_clk) {
1111 debugPrint(debug, "search", 2, "arrival seed unclked reg clk %s",
1112 network->pathName(pin));
1113 search->makeUnclkedPaths(vertex, true, tag_bldr_);
1114 }
1115
1116 bool arrivals_changed = search->arrivalsChanged(vertex, tag_bldr_);
1117 // If vertex is a latch data input arrival that changed from the
1118 // previous eval pass enqueue the latch outputs to be re-evaled on the
1119 // next pass.
1120 if (network->isLatchData(pin)) {
1121 if (arrivals_changed
1122 && network->isLatchData(pin))
1123 search->enqueueLatchDataOutputs(vertex);
1124 }
1125 if ((!search->arrivalsAtEndpointsExist()
1126 || always_to_endpoints_
1127 || arrivals_changed)
1128 && (network->isRegClkPin(pin)
1129 || !sdc->isPathDelayInternalEndpoint(pin)))
1130 search->arrivalIterator()->enqueueAdjacentVertices(vertex, adj_pred_);
1131 if (arrivals_changed) {
1132 debugPrint(debug, "search", 4, "arrival changed");
1133 // Only update arrivals when delays change by more than
1134 // fuzzyEqual can distinguish.
1135 search->setVertexArrivals(vertex, tag_bldr_);
1136 search->tnsInvalid(vertex);
1137 constrainedRequiredsInvalid(vertex, is_clk);
1138 }
1139 enqueueRefPinInputDelays(pin);
1140 }
1141 }
1142
1143 // When a clock arrival changes, the required time changes for any
1144 // timing checks, data checks or gated clock enables constrained
1145 // by the clock pin.
1146 void
constrainedRequiredsInvalid(Vertex * vertex,bool is_clk)1147 ArrivalVisitor::constrainedRequiredsInvalid(Vertex *vertex,
1148 bool is_clk)
1149 {
1150 Search *search = sta_->search();
1151 Pin *pin = vertex->pin();
1152 const Network *network = sta_->network();
1153 if (network->isLoad(pin)
1154 && search->requiredsExist()) {
1155 const Graph *graph = sta_->graph();
1156 const Sdc *sdc = sta_->sdc();
1157 if (is_clk && network->isCheckClk(pin)) {
1158 VertexOutEdgeIterator edge_iter(vertex, graph);
1159 while (edge_iter.hasNext()) {
1160 Edge *edge = edge_iter.next();
1161 if (edge->role()->isTimingCheck()) {
1162 Vertex *to_vertex = edge->to(graph);
1163 search->requiredInvalid(to_vertex);
1164 }
1165 }
1166 }
1167 // Data checks (vertex does not need to be a clk).
1168 DataCheckSet *data_checks = sdc->dataChecksFrom(pin);
1169 if (data_checks) {
1170 for (DataCheck *data_check : *data_checks) {
1171 Pin *to = data_check->to();
1172 search->requiredInvalid(to);
1173 }
1174 }
1175 // Gated clocks.
1176 if (is_clk && sdc->gatedClkChecksEnabled()) {
1177 PinSet enable_pins;
1178 search->gatedClk()->gatedClkEnables(vertex, enable_pins);
1179 for (Pin *enable : enable_pins)
1180 search->requiredInvalid(enable);
1181 }
1182 }
1183 }
1184
1185 bool
arrivalsChanged(Vertex * vertex,TagGroupBldr * tag_bldr)1186 Search::arrivalsChanged(Vertex *vertex,
1187 TagGroupBldr *tag_bldr)
1188 {
1189 Arrival *arrivals1 = graph_->arrivals(vertex);
1190 if (arrivals1) {
1191 TagGroup *tag_group = tagGroup(vertex);
1192 if (tag_group->arrivalMap()->size() != tag_bldr->arrivalMap()->size())
1193 return true;
1194 ArrivalMap::Iterator arrival_iter1(tag_group->arrivalMap());
1195 while (arrival_iter1.hasNext()) {
1196 Tag *tag1;
1197 int arrival_index1;
1198 arrival_iter1.next(tag1, arrival_index1);
1199 Arrival &arrival1 = arrivals1[arrival_index1];
1200 Arrival arrival2;
1201 bool arrival_exists2;
1202 tag_bldr->tagArrival(tag1, arrival2, arrival_exists2);
1203 if (!arrival_exists2
1204 || !delayEqual(arrival1, arrival2))
1205 return true;
1206 }
1207 return false;
1208 }
1209 else
1210 return true;
1211 }
1212
1213 bool
visitFromToPath(const Pin *,Vertex * from_vertex,const RiseFall * from_rf,Tag * from_tag,PathVertex * from_path,Edge *,TimingArc *,ArcDelay arc_delay,Vertex *,const RiseFall * to_rf,Tag * to_tag,Arrival & to_arrival,const MinMax * min_max,const PathAnalysisPt *)1214 ArrivalVisitor::visitFromToPath(const Pin *,
1215 Vertex *from_vertex,
1216 const RiseFall *from_rf,
1217 Tag *from_tag,
1218 PathVertex *from_path,
1219 Edge *,
1220 TimingArc *,
1221 ArcDelay arc_delay,
1222 Vertex *,
1223 const RiseFall *to_rf,
1224 Tag *to_tag,
1225 Arrival &to_arrival,
1226 const MinMax *min_max,
1227 const PathAnalysisPt *)
1228 {
1229 const Debug *debug = sta_->debug();
1230 const Network *sdc_network = sta_->sdcNetwork();
1231 debugPrint(debug, "search", 3, " %s",
1232 from_vertex->name(sdc_network));
1233 debugPrint(debug, "search", 3, " %s -> %s %s",
1234 from_rf->asString(),
1235 to_rf->asString(),
1236 min_max->asString());
1237 debugPrint(debug, "search", 3, " from tag: %s",
1238 from_tag->asString(sta_));
1239 debugPrint(debug, "search", 3, " to tag : %s",
1240 to_tag->asString(sta_));
1241 ClkInfo *to_clk_info = to_tag->clkInfo();
1242 bool to_is_clk = to_tag->isClock();
1243 Arrival arrival;
1244 int arrival_index;
1245 Tag *tag_match;
1246 tag_bldr_->tagMatchArrival(to_tag, tag_match, arrival, arrival_index);
1247 if (tag_match == nullptr
1248 || delayGreater(to_arrival, arrival, min_max, sta_)) {
1249 debugPrint(debug, "search", 3, " %s + %s = %s %s %s",
1250 delayAsString(from_path->arrival(sta_), sta_),
1251 delayAsString(arc_delay, sta_),
1252 delayAsString(to_arrival, sta_),
1253 min_max == MinMax::max() ? ">" : "<",
1254 tag_match ? delayAsString(arrival, sta_) : "MIA");
1255 PathVertexRep prev_path;
1256 if (to_tag->isClock() || to_tag->isGenClkSrcPath())
1257 prev_path.init(from_path, sta_);
1258 tag_bldr_->setMatchArrival(to_tag, tag_match,
1259 to_arrival, arrival_index,
1260 &prev_path);
1261 if (crpr_active_
1262 && !has_fanin_one_
1263 && to_clk_info->hasCrprClkPin()
1264 && !to_is_clk) {
1265 tag_bldr_no_crpr_->tagMatchArrival(to_tag, tag_match,
1266 arrival, arrival_index);
1267 if (tag_match == nullptr
1268 || delayGreater(to_arrival, arrival, min_max, sta_)) {
1269 tag_bldr_no_crpr_->setMatchArrival(to_tag, tag_match,
1270 to_arrival, arrival_index,
1271 &prev_path);
1272 }
1273 }
1274 }
1275 return true;
1276 }
1277
1278 void
pruneCrprArrivals()1279 ArrivalVisitor::pruneCrprArrivals()
1280 {
1281 const Debug *debug = sta_->debug();
1282 ArrivalMap::Iterator arrival_iter(tag_bldr_->arrivalMap());
1283 CheckCrpr *crpr = sta_->search()->checkCrpr();
1284 while (arrival_iter.hasNext()) {
1285 Tag *tag;
1286 int arrival_index;
1287 arrival_iter.next(tag, arrival_index);
1288 ClkInfo *clk_info = tag->clkInfo();
1289 if (!tag->isClock()
1290 && clk_info->hasCrprClkPin()) {
1291 PathAnalysisPt *path_ap = tag->pathAnalysisPt(sta_);
1292 const MinMax *min_max = path_ap->pathMinMax();
1293 Tag *tag_no_crpr;
1294 Arrival max_arrival;
1295 int max_arrival_index;
1296 tag_bldr_no_crpr_->tagMatchArrival(tag, tag_no_crpr,
1297 max_arrival, max_arrival_index);
1298 if (tag_no_crpr) {
1299 ClkInfo *clk_info_no_crpr = tag_no_crpr->clkInfo();
1300 Arrival max_crpr = crpr->maxCrpr(clk_info_no_crpr);
1301 Arrival max_arrival_max_crpr = (min_max == MinMax::max())
1302 ? max_arrival - max_crpr
1303 : max_arrival + max_crpr;
1304 debugPrint(debug, "search", 4, " cmp %s %s - %s = %s",
1305 tag->asString(sta_),
1306 delayAsString(max_arrival, sta_),
1307 delayAsString(max_crpr, sta_),
1308 delayAsString(max_arrival_max_crpr, sta_));
1309 Arrival arrival = tag_bldr_->arrival(arrival_index);
1310 if (delayGreater(max_arrival_max_crpr, arrival, min_max, sta_)) {
1311 debugPrint(debug, "search", 3, " pruned %s",
1312 tag->asString(sta_));
1313 tag_bldr_->deleteArrival(tag);
1314 }
1315 }
1316 }
1317 }
1318 }
1319
1320 // Enqueue pins with input delays that use ref_pin as the clock
1321 // reference pin as if there is a timing arc from the reference pin to
1322 // the input delay pin.
1323 void
enqueueRefPinInputDelays(const Pin * ref_pin)1324 ArrivalVisitor::enqueueRefPinInputDelays(const Pin *ref_pin)
1325 {
1326 const Sdc *sdc = sta_->sdc();
1327 InputDelaySet *input_delays = sdc->refPinInputDelays(ref_pin);
1328 if (input_delays) {
1329 const Graph *graph = sta_->graph();
1330 for (InputDelay *input_delay : *input_delays) {
1331 const Pin *pin = input_delay->pin();
1332 Vertex *vertex, *bidirect_drvr_vertex;
1333 graph->pinVertices(pin, vertex, bidirect_drvr_vertex);
1334 seedInputDelayArrival(pin, vertex, input_delay);
1335 if (bidirect_drvr_vertex)
1336 seedInputDelayArrival(pin, bidirect_drvr_vertex, input_delay);
1337 }
1338 }
1339 }
1340
1341 void
seedInputDelayArrival(const Pin * pin,Vertex * vertex,InputDelay * input_delay)1342 ArrivalVisitor::seedInputDelayArrival(const Pin *pin,
1343 Vertex *vertex,
1344 InputDelay *input_delay)
1345 {
1346 TagGroupBldr tag_bldr(true, sta_);
1347 Search *search = sta_->search();
1348 Network *network = sta_->network();
1349 tag_bldr.init(vertex);
1350 search->seedInputDelayArrival(pin, vertex, input_delay,
1351 !network->isTopLevelPort(pin), &tag_bldr);
1352 search->setVertexArrivals(vertex, &tag_bldr);
1353 search->arrivalIterator()->enqueueAdjacentVertices(vertex,
1354 search->searchAdj());
1355 }
1356
1357 void
enqueueLatchDataOutputs(Vertex * vertex)1358 Search::enqueueLatchDataOutputs(Vertex *vertex)
1359 {
1360 VertexOutEdgeIterator out_edge_iter(vertex, graph_);
1361 while (out_edge_iter.hasNext()) {
1362 Edge *out_edge = out_edge_iter.next();
1363 if (latches_->isLatchDtoQ(out_edge)) {
1364 Vertex *out_vertex = out_edge->to(graph_);
1365 UniqueLock lock(pending_latch_outputs_lock_);
1366 pending_latch_outputs_.insert(out_vertex);
1367 }
1368 }
1369 }
1370
1371 void
seedArrivals()1372 Search::seedArrivals()
1373 {
1374 VertexSet vertices;
1375 findClockVertices(vertices);
1376 findRootVertices(vertices);
1377 findInputDrvrVertices(vertices);
1378
1379 for (Vertex *vertex : vertices)
1380 seedArrival(vertex);
1381 }
1382
1383 void
findClockVertices(VertexSet & vertices)1384 Search::findClockVertices(VertexSet &vertices)
1385 {
1386 for (Clock *clk : sdc_->clks()) {
1387 for (Pin *pin : clk->leafPins()) {
1388 Vertex *vertex, *bidirect_drvr_vertex;
1389 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
1390 vertices.insert(vertex);
1391 if (bidirect_drvr_vertex)
1392 vertices.insert(bidirect_drvr_vertex);
1393 }
1394 }
1395 }
1396
1397 void
seedInvalidArrivals()1398 Search::seedInvalidArrivals()
1399 {
1400 for (Vertex *vertex : invalid_arrivals_)
1401 seedArrival(vertex);
1402 invalid_arrivals_.clear();
1403 }
1404
1405 void
seedArrival(Vertex * vertex)1406 Search::seedArrival(Vertex *vertex)
1407 {
1408 const Pin *pin = vertex->pin();
1409 if (sdc_->isLeafPinClock(pin)) {
1410 TagGroupBldr tag_bldr(true, this);
1411 tag_bldr.init(vertex);
1412 genclks_->copyGenClkSrcPaths(vertex, &tag_bldr);
1413 seedClkArrivals(pin, vertex, &tag_bldr);
1414 // Clock pin may also have input arrivals from other clocks.
1415 seedInputArrival(pin, vertex, &tag_bldr);
1416 setVertexArrivals(vertex, &tag_bldr);
1417 }
1418 else if (isInputArrivalSrchStart(vertex)) {
1419 TagGroupBldr tag_bldr(true, this);
1420 tag_bldr.init(vertex);
1421 seedInputArrival(pin, vertex, &tag_bldr);
1422 setVertexArrivals(vertex, &tag_bldr);
1423 if (!tag_bldr.empty())
1424 // Only search downstream if there were non-false paths from here.
1425 arrival_iter_->enqueueAdjacentVertices(vertex, search_adj_);
1426 }
1427 else if (levelize_->isRoot(vertex)) {
1428 bool is_reg_clk = vertex->isRegClk();
1429 if (is_reg_clk
1430 // Internal roots isolated by disabled pins are seeded with no clock.
1431 || (unconstrained_paths_
1432 && !network_->isTopLevelPort(pin))) {
1433 debugPrint(debug_, "search", 2, "arrival seed unclked root %s",
1434 network_->pathName(pin));
1435 TagGroupBldr tag_bldr(true, this);
1436 tag_bldr.init(vertex);
1437 if (makeUnclkedPaths(vertex, is_reg_clk, &tag_bldr))
1438 // Only search downstream if there were no false paths from here.
1439 arrival_iter_->enqueueAdjacentVertices(vertex, search_adj_);
1440 setVertexArrivals(vertex, &tag_bldr);
1441 }
1442 else {
1443 deletePaths(vertex);
1444 if (search_adj_->searchFrom(vertex))
1445 arrival_iter_->enqueueAdjacentVertices(vertex, search_adj_);
1446 }
1447 }
1448 else {
1449 debugPrint(debug_, "search", 2, "arrival enqueue %s",
1450 network_->pathName(pin));
1451 arrival_iter_->enqueue(vertex);
1452 }
1453 }
1454
1455 // Find all of the clock leaf pins.
1456 void
findClkVertexPins(PinSet & clk_pins)1457 Search::findClkVertexPins(PinSet &clk_pins)
1458 {
1459 for (Clock *clk : sdc_->clks()) {
1460 for (Pin *pin : clk->leafPins()) {
1461 clk_pins.insert(pin);
1462 }
1463 }
1464 }
1465
1466 void
seedClkArrivals(const Pin * pin,Vertex * vertex,TagGroupBldr * tag_bldr)1467 Search::seedClkArrivals(const Pin *pin,
1468 Vertex *vertex,
1469 TagGroupBldr *tag_bldr)
1470 {
1471 for (Clock *clk : *sdc_->findLeafPinClocks(pin)) {
1472 debugPrint(debug_, "search", 2, "arrival seed clk %s pin %s",
1473 clk->name(), network_->pathName(pin));
1474 for (PathAnalysisPt *path_ap : corners_->pathAnalysisPts()) {
1475 const MinMax *min_max = path_ap->pathMinMax();
1476 for (RiseFall *rf : RiseFall::range()) {
1477 ClockEdge *clk_edge = clk->edge(rf);
1478 const EarlyLate *early_late = min_max;
1479 if (clk->isGenerated()
1480 && clk->masterClk() == nullptr)
1481 seedClkDataArrival(pin, rf, clk, clk_edge, min_max, path_ap,
1482 0.0, tag_bldr);
1483 else {
1484 Arrival insertion = clockInsertion(clk, pin, rf, min_max,
1485 early_late, path_ap);
1486 seedClkArrival(pin, rf, clk, clk_edge, min_max, path_ap,
1487 insertion, tag_bldr);
1488 }
1489 }
1490 }
1491 arrival_iter_->enqueueAdjacentVertices(vertex, search_adj_);
1492 }
1493 }
1494
1495 void
seedClkArrival(const Pin * pin,const RiseFall * rf,Clock * clk,ClockEdge * clk_edge,const MinMax * min_max,const PathAnalysisPt * path_ap,Arrival insertion,TagGroupBldr * tag_bldr)1496 Search::seedClkArrival(const Pin *pin,
1497 const RiseFall *rf,
1498 Clock *clk,
1499 ClockEdge *clk_edge,
1500 const MinMax *min_max,
1501 const PathAnalysisPt *path_ap,
1502 Arrival insertion,
1503 TagGroupBldr *tag_bldr)
1504 {
1505 bool is_propagated = false;
1506 float latency = 0.0;
1507 bool latency_exists;
1508 // Check for clk pin latency.
1509 sdc_->clockLatency(clk, pin, rf, min_max,
1510 latency, latency_exists);
1511 if (!latency_exists) {
1512 // Check for clk latency (lower priority).
1513 sdc_->clockLatency(clk, rf, min_max,
1514 latency, latency_exists);
1515 if (latency_exists) {
1516 // Propagated pin overrides latency on clk.
1517 if (sdc_->isPropagatedClock(pin)) {
1518 latency = 0.0;
1519 latency_exists = false;
1520 is_propagated = true;
1521 }
1522 }
1523 else
1524 is_propagated = sdc_->isPropagatedClock(pin)
1525 || clk->isPropagated();
1526 }
1527
1528 ClockUncertainties *uncertainties = sdc_->clockUncertainties(pin);
1529 if (uncertainties == nullptr)
1530 uncertainties = clk->uncertainties();
1531 // Propagate liberty "pulse_clock" transition to transitive fanout.
1532 LibertyPort *port = network_->libertyPort(pin);
1533 RiseFall *pulse_clk_sense = (port ? port->pulseClkSense() : nullptr);
1534 ClkInfo *clk_info = findClkInfo(clk_edge, pin, is_propagated, nullptr, false,
1535 pulse_clk_sense, insertion, latency,
1536 uncertainties, path_ap, nullptr);
1537 // Only false_paths -from apply to clock tree pins.
1538 ExceptionStateSet *states = nullptr;
1539 sdc_->exceptionFromClkStates(pin,rf,clk,rf,min_max,states);
1540 Tag *tag = findTag(rf, path_ap, clk_info, true, nullptr, false, states, true);
1541 Arrival arrival(clk_edge->time() + insertion);
1542 tag_bldr->setArrival(tag, arrival, nullptr);
1543 }
1544
1545 void
seedClkDataArrival(const Pin * pin,const RiseFall * rf,Clock * clk,ClockEdge * clk_edge,const MinMax * min_max,const PathAnalysisPt * path_ap,Arrival insertion,TagGroupBldr * tag_bldr)1546 Search::seedClkDataArrival(const Pin *pin,
1547 const RiseFall *rf,
1548 Clock *clk,
1549 ClockEdge *clk_edge,
1550 const MinMax *min_max,
1551 const PathAnalysisPt *path_ap,
1552 Arrival insertion,
1553 TagGroupBldr *tag_bldr)
1554 {
1555 Tag *tag = clkDataTag(pin, clk, rf, clk_edge, insertion, min_max, path_ap);
1556 if (tag) {
1557 // Data arrivals include insertion delay.
1558 Arrival arrival(clk_edge->time() + insertion);
1559 tag_bldr->setArrival(tag, arrival, nullptr);
1560 }
1561 }
1562
1563 Tag *
clkDataTag(const Pin * pin,Clock * clk,const RiseFall * rf,ClockEdge * clk_edge,Arrival insertion,const MinMax * min_max,const PathAnalysisPt * path_ap)1564 Search::clkDataTag(const Pin *pin,
1565 Clock *clk,
1566 const RiseFall *rf,
1567 ClockEdge *clk_edge,
1568 Arrival insertion,
1569 const MinMax *min_max,
1570 const PathAnalysisPt *path_ap)
1571 {
1572 ExceptionStateSet *states = nullptr;
1573 if (sdc_->exceptionFromStates(pin, rf, clk, rf, min_max, states)) {
1574 bool is_propagated = (clk->isPropagated()
1575 || sdc_->isPropagatedClock(pin));
1576 ClkInfo *clk_info = findClkInfo(clk_edge, pin, is_propagated,
1577 insertion, path_ap);
1578 return findTag(rf, path_ap, clk_info, false, nullptr, false, states, true);
1579 }
1580 else
1581 return nullptr;
1582 }
1583
1584 ////////////////////////////////////////////////////////////////
1585
1586 bool
makeUnclkedPaths(Vertex * vertex,bool is_segment_start,TagGroupBldr * tag_bldr)1587 Search::makeUnclkedPaths(Vertex *vertex,
1588 bool is_segment_start,
1589 TagGroupBldr *tag_bldr)
1590 {
1591 bool search_from = false;
1592 const Pin *pin = vertex->pin();
1593 for (PathAnalysisPt *path_ap : corners_->pathAnalysisPts()) {
1594 const MinMax *min_max = path_ap->pathMinMax();
1595 for (RiseFall *rf : RiseFall::range()) {
1596 Tag *tag = fromUnclkedInputTag(pin, rf, min_max, path_ap,
1597 is_segment_start);
1598 if (tag) {
1599 tag_bldr->setArrival(tag, delay_zero, nullptr);
1600 search_from = true;
1601 }
1602 }
1603 }
1604 return search_from;
1605 }
1606
1607 // Find graph roots and input ports that do NOT have arrivals.
1608 void
findRootVertices(VertexSet & vertices)1609 Search::findRootVertices(VertexSet &vertices)
1610 {
1611 for (Vertex *vertex : levelize_->roots()) {
1612 const Pin *pin = vertex->pin();
1613 if (!sdc_->isLeafPinClock(pin)
1614 && !sdc_->hasInputDelay(pin)
1615 && !vertex->isConstant()) {
1616 vertices.insert(vertex);
1617 }
1618 }
1619 }
1620
1621 void
findInputDrvrVertices(VertexSet & vertices)1622 Search::findInputDrvrVertices(VertexSet &vertices)
1623 {
1624 Instance *top_inst = network_->topInstance();
1625 InstancePinIterator *pin_iter = network_->pinIterator(top_inst);
1626 while (pin_iter->hasNext()) {
1627 Pin *pin = pin_iter->next();
1628 if (network_->direction(pin)->isAnyInput())
1629 vertices.insert(graph_->pinDrvrVertex(pin));
1630 }
1631 delete pin_iter;
1632 }
1633
1634 bool
isSegmentStart(const Pin * pin)1635 Search::isSegmentStart(const Pin *pin)
1636 {
1637 return (sdc_->isPathDelayInternalStartpoint(pin)
1638 || sdc_->isInputDelayInternal(pin))
1639 && !sdc_->isLeafPinClock(pin);
1640 }
1641
1642 bool
isInputArrivalSrchStart(Vertex * vertex)1643 Search::isInputArrivalSrchStart(Vertex *vertex)
1644 {
1645 const Pin *pin = vertex->pin();
1646 PortDirection *dir = network_->direction(pin);
1647 bool is_top_level_port = network_->isTopLevelPort(pin);
1648 return (is_top_level_port
1649 && (dir->isInput()
1650 || (dir->isBidirect() && vertex->isBidirectDriver()))) ;
1651 }
1652
1653 // Seed input arrivals clocked by clks.
1654 void
seedInputArrivals(ClockSet * clks)1655 Search::seedInputArrivals(ClockSet *clks)
1656 {
1657 // Input arrivals can be on internal pins, so iterate over the pins
1658 // that have input arrivals rather than the top level input pins.
1659 for (auto iter : sdc_->inputDelayPinMap()) {
1660 const Pin *pin = iter.first;
1661 if (!sdc_->isLeafPinClock(pin)) {
1662 Vertex *vertex = graph_->pinDrvrVertex(pin);
1663 seedInputArrival(pin, vertex, clks);
1664 }
1665 }
1666 }
1667
1668 void
seedInputArrival(const Pin * pin,Vertex * vertex,ClockSet * wrt_clks)1669 Search::seedInputArrival(const Pin *pin,
1670 Vertex *vertex,
1671 ClockSet *wrt_clks)
1672 {
1673 bool has_arrival = false;
1674 // There can be multiple arrivals for a pin with wrt different clocks.
1675 TagGroupBldr tag_bldr(true, this);
1676 tag_bldr.init(vertex);
1677 InputDelaySet *input_delays = sdc_->inputDelaysLeafPin(pin);
1678 if (input_delays) {
1679 for (InputDelay *input_delay : *input_delays) {
1680 Clock *input_clk = input_delay->clock();
1681 ClockSet *pin_clks = sdc_->findLeafPinClocks(pin);
1682 if (input_clk && wrt_clks->hasKey(input_clk)
1683 // Input arrivals wrt a clock source pin is the insertion
1684 // delay (source latency), but arrivals wrt other clocks
1685 // propagate.
1686 && (pin_clks == nullptr
1687 || !pin_clks->hasKey(input_clk))) {
1688 seedInputDelayArrival(pin, vertex, input_delay, false, &tag_bldr);
1689 has_arrival = true;
1690 }
1691 }
1692 if (has_arrival)
1693 setVertexArrivals(vertex, &tag_bldr);
1694 }
1695 }
1696
1697 void
seedInputArrival(const Pin * pin,Vertex * vertex,TagGroupBldr * tag_bldr)1698 Search::seedInputArrival(const Pin *pin,
1699 Vertex *vertex,
1700 TagGroupBldr *tag_bldr)
1701 {
1702 if (sdc_->hasInputDelay(pin))
1703 seedInputArrival1(pin, vertex, false, tag_bldr);
1704 else if (!sdc_->isLeafPinClock(pin))
1705 // Seed inputs without set_input_delays.
1706 seedInputDelayArrival(pin, vertex, nullptr, false, tag_bldr);
1707 }
1708
1709 void
seedInputSegmentArrival(const Pin * pin,Vertex * vertex,TagGroupBldr * tag_bldr)1710 Search::seedInputSegmentArrival(const Pin *pin,
1711 Vertex *vertex,
1712 TagGroupBldr *tag_bldr)
1713 {
1714 seedInputArrival1(pin, vertex, true, tag_bldr);
1715 }
1716
1717 void
seedInputArrival1(const Pin * pin,Vertex * vertex,bool is_segment_start,TagGroupBldr * tag_bldr)1718 Search::seedInputArrival1(const Pin *pin,
1719 Vertex *vertex,
1720 bool is_segment_start,
1721 TagGroupBldr *tag_bldr)
1722 {
1723 // There can be multiple arrivals for a pin with wrt different clocks.
1724 InputDelaySet *input_delays = sdc_->inputDelaysLeafPin(pin);
1725 if (input_delays) {
1726 for (InputDelay *input_delay : *input_delays) {
1727 Clock *input_clk = input_delay->clock();
1728 ClockSet *pin_clks = sdc_->findLeafPinClocks(pin);
1729 // Input arrival wrt a clock source pin is the clock insertion
1730 // delay (source latency), but arrivals wrt other clocks
1731 // propagate.
1732 if (pin_clks == nullptr
1733 || !pin_clks->hasKey(input_clk))
1734 seedInputDelayArrival(pin, vertex, input_delay, is_segment_start,
1735 tag_bldr);
1736 }
1737 }
1738 }
1739
1740 void
seedInputDelayArrival(const Pin * pin,Vertex * vertex,InputDelay * input_delay,bool is_segment_start,TagGroupBldr * tag_bldr)1741 Search::seedInputDelayArrival(const Pin *pin,
1742 Vertex *vertex,
1743 InputDelay *input_delay,
1744 bool is_segment_start,
1745 TagGroupBldr *tag_bldr)
1746 {
1747 debugPrint(debug_, "search", 2,
1748 input_delay
1749 ? "arrival seed input arrival %s"
1750 : "arrival seed input %s",
1751 vertex->name(sdc_network_));
1752 ClockEdge *clk_edge = nullptr;
1753 const Pin *ref_pin = nullptr;
1754 if (input_delay) {
1755 clk_edge = input_delay->clkEdge();
1756 if (clk_edge == nullptr
1757 && sdc_->useDefaultArrivalClock())
1758 clk_edge = sdc_->defaultArrivalClockEdge();
1759 ref_pin = input_delay->refPin();
1760 }
1761 else if (sdc_->useDefaultArrivalClock())
1762 clk_edge = sdc_->defaultArrivalClockEdge();
1763 if (ref_pin) {
1764 Vertex *ref_vertex = graph_->pinLoadVertex(ref_pin);
1765 for (PathAnalysisPt *path_ap : corners_->pathAnalysisPts()) {
1766 const MinMax *min_max = path_ap->pathMinMax();
1767 RiseFall *ref_rf = input_delay->refTransition();
1768 const Clock *clk = input_delay->clock();
1769 VertexPathIterator ref_path_iter(ref_vertex, ref_rf, path_ap, this);
1770 while (ref_path_iter.hasNext()) {
1771 Path *ref_path = ref_path_iter.next();
1772 if (ref_path->isClock(this)
1773 && (clk == nullptr
1774 || ref_path->clock(this) == clk)) {
1775 float ref_arrival, ref_insertion, ref_latency;
1776 inputDelayRefPinArrival(ref_path, ref_path->clkEdge(this), min_max,
1777 ref_arrival, ref_insertion, ref_latency);
1778 seedInputDelayArrival(pin, input_delay, ref_path->clkEdge(this),
1779 ref_arrival, ref_insertion, ref_latency,
1780 is_segment_start, min_max, path_ap, tag_bldr);
1781 }
1782 }
1783 }
1784 }
1785 else {
1786 for (PathAnalysisPt *path_ap : corners_->pathAnalysisPts()) {
1787 const MinMax *min_max = path_ap->pathMinMax();
1788 float clk_arrival, clk_insertion, clk_latency;
1789 inputDelayClkArrival(input_delay, clk_edge, min_max, path_ap,
1790 clk_arrival, clk_insertion, clk_latency);
1791 seedInputDelayArrival(pin, input_delay, clk_edge,
1792 clk_arrival, clk_insertion, clk_latency,
1793 is_segment_start, min_max, path_ap, tag_bldr);
1794 }
1795 }
1796 }
1797
1798 // Input delays with -reference_pin use the clock network latency
1799 // from the clock source to the reference pin.
1800 void
inputDelayRefPinArrival(Path * ref_path,ClockEdge * clk_edge,const MinMax * min_max,float & ref_arrival,float & ref_insertion,float & ref_latency)1801 Search::inputDelayRefPinArrival(Path *ref_path,
1802 ClockEdge *clk_edge,
1803 const MinMax *min_max,
1804 // Return values.
1805 float &ref_arrival,
1806 float &ref_insertion,
1807 float &ref_latency)
1808 {
1809 Clock *clk = clk_edge->clock();
1810 if (clk->isPropagated()) {
1811 ClkInfo *clk_info = ref_path->clkInfo(this);
1812 ref_arrival = delayAsFloat(ref_path->arrival(this));
1813 ref_insertion = delayAsFloat(clk_info->insertion());
1814 ref_latency = clk_info->latency();
1815 }
1816 else {
1817 const RiseFall *clk_rf = clk_edge->transition();
1818 const EarlyLate *early_late = min_max;
1819 // Input delays from ideal clk reference pins include clock
1820 // insertion delay but not latency.
1821 ref_insertion = sdc_->clockInsertion(clk, clk_rf, min_max, early_late);
1822 ref_arrival = clk_edge->time() + ref_insertion;
1823 ref_latency = 0.0;
1824 }
1825 }
1826
1827 void
seedInputDelayArrival(const Pin * pin,InputDelay * input_delay,ClockEdge * clk_edge,float clk_arrival,float clk_insertion,float clk_latency,bool is_segment_start,const MinMax * min_max,PathAnalysisPt * path_ap,TagGroupBldr * tag_bldr)1828 Search::seedInputDelayArrival(const Pin *pin,
1829 InputDelay *input_delay,
1830 ClockEdge *clk_edge,
1831 float clk_arrival,
1832 float clk_insertion,
1833 float clk_latency,
1834 bool is_segment_start,
1835 const MinMax *min_max,
1836 PathAnalysisPt *path_ap,
1837 TagGroupBldr *tag_bldr)
1838 {
1839 for (RiseFall *rf : RiseFall::range()) {
1840 if (input_delay) {
1841 float delay;
1842 bool exists;
1843 input_delay->delays()->value(rf, min_max, delay, exists);
1844 if (exists)
1845 seedInputDelayArrival(pin, rf, clk_arrival + delay,
1846 input_delay, clk_edge,
1847 clk_insertion, clk_latency, is_segment_start,
1848 min_max, path_ap, tag_bldr);
1849 }
1850 else
1851 seedInputDelayArrival(pin, rf, 0.0, nullptr, clk_edge,
1852 clk_insertion, clk_latency, is_segment_start,
1853 min_max, path_ap, tag_bldr);
1854 }
1855 }
1856
1857 void
seedInputDelayArrival(const Pin * pin,const RiseFall * rf,float arrival,InputDelay * input_delay,ClockEdge * clk_edge,float clk_insertion,float clk_latency,bool is_segment_start,const MinMax * min_max,PathAnalysisPt * path_ap,TagGroupBldr * tag_bldr)1858 Search::seedInputDelayArrival(const Pin *pin,
1859 const RiseFall *rf,
1860 float arrival,
1861 InputDelay *input_delay,
1862 ClockEdge *clk_edge,
1863 float clk_insertion,
1864 float clk_latency,
1865 bool is_segment_start,
1866 const MinMax *min_max,
1867 PathAnalysisPt *path_ap,
1868 TagGroupBldr *tag_bldr)
1869 {
1870 Tag *tag = inputDelayTag(pin, rf, clk_edge, clk_insertion, clk_latency,
1871 input_delay, is_segment_start, min_max, path_ap);
1872 if (tag)
1873 tag_bldr->setArrival(tag, arrival, nullptr);
1874 }
1875
1876 void
inputDelayClkArrival(InputDelay * input_delay,ClockEdge * clk_edge,const MinMax * min_max,const PathAnalysisPt * path_ap,float & clk_arrival,float & clk_insertion,float & clk_latency)1877 Search::inputDelayClkArrival(InputDelay *input_delay,
1878 ClockEdge *clk_edge,
1879 const MinMax *min_max,
1880 const PathAnalysisPt *path_ap,
1881 // Return values.
1882 float &clk_arrival, float &clk_insertion,
1883 float &clk_latency)
1884 {
1885 clk_arrival = 0.0;
1886 clk_insertion = 0.0;
1887 clk_latency = 0.0;
1888 if (input_delay && clk_edge) {
1889 clk_arrival = clk_edge->time();
1890 Clock *clk = clk_edge->clock();
1891 RiseFall *clk_rf = clk_edge->transition();
1892 if (!input_delay->sourceLatencyIncluded()) {
1893 const EarlyLate *early_late = min_max;
1894 clk_insertion = delayAsFloat(clockInsertion(clk, clk->defaultPin(),
1895 clk_rf, min_max, early_late,
1896 path_ap));
1897 clk_arrival += clk_insertion;
1898 }
1899 if (!clk->isPropagated()
1900 && !input_delay->networkLatencyIncluded()) {
1901 clk_latency = sdc_->clockLatency(clk, clk_rf, min_max);
1902 clk_arrival += clk_latency;
1903 }
1904 }
1905 }
1906
1907 Tag *
inputDelayTag(const Pin * pin,const RiseFall * rf,ClockEdge * clk_edge,float clk_insertion,float clk_latency,InputDelay * input_delay,bool is_segment_start,const MinMax * min_max,const PathAnalysisPt * path_ap)1908 Search::inputDelayTag(const Pin *pin,
1909 const RiseFall *rf,
1910 ClockEdge *clk_edge,
1911 float clk_insertion,
1912 float clk_latency,
1913 InputDelay *input_delay,
1914 bool is_segment_start,
1915 const MinMax *min_max,
1916 const PathAnalysisPt *path_ap)
1917 {
1918 Clock *clk = nullptr;
1919 Pin *clk_pin = nullptr;
1920 RiseFall *clk_rf = nullptr;
1921 bool is_propagated = false;
1922 ClockUncertainties *clk_uncertainties = nullptr;
1923 if (clk_edge) {
1924 clk = clk_edge->clock();
1925 clk_rf = clk_edge->transition();
1926 clk_pin = clk->defaultPin();
1927 is_propagated = clk->isPropagated();
1928 clk_uncertainties = clk->uncertainties();
1929 }
1930
1931 ExceptionStateSet *states = nullptr;
1932 Tag *tag = nullptr;
1933 if (sdc_->exceptionFromStates(pin,rf,clk,clk_rf,min_max,states)) {
1934 ClkInfo *clk_info = findClkInfo(clk_edge, clk_pin, is_propagated, nullptr,
1935 false, nullptr, clk_insertion, clk_latency,
1936 clk_uncertainties, path_ap, nullptr);
1937 tag = findTag(rf, path_ap, clk_info, false, input_delay, is_segment_start,
1938 states, true);
1939 }
1940
1941 if (tag) {
1942 ClkInfo *clk_info = tag->clkInfo();
1943 // Check for state changes on existing tag exceptions (pending -thru pins).
1944 tag = mutateTag(tag, pin, rf, false, clk_info,
1945 pin, rf, false, false, is_segment_start, clk_info,
1946 input_delay, min_max, path_ap);
1947 }
1948 return tag;
1949 }
1950
1951 ////////////////////////////////////////////////////////////////
1952
PathVisitor(const StaState * sta)1953 PathVisitor::PathVisitor(const StaState *sta) :
1954 pred_(sta->search()->evalPred()),
1955 sta_(sta)
1956 {
1957 }
1958
PathVisitor(SearchPred * pred,const StaState * sta)1959 PathVisitor::PathVisitor(SearchPred *pred,
1960 const StaState *sta) :
1961 pred_(pred),
1962 sta_(sta)
1963 {
1964 }
1965
1966 void
visitFaninPaths(Vertex * to_vertex)1967 PathVisitor::visitFaninPaths(Vertex *to_vertex)
1968 {
1969 if (pred_->searchTo(to_vertex)) {
1970 const Graph *graph = sta_->graph();
1971 VertexInEdgeIterator edge_iter(to_vertex, graph);
1972 while (edge_iter.hasNext()) {
1973 Edge *edge = edge_iter.next();
1974 Vertex *from_vertex = edge->from(graph);
1975 const Pin *from_pin = from_vertex->pin();
1976 if (pred_->searchFrom(from_vertex)
1977 && pred_->searchThru(edge)) {
1978 const Pin *to_pin = to_vertex->pin();
1979 if (!visitEdge(from_pin, from_vertex, edge, to_pin, to_vertex))
1980 break;
1981 }
1982 }
1983 }
1984 }
1985
1986 void
visitFanoutPaths(Vertex * from_vertex)1987 PathVisitor::visitFanoutPaths(Vertex *from_vertex)
1988 {
1989 const Pin *from_pin = from_vertex->pin();
1990 if (pred_->searchFrom(from_vertex)) {
1991 const Graph *graph = sta_->graph();
1992 VertexOutEdgeIterator edge_iter(from_vertex, graph);
1993 while (edge_iter.hasNext()) {
1994 Edge *edge = edge_iter.next();
1995 Vertex *to_vertex = edge->to(graph);
1996 const Pin *to_pin = to_vertex->pin();
1997 if (pred_->searchTo(to_vertex)
1998 && pred_->searchThru(edge)) {
1999 debugPrint(sta_->debug(), "search", 3,
2000 " %s", to_vertex->name(sta_->network()));
2001 if (!visitEdge(from_pin, from_vertex, edge, to_pin, to_vertex))
2002 break;
2003 }
2004 }
2005 }
2006 }
2007
2008 bool
visitEdge(const Pin * from_pin,Vertex * from_vertex,Edge * edge,const Pin * to_pin,Vertex * to_vertex)2009 PathVisitor::visitEdge(const Pin *from_pin,
2010 Vertex *from_vertex,
2011 Edge *edge,
2012 const Pin *to_pin,
2013 Vertex *to_vertex)
2014 {
2015 Search *search = sta_->search();
2016 TagGroup *from_tag_group = search->tagGroup(from_vertex);
2017 if (from_tag_group) {
2018 TimingArcSet *arc_set = edge->timingArcSet();
2019 VertexPathIterator from_iter(from_vertex, search);
2020 while (from_iter.hasNext()) {
2021 PathVertex *from_path = from_iter.next();
2022 Tag *from_tag = from_path->tag(sta_);
2023 // Only propagate seeded paths from segment startpoint.
2024 if (!search->isSegmentStart(from_pin)
2025 || from_tag->isSegmentStart()) {
2026 PathAnalysisPt *path_ap = from_path->pathAnalysisPt(sta_);
2027 const MinMax *min_max = path_ap->pathMinMax();
2028 const RiseFall *from_rf = from_path->transition(sta_);
2029 // Do not propagate paths from a clock source unless they are
2030 // defined on the from pin.
2031 if (!search->pathPropagatedToClkSrc(from_pin, from_path)) {
2032 TimingArc *arc1, *arc2;
2033 arc_set->arcsFrom(from_rf, arc1, arc2);
2034 if (!visitArc(from_pin, from_vertex, from_rf, from_path,
2035 edge, arc1, to_pin, to_vertex,
2036 min_max, path_ap))
2037 return false;
2038 if (!visitArc(from_pin, from_vertex, from_rf, from_path,
2039 edge, arc2, to_pin, to_vertex,
2040 min_max, path_ap))
2041 return false;
2042 }
2043 }
2044 }
2045 }
2046 return true;
2047 }
2048
2049 bool
visitArc(const Pin * from_pin,Vertex * from_vertex,const RiseFall * from_rf,PathVertex * from_path,Edge * edge,TimingArc * arc,const Pin * to_pin,Vertex * to_vertex,const MinMax * min_max,PathAnalysisPt * path_ap)2050 PathVisitor::visitArc(const Pin *from_pin,
2051 Vertex *from_vertex,
2052 const RiseFall *from_rf,
2053 PathVertex *from_path,
2054 Edge *edge,
2055 TimingArc *arc,
2056 const Pin *to_pin,
2057 Vertex *to_vertex,
2058 const MinMax *min_max,
2059 PathAnalysisPt *path_ap)
2060 {
2061 if (arc) {
2062 RiseFall *to_rf = arc->toTrans()->asRiseFall();
2063 if (searchThru(from_vertex, from_rf, edge, to_vertex, to_rf))
2064 return visitFromPath(from_pin, from_vertex, from_rf, from_path,
2065 edge, arc, to_pin, to_vertex, to_rf,
2066 min_max, path_ap);
2067 }
2068 return true;
2069 }
2070
2071 bool
pathPropagatedToClkSrc(const Pin * pin,Path * path)2072 Search::pathPropagatedToClkSrc(const Pin *pin,
2073 Path *path)
2074 {
2075 const Tag *tag = path->tag(this);
2076 if (!tag->isGenClkSrcPath()
2077 // Clock source can have input arrivals from unrelated clock.
2078 && tag->inputDelay() == nullptr
2079 && sdc_->isPathDelayInternalEndpoint(pin)) {
2080 ClockSet *clks = sdc_->findLeafPinClocks(pin);
2081 return clks
2082 && !clks->hasKey(tag->clock());
2083 }
2084 else
2085 return false;
2086 }
2087
2088 bool
visitFromPath(const Pin * from_pin,Vertex * from_vertex,const RiseFall * from_rf,PathVertex * from_path,Edge * edge,TimingArc * arc,const Pin * to_pin,Vertex * to_vertex,const RiseFall * to_rf,const MinMax * min_max,const PathAnalysisPt * path_ap)2089 PathVisitor::visitFromPath(const Pin *from_pin,
2090 Vertex *from_vertex,
2091 const RiseFall *from_rf,
2092 PathVertex *from_path,
2093 Edge *edge,
2094 TimingArc *arc,
2095 const Pin *to_pin,
2096 Vertex *to_vertex,
2097 const RiseFall *to_rf,
2098 const MinMax *min_max,
2099 const PathAnalysisPt *path_ap)
2100 {
2101 Network *network = sta_->network();
2102 Sdc *sdc = sta_->sdc();
2103 Search *search = sta_->search();
2104 Latches *latches = sta_->latches();
2105 const TimingRole *role = edge->role();
2106 Tag *from_tag = from_path->tag(sta_);
2107 ClkInfo *from_clk_info = from_tag->clkInfo();
2108 Tag *to_tag = nullptr;
2109 ClockEdge *clk_edge = from_clk_info->clkEdge();
2110 Clock *clk = from_clk_info->clock();
2111 Arrival from_arrival = from_path->arrival(sta_);
2112 ArcDelay arc_delay = 0.0;
2113 Arrival to_arrival;
2114 if (from_clk_info->isGenClkSrcPath()) {
2115 if (!sdc->clkStopPropagation(clk,from_pin,from_rf,to_pin,to_rf)
2116 && (sdc->clkThruTristateEnabled()
2117 || !(role == TimingRole::tristateEnable()
2118 || role == TimingRole::tristateDisable()))) {
2119 Clock *gclk = from_tag->genClkSrcPathClk(sta_);
2120 if (gclk) {
2121 Genclks *genclks = search->genclks();
2122 VertexSet *fanins = genclks->fanins(gclk);
2123 // Note: encountering a latch d->q edge means find the
2124 // latch feedback edges, but they are referenced for
2125 // other edges in the gen clk fanout.
2126 if (role == TimingRole::latchDtoQ())
2127 genclks->findLatchFdbkEdges(gclk);
2128 EdgeSet *fdbk_edges = genclks->latchFdbkEdges(gclk);
2129 if ((role == TimingRole::combinational()
2130 || role == TimingRole::wire()
2131 || !gclk->combinational())
2132 && fanins->hasKey(to_vertex)
2133 && !(fdbk_edges && fdbk_edges->hasKey(edge))) {
2134 to_tag = search->thruClkTag(from_path, from_tag, true, edge, to_rf,
2135 min_max, path_ap);
2136 if (to_tag) {
2137 arc_delay = search->deratedDelay(from_vertex, arc, edge, true,
2138 path_ap);
2139 to_arrival = from_arrival + arc_delay;
2140 }
2141 }
2142 }
2143 else {
2144 // PLL out to feedback path.
2145 to_tag = search->thruTag(from_tag, edge, to_rf, min_max, path_ap);
2146 if (to_tag) {
2147 arc_delay = search->deratedDelay(from_vertex, arc, edge, true,
2148 path_ap);
2149 to_arrival = from_arrival + arc_delay;
2150 }
2151 }
2152 }
2153 }
2154 else if (role->genericRole() == TimingRole::regClkToQ()) {
2155 if (clk == nullptr
2156 || !sdc->clkStopPropagation(from_pin, clk)) {
2157 arc_delay = search->deratedDelay(from_vertex, arc, edge, false, path_ap);
2158 // Propagate from unclocked reg/latch clk pins, which have no
2159 // clk but are distinguished with a segment_start flag.
2160 if ((clk_edge == nullptr
2161 && from_tag->isSegmentStart())
2162 // Do not propagate paths from input ports with default
2163 // input arrival clk thru CLK->Q edges.
2164 || (clk != sdc->defaultArrivalClock()
2165 // Only propagate paths from clocks that have not
2166 // passed thru reg/latch D->Q edges.
2167 && from_tag->isClock())) {
2168 const RiseFall *clk_rf = clk_edge ? clk_edge->transition() : nullptr;
2169 ClkInfo *to_clk_info = from_clk_info;
2170 if (network->direction(to_pin)->isInternal())
2171 to_clk_info = search->clkInfoWithCrprClkPath(from_clk_info,
2172 from_path, path_ap);
2173 to_tag = search->fromRegClkTag(from_pin, from_rf, clk, clk_rf,
2174 to_clk_info, to_pin, to_rf, min_max,
2175 path_ap);
2176 if (to_tag)
2177 to_tag = search->thruTag(to_tag, edge, to_rf, min_max, path_ap);
2178 from_arrival = search->clkPathArrival(from_path, from_clk_info,
2179 clk_edge, min_max, path_ap);
2180 to_arrival = from_arrival + arc_delay;
2181 }
2182 else
2183 to_tag = nullptr;
2184 }
2185 }
2186 else if (edge->role() == TimingRole::latchDtoQ()) {
2187 if (min_max == MinMax::max()) {
2188 arc_delay = search->deratedDelay(from_vertex, arc, edge, false, path_ap);
2189 latches->latchOutArrival(from_path, arc, edge, path_ap,
2190 to_tag, arc_delay, to_arrival);
2191 if (to_tag)
2192 to_tag = search->thruTag(to_tag, edge, to_rf, min_max, path_ap);
2193 }
2194 }
2195 else if (from_tag->isClock()) {
2196 // Disable edges from hierarchical clock source pins that do
2197 // not go thru the hierarchical pin and edges from clock source pins
2198 // that traverse a hierarchical source pin of a different clock.
2199 // Clock arrivals used as data also need to be disabled.
2200 if (!(role == TimingRole::wire()
2201 && sdc->clkDisabledByHpinThru(clk, from_pin, to_pin))) {
2202 // Propagate arrival as non-clock at the end of the clock tree.
2203 bool to_propagates_clk =
2204 !sdc->clkStopPropagation(clk,from_pin,from_rf,to_pin,to_rf)
2205 && (sdc->clkThruTristateEnabled()
2206 || !(role == TimingRole::tristateEnable()
2207 || role == TimingRole::tristateDisable()));
2208 arc_delay = search->deratedDelay(from_vertex, arc, edge,
2209 to_propagates_clk, path_ap);
2210 to_tag = search->thruClkTag(from_path, from_tag, to_propagates_clk,
2211 edge, to_rf, min_max, path_ap);
2212 to_arrival = from_arrival + arc_delay;
2213 }
2214 }
2215 else {
2216 arc_delay = search->deratedDelay(from_vertex, arc, edge, false, path_ap);
2217 if (!delayEqual(arc_delay, min_max->initValue())) {
2218 to_arrival = from_arrival + arc_delay;
2219 to_tag = search->thruTag(from_tag, edge, to_rf, min_max, path_ap);
2220 }
2221 }
2222 if (to_tag)
2223 return visitFromToPath(from_pin, from_vertex, from_rf, from_tag, from_path,
2224 edge, arc, arc_delay,
2225 to_vertex, to_rf, to_tag, to_arrival,
2226 min_max, path_ap);
2227 else
2228 return true;
2229 }
2230
2231 Arrival
clkPathArrival(const Path * clk_path) const2232 Search::clkPathArrival(const Path *clk_path) const
2233 {
2234 ClkInfo *clk_info = clk_path->clkInfo(this);
2235 ClockEdge *clk_edge = clk_info->clkEdge();
2236 const PathAnalysisPt *path_ap = clk_path->pathAnalysisPt(this);
2237 const MinMax *min_max = path_ap->pathMinMax();
2238 return clkPathArrival(clk_path, clk_info, clk_edge, min_max, path_ap);
2239 }
2240
2241 Arrival
clkPathArrival(const Path * clk_path,ClkInfo * clk_info,ClockEdge * clk_edge,const MinMax * min_max,const PathAnalysisPt * path_ap) const2242 Search::clkPathArrival(const Path *clk_path,
2243 ClkInfo *clk_info,
2244 ClockEdge *clk_edge,
2245 const MinMax *min_max,
2246 const PathAnalysisPt *path_ap) const
2247 {
2248 if (clk_path->vertex(this)->isRegClk()
2249 && clk_path->isClock(this)
2250 && clk_edge
2251 && !clk_info->isPropagated()) {
2252 // Ideal clock, apply ideal insertion delay and latency.
2253 const EarlyLate *early_late = min_max;
2254 return clk_edge->time()
2255 + clockInsertion(clk_edge->clock(),
2256 clk_info->clkSrc(),
2257 clk_edge->transition(),
2258 min_max, early_late, path_ap)
2259 + clk_info->latency();
2260 }
2261 else
2262 return clk_path->arrival(this);
2263 }
2264
2265 Arrival
pathClkPathArrival(const Path * path) const2266 Search::pathClkPathArrival(const Path *path) const
2267 {
2268 ClkInfo *clk_info = path->clkInfo(this);
2269 if (clk_info->isPropagated()) {
2270 PathRef src_clk_path = pathClkPathArrival1(path);
2271 if (!src_clk_path.isNull())
2272 return clkPathArrival(&src_clk_path);
2273 }
2274 // Check for input arrival clock.
2275 ClockEdge *clk_edge = path->clkEdge(this);
2276 if (clk_edge)
2277 return clk_edge->time();
2278 return 0.0;
2279 }
2280
2281 // PathExpanded::expand() and PathExpanded::clkPath().
2282 PathRef
pathClkPathArrival1(const Path * path) const2283 Search::pathClkPathArrival1(const Path *path) const
2284 {
2285 PathRef p(path);
2286 while (!p.isNull()) {
2287 PathRef prev_path;
2288 TimingArc *prev_arc;
2289 p.prevPath(this, prev_path, prev_arc);
2290
2291 if (p.isClock(this))
2292 return p;
2293 if (prev_arc) {
2294 TimingRole *prev_role = prev_arc->role();
2295 if (prev_role == TimingRole::regClkToQ()
2296 || prev_role == TimingRole::latchEnToQ()) {
2297 p.prevPath(this, prev_path, prev_arc);
2298 return prev_path;
2299 }
2300 else if (prev_role == TimingRole::latchDtoQ()) {
2301 Edge *prev_edge = p.prevEdge(prev_arc, this);
2302 PathVertex enable_path;
2303 latches_->latchEnablePath(&p, prev_edge, enable_path);
2304 return enable_path;
2305 }
2306 }
2307 p.init(prev_path);
2308 }
2309 return PathRef();
2310 }
2311
2312 ////////////////////////////////////////////////////////////////
2313
2314 // Find tag for a path starting with pin/clk_edge.
2315 // Return nullptr if a false path starts at pin/clk_edge.
2316 Tag *
fromUnclkedInputTag(const Pin * pin,const RiseFall * rf,const MinMax * min_max,const PathAnalysisPt * path_ap,bool is_segment_start)2317 Search::fromUnclkedInputTag(const Pin *pin,
2318 const RiseFall *rf,
2319 const MinMax *min_max,
2320 const PathAnalysisPt *path_ap,
2321 bool is_segment_start)
2322 {
2323 ExceptionStateSet *states = nullptr;
2324 if (sdc_->exceptionFromStates(pin, rf, nullptr, nullptr, min_max, states)) {
2325 ClkInfo *clk_info = findClkInfo(nullptr, nullptr, false, 0.0, path_ap);
2326 return findTag(rf, path_ap, clk_info, false, nullptr,
2327 is_segment_start, states, true);
2328 }
2329 else
2330 return nullptr;
2331 }
2332
2333 Tag *
fromRegClkTag(const Pin * from_pin,const RiseFall * from_rf,Clock * clk,const RiseFall * clk_rf,ClkInfo * clk_info,const Pin * to_pin,const RiseFall * to_rf,const MinMax * min_max,const PathAnalysisPt * path_ap)2334 Search::fromRegClkTag(const Pin *from_pin,
2335 const RiseFall *from_rf,
2336 Clock *clk,
2337 const RiseFall *clk_rf,
2338 ClkInfo *clk_info,
2339 const Pin *to_pin,
2340 const RiseFall *to_rf,
2341 const MinMax *min_max,
2342 const PathAnalysisPt *path_ap)
2343 {
2344 ExceptionStateSet *states = nullptr;
2345 if (sdc_->exceptionFromStates(from_pin, from_rf, clk, clk_rf,
2346 min_max, states)) {
2347 // Hack for filter -from reg/Q.
2348 sdc_->filterRegQStates(to_pin, to_rf, min_max, states);
2349 return findTag(to_rf, path_ap, clk_info, false, nullptr, false, states, true);
2350 }
2351 else
2352 return nullptr;
2353 }
2354
2355 // Insert from_path as ClkInfo crpr_clk_path.
2356 ClkInfo *
clkInfoWithCrprClkPath(ClkInfo * from_clk_info,PathVertex * from_path,const PathAnalysisPt * path_ap)2357 Search::clkInfoWithCrprClkPath(ClkInfo *from_clk_info,
2358 PathVertex *from_path,
2359 const PathAnalysisPt *path_ap)
2360 {
2361 if (sdc_->crprActive())
2362 return findClkInfo(from_clk_info->clkEdge(),
2363 from_clk_info->clkSrc(),
2364 from_clk_info->isPropagated(),
2365 from_clk_info->genClkSrc(),
2366 from_clk_info->isGenClkSrcPath(),
2367 from_clk_info->pulseClkSense(),
2368 from_clk_info->insertion(),
2369 from_clk_info->latency(),
2370 from_clk_info->uncertainties(),
2371 path_ap, from_path);
2372 else
2373 return from_clk_info;
2374 }
2375
2376 // Find tag for a path starting with from_tag going thru edge.
2377 // Return nullptr if the result tag completes a false path.
2378 Tag *
thruTag(Tag * from_tag,Edge * edge,const RiseFall * to_rf,const MinMax * min_max,const PathAnalysisPt * path_ap)2379 Search::thruTag(Tag *from_tag,
2380 Edge *edge,
2381 const RiseFall *to_rf,
2382 const MinMax *min_max,
2383 const PathAnalysisPt *path_ap)
2384 {
2385 const Pin *from_pin = edge->from(graph_)->pin();
2386 Vertex *to_vertex = edge->to(graph_);
2387 const Pin *to_pin = to_vertex->pin();
2388 const RiseFall *from_rf = from_tag->transition();
2389 ClkInfo *from_clk_info = from_tag->clkInfo();
2390 bool to_is_reg_clk = to_vertex->isRegClk();
2391 Tag *to_tag = mutateTag(from_tag, from_pin, from_rf, false, from_clk_info,
2392 to_pin, to_rf, false, to_is_reg_clk, false,
2393 // input delay is not propagated.
2394 from_clk_info, nullptr, min_max, path_ap);
2395 return to_tag;
2396 }
2397
2398 Tag *
thruClkTag(PathVertex * from_path,Tag * from_tag,bool to_propagates_clk,Edge * edge,const RiseFall * to_rf,const MinMax * min_max,const PathAnalysisPt * path_ap)2399 Search::thruClkTag(PathVertex *from_path,
2400 Tag *from_tag,
2401 bool to_propagates_clk,
2402 Edge *edge,
2403 const RiseFall *to_rf,
2404 const MinMax *min_max,
2405 const PathAnalysisPt *path_ap)
2406 {
2407 const Pin *from_pin = edge->from(graph_)->pin();
2408 Vertex *to_vertex = edge->to(graph_);
2409 const Pin *to_pin = to_vertex->pin();
2410 const RiseFall *from_rf = from_tag->transition();
2411 ClkInfo *from_clk_info = from_tag->clkInfo();
2412 bool from_is_clk = from_tag->isClock();
2413 bool to_is_reg_clk = to_vertex->isRegClk();
2414 TimingRole *role = edge->role();
2415 bool to_is_clk = (from_is_clk
2416 && to_propagates_clk
2417 && (role->isWire()
2418 || role == TimingRole::combinational()));
2419 ClkInfo *to_clk_info = thruClkInfo(from_path, from_clk_info,
2420 edge, to_vertex, to_pin, min_max, path_ap);
2421 Tag *to_tag = mutateTag(from_tag,from_pin,from_rf,from_is_clk,from_clk_info,
2422 to_pin, to_rf, to_is_clk, to_is_reg_clk, false,
2423 to_clk_info, nullptr, min_max, path_ap);
2424 return to_tag;
2425 }
2426
2427 // thruTag for clocks.
2428 ClkInfo *
thruClkInfo(PathVertex * from_path,ClkInfo * from_clk_info,Edge * edge,Vertex * to_vertex,const Pin * to_pin,const MinMax * min_max,const PathAnalysisPt * path_ap)2429 Search::thruClkInfo(PathVertex *from_path,
2430 ClkInfo *from_clk_info,
2431 Edge *edge,
2432 Vertex *to_vertex,
2433 const Pin *to_pin,
2434 const MinMax *min_max,
2435 const PathAnalysisPt *path_ap)
2436 {
2437 ClkInfo *to_clk_info = from_clk_info;
2438 bool changed = false;
2439 ClockEdge *from_clk_edge = from_clk_info->clkEdge();
2440 const RiseFall *clk_rf = from_clk_edge->transition();
2441
2442 bool from_clk_prop = from_clk_info->isPropagated();
2443 bool to_clk_prop = from_clk_prop;
2444 if (!from_clk_prop
2445 && sdc_->isPropagatedClock(to_pin)) {
2446 to_clk_prop = true;
2447 changed = true;
2448 }
2449
2450 // Distinguish gen clk src path ClkInfo at generated clock roots,
2451 // so that generated clock crpr info can be (later) safely set on
2452 // the clkinfo.
2453 const Pin *gen_clk_src = nullptr;
2454 if (from_clk_info->isGenClkSrcPath()
2455 && sdc_->crprActive()
2456 && sdc_->isClock(to_pin)) {
2457 // Don't care that it could be a regular clock root.
2458 gen_clk_src = to_pin;
2459 changed = true;
2460 }
2461
2462 PathVertex *to_crpr_clk_path = nullptr;
2463 if (sdc_->crprActive()
2464 && to_vertex->isRegClk()) {
2465 to_crpr_clk_path = from_path;
2466 changed = true;
2467 }
2468
2469 // Propagate liberty "pulse_clock" transition to transitive fanout.
2470 RiseFall *from_pulse_sense = from_clk_info->pulseClkSense();
2471 RiseFall *to_pulse_sense = from_pulse_sense;
2472 LibertyPort *port = network_->libertyPort(to_pin);
2473 if (port && port->pulseClkSense()) {
2474 to_pulse_sense = port->pulseClkSense();
2475 changed = true;
2476 }
2477 else if (from_pulse_sense &&
2478 edge->timingArcSet()->sense() == TimingSense::negative_unate) {
2479 to_pulse_sense = from_pulse_sense->opposite();
2480 changed = true;
2481 }
2482
2483 Clock *from_clk = from_clk_info->clock();
2484 Arrival to_insertion = from_clk_info->insertion();
2485 float to_latency = from_clk_info->latency();
2486 float latency;
2487 bool exists;
2488 sdc_->clockLatency(from_clk, to_pin, clk_rf, min_max,
2489 latency, exists);
2490 if (exists) {
2491 // Latency on pin has precidence over fanin or hierarchical
2492 // pin latency.
2493 to_latency = latency;
2494 to_clk_prop = false;
2495 changed = true;
2496 }
2497 else {
2498 // Check for hierarchical pin latency thru edge.
2499 sdc_->clockLatency(edge, clk_rf, min_max,
2500 latency, exists);
2501 if (exists) {
2502 to_latency = latency;
2503 to_clk_prop = false;
2504 changed = true;
2505 }
2506 }
2507
2508 ClockUncertainties *to_uncertainties = from_clk_info->uncertainties();
2509 ClockUncertainties *uncertainties = sdc_->clockUncertainties(to_pin);
2510 if (uncertainties) {
2511 to_uncertainties = uncertainties;
2512 changed = true;
2513 }
2514
2515 if (changed)
2516 to_clk_info = findClkInfo(from_clk_edge, from_clk_info->clkSrc(),
2517 to_clk_prop, gen_clk_src,
2518 from_clk_info->isGenClkSrcPath(),
2519 to_pulse_sense, to_insertion, to_latency,
2520 to_uncertainties, path_ap, to_crpr_clk_path);
2521 return to_clk_info;
2522 }
2523
2524 // Find the tag for a path going from from_tag thru edge to to_pin.
2525 Tag *
mutateTag(Tag * from_tag,const Pin * from_pin,const RiseFall * from_rf,bool from_is_clk,ClkInfo * from_clk_info,const Pin * to_pin,const RiseFall * to_rf,bool to_is_clk,bool to_is_reg_clk,bool to_is_segment_start,ClkInfo * to_clk_info,InputDelay * to_input_delay,const MinMax * min_max,const PathAnalysisPt * path_ap)2526 Search::mutateTag(Tag *from_tag,
2527 const Pin *from_pin,
2528 const RiseFall *from_rf,
2529 bool from_is_clk,
2530 ClkInfo *from_clk_info,
2531 const Pin *to_pin,
2532 const RiseFall *to_rf,
2533 bool to_is_clk,
2534 bool to_is_reg_clk,
2535 bool to_is_segment_start,
2536 ClkInfo *to_clk_info,
2537 InputDelay *to_input_delay,
2538 const MinMax *min_max,
2539 const PathAnalysisPt *path_ap)
2540 {
2541 ExceptionStateSet *new_states = nullptr;
2542 ExceptionStateSet *from_states = from_tag->states();
2543 if (from_states) {
2544 // Check for state changes in from_tag (but postpone copying state set).
2545 bool state_change = false;
2546 for (auto state : *from_states) {
2547 ExceptionPath *exception = state->exception();
2548 if (state->isComplete()
2549 && exception->isFalse()
2550 && !from_is_clk)
2551 // Don't propagate a completed false path -thru unless it is a
2552 // clock (which ignores exceptions).
2553 return nullptr;
2554 if (state->matchesNextThru(from_pin,to_pin,to_rf,min_max,network_)) {
2555 // Found a -thru that we've been waiting for.
2556 if (state->nextState()->isComplete()
2557 && exception->isLoop())
2558 // to_pin/edge completes a loop path.
2559 return nullptr;
2560 state_change = true;
2561 break;
2562 }
2563 // Kill loop tags at register clock pins.
2564 if (to_is_reg_clk && exception->isLoop()) {
2565 state_change = true;
2566 break;
2567 }
2568 }
2569 // Get the set of -thru exceptions starting at to_pin/edge.
2570 sdc_->exceptionThruStates(from_pin, to_pin, to_rf, min_max, new_states);
2571 if (new_states || state_change) {
2572 // Second pass to apply state changes and add updated existing
2573 // states to new states.
2574 if (new_states == nullptr)
2575 new_states = new ExceptionStateSet;
2576 for (auto state : *from_states) {
2577 ExceptionPath *exception = state->exception();
2578 if (state->isComplete()
2579 && exception->isFalse()
2580 && !from_is_clk) {
2581 // Don't propagate a completed false path -thru unless it is a
2582 // clock. Clocks carry the completed false path to disable
2583 // downstream paths that use the clock as data.
2584 delete new_states;
2585 return nullptr;
2586 }
2587 // One edge may traverse multiple hierarchical thru pins.
2588 while (state->matchesNextThru(from_pin,to_pin,to_rf,min_max,network_))
2589 // Found a -thru that we've been waiting for.
2590 state = state->nextState();
2591
2592 if (state->isComplete()
2593 && exception->isLoop()) {
2594 // to_pin/edge completes a loop path.
2595 delete new_states;
2596 return nullptr;
2597 }
2598
2599 // Kill loop tags at register clock pins.
2600 if (!(to_is_reg_clk
2601 && exception->isLoop()))
2602 new_states->insert(state);
2603 }
2604 }
2605 }
2606 else
2607 // Get the set of -thru exceptions starting at to_pin/edge.
2608 sdc_->exceptionThruStates(from_pin, to_pin, to_rf, min_max, new_states);
2609
2610 if (new_states)
2611 return findTag(to_rf, path_ap, to_clk_info, to_is_clk,
2612 from_tag->inputDelay(), to_is_segment_start,
2613 new_states, true);
2614 else {
2615 // No state change.
2616 if (to_clk_info == from_clk_info
2617 && to_rf == from_rf
2618 && to_is_clk == from_is_clk
2619 && from_tag->isSegmentStart() == to_is_segment_start
2620 && from_tag->inputDelay() == to_input_delay)
2621 return from_tag;
2622 else
2623 return findTag(to_rf, path_ap, to_clk_info, to_is_clk,
2624 to_input_delay, to_is_segment_start,
2625 from_states, false);
2626 }
2627 }
2628
2629 TagGroup *
findTagGroup(TagGroupBldr * tag_bldr)2630 Search::findTagGroup(TagGroupBldr *tag_bldr)
2631 {
2632 TagGroup probe(tag_bldr);
2633 TagGroup *tag_group = tag_group_set_->findKey(&probe);
2634 if (tag_group == nullptr) {
2635 // Recheck with lock.
2636 UniqueLock lock(tag_group_lock_);
2637 tag_group = tag_group_set_->findKey(&probe);
2638 if (tag_group == nullptr) {
2639 TagGroupIndex tag_group_index;
2640 if (tag_group_free_indices_.empty())
2641 tag_group_index = tag_group_next_++;
2642 else {
2643 tag_group_index = tag_group_free_indices_.back();
2644 tag_group_free_indices_.pop_back();
2645 }
2646 tag_group = tag_bldr->makeTagGroup(tag_group_index, this);
2647 tag_groups_[tag_group_index] = tag_group;
2648 tag_group_set_->insert(tag_group);
2649 // If tag_groups_ needs to grow make the new array and copy the
2650 // contents into it before updating tags_groups_ so that other threads
2651 // can use Search::tagGroup(TagGroupIndex) without returning gubbish.
2652 // std::vector doesn't seem to follow this protocol so multi-thread
2653 // search fails occasionally if a vector is used for tag_groups_.
2654 if (tag_group_next_ == tag_group_capacity_) {
2655 TagGroupIndex new_capacity = nextMersenne(tag_group_capacity_);
2656 TagGroup **new_tag_groups = new TagGroup*[new_capacity];
2657 memcpy(new_tag_groups, tag_groups_,
2658 tag_group_capacity_ * sizeof(TagGroup*));
2659 TagGroup **old_tag_groups = tag_groups_;
2660 tag_groups_ = new_tag_groups;
2661 tag_group_capacity_ = new_capacity;
2662 delete [] old_tag_groups;
2663 tag_group_set_->reserve(new_capacity);
2664 }
2665 if (tag_group_next_ > tag_group_index_max)
2666 report_->critical(260, "max tag group index exceeded");
2667 }
2668 }
2669 return tag_group;
2670 }
2671
2672 void
setVertexArrivals(Vertex * vertex,TagGroupBldr * tag_bldr)2673 Search::setVertexArrivals(Vertex *vertex,
2674 TagGroupBldr *tag_bldr)
2675 {
2676 if (tag_bldr->empty())
2677 deletePaths(vertex);
2678 else {
2679 TagGroup *prev_tag_group = tagGroup(vertex);
2680 Arrival *prev_arrivals = graph_->arrivals(vertex);
2681 PathVertexRep *prev_paths = graph_->prevPaths(vertex);
2682
2683 TagGroup *tag_group = findTagGroup(tag_bldr);
2684 int arrival_count = tag_group->arrivalCount();
2685 bool has_requireds = vertex->hasRequireds();
2686 // Reuse arrival array if it is the same size.
2687 if (prev_tag_group
2688 && arrival_count == prev_tag_group->arrivalCount()
2689 && (!has_requireds
2690 // Requireds can only be reused if the tag group is unchanged.
2691 || tag_group == prev_tag_group)) {
2692 if (tag_bldr->hasClkTag() || tag_bldr->hasGenClkSrcTag()) {
2693 if (prev_paths == nullptr)
2694 prev_paths = graph_->makePrevPaths(vertex, arrival_count);
2695 }
2696 else {
2697 // Prev paths not required.
2698 prev_paths = nullptr;
2699 vertex->setPrevPaths(prev_path_null);
2700 }
2701 tag_bldr->copyArrivals(tag_group, prev_arrivals, prev_paths);
2702 vertex->setTagGroupIndex(tag_group->index());
2703 }
2704 else {
2705 Arrival *arrivals = graph_->makeArrivals(vertex, arrival_count);
2706 prev_paths = nullptr;
2707 if (tag_bldr->hasClkTag() || tag_bldr->hasGenClkSrcTag())
2708 prev_paths = graph_->makePrevPaths(vertex, arrival_count);
2709 tag_bldr->copyArrivals(tag_group, arrivals, prev_paths);
2710
2711 vertex->setTagGroupIndex(tag_group->index());
2712
2713 if (has_requireds) {
2714 requiredInvalid(vertex);
2715 vertex->setHasRequireds(false);
2716 }
2717 }
2718 }
2719 }
2720
2721 void
reportArrivals(Vertex * vertex) const2722 Search::reportArrivals(Vertex *vertex) const
2723 {
2724 report_->reportLine("Vertex %s", vertex->name(sdc_network_));
2725 TagGroup *tag_group = tagGroup(vertex);
2726 Arrival *arrivals = graph_->arrivals(vertex);
2727 if (tag_group) {
2728 report_->reportLine("Group %u", tag_group->index());
2729 ArrivalMap::Iterator arrival_iter(tag_group->arrivalMap());
2730 while (arrival_iter.hasNext()) {
2731 Tag *tag;
2732 int arrival_index;
2733 arrival_iter.next(tag, arrival_index);
2734 PathAnalysisPt *path_ap = tag->pathAnalysisPt(this);
2735 const RiseFall *rf = tag->transition();
2736 const char *req = "?";
2737 if (vertex->hasRequireds()) {
2738 int req_index;
2739 bool exists;
2740 tag_group->requiredIndex(tag, req_index, exists);
2741 if (exists)
2742 req = delayAsString(arrivals[req_index], this);
2743 }
2744 bool report_clk_prev = false;
2745 const char *clk_prev = "";
2746 if (report_clk_prev
2747 && tag_group->hasClkTag()) {
2748 PathVertex prev = check_crpr_->clkPathPrev(vertex, arrival_index);
2749 if (!prev.isNull())
2750 clk_prev = prev.name(this);
2751 }
2752 report_->reportLine(" %d %s %s %s / %s %s %s",
2753 arrival_index,
2754 rf->asString(),
2755 path_ap->pathMinMax()->asString(),
2756 delayAsString(arrivals[arrival_index], this),
2757 req,
2758 tag->asString(true, false, this),
2759 clk_prev);
2760 }
2761 }
2762 else
2763 report_->reportLine(" no arrivals");
2764 }
2765
2766 TagGroup *
tagGroup(TagGroupIndex index) const2767 Search::tagGroup(TagGroupIndex index) const
2768 {
2769 return tag_groups_[index];
2770 }
2771
2772 TagGroup *
tagGroup(const Vertex * vertex) const2773 Search::tagGroup(const Vertex *vertex) const
2774 {
2775 TagGroupIndex index = vertex->tagGroupIndex();
2776 if (index == tag_group_index_max)
2777 return nullptr;
2778 else
2779 return tag_groups_[index];
2780 }
2781
2782 TagGroupIndex
tagGroupCount() const2783 Search::tagGroupCount() const
2784 {
2785 return tag_group_set_->size();
2786 }
2787
2788 void
reportTagGroups() const2789 Search::reportTagGroups() const
2790 {
2791 for (TagGroupIndex i = 0; i < tag_group_next_; i++) {
2792 TagGroup *tag_group = tag_groups_[i];
2793 if (tag_group) {
2794 report_->reportLine("Group %4u hash = %4lu (%4lu)",
2795 i,
2796 tag_group->hash(),
2797 tag_group->hash() % tag_group_set_->capacity());
2798 tag_group->reportArrivalMap(this);
2799 }
2800 }
2801 size_t long_hash = tag_group_set_->longestBucketHash();
2802 report_->reportLine("Longest hash bucket length %d hash=%lu",
2803 tag_group_set_->bucketLength(long_hash),
2804 long_hash);
2805 }
2806
2807 void
reportArrivalCountHistogram() const2808 Search::reportArrivalCountHistogram() const
2809 {
2810 Vector<int> vertex_counts(10);
2811 VertexIterator vertex_iter(graph_);
2812 while (vertex_iter.hasNext()) {
2813 Vertex *vertex = vertex_iter.next();
2814 TagGroup *tag_group = tagGroup(vertex);
2815 if (tag_group) {
2816 size_t arrival_count = tag_group->arrivalCount();
2817 if (arrival_count >= vertex_counts.size())
2818 vertex_counts.resize(arrival_count * 2);
2819 vertex_counts[arrival_count]++;
2820 }
2821 }
2822
2823 for (size_t arrival_count = 0; arrival_count < vertex_counts.size(); arrival_count++) {
2824 int vertex_count = vertex_counts[arrival_count];
2825 if (vertex_count > 0)
2826 report_->reportLine("%6lu %6d", arrival_count, vertex_count);
2827 }
2828 }
2829
2830 ////////////////////////////////////////////////////////////////
2831
2832 Tag *
tag(TagIndex index) const2833 Search::tag(TagIndex index) const
2834 {
2835 return tags_[index];
2836 }
2837
2838 TagIndex
tagCount() const2839 Search::tagCount() const
2840 {
2841 return tag_set_->size();
2842 }
2843
2844 Tag *
findTag(const RiseFall * rf,const PathAnalysisPt * path_ap,ClkInfo * clk_info,bool is_clk,InputDelay * input_delay,bool is_segment_start,ExceptionStateSet * states,bool own_states)2845 Search::findTag(const RiseFall *rf,
2846 const PathAnalysisPt *path_ap,
2847 ClkInfo *clk_info,
2848 bool is_clk,
2849 InputDelay *input_delay,
2850 bool is_segment_start,
2851 ExceptionStateSet *states,
2852 bool own_states)
2853 {
2854 Tag probe(0, rf->index(), path_ap->index(), clk_info, is_clk, input_delay,
2855 is_segment_start, states, false, this);
2856 Tag *tag = tag_set_->findKey(&probe);
2857 if (tag == nullptr) {
2858 // Recheck with lock.
2859 UniqueLock lock(tag_lock_);
2860 tag = tag_set_->findKey(&probe);
2861 if (tag == nullptr) {
2862 ExceptionStateSet *new_states = !own_states && states
2863 ? new ExceptionStateSet(*states) : states;
2864 TagIndex tag_index;
2865 if (tag_free_indices_.empty())
2866 tag_index = tag_next_++;
2867 else {
2868 tag_index = tag_free_indices_.back();
2869 tag_free_indices_.pop_back();
2870 }
2871 tag = new Tag(tag_index, rf->index(), path_ap->index(),
2872 clk_info, is_clk, input_delay, is_segment_start,
2873 new_states, true, this);
2874 own_states = false;
2875 // Make sure tag can be indexed in tags_ before it is visible to
2876 // other threads via tag_set_.
2877 tags_[tag_index] = tag;
2878 tag_set_->insert(tag);
2879 // If tags_ needs to grow make the new array and copy the
2880 // contents into it before updating tags_ so that other threads
2881 // can use Search::tag(TagIndex) without returning gubbish.
2882 // std::vector doesn't seem to follow this protocol so multi-thread
2883 // search fails occasionally if a vector is used for tags_.
2884 if (tag_next_ == tag_capacity_) {
2885 TagIndex new_capacity = nextMersenne(tag_capacity_);
2886 Tag **new_tags = new Tag*[new_capacity];
2887 memcpy(new_tags, tags_, tag_capacity_ * sizeof(Tag*));
2888 Tag **old_tags = tags_;
2889 tags_ = new_tags;
2890 delete [] old_tags;
2891 tag_capacity_ = new_capacity;
2892 tag_set_->reserve(new_capacity);
2893 }
2894 if (tag_next_ > tag_index_max)
2895 report_->critical(261, "max tag index exceeded");
2896 }
2897 }
2898 if (own_states)
2899 delete states;
2900 return tag;
2901 }
2902
2903 void
reportTags() const2904 Search::reportTags() const
2905 {
2906 for (TagIndex i = 0; i < tag_next_; i++) {
2907 Tag *tag = tags_[i];
2908 if (tag)
2909 report_->reportLine("%s", tag->asString(this)) ;
2910 }
2911 size_t long_hash = tag_set_->longestBucketHash();
2912 report_->reportLine("Longest hash bucket length %d hash=%zu",
2913 tag_set_->bucketLength(long_hash),
2914 long_hash);
2915 }
2916
2917 void
reportClkInfos() const2918 Search::reportClkInfos() const
2919 {
2920 Vector<ClkInfo*> clk_infos;
2921 // set -> vector for sorting.
2922 for (ClkInfo *clk_info : *clk_info_set_)
2923 clk_infos.push_back(clk_info);
2924 sort(clk_infos, ClkInfoLess(this));
2925 for (ClkInfo *clk_info : clk_infos)
2926 report_->reportLine("ClkInfo %s", clk_info->asString(this));
2927 report_->reportLine("%lu clk infos", clk_info_set_->size());
2928 }
2929
2930 ClkInfo *
findClkInfo(ClockEdge * clk_edge,const Pin * clk_src,bool is_propagated,const Pin * gen_clk_src,bool gen_clk_src_path,const RiseFall * pulse_clk_sense,Arrival insertion,float latency,ClockUncertainties * uncertainties,const PathAnalysisPt * path_ap,PathVertex * crpr_clk_path)2931 Search::findClkInfo(ClockEdge *clk_edge,
2932 const Pin *clk_src,
2933 bool is_propagated,
2934 const Pin *gen_clk_src,
2935 bool gen_clk_src_path,
2936 const RiseFall *pulse_clk_sense,
2937 Arrival insertion,
2938 float latency,
2939 ClockUncertainties *uncertainties,
2940 const PathAnalysisPt *path_ap,
2941 PathVertex *crpr_clk_path)
2942 {
2943 PathVertexRep crpr_clk_path_rep(crpr_clk_path, this);
2944 ClkInfo probe(clk_edge, clk_src, is_propagated, gen_clk_src, gen_clk_src_path,
2945 pulse_clk_sense, insertion, latency, uncertainties,
2946 path_ap->index(), crpr_clk_path_rep, this);
2947 UniqueLock lock(clk_info_lock_);
2948 ClkInfo *clk_info = clk_info_set_->findKey(&probe);
2949 if (clk_info == nullptr) {
2950 clk_info = new ClkInfo(clk_edge, clk_src,
2951 is_propagated, gen_clk_src, gen_clk_src_path,
2952 pulse_clk_sense, insertion, latency, uncertainties,
2953 path_ap->index(), crpr_clk_path_rep, this);
2954 clk_info_set_->insert(clk_info);
2955 }
2956 return clk_info;
2957 }
2958
2959 ClkInfo *
findClkInfo(ClockEdge * clk_edge,const Pin * clk_src,bool is_propagated,Arrival insertion,const PathAnalysisPt * path_ap)2960 Search::findClkInfo(ClockEdge *clk_edge,
2961 const Pin *clk_src,
2962 bool is_propagated,
2963 Arrival insertion,
2964 const PathAnalysisPt *path_ap)
2965 {
2966 return findClkInfo(clk_edge, clk_src, is_propagated, nullptr, false, nullptr,
2967 insertion, 0.0, nullptr, path_ap, nullptr);
2968 }
2969
2970 int
clkInfoCount() const2971 Search::clkInfoCount() const
2972 {
2973 return clk_info_set_->size();
2974 }
2975
2976 ArcDelay
deratedDelay(Vertex * from_vertex,TimingArc * arc,Edge * edge,bool is_clk,const PathAnalysisPt * path_ap)2977 Search::deratedDelay(Vertex *from_vertex,
2978 TimingArc *arc,
2979 Edge *edge,
2980 bool is_clk,
2981 const PathAnalysisPt *path_ap)
2982 {
2983 const DcalcAnalysisPt *dcalc_ap = path_ap->dcalcAnalysisPt();
2984 DcalcAPIndex ap_index = dcalc_ap->index();
2985 float derate = timingDerate(from_vertex, arc, edge, is_clk, path_ap);
2986 ArcDelay delay = graph_->arcDelay(edge, arc, ap_index);
2987 return delay * derate;
2988 }
2989
2990 float
timingDerate(Vertex * from_vertex,TimingArc * arc,Edge * edge,bool is_clk,const PathAnalysisPt * path_ap)2991 Search::timingDerate(Vertex *from_vertex,
2992 TimingArc *arc,
2993 Edge *edge,
2994 bool is_clk,
2995 const PathAnalysisPt *path_ap)
2996 {
2997 PathClkOrData derate_clk_data =
2998 is_clk ? PathClkOrData::clk : PathClkOrData::data;
2999 TimingRole *role = edge->role();
3000 const Pin *pin = from_vertex->pin();
3001 if (role->isWire()) {
3002 const RiseFall *rf = arc->toTrans()->asRiseFall();
3003 return sdc_->timingDerateNet(pin, derate_clk_data, rf,
3004 path_ap->pathMinMax());
3005 }
3006 else {
3007 TimingDerateType derate_type;
3008 const RiseFall *rf;
3009 if (role->isTimingCheck()) {
3010 derate_type = TimingDerateType::cell_check;
3011 rf = arc->toTrans()->asRiseFall();
3012 }
3013 else {
3014 derate_type = TimingDerateType::cell_delay;
3015 rf = arc->fromTrans()->asRiseFall();
3016 }
3017 return sdc_->timingDerateInstance(pin, derate_type, derate_clk_data, rf,
3018 path_ap->pathMinMax());
3019 }
3020 }
3021
3022 void
clocks(const Vertex * vertex,ClockSet & clks) const3023 Search::clocks(const Vertex *vertex,
3024 // Return value.
3025 ClockSet &clks) const
3026 {
3027 VertexPathIterator path_iter(const_cast<Vertex*>(vertex), this);
3028 while (path_iter.hasNext()) {
3029 Path *path = path_iter.next();
3030 if (path->isClock(this))
3031 clks.insert(path->clock(this));
3032 }
3033 }
3034
3035 bool
isClock(const Vertex * vertex) const3036 Search::isClock(const Vertex *vertex) const
3037 {
3038 TagGroup *tag_group = tagGroup(vertex);
3039 if (tag_group)
3040 return tag_group->hasClkTag();
3041 else
3042 return false;
3043 }
3044
3045 bool
isGenClkSrc(const Vertex * vertex) const3046 Search::isGenClkSrc(const Vertex *vertex) const
3047 {
3048 TagGroup *tag_group = tagGroup(vertex);
3049 if (tag_group)
3050 return tag_group->hasGenClkSrcTag();
3051 else
3052 return false;
3053 }
3054
3055 void
clocks(const Pin * pin,ClockSet & clks) const3056 Search::clocks(const Pin *pin,
3057 // Return value.
3058 ClockSet &clks) const
3059 {
3060 Vertex *vertex;
3061 Vertex *bidirect_drvr_vertex;
3062 graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
3063 if (vertex)
3064 clocks(vertex, clks);
3065 if (bidirect_drvr_vertex)
3066 clocks(bidirect_drvr_vertex, clks);
3067 }
3068
3069 ////////////////////////////////////////////////////////////////
3070
3071 void
findRequireds()3072 Search::findRequireds()
3073 {
3074 findRequireds(0);
3075 }
3076
3077 void
findRequireds(Level level)3078 Search::findRequireds(Level level)
3079 {
3080 Stats stats(debug_, report_);
3081 debugPrint(debug_, "search", 1, "find requireds to level %d", level);
3082 RequiredVisitor req_visitor(this);
3083 if (!requireds_seeded_)
3084 seedRequireds();
3085 seedInvalidRequireds();
3086 int required_count = required_iter_->visitParallel(level, &req_visitor);
3087 requireds_exist_ = true;
3088 debugPrint(debug_, "search", 1, "found %d requireds", required_count);
3089 stats.report("Find requireds");
3090 }
3091
3092 void
seedRequireds()3093 Search::seedRequireds()
3094 {
3095 ensureDownstreamClkPins();
3096 for (Vertex *vertex : *endpoints())
3097 seedRequired(vertex);
3098 requireds_seeded_ = true;
3099 requireds_exist_ = true;
3100 }
3101
3102 VertexSet *
endpoints()3103 Search::endpoints()
3104 {
3105 if (endpoints_ == nullptr) {
3106 endpoints_ = new VertexSet;
3107 invalid_endpoints_ = new VertexSet;
3108 VertexIterator vertex_iter(graph_);
3109 while (vertex_iter.hasNext()) {
3110 Vertex *vertex = vertex_iter.next();
3111 if (isEndpoint(vertex)) {
3112 debugPrint(debug_, "endpoint", 2, "insert %s",
3113 vertex->name(sdc_network_));
3114 endpoints_->insert(vertex);
3115 }
3116 }
3117 }
3118 if (invalid_endpoints_) {
3119 for (Vertex *vertex : *invalid_endpoints_) {
3120 if (isEndpoint(vertex)) {
3121 debugPrint(debug_, "endpoint", 2, "insert %s",
3122 vertex->name(sdc_network_));
3123 endpoints_->insert(vertex);
3124 }
3125 else {
3126 if (debug_->check("endpoint", 2)
3127 && endpoints_->hasKey(vertex))
3128 report_->reportLine("endpoint: remove %s",
3129 vertex->name(sdc_network_));
3130 endpoints_->erase(vertex);
3131 }
3132 }
3133 invalid_endpoints_->clear();
3134 }
3135 return endpoints_;
3136 }
3137
3138 void
endpointInvalid(Vertex * vertex)3139 Search::endpointInvalid(Vertex *vertex)
3140 {
3141 if (invalid_endpoints_) {
3142 debugPrint(debug_, "endpoint", 2, "invalid %s",
3143 vertex->name(sdc_network_));
3144 invalid_endpoints_->insert(vertex);
3145 }
3146 }
3147
3148 bool
isEndpoint(Vertex * vertex) const3149 Search::isEndpoint(Vertex *vertex) const
3150 {
3151 return isEndpoint(vertex, search_adj_);
3152 }
3153
3154 bool
isEndpoint(Vertex * vertex,SearchPred * pred) const3155 Search::isEndpoint(Vertex *vertex,
3156 SearchPred *pred) const
3157 {
3158 Pin *pin = vertex->pin();
3159 return hasFanin(vertex, pred, graph_)
3160 && ((vertex->hasChecks()
3161 && hasEnabledChecks(vertex))
3162 || (sdc_->gatedClkChecksEnabled()
3163 && gated_clk_->isGatedClkEnable(vertex))
3164 || vertex->isConstrained()
3165 || sdc_->isPathDelayInternalEndpoint(pin)
3166 || !hasFanout(vertex, pred, graph_)
3167 // Unconstrained paths at register clk pins.
3168 || (unconstrained_paths_
3169 && vertex->isRegClk()));
3170 }
3171
3172 bool
hasEnabledChecks(Vertex * vertex) const3173 Search::hasEnabledChecks(Vertex *vertex) const
3174 {
3175 VertexInEdgeIterator edge_iter(vertex, graph_);
3176 while (edge_iter.hasNext()) {
3177 Edge *edge = edge_iter.next();
3178 if (visit_path_ends_->checkEdgeEnabled(edge))
3179 return true;
3180 }
3181 return false;
3182 }
3183
3184 void
endpointsInvalid()3185 Search::endpointsInvalid()
3186 {
3187 delete endpoints_;
3188 delete invalid_endpoints_;
3189 endpoints_ = nullptr;
3190 invalid_endpoints_ = nullptr;
3191 }
3192
3193 void
seedInvalidRequireds()3194 Search::seedInvalidRequireds()
3195 {
3196 for (Vertex *vertex : invalid_requireds_)
3197 required_iter_->enqueue(vertex);
3198 invalid_requireds_.clear();
3199 }
3200
3201 ////////////////////////////////////////////////////////////////
3202
3203 // Visitor used by visitPathEnds to seed end required time.
3204 class FindEndRequiredVisitor : public PathEndVisitor
3205 {
3206 public:
3207 FindEndRequiredVisitor(RequiredCmp *required_cmp,
3208 const StaState *sta);
3209 FindEndRequiredVisitor(const StaState *sta);
3210 virtual ~FindEndRequiredVisitor();
3211 virtual PathEndVisitor *copy();
3212 virtual void visit(PathEnd *path_end);
3213
3214 protected:
3215 const StaState *sta_;
3216 RequiredCmp *required_cmp_;
3217 bool own_required_cmp_;
3218 };
3219
FindEndRequiredVisitor(RequiredCmp * required_cmp,const StaState * sta)3220 FindEndRequiredVisitor::FindEndRequiredVisitor(RequiredCmp *required_cmp,
3221 const StaState *sta) :
3222 sta_(sta),
3223 required_cmp_(required_cmp),
3224 own_required_cmp_(false)
3225 {
3226 }
3227
FindEndRequiredVisitor(const StaState * sta)3228 FindEndRequiredVisitor::FindEndRequiredVisitor(const StaState *sta) :
3229 sta_(sta),
3230 required_cmp_(new RequiredCmp),
3231 own_required_cmp_(true)
3232 {
3233 }
3234
~FindEndRequiredVisitor()3235 FindEndRequiredVisitor::~FindEndRequiredVisitor()
3236 {
3237 if (own_required_cmp_)
3238 delete required_cmp_;
3239 }
3240
3241 PathEndVisitor *
copy()3242 FindEndRequiredVisitor::copy()
3243 {
3244 return new FindEndRequiredVisitor(sta_);
3245 }
3246
3247 void
visit(PathEnd * path_end)3248 FindEndRequiredVisitor::visit(PathEnd *path_end)
3249 {
3250 if (!path_end->isUnconstrained()) {
3251 PathRef &path = path_end->pathRef();
3252 const MinMax *req_min = path.minMax(sta_)->opposite();
3253 int arrival_index;
3254 bool arrival_exists;
3255 path.arrivalIndex(arrival_index, arrival_exists);
3256 Required required = path_end->requiredTime(sta_);
3257 required_cmp_->requiredSet(arrival_index, required, req_min, sta_);
3258 }
3259 }
3260
3261 void
seedRequired(Vertex * vertex)3262 Search::seedRequired(Vertex *vertex)
3263 {
3264 debugPrint(debug_, "search", 2, "required seed %s",
3265 vertex->name(sdc_network_));
3266 RequiredCmp required_cmp;
3267 FindEndRequiredVisitor seeder(&required_cmp, this);
3268 required_cmp.requiredsInit(vertex, this);
3269 visit_path_ends_->visitPathEnds(vertex, &seeder);
3270 // Enqueue fanin vertices for back-propagating required times.
3271 if (required_cmp.requiredsSave(vertex, this))
3272 required_iter_->enqueueAdjacentVertices(vertex);
3273 }
3274
3275 void
seedRequiredEnqueueFanin(Vertex * vertex)3276 Search::seedRequiredEnqueueFanin(Vertex *vertex)
3277 {
3278 RequiredCmp required_cmp;
3279 FindEndRequiredVisitor seeder(&required_cmp, this);
3280 required_cmp.requiredsInit(vertex, this);
3281 visit_path_ends_->visitPathEnds(vertex, &seeder);
3282 // Enqueue fanin vertices for back-propagating required times.
3283 required_cmp.requiredsSave(vertex, this);
3284 required_iter_->enqueueAdjacentVertices(vertex);
3285 }
3286
3287 ////////////////////////////////////////////////////////////////
3288
RequiredCmp()3289 RequiredCmp::RequiredCmp() :
3290 have_requireds_(false)
3291 {
3292 requireds_.reserve(10);
3293 }
3294
3295 void
requiredsInit(Vertex * vertex,const StaState * sta)3296 RequiredCmp::requiredsInit(Vertex *vertex,
3297 const StaState *sta)
3298 {
3299 Search *search = sta->search();
3300 TagGroup *tag_group = search->tagGroup(vertex);
3301 if (tag_group) {
3302 requireds_.resize(tag_group->arrivalCount());
3303 ArrivalMap *arrival_entries = tag_group->arrivalMap();
3304 ArrivalMap::Iterator arrival_iter(arrival_entries);
3305 while (arrival_iter.hasNext()) {
3306 Tag *tag;
3307 int arrival_index;
3308 arrival_iter.next(tag, arrival_index);
3309 PathAnalysisPt *path_ap = tag->pathAnalysisPt(sta);
3310 const MinMax *min_max = path_ap->pathMinMax();
3311 requireds_[arrival_index] = delayInitValue(min_max->opposite());
3312 }
3313 }
3314 else
3315 requireds_.resize(0);
3316 have_requireds_ = false;
3317 }
3318
3319 void
requiredSet(int arrival_index,Required required,const MinMax * min_max,const StaState * sta)3320 RequiredCmp::requiredSet(int arrival_index,
3321 Required required,
3322 const MinMax *min_max,
3323 const StaState *sta)
3324 {
3325 if (delayGreater(required, requireds_[arrival_index], min_max, sta)) {
3326 requireds_[arrival_index] = required;
3327 have_requireds_ = true;
3328 }
3329 }
3330
3331 bool
requiredsSave(Vertex * vertex,const StaState * sta)3332 RequiredCmp::requiredsSave(Vertex *vertex,
3333 const StaState *sta)
3334 {
3335 bool requireds_changed = false;
3336 bool prev_reqs = vertex->hasRequireds();
3337 if (have_requireds_) {
3338 if (!prev_reqs)
3339 requireds_changed = true;
3340 Debug *debug = sta->debug();
3341 VertexPathIterator path_iter(vertex, sta);
3342 while (path_iter.hasNext()) {
3343 PathVertex *path = path_iter.next();
3344 int arrival_index;
3345 bool arrival_exists;
3346 path->arrivalIndex(arrival_index, arrival_exists);
3347 Required req = requireds_[arrival_index];
3348 if (prev_reqs) {
3349 Required prev_req = path->required(sta);
3350 if (!delayEqual(prev_req, req)) {
3351 debugPrint(debug, "search", 3, "required save %s -> %s",
3352 delayAsString(prev_req, sta),
3353 delayAsString(req, sta));
3354 path->setRequired(req, sta);
3355 requireds_changed = true;
3356 }
3357 }
3358 else {
3359 debugPrint(debug, "search", 3, "required save MIA -> %s",
3360 delayAsString(req, sta));
3361 path->setRequired(req, sta);
3362 }
3363 }
3364 }
3365 else if (prev_reqs) {
3366 PathVertex::deleteRequireds(vertex, sta);
3367 requireds_changed = true;
3368 }
3369 return requireds_changed;
3370 }
3371
3372 Required
required(int arrival_index)3373 RequiredCmp::required(int arrival_index)
3374 {
3375 return requireds_[arrival_index];
3376 }
3377
3378 ////////////////////////////////////////////////////////////////
3379
RequiredVisitor(const StaState * sta)3380 RequiredVisitor::RequiredVisitor(const StaState *sta) :
3381 PathVisitor(sta),
3382 required_cmp_(new RequiredCmp),
3383 visit_path_ends_(new VisitPathEnds(sta))
3384 {
3385 }
3386
~RequiredVisitor()3387 RequiredVisitor::~RequiredVisitor()
3388 {
3389 delete required_cmp_;
3390 delete visit_path_ends_;
3391 }
3392
3393 VertexVisitor *
copy()3394 RequiredVisitor::copy()
3395 {
3396 return new RequiredVisitor(sta_);
3397 }
3398
3399 void
visit(Vertex * vertex)3400 RequiredVisitor::visit(Vertex *vertex)
3401 {
3402 Search *search = sta_->search();
3403 const Debug *debug = sta_->debug();
3404 debugPrint(debug, "search", 2, "find required %s",
3405 vertex->name(sta_->network()));
3406 required_cmp_->requiredsInit(vertex, sta_);
3407 vertex->setRequiredsPruned(false);
3408 // Back propagate requireds from fanout.
3409 visitFanoutPaths(vertex);
3410 // Check for constraints at endpoints that set required times.
3411 if (search->isEndpoint(vertex)) {
3412 FindEndRequiredVisitor seeder(required_cmp_, sta_);
3413 visit_path_ends_->visitPathEnds(vertex, &seeder);
3414 }
3415 bool changed = required_cmp_->requiredsSave(vertex, sta_);
3416 search->tnsInvalid(vertex);
3417
3418 if (changed)
3419 search->requiredIterator()->enqueueAdjacentVertices(vertex);
3420 }
3421
3422 bool
visitFromToPath(const Pin *,Vertex * from_vertex,const RiseFall * from_rf,Tag * from_tag,PathVertex * from_path,Edge * edge,TimingArc *,ArcDelay arc_delay,Vertex * to_vertex,const RiseFall * to_rf,Tag * to_tag,Arrival &,const MinMax * min_max,const PathAnalysisPt * path_ap)3423 RequiredVisitor::visitFromToPath(const Pin *,
3424 Vertex *from_vertex,
3425 const RiseFall *from_rf,
3426 Tag *from_tag,
3427 PathVertex *from_path,
3428 Edge *edge,
3429 TimingArc *,
3430 ArcDelay arc_delay,
3431 Vertex *to_vertex,
3432 const RiseFall *to_rf,
3433 Tag *to_tag,
3434 Arrival &,
3435 const MinMax *min_max,
3436 const PathAnalysisPt *path_ap)
3437 {
3438 // Don't propagate required times through latch D->Q edges.
3439 if (edge->role() != TimingRole::latchDtoQ()) {
3440 const Debug *debug = sta_->debug();
3441 debugPrint(debug, "search", 3, " %s -> %s %s",
3442 from_rf->asString(),
3443 to_rf->asString(),
3444 min_max->asString());
3445 debugPrint(debug, "search", 3, " from tag %2u: %s",
3446 from_tag->index(),
3447 from_tag->asString(sta_));
3448 int arrival_index;
3449 bool arrival_exists;
3450 from_path->arrivalIndex(arrival_index, arrival_exists);
3451 const MinMax *req_min = min_max->opposite();
3452 TagGroup *to_tag_group = sta_->search()->tagGroup(to_vertex);
3453 // Check to see if to_tag was pruned.
3454 if (to_tag_group && to_tag_group->hasTag(to_tag)) {
3455 PathVertex to_path(to_vertex, to_tag, sta_);
3456 Required to_required = to_path.required(sta_);
3457 Required from_required = to_required - arc_delay;
3458 debugPrint(debug, "search", 3, " to tag %2u: %s",
3459 to_tag->index(),
3460 to_tag->asString(sta_));
3461 debugPrint(debug, "search", 3, " %s - %s = %s %s %s",
3462 delayAsString(to_required, sta_),
3463 delayAsString(arc_delay, sta_),
3464 delayAsString(from_required, sta_),
3465 min_max == MinMax::max() ? "<" : ">",
3466 delayAsString(required_cmp_->required(arrival_index), sta_));
3467 required_cmp_->requiredSet(arrival_index, from_required, req_min, sta_);
3468 }
3469 else {
3470 if (sta_->search()->crprApproxMissingRequireds()) {
3471 // Arrival on to_vertex that differs by crpr_pin was pruned.
3472 // Find an arrival that matches everything but the crpr_pin
3473 // as an appromate required.
3474 VertexPathIterator to_iter(to_vertex, to_rf, path_ap, sta_);
3475 while (to_iter.hasNext()) {
3476 PathVertex *to_path = to_iter.next();
3477 Tag *to_path_tag = to_path->tag(sta_);
3478 if (tagMatchNoCrpr(to_path_tag, to_tag)) {
3479 Required to_required = to_path->required(sta_);
3480 Required from_required = to_required - arc_delay;
3481 debugPrint(debug, "search", 3, " to tag %2u: %s",
3482 to_path_tag->index(),
3483 to_path_tag->asString(sta_));
3484 debugPrint(debug, "search", 3, " %s - %s = %s %s %s",
3485 delayAsString(to_required, sta_),
3486 delayAsString(arc_delay, sta_),
3487 delayAsString(from_required, sta_),
3488 min_max == MinMax::max() ? "<" : ">",
3489 delayAsString(required_cmp_->required(arrival_index),
3490 sta_));
3491 required_cmp_->requiredSet(arrival_index, from_required, req_min, sta_);
3492 break;
3493 }
3494 }
3495 }
3496 from_vertex->setRequiredsPruned(true);
3497 }
3498 // Propagate requireds pruned flag backwards.
3499 if (to_vertex->requiredsPruned())
3500 from_vertex->setRequiredsPruned(true);
3501 }
3502 return true;
3503 }
3504
3505 ////////////////////////////////////////////////////////////////
3506
3507 void
ensureDownstreamClkPins()3508 Search::ensureDownstreamClkPins()
3509 {
3510 if (!found_downstream_clk_pins_) {
3511 // Use backward BFS from register clk pins to mark upsteam pins
3512 // as having downstream clk pins.
3513 ClkTreeSearchPred pred(this);
3514 BfsBkwdIterator iter(BfsIndex::other, &pred, this);
3515 for (Vertex *vertex : *graph_->regClkVertices())
3516 iter.enqueue(vertex);
3517
3518 // Enqueue PLL feedback pins.
3519 VertexIterator vertex_iter(graph_);
3520 while (vertex_iter.hasNext()) {
3521 Vertex *vertex = vertex_iter.next();
3522 Pin *pin = vertex->pin();
3523 const LibertyPort *port = network_->libertyPort(pin);
3524 if (port && port->isPllFeedbackPin())
3525 iter.enqueue(vertex);
3526 }
3527 while (iter.hasNext()) {
3528 Vertex *vertex = iter.next();
3529 vertex->setHasDownstreamClkPin(true);
3530 iter.enqueueAdjacentVertices(vertex);
3531 }
3532 }
3533 found_downstream_clk_pins_ = true;
3534 }
3535
3536 ////////////////////////////////////////////////////////////////
3537
3538 bool
matchesFilter(Path * path,const ClockEdge * to_clk_edge)3539 Search::matchesFilter(Path *path,
3540 const ClockEdge *to_clk_edge)
3541 {
3542 if (filter_ == nullptr
3543 && filter_from_ == nullptr
3544 && filter_to_ == nullptr)
3545 return true;
3546 else if (filter_) {
3547 // -from pins|inst
3548 // -thru
3549 // Path has to be tagged by traversing the filter exception points.
3550 ExceptionStateSet *states = path->tag(this)->states();
3551 if (states) {
3552 for (auto state : *states) {
3553 if (state->exception() == filter_
3554 && state->nextThru() == nullptr
3555 && matchesFilterTo(path, to_clk_edge))
3556 return true;
3557 }
3558 }
3559 return false;
3560 }
3561 else if (filter_from_
3562 && filter_from_->pins() == nullptr
3563 && filter_from_->instances() == nullptr
3564 && filter_from_->clks()) {
3565 // -from clks
3566 ClockEdge *path_clk_edge = path->clkEdge(this);
3567 Clock *path_clk = path_clk_edge ? path_clk_edge->clock() : nullptr;
3568 RiseFall *path_clk_rf =
3569 path_clk_edge ? path_clk_edge->transition() : nullptr;
3570 return filter_from_->clks()->hasKey(path_clk)
3571 && filter_from_->transition()->matches(path_clk_rf)
3572 && matchesFilterTo(path, to_clk_edge);
3573 }
3574 else if (filter_from_ == nullptr
3575 && filter_to_)
3576 // -to
3577 return matchesFilterTo(path, to_clk_edge);
3578 else {
3579 report_->critical(262, "unexpected filter path");
3580 return false;
3581 }
3582 }
3583
3584 // Similar to Constraints::exceptionMatchesTo.
3585 bool
matchesFilterTo(Path * path,const ClockEdge * to_clk_edge) const3586 Search::matchesFilterTo(Path *path,
3587 const ClockEdge *to_clk_edge) const
3588 {
3589 return (filter_to_ == nullptr
3590 || filter_to_->matchesFilter(path->pin(graph_), to_clk_edge,
3591 path->transition(this), network_));
3592 }
3593
3594 ////////////////////////////////////////////////////////////////
3595
3596 // Find the exception that has the highest priority for an end path,
3597 // including exceptions that start at the end pin or target clock.
3598 ExceptionPath *
exceptionTo(ExceptionPathType type,const Path * path,const Pin * pin,const RiseFall * rf,const ClockEdge * clk_edge,const MinMax * min_max,bool match_min_max_exactly,bool require_to_pin) const3599 Search::exceptionTo(ExceptionPathType type,
3600 const Path *path,
3601 const Pin *pin,
3602 const RiseFall *rf,
3603 const ClockEdge *clk_edge,
3604 const MinMax *min_max,
3605 bool match_min_max_exactly,
3606 bool require_to_pin) const
3607 {
3608 // Find the highest priority exception carried by the path's tag.
3609 int hi_priority = -1;
3610 ExceptionPath *hi_priority_exception = nullptr;
3611 const ExceptionStateSet *states = path->tag(this)->states();
3612 if (states) {
3613 for (auto state : *states) {
3614 ExceptionPath *exception = state->exception();
3615 int priority = exception->priority(min_max);
3616 if ((type == ExceptionPathType::any
3617 || exception->type() == type)
3618 && sdc_->isCompleteTo(state, pin, rf, clk_edge, min_max,
3619 match_min_max_exactly, require_to_pin)
3620 && (hi_priority_exception == nullptr
3621 || priority > hi_priority
3622 || (priority == hi_priority
3623 && exception->tighterThan(hi_priority_exception)))) {
3624 hi_priority = priority;
3625 hi_priority_exception = exception;
3626 }
3627 }
3628 }
3629 // Check for -to exceptions originating at the end pin or target clock.
3630 sdc_->exceptionTo(type, pin, rf, clk_edge, min_max,
3631 match_min_max_exactly,
3632 hi_priority_exception, hi_priority);
3633 return hi_priority_exception;
3634 }
3635
3636 ////////////////////////////////////////////////////////////////
3637
3638 Slack
totalNegativeSlack(const MinMax * min_max)3639 Search::totalNegativeSlack(const MinMax *min_max)
3640 {
3641 tnsPreamble();
3642 Slack tns = 0.0;
3643 for (Corner *corner : *corners_) {
3644 PathAPIndex path_ap_index = corner->findPathAnalysisPt(min_max)->index();
3645 Slack tns1 = tns_[path_ap_index];
3646 if (delayLess(tns1, tns, this))
3647 tns = tns1;
3648 }
3649 return tns;
3650 }
3651
3652 Slack
totalNegativeSlack(const Corner * corner,const MinMax * min_max)3653 Search::totalNegativeSlack(const Corner *corner,
3654 const MinMax *min_max)
3655 {
3656 tnsPreamble();
3657 PathAPIndex path_ap_index = corner->findPathAnalysisPt(min_max)->index();
3658 return tns_[path_ap_index];
3659 }
3660
3661 void
tnsPreamble()3662 Search::tnsPreamble()
3663 {
3664 wnsTnsPreamble();
3665 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3666 tns_.resize(path_ap_count);
3667 tns_slacks_.resize(path_ap_count);
3668 if (tns_exists_)
3669 updateInvalidTns();
3670 else
3671 findTotalNegativeSlacks();
3672 }
3673
3674 void
tnsInvalid(Vertex * vertex)3675 Search::tnsInvalid(Vertex *vertex)
3676 {
3677 if ((tns_exists_ || worst_slacks_)
3678 && isEndpoint(vertex)) {
3679 debugPrint(debug_, "tns", 2, "tns invalid %s",
3680 vertex->name(sdc_network_));
3681 UniqueLock lock(tns_lock_);
3682 invalid_tns_.insert(vertex);
3683 }
3684 }
3685
3686 void
updateInvalidTns()3687 Search::updateInvalidTns()
3688 {
3689 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3690 for (Vertex *vertex : invalid_tns_) {
3691 // Network edits can change endpointedness since tnsInvalid was called.
3692 if (isEndpoint(vertex)) {
3693 debugPrint(debug_, "tns", 2, "update tns %s",
3694 vertex->name(sdc_network_));
3695 SlackSeq slacks(path_ap_count);
3696 wnsSlacks(vertex, slacks);
3697
3698 if (tns_exists_)
3699 updateTns(vertex, slacks);
3700 if (worst_slacks_)
3701 worst_slacks_->updateWorstSlacks(vertex, slacks);
3702 }
3703 }
3704 invalid_tns_.clear();
3705 }
3706
3707 void
findTotalNegativeSlacks()3708 Search::findTotalNegativeSlacks()
3709 {
3710 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3711 for (PathAPIndex i = 0; i < path_ap_count; i++) {
3712 tns_[i] = 0.0;
3713 tns_slacks_[i].clear();
3714 }
3715 for (Vertex *vertex : *endpoints()) {
3716 // No locking required.
3717 SlackSeq slacks(path_ap_count);
3718 wnsSlacks(vertex, slacks);
3719 for (PathAPIndex i = 0; i < path_ap_count; i++)
3720 tnsIncr(vertex, slacks[i], i);
3721 }
3722 tns_exists_ = true;
3723 }
3724
3725 void
updateTns(Vertex * vertex,SlackSeq & slacks)3726 Search::updateTns(Vertex *vertex,
3727 SlackSeq &slacks)
3728 {
3729 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3730 for (PathAPIndex i = 0; i < path_ap_count; i++) {
3731 tnsDecr(vertex, i);
3732 tnsIncr(vertex, slacks[i], i);
3733 }
3734 }
3735
3736 void
tnsIncr(Vertex * vertex,Slack slack,PathAPIndex path_ap_index)3737 Search::tnsIncr(Vertex *vertex,
3738 Slack slack,
3739 PathAPIndex path_ap_index)
3740 {
3741 if (delayLess(slack, 0.0, this)) {
3742 debugPrint(debug_, "tns", 3, "tns+ %s %s",
3743 delayAsString(slack, this),
3744 vertex->name(sdc_network_));
3745 tns_[path_ap_index] += slack;
3746 if (tns_slacks_[path_ap_index].hasKey(vertex))
3747 report_->critical(263, "tns incr existing vertex");
3748 tns_slacks_[path_ap_index][vertex] = slack;
3749 }
3750 }
3751
3752 void
tnsDecr(Vertex * vertex,PathAPIndex path_ap_index)3753 Search::tnsDecr(Vertex *vertex,
3754 PathAPIndex path_ap_index)
3755 {
3756 Slack slack;
3757 bool found;
3758 tns_slacks_[path_ap_index].findKey(vertex, slack, found);
3759 if (found
3760 && delayLess(slack, 0.0, this)) {
3761 debugPrint(debug_, "tns", 3, "tns- %s %s",
3762 delayAsString(slack, this),
3763 vertex->name(sdc_network_));
3764 tns_[path_ap_index] -= slack;
3765 tns_slacks_[path_ap_index].erase(vertex);
3766 }
3767 }
3768
3769 // Notify tns before updating/deleting slack (arrival/required).
3770 void
tnsNotifyBefore(Vertex * vertex)3771 Search::tnsNotifyBefore(Vertex *vertex)
3772 {
3773 if (tns_exists_
3774 && isEndpoint(vertex)) {
3775 int ap_count = corners_->pathAnalysisPtCount();
3776 for (int i = 0; i < ap_count; i++) {
3777 tnsDecr(vertex, i);
3778 }
3779 }
3780 }
3781
3782 ////////////////////////////////////////////////////////////////
3783
3784 void
worstSlack(const MinMax * min_max,Slack & worst_slack,Vertex * & worst_vertex)3785 Search::worstSlack(const MinMax *min_max,
3786 // Return values.
3787 Slack &worst_slack,
3788 Vertex *&worst_vertex)
3789 {
3790 worstSlackPreamble();
3791 worst_slacks_->worstSlack(min_max, worst_slack, worst_vertex);
3792 }
3793
3794 void
worstSlack(const Corner * corner,const MinMax * min_max,Slack & worst_slack,Vertex * & worst_vertex)3795 Search::worstSlack(const Corner *corner,
3796 const MinMax *min_max,
3797 // Return values.
3798 Slack &worst_slack,
3799 Vertex *&worst_vertex)
3800 {
3801 worstSlackPreamble();
3802 worst_slacks_->worstSlack(corner, min_max, worst_slack, worst_vertex);
3803 }
3804
3805 void
worstSlackPreamble()3806 Search::worstSlackPreamble()
3807 {
3808 wnsTnsPreamble();
3809 if (worst_slacks_)
3810 updateInvalidTns();
3811 else
3812 worst_slacks_ = new WorstSlacks(this);
3813 }
3814
3815 void
wnsTnsPreamble()3816 Search::wnsTnsPreamble()
3817 {
3818 findAllArrivals();
3819 // Required times are only needed at endpoints.
3820 if (requireds_seeded_) {
3821 for (Vertex *vertex : invalid_requireds_) {
3822 debugPrint(debug_, "search", 2, "tns update required %s",
3823 vertex->name(sdc_network_));
3824 if (isEndpoint(vertex)) {
3825 seedRequired(vertex);
3826 // If the endpoint has fanout it's required time
3827 // depends on downstream checks, so enqueue it to
3828 // force required propagation to it's level if
3829 // the required time is requested later.
3830 if (hasFanout(vertex, search_adj_, graph_))
3831 required_iter_->enqueue(vertex);
3832 }
3833 }
3834 invalid_requireds_.clear();
3835 }
3836 else
3837 seedRequireds();
3838 }
3839
3840 void
clearWorstSlack()3841 Search::clearWorstSlack()
3842 {
3843 if (worst_slacks_) {
3844 // Don't maintain incremental worst slacks until there is a request.
3845 delete worst_slacks_;
3846 worst_slacks_ = nullptr;
3847 }
3848 }
3849
3850 ////////////////////////////////////////////////////////////////
3851
3852 class FindEndSlackVisitor : public PathEndVisitor
3853 {
3854 public:
3855 FindEndSlackVisitor(SlackSeq &slacks,
3856 const StaState *sta);
3857 virtual PathEndVisitor *copy();
3858 virtual void visit(PathEnd *path_end);
3859
3860 protected:
3861 SlackSeq &slacks_;
3862 const StaState *sta_;
3863 };
3864
FindEndSlackVisitor(SlackSeq & slacks,const StaState * sta)3865 FindEndSlackVisitor::FindEndSlackVisitor(SlackSeq &slacks,
3866 const StaState *sta) :
3867 slacks_(slacks),
3868 sta_(sta)
3869 {
3870 }
3871
3872 PathEndVisitor *
copy()3873 FindEndSlackVisitor::copy()
3874 {
3875
3876 return new FindEndSlackVisitor(slacks_, sta_);
3877 }
3878
3879 void
visit(PathEnd * path_end)3880 FindEndSlackVisitor::visit(PathEnd *path_end)
3881 {
3882 if (!path_end->isUnconstrained()) {
3883 PathRef &path = path_end->pathRef();
3884 PathAPIndex path_ap_index = path.pathAnalysisPtIndex(sta_);
3885 Slack slack = path_end->slack(sta_);
3886 if (delayLess(slack, slacks_[path_ap_index], sta_))
3887 slacks_[path_ap_index] = slack;
3888 }
3889 }
3890
3891 void
wnsSlacks(Vertex * vertex,SlackSeq & slacks)3892 Search::wnsSlacks(Vertex *vertex,
3893 // Return values.
3894 SlackSeq &slacks)
3895 {
3896 Slack slack_init = MinMax::min()->initValue();
3897 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3898 for (PathAPIndex i = 0; i < path_ap_count; i++)
3899 slacks[i] = slack_init;
3900 if (hasFanout(vertex, search_adj_, graph_)) {
3901 // If the vertex has fanout the path slacks include downstream
3902 // PathEnd slacks so find the endpoint slack directly.
3903 FindEndSlackVisitor end_visitor(slacks, this);
3904 visit_path_ends_->visitPathEnds(vertex, &end_visitor);
3905 }
3906 else {
3907 VertexPathIterator path_iter(vertex, this);
3908 while (path_iter.hasNext()) {
3909 Path *path = path_iter.next();
3910 PathAPIndex path_ap_index = path->pathAnalysisPtIndex(this);
3911 const Slack path_slack = path->slack(this);
3912 if (!path->tag(this)->isFilter()
3913 && delayLess(path_slack, slacks[path_ap_index], this))
3914 slacks[path_ap_index] = path_slack;
3915 }
3916 }
3917 }
3918
3919 Slack
wnsSlack(Vertex * vertex,PathAPIndex path_ap_index)3920 Search::wnsSlack(Vertex *vertex,
3921 PathAPIndex path_ap_index)
3922 {
3923 PathAPIndex path_ap_count = corners_->pathAnalysisPtCount();
3924 SlackSeq slacks(path_ap_count);
3925 wnsSlacks(vertex, slacks);
3926 return slacks[path_ap_index];
3927 }
3928
3929 ////////////////////////////////////////////////////////////////
3930
3931 PathGroups *
makePathGroups(int group_count,int endpoint_count,bool unique_pins,float slack_min,float slack_max,PathGroupNameSet * group_names,bool setup,bool hold,bool recovery,bool removal,bool clk_gating_setup,bool clk_gating_hold)3932 Search::makePathGroups(int group_count,
3933 int endpoint_count,
3934 bool unique_pins,
3935 float slack_min,
3936 float slack_max,
3937 PathGroupNameSet *group_names,
3938 bool setup,
3939 bool hold,
3940 bool recovery,
3941 bool removal,
3942 bool clk_gating_setup,
3943 bool clk_gating_hold)
3944 {
3945 return new PathGroups(group_count, endpoint_count, unique_pins,
3946 slack_min, slack_max,
3947 group_names,
3948 setup, hold,
3949 recovery, removal,
3950 clk_gating_setup, clk_gating_hold,
3951 unconstrained_paths_,
3952 this);
3953 }
3954
3955 void
deletePathGroups()3956 Search::deletePathGroups()
3957 {
3958 delete path_groups_;
3959 path_groups_ = nullptr;
3960 }
3961
3962 PathGroup *
pathGroup(const PathEnd * path_end) const3963 Search::pathGroup(const PathEnd *path_end) const
3964 {
3965 return path_groups_->pathGroup(path_end);
3966 }
3967
3968 bool
havePathGroups() const3969 Search::havePathGroups() const
3970 {
3971 return path_groups_ != nullptr;
3972 }
3973
3974 PathGroup *
findPathGroup(const char * name,const MinMax * min_max) const3975 Search::findPathGroup(const char *name,
3976 const MinMax *min_max) const
3977 {
3978 if (path_groups_)
3979 return path_groups_->findPathGroup(name, min_max);
3980 else
3981 return nullptr;
3982 }
3983
3984 PathGroup *
findPathGroup(const Clock * clk,const MinMax * min_max) const3985 Search::findPathGroup(const Clock *clk,
3986 const MinMax *min_max) const
3987 {
3988 if (path_groups_)
3989 return path_groups_->findPathGroup(clk, min_max);
3990 else
3991 return nullptr;
3992 }
3993
3994 } // namespace
3995