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 "CheckTiming.hh"
18
19 #include "Error.hh"
20 #include "TimingRole.hh"
21 #include "Network.hh"
22 #include "NetworkCmp.hh"
23 #include "PortDirection.hh"
24 #include "Graph.hh"
25 #include "PortDelay.hh"
26 #include "ExceptionPath.hh"
27 #include "Sdc.hh"
28 #include "SearchPred.hh"
29 #include "Levelize.hh"
30 #include "Bfs.hh"
31 #include "Search.hh"
32 #include "Genclks.hh"
33 #include "PathVertex.hh"
34
35 namespace sta {
36
37 using std::string;
38
CheckTiming(StaState * sta)39 CheckTiming::CheckTiming(StaState *sta) :
40 StaState(sta)
41 {
42 }
43
~CheckTiming()44 CheckTiming::~CheckTiming()
45 {
46 deleteErrors();
47 }
48
49 void
deleteErrors()50 CheckTiming::deleteErrors()
51 {
52 CheckErrorSeq::Iterator error_iter(errors_);
53 while (error_iter.hasNext()) {
54 CheckError *error = error_iter.next();
55 deleteContents(error);
56 delete error;
57 }
58 }
59
60 void
clear()61 CheckTiming::clear()
62 {
63 deleteErrors();
64 errors_.clear();
65 }
66
67 CheckErrorSeq &
check(bool no_input_delay,bool no_output_delay,bool reg_multiple_clks,bool reg_no_clks,bool unconstrained_endpoints,bool loops,bool generated_clks)68 CheckTiming::check(bool no_input_delay,
69 bool no_output_delay,
70 bool reg_multiple_clks,
71 bool reg_no_clks,
72 bool unconstrained_endpoints,
73 bool loops,
74 bool generated_clks)
75 {
76 clear();
77 if (no_input_delay)
78 checkNoInputDelay();
79 if (no_output_delay)
80 checkNoOutputDelay();
81 if (reg_multiple_clks || reg_no_clks)
82 checkRegClks(reg_multiple_clks, reg_no_clks);
83 if (unconstrained_endpoints)
84 checkUnconstrainedEndpoints();
85 if (loops)
86 checkLoops();
87 if (generated_clks)
88 checkGeneratedClocks();
89 return errors_;
90 }
91
92 // Make sure there is a set_input_delay for each input/bidirect.
93 void
checkNoInputDelay()94 CheckTiming::checkNoInputDelay()
95 {
96 PinSet no_arrival;
97 Instance *top_inst = network_->topInstance();
98 InstancePinIterator *pin_iter = network_->pinIterator(top_inst);
99 while (pin_iter->hasNext()) {
100 Pin *pin = pin_iter->next();
101 if (!sdc_->isClock(pin)) {
102 PortDirection *dir = network_->direction(pin);
103 if (dir->isAnyInput()
104 && !sdc_->hasInputDelay(pin))
105 no_arrival.insert(pin);
106 }
107 }
108 delete pin_iter;
109 pushPinErrors("Warning: There %is %d input port%s missing set_input_delay.",
110 no_arrival);
111 }
112
113 void
checkNoOutputDelay()114 CheckTiming::checkNoOutputDelay()
115 {
116 PinSet no_departure;
117 checkNoOutputDelay(no_departure);
118 pushPinErrors("Warning: There %is %d output port%s missing set_output_delay.",
119 no_departure);
120 }
121
122 void
checkNoOutputDelay(PinSet & no_departure)123 CheckTiming::checkNoOutputDelay(PinSet &no_departure)
124 {
125 Instance *top_inst = network_->topInstance();
126 InstancePinIterator *pin_iter = network_->pinIterator(top_inst);
127 while (pin_iter->hasNext()) {
128 Pin *pin = pin_iter->next();
129 PortDirection *dir = network_->direction(pin);
130 if (dir->isAnyOutput()
131 && !sdc_->hasOutputDelay(pin))
132 no_departure.insert(pin);
133 }
134 delete pin_iter;
135 }
136
137 bool
hasClkedCheck(Vertex * vertex)138 CheckTiming::hasClkedCheck(Vertex *vertex)
139 {
140 VertexInEdgeIterator edge_iter(vertex, graph_);
141 while (edge_iter.hasNext()) {
142 Edge *edge = edge_iter.next();
143 if (edge->role() == TimingRole::setup()
144 && search_->isClock(edge->from(graph_)))
145 return true;
146 }
147 return false;
148 }
149
150 // Search incrementally maintains register/latch clock pins, so use it.
151 void
checkRegClks(bool reg_multiple_clks,bool reg_no_clks)152 CheckTiming::checkRegClks(bool reg_multiple_clks,
153 bool reg_no_clks)
154 {
155 PinSet no_clk_pins, multiple_clk_pins;
156 VertexSet::ConstIterator reg_clk_iter(graph_->regClkVertices());
157 while (reg_clk_iter.hasNext()) {
158 Vertex *vertex = reg_clk_iter.next();
159 Pin *pin = vertex->pin();
160 ClockSet clks;
161 search_->clocks(vertex, clks);
162 if (reg_no_clks && clks.empty())
163 no_clk_pins.insert(pin);
164 if (reg_multiple_clks && clks.size() > 1)
165 multiple_clk_pins.insert(pin);
166 }
167 pushPinErrors("Warning: There %is %d unclocked register/latch pin%s.",
168 no_clk_pins);
169 pushPinErrors("Warning: There %is %d register/latch pin%s with multiple clocks.",
170 multiple_clk_pins);
171 }
172
173 void
checkLoops()174 CheckTiming::checkLoops()
175 {
176 // These may not need to be sorted because the graph roots are
177 // sorted during levelization so the discovery should be consistent.
178 GraphLoopSeq *loops = levelize_->loops();
179 // Count the combinational loops.
180 int loop_count = 0;
181 GraphLoopSeq::Iterator loop_iter1(loops);
182 while (loop_iter1.hasNext()) {
183 GraphLoop *loop = loop_iter1.next();
184 if (loop->isCombinational())
185 loop_count++;
186 }
187 if (loop_count > 0) {
188 string error_msg;
189 errorMsgSubst("Warning: There %is %d combinational loop%s in the design.",
190 loop_count, error_msg);
191 CheckError *error = new CheckError;
192 error->push_back(stringCopy(error_msg.c_str()));
193
194 GraphLoopSeq::Iterator loop_iter2(loops);
195 while (loop_iter2.hasNext()) {
196 GraphLoop *loop = loop_iter2.next();
197 if (loop->isCombinational()) {
198 EdgeSeq::Iterator edge_iter(loop->edges());
199 Edge *last_edge = nullptr;
200 while (edge_iter.hasNext()) {
201 Edge *edge = edge_iter.next();
202 Pin *pin = edge->from(graph_)->pin();
203 const char *pin_name = stringCopy(sdc_network_->pathName(pin));
204 error->push_back(pin_name);
205 last_edge = edge;
206 }
207 error->push_back(stringCopy("| loop cut point"));
208 const Pin *pin = last_edge->to(graph_)->pin();
209 const char *pin_name = stringCopy(sdc_network_->pathName(pin));
210 error->push_back(pin_name);
211
212 // Separator between loops.
213 error->push_back(stringCopy("--------------------------------"));
214 }
215 }
216 errors_.push_back(error);
217 }
218 }
219
220 void
checkUnconstrainedEndpoints()221 CheckTiming::checkUnconstrainedEndpoints()
222 {
223 PinSet unconstrained_ends;
224 checkUnconstraintedOutputs(unconstrained_ends);
225 checkUnconstrainedSetups(unconstrained_ends);
226 pushPinErrors("Warning: There %is %d unconstrained endpoint%s.",
227 unconstrained_ends);
228 }
229
230 void
checkUnconstraintedOutputs(PinSet & unconstrained_ends)231 CheckTiming::checkUnconstraintedOutputs(PinSet &unconstrained_ends)
232 {
233 Instance *top_inst = network_->topInstance();
234 InstancePinIterator *pin_iter = network_->pinIterator(top_inst);
235 while (pin_iter->hasNext()) {
236 Pin *pin = pin_iter->next();
237 PortDirection *dir = network_->direction(pin);
238 if (dir->isAnyOutput()
239 && !((hasClkedDepature(pin)
240 && hasClkedArrival(graph_->pinLoadVertex(pin)))
241 || hasMaxDelay(pin)))
242 unconstrained_ends.insert(pin);
243 }
244 delete pin_iter;
245 }
246
247 bool
hasClkedDepature(Pin * pin)248 CheckTiming::hasClkedDepature(Pin *pin)
249 {
250 OutputDelaySet *output_delays = sdc_->outputDelaysLeafPin(pin);
251 if (output_delays) {
252 for (OutputDelay *output_delay : *output_delays) {
253 if (output_delay->clkEdge() != nullptr
254 || output_delay->refPin() != nullptr)
255 return true;
256 }
257 }
258 return false;
259 }
260
261 // Check for max delay exception that ends at pin.
262 bool
hasMaxDelay(Pin * pin)263 CheckTiming::hasMaxDelay(Pin *pin)
264 {
265 ExceptionPathSet *exceptions = sdc_->exceptions();
266 ExceptionPathSet::Iterator exception_iter(exceptions);
267 while (exception_iter.hasNext()) {
268 ExceptionPath *exception = exception_iter.next();
269 ExceptionTo *to = exception->to();
270 if (exception->isPathDelay()
271 && exception->minMax() == MinMaxAll::max()
272 && to
273 && to->hasPins()
274 && to->pins()->hasKey(pin))
275 return true;
276 }
277 return false;
278 }
279
280 void
checkUnconstrainedSetups(PinSet & unconstrained_ends)281 CheckTiming::checkUnconstrainedSetups(PinSet &unconstrained_ends)
282 {
283 VertexIterator vertex_iter(graph_);
284 while (vertex_iter.hasNext()) {
285 Vertex *vertex = vertex_iter.next();
286 VertexInEdgeIterator edge_iter(vertex, graph_);
287 while (edge_iter.hasNext()) {
288 Edge *edge = edge_iter.next();
289 if (edge->role() == TimingRole::setup()
290 && (!search_->isClock(edge->from(graph_))
291 || !hasClkedArrival(edge->to(graph_)))) {
292 unconstrained_ends.insert(vertex->pin());
293 break;
294 }
295 }
296 }
297 }
298
299 bool
hasClkedArrival(Vertex * vertex)300 CheckTiming::hasClkedArrival(Vertex *vertex)
301 {
302 VertexPathIterator path_iter(vertex, this);
303 while (path_iter.hasNext()) {
304 PathVertex *path = path_iter.next();
305 if (path->clock(this))
306 return true;
307 }
308 return false;
309 }
310
311 void
checkGeneratedClocks()312 CheckTiming::checkGeneratedClocks()
313 {
314 ClockSet gen_clk_errors;
315 for (auto clk : sdc_->clks()) {
316 if (clk->isGenerated()) {
317 search_->genclks()->checkMaster(clk);
318 bool found_clk = false;
319 VertexSet src_vertices;
320 clk->srcPinVertices(src_vertices, network_, graph_);
321 VertexSet::Iterator vertex_iter(src_vertices);
322 while (vertex_iter.hasNext()) {
323 Vertex *vertex = vertex_iter.next();
324 if (search_->isClock(vertex)) {
325 found_clk = true;
326 break;
327 }
328 }
329 if (!found_clk)
330 gen_clk_errors.insert(clk);
331 }
332 }
333 pushClkErrors("Warning: There %is %d generated clock%s that %is not connected to a clock source.",
334 gen_clk_errors);
335 }
336
337 // Report the "msg" error for each pin in "pins".
338 //
339 // Substitutions in msg are done as follows if the pin count is one
340 // or greater than one.
341 // %is - is/are
342 // %d - pin count
343 // %s - s/""
344 // %a - a/""
345 void
pushPinErrors(const char * msg,PinSet & pins)346 CheckTiming::pushPinErrors(const char *msg,
347 PinSet &pins)
348 {
349 if (!pins.empty()) {
350 CheckError *error = new CheckError;
351 string error_msg;
352 errorMsgSubst(msg, pins.size(), error_msg);
353 // Copy the error strings because the error deletes them when it
354 // is deleted.
355 error->push_back(stringCopy(error_msg.c_str()));
356 // Sort the error pins so the output is independent of the order
357 // the the errors are discovered.
358 PinSeq pin_seq;
359 sortPinSet(&pins, network_, pin_seq);
360 PinSeq::Iterator pin_iter(pin_seq);
361 while (pin_iter.hasNext()) {
362 const Pin *pin = pin_iter.next();
363 const char *pin_name = stringCopy(sdc_network_->pathName(pin));
364 error->push_back(pin_name);
365 }
366 errors_.push_back(error);
367 }
368 }
369
370 void
pushClkErrors(const char * msg,ClockSet & clks)371 CheckTiming::pushClkErrors(const char *msg,
372 ClockSet &clks)
373 {
374 if (!clks.empty()) {
375 CheckError *error = new CheckError;
376 string error_msg;
377 errorMsgSubst(msg, clks.size(), error_msg);
378 // Copy the error strings because the error deletes them when it
379 // is deleted.
380 error->push_back(stringCopy(error_msg.c_str()));
381 // Sort the error clks so the output is independent of the order
382 // the the errors are discovered.
383 ClockSeq clk_seq;
384 sortClockSet(&clks, clk_seq);
385 ClockSeq::Iterator clk_iter(clk_seq);
386 while (clk_iter.hasNext()) {
387 const Clock *clk = clk_iter.next();
388 const char *clk_name = stringCopy(clk->name());
389 error->push_back(clk_name);
390 }
391 errors_.push_back(error);
392 }
393 }
394
395 // Copy msg making substitutions for singular/plurals.
396 void
errorMsgSubst(const char * msg,int obj_count,string & error_msg)397 CheckTiming::errorMsgSubst(const char *msg,
398 int obj_count,
399 string &error_msg)
400 {
401 for (const char *s = msg; *s; s++) {
402 char ch = *s;
403 if (ch == '%') {
404 char flag = s[1];
405 if (flag == 'i') {
406 if (obj_count > 1)
407 error_msg += "are";
408 else
409 error_msg += "is";
410 s += 2;
411 }
412 else if (flag == 'a') {
413 if (obj_count == 1) {
414 error_msg += 'a';
415 s++;
416 }
417 else
418 // Skip space after %a.
419 s += 2;
420 }
421 else if (flag == 's') {
422 if (obj_count > 1)
423 error_msg += 's';
424 s++;
425 }
426 else if (flag == 'd') {
427 error_msg += std::to_string(obj_count);
428 s++;
429 }
430 else
431 criticalError(245, "unknown print flag");
432 }
433 else
434 error_msg += ch;
435 }
436 }
437
438 } // namespace
439