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       size = 1;
  49       node->graph = this;
  50    } else {
  51       root->attach(node, Edge::TREE);
  52    }
  53 }
  54
  55 void Graph::Edge::unlink()
  56 {
  57    if (origin) {
  58       prev[0]->next[0] = next[0];
  59       next[0]->prev[0] = prev[0];
  60       if (origin->out == this)
  61          origin->out = (next[0] == this) ? NULL : next[0];
  62
  63       --origin->outCount;
  64    }
  65    if (target) {
  66       prev[1]->next[1] = next[1];
  67       next[1]->prev[1] = prev[1];
  68       if (target->in == this)
  69          target->in = (next[1] == this) ? NULL : next[1];
  70
  71       --target->inCount;
  72    }
  73 }
  74
  75 const char *Graph::Edge::typeStr() const
  76 {
  77    switch (type) {
  78    case TREE:    return "tree";
  79    case FORWARD: return "forward";
  80    case BACK:    return "back";
  81    case CROSS:   return "cross";
  82    case DUMMY:   return "dummy";
  83    case UNKNOWN:
  84    default:
  85       return "unk";
  86    }
  87 }
  88
  89 Graph::Node::Node(void *priv) : data(priv),
  90                                 in(0), out(0), graph(0),
  91                                 visited(0),
  92                                 inCount(0), outCount(0)
  93 {
  94    // nothing to do
  95 }
  96
  97 void Graph::Node::attach(Node *node, Edge::Type kind)
  98 {
  99    Edge *edge = new Edge(this, node, kind);
 100
 101    // insert head
 102    if (this->out) {
 103       edge->next[0] = this->out;
 104       edge->prev[0] = this->out->prev[0];
 105       edge->prev[0]->next[0] = edge;
 106       this->out->prev[0] = edge;
 107    }
 108    this->out = edge;
 109
 110    if (node->in) {
 111       edge->next[1] = node->in;
 112       edge->prev[1] = node->in->prev[1];
 113       edge->prev[1]->next[1] = edge;
 114       node->in->prev[1] = edge;
 115    }
 116    node->in = edge;
 117
 118    ++this->outCount;
 119    ++node->inCount;
 120
 121    assert(this->graph);
 122    if (!node->graph) {
 123       node->graph = this->graph;
 124       ++node->graph->size;
 125    }
 126
 127    if (kind == Edge::UNKNOWN)
 128       graph->classifyEdges();
 129 }
 130
 131 bool Graph::Node::detach(Graph::Node *node)
 132 {
 133    EdgeIterator ei = this->outgoing();
 134    for (; !ei.end(); ei.next())
 135       if (ei.getNode() == node)
 136          break;
 137    if (ei.end()) {
 138       ERROR("no such node attached\n");
 139       return false;
 140    }
 141    delete ei.getEdge();
 142    return true;
 143 }
 144
 145 // Cut a node from the graph, deleting all attached edges.
 146 void Graph::Node::cut()
 147 {
 148    while (out)
 149       delete out;
 150    while (in)
 151       delete in;
 152
 153    if (graph) {
 154       if (graph->root == this)
 155          graph->root = NULL;
 156       graph = NULL;
 157    }
 158 }
 159
 160 Graph::Edge::Edge(Node *org, Node *tgt, Type kind)
 161 {
 162    target = tgt;
 163    origin = org;
 164    type = kind;
 165
 166    next[0] = next[1] = this;
 167    prev[0] = prev[1] = this;
 168 }
 169
 170 bool
 171 Graph::Node::reachableBy(Node *node, Node *term)
 172 {
 173    Stack stack;
 174    Node *pos;
 175    const int seq = graph->nextSequence();
 176
 177    stack.push(node);
 178
 179    while (stack.getSize()) {
 180       pos = reinterpret_cast<Node *>(stack.pop().u.p);
 181
 182       if (pos == this)
 183          return true;
 184       if (pos == term)
 185          continue;
 186
 187       for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) {
 188          if (ei.getType() == Edge::BACK || ei.getType() == Edge::DUMMY)
 189             continue;
 190          if (ei.getNode()->visit(seq))
 191             stack.push(ei.getNode());
 192       }
 193    }
 194    return pos == this;
 195 }
 196
 197 class DFSIterator : public Graph::GraphIterator
 198 {
 199 public:
 200    DFSIterator(Graph *graph, const bool preorder)
 201    {
 202       unsigned int seq = graph->nextSequence();
 203
 204       nodes = new Graph::Node * [graph->getSize() + 1];
 205       count = 0;
 206       pos = 0;
 207       nodes[graph->getSize()] = 0;
 208
 209       if (graph->getRoot()) {
 210          graph->getRoot()->visit(seq);
 211          search(graph->getRoot(), preorder, seq);
 212       }
 213    }
 214
 215    ~DFSIterator()
 216    {
 217       if (nodes)
 218          delete[] nodes;
 219    }
 220
 221    void search(Graph::Node *node, const bool preorder, const int sequence)
 222    {
 223       if (preorder)
 224          nodes[count++] = node;
 225
 226       for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
 227          if (ei.getNode()->visit(sequence))
 228             search(ei.getNode(), preorder, sequence);
 229
 230       if (!preorder)
 231          nodes[count++] = node;
 232    }
 233
 234    virtual bool end() const { return pos >= count; }
 235    virtual void next() { if (pos < count) ++pos; }
 236    virtual void *get() const { return nodes[pos]; }
 237
 238    void reset() { pos = 0; }
 239
 240 protected:
 241    Graph::Node **nodes;
 242    int count;
 243    int pos;
 244 };
 245
 246 Graph::GraphIterator *Graph::iteratorDFS(bool preorder)
 247 {
 248    return new DFSIterator(this, preorder);
 249 }
 250
 251 Graph::GraphIterator *Graph::safeIteratorDFS(bool preorder)
 252 {
 253    return this->iteratorDFS(preorder);
 254 }
 255
 256 class CFGIterator : public Graph::GraphIterator
 257 {
 258 public:
 259    CFGIterator(Graph *graph)
 260    {
 261       nodes = new Graph::Node * [graph->getSize() + 1];
 262       count = 0;
 263       pos = 0;
 264       nodes[graph->getSize()] = 0;
 265
 266       // TODO: argh, use graph->sequence instead of tag and just raise it by > 1
 267       Iterator *iter;
 268       for (iter = graph->iteratorDFS(); !iter->end(); iter->next())
 269          reinterpret_cast<Graph::Node *>(iter->get())->tag = 0;
 270       graph->putIterator(iter);
 271
 272       if (graph->getRoot())
 273          search(graph->getRoot(), graph->nextSequence());
 274    }
 275
 276    ~CFGIterator()
 277    {
 278       if (nodes)
 279          delete[] nodes;
 280    }
 281
 282    virtual void *get() const { return nodes[pos]; }
 283    virtual bool end() const { return pos >= count; }
 284    virtual void next() { if (pos < count) ++pos; }
 285
 286 private:
 287    void search(Graph::Node *node, const int sequence)
 288    {
 289       Stack bb, cross;
 290
 291       bb.push(node);
 292
 293       while (bb.getSize()) {
 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             case Graph::Edge::DUMMY:
 305                if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd())
 306                   bb.push(ei.getNode());
 307                break;
 308             case Graph::Edge::BACK:
 309                continue;
 310             case Graph::Edge::CROSS:
 311                if (++(ei.getNode()->tag) == 1)
 312                   cross.push(ei.getNode());
 313                break;
 314             default:
 315                assert(!"unknown edge kind in CFG");
 316                break;
 317             }
 318          }
 319          nodes[count++] = node;
 320
 321          if (bb.getSize() == 0)
 322             cross.moveTo(bb);
 323       }
 324    }
 325
 326 private:
 327    Graph::Node **nodes;
 328    int count;
 329    int pos;
 330 };
 331
 332 Graph::GraphIterator *Graph::iteratorCFG()
 333 {
 334    return new CFGIterator(this);
 335 }
 336
 337 Graph::GraphIterator *Graph::safeIteratorCFG()
 338 {
 339    return this->iteratorCFG();
 340 }
 341
 342 void Graph::classifyEdges()
 343 {
 344    DFSIterator *iter;
 345    int seq;
 346
 347    for (iter = new DFSIterator(this, true); !iter->end(); iter->next()) {
 348       Node *node = reinterpret_cast<Node *>(iter->get());
 349       node->visit(0);
 350       node->tag = 0;
 351    }
 352    putIterator(iter);
 353
 354    classifyDFS(root, (seq = 0));
 355
 356    sequence = seq;
 357 }
 358
 359 void Graph::classifyDFS(Node *curr, int& seq)
 360 {
 361    Graph::Edge *edge;
 362    Graph::Node *node;
 363
 364    curr->visit(++seq);
 365    curr->tag = 1;
 366
 367    for (edge = curr->out; edge; edge = edge->next[0]) {
 368       node = edge->target;
 369       if (edge->type == Edge::DUMMY)
 370          continue;
 371
 372       if (node->getSequence() == 0) {
 373          edge->type = Edge::TREE;
 374          classifyDFS(node, seq);
 375       } else
 376       if (node->getSequence() > curr->getSequence()) {
 377          edge->type = Edge::FORWARD;
 378       } else {
 379          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
 380       }
 381    }
 382
 383    for (edge = curr->in; edge; edge = edge->next[1]) {
 384       node = edge->origin;
 385       if (edge->type == Edge::DUMMY)
 386          continue;
 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 } // namespace nv50_ir