LiveRangeCalc.cpp revision b18d779b35909cd5b753871f8bf2ff4f6c17ace1
1//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Implementation of the LiveRangeCalc class. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "regalloc" 15#include "LiveRangeCalc.h" 16#include "llvm/CodeGen/MachineDominators.h" 17#include "llvm/CodeGen/MachineRegisterInfo.h" 18 19using namespace llvm; 20 21void LiveRangeCalc::reset(const MachineFunction *MF, 22 SlotIndexes *SI, 23 MachineDominatorTree *MDT, 24 VNInfo::Allocator *VNIA) { 25 MRI = &MF->getRegInfo(); 26 Indexes = SI; 27 DomTree = MDT; 28 Alloc = VNIA; 29 30 unsigned N = MF->getNumBlockIDs(); 31 Seen.clear(); 32 Seen.resize(N); 33 LiveOut.resize(N); 34 LiveIn.clear(); 35} 36 37 38void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { 39 assert(MRI && Indexes && "call reset() first"); 40 41 // Visit all def operands. If the same instruction has multiple defs of Reg, 42 // LI->createDeadDef() will deduplicate. 43 for (MachineRegisterInfo::def_iterator 44 I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { 45 const MachineInstr *MI = &*I; 46 // Find the corresponding slot index. 47 SlotIndex Idx; 48 if (MI->isPHI()) 49 // PHI defs begin at the basic block start index. 50 Idx = Indexes->getMBBStartIdx(MI->getParent()); 51 else 52 // Instructions are either normal 'r', or early clobber 'e'. 53 Idx = Indexes->getInstructionIndex(MI) 54 .getRegSlot(I.getOperand().isEarlyClobber()); 55 56 // Create the def in LI. This may find an existing def. 57 LI->createDeadDef(Idx, *Alloc); 58 } 59} 60 61 62void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) { 63 assert(MRI && Indexes && "call reset() first"); 64 65 // Visit all operands that read Reg. This may include partial defs. 66 for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg), 67 E = MRI->reg_nodbg_end(); I != E; ++I) { 68 const MachineOperand &MO = I.getOperand(); 69 if (!MO.readsReg()) 70 continue; 71 // MI is reading Reg. We may have visited MI before if it happens to be 72 // reading Reg multiple times. That is OK, extend() is idempotent. 73 const MachineInstr *MI = &*I; 74 75 // Find the SlotIndex being read. 76 SlotIndex Idx; 77 if (MI->isPHI()) { 78 assert(!MO.isDef() && "Cannot handle PHI def of partial register."); 79 // PHI operands are paired: (Reg, PredMBB). 80 // Extend the live range to be live-out from PredMBB. 81 Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB()); 82 } else { 83 // This is a normal instruction. 84 Idx = Indexes->getInstructionIndex(MI).getRegSlot(); 85 // Check for early-clobber redefs. 86 unsigned DefIdx; 87 if (MO.isDef()) { 88 if (MO.isEarlyClobber()) 89 Idx = Idx.getRegSlot(true); 90 } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) { 91 // FIXME: This would be a lot easier if tied early-clobber uses also 92 // had an early-clobber flag. 93 if (MI->getOperand(DefIdx).isEarlyClobber()) 94 Idx = Idx.getRegSlot(true); 95 } 96 } 97 extend(LI, Idx, Reg); 98 } 99} 100 101 102// Transfer information from the LiveIn vector to the live ranges. 103void LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI) { 104 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 105 E = LiveIn.end(); I != E; ++I) { 106 if (!I->DomNode) 107 continue; 108 MachineBasicBlock *MBB = I->DomNode->getBlock(); 109 110 VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value; 111 assert(VNI && "No live-in value found"); 112 113 SlotIndex Start, End; 114 tie(Start, End) = Indexes->getMBBRange(MBB); 115 116 if (I->Kill.isValid()) 117 I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 118 else { 119 I->LI->addRange(LiveRange(Start, End, VNI)); 120 // The value is live-through, update LiveOut as well. Defer the Domtree 121 // lookup until it is needed. 122 assert(Seen.test(MBB->getNumber())); 123 LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0); 124 } 125 } 126 LiveIn.clear(); 127} 128 129 130void LiveRangeCalc::extend(LiveInterval *LI, 131 SlotIndex Kill, 132 unsigned PhysReg) { 133 assert(LI && "Missing live range"); 134 assert(Kill.isValid() && "Invalid SlotIndex"); 135 assert(Indexes && "Missing SlotIndexes"); 136 assert(DomTree && "Missing dominator tree"); 137 138 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot()); 139 assert(KillMBB && "No MBB at Kill"); 140 141 // Is there a def in the same MBB we can extend? 142 if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) 143 return; 144 145 // Find the single reaching def, or determine if Kill is jointly dominated by 146 // multiple values, and we may need to create even more phi-defs to preserve 147 // VNInfo SSA form. Perform a search for all predecessor blocks where we 148 // know the dominating VNInfo. 149 VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill, PhysReg); 150 151 // When there were multiple different values, we may need new PHIs. 152 if (!VNI) 153 updateSSA(); 154 155 updateLiveIns(VNI); 156} 157 158 159// This function is called by a client after using the low-level API to add 160// live-out and live-in blocks. The unique value optimization is not 161// available, SplitEditor::transferValues handles that case directly anyway. 162void LiveRangeCalc::calculateValues() { 163 assert(Indexes && "Missing SlotIndexes"); 164 assert(DomTree && "Missing dominator tree"); 165 updateSSA(); 166 updateLiveIns(0); 167} 168 169 170VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI, 171 MachineBasicBlock *KillMBB, 172 SlotIndex Kill, 173 unsigned PhysReg) { 174 // Blocks where LI should be live-in. 175 SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 176 177 // Remember if we have seen more than one value. 178 bool UniqueVNI = true; 179 VNInfo *TheVNI = 0; 180 181 // Using Seen as a visited set, perform a BFS for all reaching defs. 182 for (unsigned i = 0; i != WorkList.size(); ++i) { 183 MachineBasicBlock *MBB = WorkList[i]; 184 185#ifndef NDEBUG 186 if (MBB->pred_empty()) { 187 MBB->getParent()->verify(); 188 llvm_unreachable("Use not jointly dominated by defs."); 189 } 190 191 if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && 192 !MBB->isLiveIn(PhysReg)) { 193 MBB->getParent()->verify(); 194 errs() << "The register needs to be live in to BB#" << MBB->getNumber() 195 << ", but is missing from the live-in list.\n"; 196 llvm_unreachable("Invalid global physical register"); 197 } 198#endif 199 200 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 201 PE = MBB->pred_end(); PI != PE; ++PI) { 202 MachineBasicBlock *Pred = *PI; 203 204 // Is this a known live-out block? 205 if (Seen.test(Pred->getNumber())) { 206 if (VNInfo *VNI = LiveOut[Pred].first) { 207 if (TheVNI && TheVNI != VNI) 208 UniqueVNI = false; 209 TheVNI = VNI; 210 } 211 continue; 212 } 213 214 SlotIndex Start, End; 215 tie(Start, End) = Indexes->getMBBRange(Pred); 216 217 // First time we see Pred. Try to determine the live-out value, but set 218 // it as null if Pred is live-through with an unknown value. 219 VNInfo *VNI = LI->extendInBlock(Start, End); 220 setLiveOutValue(Pred, VNI); 221 if (VNI) { 222 if (TheVNI && TheVNI != VNI) 223 UniqueVNI = false; 224 TheVNI = VNI; 225 continue; 226 } 227 228 // No, we need a live-in value for Pred as well 229 if (Pred != KillMBB) 230 WorkList.push_back(Pred); 231 else 232 // Loopback to KillMBB, so value is really live through. 233 Kill = SlotIndex(); 234 } 235 } 236 237 // Transfer WorkList to LiveInBlocks in reverse order. 238 // This ordering works best with updateSSA(). 239 LiveIn.clear(); 240 LiveIn.reserve(WorkList.size()); 241 while(!WorkList.empty()) 242 addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val())); 243 244 // The kill block may not be live-through. 245 assert(LiveIn.back().DomNode->getBlock() == KillMBB); 246 LiveIn.back().Kill = Kill; 247 248 return UniqueVNI ? TheVNI : 0; 249} 250 251 252// This is essentially the same iterative algorithm that SSAUpdater uses, 253// except we already have a dominator tree, so we don't have to recompute it. 254void LiveRangeCalc::updateSSA() { 255 assert(Indexes && "Missing SlotIndexes"); 256 assert(DomTree && "Missing dominator tree"); 257 258 // Interate until convergence. 259 unsigned Changes; 260 do { 261 Changes = 0; 262 // Propagate live-out values down the dominator tree, inserting phi-defs 263 // when necessary. 264 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 265 E = LiveIn.end(); I != E; ++I) { 266 MachineDomTreeNode *Node = I->DomNode; 267 // Skip block if the live-in value has already been determined. 268 if (!Node) 269 continue; 270 MachineBasicBlock *MBB = Node->getBlock(); 271 MachineDomTreeNode *IDom = Node->getIDom(); 272 LiveOutPair IDomValue; 273 274 // We need a live-in value to a block with no immediate dominator? 275 // This is probably an unreachable block that has survived somehow. 276 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 277 278 // IDom dominates all of our predecessors, but it may not be their 279 // immediate dominator. Check if any of them have live-out values that are 280 // properly dominated by IDom. If so, we need a phi-def here. 281 if (!needPHI) { 282 IDomValue = LiveOut[IDom->getBlock()]; 283 284 // Cache the DomTree node that defined the value. 285 if (IDomValue.first && !IDomValue.second) 286 LiveOut[IDom->getBlock()].second = IDomValue.second = 287 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 288 289 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 290 PE = MBB->pred_end(); PI != PE; ++PI) { 291 LiveOutPair &Value = LiveOut[*PI]; 292 if (!Value.first || Value.first == IDomValue.first) 293 continue; 294 295 // Cache the DomTree node that defined the value. 296 if (!Value.second) 297 Value.second = 298 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 299 300 // This predecessor is carrying something other than IDomValue. 301 // It could be because IDomValue hasn't propagated yet, or it could be 302 // because MBB is in the dominance frontier of that value. 303 if (DomTree->dominates(IDom, Value.second)) { 304 needPHI = true; 305 break; 306 } 307 } 308 } 309 310 // The value may be live-through even if Kill is set, as can happen when 311 // we are called from extendRange. In that case LiveOutSeen is true, and 312 // LiveOut indicates a foreign or missing value. 313 LiveOutPair &LOP = LiveOut[MBB]; 314 315 // Create a phi-def if required. 316 if (needPHI) { 317 ++Changes; 318 assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 319 SlotIndex Start, End; 320 tie(Start, End) = Indexes->getMBBRange(MBB); 321 VNInfo *VNI = I->LI->getNextValue(Start, *Alloc); 322 I->Value = VNI; 323 // This block is done, we know the final value. 324 I->DomNode = 0; 325 326 // Add liveness since updateLiveIns now skips this node. 327 if (I->Kill.isValid()) 328 I->LI->addRange(LiveRange(Start, I->Kill, VNI)); 329 else { 330 I->LI->addRange(LiveRange(Start, End, VNI)); 331 LOP = LiveOutPair(VNI, Node); 332 } 333 } else if (IDomValue.first) { 334 // No phi-def here. Remember incoming value. 335 I->Value = IDomValue.first; 336 337 // If the IDomValue is killed in the block, don't propagate through. 338 if (I->Kill.isValid()) 339 continue; 340 341 // Propagate IDomValue if it isn't killed: 342 // MBB is live-out and doesn't define its own value. 343 if (LOP.first == IDomValue.first) 344 continue; 345 ++Changes; 346 LOP = IDomValue; 347 } 348 } 349 } while (Changes); 350} 351