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
29namespace 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.
35class Graph
36{
37public:
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      };
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(const Node *node, const Node *term) const;
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
147public:
148   Graph();
149   virtual ~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   // @weights: indexed by Node::tag
169   int findLightestPathWeight(Node *, Node *, const std::vector<int>& weights);
170
171private:
172   void classifyDFS(Node *, int&);
173
174private:
175   Node *root;
176   unsigned int size;
177   int sequence;
178};
179
180int Graph::nextSequence()
181{
182   return ++sequence;
183}
184
185Graph::Node *Graph::Node::parent() const
186{
187   if (inCount != 1)
188      return NULL;
189   assert(in);
190   return in->origin;
191}
192
193bool Graph::Node::visit(int v)
194{
195   if (visited == v)
196      return false;
197   visited = v;
198   return true;
199}
200
201int Graph::Node::getSequence() const
202{
203   return visited;
204}
205
206Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const
207{
208   return EdgeIterator(out, 0, reverse);
209}
210
211Graph::EdgeIterator Graph::Node::incident(bool reverse) const
212{
213   return EdgeIterator(in, 1, reverse);
214}
215
216int Graph::Node::incidentCountFwd() const
217{
218   int n = 0;
219   for (EdgeIterator ei = incident(); !ei.end(); ei.next())
220      if (ei.getType() != Edge::BACK)
221         ++n;
222   return n;
223}
224
225} // namespace nv50_ir
226
227#endif // __NV50_IR_GRAPH_H__
228