1193323Sed//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the LiveInterval analysis pass which is used 11193323Sed// by the Linear Scan Register allocator. This pass linearizes the 12193323Sed// basic blocks of the function in DFS order and uses the 13193323Sed// LiveVariables pass to conservatively compute live intervals for 14193323Sed// each virtual and physical register. 15193323Sed// 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed 18193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19249423Sdim#include "LiveRangeCalc.h" 20249423Sdim#include "llvm/ADT/DenseSet.h" 21249423Sdim#include "llvm/ADT/STLExtras.h" 22193323Sed#include "llvm/Analysis/AliasAnalysis.h" 23193323Sed#include "llvm/CodeGen/LiveVariables.h" 24276479Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25239462Sdim#include "llvm/CodeGen/MachineDominators.h" 26193323Sed#include "llvm/CodeGen/MachineInstr.h" 27193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 28193323Sed#include "llvm/CodeGen/Passes.h" 29249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 30249423Sdim#include "llvm/IR/Value.h" 31261991Sdim#include "llvm/Support/BlockFrequency.h" 32193323Sed#include "llvm/Support/CommandLine.h" 33193323Sed#include "llvm/Support/Debug.h" 34198090Srdivacky#include "llvm/Support/ErrorHandling.h" 35198090Srdivacky#include "llvm/Support/raw_ostream.h" 36249423Sdim#include "llvm/Target/TargetInstrInfo.h" 37249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 38280031Sdim#include "llvm/Target/TargetSubtargetInfo.h" 39193323Sed#include <algorithm> 40249423Sdim#include <cmath> 41193323Sed#include <limits> 42193323Sedusing namespace llvm; 43193323Sed 44276479Sdim#define DEBUG_TYPE "regalloc" 45276479Sdim 46193323Sedchar LiveIntervals::ID = 0; 47239462Sdimchar &llvm::LiveIntervalsID = LiveIntervals::ID; 48218893SdimINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 49218893Sdim "Live Interval Analysis", false, false) 50296417SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 51218893SdimINITIALIZE_PASS_DEPENDENCY(LiveVariables) 52234353SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 53218893SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 54218893SdimINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 55218893Sdim "Live Interval Analysis", false, false) 56193323Sed 57261991Sdim#ifndef NDEBUG 58261991Sdimstatic cl::opt<bool> EnablePrecomputePhysRegs( 59261991Sdim "precompute-phys-liveness", cl::Hidden, 60261991Sdim cl::desc("Eagerly compute live intervals for all physreg units.")); 61261991Sdim#else 62261991Sdimstatic bool EnablePrecomputePhysRegs = false; 63261991Sdim#endif // NDEBUG 64261991Sdim 65280031Sdimstatic cl::opt<bool> EnableSubRegLiveness( 66280031Sdim "enable-subreg-liveness", cl::Hidden, cl::init(true), 67280031Sdim cl::desc("Enable subregister liveness tracking.")); 68280031Sdim 69288943Sdimnamespace llvm { 70288943Sdimcl::opt<bool> UseSegmentSetForPhysRegs( 71288943Sdim "use-segment-set-for-physregs", cl::Hidden, cl::init(true), 72288943Sdim cl::desc( 73288943Sdim "Use segment set for the computation of the live ranges of physregs.")); 74288943Sdim} 75288943Sdim 76193323Sedvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 77198090Srdivacky AU.setPreservesCFG(); 78296417Sdim AU.addRequired<AAResultsWrapperPass>(); 79296417Sdim AU.addPreserved<AAResultsWrapperPass>(); 80249423Sdim // LiveVariables isn't really required by this analysis, it is only required 81249423Sdim // here to make sure it is live during TwoAddressInstructionPass and 82249423Sdim // PHIElimination. This is temporary. 83212904Sdim AU.addRequired<LiveVariables>(); 84193323Sed AU.addPreserved<LiveVariables>(); 85234353Sdim AU.addPreservedID(MachineLoopInfoID); 86239462Sdim AU.addRequiredTransitiveID(MachineDominatorsID); 87193323Sed AU.addPreservedID(MachineDominatorsID); 88198892Srdivacky AU.addPreserved<SlotIndexes>(); 89198892Srdivacky AU.addRequiredTransitive<SlotIndexes>(); 90193323Sed MachineFunctionPass::getAnalysisUsage(AU); 91193323Sed} 92193323Sed 93239462SdimLiveIntervals::LiveIntervals() : MachineFunctionPass(ID), 94276479Sdim DomTree(nullptr), LRCalc(nullptr) { 95239462Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 96239462Sdim} 97239462Sdim 98239462SdimLiveIntervals::~LiveIntervals() { 99239462Sdim delete LRCalc; 100239462Sdim} 101239462Sdim 102193323Sedvoid LiveIntervals::releaseMemory() { 103193323Sed // Free the live intervals themselves. 104239462Sdim for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) 105239462Sdim delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; 106239462Sdim VirtRegIntervals.clear(); 107234353Sdim RegMaskSlots.clear(); 108234353Sdim RegMaskBits.clear(); 109234353Sdim RegMaskBlocks.clear(); 110198090Srdivacky 111261991Sdim for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 112261991Sdim delete RegUnitRanges[i]; 113261991Sdim RegUnitRanges.clear(); 114239462Sdim 115210299Sed // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 116210299Sed VNInfoAllocator.Reset(); 117193323Sed} 118193323Sed 119261991Sdim/// runOnMachineFunction - calculates LiveIntervals 120193323Sed/// 121193323Sedbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 122239462Sdim MF = &fn; 123239462Sdim MRI = &MF->getRegInfo(); 124280031Sdim TRI = MF->getSubtarget().getRegisterInfo(); 125280031Sdim TII = MF->getSubtarget().getInstrInfo(); 126296417Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 127239462Sdim Indexes = &getAnalysis<SlotIndexes>(); 128239462Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 129280031Sdim 130280031Sdim if (EnableSubRegLiveness && MF->getSubtarget().enableSubRegLiveness()) 131280031Sdim MRI->enableSubRegLiveness(true); 132280031Sdim 133239462Sdim if (!LRCalc) 134239462Sdim LRCalc = new LiveRangeCalc(); 135193323Sed 136239462Sdim // Allocate space for all virtual registers. 137239462Sdim VirtRegIntervals.resize(MRI->getNumVirtRegs()); 138193323Sed 139249423Sdim computeVirtRegs(); 140249423Sdim computeRegMasks(); 141239462Sdim computeLiveInRegUnits(); 142193323Sed 143261991Sdim if (EnablePrecomputePhysRegs) { 144261991Sdim // For stress testing, precompute live ranges of all physical register 145261991Sdim // units, including reserved registers. 146261991Sdim for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 147261991Sdim getRegUnit(i); 148261991Sdim } 149193323Sed DEBUG(dump()); 150193323Sed return true; 151193323Sed} 152193323Sed 153193323Sed/// print - Implement the dump method. 154198090Srdivackyvoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 155198090Srdivacky OS << "********** INTERVALS **********\n"; 156193323Sed 157239462Sdim // Dump the regunits. 158261991Sdim for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 159261991Sdim if (LiveRange *LR = RegUnitRanges[i]) 160261991Sdim OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; 161234353Sdim 162234353Sdim // Dump the virtregs. 163239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 164239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 165239462Sdim if (hasInterval(Reg)) 166261991Sdim OS << getInterval(Reg) << '\n'; 167239462Sdim } 168234353Sdim 169243830Sdim OS << "RegMasks:"; 170243830Sdim for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) 171243830Sdim OS << ' ' << RegMaskSlots[i]; 172243830Sdim OS << '\n'; 173243830Sdim 174198090Srdivacky printInstrs(OS); 175198090Srdivacky} 176198090Srdivacky 177198090Srdivackyvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 178198090Srdivacky OS << "********** MACHINEINSTRS **********\n"; 179239462Sdim MF->print(OS, Indexes); 180193323Sed} 181193323Sed 182243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 183198090Srdivackyvoid LiveIntervals::dumpInstrs() const { 184202375Srdivacky printInstrs(dbgs()); 185198090Srdivacky} 186243830Sdim#endif 187198090Srdivacky 188193323SedLiveInterval* LiveIntervals::createInterval(unsigned reg) { 189261991Sdim float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 190261991Sdim llvm::huge_valf : 0.0F; 191193323Sed return new LiveInterval(reg, Weight); 192193323Sed} 193193323Sed 194239462Sdim 195239462Sdim/// computeVirtRegInterval - Compute the live interval of a virtual register, 196239462Sdim/// based on defs and uses. 197261991Sdimvoid LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { 198239462Sdim assert(LRCalc && "LRCalc not initialized."); 199261991Sdim assert(LI.empty() && "Should only compute empty intervals."); 200296417Sdim bool ShouldTrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(LI.reg); 201239462Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 202296417Sdim LRCalc->calculate(LI, ShouldTrackSubRegLiveness); 203296417Sdim bool SeparatedComponents = computeDeadValues(LI, nullptr); 204296417Sdim if (SeparatedComponents) { 205296417Sdim assert(ShouldTrackSubRegLiveness 206296417Sdim && "Separated components should only occur for unused subreg defs"); 207296417Sdim SmallVector<LiveInterval*, 8> SplitLIs; 208296417Sdim splitSeparateComponents(LI, SplitLIs); 209296417Sdim } 210193323Sed} 211193323Sed 212239462Sdimvoid LiveIntervals::computeVirtRegs() { 213239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 214239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 215239462Sdim if (MRI->reg_nodbg_empty(Reg)) 216239462Sdim continue; 217261991Sdim createAndComputeVirtRegInterval(Reg); 218239462Sdim } 219239462Sdim} 220239462Sdim 221239462Sdimvoid LiveIntervals::computeRegMasks() { 222239462Sdim RegMaskBlocks.resize(MF->getNumBlockIDs()); 223239462Sdim 224239462Sdim // Find all instructions with regmask operands. 225296417Sdim for (MachineBasicBlock &MBB : *MF) { 226296417Sdim std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()]; 227239462Sdim RMB.first = RegMaskSlots.size(); 228296417Sdim 229296417Sdim // Some block starts, such as EH funclets, create masks. 230296417Sdim if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { 231296417Sdim RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); 232296417Sdim RegMaskBits.push_back(Mask); 233296417Sdim } 234296417Sdim 235296417Sdim for (MachineInstr &MI : MBB) { 236296417Sdim for (const MachineOperand &MO : MI.operands()) { 237288943Sdim if (!MO.isRegMask()) 238239462Sdim continue; 239296417Sdim RegMaskSlots.push_back(Indexes->getInstructionIndex(&MI).getRegSlot()); 240296417Sdim RegMaskBits.push_back(MO.getRegMask()); 241239462Sdim } 242296417Sdim } 243296417Sdim 244296417Sdim // Some block ends, such as funclet returns, create masks. 245296417Sdim if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { 246296417Sdim RegMaskSlots.push_back(Indexes->getMBBEndIdx(&MBB)); 247296417Sdim RegMaskBits.push_back(Mask); 248296417Sdim } 249296417Sdim 250239462Sdim // Compute the number of register mask instructions in this block. 251243830Sdim RMB.second = RegMaskSlots.size() - RMB.first; 252239462Sdim } 253239462Sdim} 254239462Sdim 255239462Sdim//===----------------------------------------------------------------------===// 256239462Sdim// Register Unit Liveness 257239462Sdim//===----------------------------------------------------------------------===// 258239462Sdim// 259239462Sdim// Fixed interference typically comes from ABI boundaries: Function arguments 260239462Sdim// and return values are passed in fixed registers, and so are exception 261239462Sdim// pointers entering landing pads. Certain instructions require values to be 262239462Sdim// present in specific registers. That is also represented through fixed 263239462Sdim// interference. 264239462Sdim// 265239462Sdim 266261991Sdim/// computeRegUnitInterval - Compute the live range of a register unit, based 267261991Sdim/// on the uses and defs of aliasing registers. The range should be empty, 268239462Sdim/// or contain only dead phi-defs from ABI blocks. 269261991Sdimvoid LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { 270239462Sdim assert(LRCalc && "LRCalc not initialized."); 271239462Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 272239462Sdim 273239462Sdim // The physregs aliasing Unit are the roots and their super-registers. 274239462Sdim // Create all values as dead defs before extending to uses. Note that roots 275239462Sdim // may share super-registers. That's OK because createDeadDefs() is 276239462Sdim // idempotent. It is very rare for a register unit to have multiple roots, so 277239462Sdim // uniquing super-registers is probably not worthwhile. 278239462Sdim for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 279261991Sdim for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 280261991Sdim Supers.isValid(); ++Supers) { 281239462Sdim if (!MRI->reg_empty(*Supers)) 282261991Sdim LRCalc->createDeadDefs(LR, *Supers); 283239462Sdim } 284239462Sdim } 285239462Sdim 286261991Sdim // Now extend LR to reach all uses. 287239462Sdim // Ignore uses of reserved registers. We only track defs of those. 288239462Sdim for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 289261991Sdim for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 290261991Sdim Supers.isValid(); ++Supers) { 291239462Sdim unsigned Reg = *Supers; 292243830Sdim if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) 293261991Sdim LRCalc->extendToUses(LR, Reg); 294239462Sdim } 295239462Sdim } 296288943Sdim 297288943Sdim // Flush the segment set to the segment vector. 298288943Sdim if (UseSegmentSetForPhysRegs) 299288943Sdim LR.flushSegmentSet(); 300239462Sdim} 301239462Sdim 302239462Sdim 303239462Sdim/// computeLiveInRegUnits - Precompute the live ranges of any register units 304239462Sdim/// that are live-in to an ABI block somewhere. Register values can appear 305239462Sdim/// without a corresponding def when entering the entry block or a landing pad. 306239462Sdim/// 307239462Sdimvoid LiveIntervals::computeLiveInRegUnits() { 308261991Sdim RegUnitRanges.resize(TRI->getNumRegUnits()); 309239462Sdim DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); 310239462Sdim 311261991Sdim // Keep track of the live range sets allocated. 312261991Sdim SmallVector<unsigned, 8> NewRanges; 313239462Sdim 314239462Sdim // Check all basic blocks for live-ins. 315239462Sdim for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 316239462Sdim MFI != MFE; ++MFI) { 317296417Sdim const MachineBasicBlock *MBB = &*MFI; 318239462Sdim 319239462Sdim // We only care about ABI blocks: Entry + landing pads. 320296417Sdim if ((MFI != MF->begin() && !MBB->isEHPad()) || MBB->livein_empty()) 321239462Sdim continue; 322239462Sdim 323239462Sdim // Create phi-defs at Begin for all live-in registers. 324239462Sdim SlotIndex Begin = Indexes->getMBBStartIdx(MBB); 325239462Sdim DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); 326296417Sdim for (const auto &LI : MBB->liveins()) { 327296417Sdim for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { 328239462Sdim unsigned Unit = *Units; 329261991Sdim LiveRange *LR = RegUnitRanges[Unit]; 330261991Sdim if (!LR) { 331288943Sdim // Use segment set to speed-up initial computation of the live range. 332288943Sdim LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); 333261991Sdim NewRanges.push_back(Unit); 334239462Sdim } 335261991Sdim VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); 336239462Sdim (void)VNI; 337239462Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); 338239462Sdim } 339239462Sdim } 340239462Sdim DEBUG(dbgs() << '\n'); 341239462Sdim } 342261991Sdim DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); 343239462Sdim 344261991Sdim // Compute the 'normal' part of the ranges. 345261991Sdim for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { 346261991Sdim unsigned Unit = NewRanges[i]; 347261991Sdim computeRegUnitRange(*RegUnitRanges[Unit], Unit); 348261991Sdim } 349239462Sdim} 350239462Sdim 351239462Sdim 352280031Sdimstatic void createSegmentsForValues(LiveRange &LR, 353280031Sdim iterator_range<LiveInterval::vni_iterator> VNIs) { 354280031Sdim for (auto VNI : VNIs) { 355280031Sdim if (VNI->isUnused()) 356280031Sdim continue; 357280031Sdim SlotIndex Def = VNI->def; 358280031Sdim LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); 359280031Sdim } 360280031Sdim} 361280031Sdim 362280031Sdimtypedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList; 363280031Sdim 364280031Sdimstatic void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, 365280031Sdim ShrinkToUsesWorkList &WorkList, 366280031Sdim const LiveRange &OldRange) { 367280031Sdim // Keep track of the PHIs that are in use. 368280031Sdim SmallPtrSet<VNInfo*, 8> UsedPHIs; 369280031Sdim // Blocks that have already been added to WorkList as live-out. 370280031Sdim SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 371280031Sdim 372280031Sdim // Extend intervals to reach all uses in WorkList. 373280031Sdim while (!WorkList.empty()) { 374280031Sdim SlotIndex Idx = WorkList.back().first; 375280031Sdim VNInfo *VNI = WorkList.back().second; 376280031Sdim WorkList.pop_back(); 377280031Sdim const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot()); 378280031Sdim SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB); 379280031Sdim 380280031Sdim // Extend the live range for VNI to be live at Idx. 381280031Sdim if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) { 382280031Sdim assert(ExtVNI == VNI && "Unexpected existing value number"); 383280031Sdim (void)ExtVNI; 384280031Sdim // Is this a PHIDef we haven't seen before? 385280031Sdim if (!VNI->isPHIDef() || VNI->def != BlockStart || 386280031Sdim !UsedPHIs.insert(VNI).second) 387280031Sdim continue; 388280031Sdim // The PHI is live, make sure the predecessors are live-out. 389280031Sdim for (auto &Pred : MBB->predecessors()) { 390280031Sdim if (!LiveOut.insert(Pred).second) 391280031Sdim continue; 392280031Sdim SlotIndex Stop = Indexes.getMBBEndIdx(Pred); 393280031Sdim // A predecessor is not required to have a live-out value for a PHI. 394280031Sdim if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) 395280031Sdim WorkList.push_back(std::make_pair(Stop, PVNI)); 396280031Sdim } 397280031Sdim continue; 398280031Sdim } 399280031Sdim 400280031Sdim // VNI is live-in to MBB. 401280031Sdim DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 402280031Sdim LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); 403280031Sdim 404280031Sdim // Make sure VNI is live-out from the predecessors. 405280031Sdim for (auto &Pred : MBB->predecessors()) { 406280031Sdim if (!LiveOut.insert(Pred).second) 407280031Sdim continue; 408280031Sdim SlotIndex Stop = Indexes.getMBBEndIdx(Pred); 409280031Sdim assert(OldRange.getVNInfoBefore(Stop) == VNI && 410280031Sdim "Wrong value out of predecessor"); 411280031Sdim WorkList.push_back(std::make_pair(Stop, VNI)); 412280031Sdim } 413280031Sdim } 414280031Sdim} 415280031Sdim 416221345Sdimbool LiveIntervals::shrinkToUses(LiveInterval *li, 417221345Sdim SmallVectorImpl<MachineInstr*> *dead) { 418218893Sdim DEBUG(dbgs() << "Shrink: " << *li << '\n'); 419218893Sdim assert(TargetRegisterInfo::isVirtualRegister(li->reg) 420234353Sdim && "Can only shrink virtual registers"); 421280031Sdim 422280031Sdim // Shrink subregister live ranges. 423296417Sdim bool NeedsCleanup = false; 424280031Sdim for (LiveInterval::SubRange &S : li->subranges()) { 425280031Sdim shrinkToUses(S, li->reg); 426296417Sdim if (S.empty()) 427296417Sdim NeedsCleanup = true; 428280031Sdim } 429296417Sdim if (NeedsCleanup) 430296417Sdim li->removeEmptySubRanges(); 431280031Sdim 432218893Sdim // Find all the values used, including PHI kills. 433280031Sdim ShrinkToUsesWorkList WorkList; 434218893Sdim 435218893Sdim // Visit all instructions reading li->reg. 436276479Sdim for (MachineRegisterInfo::reg_instr_iterator 437276479Sdim I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end(); 438276479Sdim I != E; ) { 439276479Sdim MachineInstr *UseMI = &*(I++); 440218893Sdim if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 441218893Sdim continue; 442234353Sdim SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 443261991Sdim LiveQueryResult LRQ = li->Query(Idx); 444239462Sdim VNInfo *VNI = LRQ.valueIn(); 445221345Sdim if (!VNI) { 446221345Sdim // This shouldn't happen: readsVirtualRegister returns true, but there is 447221345Sdim // no live value. It is likely caused by a target getting <undef> flags 448221345Sdim // wrong. 449221345Sdim DEBUG(dbgs() << Idx << '\t' << *UseMI 450221345Sdim << "Warning: Instr claims to read non-existent value in " 451221345Sdim << *li << '\n'); 452221345Sdim continue; 453221345Sdim } 454234353Sdim // Special case: An early-clobber tied operand reads and writes the 455239462Sdim // register one slot early. 456239462Sdim if (VNInfo *DefVNI = LRQ.valueDefined()) 457239462Sdim Idx = DefVNI->def; 458239462Sdim 459218893Sdim WorkList.push_back(std::make_pair(Idx, VNI)); 460218893Sdim } 461218893Sdim 462261991Sdim // Create new live ranges with only minimal live segments per def. 463261991Sdim LiveRange NewLR; 464280031Sdim createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); 465280031Sdim extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); 466218893Sdim 467280031Sdim // Move the trimmed segments back. 468280031Sdim li->segments.swap(NewLR.segments); 469221345Sdim 470218893Sdim // Handle dead values. 471280031Sdim bool CanSeparate = computeDeadValues(*li, dead); 472276479Sdim DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 473276479Sdim return CanSeparate; 474276479Sdim} 475276479Sdim 476280031Sdimbool LiveIntervals::computeDeadValues(LiveInterval &LI, 477276479Sdim SmallVectorImpl<MachineInstr*> *dead) { 478296417Sdim bool MayHaveSplitComponents = false; 479280031Sdim for (auto VNI : LI.valnos) { 480218893Sdim if (VNI->isUnused()) 481218893Sdim continue; 482288943Sdim SlotIndex Def = VNI->def; 483288943Sdim LiveRange::iterator I = LI.FindSegmentContaining(Def); 484280031Sdim assert(I != LI.end() && "Missing segment for VNI"); 485288943Sdim 486288943Sdim // Is the register live before? Otherwise we may have to add a read-undef 487288943Sdim // flag for subregister defs. 488296417Sdim bool DeadBeforeDef = false; 489296417Sdim unsigned VReg = LI.reg; 490296417Sdim if (MRI->shouldTrackSubRegLiveness(VReg)) { 491288943Sdim if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { 492288943Sdim MachineInstr *MI = getInstructionFromIndex(Def); 493296417Sdim MI->setRegisterDefReadUndef(VReg); 494296417Sdim DeadBeforeDef = true; 495288943Sdim } 496288943Sdim } 497288943Sdim 498288943Sdim if (I->end != Def.getDeadSlot()) 499218893Sdim continue; 500221345Sdim if (VNI->isPHIDef()) { 501218893Sdim // This is a dead PHI. Remove it. 502239462Sdim VNI->markUnused(); 503280031Sdim LI.removeSegment(I); 504288943Sdim DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); 505296417Sdim MayHaveSplitComponents = true; 506218893Sdim } else { 507218893Sdim // This is a dead def. Make sure the instruction knows. 508288943Sdim MachineInstr *MI = getInstructionFromIndex(Def); 509218893Sdim assert(MI && "No instruction defining live value"); 510296417Sdim MI->addRegisterDead(VReg, TRI); 511296417Sdim 512296417Sdim // If we have a dead def that is completely separate from the rest of 513296417Sdim // the liverange then we rewrite it to use a different VReg to not violate 514296417Sdim // the rule that the liveness of a virtual register forms a connected 515296417Sdim // component. This should only happen if subregister liveness is tracked. 516296417Sdim if (DeadBeforeDef) 517296417Sdim MayHaveSplitComponents = true; 518296417Sdim 519221345Sdim if (dead && MI->allDefsAreDead()) { 520288943Sdim DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); 521221345Sdim dead->push_back(MI); 522221345Sdim } 523218893Sdim } 524218893Sdim } 525296417Sdim return MayHaveSplitComponents; 526218893Sdim} 527218893Sdim 528280031Sdimvoid LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) 529280031Sdim{ 530280031Sdim DEBUG(dbgs() << "Shrink: " << SR << '\n'); 531280031Sdim assert(TargetRegisterInfo::isVirtualRegister(Reg) 532280031Sdim && "Can only shrink virtual registers"); 533280031Sdim // Find all the values used, including PHI kills. 534280031Sdim ShrinkToUsesWorkList WorkList; 535280031Sdim 536280031Sdim // Visit all instructions reading Reg. 537280031Sdim SlotIndex LastIdx; 538280031Sdim for (MachineOperand &MO : MRI->reg_operands(Reg)) { 539280031Sdim MachineInstr *UseMI = MO.getParent(); 540280031Sdim if (UseMI->isDebugValue()) 541280031Sdim continue; 542280031Sdim // Maybe the operand is for a subregister we don't care about. 543280031Sdim unsigned SubReg = MO.getSubReg(); 544280031Sdim if (SubReg != 0) { 545296417Sdim LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); 546296417Sdim if ((LaneMask & SR.LaneMask) == 0) 547280031Sdim continue; 548280031Sdim } 549280031Sdim // We only need to visit each instruction once. 550280031Sdim SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 551280031Sdim if (Idx == LastIdx) 552280031Sdim continue; 553280031Sdim LastIdx = Idx; 554280031Sdim 555280031Sdim LiveQueryResult LRQ = SR.Query(Idx); 556280031Sdim VNInfo *VNI = LRQ.valueIn(); 557280031Sdim // For Subranges it is possible that only undef values are left in that 558280031Sdim // part of the subregister, so there is no real liverange at the use 559280031Sdim if (!VNI) 560280031Sdim continue; 561280031Sdim 562280031Sdim // Special case: An early-clobber tied operand reads and writes the 563280031Sdim // register one slot early. 564280031Sdim if (VNInfo *DefVNI = LRQ.valueDefined()) 565280031Sdim Idx = DefVNI->def; 566280031Sdim 567280031Sdim WorkList.push_back(std::make_pair(Idx, VNI)); 568280031Sdim } 569280031Sdim 570280031Sdim // Create a new live ranges with only minimal live segments per def. 571280031Sdim LiveRange NewLR; 572280031Sdim createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); 573280031Sdim extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); 574280031Sdim 575280031Sdim // Move the trimmed ranges back. 576280031Sdim SR.segments.swap(NewLR.segments); 577280031Sdim 578280031Sdim // Remove dead PHI value numbers 579280031Sdim for (auto VNI : SR.valnos) { 580280031Sdim if (VNI->isUnused()) 581280031Sdim continue; 582280031Sdim const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); 583280031Sdim assert(Segment != nullptr && "Missing segment for VNI"); 584280031Sdim if (Segment->end != VNI->def.getDeadSlot()) 585280031Sdim continue; 586280031Sdim if (VNI->isPHIDef()) { 587280031Sdim // This is a dead PHI. Remove it. 588280031Sdim VNI->markUnused(); 589280031Sdim SR.removeSegment(*Segment); 590280031Sdim DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 591280031Sdim } 592280031Sdim } 593280031Sdim 594280031Sdim DEBUG(dbgs() << "Shrunk: " << SR << '\n'); 595280031Sdim} 596280031Sdim 597261991Sdimvoid LiveIntervals::extendToIndices(LiveRange &LR, 598243830Sdim ArrayRef<SlotIndex> Indices) { 599243830Sdim assert(LRCalc && "LRCalc not initialized."); 600243830Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 601243830Sdim for (unsigned i = 0, e = Indices.size(); i != e; ++i) 602261991Sdim LRCalc->extend(LR, Indices[i]); 603243830Sdim} 604218893Sdim 605280031Sdimvoid LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, 606243830Sdim SmallVectorImpl<SlotIndex> *EndPoints) { 607280031Sdim LiveQueryResult LRQ = LR.Query(Kill); 608280031Sdim VNInfo *VNI = LRQ.valueOutOrDead(); 609243830Sdim if (!VNI) 610243830Sdim return; 611243830Sdim 612243830Sdim MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); 613280031Sdim SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); 614243830Sdim 615243830Sdim // If VNI isn't live out from KillMBB, the value is trivially pruned. 616243830Sdim if (LRQ.endPoint() < MBBEnd) { 617280031Sdim LR.removeSegment(Kill, LRQ.endPoint()); 618243830Sdim if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 619243830Sdim return; 620243830Sdim } 621243830Sdim 622243830Sdim // VNI is live out of KillMBB. 623280031Sdim LR.removeSegment(Kill, MBBEnd); 624243830Sdim if (EndPoints) EndPoints->push_back(MBBEnd); 625243830Sdim 626243830Sdim // Find all blocks that are reachable from KillMBB without leaving VNI's live 627243830Sdim // range. It is possible that KillMBB itself is reachable, so start a DFS 628243830Sdim // from each successor. 629243830Sdim typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy; 630243830Sdim VisitedTy Visited; 631243830Sdim for (MachineBasicBlock::succ_iterator 632243830Sdim SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end(); 633243830Sdim SuccI != SuccE; ++SuccI) { 634243830Sdim for (df_ext_iterator<MachineBasicBlock*, VisitedTy> 635243830Sdim I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); 636243830Sdim I != E;) { 637243830Sdim MachineBasicBlock *MBB = *I; 638243830Sdim 639243830Sdim // Check if VNI is live in to MBB. 640280031Sdim SlotIndex MBBStart, MBBEnd; 641276479Sdim std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); 642280031Sdim LiveQueryResult LRQ = LR.Query(MBBStart); 643243830Sdim if (LRQ.valueIn() != VNI) { 644261991Sdim // This block isn't part of the VNI segment. Prune the search. 645243830Sdim I.skipChildren(); 646243830Sdim continue; 647243830Sdim } 648243830Sdim 649243830Sdim // Prune the search if VNI is killed in MBB. 650243830Sdim if (LRQ.endPoint() < MBBEnd) { 651280031Sdim LR.removeSegment(MBBStart, LRQ.endPoint()); 652243830Sdim if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 653243830Sdim I.skipChildren(); 654243830Sdim continue; 655243830Sdim } 656243830Sdim 657243830Sdim // VNI is live through MBB. 658280031Sdim LR.removeSegment(MBBStart, MBBEnd); 659243830Sdim if (EndPoints) EndPoints->push_back(MBBEnd); 660243830Sdim ++I; 661243830Sdim } 662243830Sdim } 663243830Sdim} 664243830Sdim 665193323Sed//===----------------------------------------------------------------------===// 666193323Sed// Register allocator hooks. 667193323Sed// 668193323Sed 669243830Sdimvoid LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 670243830Sdim // Keep track of regunit ranges. 671280031Sdim SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU; 672280031Sdim // Keep track of subregister ranges. 673280031Sdim SmallVector<std::pair<const LiveInterval::SubRange*, 674280031Sdim LiveRange::const_iterator>, 4> SRs; 675243830Sdim 676239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 677239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 678239462Sdim if (MRI->reg_nodbg_empty(Reg)) 679218893Sdim continue; 680280031Sdim const LiveInterval &LI = getInterval(Reg); 681280031Sdim if (LI.empty()) 682243830Sdim continue; 683218893Sdim 684243830Sdim // Find the regunit intervals for the assigned register. They may overlap 685243830Sdim // the virtual register live range, cancelling any kills. 686243830Sdim RU.clear(); 687243830Sdim for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); 688243830Sdim ++Units) { 689280031Sdim const LiveRange &RURange = getRegUnit(*Units); 690280031Sdim if (RURange.empty()) 691243830Sdim continue; 692280031Sdim RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); 693243830Sdim } 694243830Sdim 695288943Sdim if (MRI->subRegLivenessEnabled()) { 696280031Sdim SRs.clear(); 697280031Sdim for (const LiveInterval::SubRange &SR : LI.subranges()) { 698280031Sdim SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); 699280031Sdim } 700280031Sdim } 701280031Sdim 702261991Sdim // Every instruction that kills Reg corresponds to a segment range end 703261991Sdim // point. 704280031Sdim for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; 705218893Sdim ++RI) { 706234353Sdim // A block index indicates an MBB edge. 707234353Sdim if (RI->end.isBlock()) 708218893Sdim continue; 709218893Sdim MachineInstr *MI = getInstructionFromIndex(RI->end); 710218893Sdim if (!MI) 711218893Sdim continue; 712243830Sdim 713261991Sdim // Check if any of the regunits are live beyond the end of RI. That could 714243830Sdim // happen when a physreg is defined as a copy of a virtreg: 715243830Sdim // 716243830Sdim // %EAX = COPY %vreg5 717243830Sdim // FOO %vreg5 <--- MI, cancel kill because %EAX is live. 718243830Sdim // BAR %EAX<kill> 719243830Sdim // 720243830Sdim // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. 721280031Sdim for (auto &RUP : RU) { 722280031Sdim const LiveRange &RURange = *RUP.first; 723280031Sdim LiveRange::const_iterator &I = RUP.second; 724280031Sdim if (I == RURange.end()) 725243830Sdim continue; 726280031Sdim I = RURange.advanceTo(I, RI->end); 727280031Sdim if (I == RURange.end() || I->start >= RI->end) 728243830Sdim continue; 729243830Sdim // I is overlapping RI. 730280031Sdim goto CancelKill; 731243830Sdim } 732280031Sdim 733288943Sdim if (MRI->subRegLivenessEnabled()) { 734280031Sdim // When reading a partial undefined value we must not add a kill flag. 735280031Sdim // The regalloc might have used the undef lane for something else. 736280031Sdim // Example: 737280031Sdim // %vreg1 = ... ; R32: %vreg1 738280031Sdim // %vreg2:high16 = ... ; R64: %vreg2 739280031Sdim // = read %vreg2<kill> ; R64: %vreg2 740280031Sdim // = read %vreg1 ; R32: %vreg1 741280031Sdim // The <kill> flag is correct for %vreg2, but the register allocator may 742280031Sdim // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0 743280031Sdim // are actually never written by %vreg2. After assignment the <kill> 744280031Sdim // flag at the read instruction is invalid. 745296417Sdim LaneBitmask DefinedLanesMask; 746280031Sdim if (!SRs.empty()) { 747280031Sdim // Compute a mask of lanes that are defined. 748280031Sdim DefinedLanesMask = 0; 749280031Sdim for (auto &SRP : SRs) { 750280031Sdim const LiveInterval::SubRange &SR = *SRP.first; 751280031Sdim LiveRange::const_iterator &I = SRP.second; 752280031Sdim if (I == SR.end()) 753280031Sdim continue; 754280031Sdim I = SR.advanceTo(I, RI->end); 755280031Sdim if (I == SR.end() || I->start >= RI->end) 756280031Sdim continue; 757280031Sdim // I is overlapping RI 758280031Sdim DefinedLanesMask |= SR.LaneMask; 759280031Sdim } 760280031Sdim } else 761280031Sdim DefinedLanesMask = ~0u; 762280031Sdim 763280031Sdim bool IsFullWrite = false; 764280031Sdim for (const MachineOperand &MO : MI->operands()) { 765280031Sdim if (!MO.isReg() || MO.getReg() != Reg) 766280031Sdim continue; 767280031Sdim if (MO.isUse()) { 768280031Sdim // Reading any undefined lanes? 769296417Sdim LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); 770280031Sdim if ((UseMask & ~DefinedLanesMask) != 0) 771280031Sdim goto CancelKill; 772280031Sdim } else if (MO.getSubReg() == 0) { 773280031Sdim // Writing to the full register? 774280031Sdim assert(MO.isDef()); 775280031Sdim IsFullWrite = true; 776280031Sdim } 777280031Sdim } 778280031Sdim 779280031Sdim // If an instruction writes to a subregister, a new segment starts in 780280031Sdim // the LiveInterval. But as this is only overriding part of the register 781280031Sdim // adding kill-flags is not correct here after registers have been 782280031Sdim // assigned. 783280031Sdim if (!IsFullWrite) { 784280031Sdim // Next segment has to be adjacent in the subregister write case. 785280031Sdim LiveRange::const_iterator N = std::next(RI); 786280031Sdim if (N != LI.end() && N->start == RI->end) 787280031Sdim goto CancelKill; 788280031Sdim } 789280031Sdim } 790280031Sdim 791280031Sdim MI->addRegisterKilled(Reg, nullptr); 792280031Sdim continue; 793280031SdimCancelKill: 794280031Sdim MI->clearRegisterKills(Reg, nullptr); 795218893Sdim } 796218893Sdim } 797218893Sdim} 798218893Sdim 799234353SdimMachineBasicBlock* 800234353SdimLiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 801234353Sdim // A local live range must be fully contained inside the block, meaning it is 802234353Sdim // defined and killed at instructions, not at block boundaries. It is not 803234353Sdim // live in or or out of any block. 804234353Sdim // 805234353Sdim // It is technically possible to have a PHI-defined live range identical to a 806234353Sdim // single block, but we are going to return false in that case. 807193323Sed 808234353Sdim SlotIndex Start = LI.beginIndex(); 809234353Sdim if (Start.isBlock()) 810276479Sdim return nullptr; 811212904Sdim 812234353Sdim SlotIndex Stop = LI.endIndex(); 813234353Sdim if (Stop.isBlock()) 814276479Sdim return nullptr; 815193323Sed 816234353Sdim // getMBBFromIndex doesn't need to search the MBB table when both indexes 817234353Sdim // belong to proper instructions. 818239462Sdim MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); 819239462Sdim MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); 820276479Sdim return MBB1 == MBB2 ? MBB1 : nullptr; 821234353Sdim} 822193323Sed 823239462Sdimbool 824239462SdimLiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { 825280031Sdim for (const VNInfo *PHI : LI.valnos) { 826239462Sdim if (PHI->isUnused() || !PHI->isPHIDef()) 827239462Sdim continue; 828239462Sdim const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 829239462Sdim // Conservatively return true instead of scanning huge predecessor lists. 830239462Sdim if (PHIMBB->pred_size() > 100) 831239462Sdim return true; 832239462Sdim for (MachineBasicBlock::const_pred_iterator 833239462Sdim PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) 834239462Sdim if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) 835239462Sdim return true; 836239462Sdim } 837239462Sdim return false; 838239462Sdim} 839239462Sdim 840234353Sdimfloat 841276479SdimLiveIntervals::getSpillWeight(bool isDef, bool isUse, 842276479Sdim const MachineBlockFrequencyInfo *MBFI, 843276479Sdim const MachineInstr *MI) { 844276479Sdim BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent()); 845276479Sdim const float Scale = 1.0f / MBFI->getEntryFreq(); 846276479Sdim return (isDef + isUse) * (Freq.getFrequency() * Scale); 847193323Sed} 848193323Sed 849261991SdimLiveRange::Segment 850261991SdimLiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) { 851261991Sdim LiveInterval& Interval = createEmptyInterval(reg); 852234353Sdim VNInfo* VN = Interval.getNextValue( 853234353Sdim SlotIndex(getInstructionIndex(startInst).getRegSlot()), 854234353Sdim getVNInfoAllocator()); 855261991Sdim LiveRange::Segment S( 856234353Sdim SlotIndex(getInstructionIndex(startInst).getRegSlot()), 857234353Sdim getMBBEndIdx(startInst->getParent()), VN); 858261991Sdim Interval.addSegment(S); 859193323Sed 860261991Sdim return S; 861193323Sed} 862193323Sed 863198892Srdivacky 864234353Sdim//===----------------------------------------------------------------------===// 865234353Sdim// Register mask functions 866234353Sdim//===----------------------------------------------------------------------===// 867198892Srdivacky 868234353Sdimbool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 869234353Sdim BitVector &UsableRegs) { 870234353Sdim if (LI.empty()) 871198892Srdivacky return false; 872234353Sdim LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 873198892Srdivacky 874234353Sdim // Use a smaller arrays for local live ranges. 875234353Sdim ArrayRef<SlotIndex> Slots; 876234353Sdim ArrayRef<const uint32_t*> Bits; 877234353Sdim if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 878234353Sdim Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 879234353Sdim Bits = getRegMaskBitsInBlock(MBB->getNumber()); 880234353Sdim } else { 881234353Sdim Slots = getRegMaskSlots(); 882234353Sdim Bits = getRegMaskBits(); 883193323Sed } 884198892Srdivacky 885234353Sdim // We are going to enumerate all the register mask slots contained in LI. 886234353Sdim // Start with a binary search of RegMaskSlots to find a starting point. 887234353Sdim ArrayRef<SlotIndex>::iterator SlotI = 888234353Sdim std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 889234353Sdim ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 890193323Sed 891234353Sdim // No slots in range, LI begins after the last call. 892234353Sdim if (SlotI == SlotE) 893234353Sdim return false; 894234353Sdim 895234353Sdim bool Found = false; 896234353Sdim for (;;) { 897234353Sdim assert(*SlotI >= LiveI->start); 898234353Sdim // Loop over all slots overlapping this segment. 899234353Sdim while (*SlotI < LiveI->end) { 900234353Sdim // *SlotI overlaps LI. Collect mask bits. 901234353Sdim if (!Found) { 902234353Sdim // This is the first overlap. Initialize UsableRegs to all ones. 903234353Sdim UsableRegs.clear(); 904239462Sdim UsableRegs.resize(TRI->getNumRegs(), true); 905234353Sdim Found = true; 906234353Sdim } 907234353Sdim // Remove usable registers clobbered by this mask. 908234353Sdim UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 909234353Sdim if (++SlotI == SlotE) 910234353Sdim return Found; 911234353Sdim } 912234353Sdim // *SlotI is beyond the current LI segment. 913234353Sdim LiveI = LI.advanceTo(LiveI, *SlotI); 914234353Sdim if (LiveI == LiveE) 915234353Sdim return Found; 916234353Sdim // Advance SlotI until it overlaps. 917234353Sdim while (*SlotI < LiveI->start) 918234353Sdim if (++SlotI == SlotE) 919234353Sdim return Found; 920193323Sed } 921193323Sed} 922193323Sed 923234353Sdim//===----------------------------------------------------------------------===// 924234353Sdim// IntervalUpdate class. 925234353Sdim//===----------------------------------------------------------------------===// 926193323Sed 927234353Sdim// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 928234353Sdimclass LiveIntervals::HMEditor { 929234353Sdimprivate: 930234353Sdim LiveIntervals& LIS; 931234353Sdim const MachineRegisterInfo& MRI; 932234353Sdim const TargetRegisterInfo& TRI; 933243830Sdim SlotIndex OldIdx; 934234353Sdim SlotIndex NewIdx; 935261991Sdim SmallPtrSet<LiveRange*, 8> Updated; 936243830Sdim bool UpdateFlags; 937193323Sed 938234353Sdimpublic: 939234353Sdim HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 940243830Sdim const TargetRegisterInfo& TRI, 941243830Sdim SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) 942243830Sdim : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), 943243830Sdim UpdateFlags(UpdateFlags) {} 944199989Srdivacky 945243830Sdim // FIXME: UpdateFlags is a workaround that creates live intervals for all 946243830Sdim // physregs, even those that aren't needed for regalloc, in order to update 947243830Sdim // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 948243830Sdim // flags, and postRA passes will use a live register utility instead. 949261991Sdim LiveRange *getRegUnitLI(unsigned Unit) { 950243830Sdim if (UpdateFlags) 951243830Sdim return &LIS.getRegUnit(Unit); 952243830Sdim return LIS.getCachedRegUnit(Unit); 953234353Sdim } 954193323Sed 955243830Sdim /// Update all live ranges touched by MI, assuming a move from OldIdx to 956243830Sdim /// NewIdx. 957243830Sdim void updateAllRanges(MachineInstr *MI) { 958243830Sdim DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); 959243830Sdim bool hasRegMask = false; 960288943Sdim for (MachineOperand &MO : MI->operands()) { 961288943Sdim if (MO.isRegMask()) 962243830Sdim hasRegMask = true; 963288943Sdim if (!MO.isReg()) 964243830Sdim continue; 965243830Sdim // Aggressively clear all kill flags. 966243830Sdim // They are reinserted by VirtRegRewriter. 967288943Sdim if (MO.isUse()) 968288943Sdim MO.setIsKill(false); 969193323Sed 970288943Sdim unsigned Reg = MO.getReg(); 971243830Sdim if (!Reg) 972243830Sdim continue; 973243830Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 974261991Sdim LiveInterval &LI = LIS.getInterval(Reg); 975280031Sdim if (LI.hasSubRanges()) { 976288943Sdim unsigned SubReg = MO.getSubReg(); 977296417Sdim LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg); 978280031Sdim for (LiveInterval::SubRange &S : LI.subranges()) { 979280031Sdim if ((S.LaneMask & LaneMask) == 0) 980280031Sdim continue; 981280031Sdim updateRange(S, Reg, S.LaneMask); 982280031Sdim } 983280031Sdim } 984280031Sdim updateRange(LI, Reg, 0); 985243830Sdim continue; 986243830Sdim } 987193323Sed 988243830Sdim // For physregs, only update the regunits that actually have a 989243830Sdim // precomputed live range. 990243830Sdim for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 991261991Sdim if (LiveRange *LR = getRegUnitLI(*Units)) 992280031Sdim updateRange(*LR, *Units, 0); 993193323Sed } 994243830Sdim if (hasRegMask) 995243830Sdim updateRegMaskSlots(); 996193323Sed } 997193323Sed 998234353Sdimprivate: 999243830Sdim /// Update a single live range, assuming an instruction has been moved from 1000243830Sdim /// OldIdx to NewIdx. 1001296417Sdim void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { 1002280031Sdim if (!Updated.insert(&LR).second) 1003243830Sdim return; 1004243830Sdim DEBUG({ 1005243830Sdim dbgs() << " "; 1006280031Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1007261991Sdim dbgs() << PrintReg(Reg); 1008280031Sdim if (LaneMask != 0) 1009296417Sdim dbgs() << " L" << PrintLaneMask(LaneMask); 1010280031Sdim } else { 1011261991Sdim dbgs() << PrintRegUnit(Reg, &TRI); 1012280031Sdim } 1013261991Sdim dbgs() << ":\t" << LR << '\n'; 1014243830Sdim }); 1015243830Sdim if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) 1016261991Sdim handleMoveDown(LR); 1017243830Sdim else 1018280031Sdim handleMoveUp(LR, Reg, LaneMask); 1019261991Sdim DEBUG(dbgs() << " -->\t" << LR << '\n'); 1020261991Sdim LR.verify(); 1021243830Sdim } 1022193323Sed 1023261991Sdim /// Update LR to reflect an instruction has been moved downwards from OldIdx 1024243830Sdim /// to NewIdx. 1025243830Sdim /// 1026243830Sdim /// 1. Live def at OldIdx: 1027243830Sdim /// Move def to NewIdx, assert endpoint after NewIdx. 1028243830Sdim /// 1029243830Sdim /// 2. Live def at OldIdx, killed at NewIdx: 1030243830Sdim /// Change to dead def at NewIdx. 1031243830Sdim /// (Happens when bundling def+kill together). 1032243830Sdim /// 1033243830Sdim /// 3. Dead def at OldIdx: 1034243830Sdim /// Move def to NewIdx, possibly across another live value. 1035243830Sdim /// 1036243830Sdim /// 4. Def at OldIdx AND at NewIdx: 1037261991Sdim /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx. 1038243830Sdim /// (Happens when bundling multiple defs together). 1039243830Sdim /// 1040243830Sdim /// 5. Value read at OldIdx, killed before NewIdx: 1041243830Sdim /// Extend kill to NewIdx. 1042243830Sdim /// 1043261991Sdim void handleMoveDown(LiveRange &LR) { 1044243830Sdim // First look for a kill at OldIdx. 1045261991Sdim LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 1046261991Sdim LiveRange::iterator E = LR.end(); 1047261991Sdim // Is LR even live at OldIdx? 1048243830Sdim if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 1049243830Sdim return; 1050243830Sdim 1051243830Sdim // Handle a live-in value. 1052243830Sdim if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 1053243830Sdim bool isKill = SlotIndex::isSameInstr(OldIdx, I->end); 1054243830Sdim // If the live-in value already extends to NewIdx, there is nothing to do. 1055243830Sdim if (!SlotIndex::isEarlierInstr(I->end, NewIdx)) 1056234353Sdim return; 1057243830Sdim // Aggressively remove all kill flags from the old kill point. 1058243830Sdim // Kill flags shouldn't be used while live intervals exist, they will be 1059243830Sdim // reinserted by VirtRegRewriter. 1060243830Sdim if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end)) 1061243830Sdim for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) 1062243830Sdim if (MO->isReg() && MO->isUse()) 1063243830Sdim MO->setIsKill(false); 1064261991Sdim // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by 1065243830Sdim // overlapping ranges. Case 5 above. 1066243830Sdim I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 1067243830Sdim // If this was a kill, there may also be a def. Otherwise we're done. 1068243830Sdim if (!isKill) 1069234353Sdim return; 1070243830Sdim ++I; 1071193323Sed } 1072193323Sed 1073243830Sdim // Check for a def at OldIdx. 1074243830Sdim if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start)) 1075243830Sdim return; 1076243830Sdim // We have a def at OldIdx. 1077243830Sdim VNInfo *DefVNI = I->valno; 1078243830Sdim assert(DefVNI->def == I->start && "Inconsistent def"); 1079243830Sdim DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 1080243830Sdim // If the defined value extends beyond NewIdx, just move the def down. 1081243830Sdim // This is case 1 above. 1082243830Sdim if (SlotIndex::isEarlierInstr(NewIdx, I->end)) { 1083243830Sdim I->start = DefVNI->def; 1084243830Sdim return; 1085193323Sed } 1086243830Sdim // The remaining possibilities are now: 1087243830Sdim // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx). 1088243830Sdim // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot(). 1089243830Sdim // In either case, it is possible that there is an existing def at NewIdx. 1090243830Sdim assert((I->end == OldIdx.getDeadSlot() || 1091243830Sdim SlotIndex::isSameInstr(I->end, NewIdx)) && 1092243830Sdim "Cannot move def below kill"); 1093261991Sdim LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot()); 1094243830Sdim if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) { 1095243830Sdim // There is an existing def at NewIdx, case 4 above. The def at OldIdx is 1096243830Sdim // coalesced into that value. 1097243830Sdim assert(NewI->valno != DefVNI && "Multiple defs of value?"); 1098261991Sdim LR.removeValNo(DefVNI); 1099243830Sdim return; 1100243830Sdim } 1101243830Sdim // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. 1102261991Sdim // If the def at OldIdx was dead, we allow it to be moved across other LR 1103243830Sdim // values. The new range should be placed immediately before NewI, move any 1104243830Sdim // intermediate ranges up. 1105243830Sdim assert(NewI != I && "Inconsistent iterators"); 1106276479Sdim std::copy(std::next(I), NewI, I); 1107276479Sdim *std::prev(NewI) 1108261991Sdim = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 1109243830Sdim } 1110193323Sed 1111261991Sdim /// Update LR to reflect an instruction has been moved upwards from OldIdx 1112243830Sdim /// to NewIdx. 1113243830Sdim /// 1114243830Sdim /// 1. Live def at OldIdx: 1115243830Sdim /// Hoist def to NewIdx. 1116243830Sdim /// 1117243830Sdim /// 2. Dead def at OldIdx: 1118243830Sdim /// Hoist def+end to NewIdx, possibly move across other values. 1119243830Sdim /// 1120243830Sdim /// 3. Dead def at OldIdx AND existing def at NewIdx: 1121243830Sdim /// Remove value defined at OldIdx, coalescing it with existing value. 1122243830Sdim /// 1123243830Sdim /// 4. Live def at OldIdx AND existing def at NewIdx: 1124243830Sdim /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx. 1125243830Sdim /// (Happens when bundling multiple defs together). 1126243830Sdim /// 1127243830Sdim /// 5. Value killed at OldIdx: 1128243830Sdim /// Hoist kill to NewIdx, then scan for last kill between NewIdx and 1129243830Sdim /// OldIdx. 1130243830Sdim /// 1131296417Sdim void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { 1132243830Sdim // First look for a kill at OldIdx. 1133261991Sdim LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 1134261991Sdim LiveRange::iterator E = LR.end(); 1135261991Sdim // Is LR even live at OldIdx? 1136243830Sdim if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 1137243830Sdim return; 1138234353Sdim 1139243830Sdim // Handle a live-in value. 1140243830Sdim if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 1141243830Sdim // If the live-in value isn't killed here, there is nothing to do. 1142243830Sdim if (!SlotIndex::isSameInstr(OldIdx, I->end)) 1143243830Sdim return; 1144243830Sdim // Adjust I->end to end at NewIdx. If we are hoisting a kill above 1145243830Sdim // another use, we need to search for that use. Case 5 above. 1146243830Sdim I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 1147243830Sdim ++I; 1148243830Sdim // If OldIdx also defines a value, there couldn't have been another use. 1149243830Sdim if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { 1150243830Sdim // No def, search for the new kill. 1151243830Sdim // This can never be an early clobber kill since there is no def. 1152280031Sdim std::prev(I)->end = findLastUseBefore(Reg, LaneMask).getRegSlot(); 1153243830Sdim return; 1154193323Sed } 1155193323Sed } 1156193323Sed 1157243830Sdim // Now deal with the def at OldIdx. 1158243830Sdim assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?"); 1159243830Sdim VNInfo *DefVNI = I->valno; 1160243830Sdim assert(DefVNI->def == I->start && "Inconsistent def"); 1161243830Sdim DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 1162193323Sed 1163243830Sdim // Check for an existing def at NewIdx. 1164261991Sdim LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot()); 1165243830Sdim if (SlotIndex::isSameInstr(NewI->start, NewIdx)) { 1166243830Sdim assert(NewI->valno != DefVNI && "Same value defined more than once?"); 1167243830Sdim // There is an existing def at NewIdx. 1168243830Sdim if (I->end.isDead()) { 1169243830Sdim // Case 3: Remove the dead def at OldIdx. 1170261991Sdim LR.removeValNo(DefVNI); 1171243830Sdim return; 1172234353Sdim } 1173243830Sdim // Case 4: Replace def at NewIdx with live def at OldIdx. 1174243830Sdim I->start = DefVNI->def; 1175261991Sdim LR.removeValNo(NewI->valno); 1176243830Sdim return; 1177234353Sdim } 1178204642Srdivacky 1179243830Sdim // There is no existing def at NewIdx. Hoist DefVNI. 1180243830Sdim if (!I->end.isDead()) { 1181243830Sdim // Leave the end point of a live def. 1182243830Sdim I->start = DefVNI->def; 1183243830Sdim return; 1184234353Sdim } 1185204642Srdivacky 1186261991Sdim // DefVNI is a dead def. It may have been moved across other values in LR, 1187243830Sdim // so move I up to NewI. Slide [NewI;I) down one position. 1188276479Sdim std::copy_backward(NewI, I, std::next(I)); 1189261991Sdim *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 1190234353Sdim } 1191193323Sed 1192243830Sdim void updateRegMaskSlots() { 1193234353Sdim SmallVectorImpl<SlotIndex>::iterator RI = 1194234353Sdim std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 1195234353Sdim OldIdx); 1196243830Sdim assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && 1197243830Sdim "No RegMask at OldIdx."); 1198243830Sdim *RI = NewIdx.getRegSlot(); 1199243830Sdim assert((RI == LIS.RegMaskSlots.begin() || 1200276479Sdim SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && 1201276479Sdim "Cannot move regmask instruction above another call"); 1202276479Sdim assert((std::next(RI) == LIS.RegMaskSlots.end() || 1203276479Sdim SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && 1204276479Sdim "Cannot move regmask instruction below another call"); 1205234353Sdim } 1206193323Sed 1207234353Sdim // Return the last use of reg between NewIdx and OldIdx. 1208296417Sdim SlotIndex findLastUseBefore(unsigned Reg, LaneBitmask LaneMask) { 1209193323Sed 1210243830Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1211249423Sdim SlotIndex LastUse = NewIdx; 1212280031Sdim for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { 1213280031Sdim unsigned SubReg = MO.getSubReg(); 1214280031Sdim if (SubReg != 0 && LaneMask != 0 1215280031Sdim && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask) == 0) 1216280031Sdim continue; 1217280031Sdim 1218280031Sdim const MachineInstr *MI = MO.getParent(); 1219243830Sdim SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 1220243830Sdim if (InstSlot > LastUse && InstSlot < OldIdx) 1221243830Sdim LastUse = InstSlot; 1222193323Sed } 1223249423Sdim return LastUse; 1224249423Sdim } 1225193323Sed 1226249423Sdim // This is a regunit interval, so scanning the use list could be very 1227249423Sdim // expensive. Scan upwards from OldIdx instead. 1228249423Sdim assert(NewIdx < OldIdx && "Expected upwards move"); 1229249423Sdim SlotIndexes *Indexes = LIS.getSlotIndexes(); 1230249423Sdim MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); 1231249423Sdim 1232249423Sdim // OldIdx may not correspond to an instruction any longer, so set MII to 1233249423Sdim // point to the next instruction after OldIdx, or MBB->end(). 1234249423Sdim MachineBasicBlock::iterator MII = MBB->end(); 1235249423Sdim if (MachineInstr *MI = Indexes->getInstructionFromIndex( 1236249423Sdim Indexes->getNextNonNullIndex(OldIdx))) 1237249423Sdim if (MI->getParent() == MBB) 1238249423Sdim MII = MI; 1239249423Sdim 1240249423Sdim MachineBasicBlock::iterator Begin = MBB->begin(); 1241249423Sdim while (MII != Begin) { 1242249423Sdim if ((--MII)->isDebugValue()) 1243249423Sdim continue; 1244249423Sdim SlotIndex Idx = Indexes->getInstructionIndex(MII); 1245249423Sdim 1246249423Sdim // Stop searching when NewIdx is reached. 1247249423Sdim if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) 1248249423Sdim return NewIdx; 1249249423Sdim 1250249423Sdim // Check if MII uses Reg. 1251249423Sdim for (MIBundleOperands MO(MII); MO.isValid(); ++MO) 1252249423Sdim if (MO->isReg() && 1253249423Sdim TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && 1254249423Sdim TRI.hasRegUnit(MO->getReg(), Reg)) 1255249423Sdim return Idx; 1256193323Sed } 1257249423Sdim // Didn't reach NewIdx. It must be the first instruction in the block. 1258249423Sdim return NewIdx; 1259193323Sed } 1260234353Sdim}; 1261234353Sdim 1262243830Sdimvoid LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) { 1263243830Sdim assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 1264239462Sdim SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1265239462Sdim Indexes->removeMachineInstrFromMaps(MI); 1266243830Sdim SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); 1267234353Sdim assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1268234353Sdim OldIndex < getMBBEndIdx(MI->getParent()) && 1269234353Sdim "Cannot handle moves across basic block boundaries."); 1270234353Sdim 1271243830Sdim HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1272243830Sdim HME.updateAllRanges(MI); 1273193323Sed} 1274198090Srdivacky 1275239462Sdimvoid LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, 1276243830Sdim MachineInstr* BundleStart, 1277243830Sdim bool UpdateFlags) { 1278243830Sdim SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1279239462Sdim SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); 1280243830Sdim HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1281243830Sdim HME.updateAllRanges(MI); 1282234353Sdim} 1283249423Sdim 1284280031Sdimvoid LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, 1285280031Sdim const MachineBasicBlock::iterator End, 1286280031Sdim const SlotIndex endIdx, 1287280031Sdim LiveRange &LR, const unsigned Reg, 1288296417Sdim LaneBitmask LaneMask) { 1289280031Sdim LiveInterval::iterator LII = LR.find(endIdx); 1290280031Sdim SlotIndex lastUseIdx; 1291280031Sdim if (LII != LR.end() && LII->start < endIdx) 1292280031Sdim lastUseIdx = LII->end; 1293280031Sdim else 1294280031Sdim --LII; 1295280031Sdim 1296280031Sdim for (MachineBasicBlock::iterator I = End; I != Begin;) { 1297280031Sdim --I; 1298280031Sdim MachineInstr *MI = I; 1299280031Sdim if (MI->isDebugValue()) 1300280031Sdim continue; 1301280031Sdim 1302280031Sdim SlotIndex instrIdx = getInstructionIndex(MI); 1303280031Sdim bool isStartValid = getInstructionFromIndex(LII->start); 1304280031Sdim bool isEndValid = getInstructionFromIndex(LII->end); 1305280031Sdim 1306280031Sdim // FIXME: This doesn't currently handle early-clobber or multiple removed 1307280031Sdim // defs inside of the region to repair. 1308280031Sdim for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1309280031Sdim OE = MI->operands_end(); OI != OE; ++OI) { 1310280031Sdim const MachineOperand &MO = *OI; 1311280031Sdim if (!MO.isReg() || MO.getReg() != Reg) 1312280031Sdim continue; 1313280031Sdim 1314280031Sdim unsigned SubReg = MO.getSubReg(); 1315296417Sdim LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); 1316280031Sdim if ((Mask & LaneMask) == 0) 1317280031Sdim continue; 1318280031Sdim 1319280031Sdim if (MO.isDef()) { 1320280031Sdim if (!isStartValid) { 1321280031Sdim if (LII->end.isDead()) { 1322280031Sdim SlotIndex prevStart; 1323280031Sdim if (LII != LR.begin()) 1324280031Sdim prevStart = std::prev(LII)->start; 1325280031Sdim 1326280031Sdim // FIXME: This could be more efficient if there was a 1327280031Sdim // removeSegment method that returned an iterator. 1328280031Sdim LR.removeSegment(*LII, true); 1329280031Sdim if (prevStart.isValid()) 1330280031Sdim LII = LR.find(prevStart); 1331280031Sdim else 1332280031Sdim LII = LR.begin(); 1333280031Sdim } else { 1334280031Sdim LII->start = instrIdx.getRegSlot(); 1335280031Sdim LII->valno->def = instrIdx.getRegSlot(); 1336280031Sdim if (MO.getSubReg() && !MO.isUndef()) 1337280031Sdim lastUseIdx = instrIdx.getRegSlot(); 1338280031Sdim else 1339280031Sdim lastUseIdx = SlotIndex(); 1340280031Sdim continue; 1341280031Sdim } 1342280031Sdim } 1343280031Sdim 1344280031Sdim if (!lastUseIdx.isValid()) { 1345280031Sdim VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); 1346280031Sdim LiveRange::Segment S(instrIdx.getRegSlot(), 1347280031Sdim instrIdx.getDeadSlot(), VNI); 1348280031Sdim LII = LR.addSegment(S); 1349280031Sdim } else if (LII->start != instrIdx.getRegSlot()) { 1350280031Sdim VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); 1351280031Sdim LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); 1352280031Sdim LII = LR.addSegment(S); 1353280031Sdim } 1354280031Sdim 1355280031Sdim if (MO.getSubReg() && !MO.isUndef()) 1356280031Sdim lastUseIdx = instrIdx.getRegSlot(); 1357280031Sdim else 1358280031Sdim lastUseIdx = SlotIndex(); 1359280031Sdim } else if (MO.isUse()) { 1360280031Sdim // FIXME: This should probably be handled outside of this branch, 1361280031Sdim // either as part of the def case (for defs inside of the region) or 1362280031Sdim // after the loop over the region. 1363280031Sdim if (!isEndValid && !LII->end.isBlock()) 1364280031Sdim LII->end = instrIdx.getRegSlot(); 1365280031Sdim if (!lastUseIdx.isValid()) 1366280031Sdim lastUseIdx = instrIdx.getRegSlot(); 1367280031Sdim } 1368280031Sdim } 1369280031Sdim } 1370280031Sdim} 1371280031Sdim 1372249423Sdimvoid 1373249423SdimLiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 1374249423Sdim MachineBasicBlock::iterator Begin, 1375249423Sdim MachineBasicBlock::iterator End, 1376249423Sdim ArrayRef<unsigned> OrigRegs) { 1377249423Sdim // Find anchor points, which are at the beginning/end of blocks or at 1378249423Sdim // instructions that already have indexes. 1379249423Sdim while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) 1380249423Sdim --Begin; 1381249423Sdim while (End != MBB->end() && !Indexes->hasIndex(End)) 1382249423Sdim ++End; 1383249423Sdim 1384249423Sdim SlotIndex endIdx; 1385249423Sdim if (End == MBB->end()) 1386249423Sdim endIdx = getMBBEndIdx(MBB).getPrevSlot(); 1387249423Sdim else 1388249423Sdim endIdx = getInstructionIndex(End); 1389249423Sdim 1390249423Sdim Indexes->repairIndexesInRange(MBB, Begin, End); 1391249423Sdim 1392249423Sdim for (MachineBasicBlock::iterator I = End; I != Begin;) { 1393249423Sdim --I; 1394249423Sdim MachineInstr *MI = I; 1395249423Sdim if (MI->isDebugValue()) 1396249423Sdim continue; 1397249423Sdim for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), 1398249423Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 1399249423Sdim if (MOI->isReg() && 1400249423Sdim TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && 1401249423Sdim !hasInterval(MOI->getReg())) { 1402261991Sdim createAndComputeVirtRegInterval(MOI->getReg()); 1403249423Sdim } 1404249423Sdim } 1405249423Sdim } 1406249423Sdim 1407249423Sdim for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { 1408249423Sdim unsigned Reg = OrigRegs[i]; 1409249423Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1410249423Sdim continue; 1411249423Sdim 1412249423Sdim LiveInterval &LI = getInterval(Reg); 1413249423Sdim // FIXME: Should we support undefs that gain defs? 1414249423Sdim if (!LI.hasAtLeastOneValue()) 1415249423Sdim continue; 1416249423Sdim 1417280031Sdim for (LiveInterval::SubRange &S : LI.subranges()) { 1418280031Sdim repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); 1419249423Sdim } 1420280031Sdim repairOldRegInRange(Begin, End, endIdx, LI, Reg); 1421249423Sdim } 1422249423Sdim} 1423288943Sdim 1424288943Sdimvoid LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { 1425288943Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1426288943Sdim if (LiveRange *LR = getCachedRegUnit(*Units)) 1427288943Sdim if (VNInfo *VNI = LR->getVNInfoAt(Pos)) 1428288943Sdim LR->removeValNo(VNI); 1429288943Sdim } 1430288943Sdim} 1431288943Sdim 1432288943Sdimvoid LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { 1433288943Sdim VNInfo *VNI = LI.getVNInfoAt(Pos); 1434288943Sdim if (VNI == nullptr) 1435288943Sdim return; 1436288943Sdim LI.removeValNo(VNI); 1437288943Sdim 1438288943Sdim // Also remove the value in subranges. 1439288943Sdim for (LiveInterval::SubRange &S : LI.subranges()) { 1440288943Sdim if (VNInfo *SVNI = S.getVNInfoAt(Pos)) 1441288943Sdim S.removeValNo(SVNI); 1442288943Sdim } 1443288943Sdim LI.removeEmptySubRanges(); 1444288943Sdim} 1445296417Sdim 1446296417Sdimvoid LiveIntervals::splitSeparateComponents(LiveInterval &LI, 1447296417Sdim SmallVectorImpl<LiveInterval*> &SplitLIs) { 1448296417Sdim ConnectedVNInfoEqClasses ConEQ(*this); 1449296417Sdim unsigned NumComp = ConEQ.Classify(LI); 1450296417Sdim if (NumComp <= 1) 1451296417Sdim return; 1452296417Sdim DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); 1453296417Sdim unsigned Reg = LI.reg; 1454296417Sdim const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); 1455296417Sdim for (unsigned I = 1; I < NumComp; ++I) { 1456296417Sdim unsigned NewVReg = MRI->createVirtualRegister(RegClass); 1457296417Sdim LiveInterval &NewLI = createEmptyInterval(NewVReg); 1458296417Sdim SplitLIs.push_back(&NewLI); 1459296417Sdim } 1460296417Sdim ConEQ.Distribute(LI, SplitLIs.data(), *MRI); 1461296417Sdim} 1462