SplitKit: Fix liveness recomputation in some remat cases.
Example situation:
```
BB0:
%0 = ...
use %0
; ...
condjump BB1
jmp BB2
BB1:
%0 = ... ; rematerialized def from above (from earlier split step)
jmp BB2
BB2:
; ...
use %0
```
%0 will have a live interval with 3 value numbers (for the BB0, BB1 and
BB2 parts). Now SplitKit tries and succeeds in rematerializing the value
number in BB2 (This only works because it is a secondary split so
SplitKit is can trace this back to a single original def).
We need to recompute all live ranges affected by a value number that we
rematerialize. The case that we missed before is that when the value
that is rematerialized is at a join (Phi VNI) then we also have to
recompute liveness for the predecessor VNIs.
rdar://35699130
Differential Revision: https://reviews.llvm.org/D42667
llvm-svn: 324039
diff --git a/llvm/lib/CodeGen/SplitKit.cpp b/llvm/lib/CodeGen/SplitKit.cpp
index c99c3b0..1628ee2 100644
--- a/llvm/lib/CodeGen/SplitKit.cpp
+++ b/llvm/lib/CodeGen/SplitKit.cpp
@@ -491,9 +491,8 @@
return VNI;
}
-void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
- assert(ParentVNI && "Mapping NULL value");
- ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
+void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
+ ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
VNInfo *VNI = VFP.getPointer();
// ParentVNI was either unmapped or already complex mapped. Either way, just
@@ -777,7 +776,7 @@
// the source live range. The spiller also won't try to hoist this copy.
if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
MI->readsVirtualRegister(Edit->getReg())) {
- forceRecompute(0, ParentVNI);
+ forceRecompute(0, *ParentVNI);
defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
return Idx;
}
@@ -835,7 +834,7 @@
// The complement interval will be extended as needed by LRCalc.extend().
if (ParentVNI)
- forceRecompute(0, ParentVNI);
+ forceRecompute(0, *ParentVNI);
DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
RegAssign.insert(Start, End, OpenIdx);
DEBUG(dump());
@@ -878,7 +877,7 @@
unsigned RegIdx = AssignI.value();
if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n');
- forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
+ forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
} else {
SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot();
DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);
@@ -982,7 +981,7 @@
}
}
if (!DominatedVNIs.empty()) {
- forceRecompute(0, ParentVNI);
+ forceRecompute(0, *ParentVNI);
for (auto VNI : DominatedVNIs) {
BackCopies.push_back(VNI);
}
@@ -1102,7 +1101,7 @@
NotToHoistSet.count(ParentVNI->id))
continue;
BackCopies.push_back(VNI);
- forceRecompute(0, ParentVNI);
+ forceRecompute(0, *ParentVNI);
}
// If it is not beneficial to hoist all the BackCopies, simply remove
@@ -1428,6 +1427,41 @@
Edit->eliminateDeadDefs(Dead, None, &AA);
}
+void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
+ // Fast-path for common case.
+ if (!ParentVNI.isPHIDef()) {
+ for (unsigned I = 0, E = Edit->size(); I != E; ++I)
+ forceRecompute(I, ParentVNI);
+ return;
+ }
+
+ // Trace value through phis.
+ SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
+ SmallVector<const VNInfo *, 4> WorkList;
+ Visited.insert(&ParentVNI);
+ WorkList.push_back(&ParentVNI);
+
+ const LiveInterval &ParentLI = Edit->getParent();
+ const SlotIndexes &Indexes = *LIS.getSlotIndexes();
+ do {
+ const VNInfo &VNI = *WorkList.back();
+ WorkList.pop_back();
+ for (unsigned I = 0, E = Edit->size(); I != E; ++I)
+ forceRecompute(I, VNI);
+ if (!VNI.isPHIDef())
+ continue;
+
+ MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
+ for (const MachineBasicBlock *Pred : MBB.predecessors()) {
+ SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
+ VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
+ assert(PredVNI && "Value available in PhiVNI predecessor");
+ if (Visited.insert(PredVNI).second)
+ WorkList.push_back(PredVNI);
+ }
+ } while(!WorkList.empty());
+}
+
void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
++NumFinished;
@@ -1444,8 +1478,7 @@
// Force rematted values to be recomputed everywhere.
// The new live ranges may be truncated.
if (Edit->didRematerialize(ParentVNI))
- for (unsigned i = 0, e = Edit->size(); i != e; ++i)
- forceRecompute(i, ParentVNI);
+ forceRecomputeVNI(*ParentVNI);
}
// Hoist back-copies to the complement interval when in spill mode.
diff --git a/llvm/lib/CodeGen/SplitKit.h b/llvm/lib/CodeGen/SplitKit.h
index c060889..2dafaf5 100644
--- a/llvm/lib/CodeGen/SplitKit.h
+++ b/llvm/lib/CodeGen/SplitKit.h
@@ -357,7 +357,11 @@
/// recomputed by LiveRangeCalc::extend regardless of the number of defs.
/// This is used for values whose live range doesn't match RegAssign exactly.
/// They could have rematerialized, or back-copies may have been moved.
- void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI);
+ void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI);
+
+ /// Calls forceRecompute() on any affected regidx and on ParentVNI
+ /// predecessors in case of a phi definition.
+ void forceRecomputeVNI(const VNInfo &ParentVNI);
/// defFromParent - Define Reg from ParentVNI at UseIdx using either
/// rematerialization or a COPY from parent. Return the new value.