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