LiveRangeCalc.cpp revision 4e53a40ea321c43bdf754147dd2ec064985e5b7b
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 21631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::reset(const MachineFunction *MF, 22631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndexes *SI, 23631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MachineDominatorTree *MDT, 24631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo::Allocator *VNIA) { 25631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 26631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen Indexes = SI; 27631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen DomTree = MDT; 28631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen Alloc = VNIA; 29631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen 30b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned N = MF->getNumBlockIDs(); 31b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.clear(); 32b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.resize(N); 33b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut.resize(N); 34b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 35b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 36b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 37b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 384e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesenvoid LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { 394e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(MRI && Indexes && "call reset() first"); 404e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 414e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Visit all def operands. If the same instruction has multiple defs of Reg, 424e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // LI->createDeadDef() will deduplicate. 434e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen for (MachineRegisterInfo::def_iterator 444e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { 454e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen const MachineInstr *MI = &*I; 464e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Find the corresponding slot index. 474e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen SlotIndex Idx; 484e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->isPHI()) 494e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // PHI defs begin at the basic block start index. 504e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getMBBStartIdx(MI->getParent()); 514e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen else 524e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Instructions are either normal 'r', or early clobber 'e'. 534e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getInstructionIndex(MI) 544e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen .getRegSlot(I.getOperand().isEarlyClobber()); 554e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 564e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Create the def in LI. This may find an existing def. 574e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *VNI = LI->createDeadDef(Idx, *Alloc); 584e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNI->setIsPHIDef(MI->isPHI()); 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) { 694e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen const MachineOperand &MO = I.getOperand(); 704e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (!MO.readsReg()) 714e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen continue; 724e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // MI is reading Reg. We may have visited MI before if it happens to be 734e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // reading Reg multiple times. That is OK, extend() is idempotent. 744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen const MachineInstr *MI = &*I; 754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 764e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Find the SlotIndex being read. 774e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen SlotIndex Idx; 784e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->isPHI()) { 794e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(!MO.isDef() && "Cannot handle PHI def of partial register."); 804e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // PHI operands are paired: (Reg, PredMBB). 814e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Extend the live range to be live-out from PredMBB. 824e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB()); 834e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } else { 844e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // This is a normal instruction. 854e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Indexes->getInstructionIndex(MI).getRegSlot(); 864e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // Check for early-clobber redefs. 874e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen unsigned DefIdx; 884e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MO.isDef()) { 894e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MO.isEarlyClobber()) 904e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Idx.getRegSlot(true); 914e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) { 924e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // FIXME: This would be a lot easier if tied early-clobber uses also 934e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen // had an early-clobber flag. 944e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (MI->getOperand(DefIdx).isEarlyClobber()) 954e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen Idx = Idx.getRegSlot(true); 964e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 974e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 984e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen extend(LI, Idx); 994e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 1004e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen} 1014e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1024e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 103b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// Transfer information from the LiveIn vector to the live ranges. 104631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI) { 105b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 106b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 107b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!I->DomNode) 108b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 109b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = I->DomNode->getBlock(); 110b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 111b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value; 112b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(VNI && "No live-in value found"); 113b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 114b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 115b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 116b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 117b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 118b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 119b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 120b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, End, VNI)); 121b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The value is live-through, update LiveOut as well. Defer the Domtree 122b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // lookup until it is needed. 123b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Seen.test(MBB->getNumber())); 124edd4f8ba4bed5b999c6a726b7991241cf1840350NAKAMURA Takumi LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0); 125b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 126b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 127b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 128b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 129b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 130b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 131b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::extend(LiveInterval *LI, 132631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndex Kill) { 133b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(LI && "Missing live range"); 134b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Kill.isValid() && "Invalid SlotIndex"); 135b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 136b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 137b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 138ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot()); 139aa13482784d100a8f4aef20f5b647192754a1a1dLang Hames assert(KillMBB && "No MBB at Kill"); 140b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 141b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is there a def in the same MBB we can extend? 142ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) 143b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen return; 144b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 145b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Find the single reaching def, or determine if Kill is jointly dominated by 146b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // multiple values, and we may need to create even more phi-defs to preserve 147b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // VNInfo SSA form. Perform a search for all predecessor blocks where we 148b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // know the dominating VNInfo. 149631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill); 150b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 151b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // When there were multiple different values, we may need new PHIs. 152b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!VNI) 153631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen updateSSA(); 154b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 155631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen updateLiveIns(VNI); 156b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 157b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 158b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 159b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This function is called by a client after using the low-level API to add 160b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// live-out and live-in blocks. The unique value optimization is not 161b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// available, SplitEditor::transferValues handles that case directly anyway. 162631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::calculateValues() { 163b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 164b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 165631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen updateSSA(); 166631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen updateLiveIns(0); 167b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 168b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 169b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 170b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund OlesenVNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI, 171b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *KillMBB, 172631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndex Kill) { 173b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Blocks where LI should be live-in. 174b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 175b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 176b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Remember if we have seen more than one value. 177b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool UniqueVNI = true; 178b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *TheVNI = 0; 179b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 180b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Using Seen as a visited set, perform a BFS for all reaching defs. 181b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (unsigned i = 0; i != WorkList.size(); ++i) { 182b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = WorkList[i]; 183b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(!MBB->pred_empty() && "Value live-in to entry block?"); 184b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 185b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 186b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 187b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 188b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is this a known live-out block? 189b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Seen.test(Pred->getNumber())) { 190b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNInfo *VNI = LiveOut[Pred].first) { 191b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 192b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 193b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 194b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 195b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 196b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 197b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 198b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 199b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(Pred); 200b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 201b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // First time we see Pred. Try to determine the live-out value, but set 202b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // it as null if Pred is live-through with an unknown value. 203ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, End); 204b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen setLiveOutValue(Pred, VNI); 205b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNI) { 206b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 207b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 208b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 209b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 210b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 211b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 212b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No, we need a live-in value for Pred as well 213b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Pred != KillMBB) 214b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen WorkList.push_back(Pred); 215b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else 216b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Loopback to KillMBB, so value is really live through. 217b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Kill = SlotIndex(); 218b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 219b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 220b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 221b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Transfer WorkList to LiveInBlocks in reverse order. 222b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This ordering works best with updateSSA(). 223b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 224b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.reserve(WorkList.size()); 225b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen while(!WorkList.empty()) 226b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val())); 227b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 228b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The kill block may not be live-through. 229b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(LiveIn.back().DomNode->getBlock() == KillMBB); 230b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.back().Kill = Kill; 231b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 232b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen return UniqueVNI ? TheVNI : 0; 233b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 234b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 235b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 236b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This is essentially the same iterative algorithm that SSAUpdater uses, 237b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// except we already have a dominator tree, so we don't have to recompute it. 238631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesenvoid LiveRangeCalc::updateSSA() { 239b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 240b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 241b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 242b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Interate until convergence. 243b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned Changes; 244b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen do { 245b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Changes = 0; 246b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 247b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // when necessary. 248b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 249b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 250b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *Node = I->DomNode; 251b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Skip block if the live-in value has already been determined. 252b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Node) 253b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 254b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 255b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 256b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair IDomValue; 257b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 258b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 259b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 260b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 261b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 262b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be their 263b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // immediate dominator. Check if any of them have live-out values that are 264b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // properly dominated by IDom. If so, we need a phi-def here. 265b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!needPHI) { 266b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen IDomValue = LiveOut[IDom->getBlock()]; 267b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 268b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 269b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (IDomValue.first && !IDomValue.second) 270b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut[IDom->getBlock()].second = IDomValue.second = 271b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 272b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 273b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 274b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 275b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &Value = LiveOut[*PI]; 276b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 277b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 278b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 279b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 280b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.second) 281b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Value.second = 282b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 283b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 284b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 285b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 286b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 287b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (DomTree->dominates(IDom, Value.second)) { 288b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen needPHI = true; 289b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen break; 290b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 291b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 292b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 293b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 294b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The value may be live-through even if Kill is set, as can happen when 295b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // we are called from extendRange. In that case LiveOutSeen is true, and 296b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // LiveOut indicates a foreign or missing value. 297b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &LOP = LiveOut[MBB]; 298b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 299b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Create a phi-def if required. 300b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (needPHI) { 301b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 302b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 303b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 304b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 3053b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = I->LI->getNextValue(Start, *Alloc); 306b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNI->setIsPHIDef(true); 307b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = VNI; 308b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block is done, we know the final value. 309b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->DomNode = 0; 310b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 311b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Add liveness since updateLiveIns now skips this node. 312b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 313b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 314b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 315b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, End, VNI)); 316b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 317b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 318b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } else if (IDomValue.first) { 319b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No phi-def here. Remember incoming value. 320b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = IDomValue.first; 321b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 322b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // If the IDomValue is killed in the block, don't propagate through. 323b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 324b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 325b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 326b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate IDomValue if it isn't killed: 327b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 328b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (LOP.first == IDomValue.first) 329b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 330b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 331b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = IDomValue; 332b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 333b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 334b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } while (Changes); 335b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 336