summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/CodeGen/LiveIntervalAnalysis.cpp186
1 files changed, 34 insertions, 152 deletions
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
index fcbe33ac9cb..bab3d0d01bd 100644
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -1044,24 +1044,6 @@ private:
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();
- }
- return;
- }
-
// Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
// invalid by overlapping ranges.
bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
@@ -1071,7 +1053,7 @@ private:
return;
// Did we have a Def at OldIdx?
- OldIdxOut = Next;
+ OldIdxOut = std::next(OldIdxIn);
if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
return;
} else {
@@ -1095,80 +1077,14 @@ private:
}
// If we are here then we have a Definition at OldIdx which ends before
- // NewIdx.
-
+ // NewIdx. Moving across unrelated defs is not allowed; That means we either
+ // 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 = INext->valno;
- INext->start = OldIdxOut->end;
- INext->valno = OldIdxVNI;
- 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
@@ -1214,18 +1130,24 @@ private:
return;
// At this point we have to move OldIdxIn->end back to the nearest
- // previous use or (dead-)def but no further than NewIdx.
- SlotIndex DefBeforeOldIdx = std::max(OldIdxIn->start.getDeadSlot(),
- NewIdx.getRegSlot());
- OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
+ // previous use but no further than NewIdx. Moreover OldIdx is a Def then
+ // we cannot have any intermediate uses or the move would be illegal.
- // Did we have a Def at OldIdx? If not we are done now.
OldIdxOut = std::next(OldIdxIn);
- if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
+ // Did we have a Def at OldIdx?
+ 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
@@ -1257,49 +1179,9 @@ private:
// Previously nothing was live after NewIdx, so all we have to do now is
// move the begin of OldIdxOut to NewIdx.
if (!OldIdxDefIsDead) {
- // Do we have any intermediate Defs between OldIdx and NewIdx?
- if (OldIdxIn != E &&
- 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);
- NewSegment->valno = OldIdxVNI;
- if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
- // There is no gap between NewSegment and its predecessor
- *NewSegment = LiveRange::Segment(Next->start, SplitPos,
- NewSegment->valno);
- NewSegment->valno->def = Next->start;
-
- *Next = LiveRange::Segment(SplitPos, Next->end, Next->valno);
- Next->valno->def = SplitPos;
- } else {
- // There is a gap between NewSegment and its predecessor
- // Value become live in
- *NewSegment = LiveRange::Segment(SplitPos, Next->start,
- NewSegment->valno);
- 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();
- }
+ // Leave the end point of a live def.
+ OldIdxVNI->def = NewIdxDef;
+ OldIdxOut->start = NewIdxDef;
} 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)
@@ -1333,10 +1215,10 @@ private:
}
// Return the last use of reg between NewIdx and OldIdx.
- SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
- LaneBitmask LaneMask) {
+ SlotIndex findLastUseBefore(unsigned Reg, LaneBitmask LaneMask) {
+
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- SlotIndex LastUse = Before;
+ SlotIndex LastUse = NewIdx;
for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
unsigned SubReg = MO.getSubReg();
if (SubReg != 0 && LaneMask != 0
@@ -1346,16 +1228,16 @@ private:
const MachineInstr *MI = MO.getParent();
SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
if (InstSlot > LastUse && InstSlot < OldIdx)
- LastUse = InstSlot.getRegSlot();
+ LastUse = InstSlot;
}
return LastUse;
}
// This is a regunit interval, so scanning the use list could be very
// expensive. Scan upwards from OldIdx instead.
- assert(Before < OldIdx && "Expected upwards move");
+ assert(NewIdx < OldIdx && "Expected upwards move");
SlotIndexes *Indexes = LIS.getSlotIndexes();
- MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
+ 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().
@@ -1371,19 +1253,19 @@ private:
continue;
SlotIndex Idx = Indexes->getInstructionIndex(MII);
- // Stop searching when Before is reached.
- if (!SlotIndex::isEarlierInstr(Before, Idx))
- return Before;
+ // 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.getRegSlot();
+ return Idx;
}
- // Didn't reach Before. It must be the first instruction in the block.
- return Before;
+ // Didn't reach NewIdx. It must be the first instruction in the block.
+ return NewIdx;
}
};
OpenPOWER on IntegriCloud