1d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller/* 2d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Copyright 2011 Christoph Bumiller 3d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 4d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Permission is hereby granted, free of charge, to any person obtaining a 5d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * copy of this software and associated documentation files (the "Software"), 6d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * to deal in the Software without restriction, including without limitation 7d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * and/or sell copies of the Software, and to permit persons to whom the 9d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Software is furnished to do so, subject to the following conditions: 10d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 11d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * The above copyright notice and this permission notice shall be included in 12d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * all copies or substantial portions of the Software. 13d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 14d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * SOFTWARE. 21d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller */ 2257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50_ir_graph.h" 2400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller#include <limits> 2500fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller#include <list> 2640c224a573f2b763046001e622aafca90f68c693Christoph Bumiller#include <stack> 2700fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller#include "nv50_ir.h" 2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir { 3057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerGraph::Graph() 3257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 3357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller root = NULL; 3457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = 0; 3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sequence = 0; 3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 3757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerGraph::~Graph() 3957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 4078de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next()) 4178de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez reinterpret_cast<Node *>(it->get())->cut(); 4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::insert(Node *node) 4557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 46099b81396eb4518cc4de0393ceff1028c5bee2bdFrancisco Jerez if (!root) 4757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller root = node; 48099b81396eb4518cc4de0393ceff1028c5bee2bdFrancisco Jerez 49099b81396eb4518cc4de0393ceff1028c5bee2bdFrancisco Jerez node->graph = this; 50099b81396eb4518cc4de0393ceff1028c5bee2bdFrancisco Jerez size++; 5157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 5257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::Edge::unlink() 5457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 5557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (origin) { 5657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prev[0]->next[0] = next[0]; 5757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next[0]->prev[0] = prev[0]; 5857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (origin->out == this) 5957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller origin->out = (next[0] == this) ? NULL : next[0]; 6057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller --origin->outCount; 6257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 6357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (target) { 6457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prev[1]->next[1] = next[1]; 6557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next[1]->prev[1] = prev[1]; 6657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (target->in == this) 6757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller target->in = (next[1] == this) ? NULL : next[1]; 6857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller --target->inCount; 7057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 7157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 7257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerconst char *Graph::Edge::typeStr() const 7457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 7557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (type) { 7657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case TREE: return "tree"; 7757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case FORWARD: return "forward"; 7857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case BACK: return "back"; 7957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case CROSS: return "cross"; 8057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case DUMMY: return "dummy"; 8157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case UNKNOWN: 8257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 8357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return "unk"; 8457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 8557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerGraph::Node::Node(void *priv) : data(priv), 8857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller in(0), out(0), graph(0), 8957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller visited(0), 9057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inCount(0), outCount(0) 9157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 9257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // nothing to do 9357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 9457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::Node::attach(Node *node, Edge::Type kind) 9657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 9757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Edge *edge = new Edge(this, node, kind); 9857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // insert head 10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (this->out) { 10157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->next[0] = this->out; 10257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->prev[0] = this->out->prev[0]; 10357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->prev[0]->next[0] = edge; 10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->out->prev[0] = edge; 10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->out = edge; 10757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (node->in) { 10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->next[1] = node->in; 11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->prev[1] = node->in->prev[1]; 11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->prev[1]->next[1] = edge; 11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node->in->prev[1] = edge; 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node->in = edge; 11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++this->outCount; 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++node->inCount; 11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1190056e1b9889ce9cdf3669e5ebc02638e5acc448eFrancisco Jerez assert(graph || node->graph); 1200056e1b9889ce9cdf3669e5ebc02638e5acc448eFrancisco Jerez if (!node->graph) 1210056e1b9889ce9cdf3669e5ebc02638e5acc448eFrancisco Jerez graph->insert(node); 1220056e1b9889ce9cdf3669e5ebc02638e5acc448eFrancisco Jerez if (!graph) 1230056e1b9889ce9cdf3669e5ebc02638e5acc448eFrancisco Jerez node->graph->insert(this); 12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (kind == Edge::UNKNOWN) 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller graph->classifyEdges(); 12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool Graph::Node::detach(Graph::Node *node) 13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller EdgeIterator ei = this->outgoing(); 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (; !ei.end(); ei.next()) 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getNode() == node) 13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.end()) { 13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ERROR("no such node attached\n"); 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete ei.getEdge(); 14057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Cut a node from the graph, deleting all attached edges. 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::Node::cut() 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (out) 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete out; 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (in) 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete in; 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 151e3a3844e8de7ff69606e16eab752152f70785de8Christoph Bumiller if (graph) { 152e3a3844e8de7ff69606e16eab752152f70785de8Christoph Bumiller if (graph->root == this) 153e3a3844e8de7ff69606e16eab752152f70785de8Christoph Bumiller graph->root = NULL; 154e3a3844e8de7ff69606e16eab752152f70785de8Christoph Bumiller graph = NULL; 155e3a3844e8de7ff69606e16eab752152f70785de8Christoph Bumiller } 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerGraph::Edge::Edge(Node *org, Node *tgt, Type kind) 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller target = tgt; 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller origin = org; 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller type = kind; 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next[0] = next[1] = this; 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prev[0] = prev[1] = this; 16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 16940c224a573f2b763046001e622aafca90f68c693Christoph BumillerGraph::Node::reachableBy(const Node *node, const Node *term) const 17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 17140c224a573f2b763046001e622aafca90f68c693Christoph Bumiller std::stack<const Node *> stack; 17240c224a573f2b763046001e622aafca90f68c693Christoph Bumiller const Node *pos = NULL; 17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const int seq = graph->nextSequence(); 17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller stack.push(node); 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17740c224a573f2b763046001e622aafca90f68c693Christoph Bumiller while (!stack.empty()) { 17840c224a573f2b763046001e622aafca90f68c693Christoph Bumiller pos = stack.top(); 17940c224a573f2b763046001e622aafca90f68c693Christoph Bumiller stack.pop(); 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (pos == this) 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (pos == term) 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) { 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getType() == Edge::BACK || ei.getType() == Edge::DUMMY) 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getNode()->visit(seq)) 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller stack.push(ei.getNode()); 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return pos == this; 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerezclass DFSIterator : public Iterator 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DFSIterator(Graph *graph, const bool preorder) 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int seq = graph->nextSequence(); 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes = new Graph::Node * [graph->getSize() + 1]; 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller count = 0; 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos = 0; 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes[graph->getSize()] = 0; 20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (graph->getRoot()) { 20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller graph->getRoot()->visit(seq); 21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller search(graph->getRoot(), preorder, seq); 21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~DFSIterator() 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (nodes) 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete[] nodes; 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void search(Graph::Node *node, const bool preorder, const int sequence) 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (preorder) 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes[count++] = node; 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getNode()->visit(sequence)) 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller search(ei.getNode(), preorder, sequence); 22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!preorder) 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes[count++] = node; 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool end() const { return pos >= count; } 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void next() { if (pos < count) ++pos; } 23557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void *get() const { return nodes[pos]; } 23600fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller virtual void reset() { pos = 0; } 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprotected: 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node **nodes; 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int count; 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int pos; 24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24478de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco JerezIteratorRef Graph::iteratorDFS(bool preorder) 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 24678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez return IteratorRef(new DFSIterator(this, preorder)); 24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24978de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco JerezIteratorRef Graph::safeIteratorDFS(bool preorder) 25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return this->iteratorDFS(preorder); 25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25478de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerezclass CFGIterator : public Iterator 25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller CFGIterator(Graph *graph) 25857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes = new Graph::Node * [graph->getSize() + 1]; 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller count = 0; 26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos = 0; 26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes[graph->getSize()] = 0; 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // TODO: argh, use graph->sequence instead of tag and just raise it by > 1 26578de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next()) 26678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez reinterpret_cast<Graph::Node *>(it->get())->tag = 0; 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (graph->getRoot()) 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller search(graph->getRoot(), graph->nextSequence()); 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~CFGIterator() 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (nodes) 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete[] nodes; 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void *get() const { return nodes[pos]; } 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool end() const { return pos >= count; } 28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void next() { if (pos < count) ++pos; } 28100fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller virtual void reset() { pos = 0; } 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void search(Graph::Node *node, const int sequence) 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Stack bb, cross; 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb.push(node); 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (bb.getSize()) { 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node = reinterpret_cast<Graph::Node *>(bb.pop().u.p); 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(node); 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!node->visit(sequence)) 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node->tag = 0; 29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (ei.getType()) { 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::TREE: 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::FORWARD: 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::DUMMY: 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd()) 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb.push(ei.getNode()); 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::BACK: 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::CROSS: 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (++(ei.getNode()->tag) == 1) 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cross.push(ei.getNode()); 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(!"unknown edge kind in CFG"); 31357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nodes[count++] = node; 31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb.getSize() == 0) 31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cross.moveTo(bb); 32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node **nodes; 32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int count; 32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int pos; 32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 32857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32978de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco JerezIteratorRef Graph::iteratorCFG() 33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 33178de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez return IteratorRef(new CFGIterator(this)); 33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33478de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco JerezIteratorRef Graph::safeIteratorCFG() 33557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return this->iteratorCFG(); 33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::classifyEdges() 34057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 34157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int seq; 34257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 34378de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) { 34478de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez Node *node = reinterpret_cast<Node *>(it->get()); 34557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node->visit(0); 34657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node->tag = 0; 34757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 34857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 34957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller classifyDFS(root, (seq = 0)); 35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sequence = seq; 35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Graph::classifyDFS(Node *curr, int& seq) 35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Edge *edge; 35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node *node; 35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller curr->visit(++seq); 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller curr->tag = 1; 36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (edge = curr->out; edge; edge = edge->next[0]) { 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node = edge->target; 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (edge->type == Edge::DUMMY) 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (node->getSequence() == 0) { 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = Edge::TREE; 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller classifyDFS(node, seq); 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (node->getSequence() > curr->getSequence()) { 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = Edge::FORWARD; 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = node->tag ? Edge::BACK : Edge::CROSS; 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (edge = curr->in; edge; edge = edge->next[1]) { 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller node = edge->origin; 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (edge->type == Edge::DUMMY) 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (node->getSequence() == 0) { 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = Edge::TREE; 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller classifyDFS(node, seq); 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (node->getSequence() > curr->getSequence()) { 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = Edge::FORWARD; 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller edge->type = node->tag ? Edge::BACK : Edge::CROSS; 39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 39257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller curr->tag = 0; 39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39700fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller// @dist is indexed by Node::tag, returns -1 if no path found 39800fe442253744c4c4e7e68da44d6983da053968bChristoph Bumillerint 39900fe442253744c4c4e7e68da44d6983da053968bChristoph BumillerGraph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight) 40000fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller{ 40100fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller std::vector<int> path(weight.size(), std::numeric_limits<int>::max()); 40200fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller std::list<Node *> nodeList; 40300fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller const int seq = nextSequence(); 40400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller 40500fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller path[a->tag] = 0; 40600fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller for (Node *c = a; c && c != b;) { 40700fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller const int p = path[c->tag] + weight[c->tag]; 40800fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) { 40900fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller Node *t = ei.getNode(); 41000fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if (t->getSequence() < seq) { 41100fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if (path[t->tag] == std::numeric_limits<int>::max()) 41200fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller nodeList.push_front(t); 41300fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if (p < path[t->tag]) 41400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller path[t->tag] = p; 41500fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller } 41600fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller } 41700fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller c->visit(seq); 41800fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller Node *next = NULL; 41900fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller for (std::list<Node *>::iterator n = nodeList.begin(); 42000fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller n != nodeList.end(); ++n) { 42100fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if (!next || path[(*n)->tag] < path[next->tag]) 42200fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller next = *n; 42300fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if ((*n) == c) { 42400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller // erase visited 42500fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller n = nodeList.erase(n); 42600fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller --n; 42700fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller } 42800fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller } 42900fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller c = next; 43000fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller } 43100fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller if (path[b->tag] == std::numeric_limits<int>::max()) 43200fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller return -1; 43300fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller return path[b->tag]; 43400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller} 43500fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller 43657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 437