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 DUMMY:   return "dummy";
  81    case UNKNOWN:
  82    default:
  83       return "unk";
  84    }
  85 }
  86
  87 Graph::Node::Node(void *priv) : data(priv),
  88                                 in(0), out(0), graph(0),
  89                                 visited(0),
  90                                 inCount(0), outCount(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 || ei.getType() == Edge::DUMMY)
 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()) {
 291          node = reinterpret_cast<Graph::Node *>(bb.pop().u.p);
 292          assert(node);
 293          if (!node->visit(sequence))
 294             continue;
 295          node->tag = 0;
 296
 297          for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {
 298             switch (ei.getType()) {
 299             case Graph::Edge::TREE:
 300             case Graph::Edge::FORWARD:
 301             case Graph::Edge::DUMMY:
 302                if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd())
 303                   bb.push(ei.getNode());
 304                break;
 305             case Graph::Edge::BACK:
 306                continue;
 307             case Graph::Edge::CROSS:
 308                if (++(ei.getNode()->tag) == 1)
 309                   cross.push(ei.getNode());
 310                break;
 311             default:
 312                assert(!"unknown edge kind in CFG");
 313                break;
 314             }
 315          }
 316          nodes[count++] = node;
 317
 318          if (bb.getSize() == 0)
 319             cross.moveTo(bb);
 320       }
 321    }
 322
 323 private:
 324    Graph::Node **nodes;
 325    int count;
 326    int pos;
 327 };
 328
 329 IteratorRef Graph::iteratorCFG()
 330 {
 331    return IteratorRef(new CFGIterator(this));
 332 }
 333
 334 IteratorRef Graph::safeIteratorCFG()
 335 {
 336    return this->iteratorCFG();
 337 }
 338
 339 void Graph::classifyEdges()
 340 {
 341    int seq;
 342
 343    for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) {
 344       Node *node = reinterpret_cast<Node *>(it->get());
 345       node->visit(0);
 346       node->tag = 0;
 347    }
 348
 349    classifyDFS(root, (seq = 0));
 350
 351    sequence = seq;
 352 }
 353
 354 void Graph::classifyDFS(Node *curr, int& seq)
 355 {
 356    Graph::Edge *edge;
 357    Graph::Node *node;
 358
 359    curr->visit(++seq);
 360    curr->tag = 1;
 361
 362    for (edge = curr->out; edge; edge = edge->next[0]) {
 363       node = edge->target;
 364       if (edge->type == Edge::DUMMY)
 365          continue;
 366
 367       if (node->getSequence() == 0) {
 368          edge->type = Edge::TREE;
 369          classifyDFS(node, seq);
 370       } else
 371       if (node->getSequence() > curr->getSequence()) {
 372          edge->type = Edge::FORWARD;
 373       } else {
 374          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
 375       }
 376    }
 377
 378    for (edge = curr->in; edge; edge = edge->next[1]) {
 379       node = edge->origin;
 380       if (edge->type == Edge::DUMMY)
 381          continue;
 382
 383       if (node->getSequence() == 0) {
 384          edge->type = Edge::TREE;
 385          classifyDFS(node, seq);
 386       } else
 387       if (node->getSequence() > curr->getSequence()) {
 388          edge->type = Edge::FORWARD;
 389       } else {
 390          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
 391       }
 392    }
 393
 394    curr->tag = 0;
 395 }
 396
 397 // @dist is indexed by Node::tag, returns -1 if no path found
 398 int
 399 Graph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight)
 400 {
 401    std::vector<int> path(weight.size(), std::numeric_limits<int>::max());
 402    std::list<Node *> nodeList;
 403    const int seq = nextSequence();
 404
 405    path[a->tag] = 0;
 406    for (Node *c = a; c && c != b;) {
 407       const int p = path[c->tag] + weight[c->tag];
 408       for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) {
 409          Node *t = ei.getNode();
 410          if (t->getSequence() < seq) {
 411             if (path[t->tag] == std::numeric_limits<int>::max())
 412                nodeList.push_front(t);
 413             if (p < path[t->tag])
 414                path[t->tag] = p;
 415          }
 416       }
 417       c->visit(seq);
 418       Node *next = NULL;
 419       for (std::list<Node *>::iterator n = nodeList.begin();
 420            n != nodeList.end(); ++n) {
 421          if (!next || path[(*n)->tag] < path[next->tag])
 422             next = *n;
 423          if ((*n) == c) {
 424             // erase visited
 425             n = nodeList.erase(n);
 426             --n;
 427          }
 428       }
 429       c = next;
 430    }
 431    if (path[b->tag] == std::numeric_limits<int>::max())
 432       return -1;
 433    return path[b->tag];
 434 }
 435
 436 } // namespace nv50_ir