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 #ifndef __NV50_IR_GRAPH_H__
     24 #define __NV50_IR_GRAPH_H__
     25 
     26 #include "nv50_ir_util.h"
     27 #include <vector>
     28 
     29 namespace nv50_ir {
     30 
     31 #define ITER_NODE(x) reinterpret_cast<Graph::Node *>((x).get())
     32 #define ITER_EDGE(x) reinterpret_cast<Graph::Edge *>((x).get())
     33 
     34 // A connected graph.
     35 class Graph
     36 {
     37 public:
     38    class Node;
     39 
     40    class Edge
     41    {
     42    public:
     43       enum Type
     44       {
     45          UNKNOWN,
     46          TREE,
     47          FORWARD,
     48          BACK,
     49          CROSS, // e.g. loop break
     50          DUMMY
     51       };
     52 
     53       Edge(Node *dst, Node *src, Type kind);
     54       ~Edge() { unlink(); }
     55 
     56       inline Node *getOrigin() const { return origin; }
     57       inline Node *getTarget() const { return target; }
     58 
     59       inline Type getType() const { return type; }
     60       const char *typeStr() const;
     61 
     62    private:
     63       Node *origin;
     64       Node *target;
     65 
     66       Type type;
     67       Edge *next[2]; // next edge outgoing/incident from/to origin/target
     68       Edge *prev[2];
     69 
     70       void unlink();
     71 
     72       friend class Graph;
     73    };
     74 
     75    class EdgeIterator : public Iterator
     76    {
     77    public:
     78       EdgeIterator() : e(0), t(0), d(0), rev(false) { }
     79       EdgeIterator(Graph::Edge *first, int dir, bool reverse)
     80          : d(dir), rev(reverse)
     81       {
     82          t = e = ((rev && first) ? first->prev[d] : first);
     83       }
     84 
     85       virtual void next()
     86       {
     87          Graph::Edge *n = (rev ? e->prev[d] : e->next[d]);
     88          e = (n == t ? NULL : n);
     89       }
     90       virtual bool end() const { return !e; }
     91       virtual void *get() const { return e; }
     92 
     93       inline Node *getNode() const { assert(e); return d ?
     94                                                    e->origin : e->target; }
     95       inline Edge *getEdge() const { return e; }
     96       inline Edge::Type getType() { return e ? e->getType() : Edge::UNKNOWN; }
     97 
     98    private:
     99       Graph::Edge *e;
    100       Graph::Edge *t;
    101       int d;
    102       bool rev;
    103    };
    104 
    105    class Node
    106    {
    107    public:
    108       Node(void *);
    109       ~Node() { cut(); }
    110 
    111       void attach(Node *, Edge::Type);
    112       bool detach(Node *);
    113       void cut();
    114 
    115       inline EdgeIterator outgoing(bool reverse = false) const;
    116       inline EdgeIterator incident(bool reverse = false) const;
    117 
    118       inline Node *parent() const; // returns NULL if count(incident edges) != 1
    119 
    120       bool reachableBy(const Node *node, const Node *term) const;
    121 
    122       inline bool visit(int);
    123       inline int  getSequence() const;
    124 
    125       inline int incidentCountFwd() const; // count of incident non-back edges
    126       inline int incidentCount() const { return inCount; }
    127       inline int outgoingCount() const { return outCount; }
    128 
    129       Graph *getGraph() const { return graph; }
    130 
    131       void *data;
    132 
    133    private:
    134       Edge *in;
    135       Edge *out;
    136       Graph *graph;
    137 
    138       int visited;
    139 
    140       int16_t inCount;
    141       int16_t outCount;
    142    public:
    143       int tag; // for temporary use
    144 
    145       friend class Graph;
    146    };
    147 
    148 public:
    149    Graph();
    150    ~Graph(); // does *not* free the nodes (make it an option ?)
    151 
    152    inline Node *getRoot() const { return root; }
    153 
    154    inline unsigned int getSize() const { return size; }
    155 
    156    inline int nextSequence();
    157 
    158    void insert(Node *node); // attach to or set as root
    159 
    160    IteratorRef iteratorDFS(bool preorder = true);
    161    IteratorRef iteratorCFG();
    162 
    163    // safe iterators are unaffected by changes to the *edges* of the graph
    164    IteratorRef safeIteratorDFS(bool preorder = true);
    165    IteratorRef safeIteratorCFG();
    166 
    167    void classifyEdges();
    168 
    169    // @weights: indexed by Node::tag
    170    int findLightestPathWeight(Node *, Node *, const std::vector<int>& weights);
    171 
    172 private:
    173    void classifyDFS(Node *, int&);
    174 
    175 private:
    176    Node *root;
    177    unsigned int size;
    178    int sequence;
    179 };
    180 
    181 int Graph::nextSequence()
    182 {
    183    return ++sequence;
    184 }
    185 
    186 Graph::Node *Graph::Node::parent() const
    187 {
    188    if (inCount != 1)
    189       return NULL;
    190    assert(in);
    191    return in->origin;
    192 }
    193 
    194 bool Graph::Node::visit(int v)
    195 {
    196    if (visited == v)
    197       return false;
    198    visited = v;
    199    return true;
    200 }
    201 
    202 int Graph::Node::getSequence() const
    203 {
    204    return visited;
    205 }
    206 
    207 Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const
    208 {
    209    return EdgeIterator(out, 0, reverse);
    210 }
    211 
    212 Graph::EdgeIterator Graph::Node::incident(bool reverse) const
    213 {
    214    return EdgeIterator(in, 1, reverse);
    215 }
    216 
    217 int Graph::Node::incidentCountFwd() const
    218 {
    219    int n = 0;
    220    for (EdgeIterator ei = incident(); !ei.end(); ei.next())
    221       if (ei.getType() != Edge::BACK)
    222          ++n;
    223    return n;
    224 }
    225 
    226 } // namespace nv50_ir
    227 
    228 #endif // __NV50_IR_GRAPH_H__
    229