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