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 "Crpr.hh"
18
19 #include <cmath> // abs
20 #include <stdio.h>
21
22 #include "Debug.hh"
23 #include "Vector.hh"
24 #include "Network.hh"
25 #include "Graph.hh"
26 #include "Sdc.hh"
27 #include "PathVertex.hh"
28 #include "PathVertexRep.hh"
29 #include "Path.hh"
30 #include "PathAnalysisPt.hh"
31 #include "ClkInfo.hh"
32 #include "Tag.hh"
33 #include "TagGroup.hh"
34 #include "VisitPathEnds.hh"
35 #include "PathEnd.hh"
36 #include "Search.hh"
37 #include "Genclks.hh"
38
39 namespace sta {
40
41 using std::min;
42 using std::abs;
43
CheckCrpr(StaState * sta)44 CheckCrpr::CheckCrpr(StaState *sta) :
45 StaState(sta)
46 {
47 }
48
49 PathVertex *
clkPathPrev(const PathVertex * path,PathVertex & tmp)50 CheckCrpr::clkPathPrev(const PathVertex *path,
51 PathVertex &tmp)
52
53 {
54 Vertex *vertex = path->vertex(this);
55 int arrival_index;
56 bool exists;
57 path->arrivalIndex(arrival_index, exists);
58 tmp = clkPathPrev(vertex, arrival_index);
59 if (tmp.isNull())
60 return nullptr;
61 else
62 return &tmp;
63 }
64
65 PathVertex
clkPathPrev(Vertex * vertex,int arrival_index)66 CheckCrpr::clkPathPrev(Vertex *vertex,
67 int arrival_index)
68 {
69 PathVertexRep *prevs = graph_->prevPaths(vertex);
70 if (prevs)
71 return PathVertex(prevs[arrival_index], this);
72 else {
73 criticalError(248, "missing prev paths");
74 return PathVertex();
75 }
76 }
77
78 ////////////////////////////////////////////////////////////////
79
80 // Find the maximum possible crpr (clock min/max delta delay) for a
81 // path from it's ClkInfo.
82 Arrival
maxCrpr(ClkInfo * clk_info)83 CheckCrpr::maxCrpr(ClkInfo *clk_info)
84 {
85 const PathVertexRep &crpr_clk_path = clk_info->crprClkPath();
86 if (!crpr_clk_path.isNull()) {
87 PathVertex crpr_clk_vpath(crpr_clk_path, this);
88 if (!crpr_clk_vpath.isNull()) {
89 Arrival other_arrival = otherMinMaxArrival(&crpr_clk_vpath);
90 float crpr_diff = abs(delayAsFloat(crpr_clk_vpath.arrival(this),
91 EarlyLate::late(),
92 this)
93 - delayAsFloat(other_arrival, EarlyLate::early(),
94 this));
95 return crpr_diff;
96 }
97 }
98 return 0.0F;
99 }
100
101 Arrival
otherMinMaxArrival(const PathVertex * path)102 CheckCrpr::otherMinMaxArrival(const PathVertex *path)
103 {
104 PathAnalysisPt *other_ap = path->pathAnalysisPt(this)->tgtClkAnalysisPt();
105 Tag *tag = path->tag(this);
106 VertexPathIterator other_iter(path->vertex(this),
107 path->transition(this),
108 other_ap, this);
109 while (other_iter.hasNext()) {
110 PathVertex *other = other_iter.next();
111 if (tagMatchCrpr(other->tag(this), tag))
112 return other->arrival(this);
113 }
114 // No corresponding path found.
115 // Match the arrival so the difference is zero.
116 return path->arrival(this);
117 }
118
119 Crpr
checkCrpr(const Path * src_path,const PathVertex * tgt_clk_path)120 CheckCrpr::checkCrpr(const Path *src_path,
121 const PathVertex *tgt_clk_path)
122 {
123 Crpr crpr;
124 Pin *crpr_pin;
125 checkCrpr(src_path, tgt_clk_path, crpr, crpr_pin);
126 return crpr;
127 }
128
129 void
checkCrpr(const Path * src_path,const PathVertex * tgt_clk_path,Crpr & crpr,Pin * & crpr_pin)130 CheckCrpr::checkCrpr(const Path *src_path,
131 const PathVertex *tgt_clk_path,
132 // Return values.
133 Crpr &crpr,
134 Pin *&crpr_pin)
135 {
136 crpr = 0.0;
137 crpr_pin = nullptr;
138 if (sdc_->crprActive()
139 && src_path && tgt_clk_path) {
140 bool same_pin = (sdc_->crprMode() == CrprMode::same_pin);
141 checkCrpr1(src_path, tgt_clk_path, same_pin, crpr, crpr_pin);
142 }
143 }
144
145 void
checkCrpr1(const Path * src_path,const PathVertex * tgt_clk_path,bool same_pin,Crpr & crpr,Pin * & crpr_pin)146 CheckCrpr::checkCrpr1(const Path *src_path,
147 const PathVertex *tgt_clk_path,
148 bool same_pin,
149 // Return values.
150 Crpr &crpr,
151 Pin *&crpr_pin)
152 {
153 crpr = 0.0;
154 crpr_pin = nullptr;
155 ClkInfo *src_clk_info = src_path->tag(this)->clkInfo();
156 ClkInfo *tgt_clk_info = tgt_clk_path->tag(this)->clkInfo();
157 Clock *src_clk = src_clk_info->clock();
158 Clock *tgt_clk = tgt_clk_info->clock();
159 const PathVertex src_clk_path1(src_clk_info->crprClkPath(), this);
160 const PathVertex *src_clk_path =
161 src_clk_path1.isNull() ? nullptr : &src_clk_path1;
162 const MinMax *src_clk_min_max =
163 src_clk_path ? src_clk_path->minMax(this) : src_path->minMax(this);
164 if (crprPossible(src_clk, tgt_clk)
165 && src_clk_info->isPropagated()
166 && tgt_clk_info->isPropagated()
167 // Note that crpr clk min/max is NOT the same as the path min max.
168 // For path from latches that are borrowing the enable path
169 // is from the opposite min/max of the data.
170 && src_clk_min_max != tgt_clk_path->minMax(this)
171 && (src_clk_path != nullptr
172 || src_clk->isGenerated())) {
173 // Src path from input port clk path can only be from generated clk path.
174 PathVertex port_clk_path;
175 if (src_clk_path == nullptr) {
176 portClkPath(src_clk_info->clkEdge(),
177 src_clk_info->clkSrc(),
178 src_path->pathAnalysisPt(this),
179 port_clk_path);
180 src_clk_path = &port_clk_path;
181 }
182 findCrpr(src_clk_path, tgt_clk_path, same_pin, crpr, crpr_pin);
183 }
184 }
185
186 // Find the clk path for an input/output port.
187 void
portClkPath(const ClockEdge * clk_edge,const Pin * clk_src_pin,const PathAnalysisPt * path_ap,PathVertex & genclk_path)188 CheckCrpr::portClkPath(const ClockEdge *clk_edge,
189 const Pin *clk_src_pin,
190 const PathAnalysisPt *path_ap,
191 // Return value.
192 PathVertex &genclk_path)
193 {
194 Vertex *clk_vertex = graph_->pinDrvrVertex(clk_src_pin);
195 VertexPathIterator path_iter(clk_vertex, clk_edge->transition(),
196 path_ap, this);
197 while (path_iter.hasNext()) {
198 PathVertex *path = path_iter.next();
199 if (path->clkEdge(this) == clk_edge
200 && path->isClock(this)) {
201 genclk_path = path;
202 break;
203 }
204 }
205 }
206
207 void
findCrpr(const PathVertex * src_clk_path,const PathVertex * tgt_clk_path,bool same_pin,Crpr & crpr,Pin * & crpr_pin)208 CheckCrpr::findCrpr(const PathVertex *src_clk_path,
209 const PathVertex *tgt_clk_path,
210 bool same_pin,
211 // Return values.
212 Crpr &crpr,
213 Pin *&crpr_pin)
214 {
215 crpr = 0.0;
216 crpr_pin = nullptr;
217 const PathVertex *src_clk_path1 = src_clk_path;
218 const PathVertex *tgt_clk_path1 = tgt_clk_path;
219 PathVertexSeq src_gclk_paths, tgt_gclk_paths;
220 if (src_clk_path1->clkInfo(this)->clkSrc()
221 != tgt_clk_path1->clkInfo(this)->clkSrc()) {
222 // Push src/tgt genclk src paths into a vector,
223 // The last genclk src path is at index 0.
224 genClkSrcPaths(src_clk_path1, src_gclk_paths);
225 genClkSrcPaths(tgt_clk_path1, tgt_gclk_paths);
226 // Search from the first gen clk toward the end
227 // of the path to find a common root pin.
228 int i = src_gclk_paths.size() - 1;
229 int j = tgt_gclk_paths.size() - 1;
230 for (; i >= 0 && j >= 0; i--, j--) {
231 PathVertex &src_path = src_gclk_paths[i];
232 PathVertex &tgt_path = tgt_gclk_paths[j];
233 if (src_path.clkInfo(this)->clkSrc()
234 == tgt_path.clkInfo(this)->clkSrc()) {
235 src_clk_path1 = &src_gclk_paths[i];
236 tgt_clk_path1 = &tgt_gclk_paths[j];
237 }
238 else
239 break;
240 }
241 }
242 const PathVertex *src_clk_path2 = src_clk_path1;
243 const PathVertex *tgt_clk_path2 = tgt_clk_path1;
244 PathVertex tmp1, tmp2;
245 // src_clk_path and tgt_clk_path are now in the same (gen)clk src path.
246 // Use the vertex levels to back up the deeper path to see if they
247 // overlap.
248 while (src_clk_path2 && tgt_clk_path2
249 && src_clk_path2->pin(this) != tgt_clk_path2->pin(this)) {
250 Level src_level = src_clk_path2->vertex(this)->level();
251 Level tgt_level = tgt_clk_path2->vertex(this)->level();
252 if (src_level >= tgt_level)
253 src_clk_path2 = clkPathPrev(src_clk_path2, tmp1);
254 if (tgt_level >= src_level)
255 tgt_clk_path2 = clkPathPrev(tgt_clk_path2, tmp2);
256 }
257 if (src_clk_path2 && tgt_clk_path2
258 && (src_clk_path2->transition(this) == tgt_clk_path2->transition(this)
259 || same_pin)) {
260 debugPrint(debug_, "crpr", 2, "crpr pin %s",
261 network_->pathName(src_clk_path2->pin(this)));
262 crpr = findCrpr1(src_clk_path2, tgt_clk_path2);
263 crpr_pin = src_clk_path2->pin(this);
264 }
265 }
266
267 void
genClkSrcPaths(const PathVertex * path,PathVertexSeq & gclk_paths)268 CheckCrpr::genClkSrcPaths(const PathVertex *path,
269 PathVertexSeq &gclk_paths)
270 {
271 ClkInfo *clk_info = path->clkInfo(this);
272 ClockEdge *clk_edge = clk_info->clkEdge();
273 const Pin *clk_src = clk_info->clkSrc();
274 PathAnalysisPt *path_ap = path->pathAnalysisPt(this);
275 gclk_paths.push_back(path);
276 while (clk_edge->clock()->isGenerated()) {
277 PathVertex genclk_path;
278 search_->genclks()->srcPath(clk_edge, clk_src, path_ap, genclk_path);
279 if (genclk_path.isNull())
280 break;
281 clk_info = genclk_path.clkInfo(this);
282 clk_src = clk_info->clkSrc();
283 clk_edge = clk_info->clkEdge();
284 gclk_paths.push_back(genclk_path);
285 }
286 }
287
288 Crpr
findCrpr1(const PathVertex * src_clk_path,const PathVertex * tgt_clk_path)289 CheckCrpr::findCrpr1(const PathVertex *src_clk_path,
290 const PathVertex *tgt_clk_path)
291 {
292 if (pocv_enabled_) {
293 // Remove variation on the common path.
294 // Note that the crpr sigma is negative to offset the
295 // sigma of the common clock path.
296 const EarlyLate *src_el = src_clk_path->minMax(this);
297 const EarlyLate *tgt_el = tgt_clk_path->minMax(this);
298 Arrival src_arrival = src_clk_path->arrival(this);
299 Arrival tgt_arrival = tgt_clk_path->arrival(this);
300 float src_clk_time = src_clk_path->clkEdge(this)->time();
301 float tgt_clk_time = tgt_clk_path->clkEdge(this)->time();
302 float crpr_mean = abs(delayAsFloat(src_arrival) - src_clk_time
303 - (delayAsFloat(tgt_arrival) - tgt_clk_time));
304 // Remove the sigma from both source and target path arrivals.
305 float crpr_sigma2 = delaySigma2(src_arrival, src_el)
306 + delaySigma2(tgt_arrival, tgt_el);
307 return makeDelay2(crpr_mean, -crpr_sigma2, -crpr_sigma2);
308 }
309 else {
310 // The source and target edges are different so the crpr
311 // is the min of the source and target max-min delay.
312 float src_delta = crprArrivalDiff(src_clk_path);
313 float tgt_delta = crprArrivalDiff(tgt_clk_path);
314 debugPrint(debug_, "crpr", 2, " src delta %s",
315 delayAsString(src_delta, this));
316 debugPrint(debug_, "crpr", 2, " tgt delta %s",
317 delayAsString(tgt_delta, this));
318 float common_delay = min(src_delta, tgt_delta);
319 debugPrint(debug_, "crpr", 2, " %s delta %s",
320 network_->pathName(src_clk_path->pin(this)),
321 delayAsString(common_delay, this));
322 return common_delay;
323 }
324 }
325
326 float
crprArrivalDiff(const PathVertex * path)327 CheckCrpr::crprArrivalDiff(const PathVertex *path)
328 {
329 Arrival other_arrival = otherMinMaxArrival(path);
330 float crpr_diff = abs(delayAsFloat(path->arrival(this))
331 - delayAsFloat(other_arrival));
332 return crpr_diff;
333 }
334
335 Crpr
outputDelayCrpr(const Path * src_clk_path,const ClockEdge * tgt_clk_edge)336 CheckCrpr::outputDelayCrpr(const Path *src_clk_path,
337 const ClockEdge *tgt_clk_edge)
338 {
339 Crpr crpr;
340 Pin *crpr_pin;
341 outputDelayCrpr(src_clk_path, tgt_clk_edge, crpr, crpr_pin);
342 return crpr;
343 }
344
345 void
outputDelayCrpr(const Path * src_path,const ClockEdge * tgt_clk_edge,Crpr & crpr,Pin * & crpr_pin)346 CheckCrpr::outputDelayCrpr(const Path *src_path,
347 const ClockEdge *tgt_clk_edge,
348 // Return values.
349 Crpr &crpr,
350 Pin *&crpr_pin)
351 {
352 crpr = 0.0;
353 crpr_pin = nullptr;
354 if (sdc_->crprActive()) {
355 const PathAnalysisPt *path_ap = src_path->pathAnalysisPt(this);
356 const PathAnalysisPt *tgt_path_ap = path_ap->tgtClkAnalysisPt();
357 bool same_pin = (sdc_->crprMode() == CrprMode::same_pin);
358 outputDelayCrpr1(src_path,tgt_clk_edge,tgt_path_ap, same_pin,
359 crpr, crpr_pin);
360 }
361 }
362
363 void
outputDelayCrpr1(const Path * src_path,const ClockEdge * tgt_clk_edge,const PathAnalysisPt * tgt_path_ap,bool same_pin,Crpr & crpr,Pin * & crpr_pin)364 CheckCrpr::outputDelayCrpr1(const Path *src_path,
365 const ClockEdge *tgt_clk_edge,
366 const PathAnalysisPt *tgt_path_ap,
367 bool same_pin,
368 // Return values.
369 Crpr &crpr,
370 Pin *&crpr_pin)
371 {
372 crpr = 0.0;
373 crpr_pin = nullptr;
374 ClkInfo *src_clk_info = src_path->tag(this)->clkInfo();
375 Clock *tgt_clk = tgt_clk_edge->clock();
376 Clock *src_clk = src_path->clock(this);
377 if (src_clk_info->isPropagated()
378 && tgt_clk->isGenerated()
379 && tgt_clk->isPropagated()
380 && crprPossible(src_clk, tgt_clk)) {
381 PathVertex tgt_genclk_path;
382 portClkPath(tgt_clk_edge, tgt_clk_edge->clock()->defaultPin(), tgt_path_ap,
383 tgt_genclk_path);
384 PathVertex src_clk_path(src_path->clkInfo(this)->crprClkPath(), this);
385 if (!src_clk_path.isNull()) {
386 findCrpr(&src_clk_path, &tgt_genclk_path, same_pin, crpr, crpr_pin);
387 }
388 }
389 }
390
391 bool
crprPossible(Clock * clk1,Clock * clk2)392 CheckCrpr::crprPossible(Clock *clk1,
393 Clock *clk2)
394 {
395 return clk1 && clk2
396 && !clk1->isVirtual()
397 && !clk2->isVirtual()
398 // Generated clocks can have crpr in the source path.
399 && (clk1 == clk2
400 || clk1->isGenerated()
401 || clk2->isGenerated()
402 // Different non-generated clocks with the same source pins (using -add).
403 || PinSet::intersects(clk1->pins(), clk2->pins()));
404 }
405
406 } // namespace
407