SplitKit: Fix liveness recomputation in some remat cases.

[MatzeB]

Summary

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 has a live interval with 3 value numbers (for the BB0, BB1 and
BB2 parts). Now SplitKit tries to rematerialize the value in BB2 before the use.
This can succeed if this is actually a secondary split
SplitKit can still trace it all back to a single original definition.

In case of rematerialization live ranges may become shorter and need to be recomputed.
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.

Do you guys want a 500kb testcase (that is the size after reducing it with bugpoint) in the repository for this?

[wmi]

Do you guys want a 500kb testcase (that is the size after reducing it with bugpoint) in the repository for this?

Maybe you can catch a smaller testcase by adding assert(0 && "catch a testcase") before SplitKit.cpp:1460 and then use credue to reduce the testcase? I tried that and got a 4k .ll test, and you may get a even smaller one.

test.ll4 KBDownload

[kparzysz]

This looks ok to me, just a couple of nitpicks.

lib/CodeGen/SplitKit.cpp

1458

In the text of the assertion, should it be "value not available..."? Also there is no variable PhiVNI.

1462

Missing space between while and (.

[MatzeB]

lib/CodeGen/SplitKit.cpp

1458

Even though most people write an error message here that should be displayed when the assert fails.

My personal aesthetics really want me to read an assert as:
"assert that ...".

From that perspective I rather state the condition that needs to be true (in this case the value must be available in the predecessor). You are right in that I should write "VNI" instead of "PhiVNI" here. I'll change the text to "value must be available in VNI predecessor".

[qcolombet]

LGTM with the nitpicks mentioned by Krzysztof.

Also, any luck with reducing the test case even more?

Although Wei's method may not reproduce the observed effect, it will still exercise the new code and potentially the final live-ranges are verifiable (as without this patch the verifier would have complained)

[qcolombet]

lib/CodeGen/SplitKit.cpp

1458

FWIW, the coding standard says to put error message:
To further assist with debugging, make sure to put some kind of error message in the assertion statement, which is printed if the assertion is tripped.

http://www.llvm.org/docs/CodingStandards.html#assert-liberally

Therefore, I would second Krzysztof here.

[MatzeB]

Nice trick wmi, I tried it and could create a very small testcase that would hit the problematic code in question. Unfortunately those small inputs would not fail in -verify-machineinstrs mode without this patch (I suspect the liveranges didn't happen to actually be invalid even though we ignored the fact that PHIs can have inputs).

So I instead I manually beat against the test for multiple hours now and reduced it to 245 which should be good enough to check in.

lib/CodeGen/SplitKit.h

private:
   /// Return the new LI value.
   VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx,
                    bool Original);
 
   /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
   /// 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.
   VNInfo *defFromParent(unsigned RegIdx,
                         VNInfo *ParentVNI,
                         SlotIndex UseIdx,
                         MachineBasicBlock &MBB,
                         MachineBasicBlock::iterator I);

lib/CodeGen/SplitKit.cpp

if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
     InsP.first->second = ValueForcePair(nullptr, Force);
   }
 
   // This is a complex mapping, add liveness for VNI
   addDeadDef(*LI, VNI, Original);
   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
   // set the force bit.
   if (!VNI) {
     VFP.setInt(true);
     return;
   }
SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
   assert(MI && "No instruction at index");
 
   // In spill mode, make live ranges as short as possible by inserting the copy
   // before MI.  This is only possible if that instruction doesn't redefine the
   // value.  The inserted COPY is not a kill, and we don't need to recompute
   // 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;
   }
 
   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
                               std::next(MachineBasicBlock::iterator(MI)));
   return VNI->def;
 }
void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
          "Parent changes value in extended range");
   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
          "Range cannot span basic blocks");
 
   // 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());
 }
 
 //===----------------------------------------------------------------------===//
 //                                  Spill modes
 //===----------------------------------------------------------------------===//
for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
     if (!AssignI.valid() || AssignI.start() >= Def)
       continue;
     // If MI doesn't kill the assigned register, just leave it.
     if (AssignI.stop() != Def)
       continue;
     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);
       AssignI.setStop(Kill);
     }
   }
 }
 
for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
         } else if (MDT.dominates(MBB1, MBB2)) {
           DominatedVNIs.insert(*It2);
         } else if (MDT.dominates(MBB2, MBB1)) {
           DominatedVNIs.insert(*It1);
         }
       }
     }
     if (!DominatedVNIs.empty()) {
-      forceRecompute(0, ParentVNI);
+      forceRecompute(0, *ParentVNI);
       for (auto VNI : DominatedVNIs) {
         BackCopies.push_back(VNI);
       }
       DominatedVNIs.clear();
     }
   }
 }
 
for (VNInfo *VNI : LI->valnos) {
     if (VNI->isUnused())
       continue;
     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
     const DomPair &Dom = NearestDom[ParentVNI->id];
     if (!Dom.first || Dom.second == VNI->def ||
         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
   // redundant BackCopies in speed mode.
   if (SpillMode == SM_Speed && !NotToHoistSet.empty())
     computeRedundantBackCopies(NotToHoistSet, BackCopies);
 
   removeBackCopies(BackCopies);
void SplitEditor::deleteRematVictims() {
   }
 
   if (Dead.empty())
     return;
 
   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;
 
   // At this point, the live intervals in Edit contain VNInfos corresponding to
   // the inserted copies.
 
   // Add the original defs from the parent interval.
   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
     if (ParentVNI->isUnused())
       continue;
     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
     defValue(RegIdx, ParentVNI, ParentVNI->def, true);
 
     // 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.
   switch (SpillMode) {
   case SM_Partition:
     // Leave all back-copies as is.
     break;
   case SM_Size: