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.h" 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "nv50_ir_target.h" 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace nv50_ir { 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// Converts nv50 IR generated from TGSI to SSA form. 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// DominatorTree implements an algorithm for finding immediate dominators, 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// as described by T. Lengauer & R. Tarjan. 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass DominatorTree : public Graph 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DominatorTree(Graph *cfg); 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~DominatorTree() { } 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool dominates(BasicBlock *, BasicBlock *); 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void findDominanceFrontiers(); 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void build(); 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void buildDFS(Node *); 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void squash(int); 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void link(int, int); 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline int eval(int); 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void debugPrint(); 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph *cfg; 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Node **vert; 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int *data; 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const int count; 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #define SEMI(i) (data[(i) + 0 * count]) 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #define ANCESTOR(i) (data[(i) + 1 * count]) 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #define PARENT(i) (data[(i) + 2 * count]) 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #define LABEL(i) (data[(i) + 3 * count]) 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #define DOM(i) (data[(i) + 4 * count]) 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::debugPrint() 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (int i = 0; i < count; ++i) { 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("SEMI(%i) = %i\n", i, SEMI(i)); 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("ANCESTOR(%i) = %i\n", i, ANCESTOR(i)); 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("PARENT(%i) = %i\n", i, PARENT(i)); 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("LABEL(%i) = %i\n", i, LABEL(i)); 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("DOM(%i) = %i\n", i, DOM(i)); 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgDominatorTree::DominatorTree(Graph *cfgraph) : cfg(cfgraph), 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count(cfg->getSize()) 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int i = 0; 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org vert = new Node * [count]; 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = new int[5 * count]; 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = cfg->iteratorDFS(true); !it->end(); it->next(), ++i) { 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org vert[i] = reinterpret_cast<Node *>(it->get()); 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org vert[i]->tag = i; 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LABEL(i) = i; 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org SEMI(i) = ANCESTOR(i) = -1; 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org build(); 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] vert; 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] data; 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::buildDFS(Graph::Node *node) 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org SEMI(node->tag) = node->tag; 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (SEMI(ei.getNode()->tag) < 0) { 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildDFS(ei.getNode()); 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PARENT(ei.getNode()->tag) = node->tag; 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::squash(int v) 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ANCESTOR(ANCESTOR(v)) >= 0) { 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org squash(ANCESTOR(v)); 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (SEMI(LABEL(ANCESTOR(v))) < SEMI(LABEL(v))) 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LABEL(v) = LABEL(ANCESTOR(v)); 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ANCESTOR(v) = ANCESTOR(ANCESTOR(v)); 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgint DominatorTree::eval(int v) 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ANCESTOR(v) < 0) 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return v; 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org squash(v); 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return LABEL(v); 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::link(int v, int w) 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ANCESTOR(w) = v; 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::build() 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLList *bucket = new DLList[count]; 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Node *nv, *nw; 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int p, u, v, w; 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildDFS(cfg->getRoot()); 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (w = count - 1; w >= 1; --w) { 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nw = vert[w]; 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(nw->tag == w); 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = nw->incident(); !ei.end(); ei.next()) { 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nv = ei.getNode(); 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org v = nv->tag; 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org u = eval(v); 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (SEMI(u) < SEMI(w)) 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org SEMI(w) = SEMI(u); 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p = PARENT(w); 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bucket[SEMI(w)].insert(nw); 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org link(p, w); 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (DLList::Iterator it = bucket[p].iterator(); !it.end(); it.erase()) { 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org v = reinterpret_cast<Node *>(it.get())->tag; 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org u = eval(v); 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DOM(v) = (SEMI(u) < SEMI(v)) ? u : p; 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (w = 1; w < count; ++w) { 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (DOM(w) != SEMI(w)) 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DOM(w) = DOM(DOM(w)); 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DOM(0) = 0; 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insert(&BasicBlock::get(cfg->getRoot())->dom); 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p = 0; 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (v = 1; v < count; ++v) { 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nw = &BasicBlock::get(vert[DOM(v)])->dom;; 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nv = &BasicBlock::get(vert[v])->dom; 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (nw->getGraph() && !nv->getGraph()) { 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++p; 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nw->attach(nv, Graph::Edge::TREE); 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while (p); 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] bucket; 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#undef SEMI 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#undef ANCESTOR 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#undef PARENT 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#undef LABEL 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#undef DOM 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DominatorTree::findDominanceFrontiers() 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb; 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef dtIt = iteratorDFS(false); !dtIt->end(); dtIt->next()) { 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org EdgeIterator succIt, chldIt; 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb = BasicBlock::get(reinterpret_cast<Node *>(dtIt->get())); 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->getDF().clear(); 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (succIt = bb->cfg.outgoing(); !succIt.end(); succIt.next()) { 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *dfLocal = BasicBlock::get(succIt.getNode()); 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (dfLocal->idom() != bb) 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->getDF().insert(dfLocal); 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (chldIt = bb->dom.outgoing(); !chldIt.end(); chldIt.next()) { 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *cb = BasicBlock::get(chldIt.getNode()); 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLList::Iterator dfIt = cb->getDF().iterator(); 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (; !dfIt.end(); dfIt.next()) { 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *dfUp = BasicBlock::get(dfIt); 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (dfUp->idom() != bb) 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->getDF().insert(dfUp); 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb)) 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::buildLiveSetsPreSSA(BasicBlock *bb, const int seq) 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Function *f = bb->getFunction(); 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet usedBeforeAssigned(allLValues.getSize(), true); 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet assigned(allLValues.getSize(), true); 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet.allocate(allLValues.getSize(), false); 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n = 0; 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *out = BasicBlock::get(ei.getNode()); 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out == bb) 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out->cfg.visit(seq)) 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildLiveSetsPreSSA(out, seq); 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!n++) 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet = out->liveSet; 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet |= out->liveSet; 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!n && !bb->liveSet.marker) 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet.fill(0); 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet.marker = true; 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *i = bb->getEntry(); i; i = i->next) { 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (int s = 0; i->srcExists(s); ++s) 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i->getSrc(s)->asLValue() && !assigned.test(i->getSrc(s)->id)) 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org usedBeforeAssigned.set(i->getSrc(s)->id); 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (int d = 0; i->defExists(d); ++d) 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assigned.set(i->getDef(d)->id); 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (bb == BasicBlock::get(f->cfgExit)) { 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (std::deque<ValueRef>::iterator it = f->outs.begin(); 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org it != f->outs.end(); ++it) { 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!assigned.test(it->get()->id)) 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org usedBeforeAssigned.set(it->get()->id); 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet.andNot(assigned); 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet |= usedBeforeAssigned; 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::buildDefSetsPreSSA(BasicBlock *bb, const int seq) 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->defSet.allocate(allLValues.getSize(), !bb->liveSet.marker); 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->liveSet.marker = true; 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *in = BasicBlock::get(ei.getNode()); 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (in->cfg.visit(seq)) 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildDefSetsPreSSA(in, seq); 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->defSet |= in->defSet; 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *i = bb->getEntry(); i; i = i->next) { 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (int d = 0; i->defExists(d); ++d) 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->defSet.set(i->getDef(d)->id); 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass RenamePass 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org RenamePass(Function *); 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~RenamePass(); 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool run(); 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void search(BasicBlock *); 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline LValue *getStackTop(Value *); 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LValue *mkUndefined(Value *); 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Stack *stack; 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Function *func; 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Program *prog; 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgProgram::convertToSSA() 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator fi = allFuncs.iterator(); !fi.end(); fi.next()) { 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Function *fn = reinterpret_cast<Function *>(fi.get()); 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!fn->convertToSSA()) 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// XXX: add edge from entry to exit ? 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// Efficiently Computing Static Single Assignment Form and 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// the Control Dependence Graph, 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::convertToSSA() 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // 0. calculate live in variables (for pruned SSA) 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildLiveSets(); 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // 1. create the dominator tree 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org domTree = new DominatorTree(&cfg); 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org reinterpret_cast<DominatorTree *>(domTree)->findDominanceFrontiers(); 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // 2. insert PHI functions 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLList workList; 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LValue *lval; 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb; 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int var; 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int iterCount = 0; 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int *hasAlready = new int[allBBlocks.getSize() * 2]; 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int *work = &hasAlready[allBBlocks.getSize()]; 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org memset(hasAlready, 0, allBBlocks.getSize() * 2 * sizeof(int)); 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // for each variable 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (var = 0; var < allLValues.getSize(); ++var) { 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!allLValues.get(var)) 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = reinterpret_cast<Value *>(allLValues.get(var))->asLValue(); 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval || lval->defs.empty()) 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++iterCount; 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // TODO: don't add phi functions for values that aren't used outside 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // the BB they're defined in 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // gather blocks with assignments to lval in workList 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Value::DefIterator d = lval->defs.begin(); 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org d != lval->defs.end(); ++d) { 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb = ((*d)->getInsn() ? (*d)->getInsn()->bb : NULL); 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!bb) 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; // instruction likely been removed but not XXX deleted 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (work[bb->getId()] == iterCount) 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org work[bb->getId()] = iterCount; 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org workList.insert(bb); 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // for each block in workList, insert a phi for lval in the block's 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // dominance frontier (if we haven't already done so) 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (DLList::Iterator wI = workList.iterator(); !wI.end(); wI.erase()) { 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb = BasicBlock::get(wI); 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLList::Iterator dfIter = bb->getDF().iterator(); 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (; !dfIter.end(); dfIter.next()) { 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Instruction *phi; 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *dfBB = BasicBlock::get(dfIter); 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (hasAlready[dfBB->getId()] >= iterCount) 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hasAlready[dfBB->getId()] = iterCount; 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // pruned SSA: don't need a phi if the value is not live-in 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!dfBB->liveSet.test(lval->id)) 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = new_Instruction(this, OP_PHI, typeOfSize(lval->reg.size)); 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org dfBB->insertTail(phi); 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi->setDef(0, lval); 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (int s = 0; s < dfBB->cfg.incidentCount(); ++s) 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi->setSrc(s, lval); 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (work[dfBB->getId()] < iterCount) { 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org work[dfBB->getId()] = iterCount; 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org wI.insert(dfBB); 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] hasAlready; 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org RenamePass rename(this); 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return rename.run(); 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgRenamePass::RenamePass(Function *fn) : func(fn), prog(fn->getProgram()) 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack = new Stack[func->allLValues.getSize()]; 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgRenamePass::~RenamePass() 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (stack) 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] stack; 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgLValue * 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgRenamePass::getStackTop(Value *val) 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!stack[val->id].getSize()) 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return reinterpret_cast<LValue *>(stack[val->id].peek().u.p); 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgLValue * 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgRenamePass::mkUndefined(Value *val) 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LValue *lval = val->asLValue(); 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lval); 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LValue *ud = new_LValue(func, lval); 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Instruction *nop = new_Instruction(func, OP_NOP, typeOfSize(lval->reg.size)); 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nop->setDef(0, ud); 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock::get(func->cfg.getRoot())->insertHead(nop); 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ud; 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool RenamePass::run() 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!stack) 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org search(BasicBlock::get(func->domTree->getRoot())); 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid RenamePass::search(BasicBlock *bb) 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org LValue *lval, *ssa; 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int d, s; 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const Target *targ = prog->getTarget(); 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (bb == BasicBlock::get(func->cfg.getRoot())) { 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (std::deque<ValueDef>::iterator it = func->ins.begin(); 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org it != func->ins.end(); ++it) { 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = it->get()->asLValue(); 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lval); 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ssa = new_LValue(func, targ->nativeFile(lval->reg.file)); 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ssa->reg.size = lval->reg.size; 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ssa->reg.data.id = lval->reg.data.id; 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org it->setSSA(ssa); 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack[lval->id].push(ssa); 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) { 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (stmt->op != OP_PHI) { 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (s = 0; stmt->srcExists(s); ++s) { 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = stmt->getSrc(s)->asLValue(); 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval) 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = getStackTop(lval); 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval) 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = mkUndefined(stmt->getSrc(s)); 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stmt->setSrc(s, lval); 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (d = 0; stmt->defExists(d); ++d) { 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = stmt->def(d).get()->asLValue(); 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lval); 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stmt->def(d).setSSA( 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org new_LValue(func, targ->nativeFile(lval->reg.file))); 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stmt->def(d).get()->reg.size = lval->reg.size; 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stmt->def(d).get()->reg.data.id = lval->reg.data.id; 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack[lval->id].push(stmt->def(d).get()); 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Instruction *phi; 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int p = 0; 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *sb = BasicBlock::get(ei.getNode()); 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // which predecessor of sb is bb ? 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = sb->cfg.incident(); !ei.end(); ei.next()) { 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ei.getNode() == &bb->cfg) 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++p; 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(p < sb->cfg.incidentCount()); 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (phi = sb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) { 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = getStackTop(phi->getSrc(p)); 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval) 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = mkUndefined(phi->getSrc(p)); 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi->setSrc(p, lval); 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = bb->dom.outgoing(); !ei.end(); ei.next()) 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org search(BasicBlock::get(ei.getNode())); 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (bb == BasicBlock::get(func->cfgExit)) { 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (std::deque<ValueRef>::iterator it = func->outs.begin(); 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org it != func->outs.end(); ++it) { 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = it->get()->asLValue(); 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval) 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = getStackTop(lval); 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lval) 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lval = mkUndefined(it->get()); 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org it->set(lval); 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) { 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (stmt->op == OP_NOP) 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (d = 0; stmt->defExists(d); ++d) 529f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stack[stmt->def(d).preSSA()->id].pop(); 530f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 531f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 532f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 533f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} // namespace nv50_ir 534