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