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

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