1 //===- LiveIntervals.cpp - Live Interval Analysis -------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file This file implements the LiveInterval analysis pass which is used 10 /// by the Linear Scan Register allocator. This pass linearizes the 11 /// basic blocks of the function in DFS order and computes live intervals for 12 /// each virtual and physical register. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/CodeGen/LiveIntervals.h" 17 #include "LiveRangeCalc.h" 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/DepthFirstIterator.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/iterator_range.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/CodeGen/LiveInterval.h" 25 #include "llvm/CodeGen/LiveVariables.h" 26 #include "llvm/CodeGen/MachineBasicBlock.h" 27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 28 #include "llvm/CodeGen/MachineDominators.h" 29 #include "llvm/CodeGen/MachineFunction.h" 30 #include "llvm/CodeGen/MachineInstr.h" 31 #include "llvm/CodeGen/MachineInstrBundle.h" 32 #include "llvm/CodeGen/MachineOperand.h" 33 #include "llvm/CodeGen/MachineRegisterInfo.h" 34 #include "llvm/CodeGen/Passes.h" 35 #include "llvm/CodeGen/SlotIndexes.h" 36 #include "llvm/CodeGen/TargetRegisterInfo.h" 37 #include "llvm/CodeGen/TargetSubtargetInfo.h" 38 #include "llvm/CodeGen/VirtRegMap.h" 39 #include "llvm/Config/llvm-config.h" 40 #include "llvm/MC/LaneBitmask.h" 41 #include "llvm/MC/MCRegisterInfo.h" 42 #include "llvm/Pass.h" 43 #include "llvm/Support/BlockFrequency.h" 44 #include "llvm/Support/CommandLine.h" 45 #include "llvm/Support/Compiler.h" 46 #include "llvm/Support/Debug.h" 47 #include "llvm/Support/MathExtras.h" 48 #include "llvm/Support/raw_ostream.h" 49 #include <algorithm> 50 #include <cassert> 51 #include <cstdint> 52 #include <iterator> 53 #include <tuple> 54 #include <utility> 55 56 using namespace llvm; 57 58 #define DEBUG_TYPE "regalloc" 59 60 char LiveIntervals::ID = 0; 61 char &llvm::LiveIntervalsID = LiveIntervals::ID; 62 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 63 "Live Interval Analysis", false, false) 64 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 65 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 67 INITIALIZE_PASS_END(LiveIntervals, "liveintervals", 68 "Live Interval Analysis", false, false) 69 70 #ifndef NDEBUG 71 static cl::opt<bool> EnablePrecomputePhysRegs( 72 "precompute-phys-liveness", cl::Hidden, 73 cl::desc("Eagerly compute live intervals for all physreg units.")); 74 #else 75 static bool EnablePrecomputePhysRegs = false; 76 #endif // NDEBUG 77 78 namespace llvm { 79 80 cl::opt<bool> UseSegmentSetForPhysRegs( 81 "use-segment-set-for-physregs", cl::Hidden, cl::init(true), 82 cl::desc( 83 "Use segment set for the computation of the live ranges of physregs.")); 84 85 } // end namespace llvm 86 87 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 88 AU.setPreservesCFG(); 89 AU.addRequired<AAResultsWrapperPass>(); 90 AU.addPreserved<AAResultsWrapperPass>(); 91 AU.addPreserved<LiveVariables>(); 92 AU.addPreservedID(MachineLoopInfoID); 93 AU.addRequiredTransitiveID(MachineDominatorsID); 94 AU.addPreservedID(MachineDominatorsID); 95 AU.addPreserved<SlotIndexes>(); 96 AU.addRequiredTransitive<SlotIndexes>(); 97 MachineFunctionPass::getAnalysisUsage(AU); 98 } 99 100 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) { 101 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 102 } 103 104 LiveIntervals::~LiveIntervals() { 105 delete LRCalc; 106 } 107 108 void LiveIntervals::releaseMemory() { 109 // Free the live intervals themselves. 110 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) 111 delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; 112 VirtRegIntervals.clear(); 113 RegMaskSlots.clear(); 114 RegMaskBits.clear(); 115 RegMaskBlocks.clear(); 116 117 for (LiveRange *LR : RegUnitRanges) 118 delete LR; 119 RegUnitRanges.clear(); 120 121 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 122 VNInfoAllocator.Reset(); 123 } 124 125 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 126 MF = &fn; 127 MRI = &MF->getRegInfo(); 128 TRI = MF->getSubtarget().getRegisterInfo(); 129 TII = MF->getSubtarget().getInstrInfo(); 130 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 131 Indexes = &getAnalysis<SlotIndexes>(); 132 DomTree = &getAnalysis<MachineDominatorTree>(); 133 134 if (!LRCalc) 135 LRCalc = new LiveRangeCalc(); 136 137 // Allocate space for all virtual registers. 138 VirtRegIntervals.resize(MRI->getNumVirtRegs()); 139 140 computeVirtRegs(); 141 computeRegMasks(); 142 computeLiveInRegUnits(); 143 144 if (EnablePrecomputePhysRegs) { 145 // For stress testing, precompute live ranges of all physical register 146 // units, including reserved registers. 147 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 148 getRegUnit(i); 149 } 150 LLVM_DEBUG(dump()); 151 return true; 152 } 153 154 void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 155 OS << "********** INTERVALS **********\n"; 156 157 // Dump the regunits. 158 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit) 159 if (LiveRange *LR = RegUnitRanges[Unit]) 160 OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n'; 161 162 // Dump the virtregs. 163 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 164 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 165 if (hasInterval(Reg)) 166 OS << getInterval(Reg) << '\n'; 167 } 168 169 OS << "RegMasks:"; 170 for (SlotIndex Idx : RegMaskSlots) 171 OS << ' ' << Idx; 172 OS << '\n'; 173 174 printInstrs(OS); 175 } 176 177 void LiveIntervals::printInstrs(raw_ostream &OS) const { 178 OS << "********** MACHINEINSTRS **********\n"; 179 MF->print(OS, Indexes); 180 } 181 182 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 183 LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const { 184 printInstrs(dbgs()); 185 } 186 #endif 187 188 LiveInterval* LiveIntervals::createInterval(unsigned reg) { 189 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F; 190 return new LiveInterval(reg, Weight); 191 } 192 193 /// Compute the live interval of a virtual register, based on defs and uses. 194 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { 195 assert(LRCalc && "LRCalc not initialized."); 196 assert(LI.empty() && "Should only compute empty intervals."); 197 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 198 LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); 199 computeDeadValues(LI, nullptr); 200 } 201 202 void LiveIntervals::computeVirtRegs() { 203 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 204 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 205 if (MRI->reg_nodbg_empty(Reg)) 206 continue; 207 createAndComputeVirtRegInterval(Reg); 208 } 209 } 210 211 void LiveIntervals::computeRegMasks() { 212 RegMaskBlocks.resize(MF->getNumBlockIDs()); 213 214 // Find all instructions with regmask operands. 215 for (const MachineBasicBlock &MBB : *MF) { 216 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()]; 217 RMB.first = RegMaskSlots.size(); 218 219 // Some block starts, such as EH funclets, create masks. 220 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { 221 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); 222 RegMaskBits.push_back(Mask); 223 } 224 225 for (const MachineInstr &MI : MBB) { 226 for (const MachineOperand &MO : MI.operands()) { 227 if (!MO.isRegMask()) 228 continue; 229 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); 230 RegMaskBits.push_back(MO.getRegMask()); 231 } 232 } 233 234 // Some block ends, such as funclet returns, create masks. Put the mask on 235 // the last instruction of the block, because MBB slot index intervals are 236 // half-open. 237 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { 238 assert(!MBB.empty() && "empty return block?"); 239 RegMaskSlots.push_back( 240 Indexes->getInstructionIndex(MBB.back()).getRegSlot()); 241 RegMaskBits.push_back(Mask); 242 } 243 244 // Compute the number of register mask instructions in this block. 245 RMB.second = RegMaskSlots.size() - RMB.first; 246 } 247 } 248 249 //===----------------------------------------------------------------------===// 250 // Register Unit Liveness 251 //===----------------------------------------------------------------------===// 252 // 253 // Fixed interference typically comes from ABI boundaries: Function arguments 254 // and return values are passed in fixed registers, and so are exception 255 // pointers entering landing pads. Certain instructions require values to be 256 // present in specific registers. That is also represented through fixed 257 // interference. 258 // 259 260 /// Compute the live range of a register unit, based on the uses and defs of 261 /// aliasing registers. The range should be empty, or contain only dead 262 /// phi-defs from ABI blocks. 263 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { 264 assert(LRCalc && "LRCalc not initialized."); 265 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 266 267 // The physregs aliasing Unit are the roots and their super-registers. 268 // Create all values as dead defs before extending to uses. Note that roots 269 // may share super-registers. That's OK because createDeadDefs() is 270 // idempotent. It is very rare for a register unit to have multiple roots, so 271 // uniquing super-registers is probably not worthwhile. 272 bool IsReserved = false; 273 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { 274 bool IsRootReserved = true; 275 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); 276 Super.isValid(); ++Super) { 277 unsigned Reg = *Super; 278 if (!MRI->reg_empty(Reg)) 279 LRCalc->createDeadDefs(LR, Reg); 280 // A register unit is considered reserved if all its roots and all their 281 // super registers are reserved. 282 if (!MRI->isReserved(Reg)) 283 IsRootReserved = false; 284 } 285 IsReserved |= IsRootReserved; 286 } 287 assert(IsReserved == MRI->isReservedRegUnit(Unit) && 288 "reserved computation mismatch"); 289 290 // Now extend LR to reach all uses. 291 // Ignore uses of reserved registers. We only track defs of those. 292 if (!IsReserved) { 293 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { 294 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); 295 Super.isValid(); ++Super) { 296 unsigned Reg = *Super; 297 if (!MRI->reg_empty(Reg)) 298 LRCalc->extendToUses(LR, Reg); 299 } 300 } 301 } 302 303 // Flush the segment set to the segment vector. 304 if (UseSegmentSetForPhysRegs) 305 LR.flushSegmentSet(); 306 } 307 308 /// Precompute the live ranges of any register units that are live-in to an ABI 309 /// block somewhere. Register values can appear without a corresponding def when 310 /// entering the entry block or a landing pad. 311 void LiveIntervals::computeLiveInRegUnits() { 312 RegUnitRanges.resize(TRI->getNumRegUnits()); 313 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); 314 315 // Keep track of the live range sets allocated. 316 SmallVector<unsigned, 8> NewRanges; 317 318 // Check all basic blocks for live-ins. 319 for (const MachineBasicBlock &MBB : *MF) { 320 // We only care about ABI blocks: Entry + landing pads. 321 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty()) 322 continue; 323 324 // Create phi-defs at Begin for all live-in registers. 325 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB); 326 LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB)); 327 for (const auto &LI : MBB.liveins()) { 328 for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { 329 unsigned Unit = *Units; 330 LiveRange *LR = RegUnitRanges[Unit]; 331 if (!LR) { 332 // Use segment set to speed-up initial computation of the live range. 333 LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); 334 NewRanges.push_back(Unit); 335 } 336 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); 337 (void)VNI; 338 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id); 339 } 340 } 341 LLVM_DEBUG(dbgs() << '\n'); 342 } 343 LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); 344 345 // Compute the 'normal' part of the ranges. 346 for (unsigned Unit : NewRanges) 347 computeRegUnitRange(*RegUnitRanges[Unit], Unit); 348 } 349 350 static void createSegmentsForValues(LiveRange &LR, 351 iterator_range<LiveInterval::vni_iterator> VNIs) { 352 for (VNInfo *VNI : VNIs) { 353 if (VNI->isUnused()) 354 continue; 355 SlotIndex Def = VNI->def; 356 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); 357 } 358 } 359 360 void LiveIntervals::extendSegmentsToUses(LiveRange &Segments, 361 ShrinkToUsesWorkList &WorkList, 362 unsigned Reg, LaneBitmask LaneMask) { 363 // Keep track of the PHIs that are in use. 364 SmallPtrSet<VNInfo*, 8> UsedPHIs; 365 // Blocks that have already been added to WorkList as live-out. 366 SmallPtrSet<const MachineBasicBlock*, 16> LiveOut; 367 368 auto getSubRange = [](const LiveInterval &I, LaneBitmask M) 369 -> const LiveRange& { 370 if (M.none()) 371 return I; 372 for (const LiveInterval::SubRange &SR : I.subranges()) { 373 if ((SR.LaneMask & M).any()) { 374 assert(SR.LaneMask == M && "Expecting lane masks to match exactly"); 375 return SR; 376 } 377 } 378 llvm_unreachable("Subrange for mask not found"); 379 }; 380 381 const LiveInterval &LI = getInterval(Reg); 382 const LiveRange &OldRange = getSubRange(LI, LaneMask); 383 384 // Extend intervals to reach all uses in WorkList. 385 while (!WorkList.empty()) { 386 SlotIndex Idx = WorkList.back().first; 387 VNInfo *VNI = WorkList.back().second; 388 WorkList.pop_back(); 389 const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot()); 390 SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB); 391 392 // Extend the live range for VNI to be live at Idx. 393 if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) { 394 assert(ExtVNI == VNI && "Unexpected existing value number"); 395 (void)ExtVNI; 396 // Is this a PHIDef we haven't seen before? 397 if (!VNI->isPHIDef() || VNI->def != BlockStart || 398 !UsedPHIs.insert(VNI).second) 399 continue; 400 // The PHI is live, make sure the predecessors are live-out. 401 for (const MachineBasicBlock *Pred : MBB->predecessors()) { 402 if (!LiveOut.insert(Pred).second) 403 continue; 404 SlotIndex Stop = Indexes->getMBBEndIdx(Pred); 405 // A predecessor is not required to have a live-out value for a PHI. 406 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) 407 WorkList.push_back(std::make_pair(Stop, PVNI)); 408 } 409 continue; 410 } 411 412 // VNI is live-in to MBB. 413 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 414 Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); 415 416 // Make sure VNI is live-out from the predecessors. 417 for (const MachineBasicBlock *Pred : MBB->predecessors()) { 418 if (!LiveOut.insert(Pred).second) 419 continue; 420 SlotIndex Stop = Indexes->getMBBEndIdx(Pred); 421 if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) { 422 assert(OldVNI == VNI && "Wrong value out of predecessor"); 423 (void)OldVNI; 424 WorkList.push_back(std::make_pair(Stop, VNI)); 425 } else { 426 #ifndef NDEBUG 427 // There was no old VNI. Verify that Stop is jointly dominated 428 // by <undef>s for this live range. 429 assert(LaneMask.any() && 430 "Missing value out of predecessor for main range"); 431 SmallVector<SlotIndex,8> Undefs; 432 LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes); 433 assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) && 434 "Missing value out of predecessor for subrange"); 435 #endif 436 } 437 } 438 } 439 } 440 441 bool LiveIntervals::shrinkToUses(LiveInterval *li, 442 SmallVectorImpl<MachineInstr*> *dead) { 443 LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n'); 444 assert(TargetRegisterInfo::isVirtualRegister(li->reg) 445 && "Can only shrink virtual registers"); 446 447 // Shrink subregister live ranges. 448 bool NeedsCleanup = false; 449 for (LiveInterval::SubRange &S : li->subranges()) { 450 shrinkToUses(S, li->reg); 451 if (S.empty()) 452 NeedsCleanup = true; 453 } 454 if (NeedsCleanup) 455 li->removeEmptySubRanges(); 456 457 // Find all the values used, including PHI kills. 458 ShrinkToUsesWorkList WorkList; 459 460 // Visit all instructions reading li->reg. 461 unsigned Reg = li->reg; 462 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) { 463 if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg)) 464 continue; 465 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 466 LiveQueryResult LRQ = li->Query(Idx); 467 VNInfo *VNI = LRQ.valueIn(); 468 if (!VNI) { 469 // This shouldn't happen: readsVirtualRegister returns true, but there is 470 // no live value. It is likely caused by a target getting <undef> flags 471 // wrong. 472 LLVM_DEBUG( 473 dbgs() << Idx << '\t' << UseMI 474 << "Warning: Instr claims to read non-existent value in " 475 << *li << '\n'); 476 continue; 477 } 478 // Special case: An early-clobber tied operand reads and writes the 479 // register one slot early. 480 if (VNInfo *DefVNI = LRQ.valueDefined()) 481 Idx = DefVNI->def; 482 483 WorkList.push_back(std::make_pair(Idx, VNI)); 484 } 485 486 // Create new live ranges with only minimal live segments per def. 487 LiveRange NewLR; 488 createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); 489 extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone()); 490 491 // Move the trimmed segments back. 492 li->segments.swap(NewLR.segments); 493 494 // Handle dead values. 495 bool CanSeparate = computeDeadValues(*li, dead); 496 LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 497 return CanSeparate; 498 } 499 500 bool LiveIntervals::computeDeadValues(LiveInterval &LI, 501 SmallVectorImpl<MachineInstr*> *dead) { 502 bool MayHaveSplitComponents = false; 503 for (VNInfo *VNI : LI.valnos) { 504 if (VNI->isUnused()) 505 continue; 506 SlotIndex Def = VNI->def; 507 LiveRange::iterator I = LI.FindSegmentContaining(Def); 508 assert(I != LI.end() && "Missing segment for VNI"); 509 510 // Is the register live before? Otherwise we may have to add a read-undef 511 // flag for subregister defs. 512 unsigned VReg = LI.reg; 513 if (MRI->shouldTrackSubRegLiveness(VReg)) { 514 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { 515 MachineInstr *MI = getInstructionFromIndex(Def); 516 MI->setRegisterDefReadUndef(VReg); 517 } 518 } 519 520 if (I->end != Def.getDeadSlot()) 521 continue; 522 if (VNI->isPHIDef()) { 523 // This is a dead PHI. Remove it. 524 VNI->markUnused(); 525 LI.removeSegment(I); 526 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); 527 MayHaveSplitComponents = true; 528 } else { 529 // This is a dead def. Make sure the instruction knows. 530 MachineInstr *MI = getInstructionFromIndex(Def); 531 assert(MI && "No instruction defining live value"); 532 MI->addRegisterDead(LI.reg, TRI); 533 if (dead && MI->allDefsAreDead()) { 534 LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); 535 dead->push_back(MI); 536 } 537 } 538 } 539 return MayHaveSplitComponents; 540 } 541 542 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { 543 LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n'); 544 assert(TargetRegisterInfo::isVirtualRegister(Reg) 545 && "Can only shrink virtual registers"); 546 // Find all the values used, including PHI kills. 547 ShrinkToUsesWorkList WorkList; 548 549 // Visit all instructions reading Reg. 550 SlotIndex LastIdx; 551 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 552 // Skip "undef" uses. 553 if (!MO.readsReg()) 554 continue; 555 // Maybe the operand is for a subregister we don't care about. 556 unsigned SubReg = MO.getSubReg(); 557 if (SubReg != 0) { 558 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); 559 if ((LaneMask & SR.LaneMask).none()) 560 continue; 561 } 562 // We only need to visit each instruction once. 563 MachineInstr *UseMI = MO.getParent(); 564 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); 565 if (Idx == LastIdx) 566 continue; 567 LastIdx = Idx; 568 569 LiveQueryResult LRQ = SR.Query(Idx); 570 VNInfo *VNI = LRQ.valueIn(); 571 // For Subranges it is possible that only undef values are left in that 572 // part of the subregister, so there is no real liverange at the use 573 if (!VNI) 574 continue; 575 576 // Special case: An early-clobber tied operand reads and writes the 577 // register one slot early. 578 if (VNInfo *DefVNI = LRQ.valueDefined()) 579 Idx = DefVNI->def; 580 581 WorkList.push_back(std::make_pair(Idx, VNI)); 582 } 583 584 // Create a new live ranges with only minimal live segments per def. 585 LiveRange NewLR; 586 createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); 587 extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask); 588 589 // Move the trimmed ranges back. 590 SR.segments.swap(NewLR.segments); 591 592 // Remove dead PHI value numbers 593 for (VNInfo *VNI : SR.valnos) { 594 if (VNI->isUnused()) 595 continue; 596 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); 597 assert(Segment != nullptr && "Missing segment for VNI"); 598 if (Segment->end != VNI->def.getDeadSlot()) 599 continue; 600 if (VNI->isPHIDef()) { 601 // This is a dead PHI. Remove it. 602 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def 603 << " may separate interval\n"); 604 VNI->markUnused(); 605 SR.removeSegment(*Segment); 606 } 607 } 608 609 LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n'); 610 } 611 612 void LiveIntervals::extendToIndices(LiveRange &LR, 613 ArrayRef<SlotIndex> Indices, 614 ArrayRef<SlotIndex> Undefs) { 615 assert(LRCalc && "LRCalc not initialized."); 616 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 617 for (SlotIndex Idx : Indices) 618 LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); 619 } 620 621 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, 622 SmallVectorImpl<SlotIndex> *EndPoints) { 623 LiveQueryResult LRQ = LR.Query(Kill); 624 VNInfo *VNI = LRQ.valueOutOrDead(); 625 if (!VNI) 626 return; 627 628 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); 629 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); 630 631 // If VNI isn't live out from KillMBB, the value is trivially pruned. 632 if (LRQ.endPoint() < MBBEnd) { 633 LR.removeSegment(Kill, LRQ.endPoint()); 634 if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 635 return; 636 } 637 638 // VNI is live out of KillMBB. 639 LR.removeSegment(Kill, MBBEnd); 640 if (EndPoints) EndPoints->push_back(MBBEnd); 641 642 // Find all blocks that are reachable from KillMBB without leaving VNI's live 643 // range. It is possible that KillMBB itself is reachable, so start a DFS 644 // from each successor. 645 using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>; 646 VisitedTy Visited; 647 for (MachineBasicBlock *Succ : KillMBB->successors()) { 648 for (df_ext_iterator<MachineBasicBlock*, VisitedTy> 649 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited); 650 I != E;) { 651 MachineBasicBlock *MBB = *I; 652 653 // Check if VNI is live in to MBB. 654 SlotIndex MBBStart, MBBEnd; 655 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); 656 LiveQueryResult LRQ = LR.Query(MBBStart); 657 if (LRQ.valueIn() != VNI) { 658 // This block isn't part of the VNI segment. Prune the search. 659 I.skipChildren(); 660 continue; 661 } 662 663 // Prune the search if VNI is killed in MBB. 664 if (LRQ.endPoint() < MBBEnd) { 665 LR.removeSegment(MBBStart, LRQ.endPoint()); 666 if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 667 I.skipChildren(); 668 continue; 669 } 670 671 // VNI is live through MBB. 672 LR.removeSegment(MBBStart, MBBEnd); 673 if (EndPoints) EndPoints->push_back(MBBEnd); 674 ++I; 675 } 676 } 677 } 678 679 //===----------------------------------------------------------------------===// 680 // Register allocator hooks. 681 // 682 683 void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 684 // Keep track of regunit ranges. 685 SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU; 686 // Keep track of subregister ranges. 687 SmallVector<std::pair<const LiveInterval::SubRange*, 688 LiveRange::const_iterator>, 4> SRs; 689 690 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 691 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 692 if (MRI->reg_nodbg_empty(Reg)) 693 continue; 694 const LiveInterval &LI = getInterval(Reg); 695 if (LI.empty()) 696 continue; 697 698 // Find the regunit intervals for the assigned register. They may overlap 699 // the virtual register live range, cancelling any kills. 700 RU.clear(); 701 for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid(); 702 ++Unit) { 703 const LiveRange &RURange = getRegUnit(*Unit); 704 if (RURange.empty()) 705 continue; 706 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); 707 } 708 709 if (MRI->subRegLivenessEnabled()) { 710 SRs.clear(); 711 for (const LiveInterval::SubRange &SR : LI.subranges()) { 712 SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); 713 } 714 } 715 716 // Every instruction that kills Reg corresponds to a segment range end 717 // point. 718 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; 719 ++RI) { 720 // A block index indicates an MBB edge. 721 if (RI->end.isBlock()) 722 continue; 723 MachineInstr *MI = getInstructionFromIndex(RI->end); 724 if (!MI) 725 continue; 726 727 // Check if any of the regunits are live beyond the end of RI. That could 728 // happen when a physreg is defined as a copy of a virtreg: 729 // 730 // %eax = COPY %5 731 // FOO %5 <--- MI, cancel kill because %eax is live. 732 // BAR killed %eax 733 // 734 // There should be no kill flag on FOO when %5 is rewritten as %eax. 735 for (auto &RUP : RU) { 736 const LiveRange &RURange = *RUP.first; 737 LiveRange::const_iterator &I = RUP.second; 738 if (I == RURange.end()) 739 continue; 740 I = RURange.advanceTo(I, RI->end); 741 if (I == RURange.end() || I->start >= RI->end) 742 continue; 743 // I is overlapping RI. 744 goto CancelKill; 745 } 746 747 if (MRI->subRegLivenessEnabled()) { 748 // When reading a partial undefined value we must not add a kill flag. 749 // The regalloc might have used the undef lane for something else. 750 // Example: 751 // %1 = ... ; R32: %1 752 // %2:high16 = ... ; R64: %2 753 // = read killed %2 ; R64: %2 754 // = read %1 ; R32: %1 755 // The <kill> flag is correct for %2, but the register allocator may 756 // assign R0L to %1, and R0 to %2 because the low 32bits of R0 757 // are actually never written by %2. After assignment the <kill> 758 // flag at the read instruction is invalid. 759 LaneBitmask DefinedLanesMask; 760 if (!SRs.empty()) { 761 // Compute a mask of lanes that are defined. 762 DefinedLanesMask = LaneBitmask::getNone(); 763 for (auto &SRP : SRs) { 764 const LiveInterval::SubRange &SR = *SRP.first; 765 LiveRange::const_iterator &I = SRP.second; 766 if (I == SR.end()) 767 continue; 768 I = SR.advanceTo(I, RI->end); 769 if (I == SR.end() || I->start >= RI->end) 770 continue; 771 // I is overlapping RI 772 DefinedLanesMask |= SR.LaneMask; 773 } 774 } else 775 DefinedLanesMask = LaneBitmask::getAll(); 776 777 bool IsFullWrite = false; 778 for (const MachineOperand &MO : MI->operands()) { 779 if (!MO.isReg() || MO.getReg() != Reg) 780 continue; 781 if (MO.isUse()) { 782 // Reading any undefined lanes? 783 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); 784 if ((UseMask & ~DefinedLanesMask).any()) 785 goto CancelKill; 786 } else if (MO.getSubReg() == 0) { 787 // Writing to the full register? 788 assert(MO.isDef()); 789 IsFullWrite = true; 790 } 791 } 792 793 // If an instruction writes to a subregister, a new segment starts in 794 // the LiveInterval. But as this is only overriding part of the register 795 // adding kill-flags is not correct here after registers have been 796 // assigned. 797 if (!IsFullWrite) { 798 // Next segment has to be adjacent in the subregister write case. 799 LiveRange::const_iterator N = std::next(RI); 800 if (N != LI.end() && N->start == RI->end) 801 goto CancelKill; 802 } 803 } 804 805 MI->addRegisterKilled(Reg, nullptr); 806 continue; 807 CancelKill: 808 MI->clearRegisterKills(Reg, nullptr); 809 } 810 } 811 } 812 813 MachineBasicBlock* 814 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 815 // A local live range must be fully contained inside the block, meaning it is 816 // defined and killed at instructions, not at block boundaries. It is not 817 // live in or out of any block. 818 // 819 // It is technically possible to have a PHI-defined live range identical to a 820 // single block, but we are going to return false in that case. 821 822 SlotIndex Start = LI.beginIndex(); 823 if (Start.isBlock()) 824 return nullptr; 825 826 SlotIndex Stop = LI.endIndex(); 827 if (Stop.isBlock()) 828 return nullptr; 829 830 // getMBBFromIndex doesn't need to search the MBB table when both indexes 831 // belong to proper instructions. 832 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); 833 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); 834 return MBB1 == MBB2 ? MBB1 : nullptr; 835 } 836 837 bool 838 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { 839 for (const VNInfo *PHI : LI.valnos) { 840 if (PHI->isUnused() || !PHI->isPHIDef()) 841 continue; 842 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 843 // Conservatively return true instead of scanning huge predecessor lists. 844 if (PHIMBB->pred_size() > 100) 845 return true; 846 for (const MachineBasicBlock *Pred : PHIMBB->predecessors()) 847 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred))) 848 return true; 849 } 850 return false; 851 } 852 853 float LiveIntervals::getSpillWeight(bool isDef, bool isUse, 854 const MachineBlockFrequencyInfo *MBFI, 855 const MachineInstr &MI) { 856 return getSpillWeight(isDef, isUse, MBFI, MI.getParent()); 857 } 858 859 float LiveIntervals::getSpillWeight(bool isDef, bool isUse, 860 const MachineBlockFrequencyInfo *MBFI, 861 const MachineBasicBlock *MBB) { 862 BlockFrequency Freq = MBFI->getBlockFreq(MBB); 863 const float Scale = 1.0f / MBFI->getEntryFreq(); 864 return (isDef + isUse) * (Freq.getFrequency() * Scale); 865 } 866 867 LiveRange::Segment 868 LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) { 869 LiveInterval& Interval = createEmptyInterval(reg); 870 VNInfo *VN = Interval.getNextValue( 871 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 872 getVNInfoAllocator()); 873 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()), 874 getMBBEndIdx(startInst.getParent()), VN); 875 Interval.addSegment(S); 876 877 return S; 878 } 879 880 //===----------------------------------------------------------------------===// 881 // Register mask functions 882 //===----------------------------------------------------------------------===// 883 884 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 885 BitVector &UsableRegs) { 886 if (LI.empty()) 887 return false; 888 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 889 890 // Use a smaller arrays for local live ranges. 891 ArrayRef<SlotIndex> Slots; 892 ArrayRef<const uint32_t*> Bits; 893 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 894 Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 895 Bits = getRegMaskBitsInBlock(MBB->getNumber()); 896 } else { 897 Slots = getRegMaskSlots(); 898 Bits = getRegMaskBits(); 899 } 900 901 // We are going to enumerate all the register mask slots contained in LI. 902 // Start with a binary search of RegMaskSlots to find a starting point. 903 ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start); 904 ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 905 906 // No slots in range, LI begins after the last call. 907 if (SlotI == SlotE) 908 return false; 909 910 bool Found = false; 911 while (true) { 912 assert(*SlotI >= LiveI->start); 913 // Loop over all slots overlapping this segment. 914 while (*SlotI < LiveI->end) { 915 // *SlotI overlaps LI. Collect mask bits. 916 if (!Found) { 917 // This is the first overlap. Initialize UsableRegs to all ones. 918 UsableRegs.clear(); 919 UsableRegs.resize(TRI->getNumRegs(), true); 920 Found = true; 921 } 922 // Remove usable registers clobbered by this mask. 923 UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 924 if (++SlotI == SlotE) 925 return Found; 926 } 927 // *SlotI is beyond the current LI segment. 928 LiveI = LI.advanceTo(LiveI, *SlotI); 929 if (LiveI == LiveE) 930 return Found; 931 // Advance SlotI until it overlaps. 932 while (*SlotI < LiveI->start) 933 if (++SlotI == SlotE) 934 return Found; 935 } 936 } 937 938 //===----------------------------------------------------------------------===// 939 // IntervalUpdate class. 940 //===----------------------------------------------------------------------===// 941 942 /// Toolkit used by handleMove to trim or extend live intervals. 943 class LiveIntervals::HMEditor { 944 private: 945 LiveIntervals& LIS; 946 const MachineRegisterInfo& MRI; 947 const TargetRegisterInfo& TRI; 948 SlotIndex OldIdx; 949 SlotIndex NewIdx; 950 SmallPtrSet<LiveRange*, 8> Updated; 951 bool UpdateFlags; 952 953 public: 954 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 955 const TargetRegisterInfo& TRI, 956 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) 957 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), 958 UpdateFlags(UpdateFlags) {} 959 960 // FIXME: UpdateFlags is a workaround that creates live intervals for all 961 // physregs, even those that aren't needed for regalloc, in order to update 962 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 963 // flags, and postRA passes will use a live register utility instead. 964 LiveRange *getRegUnitLI(unsigned Unit) { 965 if (UpdateFlags && !MRI.isReservedRegUnit(Unit)) 966 return &LIS.getRegUnit(Unit); 967 return LIS.getCachedRegUnit(Unit); 968 } 969 970 /// Update all live ranges touched by MI, assuming a move from OldIdx to 971 /// NewIdx. 972 void updateAllRanges(MachineInstr *MI) { 973 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " 974 << *MI); 975 bool hasRegMask = false; 976 for (MachineOperand &MO : MI->operands()) { 977 if (MO.isRegMask()) 978 hasRegMask = true; 979 if (!MO.isReg()) 980 continue; 981 if (MO.isUse()) { 982 if (!MO.readsReg()) 983 continue; 984 // Aggressively clear all kill flags. 985 // They are reinserted by VirtRegRewriter. 986 MO.setIsKill(false); 987 } 988 989 unsigned Reg = MO.getReg(); 990 if (!Reg) 991 continue; 992 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 993 LiveInterval &LI = LIS.getInterval(Reg); 994 if (LI.hasSubRanges()) { 995 unsigned SubReg = MO.getSubReg(); 996 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg) 997 : MRI.getMaxLaneMaskForVReg(Reg); 998 for (LiveInterval::SubRange &S : LI.subranges()) { 999 if ((S.LaneMask & LaneMask).none()) 1000 continue; 1001 updateRange(S, Reg, S.LaneMask); 1002 } 1003 } 1004 updateRange(LI, Reg, LaneBitmask::getNone()); 1005 continue; 1006 } 1007 1008 // For physregs, only update the regunits that actually have a 1009 // precomputed live range. 1010 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 1011 if (LiveRange *LR = getRegUnitLI(*Units)) 1012 updateRange(*LR, *Units, LaneBitmask::getNone()); 1013 } 1014 if (hasRegMask) 1015 updateRegMaskSlots(); 1016 } 1017 1018 private: 1019 /// Update a single live range, assuming an instruction has been moved from 1020 /// OldIdx to NewIdx. 1021 void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { 1022 if (!Updated.insert(&LR).second) 1023 return; 1024 LLVM_DEBUG({ 1025 dbgs() << " "; 1026 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1027 dbgs() << printReg(Reg); 1028 if (LaneMask.any()) 1029 dbgs() << " L" << PrintLaneMask(LaneMask); 1030 } else { 1031 dbgs() << printRegUnit(Reg, &TRI); 1032 } 1033 dbgs() << ":\t" << LR << '\n'; 1034 }); 1035 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) 1036 handleMoveDown(LR); 1037 else 1038 handleMoveUp(LR, Reg, LaneMask); 1039 LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n'); 1040 LR.verify(); 1041 } 1042 1043 /// Update LR to reflect an instruction has been moved downwards from OldIdx 1044 /// to NewIdx (OldIdx < NewIdx). 1045 void handleMoveDown(LiveRange &LR) { 1046 LiveRange::iterator E = LR.end(); 1047 // Segment going into OldIdx. 1048 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); 1049 1050 // No value live before or after OldIdx? Nothing to do. 1051 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) 1052 return; 1053 1054 LiveRange::iterator OldIdxOut; 1055 // Do we have a value live-in to OldIdx? 1056 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { 1057 // If the live-in value already extends to NewIdx, there is nothing to do. 1058 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end)) 1059 return; 1060 // Aggressively remove all kill flags from the old kill point. 1061 // Kill flags shouldn't be used while live intervals exist, they will be 1062 // reinserted by VirtRegRewriter. 1063 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end)) 1064 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO) 1065 if (MO->isReg() && MO->isUse()) 1066 MO->setIsKill(false); 1067 1068 // Is there a def before NewIdx which is not OldIdx? 1069 LiveRange::iterator Next = std::next(OldIdxIn); 1070 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) && 1071 SlotIndex::isEarlierInstr(Next->start, NewIdx)) { 1072 // If we are here then OldIdx was just a use but not a def. We only have 1073 // to ensure liveness extends to NewIdx. 1074 LiveRange::iterator NewIdxIn = 1075 LR.advanceTo(Next, NewIdx.getBaseIndex()); 1076 // Extend the segment before NewIdx if necessary. 1077 if (NewIdxIn == E || 1078 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) { 1079 LiveRange::iterator Prev = std::prev(NewIdxIn); 1080 Prev->end = NewIdx.getRegSlot(); 1081 } 1082 // Extend OldIdxIn. 1083 OldIdxIn->end = Next->start; 1084 return; 1085 } 1086 1087 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR 1088 // invalid by overlapping ranges. 1089 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); 1090 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()); 1091 // If this was not a kill, then there was no def and we're done. 1092 if (!isKill) 1093 return; 1094 1095 // Did we have a Def at OldIdx? 1096 OldIdxOut = Next; 1097 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) 1098 return; 1099 } else { 1100 OldIdxOut = OldIdxIn; 1101 } 1102 1103 // If we are here then there is a Definition at OldIdx. OldIdxOut points 1104 // to the segment starting there. 1105 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && 1106 "No def?"); 1107 VNInfo *OldIdxVNI = OldIdxOut->valno; 1108 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); 1109 1110 // If the defined value extends beyond NewIdx, just move the beginning 1111 // of the segment to NewIdx. 1112 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); 1113 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) { 1114 OldIdxVNI->def = NewIdxDef; 1115 OldIdxOut->start = OldIdxVNI->def; 1116 return; 1117 } 1118 1119 // If we are here then we have a Definition at OldIdx which ends before 1120 // NewIdx. 1121 1122 // Is there an existing Def at NewIdx? 1123 LiveRange::iterator AfterNewIdx 1124 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot()); 1125 bool OldIdxDefIsDead = OldIdxOut->end.isDead(); 1126 if (!OldIdxDefIsDead && 1127 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) { 1128 // OldIdx is not a dead def, and NewIdxDef is inside a new interval. 1129 VNInfo *DefVNI; 1130 if (OldIdxOut != LR.begin() && 1131 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end, 1132 OldIdxOut->start)) { 1133 // There is no gap between OldIdxOut and its predecessor anymore, 1134 // merge them. 1135 LiveRange::iterator IPrev = std::prev(OldIdxOut); 1136 DefVNI = OldIdxVNI; 1137 IPrev->end = OldIdxOut->end; 1138 } else { 1139 // The value is live in to OldIdx 1140 LiveRange::iterator INext = std::next(OldIdxOut); 1141 assert(INext != E && "Must have following segment"); 1142 // We merge OldIdxOut and its successor. As we're dealing with subreg 1143 // reordering, there is always a successor to OldIdxOut in the same BB 1144 // We don't need INext->valno anymore and will reuse for the new segment 1145 // we create later. 1146 DefVNI = OldIdxVNI; 1147 INext->start = OldIdxOut->end; 1148 INext->valno->def = INext->start; 1149 } 1150 // If NewIdx is behind the last segment, extend that and append a new one. 1151 if (AfterNewIdx == E) { 1152 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up 1153 // one position. 1154 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end 1155 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end 1156 std::copy(std::next(OldIdxOut), E, OldIdxOut); 1157 // The last segment is undefined now, reuse it for a dead def. 1158 LiveRange::iterator NewSegment = std::prev(E); 1159 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), 1160 DefVNI); 1161 DefVNI->def = NewIdxDef; 1162 1163 LiveRange::iterator Prev = std::prev(NewSegment); 1164 Prev->end = NewIdxDef; 1165 } else { 1166 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up 1167 // one position. 1168 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -| 1169 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -| 1170 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut); 1171 LiveRange::iterator Prev = std::prev(AfterNewIdx); 1172 // We have two cases: 1173 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) { 1174 // Case 1: NewIdx is inside a liverange. Split this liverange at 1175 // NewIdxDef into the segment "Prev" followed by "NewSegment". 1176 LiveRange::iterator NewSegment = AfterNewIdx; 1177 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno); 1178 Prev->valno->def = NewIdxDef; 1179 1180 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI); 1181 DefVNI->def = Prev->start; 1182 } else { 1183 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and 1184 // turn Prev into a segment from NewIdx to AfterNewIdx->start. 1185 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI); 1186 DefVNI->def = NewIdxDef; 1187 assert(DefVNI != AfterNewIdx->valno); 1188 } 1189 } 1190 return; 1191 } 1192 1193 if (AfterNewIdx != E && 1194 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) { 1195 // There is an existing def at NewIdx. The def at OldIdx is coalesced into 1196 // that value. 1197 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?"); 1198 LR.removeValNo(OldIdxVNI); 1199 } else { 1200 // There was no existing def at NewIdx. We need to create a dead def 1201 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees 1202 // a new segment at the place where we want to construct the dead def. 1203 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -| 1204 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -| 1205 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators"); 1206 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut); 1207 // We can reuse OldIdxVNI now. 1208 LiveRange::iterator NewSegment = std::prev(AfterNewIdx); 1209 VNInfo *NewSegmentVNI = OldIdxVNI; 1210 NewSegmentVNI->def = NewIdxDef; 1211 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), 1212 NewSegmentVNI); 1213 } 1214 } 1215 1216 /// Update LR to reflect an instruction has been moved upwards from OldIdx 1217 /// to NewIdx (NewIdx < OldIdx). 1218 void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { 1219 LiveRange::iterator E = LR.end(); 1220 // Segment going into OldIdx. 1221 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); 1222 1223 // No value live before or after OldIdx? Nothing to do. 1224 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) 1225 return; 1226 1227 LiveRange::iterator OldIdxOut; 1228 // Do we have a value live-in to OldIdx? 1229 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { 1230 // If the live-in value isn't killed here, then we have no Def at 1231 // OldIdx, moreover the value must be live at NewIdx so there is nothing 1232 // to do. 1233 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); 1234 if (!isKill) 1235 return; 1236 1237 // At this point we have to move OldIdxIn->end back to the nearest 1238 // previous use or (dead-)def but no further than NewIdx. 1239 SlotIndex DefBeforeOldIdx 1240 = std::max(OldIdxIn->start.getDeadSlot(), 1241 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber())); 1242 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask); 1243 1244 // Did we have a Def at OldIdx? If not we are done now. 1245 OldIdxOut = std::next(OldIdxIn); 1246 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) 1247 return; 1248 } else { 1249 OldIdxOut = OldIdxIn; 1250 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E; 1251 } 1252 1253 // If we are here then there is a Definition at OldIdx. OldIdxOut points 1254 // to the segment starting there. 1255 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && 1256 "No def?"); 1257 VNInfo *OldIdxVNI = OldIdxOut->valno; 1258 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); 1259 bool OldIdxDefIsDead = OldIdxOut->end.isDead(); 1260 1261 // Is there an existing def at NewIdx? 1262 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); 1263 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot()); 1264 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) { 1265 assert(NewIdxOut->valno != OldIdxVNI && 1266 "Same value defined more than once?"); 1267 // If OldIdx was a dead def remove it. 1268 if (!OldIdxDefIsDead) { 1269 // Remove segment starting at NewIdx and move begin of OldIdxOut to 1270 // NewIdx so it can take its place. 1271 OldIdxVNI->def = NewIdxDef; 1272 OldIdxOut->start = NewIdxDef; 1273 LR.removeValNo(NewIdxOut->valno); 1274 } else { 1275 // Simply remove the dead def at OldIdx. 1276 LR.removeValNo(OldIdxVNI); 1277 } 1278 } else { 1279 // Previously nothing was live after NewIdx, so all we have to do now is 1280 // move the begin of OldIdxOut to NewIdx. 1281 if (!OldIdxDefIsDead) { 1282 // Do we have any intermediate Defs between OldIdx and NewIdx? 1283 if (OldIdxIn != E && 1284 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) { 1285 // OldIdx is not a dead def and NewIdx is before predecessor start. 1286 LiveRange::iterator NewIdxIn = NewIdxOut; 1287 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); 1288 const SlotIndex SplitPos = NewIdxDef; 1289 OldIdxVNI = OldIdxIn->valno; 1290 1291 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. 1292 OldIdxOut->valno->def = OldIdxIn->start; 1293 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, 1294 OldIdxOut->valno); 1295 // OldIdxIn and OldIdxVNI are now undef and can be overridden. 1296 // We Slide [NewIdxIn, OldIdxIn) down one position. 1297 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| 1298 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| 1299 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); 1300 // NewIdxIn is now considered undef so we can reuse it for the moved 1301 // value. 1302 LiveRange::iterator NewSegment = NewIdxIn; 1303 LiveRange::iterator Next = std::next(NewSegment); 1304 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) { 1305 // There is no gap between NewSegment and its predecessor. 1306 *NewSegment = LiveRange::Segment(Next->start, SplitPos, 1307 Next->valno); 1308 *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI); 1309 Next->valno->def = SplitPos; 1310 } else { 1311 // There is a gap between NewSegment and its predecessor 1312 // Value becomes live in. 1313 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI); 1314 NewSegment->valno->def = SplitPos; 1315 } 1316 } else { 1317 // Leave the end point of a live def. 1318 OldIdxOut->start = NewIdxDef; 1319 OldIdxVNI->def = NewIdxDef; 1320 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)) 1321 OldIdxIn->end = NewIdx.getRegSlot(); 1322 } 1323 } else if (OldIdxIn != E 1324 && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx) 1325 && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) { 1326 // OldIdxVNI is a dead def that has been moved into the middle of 1327 // another value in LR. That can happen when LR is a whole register, 1328 // but the dead def is a write to a subreg that is dead at NewIdx. 1329 // The dead def may have been moved across other values 1330 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) 1331 // down one position. 1332 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | 1333 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| 1334 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); 1335 // Modify the segment at NewIdxOut and the following segment to meet at 1336 // the point of the dead def, with the following segment getting 1337 // OldIdxVNI as its value number. 1338 *NewIdxOut = LiveRange::Segment( 1339 NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno); 1340 *(NewIdxOut + 1) = LiveRange::Segment( 1341 NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI); 1342 OldIdxVNI->def = NewIdxDef; 1343 // Modify subsequent segments to be defined by the moved def OldIdxVNI. 1344 for (auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx) 1345 Idx->valno = OldIdxVNI; 1346 // Aggressively remove all dead flags from the former dead definition. 1347 // Kill/dead flags shouldn't be used while live intervals exist; they 1348 // will be reinserted by VirtRegRewriter. 1349 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx)) 1350 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO) 1351 if (MO->isReg() && !MO->isUse()) 1352 MO->setIsDead(false); 1353 } else { 1354 // OldIdxVNI is a dead def. It may have been moved across other values 1355 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) 1356 // down one position. 1357 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | 1358 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| 1359 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); 1360 // OldIdxVNI can be reused now to build a new dead def segment. 1361 LiveRange::iterator NewSegment = NewIdxOut; 1362 VNInfo *NewSegmentVNI = OldIdxVNI; 1363 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), 1364 NewSegmentVNI); 1365 NewSegmentVNI->def = NewIdxDef; 1366 } 1367 } 1368 } 1369 1370 void updateRegMaskSlots() { 1371 SmallVectorImpl<SlotIndex>::iterator RI = 1372 llvm::lower_bound(LIS.RegMaskSlots, OldIdx); 1373 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && 1374 "No RegMask at OldIdx."); 1375 *RI = NewIdx.getRegSlot(); 1376 assert((RI == LIS.RegMaskSlots.begin() || 1377 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && 1378 "Cannot move regmask instruction above another call"); 1379 assert((std::next(RI) == LIS.RegMaskSlots.end() || 1380 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && 1381 "Cannot move regmask instruction below another call"); 1382 } 1383 1384 // Return the last use of reg between NewIdx and OldIdx. 1385 SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg, 1386 LaneBitmask LaneMask) { 1387 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1388 SlotIndex LastUse = Before; 1389 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { 1390 if (MO.isUndef()) 1391 continue; 1392 unsigned SubReg = MO.getSubReg(); 1393 if (SubReg != 0 && LaneMask.any() 1394 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none()) 1395 continue; 1396 1397 const MachineInstr &MI = *MO.getParent(); 1398 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 1399 if (InstSlot > LastUse && InstSlot < OldIdx) 1400 LastUse = InstSlot.getRegSlot(); 1401 } 1402 return LastUse; 1403 } 1404 1405 // This is a regunit interval, so scanning the use list could be very 1406 // expensive. Scan upwards from OldIdx instead. 1407 assert(Before < OldIdx && "Expected upwards move"); 1408 SlotIndexes *Indexes = LIS.getSlotIndexes(); 1409 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before); 1410 1411 // OldIdx may not correspond to an instruction any longer, so set MII to 1412 // point to the next instruction after OldIdx, or MBB->end(). 1413 MachineBasicBlock::iterator MII = MBB->end(); 1414 if (MachineInstr *MI = Indexes->getInstructionFromIndex( 1415 Indexes->getNextNonNullIndex(OldIdx))) 1416 if (MI->getParent() == MBB) 1417 MII = MI; 1418 1419 MachineBasicBlock::iterator Begin = MBB->begin(); 1420 while (MII != Begin) { 1421 if ((--MII)->isDebugInstr()) 1422 continue; 1423 SlotIndex Idx = Indexes->getInstructionIndex(*MII); 1424 1425 // Stop searching when Before is reached. 1426 if (!SlotIndex::isEarlierInstr(Before, Idx)) 1427 return Before; 1428 1429 // Check if MII uses Reg. 1430 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO) 1431 if (MO->isReg() && !MO->isUndef() && 1432 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && 1433 TRI.hasRegUnit(MO->getReg(), Reg)) 1434 return Idx.getRegSlot(); 1435 } 1436 // Didn't reach Before. It must be the first instruction in the block. 1437 return Before; 1438 } 1439 }; 1440 1441 void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) { 1442 assert(!MI.isBundled() && "Can't handle bundled instructions yet."); 1443 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1444 Indexes->removeMachineInstrFromMaps(MI); 1445 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); 1446 assert(getMBBStartIdx(MI.getParent()) <= OldIndex && 1447 OldIndex < getMBBEndIdx(MI.getParent()) && 1448 "Cannot handle moves across basic block boundaries."); 1449 1450 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1451 HME.updateAllRanges(&MI); 1452 } 1453 1454 void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI, 1455 MachineInstr &BundleStart, 1456 bool UpdateFlags) { 1457 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1458 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); 1459 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1460 HME.updateAllRanges(&MI); 1461 } 1462 1463 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, 1464 const MachineBasicBlock::iterator End, 1465 const SlotIndex endIdx, 1466 LiveRange &LR, const unsigned Reg, 1467 LaneBitmask LaneMask) { 1468 LiveInterval::iterator LII = LR.find(endIdx); 1469 SlotIndex lastUseIdx; 1470 if (LII == LR.begin()) { 1471 // This happens when the function is called for a subregister that only 1472 // occurs _after_ the range that is to be repaired. 1473 return; 1474 } 1475 if (LII != LR.end() && LII->start < endIdx) 1476 lastUseIdx = LII->end; 1477 else 1478 --LII; 1479 1480 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1481 --I; 1482 MachineInstr &MI = *I; 1483 if (MI.isDebugInstr()) 1484 continue; 1485 1486 SlotIndex instrIdx = getInstructionIndex(MI); 1487 bool isStartValid = getInstructionFromIndex(LII->start); 1488 bool isEndValid = getInstructionFromIndex(LII->end); 1489 1490 // FIXME: This doesn't currently handle early-clobber or multiple removed 1491 // defs inside of the region to repair. 1492 for (MachineInstr::mop_iterator OI = MI.operands_begin(), 1493 OE = MI.operands_end(); 1494 OI != OE; ++OI) { 1495 const MachineOperand &MO = *OI; 1496 if (!MO.isReg() || MO.getReg() != Reg) 1497 continue; 1498 1499 unsigned SubReg = MO.getSubReg(); 1500 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); 1501 if ((Mask & LaneMask).none()) 1502 continue; 1503 1504 if (MO.isDef()) { 1505 if (!isStartValid) { 1506 if (LII->end.isDead()) { 1507 SlotIndex prevStart; 1508 if (LII != LR.begin()) 1509 prevStart = std::prev(LII)->start; 1510 1511 // FIXME: This could be more efficient if there was a 1512 // removeSegment method that returned an iterator. 1513 LR.removeSegment(*LII, true); 1514 if (prevStart.isValid()) 1515 LII = LR.find(prevStart); 1516 else 1517 LII = LR.begin(); 1518 } else { 1519 LII->start = instrIdx.getRegSlot(); 1520 LII->valno->def = instrIdx.getRegSlot(); 1521 if (MO.getSubReg() && !MO.isUndef()) 1522 lastUseIdx = instrIdx.getRegSlot(); 1523 else 1524 lastUseIdx = SlotIndex(); 1525 continue; 1526 } 1527 } 1528 1529 if (!lastUseIdx.isValid()) { 1530 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); 1531 LiveRange::Segment S(instrIdx.getRegSlot(), 1532 instrIdx.getDeadSlot(), VNI); 1533 LII = LR.addSegment(S); 1534 } else if (LII->start != instrIdx.getRegSlot()) { 1535 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); 1536 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); 1537 LII = LR.addSegment(S); 1538 } 1539 1540 if (MO.getSubReg() && !MO.isUndef()) 1541 lastUseIdx = instrIdx.getRegSlot(); 1542 else 1543 lastUseIdx = SlotIndex(); 1544 } else if (MO.isUse()) { 1545 // FIXME: This should probably be handled outside of this branch, 1546 // either as part of the def case (for defs inside of the region) or 1547 // after the loop over the region. 1548 if (!isEndValid && !LII->end.isBlock()) 1549 LII->end = instrIdx.getRegSlot(); 1550 if (!lastUseIdx.isValid()) 1551 lastUseIdx = instrIdx.getRegSlot(); 1552 } 1553 } 1554 } 1555 } 1556 1557 void 1558 LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 1559 MachineBasicBlock::iterator Begin, 1560 MachineBasicBlock::iterator End, 1561 ArrayRef<unsigned> OrigRegs) { 1562 // Find anchor points, which are at the beginning/end of blocks or at 1563 // instructions that already have indexes. 1564 while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin)) 1565 --Begin; 1566 while (End != MBB->end() && !Indexes->hasIndex(*End)) 1567 ++End; 1568 1569 SlotIndex endIdx; 1570 if (End == MBB->end()) 1571 endIdx = getMBBEndIdx(MBB).getPrevSlot(); 1572 else 1573 endIdx = getInstructionIndex(*End); 1574 1575 Indexes->repairIndexesInRange(MBB, Begin, End); 1576 1577 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1578 --I; 1579 MachineInstr &MI = *I; 1580 if (MI.isDebugInstr()) 1581 continue; 1582 for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), 1583 MOE = MI.operands_end(); 1584 MOI != MOE; ++MOI) { 1585 if (MOI->isReg() && 1586 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && 1587 !hasInterval(MOI->getReg())) { 1588 createAndComputeVirtRegInterval(MOI->getReg()); 1589 } 1590 } 1591 } 1592 1593 for (unsigned Reg : OrigRegs) { 1594 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1595 continue; 1596 1597 LiveInterval &LI = getInterval(Reg); 1598 // FIXME: Should we support undefs that gain defs? 1599 if (!LI.hasAtLeastOneValue()) 1600 continue; 1601 1602 for (LiveInterval::SubRange &S : LI.subranges()) 1603 repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); 1604 1605 repairOldRegInRange(Begin, End, endIdx, LI, Reg); 1606 } 1607 } 1608 1609 void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { 1610 for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { 1611 if (LiveRange *LR = getCachedRegUnit(*Unit)) 1612 if (VNInfo *VNI = LR->getVNInfoAt(Pos)) 1613 LR->removeValNo(VNI); 1614 } 1615 } 1616 1617 void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { 1618 // LI may not have the main range computed yet, but its subranges may 1619 // be present. 1620 VNInfo *VNI = LI.getVNInfoAt(Pos); 1621 if (VNI != nullptr) { 1622 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex()); 1623 LI.removeValNo(VNI); 1624 } 1625 1626 // Also remove the value defined in subranges. 1627 for (LiveInterval::SubRange &S : LI.subranges()) { 1628 if (VNInfo *SVNI = S.getVNInfoAt(Pos)) 1629 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex()) 1630 S.removeValNo(SVNI); 1631 } 1632 LI.removeEmptySubRanges(); 1633 } 1634 1635 void LiveIntervals::splitSeparateComponents(LiveInterval &LI, 1636 SmallVectorImpl<LiveInterval*> &SplitLIs) { 1637 ConnectedVNInfoEqClasses ConEQ(*this); 1638 unsigned NumComp = ConEQ.Classify(LI); 1639 if (NumComp <= 1) 1640 return; 1641 LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); 1642 unsigned Reg = LI.reg; 1643 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); 1644 for (unsigned I = 1; I < NumComp; ++I) { 1645 unsigned NewVReg = MRI->createVirtualRegister(RegClass); 1646 LiveInterval &NewLI = createEmptyInterval(NewVReg); 1647 SplitLIs.push_back(&NewLI); 1648 } 1649 ConEQ.Distribute(LI, SplitLIs.data(), *MRI); 1650 } 1651 1652 void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { 1653 assert(LRCalc && "LRCalc not initialized."); 1654 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 1655 LRCalc->constructMainRangeFromSubranges(LI); 1656 } 1657