1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright 2011 Christoph Bumiller 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice shall be included in 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * all copies or substantial portions of the Software. 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * SOFTWARE. 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "nv50_ir_graph.h" 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <limits> 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <list> 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <stack> 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "nv50_ir.h" 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace nv50_ir { 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::Graph() 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org root = NULL; 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = 0; 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org sequence = 0; 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::~Graph() 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = safeIteratorDFS(); !it->end(); it->next()) 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org reinterpret_cast<Node *>(it->get())->cut(); 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::insert(Node *node) 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!root) 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org root = node; 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->graph = this; 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size++; 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::Edge::unlink() 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (origin) { 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev[0]->next[0] = next[0]; 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next[0]->prev[0] = prev[0]; 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (origin->out == this) 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org origin->out = (next[0] == this) ? NULL : next[0]; 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org --origin->outCount; 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (target) { 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev[1]->next[1] = next[1]; 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next[1]->prev[1] = prev[1]; 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (target->in == this) 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org target->in = (next[1] == this) ? NULL : next[1]; 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org --target->inCount; 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgconst char *Graph::Edge::typeStr() const 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org switch (type) { 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case TREE: return "tree"; 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case FORWARD: return "forward"; 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case BACK: return "back"; 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case CROSS: return "cross"; 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case DUMMY: return "dummy"; 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case UNKNOWN: 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org default: 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return "unk"; 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::Node::Node(void *priv) : data(priv), 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org in(0), out(0), graph(0), 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org visited(0), 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inCount(0), outCount(0) 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // nothing to do 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::Node::attach(Node *node, Edge::Type kind) 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Edge *edge = new Edge(this, node, kind); 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // insert head 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (this->out) { 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->next[0] = this->out; 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->prev[0] = this->out->prev[0]; 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->prev[0]->next[0] = edge; 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->out->prev[0] = edge; 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->out = edge; 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (node->in) { 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->next[1] = node->in; 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->prev[1] = node->in->prev[1]; 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->prev[1]->next[1] = edge; 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->in->prev[1] = edge; 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->in = edge; 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++this->outCount; 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++node->inCount; 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(graph || node->graph); 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!node->graph) 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org graph->insert(node); 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!graph) 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->graph->insert(this); 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (kind == Edge::UNKNOWN) 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org graph->classifyEdges(); 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool Graph::Node::detach(Graph::Node *node) 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org EdgeIterator ei = this->outgoing(); 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (; !ei.end(); ei.next()) 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.getNode() == node) 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.end()) { 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ERROR("no such node attached\n"); 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete ei.getEdge(); 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// Cut a node from the graph, deleting all attached edges. 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::Node::cut() 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (out) 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete out; 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (in) 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete in; 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (graph) { 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (graph->root == this) 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org graph->root = NULL; 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org graph = NULL; 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::Edge::Edge(Node *org, Node *tgt, Type kind) 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org target = tgt; 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org origin = org; 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org type = kind; 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next[0] = next[1] = this; 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev[0] = prev[1] = this; 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::Node::reachableBy(const Node *node, const Node *term) const 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::stack<const Node *> stack; 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const Node *pos = NULL; 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const int seq = graph->nextSequence(); 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack.push(node); 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (!stack.empty()) { 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = stack.top(); 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack.pop(); 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos == this) 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos == term) 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (EdgeIterator ei = pos->outgoing(); !ei.end(); ei.next()) { 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.getType() == Edge::BACK || ei.getType() == Edge::DUMMY) 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.getNode()->visit(seq)) 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack.push(ei.getNode()); 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return pos == this; 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass DFSIterator : public Iterator 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DFSIterator(Graph *graph, const bool preorder) 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int seq = graph->nextSequence(); 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes = new Graph::Node * [graph->getSize() + 1]; 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 0; 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = 0; 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes[graph->getSize()] = 0; 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (graph->getRoot()) { 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org graph->getRoot()->visit(seq); 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org search(graph->getRoot(), preorder, seq); 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~DFSIterator() 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (nodes) 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] nodes; 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void search(Graph::Node *node, const bool preorder, const int sequence) 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (preorder) 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes[count++] = node; 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.getNode()->visit(sequence)) 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org search(ei.getNode(), preorder, sequence); 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!preorder) 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes[count++] = node; 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool end() const { return pos >= count; } 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void next() { if (pos < count) ++pos; } 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *get() const { return nodes[pos]; } 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void reset() { pos = 0; } 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node **nodes; 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int count; 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int pos; 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgIteratorRef Graph::iteratorDFS(bool preorder) 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return IteratorRef(new DFSIterator(this, preorder)); 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgIteratorRef Graph::safeIteratorDFS(bool preorder) 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return this->iteratorDFS(preorder); 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass CFGIterator : public Iterator 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org CFGIterator(Graph *graph) 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes = new Graph::Node * [graph->getSize() + 1]; 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 0; 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = 0; 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes[graph->getSize()] = 0; 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // TODO: argh, use graph->sequence instead of tag and just raise it by > 1 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = graph->iteratorDFS(); !it->end(); it->next()) 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org reinterpret_cast<Graph::Node *>(it->get())->tag = 0; 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (graph->getRoot()) 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org search(graph->getRoot(), graph->nextSequence()); 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~CFGIterator() 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (nodes) 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] nodes; 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *get() const { return nodes[pos]; } 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool end() const { return pos >= count; } 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void next() { if (pos < count) ++pos; } 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void reset() { pos = 0; } 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void search(Graph::Node *node, const int sequence) 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Stack bb, cross; 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb.push(node); 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (bb.getSize()) { 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node = reinterpret_cast<Graph::Node *>(bb.pop().u.p); 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(node); 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!node->visit(sequence)) 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->tag = 0; 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org switch (ei.getType()) { 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::TREE: 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::FORWARD: 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::DUMMY: 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (++(ei.getNode()->tag) == ei.getNode()->incidentCountFwd()) 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb.push(ei.getNode()); 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::BACK: 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::CROSS: 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (++(ei.getNode()->tag) == 1) 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org cross.push(ei.getNode()); 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org default: 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!"unknown edge kind in CFG"); 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodes[count++] = node; 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (bb.getSize() == 0) 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org cross.moveTo(bb); 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node **nodes; 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int count; 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int pos; 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgIteratorRef Graph::iteratorCFG() 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return IteratorRef(new CFGIterator(this)); 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgIteratorRef Graph::safeIteratorCFG() 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return this->iteratorCFG(); 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::classifyEdges() 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int seq; 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = iteratorDFS(true); !it->end(); it->next()) { 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Node *node = reinterpret_cast<Node *>(it->get()); 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->visit(0); 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node->tag = 0; 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org classifyDFS(root, (seq = 0)); 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org sequence = seq; 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Graph::classifyDFS(Node *curr, int& seq) 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Edge *edge; 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *node; 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org curr->visit(++seq); 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org curr->tag = 1; 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (edge = curr->out; edge; edge = edge->next[0]) { 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node = edge->target; 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (edge->type == Edge::DUMMY) 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (node->getSequence() == 0) { 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = Edge::TREE; 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org classifyDFS(node, seq); 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (node->getSequence() > curr->getSequence()) { 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = Edge::FORWARD; 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = node->tag ? Edge::BACK : Edge::CROSS; 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (edge = curr->in; edge; edge = edge->next[1]) { 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org node = edge->origin; 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (edge->type == Edge::DUMMY) 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (node->getSequence() == 0) { 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = Edge::TREE; 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org classifyDFS(node, seq); 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (node->getSequence() > curr->getSequence()) { 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = Edge::FORWARD; 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org edge->type = node->tag ? Edge::BACK : Edge::CROSS; 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org curr->tag = 0; 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// @dist is indexed by Node::tag, returns -1 if no path found 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgint 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGraph::findLightestPathWeight(Node *a, Node *b, const std::vector<int> &weight) 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::vector<int> path(weight.size(), std::numeric_limits<int>::max()); 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::list<Node *> nodeList; 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const int seq = nextSequence(); 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org path[a->tag] = 0; 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Node *c = a; c && c != b;) { 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const int p = path[c->tag] + weight[c->tag]; 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (EdgeIterator ei = c->outgoing(); !ei.end(); ei.next()) { 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Node *t = ei.getNode(); 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (t->getSequence() < seq) { 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (path[t->tag] == std::numeric_limits<int>::max()) 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nodeList.push_front(t); 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (p < path[t->tag]) 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org path[t->tag] = p; 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org c->visit(seq); 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Node *next = NULL; 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (std::list<Node *>::iterator n = nodeList.begin(); 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org n != nodeList.end(); ++n) { 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!next || path[(*n)->tag] < path[next->tag]) 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = *n; 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((*n) == c) { 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // erase visited 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org n = nodeList.erase(n); 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org --n; 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org c = next; 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (path[b->tag] == std::numeric_limits<int>::max()) 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return -1; 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return path[b->tag]; 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} // namespace nv50_ir 437