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