Home | History | Annotate | Download | only in codegen
      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 #include <limits>
     25 #include <list>
     26 #include <stack>
     27 #include "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
    437