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 OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
     18  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
     19  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
     20  * OTHER DEALINGS IN THE SOFTWARE.
     21  */
     22 
     23 #include "codegen/nv50_ir_graph.h"
     24 #include <limits>
     25 #include <list>
     26 #include <stack>
     27 #include "codegen/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() || cross.getSize()) {
    291          if (bb.getSize() == 0)
    292             cross.moveTo(bb);
    293 
    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    }
    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 /**
    340  * Edge classification:
    341  *
    342  * We have a graph and want to classify the edges into one of four types:
    343  * - TREE:    edges that belong to a spanning tree of the graph
    344  * - FORWARD: edges from a node to a descendent in the spanning tree
    345  * - BACK:    edges from a node to a parent (or itself) in the spanning tree
    346  * - CROSS:   all other edges (because they cross between branches in the
    347  *            spanning tree)
    348  */
    349 void Graph::classifyEdges()
    350 {
    351    int seq;
    352 
    353    for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) {
    354       Node *node = reinterpret_cast<Node *>(it->get());
    355       node->visit(0);
    356       node->tag = 0;
    357    }
    358 
    359    classifyDFS(root, (seq = 0));
    360 
    361    sequence = seq;
    362 }
    363 
    364 void Graph::classifyDFS(Node *curr, int& seq)
    365 {
    366    Graph::Edge *edge;
    367    Graph::Node *node;
    368 
    369    curr->visit(++seq);
    370    curr->tag = 1;
    371 
    372    for (edge = curr->out; edge; edge = edge->next[0]) {
    373       node = edge->target;
    374       if (edge->type == Edge::DUMMY)
    375          continue;
    376 
    377       if (node->getSequence() == 0) {
    378          edge->type = Edge::TREE;
    379          classifyDFS(node, seq);
    380       } else
    381       if (node->getSequence() > curr->getSequence()) {
    382          edge->type = Edge::FORWARD;
    383       } else {
    384          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
    385       }
    386    }
    387 
    388    for (edge = curr->in; edge; edge = edge->next[1]) {
    389       node = edge->origin;
    390       if (edge->type == Edge::DUMMY)
    391          continue;
    392 
    393       if (node->getSequence() == 0) {
    394          edge->type = Edge::TREE;
    395          classifyDFS(node, seq);
    396       } else
    397       if (node->getSequence() > curr->getSequence()) {
    398          edge->type = Edge::FORWARD;
    399       } else {
    400          edge->type = node->tag ? Edge::BACK : Edge::CROSS;
    401       }
    402    }
    403 
    404    curr->tag = 0;
    405 }
    406 
    407 // @dist is indexed by Node::tag, returns -1 if no path found
    408 int
    409 Graph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight)
    410 {
    411    std::vector<int> path(weight.size(), std::numeric_limits<int>::max());
    412    std::list<Node *> nodeList;
    413    const int seq = nextSequence();
    414 
    415    path[a->tag] = 0;
    416    for (Node *c = a; c && c != b;) {
    417       const int p = path[c->tag] + weight[c->tag];
    418       for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) {
    419          Node *t = ei.getNode();
    420          if (t->getSequence() < seq) {
    421             if (path[t->tag] == std::numeric_limits<int>::max())
    422                nodeList.push_front(t);
    423             if (p < path[t->tag])
    424                path[t->tag] = p;
    425          }
    426       }
    427       c->visit(seq);
    428       Node *next = NULL;
    429       for (std::list<Node *>::iterator n = nodeList.begin();
    430            n != nodeList.end(); ++n) {
    431          if (!next || path[(*n)->tag] < path[next->tag])
    432             next = *n;
    433          if ((*n) == c) {
    434             // erase visited
    435             n = nodeList.erase(n);
    436             --n;
    437          }
    438       }
    439       c = next;
    440    }
    441    if (path[b->tag] == std::numeric_limits<int>::max())
    442       return -1;
    443    return path[b->tag];
    444 }
    445 
    446 } // namespace nv50_ir
    447