2 #ifndef __NV50_IR_GRAPH_H__
3 #define __NV50_IR_GRAPH_H__
5 #include "nv50_ir_util.h"
9 #define ITER_NODE(x) reinterpret_cast<Graph::Node *>((x).get())
10 #define ITER_EDGE(x) reinterpret_cast<Graph::Edge *>((x).get())
18 class GraphIterator
: public Iterator
21 virtual ~GraphIterator() { };
33 CROSS
, // e.g. loop break
37 Edge(Node
*dst
, Node
*src
, Type kind
);
40 inline Node
*getOrigin() const { return origin
; }
41 inline Node
*getTarget() const { return target
; }
43 inline Type
getType() const { return type
; }
44 const char *typeStr() const;
51 Edge
*next
[2]; // next edge outgoing/incident from/to origin/target
59 class EdgeIterator
: public Iterator
62 EdgeIterator() : e(0), t(0), d(0) { }
63 EdgeIterator(Graph::Edge
*first
, int dir
) : e(first
), t(first
), d(dir
) { }
65 virtual void next() { e
= (e
->next
[d
] == t
) ? 0 : e
->next
[d
]; }
66 virtual bool end() const { return !e
; }
67 virtual void *get() const { return e
; }
69 inline Node
*getNode() const { assert(e
); return d
?
70 e
->origin
: e
->target
; }
71 inline Edge
*getEdge() const { return e
; }
72 inline Edge::Type
getType() { return e
? e
->getType() : Edge::UNKNOWN
; }
86 void attach(Node
*, Edge::Type
);
90 inline EdgeIterator
outgoing() const;
91 inline EdgeIterator
incident() const;
93 inline Node
*parent() const; // returns NULL if count(incident edges) != 1
95 bool reachableBy(Node
*node
, Node
*term
);
97 inline bool visit(int);
98 inline int getSequence() const;
100 inline int incidentCountFwd() const; // count of incident non-back edges
101 inline int incidentCount() const { return inCount
; }
102 inline int outgoingCount() const { return outCount
; }
104 Graph
*getGraph() const { return graph
; }
118 int tag
; // for temporary use
125 ~Graph(); // does *not* free the nodes (make it an option ?)
127 inline Node
*getRoot() const { return root
; }
129 inline unsigned int getSize() const { return size
; }
131 inline int nextSequence();
133 void insert(Node
*node
); // attach to or set as root
135 GraphIterator
*iteratorDFS(bool preorder
= true);
136 GraphIterator
*iteratorCFG();
138 // safe iterators are unaffected by changes to the *edges* of the graph
139 GraphIterator
*safeIteratorDFS(bool preorder
= true);
140 GraphIterator
*safeIteratorCFG();
142 inline void putIterator(Iterator
*); // should be GraphIterator *
144 void classifyEdges();
147 void classifyDFS(Node
*, int&);
155 int Graph::nextSequence()
160 Graph::Node
*Graph::Node::parent() const
168 bool Graph::Node::visit(int v
)
176 int Graph::Node::getSequence() const
181 void Graph::putIterator(Iterator
*iter
)
183 delete reinterpret_cast<GraphIterator
*>(iter
);
186 Graph::EdgeIterator
Graph::Node::outgoing() const
188 return EdgeIterator(out
, 0);
191 Graph::EdgeIterator
Graph::Node::incident() const
193 return EdgeIterator(in
, 1);
196 int Graph::Node::incidentCountFwd() const
199 for (EdgeIterator ei
= incident(); !ei
.end(); ei
.next())
200 if (ei
.getType() != Edge::BACK
)
205 } // namespace nv50_ir
207 #endif // __NV50_IR_GRAPH_H__