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 DUMMY
51 };
52
53 Edge(Node *dst, Node *src, Type kind);
~Edge()54 ~Edge() { unlink(); }
55
getOrigin()56 inline Node *getOrigin() const { return origin; }
getTarget()57 inline Node *getTarget() const { return target; }
58
getType()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:
EdgeIterator()78 EdgeIterator() : e(0), t(0), d(0), rev(false) { }
EdgeIterator(Graph::Edge * first,int dir,bool reverse)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
next()85 virtual void next()
86 {
87 Graph::Edge *n = (rev ? e->prev[d] : e->next[d]);
88 e = (n == t ? NULL : n);
89 }
end()90 virtual bool end() const { return !e; }
get()91 virtual void *get() const { return e; }
92
getNode()93 inline Node *getNode() const { assert(e); return d ?
94 e->origin : e->target; }
getEdge()95 inline Edge *getEdge() const { return e; }
getType()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 *);
~Node()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
incidentCount()126 inline int incidentCount() const { return inCount; }
outgoingCount()127 inline int outgoingCount() const { return outCount; }
128
getGraph()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 virtual ~Graph(); // does *not* free the nodes (make it an option ?)
151
getRoot()152 inline Node *getRoot() const { return root; }
153
getSize()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
nextSequence()181 int Graph::nextSequence()
182 {
183 return ++sequence;
184 }
185
parent()186 Graph::Node *Graph::Node::parent() const
187 {
188 if (inCount != 1)
189 return NULL;
190 assert(in);
191 return in->origin;
192 }
193
visit(int v)194 bool Graph::Node::visit(int v)
195 {
196 if (visited == v)
197 return false;
198 visited = v;
199 return true;
200 }
201
getSequence()202 int Graph::Node::getSequence() const
203 {
204 return visited;
205 }
206
outgoing(bool reverse)207 Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const
208 {
209 return EdgeIterator(out, 0, reverse);
210 }
211
incident(bool reverse)212 Graph::EdgeIterator Graph::Node::incident(bool reverse) const
213 {
214 return EdgeIterator(in, 1, reverse);
215 }
216
incidentCountFwd()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