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