src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp

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