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 "Tag.hh"
18
19 #include "Report.hh"
20 #include "Network.hh"
21 #include "Clock.hh"
22 #include "PortDelay.hh"
23 #include "ExceptionPath.hh"
24 #include "Sdc.hh"
25 #include "Graph.hh"
26 #include "Corner.hh"
27 #include "Search.hh"
28 #include "PathAnalysisPt.hh"
29 #include "ClkInfo.hh"
30
31 namespace sta {
32
33 static int
34 tagStateCmp(const Tag *tag1,
35 const Tag *tag2);
36 static bool
37 tagStateEqual(ExceptionStateSet *states1,
38 ExceptionStateSet *states2);
39 static bool
40 tagStateEqualCrpr(const Tag *tag1,
41 const Tag *tag2);
42
Tag(TagIndex index,int tr_index,PathAPIndex path_ap_index,ClkInfo * clk_info,bool is_clk,InputDelay * input_delay,bool is_segment_start,ExceptionStateSet * states,bool own_states,const StaState * sta)43 Tag::Tag(TagIndex index,
44 int tr_index,
45 PathAPIndex path_ap_index,
46 ClkInfo *clk_info,
47 bool is_clk,
48 InputDelay *input_delay,
49 bool is_segment_start,
50 ExceptionStateSet *states,
51 bool own_states,
52 const StaState *sta) :
53 clk_info_(clk_info),
54 input_delay_(input_delay),
55 states_(states),
56 is_clk_(is_clk),
57 is_filter_(false),
58 is_loop_(false),
59 is_segment_start_(is_segment_start),
60 own_states_(own_states),
61 index_(index),
62 tr_index_(tr_index),
63 path_ap_index_(path_ap_index)
64 {
65 findHash();
66 if (states_) {
67 FilterPath *filter = sta->search()->filter();
68 ExceptionStateSet::ConstIterator state_iter(states_);
69 while (state_iter.hasNext()) {
70 ExceptionState *state = state_iter.next();
71 ExceptionPath *exception = state->exception();
72 if (exception->isLoop())
73 is_loop_ = true;
74 if (exception == filter)
75 is_filter_ = true;
76 }
77 }
78 }
79
~Tag()80 Tag::~Tag()
81 {
82 if (own_states_ && states_)
83 delete states_;
84 }
85
86 const char *
asString(const StaState * sta) const87 Tag::asString(const StaState *sta) const
88 {
89 return asString(true, true, sta);
90 }
91
92 const char *
asString(bool report_index,bool report_rf_min_max,const StaState * sta) const93 Tag::asString(bool report_index,
94 bool report_rf_min_max,
95 const StaState *sta) const
96 {
97 const Network *network = sta->network();
98 const Corners *corners = sta->corners();
99 string str;
100
101 if (report_index)
102 str += stringPrintTmp("%4d ", index_);
103
104 if (report_rf_min_max) {
105 const RiseFall *rf = transition();
106 PathAnalysisPt *path_ap = corners->findPathAnalysisPt(path_ap_index_);
107 str += stringPrintTmp("%s %s/%d ",
108 rf->asString(),
109 path_ap->pathMinMax()->asString(),
110 path_ap_index_);
111 }
112
113 ClockEdge *clk_edge = clkEdge();
114 if (clk_edge)
115 str += clk_edge->name();
116 else
117 str += "unclocked";
118
119 bool is_genclk_src = clk_info_->isGenClkSrcPath();
120 if (is_clk_ || is_genclk_src) {
121 str += " (";
122 if (is_clk_) {
123 str += "clock";
124 if (clk_info_->isPropagated())
125 str += " prop";
126 else
127 str += " ideal";
128 if (is_genclk_src)
129 str += " ";
130 }
131 if (clk_info_->isGenClkSrcPath())
132 str += "genclk";
133 str += ")";
134 }
135
136 const Pin *clk_src = clkSrc();
137 if (clk_src) {
138 str += " clk_src ";
139 str += network->pathName(clk_src);
140 }
141
142 const PathVertex crpr_clk_path(clk_info_->crprClkPath(), sta);
143 if (!crpr_clk_path.isNull()) {
144 str += " crpr_pin ";
145 str += network->pathName(crpr_clk_path.pin(sta));
146 }
147
148 if (input_delay_) {
149 str += " input ";
150 str += network->pathName(input_delay_->pin());
151 }
152
153 if (is_segment_start_)
154 str += " segment_start";
155
156 if (states_) {
157 ExceptionStateSet::ConstIterator state_iter(states_);
158 while (state_iter.hasNext()) {
159 ExceptionState *state = state_iter.next();
160 ExceptionPath *exception = state->exception();
161 str += " ";
162 str += exception->asString(network);
163 if (state->nextThru()) {
164 str += " (next thru ";
165 str += state->nextThru()->asString(network);
166 str += ")";
167 }
168 else {
169 if (exception->thrus() != nullptr)
170 str += " (thrus complete)";
171 }
172 }
173 }
174
175 char *result = makeTmpString(str.size() + 1);
176 strcpy(result, str.c_str());
177 return result;
178 }
179
180 const RiseFall *
transition() const181 Tag::transition() const
182 {
183 return RiseFall::find(tr_index_);
184 }
185
186 PathAnalysisPt *
pathAnalysisPt(const StaState * sta) const187 Tag::pathAnalysisPt(const StaState *sta) const
188 {
189 const Corners *corners = sta->corners();
190 return corners->findPathAnalysisPt(path_ap_index_);
191 }
192
193 void
setStates(ExceptionStateSet * states)194 Tag::setStates(ExceptionStateSet *states)
195 {
196 states_ = states;
197 }
198
199 ClockEdge *
clkEdge() const200 Tag::clkEdge() const
201 {
202 return clk_info_->clkEdge();
203 }
204
205 Clock *
clock() const206 Tag::clock() const
207 {
208 return clk_info_->clock();
209 }
210
211 const Pin *
clkSrc() const212 Tag::clkSrc() const
213 {
214 return clk_info_->clkSrc();
215 }
216
217 bool
isGenClkSrcPath() const218 Tag::isGenClkSrcPath() const
219 {
220 return clk_info_->isGenClkSrcPath();
221 }
222
223 Clock *
genClkSrcPathClk(const StaState * sta) const224 Tag::genClkSrcPathClk(const StaState *sta) const
225 {
226 if (clk_info_->isGenClkSrcPath()
227 && states_) {
228 FilterPath *filter = sta->search()->filter();
229 ExceptionStateSet::ConstIterator state_iter(states_);
230 while (state_iter.hasNext()) {
231 ExceptionState *state = state_iter.next();
232 ExceptionPath *except = state->exception();
233 if (except->isFilter()
234 && except != filter) {
235 ExceptionTo *to = except->to();
236 if (to) {
237 ClockSet *clks = to->clks();
238 if (clks && clks->size() == 1) {
239 ClockSet::Iterator clk_iter(clks);
240 Clock *clk = clk_iter.next();
241 return clk;
242 }
243 }
244 }
245 }
246 }
247 return nullptr;
248 }
249
250 void
findHash()251 Tag::findHash()
252 {
253 // Common to hash_ and match_hash_.
254 hash_ = hash_init_value;
255 hashIncr(hash_, tr_index_);
256 hashIncr(hash_, path_ap_index_);
257 hashIncr(hash_, is_clk_);
258 hashIncr(hash_, is_segment_start_);
259 if (states_) {
260 ExceptionStateSet::Iterator state_iter(states_);
261 while (state_iter.hasNext()) {
262 ExceptionState *state = state_iter.next();
263 hashIncr(hash_, state->hash());
264 }
265 }
266 match_hash_ = hash_;
267
268 // Finish hash_.
269 hashIncr(hash_, clk_info_->hash());
270 if (input_delay_)
271 hashIncr(hash_, input_delay_->index());
272
273 // Finish match_hash_.
274 ClockEdge *clk_edge = clk_info_->clkEdge();
275 if (clk_edge)
276 hashIncr(match_hash_, clk_edge->index());
277 hashIncr(match_hash_, clk_info_->isGenClkSrcPath());
278 }
279
280 size_t
matchHash(bool match_crpr_clk_pin) const281 Tag::matchHash(bool match_crpr_clk_pin) const
282 {
283 if (match_crpr_clk_pin)
284 // match_hash_ with crpr clk pin thrown in.
285 return hashSum(match_hash_, clk_info_->crprClkVertexId());
286 else
287 return match_hash_;
288 }
289
290 ////////////////////////////////////////////////////////////////
291
292 bool
operator ()(const Tag * tag1,const Tag * tag2) const293 TagLess::operator()(const Tag *tag1,
294 const Tag *tag2) const
295 {
296 return tagCmp(tag1, tag2, true) < 0;
297 }
298
299 int
tagCmp(const Tag * tag1,const Tag * tag2,bool cmp_rf)300 tagCmp(const Tag *tag1,
301 const Tag *tag2,
302 bool cmp_rf)
303 {
304 if (tag1 == tag2)
305 return 0;
306
307 if (cmp_rf) {
308 int tr_index1 = tag1->trIndex();
309 int tr_index2 = tag2->trIndex();
310 if (tr_index1 < tr_index2)
311 return -1;
312 if (tr_index1 > tr_index2)
313 return 1;
314 }
315
316 PathAPIndex path_ap_index1 = tag1->pathAPIndex();
317 PathAPIndex path_ap_index2 = tag2->pathAPIndex();
318 if (path_ap_index1 < path_ap_index2)
319 return -1;
320 if (path_ap_index1 > path_ap_index2)
321 return 1;
322
323 size_t clk_info1 = tag1->clkInfo()->hash();
324 size_t clk_info2 = tag2->clkInfo()->hash();
325 if (clk_info1 < clk_info2)
326 return -1;
327 if (clk_info1 > clk_info2)
328 return 1;
329
330 bool is_clk1 = tag1->isClock();
331 bool is_clk2 = tag2->isClock();
332 if (!is_clk1 && is_clk2)
333 return -1;
334 if (is_clk1 && !is_clk2)
335 return 1;
336
337 InputDelay *input_delay1 = tag1->inputDelay();
338 InputDelay *input_delay2 = tag2->inputDelay();
339 int input_delay_index1 = input_delay1 ? input_delay1->index() : 0;
340 int input_delay_index2 = input_delay2 ? input_delay2->index() : 0;
341 if (input_delay_index1 < input_delay_index2)
342 return -1;
343 if (input_delay_index1 > input_delay_index2)
344 return 1;
345
346 bool is_segment_start1 = tag1->isSegmentStart();
347 bool is_segment_start2 = tag2->isSegmentStart();
348 if (!is_segment_start1 && is_segment_start2)
349 return -1;
350 if (is_segment_start1 && !is_segment_start2)
351 return 1;
352
353 return tagStateCmp(tag1, tag2);
354 }
355
356 int
tagEqual(const Tag * tag1,const Tag * tag2)357 tagEqual(const Tag *tag1,
358 const Tag *tag2)
359 {
360 return tag1 == tag2
361 || (tag1->trIndex() == tag2->trIndex()
362 && tag1->pathAPIndex() == tag2->pathAPIndex()
363 && tag1->clkInfo() == tag2->clkInfo()
364 && tag1->isClock() == tag2->isClock()
365 && tag1->inputDelay() == tag2->inputDelay()
366 && tag1->isSegmentStart() == tag2->isSegmentStart()
367 && tagStateEqual(tag1, tag2));
368 }
369
370 ////////////////////////////////////////////////////////////////
371
372 bool
operator ()(const Tag * tag1,const Tag * tag2) const373 TagIndexLess::operator()(const Tag *tag1,
374 const Tag *tag2) const
375 {
376 return tag1->index() < tag2->index();
377 }
378
379 ////////////////////////////////////////////////////////////////
380
TagMatchLess(bool match_crpr_clk_pin,const StaState * sta)381 TagMatchLess::TagMatchLess(bool match_crpr_clk_pin,
382 const StaState *sta) :
383 match_crpr_clk_pin_(match_crpr_clk_pin),
384 sta_(sta)
385 {
386 }
387
388 bool
operator ()(const Tag * tag1,const Tag * tag2) const389 TagMatchLess::operator()(const Tag *tag1,
390 const Tag *tag2) const
391 {
392 return tagMatchCmp(tag1, tag2, match_crpr_clk_pin_, sta_) < 0;
393 }
394
395 ////////////////////////////////////////////////////////////////
396
397 bool
tagMatch(const Tag * tag1,const Tag * tag2,const StaState * sta)398 tagMatch(const Tag *tag1,
399 const Tag *tag2,
400 const StaState *sta)
401 {
402 return tagMatch(tag1, tag2, true, sta);
403 }
404
405 bool
tagMatch(const Tag * tag1,const Tag * tag2,bool match_crpr_clk_pin,const StaState * sta)406 tagMatch(const Tag *tag1,
407 const Tag *tag2,
408 bool match_crpr_clk_pin,
409 const StaState *sta)
410 {
411 const ClkInfo *clk_info1 = tag1->clkInfo();
412 const ClkInfo *clk_info2 = tag2->clkInfo();
413 return tag1 == tag2
414 || (clk_info1->clkEdge() == clk_info2->clkEdge()
415 && tag1->trIndex() == tag2->trIndex()
416 && tag1->pathAPIndex() == tag2->pathAPIndex()
417 && tag1->isClock() == tag2->isClock()
418 && tag1->isSegmentStart() == tag2->isSegmentStart()
419 && clk_info1->isGenClkSrcPath() == clk_info2->isGenClkSrcPath()
420 && (!match_crpr_clk_pin
421 || !sta->sdc()->crprActive()
422 || clk_info1->crprClkVertexId() == clk_info2->crprClkVertexId())
423 && tagStateEqual(tag1, tag2));
424 }
425
426 int
tagMatchCmp(const Tag * tag1,const Tag * tag2,bool match_crpr_clk_pin,const StaState * sta)427 tagMatchCmp(const Tag *tag1,
428 const Tag *tag2,
429 bool match_crpr_clk_pin,
430 const StaState *sta)
431 {
432 if (tag1 == tag2)
433 return 0;
434
435 int tr_index1 = tag1->trIndex();
436 int tr_index2 = tag2->trIndex();
437 if (tr_index1 < tr_index2)
438 return -1;
439 if (tr_index1 > tr_index2)
440 return 1;
441
442 PathAPIndex path_ap_index1 = tag1->pathAPIndex();
443 PathAPIndex path_ap_index2 = tag2->pathAPIndex();
444 if (path_ap_index1 < path_ap_index2)
445 return -1;
446 if (path_ap_index1 > path_ap_index2)
447 return 1;
448
449 const ClkInfo *clk_info1 = tag1->clkInfo();
450 const ClkInfo *clk_info2 = tag2->clkInfo();
451 const ClockEdge *clk_edge1 = clk_info1->clkEdge();
452 const ClockEdge *clk_edge2 = clk_info2->clkEdge();
453 int edge_index1 = clk_edge1 ? clk_edge1->index() : -1;
454 int edge_index2 = clk_edge2 ? clk_edge2->index() : -1;
455 if (edge_index1 < edge_index2)
456 return -1;
457 if (edge_index1 > edge_index2)
458 return 1;
459
460 bool is_clk1 = tag1->isClock();
461 bool is_clk2 = tag2->isClock();
462 if (!is_clk1 && is_clk2)
463 return -1;
464 if (is_clk1 && !is_clk2)
465 return 1;
466
467 bool is_genclk_src1 = clk_info1->isGenClkSrcPath();
468 bool is_genclk_src2 = clk_info2->isGenClkSrcPath();
469 if (!is_genclk_src1 && is_genclk_src2)
470 return -1;
471 if (is_genclk_src1 && !is_genclk_src2)
472 return 1;
473
474 bool is_segment_start1 = tag1->isSegmentStart();
475 bool is_segment_start2 = tag2->isSegmentStart();
476 if (!is_segment_start1 && is_segment_start2)
477 return -1;
478 if (is_segment_start1 && !is_segment_start2)
479 return 1;
480
481 if (match_crpr_clk_pin
482 && sta->sdc()->crprActive()) {
483 VertexId crpr_vertex1 = clk_info1->crprClkVertexId();
484 VertexId crpr_vertex2 = clk_info2->crprClkVertexId();
485 if (crpr_vertex1 < crpr_vertex2)
486 return -1;
487 if (crpr_vertex1 > crpr_vertex2)
488 return 1;
489 }
490
491 return tagStateCmp(tag1, tag2);
492 }
493
494 bool
tagMatchNoCrpr(const Tag * tag1,const Tag * tag2)495 tagMatchNoCrpr(const Tag *tag1,
496 const Tag *tag2)
497 {
498 const ClkInfo *clk_info1 = tag1->clkInfo();
499 const ClkInfo *clk_info2 = tag2->clkInfo();
500 return tag1 == tag2
501 || (clk_info1->clkEdge() == clk_info2->clkEdge()
502 && tag1->trIndex() == tag2->trIndex()
503 && tag1->pathAPIndex() == tag2->pathAPIndex()
504 && tag1->isClock() == tag2->isClock()
505 && clk_info1->isGenClkSrcPath() == clk_info2->isGenClkSrcPath()
506 && tagStateEqual(tag1, tag2));
507 }
508
509 bool
tagMatchNoPathAp(const Tag * tag1,const Tag * tag2)510 tagMatchNoPathAp(const Tag *tag1,
511 const Tag *tag2)
512 {
513 const ClkInfo *clk_info1 = tag1->clkInfo();
514 const ClkInfo *clk_info2 = tag2->clkInfo();
515 return tag1 == tag2
516 || (clk_info1->clkEdge() == clk_info2->clkEdge()
517 && tag1->trIndex() == tag2->trIndex()
518 && tag1->isClock() == tag2->isClock()
519 && tag1->isSegmentStart() == tag2->isSegmentStart()
520 && clk_info1->isGenClkSrcPath() == clk_info2->isGenClkSrcPath()
521 && tagStateEqual(tag1, tag2));
522 }
523
524 bool
tagMatchCrpr(const Tag * tag1,const Tag * tag2)525 tagMatchCrpr(const Tag *tag1,
526 const Tag *tag2)
527 {
528 const ClkInfo *clk_info1 = tag1->clkInfo();
529 const ClkInfo *clk_info2 = tag2->clkInfo();
530 return tag1 == tag2
531 || (clk_info1->clkEdge() == clk_info2->clkEdge()
532 && tag1->trIndex() == tag2->trIndex()
533 && tag1->isClock() == tag2->isClock()
534 && tag1->isSegmentStart() == tag2->isSegmentStart()
535 && clk_info1->isGenClkSrcPath() == clk_info2->isGenClkSrcPath()
536 && tagStateEqualCrpr(tag1, tag2));
537 }
538
539 ////////////////////////////////////////////////////////////////
540
541 static int
tagStateCmp(const Tag * tag1,const Tag * tag2)542 tagStateCmp(const Tag *tag1,
543 const Tag *tag2)
544 {
545 ExceptionStateSet *states1 = tag1->states();
546 ExceptionStateSet *states2 = tag2->states();
547 bool states_null1 = (states1 == nullptr || states1->empty());
548 bool states_null2 = (states2 == nullptr || states2->empty());
549 if (states_null1
550 && states_null2)
551 return 0;
552 if (states_null1
553 && !states_null2)
554 return -1;
555 if (!states_null1
556 && states_null2)
557 return 1;
558
559 size_t state_size1 = states1->size();
560 size_t state_size2 = states2->size();
561 if (state_size1 < state_size2)
562 return -1;
563 if (state_size1 > state_size2)
564 return 1;
565
566 ExceptionStateSet::Iterator state_iter1(states1);
567 ExceptionStateSet::Iterator state_iter2(states2);
568 while (state_iter1.hasNext()
569 && state_iter2.hasNext()) {
570 ExceptionState *state1 = state_iter1.next();
571 ExceptionState *state2 = state_iter2.next();
572 if (state1 < state2)
573 return -1;
574 if (state1 > state2)
575 return 1;
576 }
577 return 0;
578 }
579
580 bool
tagStateEqual(const Tag * tag1,const Tag * tag2)581 tagStateEqual(const Tag *tag1,
582 const Tag *tag2)
583 {
584 return tagStateEqual(tag1->states(), tag2->states());
585 }
586
587 static bool
tagStateEqual(ExceptionStateSet * states1,ExceptionStateSet * states2)588 tagStateEqual(ExceptionStateSet *states1,
589 ExceptionStateSet *states2)
590 {
591 bool states_null1 = (states1 == nullptr || states1->empty());
592 bool states_null2 = (states2 == nullptr || states2->empty());
593 if (states_null1 && states_null2)
594 return true;
595 else if (states_null1 != states_null2)
596 return false;
597
598 size_t state_size1 = states1->size();
599 size_t state_size2 = states2->size();
600 if (state_size1 == state_size2) {
601 ExceptionStateSet::Iterator state_iter1(states1);
602 ExceptionStateSet::Iterator state_iter2(states2);
603 while (state_iter1.hasNext()
604 && state_iter2.hasNext()) {
605 ExceptionState *state1 = state_iter1.next();
606 ExceptionState *state2 = state_iter2.next();
607 if (state1 != state2)
608 return false;
609 }
610 return true;
611 }
612 else
613 return false;
614 }
615
616 // Match false, loop exception states only for crpr min/max paths.
617 static bool
tagStateEqualCrpr(const Tag * tag1,const Tag * tag2)618 tagStateEqualCrpr(const Tag *tag1,
619 const Tag *tag2)
620 {
621 ExceptionStateSet *states1 = tag1->states();
622 ExceptionStateSet *states2 = tag2->states();
623 ExceptionStateSet::Iterator state_iter1(states1);
624 ExceptionStateSet::Iterator state_iter2(states2);
625 ExceptionState *state1, *state2;
626 do {
627 state1 = nullptr;
628 while (state_iter1.hasNext()) {
629 state1 = state_iter1.next();
630 ExceptionPath *exception1 = state1->exception();
631 if (exception1->isFalse()
632 || exception1->isLoop())
633 break;
634 else
635 state1 = nullptr;
636 }
637 state2 = nullptr;
638 while (state_iter2.hasNext()) {
639 state2 = state_iter2.next();
640 ExceptionPath *exception2 = state2->exception();
641 if (exception2->isFalse()
642 || exception2->isLoop())
643 break;
644 else
645 state2 = nullptr;
646 }
647 if (state1 != state2)
648 return false;
649 } while (state1 && state2);
650 return state1 == nullptr
651 && state2 == nullptr;
652 }
653
654 ////////////////////////////////////////////////////////////////
655
656 size_t
operator ()(const Tag * tag)657 TagHash::operator()(const Tag *tag)
658 {
659 return tag->hash();
660 }
661
662 bool
operator ()(const Tag * tag1,const Tag * tag2)663 TagEqual::operator()(const Tag *tag1,
664 const Tag *tag2)
665 {
666 return tagEqual(tag1, tag2);
667 }
668
TagMatchHash(bool match_crpr_clk_pin,const StaState * sta)669 TagMatchHash::TagMatchHash(bool match_crpr_clk_pin,
670 const StaState *sta) :
671 match_crpr_clk_pin_(match_crpr_clk_pin),
672 sta_(sta)
673 {
674 }
675
676 size_t
operator ()(const Tag * tag) const677 TagMatchHash::operator()(const Tag *tag) const
678 {
679 return tag->matchHash(match_crpr_clk_pin_);
680 }
681
TagMatchEqual(bool match_crpr_clk_pin,const StaState * sta)682 TagMatchEqual::TagMatchEqual(bool match_crpr_clk_pin,
683 const StaState *sta) :
684 match_crpr_clk_pin_(match_crpr_clk_pin),
685 sta_(sta)
686 {
687 }
688
689 bool
operator ()(const Tag * tag1,const Tag * tag2) const690 TagMatchEqual::operator()(const Tag *tag1,
691 const Tag *tag2) const
692 {
693 return tagMatch(tag1, tag2, match_crpr_clk_pin_, sta_);
694 }
695
696 } // namespace
697