2 * Copyright 2011 Christoph Bumiller
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:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
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
23 #ifndef __NV50_IR_GRAPH_H__
24 #define __NV50_IR_GRAPH_H__
26 #include "nv50_ir_util.h"
30 #define ITER_NODE(x) reinterpret_cast<Graph::Node *>((x).get())
31 #define ITER_EDGE(x) reinterpret_cast<Graph::Edge *>((x).get())
39 class GraphIterator
: public Iterator
42 virtual ~GraphIterator() { };
54 CROSS
, // e.g. loop break
58 Edge(Node
*dst
, Node
*src
, Type kind
);
61 inline Node
*getOrigin() const { return origin
; }
62 inline Node
*getTarget() const { return target
; }
64 inline Type
getType() const { return type
; }
65 const char *typeStr() const;
72 Edge
*next
[2]; // next edge outgoing/incident from/to origin/target
80 class EdgeIterator
: public Iterator
83 EdgeIterator() : e(0), t(0), d(0), rev(false) { }
84 EdgeIterator(Graph::Edge
*first
, int dir
, bool reverse
)
85 : d(dir
), rev(reverse
)
87 t
= e
= ((rev
&& first
) ? first
->prev
[d
] : first
);
92 Graph::Edge
*n
= (rev
? e
->prev
[d
] : e
->next
[d
]);
93 e
= (n
== t
? NULL
: n
);
95 virtual bool end() const { return !e
; }
96 virtual void *get() const { return e
; }
98 inline Node
*getNode() const { assert(e
); return d
?
99 e
->origin
: e
->target
; }
100 inline Edge
*getEdge() const { return e
; }
101 inline Edge::Type
getType() { return e
? e
->getType() : Edge::UNKNOWN
; }
116 void attach(Node
*, Edge::Type
);
120 inline EdgeIterator
outgoing(bool reverse
= false) const;
121 inline EdgeIterator
incident(bool reverse
= false) const;
123 inline Node
*parent() const; // returns NULL if count(incident edges) != 1
125 bool reachableBy(Node
*node
, Node
*term
);
127 inline bool visit(int);
128 inline int getSequence() const;
130 inline int incidentCountFwd() const; // count of incident non-back edges
131 inline int incidentCount() const { return inCount
; }
132 inline int outgoingCount() const { return outCount
; }
134 Graph
*getGraph() const { return graph
; }
148 int tag
; // for temporary use
155 ~Graph(); // does *not* free the nodes (make it an option ?)
157 inline Node
*getRoot() const { return root
; }
159 inline unsigned int getSize() const { return size
; }
161 inline int nextSequence();
163 void insert(Node
*node
); // attach to or set as root
165 GraphIterator
*iteratorDFS(bool preorder
= true);
166 GraphIterator
*iteratorCFG();
168 // safe iterators are unaffected by changes to the *edges* of the graph
169 GraphIterator
*safeIteratorDFS(bool preorder
= true);
170 GraphIterator
*safeIteratorCFG();
172 inline void putIterator(Iterator
*); // should be GraphIterator *
174 void classifyEdges();
177 void classifyDFS(Node
*, int&);
185 int Graph::nextSequence()
190 Graph::Node
*Graph::Node::parent() const
198 bool Graph::Node::visit(int v
)
206 int Graph::Node::getSequence() const
211 void Graph::putIterator(Iterator
*iter
)
213 delete reinterpret_cast<GraphIterator
*>(iter
);
216 Graph::EdgeIterator
Graph::Node::outgoing(bool reverse
) const
218 return EdgeIterator(out
, 0, reverse
);
221 Graph::EdgeIterator
Graph::Node::incident(bool reverse
) const
223 return EdgeIterator(in
, 1, reverse
);
226 int Graph::Node::incidentCountFwd() const
229 for (EdgeIterator ei
= incident(); !ei
.end(); ei
.next())
230 if (ei
.getType() != Edge::BACK
)
235 } // namespace nv50_ir
237 #endif // __NV50_IR_GRAPH_H__