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 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace nv50_ir { 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::Function(Program *p, const char *fnName, uint32_t label) 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org : call(this), 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org label(label), 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org name(fnName), 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prog(p) 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org cfgExit = NULL; 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org domTree = NULL; 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bbArray = NULL; 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bbCount = 0; 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loopNestingBound = 0; 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org regClobberMax = 0; 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org binPos = 0; 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org binSize = 0; 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org stackPtr = NULL; 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org tlsBase = 0; 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org tlsSize = 0; 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prog->add(this, id); 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::~Function() 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prog->del(this, id); 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (domTree) 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete domTree; 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (bbArray) 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete[] bbArray; 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next()) 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get())); 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next()) 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete_Value(prog, reinterpret_cast<LValue *>(it.get())); 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next()) 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete reinterpret_cast<BasicBlock *>(BBs.get()); 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn) 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org program = func->getProgram(); 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org joinAt = phi = entry = exit = NULL; 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org numInsns = 0; 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org binPos = 0; 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org binSize = 0; 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org explicitCont = false; 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org func->add(this, this->id); 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::~BasicBlock() 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // nothing yet 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock * 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::clone(ClonePolicy<Function>& pol) const 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb = new BasicBlock(pol.context()); 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pol.set(this, bb); 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *i = getFirst(); i; i = i->next) 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->insertTail(i->clone(pol)); 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pol.context()->cfg.insert(&bb->cfg); 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) { 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *obb = BasicBlock::get(it.getNode()); 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->cfg.attach(&pol.get(obb)->cfg, it.getType()); 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return bb; 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock * 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::idom() const 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *dn = dom.parent(); 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return dn ? BasicBlock::get(dn) : NULL; 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::insertHead(Instruction *inst) 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(inst->next == 0 && inst->prev == 0); 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inst->op == OP_PHI) { 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (phi) { 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertBefore(phi, inst); 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry) { 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertBefore(entry, inst); 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!exit); 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = exit = inst; 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inst->bb = this; 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry) { 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertBefore(entry, inst); 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (phi) { 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertAfter(exit, inst); // after last phi 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!exit); 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = exit = inst; 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inst->bb = this; 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::insertTail(Instruction *inst) 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(inst->next == 0 && inst->prev == 0); 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inst->op == OP_PHI) { 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry) { 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertBefore(entry, inst); 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (exit) { 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(phi); 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertAfter(exit, inst); 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!phi); 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = exit = inst; 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inst->bb = this; 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (exit) { 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insertAfter(exit, inst); 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!phi); 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = exit = inst; 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inst->bb = this; 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::insertBefore(Instruction *q, Instruction *p) 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(p && q); 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(p->next == 0 && p->prev == 0); 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (q == entry) { 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (p->op == OP_PHI) { 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!phi) 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = p; 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = p; 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (q == phi) { 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(p->op == OP_PHI); 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = p; 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p->next = q; 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p->prev = q->prev; 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (p->prev) 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p->prev->next = p; 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org q->prev = p; 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p->bb = this; 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::insertAfter(Instruction *p, Instruction *q) 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(p && q); 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(q->op != OP_PHI || p->op == OP_PHI); 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(q->next == 0 && q->prev == 0); 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (p == exit) 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exit = q; 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (p->op == OP_PHI && q->op != OP_PHI) 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = q; 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org q->prev = p; 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org q->next = p->next; 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (q->next) 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org q->next->prev = q; 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org p->next = q; 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org q->bb = this; 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++numInsns; 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::remove(Instruction *insn) 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(insn->bb == this); 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn->prev) 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->prev->next = insn->next; 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn->next) 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->next->prev = insn->prev; 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exit = insn->prev; 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn == entry) { 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn->next) 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = insn->next; 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn->prev && insn->prev->op != OP_PHI) 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = insn->prev; 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = NULL; 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn == phi) 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0; 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org --numInsns; 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->bb = NULL; 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->next = 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->prev = NULL; 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid BasicBlock::permuteAdjacent(Instruction *a, Instruction *b) 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(a->bb == b->bb); 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a->next != b) { 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Instruction *i = a; 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org a = b; 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b = i; 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(a->next == b); 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(a->op != OP_PHI && b->op != OP_PHI); 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b == exit) 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exit = a; 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a == entry) 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = b; 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b->prev = a->prev; 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org a->next = b->next; 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b->next = a; 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org a->prev = b; 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b->prev) 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b->prev->next = b; 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a->prev) 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org a->next->prev = a; 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach) 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->entry = insn; 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (insn) { 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exit = insn->prev; 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->prev = NULL; 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (exit) 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exit->next = NULL; 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = NULL; 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (!cfg.outgoing(true).end()) { 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Edge *e = cfg.outgoing(true).getEdge(); 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->cfg.attach(e->getTarget(), e->getType()); 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->cfg.detach(e->getTarget()); 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (; insn; insn = insn->next) { 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->numInsns--; 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->numInsns++; 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn->bb = bb; 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->exit = insn; 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (attach) 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->cfg.attach(&bb->cfg, Graph::Edge::TREE); 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock * 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::splitBefore(Instruction *insn, bool attach) 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb = new BasicBlock(func); 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!insn || insn->op != OP_PHI); 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org splitCommon(insn, bb, attach); 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return bb; 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock * 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::splitAfter(Instruction *insn, bool attach) 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb = new BasicBlock(func); 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!insn || insn->op != OP_PHI); 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb->joinAt = joinAt; 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org joinAt = NULL; 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org splitCommon(insn ? insn->next : NULL, bb, attach); 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return bb; 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::dominatedBy(BasicBlock *that) 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *bn = &that->dom; 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *dn = &this->dom; 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (dn && dn != bn) 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org dn = dn->parent(); 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return dn != NULL; 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgunsigned int 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBasicBlock::initiatesSimpleConditional() const 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *out[2]; 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n; 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Edge::Type eR; 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (cfg.outgoingCount() != 2) // -> if and -> else/endif 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org n = 0; 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next()) 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org out[n++] = ei.getNode(); 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org eR = out[1]->outgoing().getType(); 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // IF block is out edge to the right 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK) 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0x2; 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0x0; 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // do they reconverge immediately ? 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out[1]->outgoing().getNode() == out[0]) 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0x1; 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out[0]->outgoingCount() == 1) 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode()) 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0x3; 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0x0; 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::setEntry(BasicBlock *bb) 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (cfg.getRoot()) 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org cfg.insert(&bb->cfg); 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::setExit(BasicBlock *bb) 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (cfgExit) 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org cfgExit = &bb->cfg; 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgunsigned int 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::orderInstructions(ArrayList &result) 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org result.clear(); 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) { 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb = 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get())); 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Instruction *insn = bb->getFirst(); insn; insn = insn->next) 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org result.insert(insn, insn->serial); 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return result.getSize(); 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::buildLiveSets() 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned i = 0; i <= loopNestingBound; ++i) 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence()); 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock::get(bi)->liveSet.marker = false; 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::buildDefSets() 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned i = 0; i <= loopNestingBound; ++i) 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence()); 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock::get(bi)->liveSet.marker = false; 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgPass::run(Program *prog, bool ordered, bool skipPhi) 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->prog = prog; 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org err = false; 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return doRun(prog, ordered, skipPhi); 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgPass::doRun(Program *prog, bool ordered, bool skipPhi) 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = prog->calls.iteratorDFS(false); 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org !it->end(); it->next()) { 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get()); 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!doRun(Function::get(n), ordered, skipPhi)) 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return !err; 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgPass::run(Function *func, bool ordered, bool skipPhi) 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prog = func->getProgram(); 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org err = false; 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return doRun(func, ordered, skipPhi); 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgPass::doRun(Function *func, bool ordered, bool skipPhi) 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org IteratorRef bbIter; 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb; 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Instruction *insn, *next; 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->func = func; 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!visit(func)) 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS(); 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (; !bbIter->end(); bbIter->next()) { 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get())); 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!visit(bb)) 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL; 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insn = next) { 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = insn->next; 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!visit(insn)) 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return !err; 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgFunction::printCFGraph(const char *filePath) 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FILE *out = fopen(filePath, "a"); 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!out) { 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ERROR("failed to open file: %s\n", filePath); 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("printing control flow graph to: %s\n", filePath); 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "digraph G {\n"); 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) { 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *bb = BasicBlock::get( 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org reinterpret_cast<Graph::Node *>(it->get())); 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int idA = bb->getId(); 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int idB = BasicBlock::get(ei.getNode())->getId(); 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org switch (ei.getType()) { 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::TREE: 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "\t%i -> %i;\n", idA, idB); 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::FORWARD: 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "\t%i -> %i [color=green];\n", idA, idB); 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::CROSS: 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "\t%i -> %i [color=red];\n", idA, idB); 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 529f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::BACK: 530f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "\t%i -> %i;\n", idA, idB); 531f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 532f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org case Graph::Edge::DUMMY: 533f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB); 534f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 535f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org default: 536f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(0); 537f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 538f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 539f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 540f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 541f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 542f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(out, "}\n"); 543f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fclose(out); 544f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 545f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 546f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} // namespace nv50_ir 547