1d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller/* 2d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Copyright 2011 Christoph Bumiller 3d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 4d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Permission is hereby granted, free of charge, to any person obtaining a 5d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * copy of this software and associated documentation files (the "Software"), 6d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * to deal in the Software without restriction, including without limitation 7d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * and/or sell copies of the Software, and to permit persons to whom the 9d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Software is furnished to do so, subject to the following conditions: 10d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 11d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * The above copyright notice and this permission notice shall be included in 12d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * all copies or substantial portions of the Software. 13d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 14d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * SOFTWARE. 21d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller */ 2257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50_ir.h" 2457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir { 2657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2798116cc3dc3fc2cd84990cc2c968f05fe2978b4aFrancisco JerezFunction::Function(Program *p, const char *fnName, uint32_t label) 2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller : call(this), 2998116cc3dc3fc2cd84990cc2c968f05fe2978b4aFrancisco Jerez label(label), 3057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller name(fnName), 3157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog(p) 3257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 3357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cfgExit = NULL; 3457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller domTree = NULL; 3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbArray = NULL; 3757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbCount = 0; 3857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller loopNestingBound = 0; 3957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regClobberMax = 0; 4057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller binPos = 0; 4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller binSize = 0; 4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stackPtr = NULL; 45e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tlsBase = 0; 46e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tlsSize = 0; 47e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 4857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog->add(this, id); 4957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 5057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerFunction::~Function() 5257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 535e4b2a1a47ca9a173f6419ed2f12c9fba80e757cFrancisco Jerez prog->del(this, id); 545e4b2a1a47ca9a173f6419ed2f12c9fba80e757cFrancisco Jerez 5557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (domTree) 5657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete domTree; 5757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bbArray) 5857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete[] bbArray; 5957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next()) 61da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get())); 62da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez 63da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next()) 64da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez delete_Value(prog, reinterpret_cast<LValue *>(it.get())); 65da28ba00d84f59650bf180769d9d9a1609eb6164Francisco Jerez 6657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next()) 6757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete reinterpret_cast<BasicBlock *>(BBs.get()); 6857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 6957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn) 7157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 7257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller program = func->getProgram(); 7357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller joinAt = phi = entry = exit = NULL; 7557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller numInsns = 0; 7757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller binPos = 0; 7857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller binSize = 0; 7957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller explicitCont = false; 8157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller func->add(this, this->id); 8357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 8457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::~BasicBlock() 8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 8757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // nothing yet 8857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 8957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock * 91784848a94d621b11020838fc058fc04a7fc57aa9Francisco JerezBasicBlock::clone(ClonePolicy<Function>& pol) const 92784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez{ 93784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez BasicBlock *bb = new BasicBlock(pol.context()); 94784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 95784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez pol.set(this, bb); 96784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 97784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez for (Instruction *i = getFirst(); i; i = i->next) 98784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez bb->insertTail(i->clone(pol)); 99784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 100784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez pol.context()->cfg.insert(&bb->cfg); 101784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 102784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) { 103784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez BasicBlock *obb = BasicBlock::get(it.getNode()); 104784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez bb->cfg.attach(&pol.get(obb)->cfg, it.getType()); 105784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez } 106784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 107784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez return bb; 108784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez} 109784848a94d621b11020838fc058fc04a7fc57aa9Francisco Jerez 110784848a94d621b11020838fc058fc04a7fc57aa9Francisco JerezBasicBlock * 11157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::idom() const 11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node *dn = dom.parent(); 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return dn ? BasicBlock::get(dn) : NULL; 11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 11857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::insertHead(Instruction *inst) 11957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 12057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(inst->next == 0 && inst->prev == 0); 12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (inst->op == OP_PHI) { 12357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (phi) { 12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertBefore(phi, inst); 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (entry) { 127ab382fbc35f6fd007dc278fcf4bc0dd3c0987a60Francisco Jerez insertBefore(entry, inst); 12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(!exit); 13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi = exit = inst; 13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inst->bb = this; 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (entry) { 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertBefore(entry, inst); 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (phi) { 140fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller insertAfter(exit, inst); // after last phi 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(!exit); 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller entry = exit = inst; 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inst->bb = this; 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 15257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::insertTail(Instruction *inst) 15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(inst->next == 0 && inst->prev == 0); 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (inst->op == OP_PHI) { 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (entry) { 15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertBefore(entry, inst); 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (exit) { 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(phi); 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertAfter(exit, inst); 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(!phi); 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi = exit = inst; 16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inst->bb = this; 16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 16957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (exit) { 17157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertAfter(exit, inst); 17257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(!phi); 17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller entry = exit = inst; 17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inst->bb = this; 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 17757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 17957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 18257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::insertBefore(Instruction *q, Instruction *p) 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(p && q); 18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(p->next == 0 && p->prev == 0); 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (q == entry) { 18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (p->op == OP_PHI) { 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!phi) 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi = p; 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller entry = p; 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (q == phi) { 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(p->op == OP_PHI); 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi = p; 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller p->next = q; 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller p->prev = q->prev; 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (p->prev) 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller p->prev->next = p; 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller q->prev = p; 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller p->bb = this; 20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 21257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::insertAfter(Instruction *p, Instruction *q) 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(p && q); 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(q->op != OP_PHI || p->op == OP_PHI); 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(q->next == 0 && q->prev == 0); 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (p == exit) 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller exit = q; 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (p->op == OP_PHI && q->op != OP_PHI) 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller entry = q; 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller q->prev = p; 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller q->next = p->next; 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (q->next) 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller q->next->prev = q; 22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller p->next = q; 22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller q->bb = this; 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++numInsns; 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 23557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::remove(Instruction *insn) 23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(insn->bb == this); 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (insn->prev) 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->prev->next = insn->next; 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (insn->next) 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->next->prev = insn->prev; 24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller else 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller exit = insn->prev; 24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 247fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller if (insn == entry) { 248fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller if (insn->next) 249fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller entry = insn->next; 250fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller else 251fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller if (insn->prev && insn->prev->op != OP_PHI) 252fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller entry = insn->prev; 253fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller else 254fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller entry = NULL; 255fc740e7924dfa52a39de5f2b8031c2cded0fafb3Christoph Bumiller } 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (insn == phi) 25857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0; 25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller --numInsns; 26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->bb = NULL; 26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->next = 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->prev = NULL; 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid BasicBlock::permuteAdjacent(Instruction *a, Instruction *b) 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(a->bb == b->bb); 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (a->next != b) { 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i = a; 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller a = b; 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller b = i; 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(a->next == b); 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(a->op != OP_PHI && b->op != OP_PHI); 27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b == exit) 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller exit = a; 28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (a == entry) 28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller entry = b; 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller b->prev = a->prev; 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller a->next = b->next; 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller b->next = a; 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller a->prev = b; 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b->prev) 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller b->prev->next = b; 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (a->prev) 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller a->next->prev = a; 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 294c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumillervoid 295c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph BumillerBasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach) 296c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller{ 297c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller bb->entry = insn; 298c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 299c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller if (insn) { 300c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller exit = insn->prev; 301c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller insn->prev = NULL; 302c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller } 303c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 304c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller if (exit) 305c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller exit->next = NULL; 306c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller else 307c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller entry = NULL; 308c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 309c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller while (!cfg.outgoing(true).end()) { 310c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller Graph::Edge *e = cfg.outgoing(true).getEdge(); 311c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller bb->cfg.attach(e->getTarget(), e->getType()); 312c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller this->cfg.detach(e->getTarget()); 313c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller } 314c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 315c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller for (; insn; insn = insn->next) { 316c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller this->numInsns--; 317c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller bb->numInsns++; 318c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller insn->bb = bb; 319c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller bb->exit = insn; 320c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller } 321c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller if (attach) 322c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller this->cfg.attach(&bb->cfg, Graph::Edge::TREE); 323c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller} 324c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 325c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph BumillerBasicBlock * 326c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph BumillerBasicBlock::splitBefore(Instruction *insn, bool attach) 327c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller{ 328c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller BasicBlock *bb = new BasicBlock(func); 329c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller assert(!insn || insn->op != OP_PHI); 330c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 331c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller splitCommon(insn, bb, attach); 332c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller return bb; 333c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller} 334c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 335c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph BumillerBasicBlock * 336c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph BumillerBasicBlock::splitAfter(Instruction *insn, bool attach) 337c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller{ 338c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller BasicBlock *bb = new BasicBlock(func); 339c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller assert(!insn || insn->op != OP_PHI); 340c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 341c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller bb->joinAt = joinAt; 342c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller joinAt = NULL; 343c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 344c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller splitCommon(insn ? insn->next : NULL, bb, attach); 345c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller return bb; 346c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller} 347c04d6d95e0efb8eea4d788d8d7b629209a3afaeaChristoph Bumiller 34857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 34957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::dominatedBy(BasicBlock *that) 35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node *bn = &that->dom; 35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node *dn = &this->dom; 35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (dn && dn != bn) 35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller dn = dn->parent(); 35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return dn != NULL; 35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerunsigned int 36157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBasicBlock::initiatesSimpleConditional() const 36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Node *out[2]; 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n; 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Graph::Edge::Type eR; 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cfg.outgoingCount() != 2) // -> if and -> else/endif 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller n = 0; 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next()) 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller out[n++] = ei.getNode(); 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller eR = out[1]->outgoing().getType(); 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // IF block is out edge to the right 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK) 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return 0x2; 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return 0x0; 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // do they reconverge immediately ? 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (out[1]->outgoing().getNode() == out[0]) 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return 0x1; 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (out[0]->outgoingCount() == 1) 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode()) 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return 0x3; 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return 0x0; 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 39257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerFunction::setEntry(BasicBlock *bb) 39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cfg.getRoot()) 39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cfg.insert(&bb->cfg); 39757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 39857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 39957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 40157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerFunction::setExit(BasicBlock *bb) 40257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 40357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cfgExit) 40457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 40557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cfgExit = &bb->cfg; 40657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 40757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 40857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerunsigned int 41057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerFunction::orderInstructions(ArrayList &result) 41157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 4124a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez result.clear(); 4134a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez 41478de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) { 41518294844584f1a64454593c056148201c4d79ef7Francisco Jerez BasicBlock *bb = 41678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get())); 41718294844584f1a64454593c056148201c4d79ef7Francisco Jerez 41818294844584f1a64454593c056148201c4d79ef7Francisco Jerez for (Instruction *insn = bb->getFirst(); insn; insn = insn->next) 41957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller result.insert(insn, insn->serial); 42018294844584f1a64454593c056148201c4d79ef7Francisco Jerez } 42118294844584f1a64454593c056148201c4d79ef7Francisco Jerez 42257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return result.getSize(); 42357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 42457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4253e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerezvoid 426898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco JerezFunction::buildLiveSets() 427898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez{ 428898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez for (unsigned i = 0; i <= loopNestingBound; ++i) 429898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence()); 430898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez 431898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) 432898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez BasicBlock::get(bi)->liveSet.marker = false; 433898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez} 434898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerez 435898b0981b6c90d2f1e446a532b6ac3cbbb49747dFrancisco Jerezvoid 4363e9150cd961b2399e402e940400deae11ec7852fFrancisco JerezFunction::buildDefSets() 4373e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez{ 4383e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez for (unsigned i = 0; i <= loopNestingBound; ++i) 4393e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence()); 4403e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez 4413e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) 4423e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez BasicBlock::get(bi)->liveSet.marker = false; 4433e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez} 4443e9150cd961b2399e402e940400deae11ec7852fFrancisco Jerez 44557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 44657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerPass::run(Program *prog, bool ordered, bool skipPhi) 44757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->prog = prog; 44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller err = false; 45057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return doRun(prog, ordered, skipPhi); 45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 45257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 45457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerPass::doRun(Program *prog, bool ordered, bool skipPhi) 45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 456d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez for (IteratorRef it = prog->calls.iteratorDFS(false); 457d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez !it->end(); it->next()) { 458d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get()); 459d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez if (!doRun(Function::get(n), ordered, skipPhi)) 46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 46257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return !err; 46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 46657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerPass::run(Function *func, bool ordered, bool skipPhi) 46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog = func->getProgram(); 46957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller err = false; 47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return doRun(func, ordered, skipPhi); 47157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 47257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 47457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerPass::doRun(Function *func, bool ordered, bool skipPhi) 47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 47678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez IteratorRef bbIter; 47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bb; 47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *insn, *next; 47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->func = func; 48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!visit(func)) 48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS(); 48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (; !bbIter->end(); bbIter->next()) { 48757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get())); 48857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!visit(bb)) 48957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 49057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL; 49157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn = next) { 49257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = insn->next; 49357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!visit(insn)) 49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 49778de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez 49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return !err; 49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 50057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 50257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerFunction::printCFGraph(const char *filePath) 50357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 50457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FILE *out = fopen(filePath, "a"); 50557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!out) { 50657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ERROR("failed to open file: %s\n", filePath); 50757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 50857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 50957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("printing control flow graph to: %s\n", filePath); 51057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "digraph G {\n"); 51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51378de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) { 51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bb = BasicBlock::get( 51578de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez reinterpret_cast<Graph::Node *>(it->get())); 51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int idA = bb->getId(); 51757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 51857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int idB = BasicBlock::get(ei.getNode())->getId(); 51957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (ei.getType()) { 52057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::TREE: 52157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "\t%i -> %i;\n", idA, idB); 52257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 52357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::FORWARD: 52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "\t%i -> %i [color=green];\n", idA, idB); 52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::CROSS: 52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "\t%i -> %i [color=red];\n", idA, idB); 52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 52957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::BACK: 53057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "\t%i -> %i;\n", idA, idB); 53157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 53257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case Graph::Edge::DUMMY: 53357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB); 53457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 53557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 53657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(0); 53757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 53857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 53957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fprintf(out, "}\n"); 54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fclose(out); 54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 547