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 "Clock.hh"
18
19 #include <algorithm>
20
21 #include "Error.hh"
22 #include "StringUtil.hh"
23 #include "MinMax.hh"
24 #include "Transition.hh"
25 #include "TimingRole.hh"
26 #include "Network.hh"
27 #include "Graph.hh"
28 #include "Sdc.hh"
29
30 namespace sta {
31
32 static bool
33 isPowerOfTwo(int i);
34
Clock(const char * name,int index)35 Clock::Clock(const char *name,
36 int index) :
37 name_(stringCopy(name)),
38 add_to_pins_(false),
39 pll_out_(nullptr),
40 pll_fdbk_(nullptr),
41 period_(0.0),
42 waveform_(nullptr),
43 waveform_valid_(false),
44 index_(index),
45 clk_edges_(nullptr),
46 is_propagated_(false),
47 uncertainties_(nullptr),
48 is_generated_(false),
49 src_pin_(nullptr),
50 master_clk_(nullptr),
51 master_clk_infered_(false),
52 divide_by_(0),
53 multiply_by_(0),
54 duty_cycle_(0),
55 invert_(false),
56 combinational_(false),
57 edges_(nullptr),
58 edge_shifts_(nullptr)
59 {
60 makeClkEdges();
61 }
62
63 void
initClk(PinSet * pins,bool add_to_pins,float period,FloatSeq * waveform,const char * comment,const Network * network)64 Clock::initClk(PinSet *pins,
65 bool add_to_pins,
66 float period,
67 FloatSeq *waveform,
68 const char *comment,
69 const Network *network)
70 {
71 is_generated_ = false;
72 setPins(pins, network);
73 add_to_pins_ = add_to_pins;
74 delete waveform_;
75 waveform_ = waveform;
76 waveform_valid_ = true;
77 period_ = period;
78 setClkEdgeTimes();
79 setComment(comment);
80 }
81
82 bool
isVirtual() const83 Clock::isVirtual() const
84 {
85 return pins_.empty();
86 }
87
88 void
setPins(PinSet * pins,const Network * network)89 Clock::setPins(PinSet *pins,
90 const Network *network)
91 {
92 if (pins)
93 pins_ = *pins;
94 delete pins;
95 makeLeafPins(network);
96 }
97
98 void
makeLeafPins(const Network * network)99 Clock::makeLeafPins(const Network *network)
100 {
101 leaf_pins_.clear();
102 PinSet::Iterator pin_iter(pins_);
103 while (pin_iter.hasNext()) {
104 Pin *pin = pin_iter.next();
105 findLeafDriverPins(pin, network, &leaf_pins_);
106 }
107 }
108
109 void
setMasterClk(Clock * master)110 Clock::setMasterClk(Clock *master)
111 {
112 master_clk_ = master;
113 waveform_valid_ = false;
114 }
115
116 void
makeClkEdges()117 Clock::makeClkEdges()
118 {
119 clk_edges_ = new ClockEdge*[RiseFall::index_count];
120 for (auto tr : RiseFall::range()) {
121 clk_edges_[tr->index()] = new ClockEdge(this, tr);
122 }
123 }
124
~Clock()125 Clock::~Clock()
126 {
127 stringDelete(name_);
128 if (clk_edges_) {
129 delete clk_edges_[RiseFall::riseIndex()];
130 delete clk_edges_[RiseFall::fallIndex()];
131 delete [] clk_edges_;
132 }
133 delete waveform_;
134 delete edges_;
135 delete edge_shifts_;
136 delete uncertainties_;
137 }
138
139 void
addPin(Pin * pin)140 Clock::addPin(Pin *pin)
141 {
142 pins_.insert(pin);
143 leaf_pins_.insert(pin);
144 }
145
146 void
deletePin(Pin * pin)147 Clock::deletePin(Pin *pin)
148 {
149 pins_.erase(pin);
150 }
151
152 void
setAddToPins(bool add_to_pins)153 Clock::setAddToPins(bool add_to_pins)
154 {
155 add_to_pins_ = add_to_pins;
156 }
157
158 void
setClkEdgeTimes()159 Clock::setClkEdgeTimes()
160 {
161 setClkEdgeTime(RiseFall::rise());
162 setClkEdgeTime(RiseFall::fall());
163 }
164
165 void
setClkEdgeTime(const RiseFall * rf)166 Clock::setClkEdgeTime(const RiseFall *rf)
167 {
168 float time = (rf == RiseFall::rise()) ? (*waveform_)[0]:(*waveform_)[1];
169 clk_edges_[rf->index()]->setTime(time);
170 }
171
172 Pin *
defaultPin() const173 Clock::defaultPin() const
174 {
175 PinSet::ConstIterator pin_iter(leaf_pins_);
176 if (pin_iter.hasNext())
177 return pin_iter.next();
178 else
179 return nullptr;
180 }
181
182 ClockEdge *
edge(const RiseFall * rf) const183 Clock::edge(const RiseFall *rf) const
184 {
185 return clk_edges_[rf->index()];
186 }
187
188 void
setIsPropagated(bool propagated)189 Clock::setIsPropagated(bool propagated)
190 {
191 is_propagated_ = propagated;
192 }
193
194 void
slew(const RiseFall * rf,const MinMax * min_max,float & slew,bool & exists) const195 Clock::slew(const RiseFall *rf,
196 const MinMax *min_max,
197 // Return values.
198 float &slew,
199 bool &exists) const
200 {
201 slews_.value(rf, min_max, slew, exists);
202 }
203
204 float
slew(const RiseFall * rf,const MinMax * min_max) const205 Clock::slew(const RiseFall *rf,
206 const MinMax *min_max) const
207 {
208 float slew;
209 bool exists;
210 slews_.value(rf, min_max, slew, exists);
211 if (!exists)
212 slew = 0.0;
213 return slew;
214 }
215
216 void
setSlew(const RiseFallBoth * rf,const MinMaxAll * min_max,float slew)217 Clock::setSlew(const RiseFallBoth *rf,
218 const MinMaxAll *min_max,
219 float slew)
220 {
221 slews_.setValue(rf, min_max, slew);
222 }
223
224 void
setSlew(const RiseFall * rf,const MinMax * min_max,float slew)225 Clock::setSlew(const RiseFall *rf,
226 const MinMax *min_max,
227 float slew)
228 {
229 slews_.setValue(rf, min_max, slew);
230 }
231
232 void
removeSlew()233 Clock::removeSlew()
234 {
235 slews_.clear();
236 }
237
238 void
setSlewLimit(const RiseFallBoth * rf,const PathClkOrData clk_data,const MinMax * min_max,float slew)239 Clock::setSlewLimit(const RiseFallBoth *rf,
240 const PathClkOrData clk_data,
241 const MinMax *min_max,
242 float slew)
243 {
244 slew_limits_[int(clk_data)].setValue(rf, min_max, slew);
245 }
246
247 void
slewLimit(const RiseFall * rf,const PathClkOrData clk_data,const MinMax * min_max,float & slew,bool & exists) const248 Clock::slewLimit(const RiseFall *rf,
249 const PathClkOrData clk_data,
250 const MinMax *min_max,
251 // Return values.
252 float &slew,
253 bool &exists) const
254 {
255 slew_limits_[int(clk_data)].value(rf, min_max, slew, exists);
256 }
257
258 void
uncertainty(const SetupHold * setup_hold,float & uncertainty,bool & exists) const259 Clock::uncertainty(const SetupHold *setup_hold,
260 // Return values.
261 float &uncertainty,
262 bool &exists) const
263 {
264 if (uncertainties_)
265 uncertainties_->value(setup_hold, uncertainty, exists);
266 else {
267 uncertainty = 0.0F;
268 exists = false;
269 }
270 }
271
272 void
setUncertainty(const SetupHoldAll * setup_hold,float uncertainty)273 Clock::setUncertainty(const SetupHoldAll *setup_hold,
274 float uncertainty)
275 {
276 if (uncertainties_ == nullptr)
277 uncertainties_ = new ClockUncertainties;
278 uncertainties_->setValue(setup_hold, uncertainty);
279 }
280
281 void
setUncertainty(const SetupHold * setup_hold,float uncertainty)282 Clock::setUncertainty(const SetupHold *setup_hold,
283 float uncertainty)
284 {
285 if (uncertainties_ == nullptr)
286 uncertainties_ = new ClockUncertainties;
287 uncertainties_->setValue(setup_hold, uncertainty);
288 }
289
290 void
removeUncertainty(const SetupHoldAll * setup_hold)291 Clock::removeUncertainty(const SetupHoldAll *setup_hold)
292 {
293 if (uncertainties_) {
294 uncertainties_->removeValue(setup_hold);
295 if (uncertainties_->empty()) {
296 delete uncertainties_;
297 uncertainties_ = nullptr;
298 }
299 }
300 }
301
302 void
waveformInvalid()303 Clock::waveformInvalid()
304 {
305 waveform_valid_ = false;
306 }
307
308 ////////////////////////////////////////////////////////////////
309
310 void
initGeneratedClk(PinSet * pins,bool add_to_pins,Pin * src_pin,Clock * master_clk,Pin * pll_out,Pin * pll_fdbk,int divide_by,int multiply_by,float duty_cycle,bool invert,bool combinational,IntSeq * edges,FloatSeq * edge_shifts,bool is_propagated,const char * comment,const Network * network)311 Clock::initGeneratedClk(PinSet *pins,
312 bool add_to_pins,
313 Pin *src_pin,
314 Clock *master_clk,
315 Pin *pll_out,
316 Pin *pll_fdbk,
317 int divide_by,
318 int multiply_by,
319 float duty_cycle,
320 bool invert,
321 bool combinational,
322 IntSeq *edges,
323 FloatSeq *edge_shifts,
324 bool is_propagated,
325 const char *comment,
326 const Network *network)
327 {
328 is_generated_ = true;
329 setPins(pins, network);
330 add_to_pins_ = add_to_pins;
331 src_pin_ = src_pin;
332 master_clk_ = master_clk;
333 master_clk_infered_ = false;
334 waveform_valid_ = false;
335 pll_out_= pll_out;
336 pll_fdbk_ = pll_fdbk;
337 divide_by_ = divide_by;
338 multiply_by_ = multiply_by;
339 duty_cycle_ = duty_cycle;
340 invert_ = invert;
341 combinational_ = combinational;
342 is_propagated_ = is_propagated;
343 setComment(comment);
344
345 delete edges_;
346 if (edges
347 && edges->empty()) {
348 delete edges;
349 edges = nullptr;
350 }
351 edges_ = edges;
352
353 delete edge_shifts_;
354 if (edge_shifts
355 && edge_shifts->empty()) {
356 delete edge_shifts;
357 edge_shifts = nullptr;
358 }
359 edge_shifts_ = edge_shifts;
360 }
361
362 void
setInferedMasterClk(Clock * master_clk)363 Clock::setInferedMasterClk(Clock *master_clk)
364 {
365 master_clk_ = master_clk;
366 master_clk_infered_ = true;
367 waveform_valid_ = false;
368 }
369
370 bool
isGenerated() const371 Clock::isGenerated() const
372 {
373 return is_generated_;
374 }
375
376 bool
isGeneratedWithPropagatedMaster() const377 Clock::isGeneratedWithPropagatedMaster() const
378 {
379 return is_generated_
380 && master_clk_
381 // Insertion is zero if the master clock is ideal.
382 && master_clk_->isPropagated();
383 }
384
385 void
generate(const Clock * src_clk)386 Clock::generate(const Clock *src_clk)
387 {
388 if (waveform_ == nullptr)
389 waveform_ = new FloatSeq;
390 else
391 waveform_->clear();
392
393 if (divide_by_ == 1.0) {
394 period_ = src_clk->period();
395 const FloatSeq *src_wave = src_clk->waveform();
396 waveform_->push_back((*src_wave)[0]);
397 waveform_->push_back((*src_wave)[1]);
398 }
399 else if (divide_by_ > 1) {
400 if (isPowerOfTwo(divide_by_)) {
401 period_ = src_clk->period() * divide_by_;
402 const FloatSeq *src_wave = src_clk->waveform();
403 float rise = (*src_wave)[0];
404 waveform_->push_back(rise);
405 waveform_->push_back(rise + period_ / 2);
406 }
407 else
408 generateScaledClk(src_clk, static_cast<float>(divide_by_));
409 }
410 else if (multiply_by_ >= 1)
411 generateScaledClk(src_clk, 1.0F / multiply_by_);
412 else if (edges_)
413 generateEdgesClk(src_clk);
414
415 if (invert_) {
416 float first_time = (*waveform_)[0];
417 float offset = (first_time >= period_) ? period_ : 0.0F;
418 size_t edge_count = waveform_->size();
419 for (size_t i = 0; i < edge_count - 1; i++)
420 (*waveform_)[i] = (*waveform_)[i + 1] - offset;
421 (*waveform_)[edge_count - 1] = first_time - offset + period_;
422 }
423 setClkEdgeTimes();
424 waveform_valid_ = true;
425 }
426
427 void
generateScaledClk(const Clock * src_clk,float scale)428 Clock::generateScaledClk(const Clock *src_clk,
429 float scale)
430 {
431 period_ = src_clk->period() * scale;
432 if (duty_cycle_ != 0.0) {
433 float rise = (*src_clk->waveform())[0] * scale;
434 waveform_->push_back(rise);
435 waveform_->push_back(rise + period_ * duty_cycle_ / 100.0F);
436 }
437 else {
438 FloatSeq::ConstIterator wave_iter(src_clk->waveform());
439 while (wave_iter.hasNext()) {
440 float time = wave_iter.next();
441 waveform_->push_back(time * scale);
442 }
443 }
444 }
445
446 void
generateEdgesClk(const Clock * src_clk)447 Clock::generateEdgesClk(const Clock *src_clk)
448 {
449 // The create_generated_clock tcl cmd and Sta::makeClock
450 // enforce this restriction.
451 if (edges_->size() == 3) {
452 const FloatSeq *src_wave = src_clk->waveform();
453 size_t src_size = src_wave->size();
454 float src_period = src_clk->period();
455
456 int edge0_1 = (*edges_)[0] - 1;
457 float rise = (*src_wave)[edge0_1 % src_size]
458 + (edge0_1 / src_size) * src_period;
459 if (edge_shifts_)
460 rise += (*edge_shifts_)[0];
461 waveform_->push_back(rise);
462
463 int edge1_1 = (*edges_)[1] - 1;
464 float fall = (*src_wave)[edge1_1 % src_size]
465 + (edge1_1 / src_size) * src_period;
466 if (edge_shifts_)
467 fall += (*edge_shifts_)[1];
468 waveform_->push_back(fall);
469
470 int edge2_1 = (*edges_)[2] - 1;
471 period_ = (*src_wave)[edge2_1 % src_size]
472 + (edge2_1 / src_size) * src_period - rise;
473 if (edge_shifts_)
474 period_ += (*edge_shifts_)[2];
475 }
476 else
477 criticalError(244, "generated clock edges size is not three.");
478 }
479
480 static bool
isPowerOfTwo(int i)481 isPowerOfTwo(int i)
482 {
483 return (i & (i - 1)) == 0;
484 }
485
486 const RiseFall *
masterClkEdgeTr(const RiseFall * rf) const487 Clock::masterClkEdgeTr(const RiseFall *rf) const
488 {
489 int edge_index = (rf == RiseFall::rise()) ? 0 : 1;
490 return ((*edges_)[edge_index] - 1) % 2
491 ? RiseFall::fall()
492 : RiseFall::rise();
493 }
494
495 void
srcPinVertices(VertexSet & src_vertices,const Network * network,Graph * graph)496 Clock::srcPinVertices(VertexSet &src_vertices,
497 const Network *network,
498 Graph *graph)
499 {
500 if (network->isHierarchical(src_pin_)) {
501 // Use the clocks on a non-hierarchical pin on the same net.
502 PinSet leaf_pins;
503 findLeafDriverPins(src_pin_, network, &leaf_pins);
504 PinSet::Iterator pin_iter(leaf_pins);
505 while (pin_iter.hasNext()) {
506 Pin *pin = pin_iter.next();
507 Vertex *vertex, *bidirect_drvr_vertex;
508 graph->pinVertices(pin, vertex, bidirect_drvr_vertex);
509 if (vertex)
510 src_vertices.insert(vertex);
511 if (bidirect_drvr_vertex)
512 src_vertices.insert(bidirect_drvr_vertex);
513 }
514 }
515 else {
516 Vertex *vertex = graph->pinDrvrVertex(src_pin_);
517 src_vertices.insert(vertex);
518 }
519 }
520
521 bool
isDivideByOneCombinational() const522 Clock::isDivideByOneCombinational() const
523 {
524 return combinational_
525 && divide_by_ == 1
526 && multiply_by_ == 0
527 && edge_shifts_ == 0;
528 }
529
530 ////////////////////////////////////////////////////////////////
531
ClockEdge(Clock * clock,RiseFall * rf)532 ClockEdge::ClockEdge(Clock *clock,
533 RiseFall *rf) :
534 clock_(clock),
535 rf_(rf),
536 name_(stringPrint("%s %s", clock_->name(), rf_->asString())),
537 time_(0.0),
538 index_(clock_->index() * RiseFall::index_count + rf_->index())
539 {
540 }
541
~ClockEdge()542 ClockEdge::~ClockEdge()
543 {
544 stringDelete(name_);
545 }
546
547 void
setTime(float time)548 ClockEdge::setTime(float time)
549 {
550 time_ = time;
551 }
552
553 ClockEdge *
opposite() const554 ClockEdge::opposite() const
555 {
556 return clock_->edge(rf_->opposite());
557 }
558
559 float
pulseWidth() const560 ClockEdge::pulseWidth() const
561 {
562 ClockEdge *opp_clk_edge = opposite();
563 float width = opp_clk_edge->time() - time_;
564 if (width < 0.0)
565 width += clock_->period();
566 return width;
567 }
568
569 ////////////////////////////////////////////////////////////////
570
571 int
clkCmp(const Clock * clk1,const Clock * clk2)572 clkCmp(const Clock *clk1,
573 const Clock *clk2)
574 {
575 if (clk1 == nullptr && clk2)
576 return -1;
577 else if (clk1 == nullptr && clk2 == nullptr)
578 return 0;
579 else if (clk1 && clk2 == nullptr)
580 return 1;
581 else {
582 int index1 = clk1->index();
583 int index2 = clk2->index();
584 if (index1 < index2)
585 return -1;
586 else if (index1 == index2)
587 return 0;
588 else
589 return 1;
590 }
591 }
592
593 int
clkEdgeCmp(ClockEdge * clk_edge1,ClockEdge * clk_edge2)594 clkEdgeCmp(ClockEdge *clk_edge1,
595 ClockEdge *clk_edge2)
596 {
597 if (clk_edge1 == nullptr && clk_edge2)
598 return -1;
599 else if (clk_edge1 == nullptr && clk_edge2 == nullptr)
600 return 0;
601 else if (clk_edge1 && clk_edge2 == nullptr)
602 return 1;
603 else {
604 int index1 = clk_edge1->index();
605 int index2 = clk_edge2->index();
606 if (index1 == index2)
607 return 0;
608 else if (index1 < index2)
609 return -1;
610 else
611 return 1;
612 }
613 }
614
615 bool
clkEdgeLess(ClockEdge * clk_edge1,ClockEdge * clk_edge2)616 clkEdgeLess(ClockEdge *clk_edge1,
617 ClockEdge *clk_edge2)
618 {
619 return clkEdgeCmp(clk_edge1, clk_edge2) < 0;
620 }
621
622 ////////////////////////////////////////////////////////////////
623
InterClockUncertainty(const Clock * src,const Clock * target)624 InterClockUncertainty::InterClockUncertainty(const Clock *src,
625 const Clock *target) :
626 src_(src),
627 target_(target)
628 {
629 }
630
631 bool
empty() const632 InterClockUncertainty::empty() const
633 {
634 return uncertainties_[RiseFall::riseIndex()].empty()
635 && uncertainties_[RiseFall::fallIndex()].empty();
636 }
637
638 void
uncertainty(const RiseFall * src_rf,const RiseFall * tgt_rf,const SetupHold * setup_hold,float & uncertainty,bool & exists) const639 InterClockUncertainty::uncertainty(const RiseFall *src_rf,
640 const RiseFall *tgt_rf,
641 const SetupHold *setup_hold,
642 float &uncertainty,
643 bool &exists) const
644 {
645 uncertainties_[src_rf->index()].value(tgt_rf, setup_hold,
646 uncertainty, exists);
647 }
648
649 void
setUncertainty(const RiseFallBoth * src_rf,const RiseFallBoth * tgt_rf,const SetupHoldAll * setup_hold,float uncertainty)650 InterClockUncertainty::setUncertainty(const RiseFallBoth *src_rf,
651 const RiseFallBoth *tgt_rf,
652 const SetupHoldAll *setup_hold,
653 float uncertainty)
654 {
655 for (auto src_rf_index : src_rf->rangeIndex())
656 uncertainties_[src_rf_index].setValue(tgt_rf, setup_hold, uncertainty);
657 }
658
659 void
removeUncertainty(const RiseFallBoth * src_rf,const RiseFallBoth * tgt_rf,const SetupHoldAll * setup_hold)660 InterClockUncertainty::removeUncertainty(const RiseFallBoth *src_rf,
661 const RiseFallBoth *tgt_rf,
662 const SetupHoldAll *setup_hold)
663 {
664 for (auto src_rf_index : src_rf->rangeIndex())
665 uncertainties_[src_rf_index].removeValue(tgt_rf, setup_hold);
666 }
667
668 const RiseFallMinMax *
uncertainties(RiseFall * src_rf) const669 InterClockUncertainty::uncertainties(RiseFall *src_rf) const
670 {
671 return &uncertainties_[src_rf->index()];
672 }
673
674 bool
operator ()(const InterClockUncertainty * inter1,const InterClockUncertainty * inter2) const675 InterClockUncertaintyLess::operator()(const InterClockUncertainty *inter1,
676 const InterClockUncertainty *inter2)const
677 {
678 return inter1->src()->index() < inter2->src()->index()
679 || (inter1->src() == inter2->src()
680 && inter1->target()->index() < inter2->target()->index());
681 }
682
683 ////////////////////////////////////////////////////////////////
684
685 bool
operator ()(const Clock * clk1,const Clock * clk2)686 ClockNameLess::operator()(const Clock *clk1,
687 const Clock *clk2)
688 {
689 return stringLess(clk1->name(), clk2->name());
690 }
691
692 void
sortClockSet(ClockSet * set,ClockSeq & clks)693 sortClockSet(ClockSet *set,
694 ClockSeq &clks)
695 {
696 ClockSet::Iterator clk_iter(set);
697 while (clk_iter.hasNext())
698 clks.push_back(clk_iter.next());
699 sort(clks, ClockNameLess());
700 }
701
702 } // namespace
703