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 OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 #ifndef __NV50_IR_GRAPH_H__
24 #define __NV50_IR_GRAPH_H__
25
26 #include "codegen/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 };
51
52 Edge(Node *dst, Node *src, Type kind);
~Edge()53 ~Edge() { unlink(); }
54
getOrigin()55 inline Node *getOrigin() const { return origin; }
getTarget()56 inline Node *getTarget() const { return target; }
57
getType()58 inline Type getType() const { return type; }
59 const char *typeStr() const;
60
61 private:
62 Node *origin;
63 Node *target;
64
65 Type type;
66 Edge *next[2]; // next edge outgoing/incident from/to origin/target
67 Edge *prev[2];
68
69 void unlink();
70
71 friend class Graph;
72 };
73
74 class EdgeIterator : public Iterator
75 {
76 public:
EdgeIterator()77 EdgeIterator() : e(0), t(0), d(0), rev(false) { }
EdgeIterator(Graph::Edge * first,int dir,bool reverse)78 EdgeIterator(Graph::Edge *first, int dir, bool reverse)
79 : d(dir), rev(reverse)
80 {
81 t = e = ((rev && first) ? first->prev[d] : first);
82 }
83
next()84 virtual void next()
85 {
86 Graph::Edge *n = (rev ? e->prev[d] : e->next[d]);
87 e = (n == t ? NULL : n);
88 }
end()89 virtual bool end() const { return !e; }
get()90 virtual void *get() const { return e; }
91
getNode()92 inline Node *getNode() const { assert(e); return d ?
93 e->origin : e->target; }
getEdge()94 inline Edge *getEdge() const { return e; }
getType()95 inline Edge::Type getType() { return e ? e->getType() : Edge::UNKNOWN; }
96
97 private:
98 Graph::Edge *e;
99 Graph::Edge *t;
100 int d;
101 bool rev;
102 };
103
104 class Node
105 {
106 public:
107 Node(void *);
~Node()108 ~Node() { cut(); }
109
110 void attach(Node *, Edge::Type);
111 bool detach(Node *);
112 void cut();
113
114 inline EdgeIterator outgoing(bool reverse = false) const;
115 inline EdgeIterator incident(bool reverse = false) const;
116
117 inline Node *parent() const; // returns NULL if count(incident edges) != 1
118
119 bool reachableBy(const Node *node, const Node *term) const;
120
121 inline bool visit(int);
122 inline int getSequence() const;
123
124 inline int incidentCountFwd() const; // count of incident non-back edges
incidentCount()125 inline int incidentCount() const { return inCount; }
outgoingCount()126 inline int outgoingCount() const { return outCount; }
127
getGraph()128 Graph *getGraph() const { return graph; }
129
130 void *data;
131
132 private:
133 Edge *in;
134 Edge *out;
135 Graph *graph;
136
137 int visited;
138
139 int16_t inCount;
140 int16_t outCount;
141 public:
142 int tag; // for temporary use
143
144 friend class Graph;
145 };
146
147 public:
148 Graph();
149 virtual ~Graph(); // does *not* free the nodes (make it an option ?)
150
getRoot()151 inline Node *getRoot() const { return root; }
152
getSize()153 inline unsigned int getSize() const { return size; }
154
155 inline int nextSequence();
156
157 void insert(Node *node); // attach to or set as root
158
159 IteratorRef iteratorDFS(bool preorder = true);
160 IteratorRef iteratorCFG();
161
162 // safe iterators are unaffected by changes to the *edges* of the graph
163 IteratorRef safeIteratorDFS(bool preorder = true);
164 IteratorRef safeIteratorCFG();
165
166 void classifyEdges();
167
168 // @weights: indexed by Node::tag
169 int findLightestPathWeight(Node *, Node *, const std::vector<int>& weights);
170
171 private:
172 void classifyDFS(Node *, int&);
173
174 private:
175 Node *root;
176 unsigned int size;
177 int sequence;
178 };
179
nextSequence()180 int Graph::nextSequence()
181 {
182 return ++sequence;
183 }
184
parent()185 Graph::Node *Graph::Node::parent() const
186 {
187 if (inCount != 1)
188 return NULL;
189 assert(in);
190 return in->origin;
191 }
192
visit(int v)193 bool Graph::Node::visit(int v)
194 {
195 if (visited == v)
196 return false;
197 visited = v;
198 return true;
199 }
200
getSequence()201 int Graph::Node::getSequence() const
202 {
203 return visited;
204 }
205
outgoing(bool reverse)206 Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const
207 {
208 return EdgeIterator(out, 0, reverse);
209 }
210
incident(bool reverse)211 Graph::EdgeIterator Graph::Node::incident(bool reverse) const
212 {
213 return EdgeIterator(in, 1, reverse);
214 }
215
incidentCountFwd()216 int Graph::Node::incidentCountFwd() const
217 {
218 int n = 0;
219 for (EdgeIterator ei = incident(); !ei.end(); ei.next())
220 if (ei.getType() != Edge::BACK)
221 ++n;
222 return n;
223 }
224
225 } // namespace nv50_ir
226
227 #endif // __NV50_IR_GRAPH_H__
228