| 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 |
#include "nv50_ir_graph.h" |
| 24 |
#include <limits> |
| 25 |
#include <list> |
| 26 |
#include <stack> |
| 27 |
#include "nv50_ir.h" |
| 28 |
|
| 29 |
namespace nv50_ir { |
| 30 |
|
| 31 |
Graph::Graph() |
| 32 |
{ |
| 33 |
root = NULL; |
| 34 |
size = 0; |
| 35 |
sequence = 0; |
| 36 |
} |
| 37 |
|
| 38 |
Graph::~Graph() |
| 39 |
{ |
| 40 |
for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next()) |
| 41 |
reinterpret_cast<Node *>(it->get())->cut(); |
| 42 |
} |
| 43 |
|
| 44 |
void Graph::insert(Node *node) |
| 45 |
{ |
| 46 |
if (!root) |
| 47 |
root = node; |
| 48 |
|
| 49 |
node->graph = this; |
| 50 |
size++; |
| 51 |
} |
| 52 |
|
| 53 |
void Graph::Edge::unlink() |
| 54 |
{ |
| 55 |
if (origin) { |
| 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]; |
| 60 |
|
| 61 |
--origin->outCount; |
| 62 |
} |
| 63 |
if (target) { |
| 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]; |
| 68 |
|
| 69 |
--target->inCount; |
| 70 |
} |
| 71 |
} |
| 72 |
|
| 73 |
const char *Graph::Edge::typeStr() const |
| 74 |
{ |
| 75 |
switch (type) { |
| 76 |
case TREE: return "tree"; |
| 77 |
case FORWARD: return "forward"; |
| 78 |
case BACK: return "back"; |
| 79 |
case CROSS: return "cross"; |
| 80 |
case UNKNOWN: |
| 81 |
default: |
| 82 |
return "unk"; |
| 83 |
} |
| 84 |
} |
| 85 |
|
| 86 |
Graph::Node::Node(void *priv) : data(priv), |
| 87 |
in(0), out(0), graph(0), |
| 88 |
visited(0), |
| 89 |
inCount(0), outCount(0), |
| 90 |
tag(0) |
| 91 |
{ |
| 92 |
// nothing to do |
| 93 |
} |
| 94 |
|
| 95 |
void Graph::Node::attach(Node *node, Edge::Type kind) |
| 96 |
{ |
| 97 |
Edge *edge = new Edge(this, node, kind); |
| 98 |
|
| 99 |
// insert head |
| 100 |
if (this->out) { |
| 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; |
| 105 |
} |
| 106 |
this->out = edge; |
| 107 |
|
| 108 |
if (node->in) { |
| 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; |
| 113 |
} |
| 114 |
node->in = edge; |
| 115 |
|
| 116 |
++this->outCount; |
| 117 |
++node->inCount; |
| 118 |
|
| 119 |
assert(graph || node->graph); |
| 120 |
if (!node->graph) |
| 121 |
graph->insert(node); |
| 122 |
if (!graph) |
| 123 |
node->graph->insert(this); |
| 124 |
|
| 125 |
if (kind == Edge::UNKNOWN) |
| 126 |
graph->classifyEdges(); |
| 127 |
} |
| 128 |
|
| 129 |
bool Graph::Node::detach(Graph::Node *node) |
| 130 |
{ |
| 131 |
EdgeIterator ei = this->outgoing(); |
| 132 |
for (; !ei.end(); ei.next()) |
| 133 |
if (ei.getNode() == node) |
| 134 |
break; |
| 135 |
if (ei.end()) { |
| 136 |
ERROR("no such node attached\n"); |
| 137 |
return false; |
| 138 |
} |
| 139 |
delete ei.getEdge(); |
| 140 |
return true; |
| 141 |
} |
| 142 |
|
| 143 |
// Cut a node from the graph, deleting all attached edges. |
| 144 |
void Graph::Node::cut() |
| 145 |
{ |
| 146 |
while (out) |
| 147 |
delete out; |
| 148 |
while (in) |
| 149 |
delete in; |
| 150 |
|
| 151 |
if (graph) { |
| 152 |
if (graph->root == this) |
| 153 |
graph->root = NULL; |
| 154 |
graph = NULL; |
| 155 |
} |
| 156 |
} |
| 157 |
|
| 158 |
Graph::Edge::Edge(Node *org, Node *tgt, Type kind) |
| 159 |
{ |
| 160 |
target = tgt; |
| 161 |
origin = org; |
| 162 |
type = kind; |
| 163 |
|
| 164 |
next[0] = next[1] = this; |
| 165 |
prev[0] = prev[1] = this; |
| 166 |
} |
| 167 |
|
| 168 |
bool |
| 169 |
Graph::Node::reachableBy(const Node *node, const Node *term) const |
| 170 |
{ |
| 171 |
std::stack<const Node *> stack; |
| 172 |
const Node *pos = NULL; |
| 173 |
const int seq = graph->nextSequence(); |
| 174 |
|
| 175 |
stack.push(node); |
| 176 |
|
| 177 |
while (!stack.empty()) { |
| 178 |
pos = stack.top(); |
| 179 |
stack.pop(); |
| 180 |
|
| 181 |
if (pos == this) |
| 182 |
return true; |
| 183 |
if (pos == term) |
| 184 |
continue; |
| 185 |
|
| 186 |
for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) { |
| 187 |
if (ei.getType() == Edge::BACK) |
| 188 |
continue; |
| 189 |
if (ei.getNode()->visit(seq)) |
| 190 |
stack.push(ei.getNode()); |
| 191 |
} |
| 192 |
} |
| 193 |
return pos == this; |
| 194 |
} |
| 195 |
|
| 196 |
class DFSIterator : public Iterator |
| 197 |
{ |
| 198 |
public: |
| 199 |
DFSIterator(Graph *graph, const bool preorder) |
| 200 |
{ |
| 201 |
unsigned int seq = graph->nextSequence(); |
| 202 |
|
| 203 |
nodes = new Graph::Node * [graph->getSize() + 1]; |
| 204 |
count = 0; |
| 205 |
pos = 0; |
| 206 |
nodes[graph->getSize()] = 0; |
| 207 |
|
| 208 |
if (graph->getRoot()) { |
| 209 |
graph->getRoot()->visit(seq); |
| 210 |
search(graph->getRoot(), preorder, seq); |
| 211 |
} |
| 212 |
} |
| 213 |
|
| 214 |
~DFSIterator() |
| 215 |
{ |
| 216 |
if (nodes) |
| 217 |
delete[] nodes; |
| 218 |
} |
| 219 |
|
| 220 |
void search(Graph::Node *node, const bool preorder, const int sequence) |
| 221 |
{ |
| 222 |
if (preorder) |
| 223 |
nodes[count++] = node; |
| 224 |
|
| 225 |
for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) |
| 226 |
if (ei.getNode()->visit(sequence)) |
| 227 |
search(ei.getNode(), preorder, sequence); |
| 228 |
|
| 229 |
if (!preorder) |
| 230 |
nodes[count++] = node; |
| 231 |
} |
| 232 |
|
| 233 |
virtual bool end() const { return pos >= count; } |
| 234 |
virtual void next() { if (pos < count) ++pos; } |
| 235 |
virtual void *get() const { return nodes[pos]; } |
| 236 |
virtual void reset() { pos = 0; } |
| 237 |
|
| 238 |
protected: |
| 239 |
Graph::Node **nodes; |
| 240 |
int count; |
| 241 |
int pos; |
| 242 |
}; |
| 243 |
|
| 244 |
IteratorRef Graph::iteratorDFS(bool preorder) |
| 245 |
{ |
| 246 |
return IteratorRef(new DFSIterator(this, preorder)); |
| 247 |
} |
| 248 |
|
| 249 |
IteratorRef Graph::safeIteratorDFS(bool preorder) |
| 250 |
{ |
| 251 |
return this->iteratorDFS(preorder); |
| 252 |
} |
| 253 |
|
| 254 |
class CFGIterator : public Iterator |
| 255 |
{ |
| 256 |
public: |
| 257 |
CFGIterator(Graph *graph) |
| 258 |
{ |
| 259 |
nodes = new Graph::Node * [graph->getSize() + 1]; |
| 260 |
count = 0; |
| 261 |
pos = 0; |
| 262 |
nodes[graph->getSize()] = 0; |
| 263 |
|
| 264 |
// TODO: argh, use graph->sequence instead of tag and just raise it by > 1 |
| 265 |
for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next()) |
| 266 |
reinterpret_cast<Graph::Node *>(it->get())->tag = 0; |
| 267 |
|
| 268 |
if (graph->getRoot()) |
| 269 |
search(graph->getRoot(), graph->nextSequence()); |
| 270 |
} |
| 271 |
|
| 272 |
~CFGIterator() |
| 273 |
{ |
| 274 |
if (nodes) |
| 275 |
delete[] nodes; |
| 276 |
} |
| 277 |
|
| 278 |
virtual void *get() const { return nodes[pos]; } |
| 279 |
virtual bool end() const { return pos >= count; } |
| 280 |
virtual void next() { if (pos < count) ++pos; } |
| 281 |
virtual void reset() { pos = 0; } |
| 282 |
|
| 283 |
private: |
| 284 |
void search(Graph::Node *node, const int sequence) |
| 285 |
{ |
| 286 |
Stack bb, cross; |
| 287 |
|
| 288 |
bb.push(node); |
| 289 |
|
| 290 |
while (bb.getSize() || cross.getSize()) { |
| 291 |
if (bb.getSize() == 0) |
| 292 |
cross.moveTo(bb); |
| 293 |
|
| 294 |
node = reinterpret_cast<Graph::Node *>(bb.pop().u.p); |
| 295 |
assert(node); |
| 296 |
if (!node->visit(sequence)) |
| 297 |
continue; |
| 298 |
node->tag = 0; |
| 299 |
|
| 300 |
for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { |
| 301 |
switch (ei.getType()) { |
| 302 |
case Graph::Edge::TREE: |
| 303 |
case Graph::Edge::FORWARD: |
| 304 |
if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd()) |
| 305 |
bb.push(ei.getNode()); |
| 306 |
break; |
| 307 |
case Graph::Edge::BACK: |
| 308 |
continue; |
| 309 |
case Graph::Edge::CROSS: |
| 310 |
if (++(ei.getNode()->tag) == 1) |
| 311 |
cross.push(ei.getNode()); |
| 312 |
break; |
| 313 |
default: |
| 314 |
assert(!"unknown edge kind in CFG"); |
| 315 |
break; |
| 316 |
} |
| 317 |
} |
| 318 |
nodes[count++] = node; |
| 319 |
} |
| 320 |
} |
| 321 |
|
| 322 |
private: |
| 323 |
Graph::Node **nodes; |
| 324 |
int count; |
| 325 |
int pos; |
| 326 |
}; |
| 327 |
|
| 328 |
IteratorRef Graph::iteratorCFG() |
| 329 |
{ |
| 330 |
return IteratorRef(new CFGIterator(this)); |
| 331 |
} |
| 332 |
|
| 333 |
IteratorRef Graph::safeIteratorCFG() |
| 334 |
{ |
| 335 |
return this->iteratorCFG(); |
| 336 |
} |
| 337 |
|
| 338 |
/** |
| 339 |
* Edge classification: |
| 340 |
* |
| 341 |
* We have a graph and want to classify the edges into one of four types: |
| 342 |
* - TREE: edges that belong to a spanning tree of the graph |
| 343 |
* - FORWARD: edges from a node to a descendent in the spanning tree |
| 344 |
* - BACK: edges from a node to a parent (or itself) in the spanning tree |
| 345 |
* - CROSS: all other edges (because they cross between branches in the |
| 346 |
* spanning tree) |
| 347 |
*/ |
| 348 |
void Graph::classifyEdges() |
| 349 |
{ |
| 350 |
int seq; |
| 351 |
|
| 352 |
for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) { |
| 353 |
Node *node = reinterpret_cast<Node *>(it->get()); |
| 354 |
node->visit(0); |
| 355 |
node->tag = 0; |
| 356 |
} |
| 357 |
|
| 358 |
classifyDFS(root, (seq = 0)); |
| 359 |
|
| 360 |
sequence = seq; |
| 361 |
} |
| 362 |
|
| 363 |
void Graph::classifyDFS(Node *curr, int& seq) |
| 364 |
{ |
| 365 |
Graph::Edge *edge; |
| 366 |
Graph::Node *node; |
| 367 |
|
| 368 |
curr->visit(++seq); |
| 369 |
curr->tag = 1; |
| 370 |
|
| 371 |
for (edge = curr->out; edge; edge = edge->next[0]) { |
| 372 |
node = edge->target; |
| 373 |
|
| 374 |
if (node->getSequence() == 0) { |
| 375 |
edge->type = Edge::TREE; |
| 376 |
classifyDFS(node, seq); |
| 377 |
} else |
| 378 |
if (node->getSequence() > curr->getSequence()) { |
| 379 |
edge->type = Edge::FORWARD; |
| 380 |
} else { |
| 381 |
edge->type = node->tag ? Edge::BACK : Edge::CROSS; |
| 382 |
} |
| 383 |
} |
| 384 |
|
| 385 |
for (edge = curr->in; edge; edge = edge->next[1]) { |
| 386 |
node = edge->origin; |
| 387 |
|
| 388 |
if (node->getSequence() == 0) { |
| 389 |
edge->type = Edge::TREE; |
| 390 |
classifyDFS(node, seq); |
| 391 |
} else |
| 392 |
if (node->getSequence() > curr->getSequence()) { |
| 393 |
edge->type = Edge::FORWARD; |
| 394 |
} else { |
| 395 |
edge->type = node->tag ? Edge::BACK : Edge::CROSS; |
| 396 |
} |
| 397 |
} |
| 398 |
|
| 399 |
curr->tag = 0; |
| 400 |
} |
| 401 |
|
| 402 |
// @dist is indexed by Node::tag, returns -1 if no path found |
| 403 |
int |
| 404 |
Graph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight) |
| 405 |
{ |
| 406 |
std::vector<int> path(weight.size(), std::numeric_limits<int>::max()); |
| 407 |
std::list<Node *> nodeList; |
| 408 |
const int seq = nextSequence(); |
| 409 |
|
| 410 |
path[a->tag] = 0; |
| 411 |
for (Node *c = a; c && c != b;) { |
| 412 |
const int p = path[c->tag] + weight[c->tag]; |
| 413 |
for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) { |
| 414 |
Node *t = ei.getNode(); |
| 415 |
if (t->getSequence() < seq) { |
| 416 |
if (path[t->tag] == std::numeric_limits<int>::max()) |
| 417 |
nodeList.push_front(t); |
| 418 |
if (p < path[t->tag]) |
| 419 |
path[t->tag] = p; |
| 420 |
} |
| 421 |
} |
| 422 |
c->visit(seq); |
| 423 |
Node *next = NULL; |
| 424 |
for (std::list<Node *>::iterator n = nodeList.begin(); |
| 425 |
n != nodeList.end(); ++n) { |
| 426 |
if (!next || path[(*n)->tag] < path[next->tag]) |
| 427 |
next = *n; |
| 428 |
if ((*n) == c) { |
| 429 |
// erase visited |
| 430 |
n = nodeList.erase(n); |
| 431 |
--n; |
| 432 |
} |
| 433 |
} |
| 434 |
c = next; |
| 435 |
} |
| 436 |
if (path[b->tag] == std::numeric_limits<int>::max()) |
| 437 |
return -1; |
| 438 |
return path[b->tag]; |
| 439 |
} |
| 440 |
|
| 441 |
} // namespace nv50_ir |