CbC/CbC_llvm: lib/CodeGen/LiveIntervalAnalysis.cpp comparison

comparison lib/CodeGen/LiveIntervalAnalysis.cpp @ 120:1172e4bd9c6f

update 4.0.0

author	mir3636
date	Fri, 25 Nov 2016 19:14:25 +0900
parents	7d135dc70f03
children	803732b1fca8

comparison

equal deleted inserted replaced

-:34baf5011add
+:1172e4bd9c6f
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LiveInterval analysis pass which is used
 // by the Linear Scan Register allocator. This pass linearizes the
-// basic blocks of the function in DFS order and uses the
+// basic blocks of the function in DFS order and computes live intervals for
-// LiveVariables pass to conservatively compute live intervals for
 // each virtual and physical register.
 //
 //===----------------------------------------------------------------------===//
 #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/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
 #include <cmath>
-#include <limits>
 using namespace llvm;
 #define DEBUG_TYPE "regalloc"
 char LiveIntervals::ID = 0;
 char &llvm::LiveIntervalsID = LiveIntervals::ID;
 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
 "Live Interval Analysis", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(LiveVariables)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
 "Live Interval Analysis", false, false)
 cl::desc("Eagerly compute live intervals for all physreg units."));
 #else
 static bool EnablePrecomputePhysRegs = false;
 #endif // NDEBUG
-static cl::opt<bool> EnableSubRegLiveness(
-"enable-subreg-liveness", cl::Hidden, cl::init(true),
-cl::desc("Enable subregister liveness tracking."));
 namespace llvm {
 cl::opt<bool> 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<AAResultsWrapperPass>();
 AU.addPreserved<AAResultsWrapperPass>();
-// 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<LiveVariables>();
 AU.addPreserved<LiveVariables>();
 AU.addPreservedID(MachineLoopInfoID);
 AU.addRequiredTransitiveID(MachineDominatorsID);
 AU.addPreservedID(MachineDominatorsID);
 AU.addPreserved<SlotIndexes>();
 TII = MF->getSubtarget().getInstrInfo();
 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 Indexes = &getAnalysis<SlotIndexes>();
 DomTree = &getAnalysis<MachineDominatorTree>();
-if (EnableSubRegLiveness && MF->getSubtarget().enableSubRegLiveness())
-MRI->enableSubRegLiveness(true);
 if (!LRCalc)
 LRCalc = new LiveRangeCalc();
 // Allocate space for all virtual registers.
 VirtRegIntervals.resize(MRI->getNumVirtRegs());
 /// computeVirtRegInterval - Compute the live interval of a virtual register,
 /// based on defs and uses.
 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
 assert(LRCalc && "LRCalc not initialized.");
 assert(LI.empty() && "Should only compute empty intervals.");
-bool ShouldTrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(LI.reg);
 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
-LRCalc->calculate(LI, ShouldTrackSubRegLiveness);
+LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
-bool SeparatedComponents = computeDeadValues(LI, nullptr);
+computeDeadValues(LI, nullptr);
-if (SeparatedComponents) {
-assert(ShouldTrackSubRegLiveness
-&& "Separated components should only occur for unused subreg defs");
-SmallVector<LiveInterval*, 8> SplitLIs;
-splitSeparateComponents(LI, SplitLIs);
-}
 }
 void LiveIntervals::computeVirtRegs() {
 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 for (MachineInstr &MI : MBB) {
 for (const MachineOperand &MO : MI.operands()) {
 if (!MO.isRegMask())
 continue;
-RegMaskSlots.push_back(Indexes->getInstructionIndex(&MI).getRegSlot());
+RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
 RegMaskBits.push_back(MO.getRegMask());
 }
 }
-// Some block ends, such as funclet returns, create masks.
+// Some block ends, such as funclet returns, create masks. Put the mask on
+// the last instruction of the block, because MBB slot index intervals are
+// half-open.
 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
-RegMaskSlots.push_back(Indexes->getMBBEndIdx(&MBB));
+assert(!MBB.empty() && "empty return block?");
+RegMaskSlots.push_back(
+Indexes->getInstructionIndex(MBB.back()).getRegSlot());
 RegMaskBits.push_back(Mask);
 }
 // Compute the number of register mask instructions in this block.
 RMB.second = RegMaskSlots.size() - RMB.first;
 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();
+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 <undef> flags
 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.
-bool DeadBeforeDef = false;
 unsigned VReg = LI.reg;
 if (MRI->shouldTrackSubRegLiveness(VReg)) {
 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
 MachineInstr *MI = getInstructionFromIndex(Def);
 MI->setRegisterDefReadUndef(VReg);
-DeadBeforeDef = true;
 }
 }
 if (I->end != Def.getDeadSlot())
 continue;
 MayHaveSplitComponents = true;
 } else {
 // This is a dead def. Make sure the instruction knows.
 MachineInstr *MI = getInstructionFromIndex(Def);
 assert(MI && "No instruction defining live value");
-MI->addRegisterDead(VReg, TRI);
+MI->addRegisterDead(LI.reg, TRI);
-// If we have a dead def that is completely separate from the rest of
-// the liverange then we rewrite it to use a different VReg to not violate
-// the rule that the liveness of a virtual register forms a connected
-// component. This should only happen if subregister liveness is tracked.
-if (DeadBeforeDef)
-MayHaveSplitComponents = true;
 if (dead && MI->allDefsAreDead()) {
 DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
 dead->push_back(MI);
 }
 }
 }
 return MayHaveSplitComponents;
 }
-void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
+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)) {
+for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
-MachineInstr *UseMI = MO.getParent();
+// Skip "undef" uses.
-if (UseMI->isDebugValue())
+if (!MO.readsReg())
 continue;
 // Maybe the operand is for a subregister we don't care about.
 unsigned SubReg = MO.getSubReg();
 if (SubReg != 0) {
 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
 if ((LaneMask & SR.LaneMask) == 0)
 continue;
 }
 // We only need to visit each instruction once.
-SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
+MachineInstr *UseMI = MO.getParent();
+SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
 if (Idx == LastIdx)
 continue;
 LastIdx = Idx;
 LiveQueryResult LRQ = SR.Query(Idx);
 assert(Segment != nullptr && "Missing segment for VNI");
 if (Segment->end != VNI->def.getDeadSlot())
 continue;
 if (VNI->isPHIDef()) {
 // This is a dead PHI. Remove it.
+DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 VNI->markUnused();
 SR.removeSegment(*Segment);
-DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 }
 }
 DEBUG(dbgs() << "Shrunk: " << SR << '\n');
 }
 void LiveIntervals::extendToIndices(LiveRange &LR,
-ArrayRef<SlotIndex> Indices) {
+ArrayRef<SlotIndex> Indices,
+ArrayRef<SlotIndex> Undefs) {
 assert(LRCalc && "LRCalc not initialized.");
 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 for (unsigned i = 0, e = Indices.size(); i != e; ++i)
-LRCalc->extend(LR, Indices[i]);
+LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, Undefs);
 }
 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
 SmallVectorImpl<SlotIndex> *EndPoints) {
 LiveQueryResult LRQ = LR.Query(Kill);
 if (EndPoints) EndPoints->push_back(MBBEnd);
 // Find all blocks that are reachable from KillMBB without leaving VNI's live
 // range. It is possible that KillMBB itself is reachable, so start a DFS
 // from each successor.
-typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy;
+typedef df_iterator_default_set<MachineBasicBlock*,9> VisitedTy;
 VisitedTy Visited;
 for (MachineBasicBlock::succ_iterator
 SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end();
 SuccI != SuccE; ++SuccI) {
 for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
 return true;
 }
 return false;
 }
-float
+float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
-LiveIntervals::getSpillWeight(bool isDef, bool isUse,
+const MachineBlockFrequencyInfo *MBFI,
-const MachineBlockFrequencyInfo *MBFI,
+const MachineInstr &MI) {
-const MachineInstr *MI) {
+BlockFrequency Freq = MBFI->getBlockFreq(MI.getParent());
-BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent());
 const float Scale = 1.0f / MBFI->getEntryFreq();
 return (isDef + isUse) * (Freq.getFrequency() * Scale);
 }
 LiveRange::Segment
-LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
+LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) {
 LiveInterval& Interval = createEmptyInterval(reg);
-VNInfo* VN = Interval.getNextValue(
+VNInfo *VN = Interval.getNextValue(
 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
 getVNInfoAllocator());
-LiveRange::Segment S(
+LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
-SlotIndex(getInstructionIndex(startInst).getRegSlot()),
+getMBBEndIdx(startInst.getParent()), VN);
-getMBBEndIdx(startInst->getParent()), VN);
 Interval.addSegment(S);
 return S;
 }
 for (MachineOperand &MO : MI->operands()) {
 if (MO.isRegMask())
 hasRegMask = true;
 if (!MO.isReg())
 continue;
-// Aggressively clear all kill flags.
+if (MO.isUse()) {
-// They are reinserted by VirtRegRewriter.
+if (!MO.readsReg())
-if (MO.isUse())
+continue;
+// Aggressively clear all kill flags.
+// They are reinserted by VirtRegRewriter.
 MO.setIsKill(false);
+}
 unsigned Reg = MO.getReg();
 if (!Reg)
 continue;
 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 LiveInterval &LI = LIS.getInterval(Reg);
 if (LI.hasSubRanges()) {
 unsigned SubReg = MO.getSubReg();
-LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
+LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
+: MRI.getMaxLaneMaskForVReg(Reg);
 for (LiveInterval::SubRange &S : LI.subranges()) {
 if ((S.LaneMask & LaneMask) == 0)
 continue;
 updateRange(S, Reg, S.LaneMask);
 }
 return;
 // Aggressively remove all kill flags from the old kill point.
 // Kill flags shouldn't be used while live intervals exist, they will be
 // reinserted by VirtRegRewriter.
 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
-for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO)
+for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
 if (MO->isReg() && MO->isUse())
 MO->setIsKill(false);
+// Is there a def before NewIdx which is not OldIdx?
+LiveRange::iterator Next = std::next(OldIdxIn);
+if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
+SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
+// If we are here then OldIdx was just a use but not a def. We only have
+// to ensure liveness extends to NewIdx.
+LiveRange::iterator NewIdxIn =
+LR.advanceTo(Next, NewIdx.getBaseIndex());
+// Extend the segment before NewIdx if necessary.
+if (NewIdxIn == E ||
+!SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
+LiveRange::iterator Prev = std::prev(NewIdxIn);
+Prev->end = NewIdx.getRegSlot();
+}
+// Extend OldIdxIn.
+OldIdxIn->end = Next->start;
+return;
+}
 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
 // invalid by overlapping ranges.
 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
 // If this was not a kill, then there was no def and we're done.
 if (!isKill)
 return;
 // Did we have a Def at OldIdx?
-OldIdxOut = std::next(OldIdxIn);
+OldIdxOut = Next;
 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
 return;
 } else {
 OldIdxOut = OldIdxIn;
 }
 OldIdxOut->start = OldIdxVNI->def;
 return;
 }
 // If we are here then we have a Definition at OldIdx which ends before
-// NewIdx. Moving across unrelated defs is not allowed; That means we either
+// NewIdx.
-// had a dead-def at OldIdx or the OldIdxOut segment ends at NewIdx.
-assert((OldIdxOut->end == OldIdx.getDeadSlot() ||
-SlotIndex::isSameInstr(OldIdxOut->end, NewIdxDef)) &&
-"Cannot move def below kill");
 // Is there an existing Def at NewIdx?
 LiveRange::iterator AfterNewIdx
 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
+bool OldIdxDefIsDead = OldIdxOut->end.isDead();
+if (!OldIdxDefIsDead &&
+SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
+// OldIdx is not a dead def, and NewIdxDef is inside a new interval.
+VNInfo *DefVNI;
+if (OldIdxOut != LR.begin() &&
+!SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
+OldIdxOut->start)) {
+// There is no gap between OldIdxOut and its predecessor anymore,
+// merge them.
+LiveRange::iterator IPrev = std::prev(OldIdxOut);
+DefVNI = OldIdxVNI;
+IPrev->end = OldIdxOut->end;
+} else {
+// The value is live in to OldIdx
+LiveRange::iterator INext = std::next(OldIdxOut);
+assert(INext != E && "Must have following segment");
+// We merge OldIdxOut and its successor. As we're dealing with subreg
+// reordering, there is always a successor to OldIdxOut in the same BB
+// We don't need INext->valno anymore and will reuse for the new segment
+// we create later.
+DefVNI = OldIdxVNI;
+INext->start = OldIdxOut->end;
+INext->valno->def = INext->start;
+}
+// If NewIdx is behind the last segment, extend that and append a new one.
+if (AfterNewIdx == E) {
+// OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
+// one position.
+//    |-  ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
+// => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
+std::copy(std::next(OldIdxOut), E, OldIdxOut);
+// The last segment is undefined now, reuse it for a dead def.
+LiveRange::iterator NewSegment = std::prev(E);
+*NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
+DefVNI);
+DefVNI->def = NewIdxDef;
+LiveRange::iterator Prev = std::prev(NewSegment);
+Prev->end = NewIdxDef;
+} else {
+// OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
+// one position.
+//    |-  ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
+// => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
+std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
+LiveRange::iterator Prev = std::prev(AfterNewIdx);
+// We have two cases:
+if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
+// Case 1: NewIdx is inside a liverange. Split this liverange at
+// NewIdxDef into the segment "Prev" followed by "NewSegment".
+LiveRange::iterator NewSegment = AfterNewIdx;
+*NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
+Prev->valno->def = NewIdxDef;
+*Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
+DefVNI->def = Prev->start;
+} else {
+// Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
+// turn Prev into a segment from NewIdx to AfterNewIdx->start.
+*Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
+DefVNI->def = NewIdxDef;
+assert(DefVNI != AfterNewIdx->valno);
+}
+}
+return;
+}
 if (AfterNewIdx != E &&
 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
 // that value.
 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
 if (!isKill)
 return;
 // At this point we have to move OldIdxIn->end back to the nearest
-// previous use but no further than NewIdx. Moreover OldIdx is a Def then
+// previous use or (dead-)def but no further than NewIdx.
-// we cannot have any intermediate uses or the move would be illegal.
+SlotIndex DefBeforeOldIdx
+= std::max(OldIdxIn->start.getDeadSlot(),
+NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
+OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
+// Did we have a Def at OldIdx? If not we are done now.
 OldIdxOut = std::next(OldIdxIn);
-// Did we have a Def at OldIdx?
+if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
-if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) {
-// No def, search for the nearest previous use.
-// This can never be an early clobber kill since there is no def.
-OldIdxIn->end = findLastUseBefore(Reg, LaneMask).getRegSlot();
-// We are done if there is no def at OldIdx.
 return;
-} else {
-// There can't have been any intermediate uses or defs, so move
-// OldIdxIn->end to NewIdx.
-OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
-}
 } else {
 OldIdxOut = OldIdxIn;
+OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
 }
 // If we are here then there is a Definition at OldIdx. OldIdxOut points
 // to the segment starting there.
 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
 }
 } else {
 // Previously nothing was live after NewIdx, so all we have to do now is
 // move the begin of OldIdxOut to NewIdx.
 if (!OldIdxDefIsDead) {
-// Leave the end point of a live def.
+// Do we have any intermediate Defs between OldIdx and NewIdx?
-OldIdxVNI->def = NewIdxDef;
+if (OldIdxIn != E &&
-OldIdxOut->start = NewIdxDef;
+SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
+// OldIdx is not a dead def and NewIdx is before predecessor start.
+LiveRange::iterator NewIdxIn = NewIdxOut;
+assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
+const SlotIndex SplitPos = NewIdxDef;
+// Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
+*OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
+OldIdxIn->valno);
+// OldIdxIn and OldIdxVNI are now undef and can be overridden.
+// We Slide [NewIdxIn, OldIdxIn) down one position.
+//    |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
+// => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
+std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
+// NewIdxIn is now considered undef so we can reuse it for the moved
+// value.
+LiveRange::iterator NewSegment = NewIdxIn;
+LiveRange::iterator Next = std::next(NewSegment);
+if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
+// There is no gap between NewSegment and its predecessor.
+*NewSegment = LiveRange::Segment(Next->start, SplitPos,
+Next->valno);
+*Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI);
+Next->valno->def = SplitPos;
+} else {
+// There is a gap between NewSegment and its predecessor
+// Value becomes live in.
+*NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
+NewSegment->valno->def = SplitPos;
+}
+} else {
+// Leave the end point of a live def.
+OldIdxOut->start = NewIdxDef;
+OldIdxVNI->def = NewIdxDef;
+if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
+OldIdxIn->end = NewIdx.getRegSlot();
+}
 } else {
 // OldIdxVNI is a dead def. It may have been moved across other values
 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
 // down one position.
 //    |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
 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, LaneBitmask LaneMask) {
+SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
+LaneBitmask LaneMask) {
 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
-SlotIndex LastUse = NewIdx;
+SlotIndex LastUse = Before;
 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
+if (MO.isUndef())
+continue;
 unsigned SubReg = MO.getSubReg();
 if (SubReg != 0 && LaneMask != 0
 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask) == 0)
 continue;
-const MachineInstr *MI = MO.getParent();
+const MachineInstr &MI = *MO.getParent();
 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
 if (InstSlot > LastUse && InstSlot < OldIdx)
-LastUse = InstSlot;
+LastUse = InstSlot.getRegSlot();
 }
 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");
+assert(Before < OldIdx && "Expected upwards move");
 SlotIndexes *Indexes = LIS.getSlotIndexes();
-MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx);
+MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
 // 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(
 MachineBasicBlock::iterator Begin = MBB->begin();
 while (MII != Begin) {
 if ((--MII)->isDebugValue())
 continue;
-SlotIndex Idx = Indexes->getInstructionIndex(MII);
+SlotIndex Idx = Indexes->getInstructionIndex(*MII);
-// Stop searching when NewIdx is reached.
+// Stop searching when Before is reached.
-if (!SlotIndex::isEarlierInstr(NewIdx, Idx))
+if (!SlotIndex::isEarlierInstr(Before, Idx))
-return NewIdx;
+return Before;
 // Check if MII uses Reg.
-for (MIBundleOperands MO(MII); MO.isValid(); ++MO)
+for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
-if (MO->isReg() &&
+if (MO->isReg() && !MO->isUndef() &&
 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
 TRI.hasRegUnit(MO->getReg(), Reg))
-return Idx;
+return Idx.getRegSlot();
 }
-// Didn't reach NewIdx. It must be the first instruction in the block.
+// Didn't reach Before. It must be the first instruction in the block.
-return NewIdx;
+return Before;
 }
 };
-void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) {
+void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
-assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
+assert(!MI.isBundled() && "Can't handle bundled instructions yet.");
 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
 Indexes->removeMachineInstrFromMaps(MI);
 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
-assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
+assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
-OldIndex < getMBBEndIdx(MI->getParent()) &&
+OldIndex < getMBBEndIdx(MI.getParent()) &&
 "Cannot handle moves across basic block boundaries.");
 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
-HME.updateAllRanges(MI);
+HME.updateAllRanges(&MI);
 }
-void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
+void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
-MachineInstr* BundleStart,
+MachineInstr &BundleStart,
 bool UpdateFlags) {
 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
-HME.updateAllRanges(MI);
+HME.updateAllRanges(&MI);
 }
 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
 const MachineBasicBlock::iterator End,
 const SlotIndex endIdx,
 LiveRange &LR, const unsigned Reg,
 LaneBitmask LaneMask) {
 LiveInterval::iterator LII = LR.find(endIdx);
 SlotIndex lastUseIdx;
+if (LII == LR.begin()) {
+// This happens when the function is called for a subregister that only
+// occurs _after_ the range that is to be repaired.
+return;
+}
 if (LII != LR.end() && LII->start < endIdx)
 lastUseIdx = LII->end;
 else
 --LII;
 for (MachineBasicBlock::iterator I = End; I != Begin;) {
 --I;
-MachineInstr *MI = I;
+MachineInstr &MI = *I;
-if (MI->isDebugValue())
+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(),
+for (MachineInstr::mop_iterator OI = MI.operands_begin(),
-OE = MI->operands_end(); OI != OE; ++OI) {
+OE = MI.operands_end();
+OI != OE; ++OI) {
 const MachineOperand &MO = *OI;
 if (!MO.isReg() || MO.getReg() != Reg)
 continue;
 unsigned SubReg = MO.getSubReg();
 MachineBasicBlock::iterator Begin,
 MachineBasicBlock::iterator End,
 ArrayRef<unsigned> 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))
+while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin))
 --Begin;
-while (End != MBB->end() && !Indexes->hasIndex(End))
+while (End != MBB->end() && !Indexes->hasIndex(*End))
 ++End;
 SlotIndex endIdx;
 if (End == MBB->end())
 endIdx = getMBBEndIdx(MBB).getPrevSlot();
 else
-endIdx = getInstructionIndex(End);
+endIdx = getInstructionIndex(*End);
 Indexes->repairIndexesInRange(MBB, Begin, End);
 for (MachineBasicBlock::iterator I = End; I != Begin;) {
 --I;
-MachineInstr *MI = I;
+MachineInstr &MI = *I;
-if (MI->isDebugValue())
+if (MI.isDebugValue())
 continue;
-for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
+for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
-MOE = MI->operands_end(); MOI != MOE; ++MOI) {
+MOE = MI.operands_end();
+MOI != MOE; ++MOI) {
 if (MOI->isReg() &&
 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
 !hasInterval(MOI->getReg())) {
 createAndComputeVirtRegInterval(MOI->getReg());
 }
 LR->removeValNo(VNI);
 }
 }
 void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
+// LI may not have the main range computed yet, but its subranges may
+// be present.
 VNInfo *VNI = LI.getVNInfoAt(Pos);
-if (VNI == nullptr)
+if (VNI != nullptr) {
-return;
+assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
 LI.removeValNo(VNI);
+}
-// Also remove the value in subranges.
+// Also remove the value defined in subranges.
 for (LiveInterval::SubRange &S : LI.subranges()) {
 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
-S.removeValNo(SVNI);
+if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
+S.removeValNo(SVNI);
 }
 LI.removeEmptySubRanges();
 }
 void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
 SplitLIs.push_back(&NewLI);
 }
 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
 }
-void LiveIntervals::renameDisconnectedComponents() {
+void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
-ConnectedSubRegClasses SubRegClasses(*this, *MRI);
+assert(LRCalc && "LRCalc not initialized.");
+LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
-// Iterate over all vregs. Note that we query getNumVirtRegs() the newly
+LRCalc->constructMainRangeFromSubranges(LI);
-// created vregs end up with higher numbers but do not need to be visited as
+}
-// there can't be any further splitting.
-for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
-unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
-LiveInterval *LI = VirtRegIntervals[Reg];
-if (LI == nullptr || !LI->hasSubRanges())
-continue;
-SubRegClasses.renameComponents(*LI);
-}
-}

Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/LiveIntervalAnalysis.cpp @ 120:1172e4bd9c6f