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

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