1b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===// 2b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 3b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 5b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 8b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 10b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// Implementation of the LiveRangeCalc class. 11b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 12b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 14b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 15b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "LiveRangeCalc.h" 16b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 174e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 18b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 19b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenusing namespace llvm; 20b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 21beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesenvoid LiveRangeCalc::reset(const MachineFunction *mf, 22631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndexes *SI, 23631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MachineDominatorTree *MDT, 24631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo::Allocator *VNIA) { 25beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen MF = mf; 26631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 27631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen Indexes = SI; 28631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen DomTree = MDT; 29631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen Alloc = VNIA; 30631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen 31b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned N = MF->getNumBlockIDs(); 32b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.clear(); 33b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.resize(N); 34b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut.resize(N); 35b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 36b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 37b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 38b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 394e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesenvoid LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { 404e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(MRI && Indexes && "call reset() first"); 414e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 424e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Visit all def operands. If the same instruction has multiple defs of Reg, 434e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // LI->createDeadDef() will deduplicate. 444e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen for (MachineRegisterInfo::def_iterator 454e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { 464e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen const MachineInstr *MI = &*I; 474e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Find the corresponding slot index. 484e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen SlotIndex Idx; 494e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->isPHI()) 504e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // PHI defs begin at the basic block start index. 514e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getMBBStartIdx(MI->getParent()); 524e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen else 534e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Instructions are either normal 'r', or early clobber 'e'. 544e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getInstructionIndex(MI) 554e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen .getRegSlot(I.getOperand().isEarlyClobber()); 564e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 574e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Create the def in LI. This may find an existing def. 58b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen LI->createDeadDef(Idx, *Alloc); 594e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 604e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen} 614e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 624e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 634e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesenvoid LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) { 644e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(MRI && Indexes && "call reset() first"); 654e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 664e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Visit all operands that read Reg. This may include partial defs. 674e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg), 684e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen E = MRI->reg_nodbg_end(); I != E; ++I) { 69f9dff0e0e4e8aa9fd99c5f069e431fe6de98c1c9Jakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 70f9dff0e0e4e8aa9fd99c5f069e431fe6de98c1c9Jakob Stoklund Olesen // Clear all kill flags. They will be reinserted after register allocation 71f9dff0e0e4e8aa9fd99c5f069e431fe6de98c1c9Jakob Stoklund Olesen // by LiveIntervalAnalysis::addKillFlags(). 72f9dff0e0e4e8aa9fd99c5f069e431fe6de98c1c9Jakob Stoklund Olesen if (MO.isUse()) 73f9dff0e0e4e8aa9fd99c5f069e431fe6de98c1c9Jakob Stoklund Olesen MO.setIsKill(false); 744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (!MO.readsReg()) 754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen continue; 764e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // MI is reading Reg. We may have visited MI before if it happens to be 774e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // reading Reg multiple times. That is OK, extend() is idempotent. 784e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen const MachineInstr *MI = &*I; 794e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 804e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Find the SlotIndex being read. 814e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen SlotIndex Idx; 824e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->isPHI()) { 834e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(!MO.isDef() && "Cannot handle PHI def of partial register."); 844e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // PHI operands are paired: (Reg, PredMBB). 854e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Extend the live range to be live-out from PredMBB. 864e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB()); 874e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } else { 884e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // This is a normal instruction. 894e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getInstructionIndex(MI).getRegSlot(); 904e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Check for early-clobber redefs. 914e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen unsigned DefIdx; 924e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MO.isDef()) { 934e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MO.isEarlyClobber()) 944e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Idx.getRegSlot(true); 954e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) { 964e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // FIXME: This would be a lot easier if tied early-clobber uses also 974e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // had an early-clobber flag. 984e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->getOperand(DefIdx).isEarlyClobber()) 994e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Idx.getRegSlot(true); 1004e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 1014e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 102c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen extend(LI, Idx, Reg); 1034e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 1044e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen} 1054e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1064e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 107b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// Transfer information from the LiveIn vector to the live ranges. 108beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesenvoid LiveRangeCalc::updateLiveIns() { 109beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveRangeUpdater Updater; 110b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 111b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 112b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!I->DomNode) 113b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 114b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = I->DomNode->getBlock(); 115beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen assert(I->Value && "No live-in value found"); 116b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 117b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 118b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 119b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 120beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Value is killed inside this block. 121beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen End = I->Kill; 122b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 123beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // The value is live-through, update LiveOut as well. 124beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Defer the Domtree lookup until it is needed. 125b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Seen.test(MBB->getNumber())); 126beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0); 127b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 128beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen Updater.setDest(I->LI); 129beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen Updater.add(Start, End, I->Value); 130b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 131b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 132b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 133b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 134b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 135b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::extend(LiveInterval *LI, 136c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen SlotIndex Kill, 137c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen unsigned PhysReg) { 138b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(LI && "Missing live range"); 139b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Kill.isValid() && "Invalid SlotIndex"); 140b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 141b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 142b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 143ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot()); 144aa13482784d100a8f4aef20f5b647192754a1a1dLang Hames assert(KillMBB && "No MBB at Kill"); 145b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 146b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is there a def in the same MBB we can extend? 147ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) 148b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen return; 149b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 150b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Find the single reaching def, or determine if Kill is jointly dominated by 151b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // multiple values, and we may need to create even more phi-defs to preserve 152b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // VNInfo SSA form. Perform a search for all predecessor blocks where we 153b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // know the dominating VNInfo. 154beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen if (findReachingDefs(LI, KillMBB, Kill, PhysReg)) 155beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen return; 156b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 157b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // When there were multiple different values, we may need new PHIs. 158beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen calculateValues(); 159b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 160b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 161b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 162b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This function is called by a client after using the low-level API to add 163b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// live-out and live-in blocks. The unique value optimization is not 164b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// available, SplitEditor::transferValues handles that case directly anyway. 165631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::calculateValues() { 166b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 167b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 168631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen updateSSA(); 169beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen updateLiveIns(); 170b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 171b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 172b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 173beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesenbool LiveRangeCalc::findReachingDefs(LiveInterval *LI, 174beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen MachineBasicBlock *KillMBB, 175beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen SlotIndex Kill, 176beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen unsigned PhysReg) { 177beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen unsigned KillMBBNum = KillMBB->getNumber(); 178beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen 179beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Block numbers where LI should be live-in. 180beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen SmallVector<unsigned, 16> WorkList(1, KillMBBNum); 181b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 182b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Remember if we have seen more than one value. 183b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool UniqueVNI = true; 184b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *TheVNI = 0; 185b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 186b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Using Seen as a visited set, perform a BFS for all reaching defs. 187b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (unsigned i = 0; i != WorkList.size(); ++i) { 188beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); 189c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen 190c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen#ifndef NDEBUG 191c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen if (MBB->pred_empty()) { 192c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen MBB->getParent()->verify(); 193c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen llvm_unreachable("Use not jointly dominated by defs."); 194c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen } 195c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen 196c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && 197c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen !MBB->isLiveIn(PhysReg)) { 198c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen MBB->getParent()->verify(); 199c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen errs() << "The register needs to be live in to BB#" << MBB->getNumber() 200c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen << ", but is missing from the live-in list.\n"; 201c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen llvm_unreachable("Invalid global physical register"); 202c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen } 203c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen#endif 204c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen 205b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 206b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 207b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 208b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 209b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is this a known live-out block? 210b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Seen.test(Pred->getNumber())) { 211b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNInfo *VNI = LiveOut[Pred].first) { 212b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 213b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 214b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 215b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 216b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 217b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 218b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 219b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 220b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(Pred); 221b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 222b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // First time we see Pred. Try to determine the live-out value, but set 223b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // it as null if Pred is live-through with an unknown value. 224ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, End); 225b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen setLiveOutValue(Pred, VNI); 226b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNI) { 227b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 228b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 229b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 230b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 231b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 232b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 233b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No, we need a live-in value for Pred as well 234b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Pred != KillMBB) 235beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen WorkList.push_back(Pred->getNumber()); 236b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else 237b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Loopback to KillMBB, so value is really live through. 238b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Kill = SlotIndex(); 239b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 240b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 241b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 242b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 243b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 244beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but 245beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // neither require it. Skip the sorting overhead for small updates. 246beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen if (WorkList.size() > 4) 247beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen array_pod_sort(WorkList.begin(), WorkList.end()); 248beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen 249beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // If a unique reaching def was found, blit in the live ranges immediately. 250beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen if (UniqueVNI) { 251beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveRangeUpdater Updater(LI); 252beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen for (SmallVectorImpl<unsigned>::const_iterator 253beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { 254beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen SlotIndex Start, End; 255beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(*I); 256beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Trim the live range in KillMBB. 257beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen if (*I == KillMBBNum && Kill.isValid()) 258beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen End = Kill; 259beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen else 260beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveOut[MF->getBlockNumbered(*I)] = 261beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveOutPair(TheVNI, (MachineDomTreeNode *)0); 262beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen Updater.add(Start, End, TheVNI); 263beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen } 264beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen return true; 265beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen } 266beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen 267beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // Multiple values were found, so transfer the work list to the LiveIn array 268beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen // where UpdateSSA will use it as a work list. 269beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveIn.reserve(WorkList.size()); 270beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen for (SmallVectorImpl<unsigned>::const_iterator 271beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { 272beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen MachineBasicBlock *MBB = MF->getBlockNumbered(*I); 273beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen addLiveInBlock(LI, DomTree->getNode(MBB)); 274beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen if (MBB == KillMBB) 275beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveIn.back().Kill = Kill; 276beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen } 277b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 278beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen return false; 279b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 280b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 281b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 282b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This is essentially the same iterative algorithm that SSAUpdater uses, 283b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// except we already have a dominator tree, so we don't have to recompute it. 284631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::updateSSA() { 285b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 286b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 287b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 288b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Interate until convergence. 289b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned Changes; 290b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen do { 291b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Changes = 0; 292b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 293b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // when necessary. 294b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 295b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 296b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *Node = I->DomNode; 297b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Skip block if the live-in value has already been determined. 298b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Node) 299b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 300b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 301b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 302b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair IDomValue; 303b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 304b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 305b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 306b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 307b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 308b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be their 309b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // immediate dominator. Check if any of them have live-out values that are 310b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // properly dominated by IDom. If so, we need a phi-def here. 311b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!needPHI) { 312b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen IDomValue = LiveOut[IDom->getBlock()]; 313b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 314b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 315b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (IDomValue.first && !IDomValue.second) 316b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut[IDom->getBlock()].second = IDomValue.second = 317b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 318b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 319b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 320b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 321b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &Value = LiveOut[*PI]; 322b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 323b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 324b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 325b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 326b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.second) 327b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Value.second = 328b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 329b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 330b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 331b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 332b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 333b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (DomTree->dominates(IDom, Value.second)) { 334b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen needPHI = true; 335b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen break; 336b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 337b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 338b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 339b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 340b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The value may be live-through even if Kill is set, as can happen when 341b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // we are called from extendRange. In that case LiveOutSeen is true, and 342b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // LiveOut indicates a foreign or missing value. 343b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &LOP = LiveOut[MBB]; 344b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 345b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Create a phi-def if required. 346b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (needPHI) { 347b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 348b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 349b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 350b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 3513b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = I->LI->getNextValue(Start, *Alloc); 352b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = VNI; 353b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block is done, we know the final value. 354b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->DomNode = 0; 355b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 356b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Add liveness since updateLiveIns now skips this node. 357b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 358b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 359b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 360b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, End, VNI)); 361b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 362b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 363b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } else if (IDomValue.first) { 364b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No phi-def here. Remember incoming value. 365b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = IDomValue.first; 366b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 367b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // If the IDomValue is killed in the block, don't propagate through. 368b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 369b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 370b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 371b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate IDomValue if it isn't killed: 372b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 373b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (LOP.first == IDomValue.first) 374b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 375b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 376b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = IDomValue; 377b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 378b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 379b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } while (Changes); 380b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 381