src/gallium/drivers/nouveau/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 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 #ifndef __NV50_IR_GRAPH_H__
  24 #define __NV50_IR_GRAPH_H__
  25
  26 #include "codegen/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    virtual ~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__