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 #include "nv50_ir_graph.h"
36 Iterator
*iter
= this->safeIteratorDFS();
38 for (; !iter
->end(); iter
->next())
39 reinterpret_cast<Node
*>(iter
->get())->cut();
44 void Graph::insert(Node
*node
)
53 void Graph::Edge::unlink()
56 prev
[0]->next
[0] = next
[0];
57 next
[0]->prev
[0] = prev
[0];
58 if (origin
->out
== this)
59 origin
->out
= (next
[0] == this) ? NULL
: next
[0];
64 prev
[1]->next
[1] = next
[1];
65 next
[1]->prev
[1] = prev
[1];
66 if (target
->in
== this)
67 target
->in
= (next
[1] == this) ? NULL
: next
[1];
73 const char *Graph::Edge::typeStr() const
76 case TREE
: return "tree";
77 case FORWARD
: return "forward";
78 case BACK
: return "back";
79 case CROSS
: return "cross";
80 case DUMMY
: return "dummy";
87 Graph::Node::Node(void *priv
) : data(priv
),
88 in(0), out(0), graph(0),
90 inCount(0), outCount(0)
95 void Graph::Node::attach(Node
*node
, Edge::Type kind
)
97 Edge
*edge
= new Edge(this, node
, kind
);
101 edge
->next
[0] = this->out
;
102 edge
->prev
[0] = this->out
->prev
[0];
103 edge
->prev
[0]->next
[0] = edge
;
104 this->out
->prev
[0] = edge
;
109 edge
->next
[1] = node
->in
;
110 edge
->prev
[1] = node
->in
->prev
[1];
111 edge
->prev
[1]->next
[1] = edge
;
112 node
->in
->prev
[1] = edge
;
119 assert(graph
|| node
->graph
);
123 node
->graph
->insert(this);
125 if (kind
== Edge::UNKNOWN
)
126 graph
->classifyEdges();
129 bool Graph::Node::detach(Graph::Node
*node
)
131 EdgeIterator ei
= this->outgoing();
132 for (; !ei
.end(); ei
.next())
133 if (ei
.getNode() == node
)
136 ERROR("no such node attached\n");
143 // Cut a node from the graph, deleting all attached edges.
144 void Graph::Node::cut()
152 if (graph
->root
== this)
158 Graph::Edge::Edge(Node
*org
, Node
*tgt
, Type kind
)
164 next
[0] = next
[1] = this;
165 prev
[0] = prev
[1] = this;
169 Graph::Node::reachableBy(Node
*node
, Node
*term
)
173 const int seq
= graph
->nextSequence();
177 while (stack
.getSize()) {
178 pos
= reinterpret_cast<Node
*>(stack
.pop().u
.p
);
185 for (EdgeIterator ei
= pos
->outgoing(); !ei
.end(); ei
.next()) {
186 if (ei
.getType() == Edge::BACK
|| ei
.getType() == Edge::DUMMY
)
188 if (ei
.getNode()->visit(seq
))
189 stack
.push(ei
.getNode());
195 class DFSIterator
: public Graph::GraphIterator
198 DFSIterator(Graph
*graph
, const bool preorder
)
200 unsigned int seq
= graph
->nextSequence();
202 nodes
= new Graph::Node
* [graph
->getSize() + 1];
205 nodes
[graph
->getSize()] = 0;
207 if (graph
->getRoot()) {
208 graph
->getRoot()->visit(seq
);
209 search(graph
->getRoot(), preorder
, seq
);
219 void search(Graph::Node
*node
, const bool preorder
, const int sequence
)
222 nodes
[count
++] = node
;
224 for (Graph::EdgeIterator ei
= node
->outgoing(); !ei
.end(); ei
.next())
225 if (ei
.getNode()->visit(sequence
))
226 search(ei
.getNode(), preorder
, sequence
);
229 nodes
[count
++] = node
;
232 virtual bool end() const { return pos
>= count
; }
233 virtual void next() { if (pos
< count
) ++pos
; }
234 virtual void *get() const { return nodes
[pos
]; }
236 void reset() { pos
= 0; }
244 Graph::GraphIterator
*Graph::iteratorDFS(bool preorder
)
246 return new DFSIterator(this, preorder
);
249 Graph::GraphIterator
*Graph::safeIteratorDFS(bool preorder
)
251 return this->iteratorDFS(preorder
);
254 class CFGIterator
: public Graph::GraphIterator
257 CFGIterator(Graph
*graph
)
259 nodes
= new Graph::Node
* [graph
->getSize() + 1];
262 nodes
[graph
->getSize()] = 0;
264 // TODO: argh, use graph->sequence instead of tag and just raise it by > 1
266 for (iter
= graph
->iteratorDFS(); !iter
->end(); iter
->next())
267 reinterpret_cast<Graph::Node
*>(iter
->get())->tag
= 0;
268 graph
->putIterator(iter
);
270 if (graph
->getRoot())
271 search(graph
->getRoot(), graph
->nextSequence());
280 virtual void *get() const { return nodes
[pos
]; }
281 virtual bool end() const { return pos
>= count
; }
282 virtual void next() { if (pos
< count
) ++pos
; }
285 void search(Graph::Node
*node
, const int sequence
)
291 while (bb
.getSize()) {
292 node
= reinterpret_cast<Graph::Node
*>(bb
.pop().u
.p
);
294 if (!node
->visit(sequence
))
298 for (Graph::EdgeIterator ei
= node
->outgoing(); !ei
.end(); ei
.next()) {
299 switch (ei
.getType()) {
300 case Graph::Edge::TREE
:
301 case Graph::Edge::FORWARD
:
302 case Graph::Edge::DUMMY
:
303 if (++(ei
.getNode()->tag
) == ei
.getNode()->incidentCountFwd())
304 bb
.push(ei
.getNode());
306 case Graph::Edge::BACK
:
308 case Graph::Edge::CROSS
:
309 if (++(ei
.getNode()->tag
) == 1)
310 cross
.push(ei
.getNode());
313 assert(!"unknown edge kind in CFG");
317 nodes
[count
++] = node
;
319 if (bb
.getSize() == 0)
330 Graph::GraphIterator
*Graph::iteratorCFG()
332 return new CFGIterator(this);
335 Graph::GraphIterator
*Graph::safeIteratorCFG()
337 return this->iteratorCFG();
340 void Graph::classifyEdges()
345 for (iter
= new DFSIterator(this, true); !iter
->end(); iter
->next()) {
346 Node
*node
= reinterpret_cast<Node
*>(iter
->get());
352 classifyDFS(root
, (seq
= 0));
357 void Graph::classifyDFS(Node
*curr
, int& seq
)
365 for (edge
= curr
->out
; edge
; edge
= edge
->next
[0]) {
367 if (edge
->type
== Edge::DUMMY
)
370 if (node
->getSequence() == 0) {
371 edge
->type
= Edge::TREE
;
372 classifyDFS(node
, seq
);
374 if (node
->getSequence() > curr
->getSequence()) {
375 edge
->type
= Edge::FORWARD
;
377 edge
->type
= node
->tag
? Edge::BACK
: Edge::CROSS
;
381 for (edge
= curr
->in
; edge
; edge
= edge
->next
[1]) {
383 if (edge
->type
== Edge::DUMMY
)
386 if (node
->getSequence() == 0) {
387 edge
->type
= Edge::TREE
;
388 classifyDFS(node
, seq
);
390 if (node
->getSequence() > curr
->getSequence()) {
391 edge
->type
= Edge::FORWARD
;
393 edge
->type
= node
->tag
? Edge::BACK
: Edge::CROSS
;
400 } // namespace nv50_ir