X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=9738dac65ad8e6fa351f4809d92930ffb5ae9caa;hb=0219a272ec3c1a3784bd85bd0dc2fa457743ffd6;hp=c0fc477fe6d7117f541e085c639a09b8412c2f64;hpb=2aeef00d681bf4010d234949043fe0beb29547e2;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index c0fc477fe6d..9738dac65ad 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -15,13 +15,13 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "LiveRangeCalc.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" @@ -32,15 +32,18 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/Format.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include #include #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + char LiveIntervals::ID = 0; char &llvm::LiveIntervalsID = LiveIntervals::ID; INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", @@ -60,6 +63,17 @@ static cl::opt EnablePrecomputePhysRegs( static bool EnablePrecomputePhysRegs = false; #endif // NDEBUG +static cl::opt EnableSubRegLiveness( + "enable-subreg-liveness", cl::Hidden, cl::init(true), + cl::desc("Enable subregister liveness tracking.")); + +namespace llvm { +cl::opt UseSegmentSetForPhysRegs( + "use-segment-set-for-physregs", cl::Hidden, cl::init(true), + cl::desc( + "Use segment set for the computation of the live ranges of physregs.")); +} + void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); @@ -78,7 +92,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), - DomTree(0), LRCalc(0) { + DomTree(nullptr), LRCalc(nullptr) { initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); } @@ -95,9 +109,9 @@ void LiveIntervals::releaseMemory() { RegMaskBits.clear(); RegMaskBlocks.clear(); - for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i) - delete RegUnitIntervals[i]; - RegUnitIntervals.clear(); + for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) + delete RegUnitRanges[i]; + RegUnitRanges.clear(); // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. VNInfoAllocator.Reset(); @@ -108,12 +122,15 @@ void LiveIntervals::releaseMemory() { bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MF = &fn; MRI = &MF->getRegInfo(); - TM = &fn.getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + TII = MF->getSubtarget().getInstrInfo(); AA = &getAnalysis(); Indexes = &getAnalysis(); DomTree = &getAnalysis(); + + if (EnableSubRegLiveness && MF->getSubtarget().enableSubRegLiveness()) + MRI->enableSubRegLiveness(true); + if (!LRCalc) LRCalc = new LiveRangeCalc(); @@ -139,15 +156,15 @@ void LiveIntervals::print(raw_ostream &OS, const Module* ) const { OS << "********** INTERVALS **********\n"; // Dump the regunits. - for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i) - if (LiveInterval *LI = RegUnitIntervals[i]) - OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n'; + for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) + if (LiveRange *LR = RegUnitRanges[i]) + OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; // Dump the virtregs. for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { unsigned Reg = TargetRegisterInfo::index2VirtReg(i); if (hasInterval(Reg)) - OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n'; + OS << getInterval(Reg) << '\n'; } OS << "RegMasks:"; @@ -170,19 +187,20 @@ void LiveIntervals::dumpInstrs() const { #endif LiveInterval* LiveIntervals::createInterval(unsigned reg) { - float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? + llvm::huge_valf : 0.0F; return new LiveInterval(reg, Weight); } /// computeVirtRegInterval - Compute the live interval of a virtual register, /// based on defs and uses. -void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) { +void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); - assert(LI->empty() && "Should only compute empty intervals."); + assert(LI.empty() && "Should only compute empty intervals."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->createDeadDefs(LI); - LRCalc->extendToUses(LI); + LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); + computeDeadValues(LI, nullptr); } void LiveIntervals::computeVirtRegs() { @@ -190,9 +208,7 @@ void LiveIntervals::computeVirtRegs() { unsigned Reg = TargetRegisterInfo::index2VirtReg(i); if (MRI->reg_nodbg_empty(Reg)) continue; - LiveInterval *LI = createInterval(Reg); - VirtRegIntervals[Reg] = LI; - computeVirtRegInterval(LI); + createAndComputeVirtRegInterval(Reg); } } @@ -207,11 +223,11 @@ void LiveIntervals::computeRegMasks() { RMB.first = RegMaskSlots.size(); for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end(); MI != ME; ++MI) - for (MIOperands MO(MI); MO.isValid(); ++MO) { - if (!MO->isRegMask()) + for (const MachineOperand &MO : MI->operands()) { + if (!MO.isRegMask()) continue; RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); - RegMaskBits.push_back(MO->getRegMask()); + RegMaskBits.push_back(MO.getRegMask()); } // Compute the number of register mask instructions in this block. RMB.second = RegMaskSlots.size() - RMB.first; @@ -229,12 +245,10 @@ void LiveIntervals::computeRegMasks() { // interference. // -/// computeRegUnitInterval - Compute the live interval of a register unit, based -/// on the uses and defs of aliasing registers. The interval should be empty, +/// computeRegUnitInterval - Compute the live range of a register unit, based +/// on the uses and defs of aliasing registers. The range should be empty, /// or contain only dead phi-defs from ABI blocks. -void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { - unsigned Unit = LI->reg; - +void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); @@ -247,20 +261,24 @@ void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); Supers.isValid(); ++Supers) { if (!MRI->reg_empty(*Supers)) - LRCalc->createDeadDefs(LI, *Supers); + LRCalc->createDeadDefs(LR, *Supers); } } - // Now extend LI to reach all uses. + // Now extend LR to reach all uses. // Ignore uses of reserved registers. We only track defs of those. for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); Supers.isValid(); ++Supers) { unsigned Reg = *Supers; if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) - LRCalc->extendToUses(LI, Reg); + LRCalc->extendToUses(LR, Reg); } } + + // Flush the segment set to the segment vector. + if (UseSegmentSetForPhysRegs) + LR.flushSegmentSet(); } @@ -269,11 +287,11 @@ void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { /// without a corresponding def when entering the entry block or a landing pad. /// void LiveIntervals::computeLiveInRegUnits() { - RegUnitIntervals.resize(TRI->getNumRegUnits()); + RegUnitRanges.resize(TRI->getNumRegUnits()); DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); - // Keep track of the intervals allocated. - SmallVector NewIntvs; + // Keep track of the live range sets allocated. + SmallVector NewRanges; // Check all basic blocks for live-ins. for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); @@ -291,101 +309,72 @@ void LiveIntervals::computeLiveInRegUnits() { LIE = MBB->livein_end(); LII != LIE; ++LII) { for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) { unsigned Unit = *Units; - LiveInterval *Intv = RegUnitIntervals[Unit]; - if (!Intv) { - Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF); - NewIntvs.push_back(Intv); + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { + // Use segment set to speed-up initial computation of the live range. + LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); + NewRanges.push_back(Unit); } - VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator()); + VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); (void)VNI; DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); } } DEBUG(dbgs() << '\n'); } - DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n"); + DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); - // Compute the 'normal' part of the intervals. - for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i) - computeRegUnitInterval(NewIntvs[i]); + // Compute the 'normal' part of the ranges. + for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { + unsigned Unit = NewRanges[i]; + computeRegUnitRange(*RegUnitRanges[Unit], Unit); + } } -/// shrinkToUses - After removing some uses of a register, shrink its live -/// range to just the remaining uses. This method does not compute reaching -/// defs for new uses, and it doesn't remove dead defs. -bool LiveIntervals::shrinkToUses(LiveInterval *li, - SmallVectorImpl *dead) { - DEBUG(dbgs() << "Shrink: " << *li << '\n'); - assert(TargetRegisterInfo::isVirtualRegister(li->reg) - && "Can only shrink virtual registers"); - // Find all the values used, including PHI kills. - SmallVector, 16> WorkList; - - // Blocks that have already been added to WorkList as live-out. - SmallPtrSet LiveOut; - - // Visit all instructions reading li->reg. - for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg); - MachineInstr *UseMI = I.skipInstruction();) { - if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) - continue; - SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); - LiveRangeQuery LRQ(*li, Idx); - VNInfo *VNI = LRQ.valueIn(); - if (!VNI) { - // This shouldn't happen: readsVirtualRegister returns true, but there is - // no live value. It is likely caused by a target getting flags - // wrong. - DEBUG(dbgs() << Idx << '\t' << *UseMI - << "Warning: Instr claims to read non-existent value in " - << *li << '\n'); - continue; - } - // Special case: An early-clobber tied operand reads and writes the - // register one slot early. - if (VNInfo *DefVNI = LRQ.valueDefined()) - Idx = DefVNI->def; - - WorkList.push_back(std::make_pair(Idx, VNI)); - } - - // Create a new live interval with only minimal live segments per def. - LiveInterval NewLI(li->reg, 0); - for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; +static void createSegmentsForValues(LiveRange &LR, + iterator_range VNIs) { + for (auto VNI : VNIs) { if (VNI->isUnused()) continue; - NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); + SlotIndex Def = VNI->def; + LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); } +} + +typedef SmallVector, 16> ShrinkToUsesWorkList; +static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, + ShrinkToUsesWorkList &WorkList, + const LiveRange &OldRange) { // Keep track of the PHIs that are in use. SmallPtrSet UsedPHIs; + // Blocks that have already been added to WorkList as live-out. + SmallPtrSet LiveOut; // Extend intervals to reach all uses in WorkList. while (!WorkList.empty()) { SlotIndex Idx = WorkList.back().first; VNInfo *VNI = WorkList.back().second; WorkList.pop_back(); - const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); - SlotIndex BlockStart = getMBBStartIdx(MBB); + const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot()); + SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB); // Extend the live range for VNI to be live at Idx. - if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { - (void)ExtVNI; + if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) { assert(ExtVNI == VNI && "Unexpected existing value number"); + (void)ExtVNI; // Is this a PHIDef we haven't seen before? - if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) + if (!VNI->isPHIDef() || VNI->def != BlockStart || + !UsedPHIs.insert(VNI).second) continue; // The PHI is live, make sure the predecessors are live-out. - for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { - if (!LiveOut.insert(*PI)) + for (auto &Pred : MBB->predecessors()) { + if (!LiveOut.insert(Pred).second) continue; - SlotIndex Stop = getMBBEndIdx(*PI); + SlotIndex Stop = Indexes.getMBBEndIdx(Pred); // A predecessor is not required to have a live-out value for a PHI. - if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) + if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) WorkList.push_back(std::make_pair(Stop, PVNI)); } continue; @@ -393,83 +382,217 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, // VNI is live-in to MBB. DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); - NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); + LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); // Make sure VNI is live-out from the predecessors. - for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { - if (!LiveOut.insert(*PI)) + for (auto &Pred : MBB->predecessors()) { + if (!LiveOut.insert(Pred).second) continue; - SlotIndex Stop = getMBBEndIdx(*PI); - assert(li->getVNInfoBefore(Stop) == VNI && + SlotIndex Stop = Indexes.getMBBEndIdx(Pred); + assert(OldRange.getVNInfoBefore(Stop) == VNI && "Wrong value out of predecessor"); WorkList.push_back(std::make_pair(Stop, VNI)); } } +} + +bool LiveIntervals::shrinkToUses(LiveInterval *li, + SmallVectorImpl *dead) { + DEBUG(dbgs() << "Shrink: " << *li << '\n'); + assert(TargetRegisterInfo::isVirtualRegister(li->reg) + && "Can only shrink virtual registers"); + + // Shrink subregister live ranges. + bool NeedsCleanup = false; + for (LiveInterval::SubRange &S : li->subranges()) { + shrinkToUses(S, li->reg); + if (S.empty()) + NeedsCleanup = true; + } + if (NeedsCleanup) + li->removeEmptySubRanges(); + + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; + + // Visit all instructions reading li->reg. + for (MachineRegisterInfo::reg_instr_iterator + I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end(); + I != E; ) { + MachineInstr *UseMI = &*(I++); + if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) + continue; + SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); + LiveQueryResult LRQ = li->Query(Idx); + VNInfo *VNI = LRQ.valueIn(); + if (!VNI) { + // This shouldn't happen: readsVirtualRegister returns true, but there is + // no live value. It is likely caused by a target getting flags + // wrong. + DEBUG(dbgs() << Idx << '\t' << *UseMI + << "Warning: Instr claims to read non-existent value in " + << *li << '\n'); + continue; + } + // Special case: An early-clobber tied operand reads and writes the + // register one slot early. + if (VNInfo *DefVNI = LRQ.valueDefined()) + Idx = DefVNI->def; + + WorkList.push_back(std::make_pair(Idx, VNI)); + } + + // Create new live ranges with only minimal live segments per def. + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); + extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); + + // Move the trimmed segments back. + li->segments.swap(NewLR.segments); // Handle dead values. - bool CanSeparate = false; - for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; + bool CanSeparate = computeDeadValues(*li, dead); + DEBUG(dbgs() << "Shrunk: " << *li << '\n'); + return CanSeparate; +} + +bool LiveIntervals::computeDeadValues(LiveInterval &LI, + SmallVectorImpl *dead) { + bool PHIRemoved = false; + for (auto VNI : LI.valnos) { if (VNI->isUnused()) continue; - LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); - assert(LII != NewLI.end() && "Missing live range for PHI"); - if (LII->end != VNI->def.getDeadSlot()) + SlotIndex Def = VNI->def; + LiveRange::iterator I = LI.FindSegmentContaining(Def); + assert(I != LI.end() && "Missing segment for VNI"); + + // Is the register live before? Otherwise we may have to add a read-undef + // flag for subregister defs. + if (MRI->shouldTrackSubRegLiveness(LI.reg)) { + if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { + MachineInstr *MI = getInstructionFromIndex(Def); + MI->addRegisterDefReadUndef(LI.reg); + } + } + + if (I->end != Def.getDeadSlot()) continue; if (VNI->isPHIDef()) { // This is a dead PHI. Remove it. VNI->markUnused(); - NewLI.removeRange(*LII); - DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - CanSeparate = true; + LI.removeSegment(I); + DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); + PHIRemoved = true; } else { // This is a dead def. Make sure the instruction knows. - MachineInstr *MI = getInstructionFromIndex(VNI->def); + MachineInstr *MI = getInstructionFromIndex(Def); assert(MI && "No instruction defining live value"); - MI->addRegisterDead(li->reg, TRI); + MI->addRegisterDead(LI.reg, TRI); if (dead && MI->allDefsAreDead()) { - DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); + DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); dead->push_back(MI); } } } + return PHIRemoved; +} + +void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) +{ + DEBUG(dbgs() << "Shrink: " << SR << '\n'); + assert(TargetRegisterInfo::isVirtualRegister(Reg) + && "Can only shrink virtual registers"); + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; + + // Visit all instructions reading Reg. + SlotIndex LastIdx; + for (MachineOperand &MO : MRI->reg_operands(Reg)) { + MachineInstr *UseMI = MO.getParent(); + if (UseMI->isDebugValue()) + continue; + // Maybe the operand is for a subregister we don't care about. + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0) { + unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg); + if ((SubRegMask & SR.LaneMask) == 0) + continue; + } + // We only need to visit each instruction once. + SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); + if (Idx == LastIdx) + continue; + LastIdx = Idx; + + LiveQueryResult LRQ = SR.Query(Idx); + VNInfo *VNI = LRQ.valueIn(); + // For Subranges it is possible that only undef values are left in that + // part of the subregister, so there is no real liverange at the use + if (!VNI) + continue; + + // Special case: An early-clobber tied operand reads and writes the + // register one slot early. + if (VNInfo *DefVNI = LRQ.valueDefined()) + Idx = DefVNI->def; + + WorkList.push_back(std::make_pair(Idx, VNI)); + } + + // Create a new live ranges with only minimal live segments per def. + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); + extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); // Move the trimmed ranges back. - li->ranges.swap(NewLI.ranges); - DEBUG(dbgs() << "Shrunk: " << *li << '\n'); - return CanSeparate; + SR.segments.swap(NewLR.segments); + + // Remove dead PHI value numbers + for (auto VNI : SR.valnos) { + if (VNI->isUnused()) + continue; + const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); + assert(Segment != nullptr && "Missing segment for VNI"); + if (Segment->end != VNI->def.getDeadSlot()) + continue; + if (VNI->isPHIDef()) { + // This is a dead PHI. Remove it. + VNI->markUnused(); + SR.removeSegment(*Segment); + DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); + } + } + + DEBUG(dbgs() << "Shrunk: " << SR << '\n'); } -void LiveIntervals::extendToIndices(LiveInterval *LI, +void LiveIntervals::extendToIndices(LiveRange &LR, ArrayRef Indices) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); for (unsigned i = 0, e = Indices.size(); i != e; ++i) - LRCalc->extend(LI, Indices[i]); + LRCalc->extend(LR, Indices[i]); } -void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, +void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl *EndPoints) { - LiveRangeQuery LRQ(*LI, Kill); - VNInfo *VNI = LRQ.valueOut(); + LiveQueryResult LRQ = LR.Query(Kill); + VNInfo *VNI = LRQ.valueOutOrDead(); if (!VNI) return; MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); - SlotIndex MBBStart, MBBEnd; - tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); + SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); // If VNI isn't live out from KillMBB, the value is trivially pruned. if (LRQ.endPoint() < MBBEnd) { - LI->removeRange(Kill, LRQ.endPoint()); + LR.removeSegment(Kill, LRQ.endPoint()); if (EndPoints) EndPoints->push_back(LRQ.endPoint()); return; } // VNI is live out of KillMBB. - LI->removeRange(Kill, MBBEnd); + LR.removeSegment(Kill, MBBEnd); if (EndPoints) EndPoints->push_back(MBBEnd); // Find all blocks that are reachable from KillMBB without leaving VNI's live @@ -486,24 +609,25 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, MachineBasicBlock *MBB = *I; // Check if VNI is live in to MBB. - tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); - LiveRangeQuery LRQ(*LI, MBBStart); + SlotIndex MBBStart, MBBEnd; + std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); + LiveQueryResult LRQ = LR.Query(MBBStart); if (LRQ.valueIn() != VNI) { - // This block isn't part of the VNI live range. Prune the search. + // This block isn't part of the VNI segment. Prune the search. I.skipChildren(); continue; } // Prune the search if VNI is killed in MBB. if (LRQ.endPoint() < MBBEnd) { - LI->removeRange(MBBStart, LRQ.endPoint()); + LR.removeSegment(MBBStart, LRQ.endPoint()); if (EndPoints) EndPoints->push_back(LRQ.endPoint()); I.skipChildren(); continue; } // VNI is live through MBB. - LI->removeRange(MBBStart, MBBEnd); + LR.removeSegment(MBBStart, MBBEnd); if (EndPoints) EndPoints->push_back(MBBEnd); ++I; } @@ -516,14 +640,17 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // Keep track of regunit ranges. - SmallVector, 8> RU; + SmallVector, 8> RU; + // Keep track of subregister ranges. + SmallVector, 4> SRs; for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { unsigned Reg = TargetRegisterInfo::index2VirtReg(i); if (MRI->reg_nodbg_empty(Reg)) continue; - LiveInterval *LI = &getInterval(Reg); - if (LI->empty()) + const LiveInterval &LI = getInterval(Reg); + if (LI.empty()) continue; // Find the regunit intervals for the assigned register. They may overlap @@ -531,14 +658,22 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { RU.clear(); for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); ++Units) { - LiveInterval *RUInt = &getRegUnit(*Units); - if (RUInt->empty()) + const LiveRange &RURange = getRegUnit(*Units); + if (RURange.empty()) continue; - RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end))); + RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); + } + + if (MRI->subRegLivenessEnabled()) { + SRs.clear(); + for (const LiveInterval::SubRange &SR : LI.subranges()) { + SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); + } } - // Every instruction that kills Reg corresponds to a live range end point. - for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; + // Every instruction that kills Reg corresponds to a segment range end + // point. + for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; ++RI) { // A block index indicates an MBB edge. if (RI->end.isBlock()) @@ -547,7 +682,7 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { if (!MI) continue; - // Check if any of the reguints are live beyond the end of RI. That could + // Check if any of the regunits are live beyond the end of RI. That could // happen when a physreg is defined as a copy of a virtreg: // // %EAX = COPY %vreg5 @@ -555,23 +690,80 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // BAR %EAX // // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. - bool CancelKill = false; - for (unsigned u = 0, e = RU.size(); u != e; ++u) { - LiveInterval *RInt = RU[u].first; - LiveInterval::iterator &I = RU[u].second; - if (I == RInt->end()) + for (auto &RUP : RU) { + const LiveRange &RURange = *RUP.first; + LiveRange::const_iterator &I = RUP.second; + if (I == RURange.end()) continue; - I = RInt->advanceTo(I, RI->end); - if (I == RInt->end() || I->start >= RI->end) + I = RURange.advanceTo(I, RI->end); + if (I == RURange.end() || I->start >= RI->end) continue; // I is overlapping RI. - CancelKill = true; - break; + goto CancelKill; } - if (CancelKill) - MI->clearRegisterKills(Reg, NULL); - else - MI->addRegisterKilled(Reg, NULL); + + if (MRI->subRegLivenessEnabled()) { + // When reading a partial undefined value we must not add a kill flag. + // The regalloc might have used the undef lane for something else. + // Example: + // %vreg1 = ... ; R32: %vreg1 + // %vreg2:high16 = ... ; R64: %vreg2 + // = read %vreg2 ; R64: %vreg2 + // = read %vreg1 ; R32: %vreg1 + // The flag is correct for %vreg2, but the register allocator may + // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0 + // are actually never written by %vreg2. After assignment the + // flag at the read instruction is invalid. + unsigned DefinedLanesMask; + if (!SRs.empty()) { + // Compute a mask of lanes that are defined. + DefinedLanesMask = 0; + for (auto &SRP : SRs) { + const LiveInterval::SubRange &SR = *SRP.first; + LiveRange::const_iterator &I = SRP.second; + if (I == SR.end()) + continue; + I = SR.advanceTo(I, RI->end); + if (I == SR.end() || I->start >= RI->end) + continue; + // I is overlapping RI + DefinedLanesMask |= SR.LaneMask; + } + } else + DefinedLanesMask = ~0u; + + bool IsFullWrite = false; + for (const MachineOperand &MO : MI->operands()) { + if (!MO.isReg() || MO.getReg() != Reg) + continue; + if (MO.isUse()) { + // Reading any undefined lanes? + unsigned UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); + if ((UseMask & ~DefinedLanesMask) != 0) + goto CancelKill; + } else if (MO.getSubReg() == 0) { + // Writing to the full register? + assert(MO.isDef()); + IsFullWrite = true; + } + } + + // If an instruction writes to a subregister, a new segment starts in + // the LiveInterval. But as this is only overriding part of the register + // adding kill-flags is not correct here after registers have been + // assigned. + if (!IsFullWrite) { + // Next segment has to be adjacent in the subregister write case. + LiveRange::const_iterator N = std::next(RI); + if (N != LI.end() && N->start == RI->end) + goto CancelKill; + } + } + + MI->addRegisterKilled(Reg, nullptr); + continue; +CancelKill: + MI->clearRegisterKills(Reg, nullptr); } } } @@ -587,24 +779,22 @@ LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { SlotIndex Start = LI.beginIndex(); if (Start.isBlock()) - return NULL; + return nullptr; SlotIndex Stop = LI.endIndex(); if (Stop.isBlock()) - return NULL; + return nullptr; // getMBBFromIndex doesn't need to search the MBB table when both indexes // belong to proper instructions. MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); - return MBB1 == MBB2 ? MBB1 : NULL; + return MBB1 == MBB2 ? MBB1 : nullptr; } bool LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { - for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); - I != E; ++I) { - const VNInfo *PHI = *I; + for (const VNInfo *PHI : LI.valnos) { if (PHI->isUnused() || !PHI->isPHIDef()) continue; const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); @@ -620,23 +810,26 @@ LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { } float -LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) { - const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); - return (isDef + isUse) * (freq.getFrequency() * Scale); +LiveIntervals::getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr *MI) { + BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent()); + const float Scale = 1.0f / MBFI->getEntryFreq(); + return (isDef + isUse) * (Freq.getFrequency() * Scale); } -LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, - MachineInstr* startInst) { - LiveInterval& Interval = getOrCreateInterval(reg); +LiveRange::Segment +LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) { + LiveInterval& Interval = createEmptyInterval(reg); VNInfo* VN = Interval.getNextValue( SlotIndex(getInstructionIndex(startInst).getRegSlot()), getVNInfoAllocator()); - LiveRange LR( + LiveRange::Segment S( SlotIndex(getInstructionIndex(startInst).getRegSlot()), getMBBEndIdx(startInst->getParent()), VN); - Interval.addRange(LR); + Interval.addSegment(S); - return LR; + return S; } @@ -711,7 +904,7 @@ private: const TargetRegisterInfo& TRI; SlotIndex OldIdx; SlotIndex NewIdx; - SmallPtrSet Updated; + SmallPtrSet Updated; bool UpdateFlags; public: @@ -725,7 +918,7 @@ public: // physregs, even those that aren't needed for regalloc, in order to update // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill // flags, and postRA passes will use a live register utility instead. - LiveInterval *getRegUnitLI(unsigned Unit) { + LiveRange *getRegUnitLI(unsigned Unit) { if (UpdateFlags) return &LIS.getRegUnit(Unit); return LIS.getCachedRegUnit(Unit); @@ -736,29 +929,39 @@ public: void updateAllRanges(MachineInstr *MI) { DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); bool hasRegMask = false; - for (MIOperands MO(MI); MO.isValid(); ++MO) { - if (MO->isRegMask()) + for (MachineOperand &MO : MI->operands()) { + if (MO.isRegMask()) hasRegMask = true; - if (!MO->isReg()) + if (!MO.isReg()) continue; // Aggressively clear all kill flags. // They are reinserted by VirtRegRewriter. - if (MO->isUse()) - MO->setIsKill(false); + if (MO.isUse()) + MO.setIsKill(false); - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); if (!Reg) continue; if (TargetRegisterInfo::isVirtualRegister(Reg)) { - updateRange(LIS.getInterval(Reg)); + LiveInterval &LI = LIS.getInterval(Reg); + if (LI.hasSubRanges()) { + unsigned SubReg = MO.getSubReg(); + unsigned LaneMask = TRI.getSubRegIndexLaneMask(SubReg); + for (LiveInterval::SubRange &S : LI.subranges()) { + if ((S.LaneMask & LaneMask) == 0) + continue; + updateRange(S, Reg, S.LaneMask); + } + } + updateRange(LI, Reg, 0); continue; } // For physregs, only update the regunits that actually have a // precomputed live range. for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) - if (LiveInterval *LI = getRegUnitLI(*Units)) - updateRange(*LI); + if (LiveRange *LR = getRegUnitLI(*Units)) + updateRange(*LR, *Units, 0); } if (hasRegMask) updateRegMaskSlots(); @@ -767,26 +970,29 @@ public: private: /// Update a single live range, assuming an instruction has been moved from /// OldIdx to NewIdx. - void updateRange(LiveInterval &LI) { - if (!Updated.insert(&LI)) + void updateRange(LiveRange &LR, unsigned Reg, unsigned LaneMask) { + if (!Updated.insert(&LR).second) return; DEBUG({ dbgs() << " "; - if (TargetRegisterInfo::isVirtualRegister(LI.reg)) - dbgs() << PrintReg(LI.reg); - else - dbgs() << PrintRegUnit(LI.reg, &TRI); - dbgs() << ":\t" << LI << '\n'; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + dbgs() << PrintReg(Reg); + if (LaneMask != 0) + dbgs() << format(" L%04X", LaneMask); + } else { + dbgs() << PrintRegUnit(Reg, &TRI); + } + dbgs() << ":\t" << LR << '\n'; }); if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) - handleMoveDown(LI); + handleMoveDown(LR); else - handleMoveUp(LI); - DEBUG(dbgs() << " -->\t" << LI << '\n'); - LI.verify(); + handleMoveUp(LR, Reg, LaneMask); + DEBUG(dbgs() << " -->\t" << LR << '\n'); + LR.verify(); } - /// Update LI to reflect an instruction has been moved downwards from OldIdx + /// Update LR to reflect an instruction has been moved downwards from OldIdx /// to NewIdx. /// /// 1. Live def at OldIdx: @@ -800,17 +1006,17 @@ private: /// Move def to NewIdx, possibly across another live value. /// /// 4. Def at OldIdx AND at NewIdx: - /// Remove live range [OldIdx;NewIdx) and value defined at OldIdx. + /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx. /// (Happens when bundling multiple defs together). /// /// 5. Value read at OldIdx, killed before NewIdx: /// Extend kill to NewIdx. /// - void handleMoveDown(LiveInterval &LI) { + void handleMoveDown(LiveRange &LR) { // First look for a kill at OldIdx. - LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); - LiveInterval::iterator E = LI.end(); - // Is LI even live at OldIdx? + LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); + LiveRange::iterator E = LR.end(); + // Is LR even live at OldIdx? if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) return; @@ -827,7 +1033,7 @@ private: for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) if (MO->isReg() && MO->isUse()) MO->setIsKill(false); - // Adjust I->end to reach NewIdx. This may temporarily make LI invalid by + // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by // overlapping ranges. Case 5 above. I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); // If this was a kill, there may also be a def. Otherwise we're done. @@ -856,24 +1062,25 @@ private: assert((I->end == OldIdx.getDeadSlot() || SlotIndex::isSameInstr(I->end, NewIdx)) && "Cannot move def below kill"); - LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot()); + LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot()); if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) { // There is an existing def at NewIdx, case 4 above. The def at OldIdx is // coalesced into that value. assert(NewI->valno != DefVNI && "Multiple defs of value?"); - LI.removeValNo(DefVNI); + LR.removeValNo(DefVNI); return; } // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. - // If the def at OldIdx was dead, we allow it to be moved across other LI + // If the def at OldIdx was dead, we allow it to be moved across other LR // values. The new range should be placed immediately before NewI, move any // intermediate ranges up. assert(NewI != I && "Inconsistent iterators"); - std::copy(llvm::next(I), NewI, I); - *llvm::prior(NewI) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); + std::copy(std::next(I), NewI, I); + *std::prev(NewI) + = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); } - /// Update LI to reflect an instruction has been moved upwards from OldIdx + /// Update LR to reflect an instruction has been moved upwards from OldIdx /// to NewIdx. /// /// 1. Live def at OldIdx: @@ -893,11 +1100,11 @@ private: /// Hoist kill to NewIdx, then scan for last kill between NewIdx and /// OldIdx. /// - void handleMoveUp(LiveInterval &LI) { + void handleMoveUp(LiveRange &LR, unsigned Reg, unsigned LaneMask) { // First look for a kill at OldIdx. - LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); - LiveInterval::iterator E = LI.end(); - // Is LI even live at OldIdx? + LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); + LiveRange::iterator E = LR.end(); + // Is LR even live at OldIdx? if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) return; @@ -914,7 +1121,7 @@ private: if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { // No def, search for the new kill. // This can never be an early clobber kill since there is no def. - llvm::prior(I)->end = findLastUseBefore(LI.reg).getRegSlot(); + std::prev(I)->end = findLastUseBefore(Reg, LaneMask).getRegSlot(); return; } } @@ -926,18 +1133,18 @@ private: DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); // Check for an existing def at NewIdx. - LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot()); + LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot()); if (SlotIndex::isSameInstr(NewI->start, NewIdx)) { assert(NewI->valno != DefVNI && "Same value defined more than once?"); // There is an existing def at NewIdx. if (I->end.isDead()) { // Case 3: Remove the dead def at OldIdx. - LI.removeValNo(DefVNI); + LR.removeValNo(DefVNI); return; } // Case 4: Replace def at NewIdx with live def at OldIdx. I->start = DefVNI->def; - LI.removeValNo(NewI->valno); + LR.removeValNo(NewI->valno); return; } @@ -948,10 +1155,10 @@ private: return; } - // DefVNI is a dead def. It may have been moved across other values in LI, + // DefVNI is a dead def. It may have been moved across other values in LR, // so move I up to NewI. Slide [NewI;I) down one position. - std::copy_backward(NewI, I, llvm::next(I)); - *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); + std::copy_backward(NewI, I, std::next(I)); + *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); } void updateRegMaskSlots() { @@ -962,23 +1169,25 @@ private: "No RegMask at OldIdx."); *RI = NewIdx.getRegSlot(); assert((RI == LIS.RegMaskSlots.begin() || - SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) && - "Cannot move regmask instruction above another call"); - assert((llvm::next(RI) == LIS.RegMaskSlots.end() || - SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) && - "Cannot move regmask instruction below another call"); + SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && + "Cannot move regmask instruction above another call"); + assert((std::next(RI) == LIS.RegMaskSlots.end() || + SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && + "Cannot move regmask instruction below another call"); } // Return the last use of reg between NewIdx and OldIdx. - SlotIndex findLastUseBefore(unsigned Reg) { + SlotIndex findLastUseBefore(unsigned Reg, unsigned LaneMask) { if (TargetRegisterInfo::isVirtualRegister(Reg)) { SlotIndex LastUse = NewIdx; - for (MachineRegisterInfo::use_nodbg_iterator - UI = MRI.use_nodbg_begin(Reg), - UE = MRI.use_nodbg_end(); - UI != UE; UI.skipInstruction()) { - const MachineInstr* MI = &*UI; + for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0 && LaneMask != 0 + && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask) == 0) + continue; + + const MachineInstr *MI = MO.getParent(); SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); if (InstSlot > LastUse && InstSlot < OldIdx) LastUse = InstSlot; @@ -1044,6 +1253,94 @@ void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, HME.updateAllRanges(MI); } +void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, + const MachineBasicBlock::iterator End, + const SlotIndex endIdx, + LiveRange &LR, const unsigned Reg, + const unsigned LaneMask) { + LiveInterval::iterator LII = LR.find(endIdx); + SlotIndex lastUseIdx; + if (LII != LR.end() && LII->start < endIdx) + lastUseIdx = LII->end; + else + --LII; + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; + + SlotIndex instrIdx = getInstructionIndex(MI); + bool isStartValid = getInstructionFromIndex(LII->start); + bool isEndValid = getInstructionFromIndex(LII->end); + + // FIXME: This doesn't currently handle early-clobber or multiple removed + // defs inside of the region to repair. + for (MachineInstr::mop_iterator OI = MI->operands_begin(), + OE = MI->operands_end(); OI != OE; ++OI) { + const MachineOperand &MO = *OI; + if (!MO.isReg() || MO.getReg() != Reg) + continue; + + unsigned SubReg = MO.getSubReg(); + unsigned Mask = TRI->getSubRegIndexLaneMask(SubReg); + if ((Mask & LaneMask) == 0) + continue; + + if (MO.isDef()) { + if (!isStartValid) { + if (LII->end.isDead()) { + SlotIndex prevStart; + if (LII != LR.begin()) + prevStart = std::prev(LII)->start; + + // FIXME: This could be more efficient if there was a + // removeSegment method that returned an iterator. + LR.removeSegment(*LII, true); + if (prevStart.isValid()) + LII = LR.find(prevStart); + else + LII = LR.begin(); + } else { + LII->start = instrIdx.getRegSlot(); + LII->valno->def = instrIdx.getRegSlot(); + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + continue; + } + } + + if (!lastUseIdx.isValid()) { + VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); + LiveRange::Segment S(instrIdx.getRegSlot(), + instrIdx.getDeadSlot(), VNI); + LII = LR.addSegment(S); + } else if (LII->start != instrIdx.getRegSlot()) { + VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); + LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); + LII = LR.addSegment(S); + } + + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + } else if (MO.isUse()) { + // FIXME: This should probably be handled outside of this branch, + // either as part of the def case (for defs inside of the region) or + // after the loop over the region. + if (!isEndValid && !LII->end.isBlock()) + LII->end = instrIdx.getRegSlot(); + if (!lastUseIdx.isValid()) + lastUseIdx = instrIdx.getRegSlot(); + } + } + } +} + void LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, @@ -1074,8 +1371,7 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, if (MOI->isReg() && TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && !hasInterval(MOI->getReg())) { - LiveInterval &LI = getOrCreateInterval(MOI->getReg()); - computeVirtRegInterval(&LI); + createAndComputeVirtRegInterval(MOI->getReg()); } } } @@ -1090,82 +1386,31 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, if (!LI.hasAtLeastOneValue()) continue; - LiveInterval::iterator LII = LI.find(endIdx); - SlotIndex lastUseIdx; - if (LII != LI.end() && LII->start < endIdx) - lastUseIdx = LII->end; - else - --LII; - - for (MachineBasicBlock::iterator I = End; I != Begin;) { - --I; - MachineInstr *MI = I; - if (MI->isDebugValue()) - continue; - - SlotIndex instrIdx = getInstructionIndex(MI); - bool isStartValid = getInstructionFromIndex(LII->start); - bool isEndValid = getInstructionFromIndex(LII->end); - - // FIXME: This doesn't currently handle early-clobber or multiple removed - // defs inside of the region to repair. - for (MachineInstr::mop_iterator OI = MI->operands_begin(), - OE = MI->operands_end(); OI != OE; ++OI) { - const MachineOperand &MO = *OI; - if (!MO.isReg() || MO.getReg() != Reg) - continue; + for (LiveInterval::SubRange &S : LI.subranges()) { + repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); + } + repairOldRegInRange(Begin, End, endIdx, LI, Reg); + } +} - if (MO.isDef()) { - if (!isStartValid) { - if (LII->end.isDead()) { - SlotIndex prevStart; - if (LII != LI.begin()) - prevStart = llvm::prior(LII)->start; - - // FIXME: This could be more efficient if there was a removeRange - // method that returned an iterator. - LI.removeRange(*LII, true); - if (prevStart.isValid()) - LII = LI.find(prevStart); - else - LII = LI.begin(); - } else { - LII->start = instrIdx.getRegSlot(); - LII->valno->def = instrIdx.getRegSlot(); - if (MO.getSubReg() && !MO.isUndef()) - lastUseIdx = instrIdx.getRegSlot(); - else - lastUseIdx = SlotIndex(); - continue; - } - } +void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { + if (LiveRange *LR = getCachedRegUnit(*Units)) + if (VNInfo *VNI = LR->getVNInfoAt(Pos)) + LR->removeValNo(VNI); + } +} - if (!lastUseIdx.isValid()) { - VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), - VNInfoAllocator); - LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI); - LII = LI.addRange(LR); - } else if (LII->start != instrIdx.getRegSlot()) { - VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), - VNInfoAllocator); - LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI); - LII = LI.addRange(LR); - } +void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { + VNInfo *VNI = LI.getVNInfoAt(Pos); + if (VNI == nullptr) + return; + LI.removeValNo(VNI); - if (MO.getSubReg() && !MO.isUndef()) - lastUseIdx = instrIdx.getRegSlot(); - else - lastUseIdx = SlotIndex(); - } else if (MO.isUse()) { - // FIXME: This should probably be handled outside of this branch, - // either as part of the def case (for defs inside of the region) or - // after the loop over the region. - if (!isEndValid && !LII->end.isBlock()) - LII->end = instrIdx.getRegSlot(); - if (!lastUseIdx.isValid()) - lastUseIdx = instrIdx.getRegSlot(); - } - } - } + // Also remove the value in subranges. + for (LiveInterval::SubRange &S : LI.subranges()) { + if (VNInfo *SVNI = S.getVNInfoAt(Pos)) + S.removeValNo(SVNI); } + LI.removeEmptySubRanges(); }