X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=886c7f1cc52449dd5edd870b1103e65c39bfa697;hb=19262ee0725a09b7c621a3d2eb66ba1513ae932a;hp=404cf76fad8c5d8bba5bb0d5933e48582d256d5d;hpb=30fe61aa35ff12cdcbf5f94d8e3ab9a2d964654e;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 404cf76fad8..886c7f1cc52 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -17,7 +17,9 @@ #define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/Value.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/MachineDominators.h" @@ -25,26 +27,20 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/VirtRegMap.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/BlockFrequency.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/STLExtras.h" -#include "LiveRangeCalc.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" #include -#include #include +#include using namespace llvm; -// Switch to the new experimental algorithm for computing live intervals. -static cl::opt -NewLiveIntervals("new-live-intervals", cl::Hidden, - cl::desc("Use new algorithm forcomputing live intervals")); - char LiveIntervals::ID = 0; char &llvm::LiveIntervalsID = LiveIntervals::ID; INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", @@ -56,10 +52,21 @@ INITIALIZE_PASS_DEPENDENCY(SlotIndexes) INITIALIZE_PASS_END(LiveIntervals, "liveintervals", "Live Interval Analysis", false, false) +#ifndef NDEBUG +static cl::opt EnablePrecomputePhysRegs( + "precompute-phys-liveness", cl::Hidden, + cl::desc("Eagerly compute live intervals for all physreg units.")); +#else +static bool EnablePrecomputePhysRegs = false; +#endif // NDEBUG + void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); + // LiveVariables isn't really required by this analysis, it is only required + // here to make sure it is live during TwoAddressInstructionPass and + // PHIElimination. This is temporary. AU.addRequired(); AU.addPreserved(); AU.addPreservedID(MachineLoopInfoID); @@ -96,7 +103,7 @@ void LiveIntervals::releaseMemory() { VNInfoAllocator.Reset(); } -/// runOnMachineFunction - Register allocate the whole function +/// runOnMachineFunction - calculates LiveIntervals /// bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MF = &fn; @@ -105,7 +112,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { TRI = TM->getRegisterInfo(); TII = TM->getInstrInfo(); AA = &getAnalysis(); - LV = &getAnalysis(); Indexes = &getAnalysis(); DomTree = &getAnalysis(); if (!LRCalc) @@ -114,18 +120,16 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { // Allocate space for all virtual registers. VirtRegIntervals.resize(MRI->getNumVirtRegs()); - if (NewLiveIntervals) { - // This is the new way of computing live intervals. - // It is independent of LiveVariables, and it can run at any time. - computeVirtRegs(); - computeRegMasks(); - } else { - // This is the old way of computing live intervals. - // It depends on LiveVariables. - computeIntervals(); - } + computeVirtRegs(); + computeRegMasks(); computeLiveInRegUnits(); + if (EnablePrecomputePhysRegs) { + // For stress testing, precompute live ranges of all physical register + // units, including reserved registers. + for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) + getRegUnit(i); + } DEBUG(dump()); return true; } @@ -165,298 +169,6 @@ void LiveIntervals::dumpInstrs() const { } #endif -static -bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { - unsigned Reg = MI.getOperand(MOIdx).getReg(); - for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { - const MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg()) - continue; - if (MO.getReg() == Reg && MO.isDef()) { - assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && - MI.getOperand(MOIdx).getSubReg() && - (MO.getSubReg() || MO.isImplicit())); - return true; - } - } - return false; -} - -/// isPartialRedef - Return true if the specified def at the specific index is -/// partially re-defining the specified live interval. A common case of this is -/// a definition of the sub-register. -bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, - LiveInterval &interval) { - if (!MO.getSubReg() || MO.isEarlyClobber()) - return false; - - SlotIndex RedefIndex = MIIdx.getRegSlot(); - const LiveRange *OldLR = - interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); - MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); - if (DefMI != 0) { - return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; - } - return false; -} - -void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, - MachineBasicBlock::iterator mi, - SlotIndex MIIdx, - MachineOperand& MO, - unsigned MOIdx, - LiveInterval &interval) { - DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, TRI)); - - // Virtual registers may be defined multiple times (due to phi - // elimination and 2-addr elimination). Much of what we do only has to be - // done once for the vreg. We use an empty interval to detect the first - // time we see a vreg. - LiveVariables::VarInfo& vi = LV->getVarInfo(interval.reg); - if (interval.empty()) { - // Get the Idx of the defining instructions. - SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); - - // Make sure the first definition is not a partial redefinition. - assert(!MO.readsReg() && "First def cannot also read virtual register " - "missing flag?"); - - VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); - assert(ValNo->id == 0 && "First value in interval is not 0?"); - - // Loop over all of the blocks that the vreg is defined in. There are - // two cases we have to handle here. The most common case is a vreg - // whose lifetime is contained within a basic block. In this case there - // will be a single kill, in MBB, which comes after the definition. - if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { - // FIXME: what about dead vars? - SlotIndex killIdx; - if (vi.Kills[0] != mi) - killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); - else - killIdx = defIndex.getDeadSlot(); - - // If the kill happens after the definition, we have an intra-block - // live range. - if (killIdx > defIndex) { - assert(vi.AliveBlocks.empty() && - "Shouldn't be alive across any blocks!"); - LiveRange LR(defIndex, killIdx, ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR << "\n"); - return; - } - } - - // The other case we handle is when a virtual register lives to the end - // of the defining block, potentially live across some blocks, then is - // live into some number of blocks, but gets killed. Start by adding a - // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); - DEBUG(dbgs() << " +" << NewLR); - interval.addRange(NewLR); - - bool PHIJoin = LV->isPHIJoin(interval.reg); - - if (PHIJoin) { - // A phi join register is killed at the end of the MBB and revived as a - // new valno in the killing blocks. - assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); - DEBUG(dbgs() << " phi-join"); - } else { - // Iterate over all of the blocks that the variable is completely - // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the - // live interval. - for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), - E = vi.AliveBlocks.end(); I != E; ++I) { - MachineBasicBlock *aliveBlock = MF->getBlockNumbered(*I); - LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), - ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR); - } - } - - // Finally, this virtual register is live from the start of any killing - // block to the 'use' slot of the killing instruction. - for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { - MachineInstr *Kill = vi.Kills[i]; - SlotIndex Start = getMBBStartIdx(Kill->getParent()); - SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); - - // Create interval with one of a NEW value number. Note that this value - // number isn't actually defined by an instruction, weird huh? :) - if (PHIJoin) { - assert(getInstructionFromIndex(Start) == 0 && - "PHI def index points at actual instruction."); - ValNo = interval.getNextValue(Start, VNInfoAllocator); - } - LiveRange LR(Start, killIdx, ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR); - } - - } else { - if (MultipleDefsBySameMI(*mi, MOIdx)) - // Multiple defs of the same virtual register by the same instruction. - // e.g. %reg1031:5, %reg1031:6 = VLD1q16 %reg1024, ... - // This is likely due to elimination of REG_SEQUENCE instructions. Return - // here since there is nothing to do. - return; - - // If this is the second time we see a virtual register definition, it - // must be due to phi elimination or two addr elimination. If this is - // the result of two address elimination, then the vreg is one of the - // def-and-use register operand. - - // It may also be partial redef like this: - // 80 %reg1041:6 = VSHRNv4i16 %reg1034, 12, pred:14, pred:%reg0 - // 120 %reg1041:5 = VSHRNv4i16 %reg1039, 12, pred:14, pred:%reg0 - bool PartReDef = isPartialRedef(MIIdx, MO, interval); - if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { - // If this is a two-address definition, then we have already processed - // the live range. The only problem is that we didn't realize there - // are actually two values in the live interval. Because of this we - // need to take the LiveRegion that defines this register and split it - // into two values. - SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); - - const LiveRange *OldLR = - interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); - VNInfo *OldValNo = OldLR->valno; - SlotIndex DefIndex = OldValNo->def.getRegSlot(); - - // Delete the previous value, which should be short and continuous, - // because the 2-addr copy must be in the same MBB as the redef. - interval.removeRange(DefIndex, RedefIndex); - - // The new value number (#1) is defined by the instruction we claimed - // defined value #0. - VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); - - // Value#0 is now defined by the 2-addr instruction. - OldValNo->def = RedefIndex; - - // Add the new live interval which replaces the range for the input copy. - LiveRange LR(DefIndex, RedefIndex, ValNo); - DEBUG(dbgs() << " replace range with " << LR); - interval.addRange(LR); - - // If this redefinition is dead, we need to add a dummy unit live - // range covering the def slot. - if (MO.isDead()) - interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), - OldValNo)); - - DEBUG(dbgs() << " RESULT: " << interval); - } else if (LV->isPHIJoin(interval.reg)) { - // In the case of PHI elimination, each variable definition is only - // live until the end of the block. We've already taken care of the - // rest of the live range. - - SlotIndex defIndex = MIIdx.getRegSlot(); - if (MO.isEarlyClobber()) - defIndex = MIIdx.getRegSlot(true); - - VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); - - SlotIndex killIndex = getMBBEndIdx(mbb); - LiveRange LR(defIndex, killIndex, ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " phi-join +" << LR); - } else { - llvm_unreachable("Multiply defined register"); - } - } - - DEBUG(dbgs() << '\n'); -} - -void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator MI, - SlotIndex MIIdx, - MachineOperand& MO, - unsigned MOIdx) { - if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) - handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, - getOrCreateInterval(MO.getReg())); -} - -/// computeIntervals - computes the live intervals for virtual -/// registers. for some ordering of the machine instructions [1,N] a -/// live interval is an interval [i, j) where 1 <= i <= j < N for -/// which a variable is live -void LiveIntervals::computeIntervals() { - DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" - << "********** Function: " << MF->getName() << '\n'); - - RegMaskBlocks.resize(MF->getNumBlockIDs()); - - SmallVector UndefUses; - for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); - MBBI != E; ++MBBI) { - MachineBasicBlock *MBB = MBBI; - RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); - - if (MBB->empty()) - continue; - - // Track the index of the current machine instr. - SlotIndex MIIndex = getMBBStartIdx(MBB); - DEBUG(dbgs() << "BB#" << MBB->getNumber() - << ":\t\t# derived from " << MBB->getName() << "\n"); - - // Skip over empty initial indices. - if (getInstructionFromIndex(MIIndex) == 0) - MIIndex = Indexes->getNextNonNullIndex(MIIndex); - - for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); - MI != miEnd; ++MI) { - DEBUG(dbgs() << MIIndex << "\t" << *MI); - if (MI->isDebugValue()) - continue; - assert(Indexes->getInstructionFromIndex(MIIndex) == MI && - "Lost SlotIndex synchronization"); - - // Handle defs. - for (int i = MI->getNumOperands() - 1; i >= 0; --i) { - MachineOperand &MO = MI->getOperand(i); - - // Collect register masks. - if (MO.isRegMask()) { - RegMaskSlots.push_back(MIIndex.getRegSlot()); - RegMaskBits.push_back(MO.getRegMask()); - continue; - } - - if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) - continue; - - // handle register defs - build intervals - if (MO.isDef()) - handleRegisterDef(MBB, MI, MIIndex, MO, i); - else if (MO.isUndef()) - UndefUses.push_back(MO.getReg()); - } - - // Move to the next instr slot. - MIIndex = Indexes->getNextNonNullIndex(MIIndex); - } - - // Compute the number of register mask instructions in this block. - std::pair &RMB = RegMaskBlocks[MBB->getNumber()]; - RMB.second = RegMaskSlots.size() - RMB.first; - } - - // Create empty intervals for registers defined by implicit_def's (except - // for those implicit_def that define values which are liveout of their - // blocks. - for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { - unsigned UndefReg = UndefUses[i]; - (void)getOrCreateInterval(UndefReg); - } -} - LiveInterval* LiveIntervals::createInterval(unsigned reg) { float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; return new LiveInterval(reg, Weight); @@ -478,9 +190,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); } } @@ -532,10 +242,8 @@ void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { // idempotent. It is very rare for a register unit to have multiple roots, so // uniquing super-registers is probably not worthwhile. for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { - unsigned Root = *Roots; - if (!MRI->reg_empty(Root)) - LRCalc->createDeadDefs(LI, Root); - for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) { + for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); + Supers.isValid(); ++Supers) { if (!MRI->reg_empty(*Supers)) LRCalc->createDeadDefs(LI, *Supers); } @@ -544,10 +252,8 @@ void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { // Now extend LI to reach all uses. // Ignore uses of reserved registers. We only track defs of those. for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { - unsigned Root = *Roots; - if (!MRI->isReserved(Root) && !MRI->reg_empty(Root)) - LRCalc->extendToUses(LI, Root); - for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) { + 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); @@ -912,26 +618,14 @@ LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { } float -LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { - // Limit the loop depth ridiculousness. - if (loopDepth > 200) - loopDepth = 200; - - // The loop depth is used to roughly estimate the number of times the - // instruction is executed. Something like 10^d is simple, but will quickly - // overflow a float. This expression behaves like 10^d for small d, but is - // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of - // headroom before overflow. - // By the way, powf() might be unavailable here. For consistency, - // We may take pow(double,double). - float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); - - return (isDef + isUse) * lc; +LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) { + const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); + return (isDef + isUse) * (freq.getFrequency() * Scale); } LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, MachineInstr* startInst) { - LiveInterval& Interval = getOrCreateInterval(reg); + LiveInterval& Interval = createEmptyInterval(reg); VNInfo* VN = Interval.getNextValue( SlotIndex(getInstructionIndex(startInst).getRegSlot()), getVNInfoAllocator()); @@ -1275,9 +969,9 @@ private: // Return the last use of reg between NewIdx and OldIdx. SlotIndex findLastUseBefore(unsigned Reg) { - SlotIndex LastUse = NewIdx; if (TargetRegisterInfo::isVirtualRegister(Reg)) { + SlotIndex LastUse = NewIdx; for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg), UE = MRI.use_nodbg_end(); @@ -1287,30 +981,42 @@ private: if (InstSlot > LastUse && InstSlot < OldIdx) LastUse = InstSlot; } - } else { - MachineInstr* MI = LIS.getSlotIndexes()->getInstructionFromIndex(NewIdx); - MachineBasicBlock::iterator MII(MI); - ++MII; - MachineBasicBlock* MBB = MI->getParent(); - for (; MII != MBB->end(); ++MII){ - if (MII->isDebugValue()) - continue; - if (LIS.getInstructionIndex(MII) < OldIdx) - break; - for (MachineInstr::mop_iterator MOI = MII->operands_begin(), - MOE = MII->operands_end(); - MOI != MOE; ++MOI) { - const MachineOperand& mop = *MOI; - if (!mop.isReg() || mop.getReg() == 0 || - TargetRegisterInfo::isVirtualRegister(mop.getReg())) - continue; - - if (TRI.hasRegUnit(mop.getReg(), Reg)) - LastUse = LIS.getInstructionIndex(MII); - } - } + return LastUse; + } + + // This is a regunit interval, so scanning the use list could be very + // expensive. Scan upwards from OldIdx instead. + assert(NewIdx < OldIdx && "Expected upwards move"); + SlotIndexes *Indexes = LIS.getSlotIndexes(); + MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); + + // OldIdx may not correspond to an instruction any longer, so set MII to + // point to the next instruction after OldIdx, or MBB->end(). + MachineBasicBlock::iterator MII = MBB->end(); + if (MachineInstr *MI = Indexes->getInstructionFromIndex( + Indexes->getNextNonNullIndex(OldIdx))) + if (MI->getParent() == MBB) + MII = MI; + + MachineBasicBlock::iterator Begin = MBB->begin(); + while (MII != Begin) { + if ((--MII)->isDebugValue()) + continue; + SlotIndex Idx = Indexes->getInstructionIndex(MII); + + // Stop searching when NewIdx is reached. + if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) + return NewIdx; + + // Check if MII uses Reg. + for (MIBundleOperands MO(MII); MO.isValid(); ++MO) + if (MO->isReg() && + TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && + TRI.hasRegUnit(MO->getReg(), Reg)) + return Idx; } - return LastUse; + // Didn't reach NewIdx. It must be the first instruction in the block. + return NewIdx; } }; @@ -1335,3 +1041,128 @@ void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); HME.updateAllRanges(MI); } + +void +LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef OrigRegs) { + // Find anchor points, which are at the beginning/end of blocks or at + // instructions that already have indexes. + while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) + --Begin; + while (End != MBB->end() && !Indexes->hasIndex(End)) + ++End; + + SlotIndex endIdx; + if (End == MBB->end()) + endIdx = getMBBEndIdx(MBB).getPrevSlot(); + else + endIdx = getInstructionIndex(End); + + Indexes->repairIndexesInRange(MBB, Begin, End); + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; + for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + if (MOI->isReg() && + TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && + !hasInterval(MOI->getReg())) { + createAndComputeVirtRegInterval(MOI->getReg()); + } + } + } + + for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { + unsigned Reg = OrigRegs[i]; + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + + LiveInterval &LI = getInterval(Reg); + // FIXME: Should we support undefs that gain defs? + 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; + + 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; + } + } + + 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); + } + + 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(); + } + } + } + } +}