0,0 → 1,436 |
/* |
* Copyright 2011 Christoph Bumiller |
* |
* Permission is hereby granted, free of charge, to any person obtaining a |
* copy of this software and associated documentation files (the "Software"), |
* to deal in the Software without restriction, including without limitation |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
* and/or sell copies of the Software, and to permit persons to whom the |
* Software is furnished to do so, subject to the following conditions: |
* |
* The above copyright notice and this permission notice shall be included in |
* all copies or substantial portions of the Software. |
* |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
* OTHER DEALINGS IN THE SOFTWARE. |
*/ |
|
#include "nv50_ir_graph.h" |
#include <limits> |
#include <list> |
#include <stack> |
#include "nv50_ir.h" |
|
namespace nv50_ir { |
|
Graph::Graph() |
{ |
root = NULL; |
size = 0; |
sequence = 0; |
} |
|
Graph::~Graph() |
{ |
for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next()) |
reinterpret_cast<Node *>(it->get())->cut(); |
} |
|
void Graph::insert(Node *node) |
{ |
if (!root) |
root = node; |
|
node->graph = this; |
size++; |
} |
|
void Graph::Edge::unlink() |
{ |
if (origin) { |
prev[0]->next[0] = next[0]; |
next[0]->prev[0] = prev[0]; |
if (origin->out == this) |
origin->out = (next[0] == this) ? NULL : next[0]; |
|
--origin->outCount; |
} |
if (target) { |
prev[1]->next[1] = next[1]; |
next[1]->prev[1] = prev[1]; |
if (target->in == this) |
target->in = (next[1] == this) ? NULL : next[1]; |
|
--target->inCount; |
} |
} |
|
const char *Graph::Edge::typeStr() const |
{ |
switch (type) { |
case TREE: return "tree"; |
case FORWARD: return "forward"; |
case BACK: return "back"; |
case CROSS: return "cross"; |
case DUMMY: return "dummy"; |
case UNKNOWN: |
default: |
return "unk"; |
} |
} |
|
Graph::Node::Node(void *priv) : data(priv), |
in(0), out(0), graph(0), |
visited(0), |
inCount(0), outCount(0) |
{ |
// nothing to do |
} |
|
void Graph::Node::attach(Node *node, Edge::Type kind) |
{ |
Edge *edge = new Edge(this, node, kind); |
|
// insert head |
if (this->out) { |
edge->next[0] = this->out; |
edge->prev[0] = this->out->prev[0]; |
edge->prev[0]->next[0] = edge; |
this->out->prev[0] = edge; |
} |
this->out = edge; |
|
if (node->in) { |
edge->next[1] = node->in; |
edge->prev[1] = node->in->prev[1]; |
edge->prev[1]->next[1] = edge; |
node->in->prev[1] = edge; |
} |
node->in = edge; |
|
++this->outCount; |
++node->inCount; |
|
assert(graph || node->graph); |
if (!node->graph) |
graph->insert(node); |
if (!graph) |
node->graph->insert(this); |
|
if (kind == Edge::UNKNOWN) |
graph->classifyEdges(); |
} |
|
bool Graph::Node::detach(Graph::Node *node) |
{ |
EdgeIterator ei = this->outgoing(); |
for (; !ei.end(); ei.next()) |
if (ei.getNode() == node) |
break; |
if (ei.end()) { |
ERROR("no such node attached\n"); |
return false; |
} |
delete ei.getEdge(); |
return true; |
} |
|
// Cut a node from the graph, deleting all attached edges. |
void Graph::Node::cut() |
{ |
while (out) |
delete out; |
while (in) |
delete in; |
|
if (graph) { |
if (graph->root == this) |
graph->root = NULL; |
graph = NULL; |
} |
} |
|
Graph::Edge::Edge(Node *org, Node *tgt, Type kind) |
{ |
target = tgt; |
origin = org; |
type = kind; |
|
next[0] = next[1] = this; |
prev[0] = prev[1] = this; |
} |
|
bool |
Graph::Node::reachableBy(const Node *node, const Node *term) const |
{ |
std::stack<const Node *> stack; |
const Node *pos = NULL; |
const int seq = graph->nextSequence(); |
|
stack.push(node); |
|
while (!stack.empty()) { |
pos = stack.top(); |
stack.pop(); |
|
if (pos == this) |
return true; |
if (pos == term) |
continue; |
|
for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) { |
if (ei.getType() == Edge::BACK || ei.getType() == Edge::DUMMY) |
continue; |
if (ei.getNode()->visit(seq)) |
stack.push(ei.getNode()); |
} |
} |
return pos == this; |
} |
|
class DFSIterator : public Iterator |
{ |
public: |
DFSIterator(Graph *graph, const bool preorder) |
{ |
unsigned int seq = graph->nextSequence(); |
|
nodes = new Graph::Node * [graph->getSize() + 1]; |
count = 0; |
pos = 0; |
nodes[graph->getSize()] = 0; |
|
if (graph->getRoot()) { |
graph->getRoot()->visit(seq); |
search(graph->getRoot(), preorder, seq); |
} |
} |
|
~DFSIterator() |
{ |
if (nodes) |
delete[] nodes; |
} |
|
void search(Graph::Node *node, const bool preorder, const int sequence) |
{ |
if (preorder) |
nodes[count++] = node; |
|
for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) |
if (ei.getNode()->visit(sequence)) |
search(ei.getNode(), preorder, sequence); |
|
if (!preorder) |
nodes[count++] = node; |
} |
|
virtual bool end() const { return pos >= count; } |
virtual void next() { if (pos < count) ++pos; } |
virtual void *get() const { return nodes[pos]; } |
virtual void reset() { pos = 0; } |
|
protected: |
Graph::Node **nodes; |
int count; |
int pos; |
}; |
|
IteratorRef Graph::iteratorDFS(bool preorder) |
{ |
return IteratorRef(new DFSIterator(this, preorder)); |
} |
|
IteratorRef Graph::safeIteratorDFS(bool preorder) |
{ |
return this->iteratorDFS(preorder); |
} |
|
class CFGIterator : public Iterator |
{ |
public: |
CFGIterator(Graph *graph) |
{ |
nodes = new Graph::Node * [graph->getSize() + 1]; |
count = 0; |
pos = 0; |
nodes[graph->getSize()] = 0; |
|
// TODO: argh, use graph->sequence instead of tag and just raise it by > 1 |
for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next()) |
reinterpret_cast<Graph::Node *>(it->get())->tag = 0; |
|
if (graph->getRoot()) |
search(graph->getRoot(), graph->nextSequence()); |
} |
|
~CFGIterator() |
{ |
if (nodes) |
delete[] nodes; |
} |
|
virtual void *get() const { return nodes[pos]; } |
virtual bool end() const { return pos >= count; } |
virtual void next() { if (pos < count) ++pos; } |
virtual void reset() { pos = 0; } |
|
private: |
void search(Graph::Node *node, const int sequence) |
{ |
Stack bb, cross; |
|
bb.push(node); |
|
while (bb.getSize()) { |
node = reinterpret_cast<Graph::Node *>(bb.pop().u.p); |
assert(node); |
if (!node->visit(sequence)) |
continue; |
node->tag = 0; |
|
for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { |
switch (ei.getType()) { |
case Graph::Edge::TREE: |
case Graph::Edge::FORWARD: |
case Graph::Edge::DUMMY: |
if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd()) |
bb.push(ei.getNode()); |
break; |
case Graph::Edge::BACK: |
continue; |
case Graph::Edge::CROSS: |
if (++(ei.getNode()->tag) == 1) |
cross.push(ei.getNode()); |
break; |
default: |
assert(!"unknown edge kind in CFG"); |
break; |
} |
} |
nodes[count++] = node; |
|
if (bb.getSize() == 0) |
cross.moveTo(bb); |
} |
} |
|
private: |
Graph::Node **nodes; |
int count; |
int pos; |
}; |
|
IteratorRef Graph::iteratorCFG() |
{ |
return IteratorRef(new CFGIterator(this)); |
} |
|
IteratorRef Graph::safeIteratorCFG() |
{ |
return this->iteratorCFG(); |
} |
|
void Graph::classifyEdges() |
{ |
int seq; |
|
for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) { |
Node *node = reinterpret_cast<Node *>(it->get()); |
node->visit(0); |
node->tag = 0; |
} |
|
classifyDFS(root, (seq = 0)); |
|
sequence = seq; |
} |
|
void Graph::classifyDFS(Node *curr, int& seq) |
{ |
Graph::Edge *edge; |
Graph::Node *node; |
|
curr->visit(++seq); |
curr->tag = 1; |
|
for (edge = curr->out; edge; edge = edge->next[0]) { |
node = edge->target; |
if (edge->type == Edge::DUMMY) |
continue; |
|
if (node->getSequence() == 0) { |
edge->type = Edge::TREE; |
classifyDFS(node, seq); |
} else |
if (node->getSequence() > curr->getSequence()) { |
edge->type = Edge::FORWARD; |
} else { |
edge->type = node->tag ? Edge::BACK : Edge::CROSS; |
} |
} |
|
for (edge = curr->in; edge; edge = edge->next[1]) { |
node = edge->origin; |
if (edge->type == Edge::DUMMY) |
continue; |
|
if (node->getSequence() == 0) { |
edge->type = Edge::TREE; |
classifyDFS(node, seq); |
} else |
if (node->getSequence() > curr->getSequence()) { |
edge->type = Edge::FORWARD; |
} else { |
edge->type = node->tag ? Edge::BACK : Edge::CROSS; |
} |
} |
|
curr->tag = 0; |
} |
|
// @dist is indexed by Node::tag, returns -1 if no path found |
int |
Graph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight) |
{ |
std::vector<int> path(weight.size(), std::numeric_limits<int>::max()); |
std::list<Node *> nodeList; |
const int seq = nextSequence(); |
|
path[a->tag] = 0; |
for (Node *c = a; c && c != b;) { |
const int p = path[c->tag] + weight[c->tag]; |
for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) { |
Node *t = ei.getNode(); |
if (t->getSequence() < seq) { |
if (path[t->tag] == std::numeric_limits<int>::max()) |
nodeList.push_front(t); |
if (p < path[t->tag]) |
path[t->tag] = p; |
} |
} |
c->visit(seq); |
Node *next = NULL; |
for (std::list<Node *>::iterator n = nodeList.begin(); |
n != nodeList.end(); ++n) { |
if (!next || path[(*n)->tag] < path[next->tag]) |
next = *n; |
if ((*n) == c) { |
// erase visited |
n = nodeList.erase(n); |
--n; |
} |
} |
c = next; |
} |
if (path[b->tag] == std::numeric_limits<int>::max()) |
return -1; |
return path[b->tag]; |
} |
|
} // namespace nv50_ir |