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