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 #pragma once 18 19 #include "DisallowCopyAssign.hh" 20 #include "NetworkClass.hh" 21 #include "SdcClass.hh" 22 #include "GraphClass.hh" 23 #include "StaState.hh" 24 25 namespace sta { 26 27 class SearchPred; 28 class LevelizeObserver; 29 30 class Levelize : public StaState 31 { 32 public: 33 explicit Levelize(StaState *sta); 34 virtual ~Levelize(); 35 // Space between initially assigned levels that is filled in by 36 // incremental levelization. Set level space before levelization. 37 void setLevelSpace(Level space); levelized()38 bool levelized() { return levels_valid_; } 39 void ensureLevelized(); 40 void invalid(); 41 // Levels downstream from vertex are invalid. 42 void invalidFrom(Vertex *vertex); 43 void relevelizeFrom(Vertex *vertex); 44 void deleteVertexBefore(Vertex *vertex); 45 void deleteEdgeBefore(Edge *edge); maxLevel() const46 int maxLevel() const { return max_level_; } 47 // Vertices with no fanin edges. roots()48 VertexSet &roots() { return roots_; } 49 bool isRoot(Vertex *vertex); 50 // Reset to virgin state. 51 void clear(); 52 // Edge is disabled to break combinational loops. 53 bool isDisabledLoop(Edge *edge) const; 54 // Only valid when levels are valid. loops()55 GraphLoopSeq *loops() { return loops_; } 56 // Set the observer for level changes. 57 void setObserver(LevelizeObserver *observer); 58 59 protected: 60 void levelize(); 61 void findRoots(); 62 void sortRoots(VertexSeq &roots); 63 void levelizeFrom(VertexSeq &roots); 64 void visit(Vertex *vertex, Level level, Level level_space, EdgeSeq &path); 65 void levelizeCycles(); 66 void relevelize(); 67 void clearLoopEdges(); 68 void deleteLoops(); 69 void recordLoop(Edge *edge, EdgeSeq &path); 70 EdgeSeq *loopEdges(EdgeSeq &path, Edge *closing_edge); 71 void ensureLatchLevels(); 72 void setLevel(Vertex *vertex, 73 Level level); 74 void reportPath(EdgeSeq &path) const; 75 76 SearchPred *search_pred_; 77 bool levelized_; 78 bool levels_valid_; 79 Level max_level_; 80 Level level_space_; 81 VertexSet roots_; 82 VertexSet relevelize_from_; 83 GraphLoopSeq *loops_; 84 EdgeSet loop_edges_; 85 EdgeSet disabled_loop_edges_; 86 EdgeSet latch_d_to_q_edges_; 87 LevelizeObserver *observer_; 88 89 private: 90 DISALLOW_COPY_AND_ASSIGN(Levelize); 91 }; 92 93 // Loops broken by levelization may not necessarily be combinational. 94 // For example, a register/latch output can feed back to a gated clock 95 // enable on the register/latch clock. 96 class GraphLoop 97 { 98 public: 99 explicit GraphLoop(EdgeSeq *edges); 100 ~GraphLoop(); edges()101 EdgeSeq *edges() { return edges_; } 102 bool isCombinational() const; 103 void report(Report *report, 104 Network *network, 105 Graph *graph) const; 106 107 private: 108 DISALLOW_COPY_AND_ASSIGN(GraphLoop); 109 110 EdgeSeq *edges_; 111 }; 112 113 class LevelizeObserver 114 { 115 public: LevelizeObserver()116 LevelizeObserver() {} ~LevelizeObserver()117 virtual ~LevelizeObserver() {} 118 virtual void levelChangedBefore(Vertex *vertex) = 0; 119 120 private: 121 DISALLOW_COPY_AND_ASSIGN(LevelizeObserver); 122 }; 123 124 } // namespace 125