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

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