src/gallium/drivers/nv50/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 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
  20  * SOFTWARE.
  21  */
  22
  23 #include "nv50_ir_graph.h"
  24
  25 namespace nv50_ir {
  26
  27 Graph::Graph()
  28 {
  29    root = NULL;
  30    size = 0;
  31    sequence = 0;
  32 }
  33
  34 Graph::~Graph()
  35 {
  36    Iterator *iter = this->safeIteratorDFS();
  37
  38    for (; !iter->end(); iter->next())
  39       reinterpret_cast<Node *>(iter->get())->cut();
  40
  41    putIterator(iter);
  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(Node *node, Node *term)
 170 {
 171    Stack stack;
 172    Node *pos;
 173    const int seq = graph->nextSequence();
 174
 175    stack.push(node);
 176
 177    while (stack.getSize()) {
 178       pos = reinterpret_cast<Node *>(stack.pop().u.p);
 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 || ei.getType() == Edge::DUMMY)
 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 Graph::GraphIterator
 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
 236    void reset() { pos = 0; }
 237
 238 protected:
 239    Graph::Node **nodes;
 240    int count;
 241    int pos;
 242 };
 243
 244 Graph::GraphIterator *Graph::iteratorDFS(bool preorder)
 245 {
 246    return new DFSIterator(this, preorder);
 247 }
 248
 249 Graph::GraphIterator *Graph::safeIteratorDFS(bool preorder)
 250 {
 251    return this->iteratorDFS(preorder);
 252 }
 253
 254 class CFGIterator : public Graph::GraphIterator
 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       Iterator *iter;
 266       for (iter = graph->iteratorDFS(); !iter->end(); iter->next())
 267          reinterpret_cast<Graph::Node *>(iter->get())->tag = 0;
 268       graph->putIterator(iter);
 269
 270       if (graph->getRoot())
 271          search(graph->getRoot(), graph->nextSequence());
 272    }
 273
 274    ~CFGIterator()
 275    {
 276       if (nodes)
 277          delete[] nodes;
 278    }
 279
 280    virtual void *get() const { return nodes[pos]; }
 281    virtual bool end() const { return pos >= count; }
 282    virtual void next() { if (pos < count) ++pos; }
 283
 284 private:
 285    void search(Graph::Node *node, const int sequence)
 286    {
 287       Stack bb, cross;
 288
 289       bb.push(node);
 290
 291       while (bb.getSize()) {
 292          node = reinterpret_cast<Graph::Node *>(bb.pop().u.p);
 293          assert(node);
 294          if (!node->visit(sequence))
 295             continue;
 296          node->tag = 0;
 297
 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());
 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          if (bb.getSize() == 0)
 320             cross.moveTo(bb);
 321       }
 322    }
 323
 324 private:
 325    Graph::Node **nodes;
 326    int count;
 327    int pos;
 328 };
 329
 330 Graph::GraphIterator *Graph::iteratorCFG()
 331 {
 332    return new CFGIterator(this);
 333 }
 334
 335 Graph::GraphIterator *Graph::safeIteratorCFG()
 336 {
 337    return this->iteratorCFG();
 338 }
 339
 340 void Graph::classifyEdges()
 341 {
 342    DFSIterator *iter;
 343    int seq;
 344
 345    for (iter = new DFSIterator(this, true); !iter->end(); iter->next()) {
 346       Node *node = reinterpret_cast<Node *>(iter->get());
 347       node->visit(0);
 348       node->tag = 0;
 349    }
 350    putIterator(iter);
 351
 352    classifyDFS(root, (seq = 0));
 353
 354    sequence = seq;
 355 }
 356
 357 void Graph::classifyDFS(Node *curr, int& seq)
 358 {
 359    Graph::Edge *edge;
 360    Graph::Node *node;
 361
 362    curr->visit(++seq);
 363    curr->tag = 1;
 364
 365    for (edge = curr->out; edge; edge = edge->next[0]) {
 366       node = edge->target;
 367       if (edge->type == Edge::DUMMY)
 368          continue;
 369
 370       if (node->getSequence() == 0) {
 371          edge->type = Edge::TREE;
 372          classifyDFS(node, seq);
 373       } else
 374       if (node->getSequence() > curr->getSequence()) {
 375          edge->type = Edge::FORWARD;
 376       } else {
 377          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
 378       }
 379    }
 380
 381    for (edge = curr->in; edge; edge = edge->next[1]) {
 382       node = edge->origin;
 383       if (edge->type == Edge::DUMMY)
 384          continue;
 385
 386       if (node->getSequence() == 0) {
 387          edge->type = Edge::TREE;
 388          classifyDFS(node, seq);
 389       } else
 390       if (node->getSequence() > curr->getSequence()) {
 391          edge->type = Edge::FORWARD;
 392       } else {
 393          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
 394       }
 395    }
 396
 397    curr->tag = 0;
 398 }
 399
 400 } // namespace nv50_ir