LiveRangeCalc.cpp revision 3b1088a2cc15a39c7a7b8dd95a56143f1dda6863
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" 17b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 18b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenusing namespace llvm; 19b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 20b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::reset(const MachineFunction *MF) { 21b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned N = MF->getNumBlockIDs(); 22b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.clear(); 23b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.resize(N); 24b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut.resize(N); 25b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 26b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 27b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 28b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 29b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// Transfer information from the LiveIn vector to the live ranges. 30b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI, SlotIndexes *Indexes) { 31b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 32b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 33b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!I->DomNode) 34b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 35b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = I->DomNode->getBlock(); 36b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 37b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value; 38b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(VNI && "No live-in value found"); 39b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 40b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 41b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 42b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 43b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 44b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 45b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 46b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, End, VNI)); 47b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The value is live-through, update LiveOut as well. Defer the Domtree 48b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // lookup until it is needed. 49b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Seen.test(MBB->getNumber())); 50edd4f8ba4bed5b999c6a726b7991241cf1840350NAKAMURA Takumi LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0); 51b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 52b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 53b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 54b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 55b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 56b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 57b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::extend(LiveInterval *LI, 58b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Kill, 59b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndexes *Indexes, 60b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDominatorTree *DomTree, 61b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo::Allocator *Alloc) { 62b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(LI && "Missing live range"); 63b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Kill.isValid() && "Invalid SlotIndex"); 64b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 65b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 66b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 67ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot()); 68aa13482784d100a8f4aef20f5b647192754a1a1dLang Hames assert(KillMBB && "No MBB at Kill"); 69b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 70b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is there a def in the same MBB we can extend? 71ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) 72b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen return; 73b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 74b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Find the single reaching def, or determine if Kill is jointly dominated by 75b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // multiple values, and we may need to create even more phi-defs to preserve 76b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // VNInfo SSA form. Perform a search for all predecessor blocks where we 77b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // know the dominating VNInfo. 78b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill, Indexes, DomTree); 79b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 80b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // When there were multiple different values, we may need new PHIs. 81b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!VNI) 82b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen updateSSA(Indexes, DomTree, Alloc); 83b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 84b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen updateLiveIns(VNI, Indexes); 85b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 86b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 87b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 88b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This function is called by a client after using the low-level API to add 89b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// live-out and live-in blocks. The unique value optimization is not 90b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// available, SplitEditor::transferValues handles that case directly anyway. 91b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::calculateValues(SlotIndexes *Indexes, 92b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDominatorTree *DomTree, 93b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo::Allocator *Alloc) { 94b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 95b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 96b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen updateSSA(Indexes, DomTree, Alloc); 97b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen updateLiveIns(0, Indexes); 98b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 99b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 100b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 101b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund OlesenVNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI, 102b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *KillMBB, 103b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Kill, 104b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndexes *Indexes, 105b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDominatorTree *DomTree) { 106b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Blocks where LI should be live-in. 107b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 108b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 109b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Remember if we have seen more than one value. 110b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool UniqueVNI = true; 111b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *TheVNI = 0; 112b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 113b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Using Seen as a visited set, perform a BFS for all reaching defs. 114b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (unsigned i = 0; i != WorkList.size(); ++i) { 115b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = WorkList[i]; 116b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(!MBB->pred_empty() && "Value live-in to entry block?"); 117b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 118b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 119b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 120b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 121b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Is this a known live-out block? 122b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Seen.test(Pred->getNumber())) { 123b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNInfo *VNI = LiveOut[Pred].first) { 124b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 125b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 126b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 127b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 128b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 129b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 130b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 131b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 132b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(Pred); 133b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 134b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // First time we see Pred. Try to determine the live-out value, but set 135b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // it as null if Pred is live-through with an unknown value. 136ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, End); 137b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen setLiveOutValue(Pred, VNI); 138b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (VNI) { 139b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 140b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen UniqueVNI = false; 141b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen TheVNI = VNI; 142b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 143b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 144b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 145b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No, we need a live-in value for Pred as well 146b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (Pred != KillMBB) 147b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen WorkList.push_back(Pred); 148b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else 149b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Loopback to KillMBB, so value is really live through. 150b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Kill = SlotIndex(); 151b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 152b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 153b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 154b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Transfer WorkList to LiveInBlocks in reverse order. 155b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This ordering works best with updateSSA(). 156b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.clear(); 157b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.reserve(WorkList.size()); 158b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen while(!WorkList.empty()) 159b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val())); 160b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 161b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The kill block may not be live-through. 162b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(LiveIn.back().DomNode->getBlock() == KillMBB); 163b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.back().Kill = Kill; 164b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 165b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen return UniqueVNI ? TheVNI : 0; 166b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 167b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 168b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 169b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This is essentially the same iterative algorithm that SSAUpdater uses, 170b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// except we already have a dominator tree, so we don't have to recompute it. 171b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenvoid LiveRangeCalc::updateSSA(SlotIndexes *Indexes, 172b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDominatorTree *DomTree, 173b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo::Allocator *Alloc) { 174b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Indexes && "Missing SlotIndexes"); 175b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(DomTree && "Missing dominator tree"); 176b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 177b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Interate until convergence. 178b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen unsigned Changes; 179b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen do { 180b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Changes = 0; 181b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 182b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // when necessary. 183b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 184b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen E = LiveIn.end(); I != E; ++I) { 185b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *Node = I->DomNode; 186b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Skip block if the live-in value has already been determined. 187b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Node) 188b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 189b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 190b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 191b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair IDomValue; 192b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 193b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 194b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 195b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 196b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 197b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be their 198b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // immediate dominator. Check if any of them have live-out values that are 199b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // properly dominated by IDom. If so, we need a phi-def here. 200b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!needPHI) { 201b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen IDomValue = LiveOut[IDom->getBlock()]; 202b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 203b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 204b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (IDomValue.first && !IDomValue.second) 205b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOut[IDom->getBlock()].second = IDomValue.second = 206b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 207b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 208b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 209b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 210b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &Value = LiveOut[*PI]; 211b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 212b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 213b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 214b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cache the DomTree node that defined the value. 215b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (!Value.second) 216b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Value.second = 217b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 218b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 219b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 220b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 221b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 222b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (DomTree->dominates(IDom, Value.second)) { 223b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen needPHI = true; 224b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen break; 225b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 226b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 227b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 228b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 229b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // The value may be live-through even if Kill is set, as can happen when 230b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // we are called from extendRange. In that case LiveOutSeen is true, and 231b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // LiveOut indicates a foreign or missing value. 232b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutPair &LOP = LiveOut[MBB]; 233b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 234b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Create a phi-def if required. 235b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (needPHI) { 236b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 237b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 238b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Start, End; 239b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen tie(Start, End) = Indexes->getMBBRange(MBB); 2403b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = I->LI->getNextValue(Start, *Alloc); 241b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNI->setIsPHIDef(true); 242b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = VNI; 243b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block is done, we know the final value. 244b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->DomNode = 0; 245b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 246b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Add liveness since updateLiveIns now skips this node. 247b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 248b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 249b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen else { 250b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->LI->addRange(LiveRange(Start, End, VNI)); 251b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 252b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 253b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } else if (IDomValue.first) { 254b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // No phi-def here. Remember incoming value. 255b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen I->Value = IDomValue.first; 256b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 257b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // If the IDomValue is killed in the block, don't propagate through. 258b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (I->Kill.isValid()) 259b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 260b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 261b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Propagate IDomValue if it isn't killed: 262b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 263b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (LOP.first == IDomValue.first) 264b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen continue; 265b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen ++Changes; 266b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LOP = IDomValue; 267b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 268b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 269b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } while (Changes); 270b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} 271