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 18234353Sdim#define DEBUG_TYPE "regalloc" 19193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20249423Sdim#include "LiveRangeCalc.h" 21249423Sdim#include "llvm/ADT/DenseSet.h" 22249423Sdim#include "llvm/ADT/STLExtras.h" 23193323Sed#include "llvm/Analysis/AliasAnalysis.h" 24193323Sed#include "llvm/CodeGen/LiveVariables.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" 31263508Sdim#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/TargetMachine.h" 38249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 39193323Sed#include <algorithm> 40249423Sdim#include <cmath> 41193323Sed#include <limits> 42193323Sedusing namespace llvm; 43193323Sed 44193323Sedchar LiveIntervals::ID = 0; 45239462Sdimchar &llvm::LiveIntervalsID = LiveIntervals::ID; 46218893SdimINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 47218893Sdim "Live Interval Analysis", false, false) 48234353SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 49218893SdimINITIALIZE_PASS_DEPENDENCY(LiveVariables) 50234353SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 51218893SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 52218893SdimINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 53218893Sdim "Live Interval Analysis", false, false) 54193323Sed 55263508Sdim#ifndef NDEBUG 56263508Sdimstatic cl::opt<bool> EnablePrecomputePhysRegs( 57263508Sdim "precompute-phys-liveness", cl::Hidden, 58263508Sdim cl::desc("Eagerly compute live intervals for all physreg units.")); 59263508Sdim#else 60263508Sdimstatic bool EnablePrecomputePhysRegs = false; 61263508Sdim#endif // NDEBUG 62263508Sdim 63193323Sedvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 64198090Srdivacky AU.setPreservesCFG(); 65193323Sed AU.addRequired<AliasAnalysis>(); 66193323Sed AU.addPreserved<AliasAnalysis>(); 67249423Sdim // LiveVariables isn't really required by this analysis, it is only required 68249423Sdim // here to make sure it is live during TwoAddressInstructionPass and 69249423Sdim // PHIElimination. This is temporary. 70212904Sdim AU.addRequired<LiveVariables>(); 71193323Sed AU.addPreserved<LiveVariables>(); 72234353Sdim AU.addPreservedID(MachineLoopInfoID); 73239462Sdim AU.addRequiredTransitiveID(MachineDominatorsID); 74193323Sed AU.addPreservedID(MachineDominatorsID); 75198892Srdivacky AU.addPreserved<SlotIndexes>(); 76198892Srdivacky AU.addRequiredTransitive<SlotIndexes>(); 77193323Sed MachineFunctionPass::getAnalysisUsage(AU); 78193323Sed} 79193323Sed 80239462SdimLiveIntervals::LiveIntervals() : MachineFunctionPass(ID), 81239462Sdim DomTree(0), LRCalc(0) { 82239462Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 83239462Sdim} 84239462Sdim 85239462SdimLiveIntervals::~LiveIntervals() { 86239462Sdim delete LRCalc; 87239462Sdim} 88239462Sdim 89193323Sedvoid LiveIntervals::releaseMemory() { 90193323Sed // Free the live intervals themselves. 91239462Sdim for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) 92239462Sdim delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; 93239462Sdim VirtRegIntervals.clear(); 94234353Sdim RegMaskSlots.clear(); 95234353Sdim RegMaskBits.clear(); 96234353Sdim RegMaskBlocks.clear(); 97198090Srdivacky 98263508Sdim for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 99263508Sdim delete RegUnitRanges[i]; 100263508Sdim RegUnitRanges.clear(); 101239462Sdim 102210299Sed // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 103210299Sed VNInfoAllocator.Reset(); 104193323Sed} 105193323Sed 106263508Sdim/// runOnMachineFunction - calculates LiveIntervals 107193323Sed/// 108193323Sedbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 109239462Sdim MF = &fn; 110239462Sdim MRI = &MF->getRegInfo(); 111239462Sdim TM = &fn.getTarget(); 112239462Sdim TRI = TM->getRegisterInfo(); 113239462Sdim TII = TM->getInstrInfo(); 114239462Sdim AA = &getAnalysis<AliasAnalysis>(); 115239462Sdim Indexes = &getAnalysis<SlotIndexes>(); 116239462Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 117239462Sdim if (!LRCalc) 118239462Sdim LRCalc = new LiveRangeCalc(); 119193323Sed 120239462Sdim // Allocate space for all virtual registers. 121239462Sdim VirtRegIntervals.resize(MRI->getNumVirtRegs()); 122193323Sed 123249423Sdim computeVirtRegs(); 124249423Sdim computeRegMasks(); 125239462Sdim computeLiveInRegUnits(); 126193323Sed 127263508Sdim if (EnablePrecomputePhysRegs) { 128263508Sdim // For stress testing, precompute live ranges of all physical register 129263508Sdim // units, including reserved registers. 130263508Sdim for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 131263508Sdim getRegUnit(i); 132263508Sdim } 133193323Sed DEBUG(dump()); 134193323Sed return true; 135193323Sed} 136193323Sed 137193323Sed/// print - Implement the dump method. 138198090Srdivackyvoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 139198090Srdivacky OS << "********** INTERVALS **********\n"; 140193323Sed 141239462Sdim // Dump the regunits. 142263508Sdim for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 143263508Sdim if (LiveRange *LR = RegUnitRanges[i]) 144263508Sdim OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; 145234353Sdim 146234353Sdim // Dump the virtregs. 147239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 148239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 149239462Sdim if (hasInterval(Reg)) 150263508Sdim OS << getInterval(Reg) << '\n'; 151239462Sdim } 152234353Sdim 153243830Sdim OS << "RegMasks:"; 154243830Sdim for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) 155243830Sdim OS << ' ' << RegMaskSlots[i]; 156243830Sdim OS << '\n'; 157243830Sdim 158198090Srdivacky printInstrs(OS); 159198090Srdivacky} 160198090Srdivacky 161198090Srdivackyvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 162198090Srdivacky OS << "********** MACHINEINSTRS **********\n"; 163239462Sdim MF->print(OS, Indexes); 164193323Sed} 165193323Sed 166243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 167198090Srdivackyvoid LiveIntervals::dumpInstrs() const { 168202375Srdivacky printInstrs(dbgs()); 169198090Srdivacky} 170243830Sdim#endif 171198090Srdivacky 172193323SedLiveInterval* LiveIntervals::createInterval(unsigned reg) { 173263508Sdim float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 174263508Sdim llvm::huge_valf : 0.0F; 175193323Sed return new LiveInterval(reg, Weight); 176193323Sed} 177193323Sed 178239462Sdim 179239462Sdim/// computeVirtRegInterval - Compute the live interval of a virtual register, 180239462Sdim/// based on defs and uses. 181263508Sdimvoid LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { 182239462Sdim assert(LRCalc && "LRCalc not initialized."); 183263508Sdim assert(LI.empty() && "Should only compute empty intervals."); 184239462Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 185239462Sdim LRCalc->createDeadDefs(LI); 186239462Sdim LRCalc->extendToUses(LI); 187193323Sed} 188193323Sed 189239462Sdimvoid LiveIntervals::computeVirtRegs() { 190239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 191239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 192239462Sdim if (MRI->reg_nodbg_empty(Reg)) 193239462Sdim continue; 194263508Sdim createAndComputeVirtRegInterval(Reg); 195239462Sdim } 196239462Sdim} 197239462Sdim 198239462Sdimvoid LiveIntervals::computeRegMasks() { 199239462Sdim RegMaskBlocks.resize(MF->getNumBlockIDs()); 200239462Sdim 201239462Sdim // Find all instructions with regmask operands. 202239462Sdim for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); 203239462Sdim MBBI != E; ++MBBI) { 204239462Sdim MachineBasicBlock *MBB = MBBI; 205239462Sdim std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 206239462Sdim RMB.first = RegMaskSlots.size(); 207239462Sdim for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end(); 208239462Sdim MI != ME; ++MI) 209239462Sdim for (MIOperands MO(MI); MO.isValid(); ++MO) { 210239462Sdim if (!MO->isRegMask()) 211239462Sdim continue; 212239462Sdim RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); 213239462Sdim RegMaskBits.push_back(MO->getRegMask()); 214239462Sdim } 215239462Sdim // Compute the number of register mask instructions in this block. 216243830Sdim RMB.second = RegMaskSlots.size() - RMB.first; 217239462Sdim } 218239462Sdim} 219239462Sdim 220239462Sdim//===----------------------------------------------------------------------===// 221239462Sdim// Register Unit Liveness 222239462Sdim//===----------------------------------------------------------------------===// 223239462Sdim// 224239462Sdim// Fixed interference typically comes from ABI boundaries: Function arguments 225239462Sdim// and return values are passed in fixed registers, and so are exception 226239462Sdim// pointers entering landing pads. Certain instructions require values to be 227239462Sdim// present in specific registers. That is also represented through fixed 228239462Sdim// interference. 229239462Sdim// 230239462Sdim 231263508Sdim/// computeRegUnitInterval - Compute the live range of a register unit, based 232263508Sdim/// on the uses and defs of aliasing registers. The range should be empty, 233239462Sdim/// or contain only dead phi-defs from ABI blocks. 234263508Sdimvoid LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { 235239462Sdim assert(LRCalc && "LRCalc not initialized."); 236239462Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 237239462Sdim 238239462Sdim // The physregs aliasing Unit are the roots and their super-registers. 239239462Sdim // Create all values as dead defs before extending to uses. Note that roots 240239462Sdim // may share super-registers. That's OK because createDeadDefs() is 241239462Sdim // idempotent. It is very rare for a register unit to have multiple roots, so 242239462Sdim // uniquing super-registers is probably not worthwhile. 243239462Sdim for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 244263508Sdim for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 245263508Sdim Supers.isValid(); ++Supers) { 246239462Sdim if (!MRI->reg_empty(*Supers)) 247263508Sdim LRCalc->createDeadDefs(LR, *Supers); 248239462Sdim } 249239462Sdim } 250239462Sdim 251263508Sdim // Now extend LR to reach all uses. 252239462Sdim // Ignore uses of reserved registers. We only track defs of those. 253239462Sdim for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 254263508Sdim for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 255263508Sdim Supers.isValid(); ++Supers) { 256239462Sdim unsigned Reg = *Supers; 257243830Sdim if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) 258263508Sdim LRCalc->extendToUses(LR, Reg); 259239462Sdim } 260239462Sdim } 261239462Sdim} 262239462Sdim 263239462Sdim 264239462Sdim/// computeLiveInRegUnits - Precompute the live ranges of any register units 265239462Sdim/// that are live-in to an ABI block somewhere. Register values can appear 266239462Sdim/// without a corresponding def when entering the entry block or a landing pad. 267239462Sdim/// 268239462Sdimvoid LiveIntervals::computeLiveInRegUnits() { 269263508Sdim RegUnitRanges.resize(TRI->getNumRegUnits()); 270239462Sdim DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); 271239462Sdim 272263508Sdim // Keep track of the live range sets allocated. 273263508Sdim SmallVector<unsigned, 8> NewRanges; 274239462Sdim 275239462Sdim // Check all basic blocks for live-ins. 276239462Sdim for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 277239462Sdim MFI != MFE; ++MFI) { 278239462Sdim const MachineBasicBlock *MBB = MFI; 279239462Sdim 280239462Sdim // We only care about ABI blocks: Entry + landing pads. 281239462Sdim if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty()) 282239462Sdim continue; 283239462Sdim 284239462Sdim // Create phi-defs at Begin for all live-in registers. 285239462Sdim SlotIndex Begin = Indexes->getMBBStartIdx(MBB); 286239462Sdim DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); 287239462Sdim for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(), 288239462Sdim LIE = MBB->livein_end(); LII != LIE; ++LII) { 289239462Sdim for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) { 290239462Sdim unsigned Unit = *Units; 291263508Sdim LiveRange *LR = RegUnitRanges[Unit]; 292263508Sdim if (!LR) { 293263508Sdim LR = RegUnitRanges[Unit] = new LiveRange(); 294263508Sdim NewRanges.push_back(Unit); 295239462Sdim } 296263508Sdim VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); 297239462Sdim (void)VNI; 298239462Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); 299239462Sdim } 300239462Sdim } 301239462Sdim DEBUG(dbgs() << '\n'); 302239462Sdim } 303263508Sdim DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); 304239462Sdim 305263508Sdim // Compute the 'normal' part of the ranges. 306263508Sdim for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { 307263508Sdim unsigned Unit = NewRanges[i]; 308263508Sdim computeRegUnitRange(*RegUnitRanges[Unit], Unit); 309263508Sdim } 310239462Sdim} 311239462Sdim 312239462Sdim 313218893Sdim/// shrinkToUses - After removing some uses of a register, shrink its live 314218893Sdim/// range to just the remaining uses. This method does not compute reaching 315218893Sdim/// defs for new uses, and it doesn't remove dead defs. 316221345Sdimbool LiveIntervals::shrinkToUses(LiveInterval *li, 317221345Sdim SmallVectorImpl<MachineInstr*> *dead) { 318218893Sdim DEBUG(dbgs() << "Shrink: " << *li << '\n'); 319218893Sdim assert(TargetRegisterInfo::isVirtualRegister(li->reg) 320234353Sdim && "Can only shrink virtual registers"); 321218893Sdim // Find all the values used, including PHI kills. 322218893Sdim SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 323218893Sdim 324226633Sdim // Blocks that have already been added to WorkList as live-out. 325226633Sdim SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 326226633Sdim 327218893Sdim // Visit all instructions reading li->reg. 328239462Sdim for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg); 329218893Sdim MachineInstr *UseMI = I.skipInstruction();) { 330218893Sdim if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 331218893Sdim continue; 332234353Sdim SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 333263508Sdim LiveQueryResult LRQ = li->Query(Idx); 334239462Sdim VNInfo *VNI = LRQ.valueIn(); 335221345Sdim if (!VNI) { 336221345Sdim // This shouldn't happen: readsVirtualRegister returns true, but there is 337221345Sdim // no live value. It is likely caused by a target getting <undef> flags 338221345Sdim // wrong. 339221345Sdim DEBUG(dbgs() << Idx << '\t' << *UseMI 340221345Sdim << "Warning: Instr claims to read non-existent value in " 341221345Sdim << *li << '\n'); 342221345Sdim continue; 343221345Sdim } 344234353Sdim // Special case: An early-clobber tied operand reads and writes the 345239462Sdim // register one slot early. 346239462Sdim if (VNInfo *DefVNI = LRQ.valueDefined()) 347239462Sdim Idx = DefVNI->def; 348239462Sdim 349218893Sdim WorkList.push_back(std::make_pair(Idx, VNI)); 350218893Sdim } 351218893Sdim 352263508Sdim // Create new live ranges with only minimal live segments per def. 353263508Sdim LiveRange NewLR; 354218893Sdim for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 355218893Sdim I != E; ++I) { 356218893Sdim VNInfo *VNI = *I; 357218893Sdim if (VNI->isUnused()) 358218893Sdim continue; 359263508Sdim NewLR.addSegment(LiveRange::Segment(VNI->def, VNI->def.getDeadSlot(), VNI)); 360218893Sdim } 361218893Sdim 362221345Sdim // Keep track of the PHIs that are in use. 363221345Sdim SmallPtrSet<VNInfo*, 8> UsedPHIs; 364221345Sdim 365218893Sdim // Extend intervals to reach all uses in WorkList. 366218893Sdim while (!WorkList.empty()) { 367218893Sdim SlotIndex Idx = WorkList.back().first; 368218893Sdim VNInfo *VNI = WorkList.back().second; 369218893Sdim WorkList.pop_back(); 370234353Sdim const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 371221345Sdim SlotIndex BlockStart = getMBBStartIdx(MBB); 372218893Sdim 373218893Sdim // Extend the live range for VNI to be live at Idx. 374263508Sdim if (VNInfo *ExtVNI = NewLR.extendInBlock(BlockStart, Idx)) { 375221345Sdim (void)ExtVNI; 376221345Sdim assert(ExtVNI == VNI && "Unexpected existing value number"); 377221345Sdim // Is this a PHIDef we haven't seen before? 378221345Sdim if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 379221345Sdim continue; 380221345Sdim // The PHI is live, make sure the predecessors are live-out. 381221345Sdim for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 382221345Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 383226633Sdim if (!LiveOut.insert(*PI)) 384226633Sdim continue; 385234353Sdim SlotIndex Stop = getMBBEndIdx(*PI); 386221345Sdim // A predecessor is not required to have a live-out value for a PHI. 387234353Sdim if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 388221345Sdim WorkList.push_back(std::make_pair(Stop, PVNI)); 389218893Sdim } 390218893Sdim continue; 391218893Sdim } 392218893Sdim 393218893Sdim // VNI is live-in to MBB. 394218893Sdim DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 395263508Sdim NewLR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); 396218893Sdim 397218893Sdim // Make sure VNI is live-out from the predecessors. 398218893Sdim for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 399218893Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 400226633Sdim if (!LiveOut.insert(*PI)) 401226633Sdim continue; 402234353Sdim SlotIndex Stop = getMBBEndIdx(*PI); 403234353Sdim assert(li->getVNInfoBefore(Stop) == VNI && 404234353Sdim "Wrong value out of predecessor"); 405218893Sdim WorkList.push_back(std::make_pair(Stop, VNI)); 406218893Sdim } 407218893Sdim } 408218893Sdim 409218893Sdim // Handle dead values. 410221345Sdim bool CanSeparate = false; 411218893Sdim for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 412218893Sdim I != E; ++I) { 413218893Sdim VNInfo *VNI = *I; 414218893Sdim if (VNI->isUnused()) 415218893Sdim continue; 416263508Sdim LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def); 417263508Sdim assert(LRI != NewLR.end() && "Missing segment for PHI"); 418263508Sdim if (LRI->end != VNI->def.getDeadSlot()) 419218893Sdim continue; 420221345Sdim if (VNI->isPHIDef()) { 421218893Sdim // This is a dead PHI. Remove it. 422239462Sdim VNI->markUnused(); 423263508Sdim NewLR.removeSegment(LRI->start, LRI->end); 424221345Sdim DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 425221345Sdim CanSeparate = true; 426218893Sdim } else { 427218893Sdim // This is a dead def. Make sure the instruction knows. 428218893Sdim MachineInstr *MI = getInstructionFromIndex(VNI->def); 429218893Sdim assert(MI && "No instruction defining live value"); 430239462Sdim MI->addRegisterDead(li->reg, TRI); 431221345Sdim if (dead && MI->allDefsAreDead()) { 432221345Sdim DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 433221345Sdim dead->push_back(MI); 434221345Sdim } 435218893Sdim } 436218893Sdim } 437218893Sdim 438263508Sdim // Move the trimmed segments back. 439263508Sdim li->segments.swap(NewLR.segments); 440221345Sdim DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 441221345Sdim return CanSeparate; 442218893Sdim} 443218893Sdim 444263508Sdimvoid LiveIntervals::extendToIndices(LiveRange &LR, 445243830Sdim ArrayRef<SlotIndex> Indices) { 446243830Sdim assert(LRCalc && "LRCalc not initialized."); 447243830Sdim LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 448243830Sdim for (unsigned i = 0, e = Indices.size(); i != e; ++i) 449263508Sdim LRCalc->extend(LR, Indices[i]); 450243830Sdim} 451218893Sdim 452243830Sdimvoid LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, 453243830Sdim SmallVectorImpl<SlotIndex> *EndPoints) { 454263508Sdim LiveQueryResult LRQ = LI->Query(Kill); 455243830Sdim VNInfo *VNI = LRQ.valueOut(); 456243830Sdim if (!VNI) 457243830Sdim return; 458243830Sdim 459243830Sdim MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); 460243830Sdim SlotIndex MBBStart, MBBEnd; 461243830Sdim tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); 462243830Sdim 463243830Sdim // If VNI isn't live out from KillMBB, the value is trivially pruned. 464243830Sdim if (LRQ.endPoint() < MBBEnd) { 465263508Sdim LI->removeSegment(Kill, LRQ.endPoint()); 466243830Sdim if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 467243830Sdim return; 468243830Sdim } 469243830Sdim 470243830Sdim // VNI is live out of KillMBB. 471263508Sdim LI->removeSegment(Kill, MBBEnd); 472243830Sdim if (EndPoints) EndPoints->push_back(MBBEnd); 473243830Sdim 474243830Sdim // Find all blocks that are reachable from KillMBB without leaving VNI's live 475243830Sdim // range. It is possible that KillMBB itself is reachable, so start a DFS 476243830Sdim // from each successor. 477243830Sdim typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy; 478243830Sdim VisitedTy Visited; 479243830Sdim for (MachineBasicBlock::succ_iterator 480243830Sdim SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end(); 481243830Sdim SuccI != SuccE; ++SuccI) { 482243830Sdim for (df_ext_iterator<MachineBasicBlock*, VisitedTy> 483243830Sdim I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); 484243830Sdim I != E;) { 485243830Sdim MachineBasicBlock *MBB = *I; 486243830Sdim 487243830Sdim // Check if VNI is live in to MBB. 488243830Sdim tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); 489263508Sdim LiveQueryResult LRQ = LI->Query(MBBStart); 490243830Sdim if (LRQ.valueIn() != VNI) { 491263508Sdim // This block isn't part of the VNI segment. Prune the search. 492243830Sdim I.skipChildren(); 493243830Sdim continue; 494243830Sdim } 495243830Sdim 496243830Sdim // Prune the search if VNI is killed in MBB. 497243830Sdim if (LRQ.endPoint() < MBBEnd) { 498263508Sdim LI->removeSegment(MBBStart, LRQ.endPoint()); 499243830Sdim if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 500243830Sdim I.skipChildren(); 501243830Sdim continue; 502243830Sdim } 503243830Sdim 504243830Sdim // VNI is live through MBB. 505263508Sdim LI->removeSegment(MBBStart, MBBEnd); 506243830Sdim if (EndPoints) EndPoints->push_back(MBBEnd); 507243830Sdim ++I; 508243830Sdim } 509243830Sdim } 510243830Sdim} 511243830Sdim 512193323Sed//===----------------------------------------------------------------------===// 513193323Sed// Register allocator hooks. 514193323Sed// 515193323Sed 516243830Sdimvoid LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 517243830Sdim // Keep track of regunit ranges. 518263508Sdim SmallVector<std::pair<LiveRange*, LiveRange::iterator>, 8> RU; 519243830Sdim 520239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 521239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 522239462Sdim if (MRI->reg_nodbg_empty(Reg)) 523218893Sdim continue; 524239462Sdim LiveInterval *LI = &getInterval(Reg); 525243830Sdim if (LI->empty()) 526243830Sdim continue; 527218893Sdim 528243830Sdim // Find the regunit intervals for the assigned register. They may overlap 529243830Sdim // the virtual register live range, cancelling any kills. 530243830Sdim RU.clear(); 531243830Sdim for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); 532243830Sdim ++Units) { 533263508Sdim LiveRange &RURanges = getRegUnit(*Units); 534263508Sdim if (RURanges.empty()) 535243830Sdim continue; 536263508Sdim RU.push_back(std::make_pair(&RURanges, RURanges.find(LI->begin()->end))); 537243830Sdim } 538243830Sdim 539263508Sdim // Every instruction that kills Reg corresponds to a segment range end 540263508Sdim // point. 541218893Sdim for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 542218893Sdim ++RI) { 543234353Sdim // A block index indicates an MBB edge. 544234353Sdim if (RI->end.isBlock()) 545218893Sdim continue; 546218893Sdim MachineInstr *MI = getInstructionFromIndex(RI->end); 547218893Sdim if (!MI) 548218893Sdim continue; 549243830Sdim 550263508Sdim // Check if any of the regunits are live beyond the end of RI. That could 551243830Sdim // happen when a physreg is defined as a copy of a virtreg: 552243830Sdim // 553243830Sdim // %EAX = COPY %vreg5 554243830Sdim // FOO %vreg5 <--- MI, cancel kill because %EAX is live. 555243830Sdim // BAR %EAX<kill> 556243830Sdim // 557243830Sdim // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. 558243830Sdim bool CancelKill = false; 559243830Sdim for (unsigned u = 0, e = RU.size(); u != e; ++u) { 560263508Sdim LiveRange &RRanges = *RU[u].first; 561263508Sdim LiveRange::iterator &I = RU[u].second; 562263508Sdim if (I == RRanges.end()) 563243830Sdim continue; 564263508Sdim I = RRanges.advanceTo(I, RI->end); 565263508Sdim if (I == RRanges.end() || I->start >= RI->end) 566243830Sdim continue; 567243830Sdim // I is overlapping RI. 568243830Sdim CancelKill = true; 569243830Sdim break; 570243830Sdim } 571243830Sdim if (CancelKill) 572243830Sdim MI->clearRegisterKills(Reg, NULL); 573243830Sdim else 574243830Sdim MI->addRegisterKilled(Reg, NULL); 575218893Sdim } 576218893Sdim } 577218893Sdim} 578218893Sdim 579234353SdimMachineBasicBlock* 580234353SdimLiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 581234353Sdim // A local live range must be fully contained inside the block, meaning it is 582234353Sdim // defined and killed at instructions, not at block boundaries. It is not 583234353Sdim // live in or or out of any block. 584234353Sdim // 585234353Sdim // It is technically possible to have a PHI-defined live range identical to a 586234353Sdim // single block, but we are going to return false in that case. 587193323Sed 588234353Sdim SlotIndex Start = LI.beginIndex(); 589234353Sdim if (Start.isBlock()) 590234353Sdim return NULL; 591212904Sdim 592234353Sdim SlotIndex Stop = LI.endIndex(); 593234353Sdim if (Stop.isBlock()) 594234353Sdim return NULL; 595193323Sed 596234353Sdim // getMBBFromIndex doesn't need to search the MBB table when both indexes 597234353Sdim // belong to proper instructions. 598239462Sdim MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); 599239462Sdim MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); 600234353Sdim return MBB1 == MBB2 ? MBB1 : NULL; 601234353Sdim} 602193323Sed 603239462Sdimbool 604239462SdimLiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { 605239462Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 606239462Sdim I != E; ++I) { 607239462Sdim const VNInfo *PHI = *I; 608239462Sdim if (PHI->isUnused() || !PHI->isPHIDef()) 609239462Sdim continue; 610239462Sdim const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 611239462Sdim // Conservatively return true instead of scanning huge predecessor lists. 612239462Sdim if (PHIMBB->pred_size() > 100) 613239462Sdim return true; 614239462Sdim for (MachineBasicBlock::const_pred_iterator 615239462Sdim PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) 616239462Sdim if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) 617239462Sdim return true; 618239462Sdim } 619239462Sdim return false; 620239462Sdim} 621239462Sdim 622234353Sdimfloat 623263508SdimLiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) { 624263508Sdim const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); 625263508Sdim return (isDef + isUse) * (freq.getFrequency() * Scale); 626193323Sed} 627193323Sed 628263508SdimLiveRange::Segment 629263508SdimLiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) { 630263508Sdim LiveInterval& Interval = createEmptyInterval(reg); 631234353Sdim VNInfo* VN = Interval.getNextValue( 632234353Sdim SlotIndex(getInstructionIndex(startInst).getRegSlot()), 633234353Sdim getVNInfoAllocator()); 634263508Sdim LiveRange::Segment S( 635234353Sdim SlotIndex(getInstructionIndex(startInst).getRegSlot()), 636234353Sdim getMBBEndIdx(startInst->getParent()), VN); 637263508Sdim Interval.addSegment(S); 638193323Sed 639263508Sdim return S; 640193323Sed} 641193323Sed 642198892Srdivacky 643234353Sdim//===----------------------------------------------------------------------===// 644234353Sdim// Register mask functions 645234353Sdim//===----------------------------------------------------------------------===// 646198892Srdivacky 647234353Sdimbool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 648234353Sdim BitVector &UsableRegs) { 649234353Sdim if (LI.empty()) 650198892Srdivacky return false; 651234353Sdim LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 652198892Srdivacky 653234353Sdim // Use a smaller arrays for local live ranges. 654234353Sdim ArrayRef<SlotIndex> Slots; 655234353Sdim ArrayRef<const uint32_t*> Bits; 656234353Sdim if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 657234353Sdim Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 658234353Sdim Bits = getRegMaskBitsInBlock(MBB->getNumber()); 659234353Sdim } else { 660234353Sdim Slots = getRegMaskSlots(); 661234353Sdim Bits = getRegMaskBits(); 662193323Sed } 663198892Srdivacky 664234353Sdim // We are going to enumerate all the register mask slots contained in LI. 665234353Sdim // Start with a binary search of RegMaskSlots to find a starting point. 666234353Sdim ArrayRef<SlotIndex>::iterator SlotI = 667234353Sdim std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 668234353Sdim ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 669193323Sed 670234353Sdim // No slots in range, LI begins after the last call. 671234353Sdim if (SlotI == SlotE) 672234353Sdim return false; 673234353Sdim 674234353Sdim bool Found = false; 675234353Sdim for (;;) { 676234353Sdim assert(*SlotI >= LiveI->start); 677234353Sdim // Loop over all slots overlapping this segment. 678234353Sdim while (*SlotI < LiveI->end) { 679234353Sdim // *SlotI overlaps LI. Collect mask bits. 680234353Sdim if (!Found) { 681234353Sdim // This is the first overlap. Initialize UsableRegs to all ones. 682234353Sdim UsableRegs.clear(); 683239462Sdim UsableRegs.resize(TRI->getNumRegs(), true); 684234353Sdim Found = true; 685234353Sdim } 686234353Sdim // Remove usable registers clobbered by this mask. 687234353Sdim UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 688234353Sdim if (++SlotI == SlotE) 689234353Sdim return Found; 690234353Sdim } 691234353Sdim // *SlotI is beyond the current LI segment. 692234353Sdim LiveI = LI.advanceTo(LiveI, *SlotI); 693234353Sdim if (LiveI == LiveE) 694234353Sdim return Found; 695234353Sdim // Advance SlotI until it overlaps. 696234353Sdim while (*SlotI < LiveI->start) 697234353Sdim if (++SlotI == SlotE) 698234353Sdim return Found; 699193323Sed } 700193323Sed} 701193323Sed 702234353Sdim//===----------------------------------------------------------------------===// 703234353Sdim// IntervalUpdate class. 704234353Sdim//===----------------------------------------------------------------------===// 705193323Sed 706234353Sdim// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 707234353Sdimclass LiveIntervals::HMEditor { 708234353Sdimprivate: 709234353Sdim LiveIntervals& LIS; 710234353Sdim const MachineRegisterInfo& MRI; 711234353Sdim const TargetRegisterInfo& TRI; 712243830Sdim SlotIndex OldIdx; 713234353Sdim SlotIndex NewIdx; 714263508Sdim SmallPtrSet<LiveRange*, 8> Updated; 715243830Sdim bool UpdateFlags; 716193323Sed 717234353Sdimpublic: 718234353Sdim HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 719243830Sdim const TargetRegisterInfo& TRI, 720243830Sdim SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) 721243830Sdim : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), 722243830Sdim UpdateFlags(UpdateFlags) {} 723199989Srdivacky 724243830Sdim // FIXME: UpdateFlags is a workaround that creates live intervals for all 725243830Sdim // physregs, even those that aren't needed for regalloc, in order to update 726243830Sdim // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 727243830Sdim // flags, and postRA passes will use a live register utility instead. 728263508Sdim LiveRange *getRegUnitLI(unsigned Unit) { 729243830Sdim if (UpdateFlags) 730243830Sdim return &LIS.getRegUnit(Unit); 731243830Sdim return LIS.getCachedRegUnit(Unit); 732234353Sdim } 733193323Sed 734243830Sdim /// Update all live ranges touched by MI, assuming a move from OldIdx to 735243830Sdim /// NewIdx. 736243830Sdim void updateAllRanges(MachineInstr *MI) { 737243830Sdim DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); 738243830Sdim bool hasRegMask = false; 739243830Sdim for (MIOperands MO(MI); MO.isValid(); ++MO) { 740243830Sdim if (MO->isRegMask()) 741243830Sdim hasRegMask = true; 742243830Sdim if (!MO->isReg()) 743243830Sdim continue; 744243830Sdim // Aggressively clear all kill flags. 745243830Sdim // They are reinserted by VirtRegRewriter. 746243830Sdim if (MO->isUse()) 747243830Sdim MO->setIsKill(false); 748193323Sed 749243830Sdim unsigned Reg = MO->getReg(); 750243830Sdim if (!Reg) 751243830Sdim continue; 752243830Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 753263508Sdim LiveInterval &LI = LIS.getInterval(Reg); 754263508Sdim updateRange(LI, Reg); 755243830Sdim continue; 756243830Sdim } 757193323Sed 758243830Sdim // For physregs, only update the regunits that actually have a 759243830Sdim // precomputed live range. 760243830Sdim for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 761263508Sdim if (LiveRange *LR = getRegUnitLI(*Units)) 762263508Sdim updateRange(*LR, *Units); 763193323Sed } 764243830Sdim if (hasRegMask) 765243830Sdim updateRegMaskSlots(); 766193323Sed } 767193323Sed 768234353Sdimprivate: 769243830Sdim /// Update a single live range, assuming an instruction has been moved from 770243830Sdim /// OldIdx to NewIdx. 771263508Sdim void updateRange(LiveRange &LR, unsigned Reg) { 772263508Sdim if (!Updated.insert(&LR)) 773243830Sdim return; 774243830Sdim DEBUG({ 775243830Sdim dbgs() << " "; 776263508Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) 777263508Sdim dbgs() << PrintReg(Reg); 778243830Sdim else 779263508Sdim dbgs() << PrintRegUnit(Reg, &TRI); 780263508Sdim dbgs() << ":\t" << LR << '\n'; 781243830Sdim }); 782243830Sdim if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) 783263508Sdim handleMoveDown(LR); 784243830Sdim else 785263508Sdim handleMoveUp(LR, Reg); 786263508Sdim DEBUG(dbgs() << " -->\t" << LR << '\n'); 787263508Sdim LR.verify(); 788243830Sdim } 789193323Sed 790263508Sdim /// Update LR to reflect an instruction has been moved downwards from OldIdx 791243830Sdim /// to NewIdx. 792243830Sdim /// 793243830Sdim /// 1. Live def at OldIdx: 794243830Sdim /// Move def to NewIdx, assert endpoint after NewIdx. 795243830Sdim /// 796243830Sdim /// 2. Live def at OldIdx, killed at NewIdx: 797243830Sdim /// Change to dead def at NewIdx. 798243830Sdim /// (Happens when bundling def+kill together). 799243830Sdim /// 800243830Sdim /// 3. Dead def at OldIdx: 801243830Sdim /// Move def to NewIdx, possibly across another live value. 802243830Sdim /// 803243830Sdim /// 4. Def at OldIdx AND at NewIdx: 804263508Sdim /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx. 805243830Sdim /// (Happens when bundling multiple defs together). 806243830Sdim /// 807243830Sdim /// 5. Value read at OldIdx, killed before NewIdx: 808243830Sdim /// Extend kill to NewIdx. 809243830Sdim /// 810263508Sdim void handleMoveDown(LiveRange &LR) { 811243830Sdim // First look for a kill at OldIdx. 812263508Sdim LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 813263508Sdim LiveRange::iterator E = LR.end(); 814263508Sdim // Is LR even live at OldIdx? 815243830Sdim if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 816243830Sdim return; 817243830Sdim 818243830Sdim // Handle a live-in value. 819243830Sdim if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 820243830Sdim bool isKill = SlotIndex::isSameInstr(OldIdx, I->end); 821243830Sdim // If the live-in value already extends to NewIdx, there is nothing to do. 822243830Sdim if (!SlotIndex::isEarlierInstr(I->end, NewIdx)) 823234353Sdim return; 824243830Sdim // Aggressively remove all kill flags from the old kill point. 825243830Sdim // Kill flags shouldn't be used while live intervals exist, they will be 826243830Sdim // reinserted by VirtRegRewriter. 827243830Sdim if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end)) 828243830Sdim for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) 829243830Sdim if (MO->isReg() && MO->isUse()) 830243830Sdim MO->setIsKill(false); 831263508Sdim // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by 832243830Sdim // overlapping ranges. Case 5 above. 833243830Sdim I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 834243830Sdim // If this was a kill, there may also be a def. Otherwise we're done. 835243830Sdim if (!isKill) 836234353Sdim return; 837243830Sdim ++I; 838193323Sed } 839193323Sed 840243830Sdim // Check for a def at OldIdx. 841243830Sdim if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start)) 842243830Sdim return; 843243830Sdim // We have a def at OldIdx. 844243830Sdim VNInfo *DefVNI = I->valno; 845243830Sdim assert(DefVNI->def == I->start && "Inconsistent def"); 846243830Sdim DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 847243830Sdim // If the defined value extends beyond NewIdx, just move the def down. 848243830Sdim // This is case 1 above. 849243830Sdim if (SlotIndex::isEarlierInstr(NewIdx, I->end)) { 850243830Sdim I->start = DefVNI->def; 851243830Sdim return; 852193323Sed } 853243830Sdim // The remaining possibilities are now: 854243830Sdim // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx). 855243830Sdim // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot(). 856243830Sdim // In either case, it is possible that there is an existing def at NewIdx. 857243830Sdim assert((I->end == OldIdx.getDeadSlot() || 858243830Sdim SlotIndex::isSameInstr(I->end, NewIdx)) && 859243830Sdim "Cannot move def below kill"); 860263508Sdim LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot()); 861243830Sdim if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) { 862243830Sdim // There is an existing def at NewIdx, case 4 above. The def at OldIdx is 863243830Sdim // coalesced into that value. 864243830Sdim assert(NewI->valno != DefVNI && "Multiple defs of value?"); 865263508Sdim LR.removeValNo(DefVNI); 866243830Sdim return; 867243830Sdim } 868243830Sdim // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. 869263508Sdim // If the def at OldIdx was dead, we allow it to be moved across other LR 870243830Sdim // values. The new range should be placed immediately before NewI, move any 871243830Sdim // intermediate ranges up. 872243830Sdim assert(NewI != I && "Inconsistent iterators"); 873243830Sdim std::copy(llvm::next(I), NewI, I); 874263508Sdim *llvm::prior(NewI) 875263508Sdim = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 876243830Sdim } 877193323Sed 878263508Sdim /// Update LR to reflect an instruction has been moved upwards from OldIdx 879243830Sdim /// to NewIdx. 880243830Sdim /// 881243830Sdim /// 1. Live def at OldIdx: 882243830Sdim /// Hoist def to NewIdx. 883243830Sdim /// 884243830Sdim /// 2. Dead def at OldIdx: 885243830Sdim /// Hoist def+end to NewIdx, possibly move across other values. 886243830Sdim /// 887243830Sdim /// 3. Dead def at OldIdx AND existing def at NewIdx: 888243830Sdim /// Remove value defined at OldIdx, coalescing it with existing value. 889243830Sdim /// 890243830Sdim /// 4. Live def at OldIdx AND existing def at NewIdx: 891243830Sdim /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx. 892243830Sdim /// (Happens when bundling multiple defs together). 893243830Sdim /// 894243830Sdim /// 5. Value killed at OldIdx: 895243830Sdim /// Hoist kill to NewIdx, then scan for last kill between NewIdx and 896243830Sdim /// OldIdx. 897243830Sdim /// 898263508Sdim void handleMoveUp(LiveRange &LR, unsigned Reg) { 899243830Sdim // First look for a kill at OldIdx. 900263508Sdim LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 901263508Sdim LiveRange::iterator E = LR.end(); 902263508Sdim // Is LR even live at OldIdx? 903243830Sdim if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 904243830Sdim return; 905234353Sdim 906243830Sdim // Handle a live-in value. 907243830Sdim if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 908243830Sdim // If the live-in value isn't killed here, there is nothing to do. 909243830Sdim if (!SlotIndex::isSameInstr(OldIdx, I->end)) 910243830Sdim return; 911243830Sdim // Adjust I->end to end at NewIdx. If we are hoisting a kill above 912243830Sdim // another use, we need to search for that use. Case 5 above. 913243830Sdim I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 914243830Sdim ++I; 915243830Sdim // If OldIdx also defines a value, there couldn't have been another use. 916243830Sdim if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { 917243830Sdim // No def, search for the new kill. 918243830Sdim // This can never be an early clobber kill since there is no def. 919263508Sdim llvm::prior(I)->end = findLastUseBefore(Reg).getRegSlot(); 920243830Sdim return; 921193323Sed } 922193323Sed } 923193323Sed 924243830Sdim // Now deal with the def at OldIdx. 925243830Sdim assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?"); 926243830Sdim VNInfo *DefVNI = I->valno; 927243830Sdim assert(DefVNI->def == I->start && "Inconsistent def"); 928243830Sdim DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 929193323Sed 930243830Sdim // Check for an existing def at NewIdx. 931263508Sdim LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot()); 932243830Sdim if (SlotIndex::isSameInstr(NewI->start, NewIdx)) { 933243830Sdim assert(NewI->valno != DefVNI && "Same value defined more than once?"); 934243830Sdim // There is an existing def at NewIdx. 935243830Sdim if (I->end.isDead()) { 936243830Sdim // Case 3: Remove the dead def at OldIdx. 937263508Sdim LR.removeValNo(DefVNI); 938243830Sdim return; 939234353Sdim } 940243830Sdim // Case 4: Replace def at NewIdx with live def at OldIdx. 941243830Sdim I->start = DefVNI->def; 942263508Sdim LR.removeValNo(NewI->valno); 943243830Sdim return; 944234353Sdim } 945204642Srdivacky 946243830Sdim // There is no existing def at NewIdx. Hoist DefVNI. 947243830Sdim if (!I->end.isDead()) { 948243830Sdim // Leave the end point of a live def. 949243830Sdim I->start = DefVNI->def; 950243830Sdim return; 951234353Sdim } 952204642Srdivacky 953263508Sdim // DefVNI is a dead def. It may have been moved across other values in LR, 954243830Sdim // so move I up to NewI. Slide [NewI;I) down one position. 955243830Sdim std::copy_backward(NewI, I, llvm::next(I)); 956263508Sdim *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 957234353Sdim } 958193323Sed 959243830Sdim void updateRegMaskSlots() { 960234353Sdim SmallVectorImpl<SlotIndex>::iterator RI = 961234353Sdim std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 962234353Sdim OldIdx); 963243830Sdim assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && 964243830Sdim "No RegMask at OldIdx."); 965243830Sdim *RI = NewIdx.getRegSlot(); 966243830Sdim assert((RI == LIS.RegMaskSlots.begin() || 967243830Sdim SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) && 968243830Sdim "Cannot move regmask instruction above another call"); 969243830Sdim assert((llvm::next(RI) == LIS.RegMaskSlots.end() || 970243830Sdim SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) && 971243830Sdim "Cannot move regmask instruction below another call"); 972234353Sdim } 973193323Sed 974234353Sdim // Return the last use of reg between NewIdx and OldIdx. 975243830Sdim SlotIndex findLastUseBefore(unsigned Reg) { 976193323Sed 977243830Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 978249423Sdim SlotIndex LastUse = NewIdx; 979243830Sdim for (MachineRegisterInfo::use_nodbg_iterator 980243830Sdim UI = MRI.use_nodbg_begin(Reg), 981243830Sdim UE = MRI.use_nodbg_end(); 982243830Sdim UI != UE; UI.skipInstruction()) { 983243830Sdim const MachineInstr* MI = &*UI; 984243830Sdim SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 985243830Sdim if (InstSlot > LastUse && InstSlot < OldIdx) 986243830Sdim LastUse = InstSlot; 987193323Sed } 988249423Sdim return LastUse; 989249423Sdim } 990193323Sed 991249423Sdim // This is a regunit interval, so scanning the use list could be very 992249423Sdim // expensive. Scan upwards from OldIdx instead. 993249423Sdim assert(NewIdx < OldIdx && "Expected upwards move"); 994249423Sdim SlotIndexes *Indexes = LIS.getSlotIndexes(); 995249423Sdim MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); 996249423Sdim 997249423Sdim // OldIdx may not correspond to an instruction any longer, so set MII to 998249423Sdim // point to the next instruction after OldIdx, or MBB->end(). 999249423Sdim MachineBasicBlock::iterator MII = MBB->end(); 1000249423Sdim if (MachineInstr *MI = Indexes->getInstructionFromIndex( 1001249423Sdim Indexes->getNextNonNullIndex(OldIdx))) 1002249423Sdim if (MI->getParent() == MBB) 1003249423Sdim MII = MI; 1004249423Sdim 1005249423Sdim MachineBasicBlock::iterator Begin = MBB->begin(); 1006249423Sdim while (MII != Begin) { 1007249423Sdim if ((--MII)->isDebugValue()) 1008249423Sdim continue; 1009249423Sdim SlotIndex Idx = Indexes->getInstructionIndex(MII); 1010249423Sdim 1011249423Sdim // Stop searching when NewIdx is reached. 1012249423Sdim if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) 1013249423Sdim return NewIdx; 1014249423Sdim 1015249423Sdim // Check if MII uses Reg. 1016249423Sdim for (MIBundleOperands MO(MII); MO.isValid(); ++MO) 1017249423Sdim if (MO->isReg() && 1018249423Sdim TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && 1019249423Sdim TRI.hasRegUnit(MO->getReg(), Reg)) 1020249423Sdim return Idx; 1021193323Sed } 1022249423Sdim // Didn't reach NewIdx. It must be the first instruction in the block. 1023249423Sdim return NewIdx; 1024193323Sed } 1025234353Sdim}; 1026234353Sdim 1027243830Sdimvoid LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) { 1028243830Sdim assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 1029239462Sdim SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1030239462Sdim Indexes->removeMachineInstrFromMaps(MI); 1031243830Sdim SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); 1032234353Sdim assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1033234353Sdim OldIndex < getMBBEndIdx(MI->getParent()) && 1034234353Sdim "Cannot handle moves across basic block boundaries."); 1035234353Sdim 1036243830Sdim HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1037243830Sdim HME.updateAllRanges(MI); 1038193323Sed} 1039198090Srdivacky 1040239462Sdimvoid LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, 1041243830Sdim MachineInstr* BundleStart, 1042243830Sdim bool UpdateFlags) { 1043243830Sdim SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1044239462Sdim SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); 1045243830Sdim HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1046243830Sdim HME.updateAllRanges(MI); 1047234353Sdim} 1048249423Sdim 1049249423Sdimvoid 1050249423SdimLiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 1051249423Sdim MachineBasicBlock::iterator Begin, 1052249423Sdim MachineBasicBlock::iterator End, 1053249423Sdim ArrayRef<unsigned> OrigRegs) { 1054249423Sdim // Find anchor points, which are at the beginning/end of blocks or at 1055249423Sdim // instructions that already have indexes. 1056249423Sdim while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) 1057249423Sdim --Begin; 1058249423Sdim while (End != MBB->end() && !Indexes->hasIndex(End)) 1059249423Sdim ++End; 1060249423Sdim 1061249423Sdim SlotIndex endIdx; 1062249423Sdim if (End == MBB->end()) 1063249423Sdim endIdx = getMBBEndIdx(MBB).getPrevSlot(); 1064249423Sdim else 1065249423Sdim endIdx = getInstructionIndex(End); 1066249423Sdim 1067249423Sdim Indexes->repairIndexesInRange(MBB, Begin, End); 1068249423Sdim 1069249423Sdim for (MachineBasicBlock::iterator I = End; I != Begin;) { 1070249423Sdim --I; 1071249423Sdim MachineInstr *MI = I; 1072249423Sdim if (MI->isDebugValue()) 1073249423Sdim continue; 1074249423Sdim for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), 1075249423Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 1076249423Sdim if (MOI->isReg() && 1077249423Sdim TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && 1078249423Sdim !hasInterval(MOI->getReg())) { 1079263508Sdim createAndComputeVirtRegInterval(MOI->getReg()); 1080249423Sdim } 1081249423Sdim } 1082249423Sdim } 1083249423Sdim 1084249423Sdim for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { 1085249423Sdim unsigned Reg = OrigRegs[i]; 1086249423Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1087249423Sdim continue; 1088249423Sdim 1089249423Sdim LiveInterval &LI = getInterval(Reg); 1090249423Sdim // FIXME: Should we support undefs that gain defs? 1091249423Sdim if (!LI.hasAtLeastOneValue()) 1092249423Sdim continue; 1093249423Sdim 1094249423Sdim LiveInterval::iterator LII = LI.find(endIdx); 1095249423Sdim SlotIndex lastUseIdx; 1096249423Sdim if (LII != LI.end() && LII->start < endIdx) 1097249423Sdim lastUseIdx = LII->end; 1098249423Sdim else 1099249423Sdim --LII; 1100249423Sdim 1101249423Sdim for (MachineBasicBlock::iterator I = End; I != Begin;) { 1102249423Sdim --I; 1103249423Sdim MachineInstr *MI = I; 1104249423Sdim if (MI->isDebugValue()) 1105249423Sdim continue; 1106249423Sdim 1107249423Sdim SlotIndex instrIdx = getInstructionIndex(MI); 1108249423Sdim bool isStartValid = getInstructionFromIndex(LII->start); 1109249423Sdim bool isEndValid = getInstructionFromIndex(LII->end); 1110249423Sdim 1111249423Sdim // FIXME: This doesn't currently handle early-clobber or multiple removed 1112249423Sdim // defs inside of the region to repair. 1113249423Sdim for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1114249423Sdim OE = MI->operands_end(); OI != OE; ++OI) { 1115249423Sdim const MachineOperand &MO = *OI; 1116249423Sdim if (!MO.isReg() || MO.getReg() != Reg) 1117249423Sdim continue; 1118249423Sdim 1119249423Sdim if (MO.isDef()) { 1120249423Sdim if (!isStartValid) { 1121249423Sdim if (LII->end.isDead()) { 1122249423Sdim SlotIndex prevStart; 1123249423Sdim if (LII != LI.begin()) 1124249423Sdim prevStart = llvm::prior(LII)->start; 1125249423Sdim 1126263508Sdim // FIXME: This could be more efficient if there was a 1127263508Sdim // removeSegment method that returned an iterator. 1128263508Sdim LI.removeSegment(*LII, true); 1129249423Sdim if (prevStart.isValid()) 1130249423Sdim LII = LI.find(prevStart); 1131249423Sdim else 1132249423Sdim LII = LI.begin(); 1133249423Sdim } else { 1134249423Sdim LII->start = instrIdx.getRegSlot(); 1135249423Sdim LII->valno->def = instrIdx.getRegSlot(); 1136249423Sdim if (MO.getSubReg() && !MO.isUndef()) 1137249423Sdim lastUseIdx = instrIdx.getRegSlot(); 1138249423Sdim else 1139249423Sdim lastUseIdx = SlotIndex(); 1140249423Sdim continue; 1141249423Sdim } 1142249423Sdim } 1143249423Sdim 1144249423Sdim if (!lastUseIdx.isValid()) { 1145249423Sdim VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1146249423Sdim VNInfoAllocator); 1147263508Sdim LiveRange::Segment S(instrIdx.getRegSlot(), 1148263508Sdim instrIdx.getDeadSlot(), VNI); 1149263508Sdim LII = LI.addSegment(S); 1150249423Sdim } else if (LII->start != instrIdx.getRegSlot()) { 1151249423Sdim VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1152249423Sdim VNInfoAllocator); 1153263508Sdim LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); 1154263508Sdim LII = LI.addSegment(S); 1155249423Sdim } 1156249423Sdim 1157249423Sdim if (MO.getSubReg() && !MO.isUndef()) 1158249423Sdim lastUseIdx = instrIdx.getRegSlot(); 1159249423Sdim else 1160249423Sdim lastUseIdx = SlotIndex(); 1161249423Sdim } else if (MO.isUse()) { 1162249423Sdim // FIXME: This should probably be handled outside of this branch, 1163249423Sdim // either as part of the def case (for defs inside of the region) or 1164249423Sdim // after the loop over the region. 1165249423Sdim if (!isEndValid && !LII->end.isBlock()) 1166249423Sdim LII->end = instrIdx.getRegSlot(); 1167249423Sdim if (!lastUseIdx.isValid()) 1168249423Sdim lastUseIdx = instrIdx.getRegSlot(); 1169249423Sdim } 1170249423Sdim } 1171249423Sdim } 1172249423Sdim } 1173249423Sdim} 1174