1 /* 2 * Copyright 2011 Christoph Bumiller 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in 12 * all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20 * SOFTWARE. 21 */ 22 23 #ifndef __NV50_IR_GRAPH_H__ 24 #define __NV50_IR_GRAPH_H__ 25 26 #include "nv50_ir_util.h" 27 #include <vector> 28 29 namespace nv50_ir { 30 31 #define ITER_NODE(x) reinterpret_cast<Graph::Node *>((x).get()) 32 #define ITER_EDGE(x) reinterpret_cast<Graph::Edge *>((x).get()) 33 34 // A connected graph. 35 class Graph 36 { 37 public: 38 class Node; 39 40 class Edge 41 { 42 public: 43 enum Type 44 { 45 UNKNOWN, 46 TREE, 47 FORWARD, 48 BACK, 49 CROSS, // e.g. loop break 50 DUMMY 51 }; 52 53 Edge(Node *dst, Node *src, Type kind); 54 ~Edge() { unlink(); } 55 56 inline Node *getOrigin() const { return origin; } 57 inline Node *getTarget() const { return target; } 58 59 inline Type getType() const { return type; } 60 const char *typeStr() const; 61 62 private: 63 Node *origin; 64 Node *target; 65 66 Type type; 67 Edge *next[2]; // next edge outgoing/incident from/to origin/target 68 Edge *prev[2]; 69 70 void unlink(); 71 72 friend class Graph; 73 }; 74 75 class EdgeIterator : public Iterator 76 { 77 public: 78 EdgeIterator() : e(0), t(0), d(0), rev(false) { } 79 EdgeIterator(Graph::Edge *first, int dir, bool reverse) 80 : d(dir), rev(reverse) 81 { 82 t = e = ((rev && first) ? first->prev[d] : first); 83 } 84 85 virtual void next() 86 { 87 Graph::Edge *n = (rev ? e->prev[d] : e->next[d]); 88 e = (n == t ? NULL : n); 89 } 90 virtual bool end() const { return !e; } 91 virtual void *get() const { return e; } 92 93 inline Node *getNode() const { assert(e); return d ? 94 e->origin : e->target; } 95 inline Edge *getEdge() const { return e; } 96 inline Edge::Type getType() { return e ? e->getType() : Edge::UNKNOWN; } 97 98 private: 99 Graph::Edge *e; 100 Graph::Edge *t; 101 int d; 102 bool rev; 103 }; 104 105 class Node 106 { 107 public: 108 Node(void *); 109 ~Node() { cut(); } 110 111 void attach(Node *, Edge::Type); 112 bool detach(Node *); 113 void cut(); 114 115 inline EdgeIterator outgoing(bool reverse = false) const; 116 inline EdgeIterator incident(bool reverse = false) const; 117 118 inline Node *parent() const; // returns NULL if count(incident edges) != 1 119 120 bool reachableBy(const Node *node, const Node *term) const; 121 122 inline bool visit(int); 123 inline int getSequence() const; 124 125 inline int incidentCountFwd() const; // count of incident non-back edges 126 inline int incidentCount() const { return inCount; } 127 inline int outgoingCount() const { return outCount; } 128 129 Graph *getGraph() const { return graph; } 130 131 void *data; 132 133 private: 134 Edge *in; 135 Edge *out; 136 Graph *graph; 137 138 int visited; 139 140 int16_t inCount; 141 int16_t outCount; 142 public: 143 int tag; // for temporary use 144 145 friend class Graph; 146 }; 147 148 public: 149 Graph(); 150 ~Graph(); // does *not* free the nodes (make it an option ?) 151 152 inline Node *getRoot() const { return root; } 153 154 inline unsigned int getSize() const { return size; } 155 156 inline int nextSequence(); 157 158 void insert(Node *node); // attach to or set as root 159 160 IteratorRef iteratorDFS(bool preorder = true); 161 IteratorRef iteratorCFG(); 162 163 // safe iterators are unaffected by changes to the *edges* of the graph 164 IteratorRef safeIteratorDFS(bool preorder = true); 165 IteratorRef safeIteratorCFG(); 166 167 void classifyEdges(); 168 169 // @weights: indexed by Node::tag 170 int findLightestPathWeight(Node *, Node *, const std::vector<int>& weights); 171 172 private: 173 void classifyDFS(Node *, int&); 174 175 private: 176 Node *root; 177 unsigned int size; 178 int sequence; 179 }; 180 181 int Graph::nextSequence() 182 { 183 return ++sequence; 184 } 185 186 Graph::Node *Graph::Node::parent() const 187 { 188 if (inCount != 1) 189 return NULL; 190 assert(in); 191 return in->origin; 192 } 193 194 bool Graph::Node::visit(int v) 195 { 196 if (visited == v) 197 return false; 198 visited = v; 199 return true; 200 } 201 202 int Graph::Node::getSequence() const 203 { 204 return visited; 205 } 206 207 Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const 208 { 209 return EdgeIterator(out, 0, reverse); 210 } 211 212 Graph::EdgeIterator Graph::Node::incident(bool reverse) const 213 { 214 return EdgeIterator(in, 1, reverse); 215 } 216 217 int Graph::Node::incidentCountFwd() const 218 { 219 int n = 0; 220 for (EdgeIterator ei = incident(); !ei.end(); ei.next()) 221 if (ei.getType() != Edge::BACK) 222 ++n; 223 return n; 224 } 225 226 } // namespace nv50_ir 227 228 #endif // __NV50_IR_GRAPH_H__ 229
