Subversion Repositories Kolibri OS

/*

 * Copyright 2011 Christoph Bumiller

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and associated documentation files (the "Software"),

 * to deal in the Software without restriction, including without limitation

 * the rights to use, copy, modify, merge, publish, distribute, sublicense,

 * and/or sell copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR

 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,

 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

#include "nv50_ir_graph.h"

#include 

#include 

#include 

#include "nv50_ir.h"

namespace nv50_ir {

Graph::Graph()

{

   root = NULL;

   size = 0;

   sequence = 0;

}

Graph::~Graph()

{

   for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next())

      reinterpret_cast(it->get())->cut();

}

void Graph::insert(Node *node)

{

   if (!root)

      root = node;

   node->graph = this;

   size++;

}

void Graph::Edge::unlink()

{

   if (origin) {

      prev[0]->next[0] = next[0];

      next[0]->prev[0] = prev[0];

      if (origin->out == this)

         origin->out = (next[0] == this) ? NULL : next[0];

      --origin->outCount;

   }

   if (target) {

      prev[1]->next[1] = next[1];

      next[1]->prev[1] = prev[1];

      if (target->in == this)

         target->in = (next[1] == this) ? NULL : next[1];

      --target->inCount;

   }

}

const char *Graph::Edge::typeStr() const

{

   switch (type) {

   case TREE:    return "tree";

   case FORWARD: return "forward";

   case BACK:    return "back";

   case CROSS:   return "cross";

   case DUMMY:   return "dummy";

   case UNKNOWN:

   default:

      return "unk";

   }

}

Graph::Node::Node(void *priv) : data(priv),

                                in(0), out(0), graph(0),

                                visited(0),

                                inCount(0), outCount(0)

{

   // nothing to do

}

void Graph::Node::attach(Node *node, Edge::Type kind)

{

   Edge *edge = new Edge(this, node, kind);

   // insert head

   if (this->out) {

      edge->next[0] = this->out;

      edge->prev[0] = this->out->prev[0];

      edge->prev[0]->next[0] = edge;

      this->out->prev[0] = edge;

   }

   this->out = edge;

   if (node->in) {

      edge->next[1] = node->in;

      edge->prev[1] = node->in->prev[1];

      edge->prev[1]->next[1] = edge;

      node->in->prev[1] = edge;

   }

   node->in = edge;

   ++this->outCount;

   ++node->inCount;

   assert(graph || node->graph);

   if (!node->graph)

      graph->insert(node);

   if (!graph)

      node->graph->insert(this);

   if (kind == Edge::UNKNOWN)

      graph->classifyEdges();

}

bool Graph::Node::detach(Graph::Node *node)

{

   EdgeIterator ei = this->outgoing();

   for (; !ei.end(); ei.next())

      if (ei.getNode() == node)

         break;

   if (ei.end()) {

      ERROR("no such node attached\n");

      return false;

   }

   delete ei.getEdge();

   return true;

}

// Cut a node from the graph, deleting all attached edges.

void Graph::Node::cut()

{

   while (out)

      delete out;

   while (in)

      delete in;

   if (graph) {

      if (graph->root == this)

         graph->root = NULL;

      graph = NULL;

   }

}

Graph::Edge::Edge(Node *org, Node *tgt, Type kind)

{

   target = tgt;

   origin = org;

   type = kind;

   next[0] = next[1] = this;

   prev[0] = prev[1] = this;

}

bool

Graph::Node::reachableBy(const Node *node, const Node *term) const

{

   std::stack stack;

   const Node *pos = NULL;

   const int seq = graph->nextSequence();

   stack.push(node);

   while (!stack.empty()) {

      pos = stack.top();

      stack.pop();

      if (pos == this)

         return true;

      if (pos == term)

         continue;

      for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) {

         if (ei.getType() == Edge::BACK || ei.getType() == Edge::DUMMY)

            continue;

         if (ei.getNode()->visit(seq))

            stack.push(ei.getNode());

      }

   }

   return pos == this;

}

class DFSIterator : public Iterator

{

public:

   DFSIterator(Graph *graph, const bool preorder)

   {

      unsigned int seq = graph->nextSequence();

      nodes = new Graph::Node * [graph->getSize() + 1];

      count = 0;

      pos = 0;

      nodes[graph->getSize()] = 0;

      if (graph->getRoot()) {

         graph->getRoot()->visit(seq);

         search(graph->getRoot(), preorder, seq);

      }

   }

   ~DFSIterator()

   {

      if (nodes)

         delete[] nodes;

   }

   void search(Graph::Node *node, const bool preorder, const int sequence)

   {

      if (preorder)

         nodes[count++] = node;

      for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())

         if (ei.getNode()->visit(sequence))

            search(ei.getNode(), preorder, sequence);

      if (!preorder)

         nodes[count++] = node;

   }

   virtual bool end() const { return pos >= count; }

   virtual void next() { if (pos < count) ++pos; }

   virtual void *get() const { return nodes[pos]; }

   virtual void reset() { pos = 0; }

protected:

   Graph::Node **nodes;

   int count;

   int pos;

};

IteratorRef Graph::iteratorDFS(bool preorder)

{

   return IteratorRef(new DFSIterator(this, preorder));

}

IteratorRef Graph::safeIteratorDFS(bool preorder)

{

   return this->iteratorDFS(preorder);

}

class CFGIterator : public Iterator

{

public:

   CFGIterator(Graph *graph)

   {

      nodes = new Graph::Node * [graph->getSize() + 1];

      count = 0;

      pos = 0;

      nodes[graph->getSize()] = 0;

      // TODO: argh, use graph->sequence instead of tag and just raise it by > 1

      for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next())

         reinterpret_cast(it->get())->tag = 0;

      if (graph->getRoot())

         search(graph->getRoot(), graph->nextSequence());

   }

   ~CFGIterator()

   {

      if (nodes)

         delete[] nodes;

   }

   virtual void *get() const { return nodes[pos]; }

   virtual bool end() const { return pos >= count; }

   virtual void next() { if (pos < count) ++pos; }

   virtual void reset() { pos = 0; }

private:

   void search(Graph::Node *node, const int sequence)

   {

      Stack bb, cross;

      bb.push(node);

      while (bb.getSize()) {

         node = reinterpret_cast(bb.pop().u.p);

         assert(node);

         if (!node->visit(sequence))

            continue;

         node->tag = 0;

         for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {

            switch (ei.getType()) {

            case Graph::Edge::TREE:

            case Graph::Edge::FORWARD:

            case Graph::Edge::DUMMY:

               if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd())

                  bb.push(ei.getNode());

               break;

            case Graph::Edge::BACK:

               continue;

            case Graph::Edge::CROSS:

               if (++(ei.getNode()->tag) == 1)

                  cross.push(ei.getNode());

               break;

            default:

               assert(!"unknown edge kind in CFG");

               break;

            }

         }

         nodes[count++] = node;

         if (bb.getSize() == 0)

            cross.moveTo(bb);

      }

   }

private:

   Graph::Node **nodes;

   int count;

   int pos;

};

IteratorRef Graph::iteratorCFG()

{

   return IteratorRef(new CFGIterator(this));

}

IteratorRef Graph::safeIteratorCFG()

{

   return this->iteratorCFG();

}

void Graph::classifyEdges()

{

   int seq;

   for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) {

      Node *node = reinterpret_cast(it->get());

      node->visit(0);

      node->tag = 0;

   }

   classifyDFS(root, (seq = 0));

   sequence = seq;

}

void Graph::classifyDFS(Node *curr, int& seq)

{

   Graph::Edge *edge;

   Graph::Node *node;

   curr->visit(++seq);

   curr->tag = 1;

   for (edge = curr->out; edge; edge = edge->next[0]) {

      node = edge->target;

      if (edge->type == Edge::DUMMY)

         continue;

      if (node->getSequence() == 0) {

         edge->type = Edge::TREE;

         classifyDFS(node, seq);

      } else

      if (node->getSequence() > curr->getSequence()) {

         edge->type = Edge::FORWARD;

      } else {

         edge->type = node->tag ? Edge::BACK : Edge::CROSS;

      }

   }

   for (edge = curr->in; edge; edge = edge->next[1]) {

      node = edge->origin;

      if (edge->type == Edge::DUMMY)

         continue;

      if (node->getSequence() == 0) {

         edge->type = Edge::TREE;

         classifyDFS(node, seq);

      } else

      if (node->getSequence() > curr->getSequence()) {

         edge->type = Edge::FORWARD;

      } else {

         edge->type = node->tag ? Edge::BACK : Edge::CROSS;

      }

   }

   curr->tag = 0;

}

// @dist is indexed by Node::tag, returns -1 if no path found

int

Graph::findLightestPathWeight(Node *a, Node *b, const std::vector &weight)

{

   std::vector path(weight.size(), std::numeric_limits::max());

   std::list nodeList;

   const int seq = nextSequence();

   path[a->tag] = 0;

   for (Node *c = a; c && c != b;) {

      const int p = path[c->tag] + weight[c->tag];

      for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) {

         Node *t = ei.getNode();

         if (t->getSequence() < seq) {

            if (path[t->tag] == std::numeric_limits::max())

               nodeList.push_front(t);

            if (p < path[t->tag])

               path[t->tag] = p;

         }

      }

      c->visit(seq);

      Node *next = NULL;

      for (std::list::iterator n = nodeList.begin();

           n != nodeList.end(); ++n) {

         if (!next || path[(*n)->tag] < path[next->tag])

            next = *n;

         if ((*n) == c) {

            // erase visited

            n = nodeList.erase(n);

            --n;

         }

      }

      c = next;

   }

   if (path[b->tag] == std::numeric_limits::max())

      return -1;

   return path[b->tag];

}

} // namespace nv50_ir