1 // -*- mode: C++; c-file-style: "cc-mode" -*- 2 //************************************************************************* 3 // DESCRIPTION: Verilator: Graph optimizations 4 // 5 // Code available from: https://verilator.org 6 // 7 //************************************************************************* 8 // 9 // Copyright 2003-2021 by Wilson Snyder. This program is free software; you 10 // can redistribute it and/or modify it under the terms of either the GNU 11 // Lesser General Public License Version 3 or the Perl Artistic License 12 // Version 2.0. 13 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0 14 // 15 //************************************************************************* 16 17 #ifndef VERILATOR_V3GRAPH_H_ 18 #define VERILATOR_V3GRAPH_H_ 19 20 #include "config_build.h" 21 #include "verilatedos.h" 22 23 #include "V3Error.h" 24 #include "V3List.h" 25 26 #include <algorithm> 27 28 class FileLine; 29 class V3Graph; 30 class V3GraphVertex; 31 class V3GraphEdge; 32 class GraphAcycEdge; 33 class OrderEitherVertex; 34 class OrderLogicVertex; 35 36 //============================================================================= 37 // Most graph algorithms accept an arbitrary function that returns 38 // True for those edges we should honor. 39 40 using V3EdgeFuncP = bool (*)(const V3GraphEdge* edgep); 41 42 //============================================================================= 43 // When the Graph represents a directional acyclical graph (DAG), following 44 // the to() edges is forward, and back() is reverse. However, sometimes 45 // it's useful to have algorithms that can walk in either direction, hence 46 // some methods take GraphWay to programmatically select the direction. 47 48 class GraphWay final { 49 public: 50 enum en : uint8_t { 51 FORWARD = 0, 52 REVERSE = 1, 53 NUM_WAYS = 2 // NUM_WAYS is not an actual way, it's typically 54 // // an array dimension or loop bound. 55 }; 56 enum en m_e; GraphWay()57 inline GraphWay() 58 : m_e{FORWARD} {} 59 // cppcheck-suppress noExplicitConstructor GraphWay(en _e)60 inline GraphWay(en _e) 61 : m_e{_e} {} GraphWay(int _e)62 explicit inline GraphWay(int _e) 63 : m_e(static_cast<en>(_e)) {} // Need () or GCC 4.8 false warning en()64 operator en() const { return m_e; } ascii()65 const char* ascii() const { 66 static const char* const names[] = {"FORWARD", "REVERSE"}; 67 return names[m_e]; 68 } 69 // METHODS unique to this class invert()70 GraphWay invert() const { return m_e == FORWARD ? REVERSE : FORWARD; } forward()71 bool forward() const { return m_e == FORWARD; } reverse()72 bool reverse() const { return m_e != FORWARD; } 73 }; 74 inline bool operator==(const GraphWay& lhs, const GraphWay& rhs) { return lhs.m_e == rhs.m_e; } 75 inline bool operator==(const GraphWay& lhs, GraphWay::en rhs) { return lhs.m_e == rhs; } 76 inline bool operator==(GraphWay::en lhs, const GraphWay& rhs) { return lhs == rhs.m_e; } 77 78 //============================================================================ 79 80 class V3Graph VL_NOT_FINAL { 81 private: 82 // MEMBERS 83 V3List<V3GraphVertex*> m_vertices; // All vertices 84 static int s_debug; 85 86 protected: 87 friend class V3GraphVertex; 88 friend class V3GraphEdge; 89 friend class GraphAcyc; 90 // METHODS 91 double orderDFSIterate(V3GraphVertex* vertexp); 92 void dumpEdge(std::ostream& os, V3GraphVertex* vertexp, V3GraphEdge* edgep); verticesUnlink()93 void verticesUnlink() { m_vertices.reset(); } 94 // ACCESSORS 95 static int debug(); 96 97 public: 98 V3Graph(); 99 virtual ~V3Graph(); debug(int level)100 static void debug(int level) { s_debug = level; } dotRankDir()101 virtual string dotRankDir() const { return "TB"; } // rankdir for dot plotting 102 103 // METHODS 104 void clear(); // Empty it of all vertices/edges, as if making a new object 105 void clearColors(); empty()106 bool empty() const { return m_vertices.empty(); } 107 verticesBeginp()108 V3GraphVertex* verticesBeginp() const { return m_vertices.begin(); } 109 110 // METHODS - ALGORITHMS 111 112 /// Assign same color to all vertices in the same weakly connected component 113 /// Thus different color if there's no edges between the two subgraphs 114 void weaklyConnected(V3EdgeFuncP edgeFuncp); 115 116 /// Assign same color to all vertices that are strongly connected 117 /// Thus different color if there's no directional circuit within the subgraphs. 118 /// (I.E. all loops will occur within each color, not between them.) 119 void stronglyConnected(V3EdgeFuncP edgeFuncp); 120 121 /// Assign a ordering number to all vertexes in a tree. 122 /// All nodes with no inputs will get rank 1 123 void rank(V3EdgeFuncP edgeFuncp); 124 void rank(); 125 126 /// Sort all vertices and edges using the V3GraphVertex::sortCmp() function 127 void sortVertices(); 128 /// Sort all edges and edges using the V3GraphEdge::sortCmp() function 129 void sortEdges(); 130 131 /// Order all vertices by rank and fanout, lowest first 132 /// Sort all vertices by rank and fanout, lowest first 133 /// Sort all edges by weight, lowest first 134 /// Side-effect: assigns ranks to every node. 135 void order(); 136 137 // Similar to order() but does not assign ranks. Caller must 138 // ensure that the graph has been ranked ahead of the call. 139 void orderPreRanked(); 140 141 /// Make acyclical (into a tree) by breaking a minimal subset of cutable edges. 142 void acyclic(V3EdgeFuncP edgeFuncp); 143 144 /// Remove any redundant edges, weights become MAX of any other weight 145 void removeRedundantEdges(V3EdgeFuncP edgeFuncp); 146 147 /// Remove any redundant edges, weights become SUM of any other weight 148 void removeRedundantEdgesSum(V3EdgeFuncP edgeFuncp); 149 150 /// Remove any transitive edges. E.g. if have edges A->B, B->C, and A->C 151 /// then A->C is a "transitive" edge; it's implied by the first two 152 /// (assuming the DAG is a dependency graph.) 153 /// This algorithm can be expensive. 154 void removeTransitiveEdges(); 155 156 /// Call loopsVertexCb on any one loop starting where specified 157 void reportLoops(V3EdgeFuncP edgeFuncp, V3GraphVertex* vertexp); 158 159 /// Build a subgraph of all loops starting where specified 160 void subtreeLoops(V3EdgeFuncP edgeFuncp, V3GraphVertex* vertexp, V3Graph* loopGraphp); 161 162 /// Debugging 163 void dump(std::ostream& os = std::cout); 164 void dumpDotFile(const string& filename, bool colorAsSubgraph) const; 165 void dumpDotFilePrefixed(const string& nameComment, bool colorAsSubgraph = false) const; 166 void dumpDotFilePrefixedAlways(const string& nameComment, bool colorAsSubgraph = false) const; 167 void userClearVertices(); 168 void userClearEdges(); 169 static void selfTest(); 170 171 // CALLBACKS 172 virtual void loopsMessageCb(V3GraphVertex* vertexp); 173 virtual void loopsVertexCb(V3GraphVertex* vertexp); 174 }; 175 176 //============================================================================ 177 178 class V3GraphVertex VL_NOT_FINAL { 179 // Vertices may be a 'gate'/wire statement OR a variable 180 protected: 181 friend class V3Graph; 182 friend class V3GraphEdge; 183 friend class GraphAcyc; 184 friend class GraphAlgRank; 185 V3ListEnt<V3GraphVertex*> m_vertices; // All vertices, linked list 186 V3List<V3GraphEdge*> m_outs; // Outbound edges,linked list 187 V3List<V3GraphEdge*> m_ins; // Inbound edges, linked list 188 double m_fanout; // Order fanout 189 uint32_t m_color; // Color of the node 190 uint32_t m_rank; // Rank of edge 191 union { 192 void* m_userp; // Marker for some algorithms 193 uint32_t m_user; // Marker for some algorithms 194 }; 195 // METHODS 196 void verticesPushBack(V3Graph* graphp); 197 // ACCESSORS fanout(double fanout)198 void fanout(double fanout) { m_fanout = fanout; } inUnlink()199 void inUnlink() { m_ins.reset(); } // Low level; normally unlinkDelete is what you want outUnlink()200 void outUnlink() { m_outs.reset(); } // Low level; normally unlinkDelete is what you want 201 protected: 202 // CONSTRUCTORS 203 V3GraphVertex(V3Graph* graphp, const V3GraphVertex& old); 204 205 public: 206 explicit V3GraphVertex(V3Graph* graphp); 207 //! Clone copy constructor. Doesn't copy edges or user/userp. clone(V3Graph * graphp)208 virtual V3GraphVertex* clone(V3Graph* graphp) const { 209 return new V3GraphVertex(graphp, *this); 210 } 211 virtual ~V3GraphVertex() = default; 212 void unlinkEdges(V3Graph* graphp); 213 void unlinkDelete(V3Graph* graphp); 214 215 // ACCESSORS name()216 virtual string name() const { return ""; } dotColor()217 virtual string dotColor() const { return "black"; } dotShape()218 virtual string dotShape() const { return ""; } dotStyle()219 virtual string dotStyle() const { return ""; } dotName()220 virtual string dotName() const { return ""; } rankAdder()221 virtual uint32_t rankAdder() const { return 1; } fileline()222 virtual FileLine* fileline() const { return nullptr; } // nullptr for unknown sortCmp(const V3GraphVertex * rhsp)223 virtual int sortCmp(const V3GraphVertex* rhsp) const { 224 // LHS goes first if of lower rank, or lower fanout 225 if (m_rank < rhsp->m_rank) return -1; 226 if (m_rank > rhsp->m_rank) return 1; 227 if (m_fanout < rhsp->m_fanout) return -1; 228 if (m_fanout > rhsp->m_fanout) return 1; 229 return 0; 230 } color()231 uint32_t color() const { return m_color; } color(uint32_t color)232 void color(uint32_t color) { m_color = color; } rank()233 uint32_t rank() const { return m_rank; } rank(uint32_t rank)234 void rank(uint32_t rank) { m_rank = rank; } fanout()235 double fanout() const { return m_fanout; } user(uint32_t user)236 void user(uint32_t user) { m_user = user; } user()237 uint32_t user() const { return m_user; } userp(void * userp)238 void userp(void* userp) { m_userp = userp; } userp()239 void* userp() const { return m_userp; } 240 // ITERATORS verticesNextp()241 V3GraphVertex* verticesNextp() const { return m_vertices.nextp(); } inBeginp()242 V3GraphEdge* inBeginp() const { return m_ins.begin(); } inEmpty()243 bool inEmpty() const { return inBeginp() == nullptr; } 244 bool inSize1() const; 245 uint32_t inHash() const; outBeginp()246 V3GraphEdge* outBeginp() const { return m_outs.begin(); } outEmpty()247 bool outEmpty() const { return outBeginp() == nullptr; } 248 bool outSize1() const; 249 uint32_t outHash() const; beginp(GraphWay way)250 V3GraphEdge* beginp(GraphWay way) const { return way.forward() ? outBeginp() : inBeginp(); } 251 // METHODS 252 /// Error reporting 253 void v3errorEnd(std::ostringstream& str) const; 254 void v3errorEndFatal(std::ostringstream& str) const; 255 /// Edges are routed around this vertex to point from "from" directly to "to" 256 void rerouteEdges(V3Graph* graphp); 257 /// Find the edge connecting ap and bp, where bp is wayward from ap. 258 /// If edge is not found returns nullptr. O(edges) performance. 259 V3GraphEdge* findConnectingEdgep(GraphWay way, const V3GraphVertex* waywardp); 260 }; 261 262 std::ostream& operator<<(std::ostream& os, V3GraphVertex* vertexp); 263 264 //============================================================================ 265 266 class V3GraphEdge VL_NOT_FINAL { 267 // Wires/variables aren't edges. Edges have only a single to/from vertex 268 public: 269 // ENUMS 270 enum Cutable : uint8_t { NOT_CUTABLE = false, CUTABLE = true }; // For passing to V3GraphEdge 271 protected: 272 friend class V3Graph; 273 friend class V3GraphVertex; 274 friend class GraphAcyc; 275 friend class GraphAcycEdge; 276 V3ListEnt<V3GraphEdge*> m_outs; // Next Outbound edge for same vertex (linked list) 277 V3ListEnt<V3GraphEdge*> m_ins; // Next Inbound edge for same vertex (linked list) 278 // 279 V3GraphVertex* m_fromp; // Vertices pointing to this edge 280 V3GraphVertex* m_top; // Vertices this edge points to 281 int m_weight; // Weight of the connection 282 bool m_cutable; // Interconnect may be broken in order sorting 283 union { 284 void* m_userp; // Marker for some algorithms 285 uint32_t m_user; // Marker for some algorithms 286 }; 287 // METHODS 288 void init(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top, int weight, 289 bool cutable = false); cut()290 void cut() { m_weight = 0; } // 0 weight is same as disconnected 291 void outPushBack(); 292 void inPushBack(); 293 // CONSTRUCTORS 294 protected: V3GraphEdge(V3Graph * graphp,V3GraphVertex * fromp,V3GraphVertex * top,const V3GraphEdge & old)295 V3GraphEdge(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top, 296 const V3GraphEdge& old) { 297 init(graphp, fromp, top, old.m_weight, old.m_cutable); 298 } 299 300 public: 301 //! Add DAG from one node to the specified node 302 V3GraphEdge(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top, int weight, 303 bool cutable = false) { 304 init(graphp, fromp, top, weight, cutable); 305 } 306 //! Clone copy constructor. Doesn't copy existing vertices or user/userp. clone(V3Graph * graphp,V3GraphVertex * fromp,V3GraphVertex * top)307 virtual V3GraphEdge* clone(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top) const { 308 return new V3GraphEdge(graphp, fromp, top, *this); 309 } 310 virtual ~V3GraphEdge() = default; 311 // METHODS name()312 virtual string name() const { return m_fromp->name() + "->" + m_top->name(); } dotLabel()313 virtual string dotLabel() const { return ""; } dotColor()314 virtual string dotColor() const { return cutable() ? "yellowGreen" : "red"; } dotStyle()315 virtual string dotStyle() const { return cutable() ? "dashed" : ""; } sortCmp(const V3GraphEdge * rhsp)316 virtual int sortCmp(const V3GraphEdge* rhsp) const { 317 if (!m_weight || !rhsp->m_weight) return 0; 318 return top()->sortCmp(rhsp->top()); 319 } 320 void unlinkDelete(); 321 V3GraphEdge* relinkFromp(V3GraphVertex* newFromp); 322 // ACCESSORS weight()323 int weight() const { return m_weight; } weight(int weight)324 void weight(int weight) { m_weight = weight; } cutable()325 bool cutable() const { return m_cutable; } cutable(bool cutable)326 void cutable(bool cutable) { m_cutable = cutable; } userp(void * user)327 void userp(void* user) { m_userp = user; } userp()328 void* userp() const { return m_userp; } user(uint32_t user)329 void user(uint32_t user) { m_user = user; } user()330 uint32_t user() const { return m_user; } fromp()331 V3GraphVertex* fromp() const { return m_fromp; } top()332 V3GraphVertex* top() const { return m_top; } closerp(GraphWay way)333 V3GraphVertex* closerp(GraphWay way) const { return way.forward() ? fromp() : top(); } furtherp(GraphWay way)334 V3GraphVertex* furtherp(GraphWay way) const { return way.forward() ? top() : fromp(); } 335 // STATIC ACCESSORS followNotCutable(const V3GraphEdge * edgep)336 static bool followNotCutable(const V3GraphEdge* edgep) { return !edgep->m_cutable; } followAlwaysTrue(const V3GraphEdge *)337 static bool followAlwaysTrue(const V3GraphEdge*) { return true; } 338 // ITERATORS outNextp()339 V3GraphEdge* outNextp() const { return m_outs.nextp(); } inNextp()340 V3GraphEdge* inNextp() const { return m_ins.nextp(); } nextp(GraphWay way)341 V3GraphEdge* nextp(GraphWay way) const { return way.forward() ? outNextp() : inNextp(); } 342 }; 343 344 //============================================================================ 345 346 #endif // Guard 347