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#include "codegen/nv50_ir_graph.h"
24#include <limits>
25#include <list>
26#include <stack>
27#include "codegen/nv50_ir.h"
28
29namespace nv50_ir {
30
31Graph::Graph()
32{
33   root = NULL;
34   size = 0;
35   sequence = 0;
36}
37
38Graph::~Graph()
39{
40   for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next())
41      reinterpret_cast<Node *>(it->get())->cut();
42}
43
44void Graph::insert(Node *node)
45{
46   if (!root)
47      root = node;
48
49   node->graph = this;
50   size++;
51}
52
53void Graph::Edge::unlink()
54{
55   if (origin) {
56      prev[0]->next[0] = next[0];
57      next[0]->prev[0] = prev[0];
58      if (origin->out == this)
59         origin->out = (next[0] == this) ? NULL : next[0];
60
61      --origin->outCount;
62   }
63   if (target) {
64      prev[1]->next[1] = next[1];
65      next[1]->prev[1] = prev[1];
66      if (target->in == this)
67         target->in = (next[1] == this) ? NULL : next[1];
68
69      --target->inCount;
70   }
71}
72
73const char *Graph::Edge::typeStr() const
74{
75   switch (type) {
76   case TREE:    return "tree";
77   case FORWARD: return "forward";
78   case BACK:    return "back";
79   case CROSS:   return "cross";
80   case UNKNOWN:
81   default:
82      return "unk";
83   }
84}
85
86Graph::Node::Node(void *priv) : data(priv),
87                                in(0), out(0), graph(0),
88                                visited(0),
89                                inCount(0), outCount(0),
90                                tag(0)
91{
92   // nothing to do
93}
94
95void Graph::Node::attach(Node *node, Edge::Type kind)
96{
97   Edge *edge = new Edge(this, node, kind);
98
99   // insert head
100   if (this->out) {
101      edge->next[0] = this->out;
102      edge->prev[0] = this->out->prev[0];
103      edge->prev[0]->next[0] = edge;
104      this->out->prev[0] = edge;
105   }
106   this->out = edge;
107
108   if (node->in) {
109      edge->next[1] = node->in;
110      edge->prev[1] = node->in->prev[1];
111      edge->prev[1]->next[1] = edge;
112      node->in->prev[1] = edge;
113   }
114   node->in = edge;
115
116   ++this->outCount;
117   ++node->inCount;
118
119   assert(graph || node->graph);
120   if (!node->graph)
121      graph->insert(node);
122   if (!graph)
123      node->graph->insert(this);
124
125   if (kind == Edge::UNKNOWN)
126      graph->classifyEdges();
127}
128
129bool Graph::Node::detach(Graph::Node *node)
130{
131   EdgeIterator ei = this->outgoing();
132   for (; !ei.end(); ei.next())
133      if (ei.getNode() == node)
134         break;
135   if (ei.end()) {
136      ERROR("no such node attached\n");
137      return false;
138   }
139   delete ei.getEdge();
140   return true;
141}
142
143// Cut a node from the graph, deleting all attached edges.
144void Graph::Node::cut()
145{
146   while (out)
147      delete out;
148   while (in)
149      delete in;
150
151   if (graph) {
152      if (graph->root == this)
153         graph->root = NULL;
154      graph = NULL;
155   }
156}
157
158Graph::Edge::Edge(Node *org, Node *tgt, Type kind)
159{
160   target = tgt;
161   origin = org;
162   type = kind;
163
164   next[0] = next[1] = this;
165   prev[0] = prev[1] = this;
166}
167
168bool
169Graph::Node::reachableBy(const Node *node, const Node *term) const
170{
171   std::stack<const Node *> stack;
172   const Node *pos = NULL;
173   const int seq = graph->nextSequence();
174
175   stack.push(node);
176
177   while (!stack.empty()) {
178      pos = stack.top();
179      stack.pop();
180
181      if (pos == this)
182         return true;
183      if (pos == term)
184         continue;
185
186      for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) {
187         if (ei.getType() == Edge::BACK)
188            continue;
189         if (ei.getNode()->visit(seq))
190            stack.push(ei.getNode());
191      }
192   }
193   return pos == this;
194}
195
196class DFSIterator : public Iterator
197{
198public:
199   DFSIterator(Graph *graph, const bool preorder)
200   {
201      unsigned int seq = graph->nextSequence();
202
203      nodes = new Graph::Node * [graph->getSize() + 1];
204      count = 0;
205      pos = 0;
206      nodes[graph->getSize()] = 0;
207
208      if (graph->getRoot()) {
209         graph->getRoot()->visit(seq);
210         search(graph->getRoot(), preorder, seq);
211      }
212   }
213
214   ~DFSIterator()
215   {
216      if (nodes)
217         delete[] nodes;
218   }
219
220   void search(Graph::Node *node, const bool preorder, const int sequence)
221   {
222      if (preorder)
223         nodes[count++] = node;
224
225      for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
226         if (ei.getNode()->visit(sequence))
227            search(ei.getNode(), preorder, sequence);
228
229      if (!preorder)
230         nodes[count++] = node;
231   }
232
233   virtual bool end() const { return pos >= count; }
234   virtual void next() { if (pos < count) ++pos; }
235   virtual void *get() const { return nodes[pos]; }
236   virtual void reset() { pos = 0; }
237
238protected:
239   Graph::Node **nodes;
240   int count;
241   int pos;
242};
243
244IteratorRef Graph::iteratorDFS(bool preorder)
245{
246   return IteratorRef(new DFSIterator(this, preorder));
247}
248
249IteratorRef Graph::safeIteratorDFS(bool preorder)
250{
251   return this->iteratorDFS(preorder);
252}
253
254class CFGIterator : public Iterator
255{
256public:
257   CFGIterator(Graph *graph)
258   {
259      nodes = new Graph::Node * [graph->getSize() + 1];
260      count = 0;
261      pos = 0;
262      nodes[graph->getSize()] = 0;
263
264      // TODO: argh, use graph->sequence instead of tag and just raise it by > 1
265      for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next())
266         reinterpret_cast<Graph::Node *>(it->get())->tag = 0;
267
268      if (graph->getRoot())
269         search(graph->getRoot(), graph->nextSequence());
270   }
271
272   ~CFGIterator()
273   {
274      if (nodes)
275         delete[] nodes;
276   }
277
278   virtual void *get() const { return nodes[pos]; }
279   virtual bool end() const { return pos >= count; }
280   virtual void next() { if (pos < count) ++pos; }
281   virtual void reset() { pos = 0; }
282
283private:
284   void search(Graph::Node *node, const int sequence)
285   {
286      Stack bb, cross;
287
288      bb.push(node);
289
290      while (bb.getSize() || cross.getSize()) {
291         if (bb.getSize() == 0)
292            cross.moveTo(bb);
293
294         node = reinterpret_cast<Graph::Node *>(bb.pop().u.p);
295         assert(node);
296         if (!node->visit(sequence))
297            continue;
298         node->tag = 0;
299
300         for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {
301            switch (ei.getType()) {
302            case Graph::Edge::TREE:
303            case Graph::Edge::FORWARD:
304               if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd())
305                  bb.push(ei.getNode());
306               break;
307            case Graph::Edge::BACK:
308               continue;
309            case Graph::Edge::CROSS:
310               if (++(ei.getNode()->tag) == 1)
311                  cross.push(ei.getNode());
312               break;
313            default:
314               assert(!"unknown edge kind in CFG");
315               break;
316            }
317         }
318         nodes[count++] = node;
319      }
320   }
321
322private:
323   Graph::Node **nodes;
324   int count;
325   int pos;
326};
327
328IteratorRef Graph::iteratorCFG()
329{
330   return IteratorRef(new CFGIterator(this));
331}
332
333IteratorRef Graph::safeIteratorCFG()
334{
335   return this->iteratorCFG();
336}
337
338/**
339 * Edge classification:
340 *
341 * We have a graph and want to classify the edges into one of four types:
342 * - TREE:    edges that belong to a spanning tree of the graph
343 * - FORWARD: edges from a node to a descendent in the spanning tree
344 * - BACK:    edges from a node to a parent (or itself) in the spanning tree
345 * - CROSS:   all other edges (because they cross between branches in the
346 *            spanning tree)
347 */
348void Graph::classifyEdges()
349{
350   int seq;
351
352   for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) {
353      Node *node = reinterpret_cast<Node *>(it->get());
354      node->visit(0);
355      node->tag = 0;
356   }
357
358   classifyDFS(root, (seq = 0));
359
360   sequence = seq;
361}
362
363void Graph::classifyDFS(Node *curr, int& seq)
364{
365   Graph::Edge *edge;
366   Graph::Node *node;
367
368   curr->visit(++seq);
369   curr->tag = 1;
370
371   for (edge = curr->out; edge; edge = edge->next[0]) {
372      node = edge->target;
373
374      if (node->getSequence() == 0) {
375         edge->type = Edge::TREE;
376         classifyDFS(node, seq);
377      } else
378      if (node->getSequence() > curr->getSequence()) {
379         edge->type = Edge::FORWARD;
380      } else {
381         edge->type = node->tag ? Edge::BACK : Edge::CROSS;
382      }
383   }
384
385   for (edge = curr->in; edge; edge = edge->next[1]) {
386      node = edge->origin;
387
388      if (node->getSequence() == 0) {
389         edge->type = Edge::TREE;
390         classifyDFS(node, seq);
391      } else
392      if (node->getSequence() > curr->getSequence()) {
393         edge->type = Edge::FORWARD;
394      } else {
395         edge->type = node->tag ? Edge::BACK : Edge::CROSS;
396      }
397   }
398
399   curr->tag = 0;
400}
401
402// @dist is indexed by Node::tag, returns -1 if no path found
403int
404Graph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight)
405{
406   std::vector<int> path(weight.size(), std::numeric_limits<int>::max());
407   std::list<Node *> nodeList;
408   const int seq = nextSequence();
409
410   path[a->tag] = 0;
411   for (Node *c = a; c && c != b;) {
412      const int p = path[c->tag] + weight[c->tag];
413      for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) {
414         Node *t = ei.getNode();
415         if (t->getSequence() < seq) {
416            if (path[t->tag] == std::numeric_limits<int>::max())
417               nodeList.push_front(t);
418            if (p < path[t->tag])
419               path[t->tag] = p;
420         }
421      }
422      c->visit(seq);
423      Node *next = NULL;
424      for (std::list<Node *>::iterator n = nodeList.begin();
425           n != nodeList.end(); ++n) {
426         if (!next || path[(*n)->tag] < path[next->tag])
427            next = *n;
428         if ((*n) == c) {
429            // erase visited
430            n = nodeList.erase(n);
431            --n;
432         }
433      }
434      c = next;
435   }
436   if (path[b->tag] == std::numeric_limits<int>::max())
437      return -1;
438   return path[b->tag];
439}
440
441} // namespace nv50_ir
442