LiveRangeCalc.cpp revision 288943
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#include "LiveRangeCalc.h" 15#include "llvm/CodeGen/MachineDominators.h" 16#include "llvm/CodeGen/MachineRegisterInfo.h" 17 18using namespace llvm; 19 20#define DEBUG_TYPE "regalloc" 21 22void LiveRangeCalc::resetLiveOutMap() { 23 unsigned NumBlocks = MF->getNumBlockIDs(); 24 Seen.clear(); 25 Seen.resize(NumBlocks); 26 Map.resize(NumBlocks); 27} 28 29void LiveRangeCalc::reset(const MachineFunction *mf, 30 SlotIndexes *SI, 31 MachineDominatorTree *MDT, 32 VNInfo::Allocator *VNIA) { 33 MF = mf; 34 MRI = &MF->getRegInfo(); 35 Indexes = SI; 36 DomTree = MDT; 37 Alloc = VNIA; 38 resetLiveOutMap(); 39 LiveIn.clear(); 40} 41 42 43static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, 44 LiveRange &LR, const MachineOperand &MO) { 45 const MachineInstr *MI = MO.getParent(); 46 SlotIndex DefIdx = 47 Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber()); 48 49 // Create the def in LR. This may find an existing def. 50 LR.createDeadDef(DefIdx, Alloc); 51} 52 53void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) { 54 assert(MRI && Indexes && "call reset() first"); 55 56 // Step 1: Create minimal live segments for every definition of Reg. 57 // Visit all def operands. If the same instruction has multiple defs of Reg, 58 // createDeadDef() will deduplicate. 59 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); 60 unsigned Reg = LI.reg; 61 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { 62 if (!MO.isDef() && !MO.readsReg()) 63 continue; 64 65 unsigned SubReg = MO.getSubReg(); 66 if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) { 67 unsigned Mask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg) 68 : MRI->getMaxLaneMaskForVReg(Reg); 69 70 // If this is the first time we see a subregister def, initialize 71 // subranges by creating a copy of the main range. 72 if (!LI.hasSubRanges() && !LI.empty()) { 73 unsigned ClassMask = MRI->getMaxLaneMaskForVReg(Reg); 74 LI.createSubRangeFrom(*Alloc, ClassMask, LI); 75 } 76 77 for (LiveInterval::SubRange &S : LI.subranges()) { 78 // A Mask for subregs common to the existing subrange and current def. 79 unsigned Common = S.LaneMask & Mask; 80 if (Common == 0) 81 continue; 82 // A Mask for subregs covered by the subrange but not the current def. 83 unsigned LRest = S.LaneMask & ~Mask; 84 LiveInterval::SubRange *CommonRange; 85 if (LRest != 0) { 86 // Split current subrange into Common and LRest ranges. 87 S.LaneMask = LRest; 88 CommonRange = LI.createSubRangeFrom(*Alloc, Common, S); 89 } else { 90 assert(Common == S.LaneMask); 91 CommonRange = &S; 92 } 93 if (MO.isDef()) 94 createDeadDef(*Indexes, *Alloc, *CommonRange, MO); 95 Mask &= ~Common; 96 } 97 // Create a new SubRange for subregs we did not cover yet. 98 if (Mask != 0) { 99 LiveInterval::SubRange *NewRange = LI.createSubRange(*Alloc, Mask); 100 if (MO.isDef()) 101 createDeadDef(*Indexes, *Alloc, *NewRange, MO); 102 } 103 } 104 105 // Create the def in the main liverange. We do not have to do this if 106 // subranges are tracked as we recreate the main range later in this case. 107 if (MO.isDef() && !LI.hasSubRanges()) 108 createDeadDef(*Indexes, *Alloc, LI, MO); 109 } 110 111 // We may have created empty live ranges for partially undefined uses, we 112 // can't keep them because we won't find defs in them later. 113 LI.removeEmptySubRanges(); 114 115 // Step 2: Extend live segments to all uses, constructing SSA form as 116 // necessary. 117 if (LI.hasSubRanges()) { 118 for (LiveInterval::SubRange &S : LI.subranges()) { 119 resetLiveOutMap(); 120 extendToUses(S, Reg, S.LaneMask); 121 } 122 LI.clear(); 123 LI.constructMainRangeFromSubranges(*Indexes, *Alloc); 124 } else { 125 resetLiveOutMap(); 126 extendToUses(LI, Reg, ~0u); 127 } 128} 129 130 131void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { 132 assert(MRI && Indexes && "call reset() first"); 133 134 // Visit all def operands. If the same instruction has multiple defs of Reg, 135 // LR.createDeadDef() will deduplicate. 136 for (MachineOperand &MO : MRI->def_operands(Reg)) 137 createDeadDef(*Indexes, *Alloc, LR, MO); 138} 139 140 141void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, unsigned Mask) { 142 // Visit all operands that read Reg. This may include partial defs. 143 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); 144 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { 145 // Clear all kill flags. They will be reinserted after register allocation 146 // by LiveIntervalAnalysis::addKillFlags(). 147 if (MO.isUse()) 148 MO.setIsKill(false); 149 else { 150 // We only care about uses, but on the main range (mask ~0u) this includes 151 // the "virtual" reads happening for subregister defs. 152 if (Mask != ~0u) 153 continue; 154 } 155 156 if (!MO.readsReg()) 157 continue; 158 unsigned SubReg = MO.getSubReg(); 159 if (SubReg != 0) { 160 unsigned SubRegMask = TRI.getSubRegIndexLaneMask(SubReg); 161 // Ignore uses not covering the current subrange. 162 if ((SubRegMask & Mask) == 0) 163 continue; 164 } 165 166 // Determine the actual place of the use. 167 const MachineInstr *MI = MO.getParent(); 168 unsigned OpNo = (&MO - &MI->getOperand(0)); 169 SlotIndex UseIdx; 170 if (MI->isPHI()) { 171 assert(!MO.isDef() && "Cannot handle PHI def of partial register."); 172 // The actual place where a phi operand is used is the end of the pred 173 // MBB. PHI operands are paired: (Reg, PredMBB). 174 UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB()); 175 } else { 176 // Check for early-clobber redefs. 177 bool isEarlyClobber = false; 178 unsigned DefIdx; 179 if (MO.isDef()) 180 isEarlyClobber = MO.isEarlyClobber(); 181 else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) { 182 // FIXME: This would be a lot easier if tied early-clobber uses also 183 // had an early-clobber flag. 184 isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber(); 185 } 186 UseIdx = Indexes->getInstructionIndex(MI).getRegSlot(isEarlyClobber); 187 } 188 189 // MI is reading Reg. We may have visited MI before if it happens to be 190 // reading Reg multiple times. That is OK, extend() is idempotent. 191 extend(LR, UseIdx, Reg); 192 } 193} 194 195 196void LiveRangeCalc::updateFromLiveIns() { 197 LiveRangeUpdater Updater; 198 for (const LiveInBlock &I : LiveIn) { 199 if (!I.DomNode) 200 continue; 201 MachineBasicBlock *MBB = I.DomNode->getBlock(); 202 assert(I.Value && "No live-in value found"); 203 SlotIndex Start, End; 204 std::tie(Start, End) = Indexes->getMBBRange(MBB); 205 206 if (I.Kill.isValid()) 207 // Value is killed inside this block. 208 End = I.Kill; 209 else { 210 // The value is live-through, update LiveOut as well. 211 // Defer the Domtree lookup until it is needed. 212 assert(Seen.test(MBB->getNumber())); 213 Map[MBB] = LiveOutPair(I.Value, nullptr); 214 } 215 Updater.setDest(&I.LR); 216 Updater.add(Start, End, I.Value); 217 } 218 LiveIn.clear(); 219} 220 221 222void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg) { 223 assert(Use.isValid() && "Invalid SlotIndex"); 224 assert(Indexes && "Missing SlotIndexes"); 225 assert(DomTree && "Missing dominator tree"); 226 227 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot()); 228 assert(UseMBB && "No MBB at Use"); 229 230 // Is there a def in the same MBB we can extend? 231 if (LR.extendInBlock(Indexes->getMBBStartIdx(UseMBB), Use)) 232 return; 233 234 // Find the single reaching def, or determine if Use is jointly dominated by 235 // multiple values, and we may need to create even more phi-defs to preserve 236 // VNInfo SSA form. Perform a search for all predecessor blocks where we 237 // know the dominating VNInfo. 238 if (findReachingDefs(LR, *UseMBB, Use, PhysReg)) 239 return; 240 241 // When there were multiple different values, we may need new PHIs. 242 calculateValues(); 243} 244 245 246// This function is called by a client after using the low-level API to add 247// live-out and live-in blocks. The unique value optimization is not 248// available, SplitEditor::transferValues handles that case directly anyway. 249void LiveRangeCalc::calculateValues() { 250 assert(Indexes && "Missing SlotIndexes"); 251 assert(DomTree && "Missing dominator tree"); 252 updateSSA(); 253 updateFromLiveIns(); 254} 255 256 257bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, 258 SlotIndex Use, unsigned PhysReg) { 259 unsigned UseMBBNum = UseMBB.getNumber(); 260 261 // Block numbers where LR should be live-in. 262 SmallVector<unsigned, 16> WorkList(1, UseMBBNum); 263 264 // Remember if we have seen more than one value. 265 bool UniqueVNI = true; 266 VNInfo *TheVNI = nullptr; 267 268 // Using Seen as a visited set, perform a BFS for all reaching defs. 269 for (unsigned i = 0; i != WorkList.size(); ++i) { 270 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); 271 272#ifndef NDEBUG 273 if (MBB->pred_empty()) { 274 MBB->getParent()->verify(); 275 errs() << "Use of " << PrintReg(PhysReg) 276 << " does not have a corresponding definition on every path:\n"; 277 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use); 278 if (MI != nullptr) 279 errs() << Use << " " << *MI; 280 llvm_unreachable("Use not jointly dominated by defs."); 281 } 282 283 if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && 284 !MBB->isLiveIn(PhysReg)) { 285 MBB->getParent()->verify(); 286 errs() << "The register " << PrintReg(PhysReg) 287 << " needs to be live in to BB#" << MBB->getNumber() 288 << ", but is missing from the live-in list.\n"; 289 llvm_unreachable("Invalid global physical register"); 290 } 291#endif 292 293 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 294 PE = MBB->pred_end(); PI != PE; ++PI) { 295 MachineBasicBlock *Pred = *PI; 296 297 // Is this a known live-out block? 298 if (Seen.test(Pred->getNumber())) { 299 if (VNInfo *VNI = Map[Pred].first) { 300 if (TheVNI && TheVNI != VNI) 301 UniqueVNI = false; 302 TheVNI = VNI; 303 } 304 continue; 305 } 306 307 SlotIndex Start, End; 308 std::tie(Start, End) = Indexes->getMBBRange(Pred); 309 310 // First time we see Pred. Try to determine the live-out value, but set 311 // it as null if Pred is live-through with an unknown value. 312 VNInfo *VNI = LR.extendInBlock(Start, End); 313 setLiveOutValue(Pred, VNI); 314 if (VNI) { 315 if (TheVNI && TheVNI != VNI) 316 UniqueVNI = false; 317 TheVNI = VNI; 318 continue; 319 } 320 321 // No, we need a live-in value for Pred as well 322 if (Pred != &UseMBB) 323 WorkList.push_back(Pred->getNumber()); 324 else 325 // Loopback to UseMBB, so value is really live through. 326 Use = SlotIndex(); 327 } 328 } 329 330 LiveIn.clear(); 331 332 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but 333 // neither require it. Skip the sorting overhead for small updates. 334 if (WorkList.size() > 4) 335 array_pod_sort(WorkList.begin(), WorkList.end()); 336 337 // If a unique reaching def was found, blit in the live ranges immediately. 338 if (UniqueVNI) { 339 LiveRangeUpdater Updater(&LR); 340 for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(), 341 E = WorkList.end(); I != E; ++I) { 342 SlotIndex Start, End; 343 std::tie(Start, End) = Indexes->getMBBRange(*I); 344 // Trim the live range in UseMBB. 345 if (*I == UseMBBNum && Use.isValid()) 346 End = Use; 347 else 348 Map[MF->getBlockNumbered(*I)] = LiveOutPair(TheVNI, nullptr); 349 Updater.add(Start, End, TheVNI); 350 } 351 return true; 352 } 353 354 // Multiple values were found, so transfer the work list to the LiveIn array 355 // where UpdateSSA will use it as a work list. 356 LiveIn.reserve(WorkList.size()); 357 for (SmallVectorImpl<unsigned>::const_iterator 358 I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { 359 MachineBasicBlock *MBB = MF->getBlockNumbered(*I); 360 addLiveInBlock(LR, DomTree->getNode(MBB)); 361 if (MBB == &UseMBB) 362 LiveIn.back().Kill = Use; 363 } 364 365 return false; 366} 367 368 369// This is essentially the same iterative algorithm that SSAUpdater uses, 370// except we already have a dominator tree, so we don't have to recompute it. 371void LiveRangeCalc::updateSSA() { 372 assert(Indexes && "Missing SlotIndexes"); 373 assert(DomTree && "Missing dominator tree"); 374 375 // Interate until convergence. 376 unsigned Changes; 377 do { 378 Changes = 0; 379 // Propagate live-out values down the dominator tree, inserting phi-defs 380 // when necessary. 381 for (LiveInBlock &I : LiveIn) { 382 MachineDomTreeNode *Node = I.DomNode; 383 // Skip block if the live-in value has already been determined. 384 if (!Node) 385 continue; 386 MachineBasicBlock *MBB = Node->getBlock(); 387 MachineDomTreeNode *IDom = Node->getIDom(); 388 LiveOutPair IDomValue; 389 390 // We need a live-in value to a block with no immediate dominator? 391 // This is probably an unreachable block that has survived somehow. 392 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 393 394 // IDom dominates all of our predecessors, but it may not be their 395 // immediate dominator. Check if any of them have live-out values that are 396 // properly dominated by IDom. If so, we need a phi-def here. 397 if (!needPHI) { 398 IDomValue = Map[IDom->getBlock()]; 399 400 // Cache the DomTree node that defined the value. 401 if (IDomValue.first && !IDomValue.second) 402 Map[IDom->getBlock()].second = IDomValue.second = 403 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 404 405 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 406 PE = MBB->pred_end(); PI != PE; ++PI) { 407 LiveOutPair &Value = Map[*PI]; 408 if (!Value.first || Value.first == IDomValue.first) 409 continue; 410 411 // Cache the DomTree node that defined the value. 412 if (!Value.second) 413 Value.second = 414 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 415 416 // This predecessor is carrying something other than IDomValue. 417 // It could be because IDomValue hasn't propagated yet, or it could be 418 // because MBB is in the dominance frontier of that value. 419 if (DomTree->dominates(IDom, Value.second)) { 420 needPHI = true; 421 break; 422 } 423 } 424 } 425 426 // The value may be live-through even if Kill is set, as can happen when 427 // we are called from extendRange. In that case LiveOutSeen is true, and 428 // LiveOut indicates a foreign or missing value. 429 LiveOutPair &LOP = Map[MBB]; 430 431 // Create a phi-def if required. 432 if (needPHI) { 433 ++Changes; 434 assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 435 SlotIndex Start, End; 436 std::tie(Start, End) = Indexes->getMBBRange(MBB); 437 LiveRange &LR = I.LR; 438 VNInfo *VNI = LR.getNextValue(Start, *Alloc); 439 I.Value = VNI; 440 // This block is done, we know the final value. 441 I.DomNode = nullptr; 442 443 // Add liveness since updateFromLiveIns now skips this node. 444 if (I.Kill.isValid()) 445 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); 446 else { 447 LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 448 LOP = LiveOutPair(VNI, Node); 449 } 450 } else if (IDomValue.first) { 451 // No phi-def here. Remember incoming value. 452 I.Value = IDomValue.first; 453 454 // If the IDomValue is killed in the block, don't propagate through. 455 if (I.Kill.isValid()) 456 continue; 457 458 // Propagate IDomValue if it isn't killed: 459 // MBB is live-out and doesn't define its own value. 460 if (LOP.first == IDomValue.first) 461 continue; 462 ++Changes; 463 LOP = IDomValue; 464 } 465 } 466 } while (Changes); 467} 468