Account for undef values from predecessors in extendSegmentsToUses
It is legal for a PHI node not to have a live value in a predecessor
as long as the end of the predecessor is jointly dominated by an undef
value.
llvm-svn: 335607
diff --git a/llvm/lib/CodeGen/LiveIntervals.cpp b/llvm/lib/CodeGen/LiveIntervals.cpp
index f4a56a3..8c38705 100644
--- a/llvm/lib/CodeGen/LiveIntervals.cpp
+++ b/llvm/lib/CodeGen/LiveIntervals.cpp
@@ -358,26 +358,40 @@
}
}
-using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
-
-static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
- ShrinkToUsesWorkList &WorkList,
- const LiveRange &OldRange) {
+void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
+ ShrinkToUsesWorkList &WorkList,
+ unsigned Reg, LaneBitmask LaneMask) {
// Keep track of the PHIs that are in use.
SmallPtrSet<VNInfo*, 8> UsedPHIs;
// Blocks that have already been added to WorkList as live-out.
SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
+ auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
+ -> const LiveRange& {
+ if (M.none())
+ return I;
+ for (const LiveInterval::SubRange &SR : I.subranges()) {
+ if ((SR.LaneMask & M).any()) {
+ assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
+ return SR;
+ }
+ }
+ llvm_unreachable("Subrange for mask not found");
+ };
+
+ const LiveInterval &LI = getInterval(Reg);
+ const LiveRange &OldRange = getSubRange(LI, LaneMask);
+
// 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 = Indexes.getMBBFromIndex(Idx.getPrevSlot());
- SlotIndex BlockStart = Indexes.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 = LR.extendInBlock(BlockStart, Idx)) {
+ if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
assert(ExtVNI == VNI && "Unexpected existing value number");
(void)ExtVNI;
// Is this a PHIDef we haven't seen before?
@@ -388,7 +402,7 @@
for (const MachineBasicBlock *Pred : MBB->predecessors()) {
if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
+ SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
// A predecessor is not required to have a live-out value for a PHI.
if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
WorkList.push_back(std::make_pair(Stop, PVNI));
@@ -398,16 +412,28 @@
// VNI is live-in to MBB.
LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
- LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
+ Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
// Make sure VNI is live-out from the predecessors.
for (const MachineBasicBlock *Pred : MBB->predecessors()) {
if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
- assert(OldRange.getVNInfoBefore(Stop) == VNI &&
- "Wrong value out of predecessor");
- WorkList.push_back(std::make_pair(Stop, VNI));
+ SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
+ if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
+ assert(OldVNI == VNI && "Wrong value out of predecessor");
+ WorkList.push_back(std::make_pair(Stop, VNI));
+ } else {
+#ifndef NDEBUG
+ // There was no old VNI. Verify that Stop is jointly dominated
+ // by <undef>s for this live range.
+ assert(LaneMask.any() &&
+ "Missing value out of predecessor for main range");
+ SmallVector<SlotIndex,8> Undefs;
+ LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
+ assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
+ "Missing value out of predecessor for subrange");
+#endif
+ }
}
}
}
@@ -460,7 +486,7 @@
// 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);
+ extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
// Move the trimmed segments back.
li->segments.swap(NewLR.segments);
@@ -558,7 +584,7 @@
// 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);
+ extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
// Move the trimmed ranges back.
SR.segments.swap(NewLR.segments);
diff --git a/llvm/lib/CodeGen/LiveRangeCalc.cpp b/llvm/lib/CodeGen/LiveRangeCalc.cpp
index 66c23b7..0432494 100644
--- a/llvm/lib/CodeGen/LiveRangeCalc.cpp
+++ b/llvm/lib/CodeGen/LiveRangeCalc.cpp
@@ -584,3 +584,24 @@
}
} while (Changed);
}
+
+bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
+ ArrayRef<SlotIndex> Defs,
+ const SlotIndexes &Indexes) {
+ const MachineFunction &MF = *MBB->getParent();
+ BitVector DefBlocks(MF.getNumBlockIDs());
+ for (SlotIndex I : Defs)
+ DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
+
+ SetVector<unsigned> PredQueue;
+ PredQueue.insert(MBB->getNumber());
+ for (unsigned i = 0; i != PredQueue.size(); ++i) {
+ unsigned BN = PredQueue[i];
+ if (DefBlocks[BN])
+ return true;
+ const MachineBasicBlock *B = MF.getBlockNumbered(BN);
+ for (const MachineBasicBlock *P : B->predecessors())
+ PredQueue.insert(P->getNumber());
+ }
+ return false;
+}
diff --git a/llvm/lib/CodeGen/LiveRangeCalc.h b/llvm/lib/CodeGen/LiveRangeCalc.h
index c4914f2..b8502ac 100644
--- a/llvm/lib/CodeGen/LiveRangeCalc.h
+++ b/llvm/lib/CodeGen/LiveRangeCalc.h
@@ -282,6 +282,15 @@
/// Every predecessor of a live-in block must have been given a value with
/// setLiveOutValue, the value may be null for live-trough blocks.
void calculateValues();
+
+ /// A diagnostic function to check if the end of the block @p MBB is
+ /// jointly dominated by the blocks corresponding to the slot indices
+ /// in @p Defs. This function is mainly for use in self-verification
+ /// checks.
+ LLVM_ATTRIBUTE_UNUSED
+ static bool isJointlyDominated(const MachineBasicBlock *MBB,
+ ArrayRef<SlotIndex> Defs,
+ const SlotIndexes &Indexes);
};
} // end namespace llvm
