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 "Levelize.hh"
18
19 #include <algorithm>
20
21 #include "Report.hh"
22 #include "Debug.hh"
23 #include "Stats.hh"
24 #include "TimingRole.hh"
25 #include "PortDirection.hh"
26 #include "Network.hh"
27 #include "Sdc.hh"
28 #include "Graph.hh"
29 #include "GraphCmp.hh"
30 #include "SearchPred.hh"
31
32 namespace sta {
33
34 using std::max;
35
Levelize(StaState * sta)36 Levelize::Levelize(StaState *sta) :
37 StaState(sta),
38 search_pred_(new SearchPredNonLatch2(sta)),
39 levelized_(false),
40 levels_valid_(false),
41 max_level_(0),
42 level_space_(10),
43 loops_(nullptr),
44 observer_(nullptr)
45 {
46 }
47
~Levelize()48 Levelize::~Levelize()
49 {
50 delete search_pred_;
51 delete observer_;
52 deleteLoops();
53 }
54
55 void
setLevelSpace(Level space)56 Levelize::setLevelSpace(Level space)
57 {
58 level_space_ = space;
59 }
60
61 void
setObserver(LevelizeObserver * observer)62 Levelize::setObserver(LevelizeObserver *observer)
63 {
64 delete observer_;
65 observer_ = observer;
66 }
67
68 void
clear()69 Levelize::clear()
70 {
71 levelized_ = false;
72 levels_valid_ = false;
73 roots_.clear();
74 relevelize_from_.clear();
75 clearLoopEdges();
76 deleteLoops();
77 }
78
79 void
clearLoopEdges()80 Levelize::clearLoopEdges()
81 {
82 EdgeSet::Iterator edge_iter(disabled_loop_edges_);
83 while (edge_iter.hasNext()) {
84 Edge *edge = edge_iter.next();
85 edge->setIsDisabledLoop(false);
86 }
87 disabled_loop_edges_.clear();
88 }
89
90 void
deleteLoops()91 Levelize::deleteLoops()
92 {
93 if (loops_) {
94 loops_->deleteContents();
95 delete loops_;
96 loops_ = nullptr;
97 loop_edges_.clear();
98 }
99 }
100
101 void
ensureLevelized()102 Levelize::ensureLevelized()
103 {
104 if (!levels_valid_) {
105 if (levelized_)
106 relevelize();
107 else
108 levelize();
109 }
110 }
111
112 // Depth first search.
113 // "Introduction to Algorithms", section 23.3 pg 478.
114 void
levelize()115 Levelize::levelize()
116 {
117 Stats stats(debug_, report_);
118 debugPrint(debug_, "levelize", 1, "levelize");
119 max_level_ = 0;
120 clearLoopEdges();
121 deleteLoops();
122 loops_ = new GraphLoopSeq;
123 findRoots();
124 VertexSeq roots;
125 // Sort the roots so that loop breaking is stable in regressions.
126 // In situations where port directions are broken pins may
127 // be treated as bidirects, leading to a plethora of degenerate
128 // roots that take forever to sort.
129 if (roots.size() < 100)
130 sortRoots(roots);
131 levelizeFrom(roots);
132 ensureLatchLevels();
133 // Find vertices in cycles that are were not accessible from roots.
134 levelizeCycles();
135 levelized_ = true;
136 levels_valid_ = true;
137 stats.report("Levelize");
138 }
139
140 void
findRoots()141 Levelize::findRoots()
142 {
143 VertexIterator vertex_iter(graph_);
144 while (vertex_iter.hasNext()) {
145 Vertex *vertex = vertex_iter.next();
146 setLevel(vertex, 0);
147 if (isRoot(vertex)) {
148 debugPrint(debug_, "levelize", 2, "root %s", vertex->name(sdc_network_));
149 roots_.insert(vertex);
150 if (hasFanout(vertex, search_pred_, graph_))
151 // Color roots with no fanout black so that they are
152 // not treated as degenerate loops by levelizeCycles().
153 vertex->setColor(LevelColor::black);
154 }
155 else
156 vertex->setColor(LevelColor::white);
157 }
158 }
159
160 // Root vertices have at no enabled (non-disabled) edges entering them
161 // and are not disabled.
162 bool
isRoot(Vertex * vertex)163 Levelize::isRoot(Vertex *vertex)
164 {
165 if (search_pred_->searchTo(vertex)) {
166 VertexInEdgeIterator edge_iter(vertex, graph_);
167 while (edge_iter.hasNext()) {
168 Edge *edge = edge_iter.next();
169 Vertex *from_vertex = edge->from(graph_);
170 if (search_pred_->searchFrom(from_vertex)
171 && search_pred_->searchThru(edge))
172 return false;
173 }
174 // Bidirect pins are not treated as roots in this case.
175 return !sdc_->bidirectDrvrSlewFromLoad(vertex->pin());
176 }
177 else
178 return false;
179 }
180
181 void
sortRoots(VertexSeq & roots)182 Levelize::sortRoots(VertexSeq &roots)
183 {
184 // roots_ is a set so insert/delete are fast for incremental changes.
185 // Copy the set into a vector for sorting.
186 VertexSet::Iterator root_iter(roots_);
187 while (root_iter.hasNext()) {
188 Vertex *root = root_iter.next();
189 roots.push_back(root);
190 }
191 sort(roots, VertexNameLess(network_));
192 }
193
194 void
levelizeFrom(VertexSeq & roots)195 Levelize::levelizeFrom(VertexSeq &roots)
196 {
197 VertexSeq::Iterator root_iter(roots);
198 while (root_iter.hasNext()) {
199 Vertex *root = root_iter.next();
200 EdgeSeq path;
201 visit(root, 0, level_space_, path);
202 }
203 }
204
205 void
visit(Vertex * vertex,Level level,Level level_space,EdgeSeq & path)206 Levelize::visit(Vertex *vertex,
207 Level level,
208 Level level_space,
209 EdgeSeq &path)
210 {
211 Pin *from_pin = vertex->pin();
212 debugPrint(debug_, "levelize", 3, "level %d %s",
213 level, vertex->name(sdc_network_));
214 vertex->setColor(LevelColor::gray);
215 setLevel(vertex, level);
216 max_level_ = max(level, max_level_);
217 level += level_space;
218 if (level >= Graph::vertex_level_max)
219 criticalError(616, "maximum logic level exceeded");
220
221 if (search_pred_->searchFrom(vertex)) {
222 VertexOutEdgeIterator edge_iter(vertex, graph_);
223 while (edge_iter.hasNext()) {
224 Edge *edge = edge_iter.next();
225 Vertex *to_vertex = edge->to(graph_);
226 if (search_pred_->searchThru(edge)
227 && search_pred_->searchTo(to_vertex)) {
228 LevelColor to_color = to_vertex->color();
229 if (to_color == LevelColor::gray)
230 // Back edges form feedback loops.
231 recordLoop(edge, path);
232 else if (to_color == LevelColor::white
233 || to_vertex->level() < level) {
234 path.push_back(edge);
235 visit(to_vertex, level, level_space, path);
236 path.pop_back();
237 }
238 }
239 if (edge->role() == TimingRole::latchDtoQ())
240 latch_d_to_q_edges_.insert(edge);
241 }
242 // Levelize bidirect driver as if it was a fanout of the bidirect load.
243 if (sdc_->bidirectDrvrSlewFromLoad(from_pin)
244 && !vertex->isBidirectDriver()) {
245 Vertex *to_vertex = graph_->pinDrvrVertex(from_pin);
246 if (search_pred_->searchTo(to_vertex)
247 && (to_vertex->color() == LevelColor::white
248 || to_vertex->level() < level))
249 visit(to_vertex, level, level_space, path);
250 }
251 }
252 vertex->setColor(LevelColor::black);
253 }
254
255 void
reportPath(EdgeSeq & path) const256 Levelize::reportPath(EdgeSeq &path) const
257 {
258 bool first_edge = true;
259 EdgeSeq::Iterator edge_iter(path);
260 while (edge_iter.hasNext()) {
261 Edge *edge = edge_iter.next();
262 if (first_edge)
263 report_->reportLine(" %s", edge->from(graph_)->name(network_));
264 report_->reportLine(" %s", edge->to(graph_)->name(network_));
265 first_edge = false;
266 }
267 }
268
269 void
recordLoop(Edge * edge,EdgeSeq & path)270 Levelize::recordLoop(Edge *edge,
271 EdgeSeq &path)
272 {
273 debugPrint(debug_, "levelize", 2, "Loop edge %s -> %s (%s)",
274 edge->from(graph_)->name(sdc_network_),
275 edge->to(graph_)->name(sdc_network_),
276 edge->role()->asString());
277 // Do not record loops if they have been invalidated.
278 if (loops_) {
279 EdgeSeq *loop_edges = loopEdges(path, edge);
280 GraphLoop *loop = new GraphLoop(loop_edges);
281 loops_->push_back(loop);
282 if (sdc_->dynamicLoopBreaking())
283 sdc_->makeLoopExceptions(loop);
284 }
285 // Record disabled loop edges so they can be cleared without
286 // traversing the entire graph to find them.
287 disabled_loop_edges_.insert(edge);
288 edge->setIsDisabledLoop(true);
289 }
290
291 EdgeSeq *
loopEdges(EdgeSeq & path,Edge * closing_edge)292 Levelize::loopEdges(EdgeSeq &path,
293 Edge *closing_edge)
294 {
295 debugPrint(debug_, "loop", 2, "Loop");
296 EdgeSeq *loop_edges = new EdgeSeq;
297 // Skip the "head" of the path up to where closing_edge closes the loop.
298 Pin *loop_pin = closing_edge->to(graph_)->pin();
299 bool copy = false;
300 EdgeSeq::Iterator edge_iter(path);
301 while (edge_iter.hasNext()) {
302 Edge *edge = edge_iter.next();
303 Pin *from_pin = edge->from(graph_)->pin();
304 if (from_pin == loop_pin)
305 copy = true;
306 if (copy) {
307 debugPrint(debug_, "loop", 2, " %s -> %s",
308 edge->from(graph_)->name(sdc_network_),
309 edge->to(graph_)->name(sdc_network_));
310 loop_edges->push_back(edge);
311 loop_edges_.insert(edge);
312 }
313 }
314 debugPrint(debug_, "loop", 2, " %s -> %s",
315 closing_edge->from(graph_)->name(sdc_network_),
316 closing_edge->to(graph_)->name(sdc_network_));
317 loop_edges->push_back(closing_edge);
318 loop_edges_.insert(closing_edge);
319 return loop_edges;
320 }
321
322 // Make sure latch D input level is not the same as the Q level.
323 // This is because the Q arrival depends on the D arrival and
324 // to find them in parallel they have to be scheduled separately
325 // to avoid a race condition.
326 void
ensureLatchLevels()327 Levelize::ensureLatchLevels()
328 {
329 EdgeSet::Iterator latch_edge_iter(latch_d_to_q_edges_);
330 while (latch_edge_iter.hasNext()) {
331 Edge *edge = latch_edge_iter.next();
332 Vertex *from = edge->from(graph_);
333 Vertex *to = edge->to(graph_);
334 if (from->level() == to->level())
335 setLevel(from, from->level() + level_space_);
336 }
337 latch_d_to_q_edges_.clear();
338 }
339
340 void
levelizeCycles()341 Levelize::levelizeCycles()
342 {
343 // Find vertices that were not discovered by searching from all
344 // graph roots.
345 VertexSeq uncolored;
346 VertexIterator vertex_iter(graph_);
347 while (vertex_iter.hasNext()) {
348 Vertex *vertex = vertex_iter.next();
349 if (vertex->color() == LevelColor::white
350 && search_pred_->searchFrom(vertex))
351 uncolored.push_back(vertex);
352 }
353
354 // Sort cycle vertices so results are stable.
355 sort(uncolored, VertexNameLess(network_));
356
357 VertexSeq::Iterator uncolored_iter(uncolored);
358 while (uncolored_iter.hasNext()) {
359 Vertex *vertex = uncolored_iter.next();
360 // Only search from and assign root status to vertices that
361 // previous searches did not visit. Otherwise "everybody is a
362 // root".
363 if (vertex->color() == LevelColor::white) {
364 EdgeSeq path;
365 roots_.insert(vertex);
366 visit(vertex, 0, level_space_, path);
367 }
368 }
369 }
370
371 void
invalid()372 Levelize::invalid()
373 {
374 debugPrint(debug_, "levelize", 1, "levels invalid");
375 clear();
376 }
377
378 void
invalidFrom(Vertex * vertex)379 Levelize::invalidFrom(Vertex *vertex)
380 {
381 debugPrint(debug_, "levelize", 1, "level invalid from %s",
382 vertex->name(sdc_network_));
383 VertexInEdgeIterator edge_iter(vertex, graph_);
384 while (edge_iter.hasNext()) {
385 Edge *edge = edge_iter.next();
386 Vertex *from_vertex = edge->from(graph_);
387 relevelize_from_.insert(from_vertex);
388 }
389 relevelize_from_.insert(vertex);
390 levels_valid_ = false;
391 }
392
393 void
deleteVertexBefore(Vertex * vertex)394 Levelize::deleteVertexBefore(Vertex *vertex)
395 {
396 roots_.erase(vertex);
397 relevelize_from_.erase(vertex);
398 }
399
400 void
relevelizeFrom(Vertex * vertex)401 Levelize::relevelizeFrom(Vertex *vertex)
402 {
403 debugPrint(debug_, "levelize", 1, "invalid relevelize from %s",
404 vertex->name(sdc_network_));
405 relevelize_from_.insert(vertex);
406 levels_valid_ = false;
407 }
408
409 void
deleteEdgeBefore(Edge * edge)410 Levelize::deleteEdgeBefore(Edge *edge)
411 {
412 if (loop_edges_.hasKey(edge)) {
413 // Relevelize if a loop edge is removed. Incremental levelization
414 // fails because the DFS path will be missing.
415 invalid();
416 // Prevent refererence to deleted edge by clearLoopEdges().
417 disabled_loop_edges_.erase(edge);
418 }
419 }
420
421 // Incremental relevelization.
422 // Note that if vertices or edges are removed from the graph the
423 // downstream levels will NOT be reduced to the "correct" level (the
424 // search will immediately terminate without visiting downstream
425 // vertices because the new level is less than the existing level).
426 // This is acceptable because the BFS search that depends on the
427 // levels only requires that a vertex level be greater than that of
428 // its predecessors.
429 void
relevelize()430 Levelize::relevelize()
431 {
432 VertexSet::Iterator vertex_iter(relevelize_from_);
433 while (vertex_iter.hasNext()) {
434 Vertex *vertex = vertex_iter.next();
435 debugPrint(debug_, "levelize", 1, "relevelize from %s",
436 vertex->name(sdc_network_));
437 if (search_pred_->searchFrom(vertex)) {
438 if (isRoot(vertex)) {
439 setLevel(vertex, 0);
440 roots_.insert(vertex);
441 }
442 EdgeSeq path;
443 visit(vertex, vertex->level(), 1, path);
444 }
445 }
446 ensureLatchLevels();
447 levels_valid_ = true;
448 relevelize_from_.clear();
449 }
450
451 bool
isDisabledLoop(Edge * edge) const452 Levelize::isDisabledLoop(Edge *edge) const
453 {
454 return disabled_loop_edges_.hasKey(edge);
455 }
456
457 void
setLevel(Vertex * vertex,Level level)458 Levelize::setLevel(Vertex *vertex,
459 Level level)
460 {
461 if (vertex->level() != level) {
462 if (observer_)
463 observer_->levelChangedBefore(vertex);
464 vertex->setLevel(level);
465 }
466 }
467
468 ////////////////////////////////////////////////////////////////
469
GraphLoop(EdgeSeq * edges)470 GraphLoop::GraphLoop(EdgeSeq *edges) :
471 edges_(edges)
472 {
473 }
474
~GraphLoop()475 GraphLoop::~GraphLoop()
476 {
477 delete edges_;
478 }
479
480 bool
isCombinational() const481 GraphLoop::isCombinational() const
482 {
483 EdgeSeq::Iterator edge_iter(edges_);
484 while (edge_iter.hasNext()) {
485 Edge *edge = edge_iter.next();
486 TimingRole *role = edge->role();
487 if (!(role == TimingRole::wire()
488 || role == TimingRole::combinational()
489 || role == TimingRole::tristateEnable()
490 || role == TimingRole::tristateDisable()))
491 return false;
492 }
493 return true;
494 }
495
496 void
report(Report * report,Network * network,Graph * graph) const497 GraphLoop::report(Report *report,
498 Network *network,
499 Graph *graph) const
500 {
501 bool first_edge = true;
502 EdgeSeq::Iterator loop_edge_iter(edges_);
503 while (loop_edge_iter.hasNext()) {
504 Edge *edge = loop_edge_iter.next();
505 if (first_edge)
506 report->reportLine(" %s", edge->from(graph)->name(network));
507 report->reportLine(" %s", edge->to(graph)->name(network));
508 first_edge = false;
509 }
510 }
511
512 } // namespace
513