Fix a bug when hoist spill to a BB with landingpad successor

[wmi]

Summary

This is to fix the bug in https://llvm.org/bugs/show_bug.cgi?id=27612.

When spill is hoisted to a BB with landingpad successor, and if the VNI of the spill reg lives into the landingpad successor, the
spill should be inserted before the call which may throw exception. I uses SplitAnalysis::computeLastSplitPoint to get the insert point.

[echristo]

lib/CodeGen/InlineSpiller.cpp

1398

Needs a comment of why you want to skip the analysis here.

test/CodeGen/X86/hoist-spill-lpad.ll

4–6

I think this can be reworded in a more general way such that it's clear if this breaks what's going on. If I understand correctly we need to use the split point as the insert location because the spill reg could be live through the next block?

[wmi]

Address Eric's comment.

lib/CodeGen/InlineSpiller.cpp

1398

Comments added

test/CodeGen/X86/hoist-spill-lpad.ll

4–6

Yes, the spill should live through both the fall through path and the landingpad path of the same call which may throw, so we should use the split point as the insert point. comment fixed.

[majnemer]

lib/CodeGen/SplitKit.h

124–126 ↗

(On Diff #56094)

It is a little confusing to have a function called analyze which takes a parameter named SkipAnalyze. Perhaps it would be more obvious what you are trying to achieve if the functionality that you desired from analyze was split out into another method.

[wmi]

Address David's comment.

[echristo]

lib/CodeGen/InlineSpiller.cpp

1398

Capital 'S' at the beginning of the sentence.

Perhaps: "Use the current interval for SA to compute a safe insertion point in the target basic block."

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56207)

I'm not sure I get it after your changes. Can you explain what you're doing now with setParent in a bit more detail?

[wmi]

lib/CodeGen/InlineSpiller.cpp

1398

Thanks. That is a better description. will fix it.

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56207)

I use setParent to set SplitAnalysis::CurLi, which will be used in SplitAnalysis::computeLastSplitPoint to compute the last split point, i.e., insert point of bb.

124–126 ↗

(On Diff #56094)

I only need to set current liveinterval for SplitAnalysis. I creat a method SplitAnalysis::setParent for it.

[echristo]

One inline comment about the patch and a couple about the testcase. If you could look through the testcase and see if there's anything else that can be removed it'd be appreciated.

-eric

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56207)

Why aren't you just doing something like:

if (SA->getParent() != OrigLi)
  analyze(OrigLi);
SA->getLastSplitPointIter(BB);

or some such? I'm probably missing something here :)

test/CodeGen/X86/hoist-spill-lpad.ll

113

Can delete.

124

Can delete.

[wmi]

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56207)

Because there are more than one place (now two, but maybe more in the future) where getLastSplitPointIter is called, I choose to set CurLI for SA at the beginning.

test/CodeGen/X86/hoist-spill-lpad.ll

113

unused func decls removed.

[echristo]

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56305)

I could be missing something but analyze sets the interval and does the analysis which is then cached, but the setParent you've got doesn't do the analysis and so isn't updating aspects of SA right (the computation is happening as part of getLastSplitPointIter, but the clear and analyzeUses isn't happening)? You might not be using it, but it seems odd to leave it in an indeterminate state.

[wmi]

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56305)

The cache LastSplitPoint[] in SA is not changed even if CurLI is changed, so we don't need to updated it every time we call setParent (you can see that in SplitAnalysis::clear(), LastSplitPoint is not cleared there. It is also not set by analyzeUses()).

SplitAnalysis::clear() is used to clear several caches of other analysises set up in SplitAnalysis::analyzeUses(). Those analysises are unused by hoistspill for now. To make SA a little bit light weighted. I choose not to call analyze(). If other analysises in SplitAnalysis will be used in hoistspill in the future, we can easily change setParent() to analyze() to make them available.

I will add a comment before setParent() is called to make it clear.

[echristo]

lib/CodeGen/SplitKit.h

124–127 ↗

(On Diff #56305)

I see what you mean. Basically getLastSplitPoint could be static if it wasn't for the cache. I worry about surprising people with bugs with setting the LI and then not resetting the rest of the object.

I think this needs a bit more documentation in general. Personally I'm not a huge fan of side-stepping this aspect of the analysis here, but I'm not sure we should pull it out or do something else either. I'm probably going to have to defer to Quentin or Matthias here.

[MatzeB]

I just filed http://llvm.org/PR27659 which we should fix in the long term.

For the short term we do indeed need code like the one found in SplitKit::computeLastSplitPoint(). However we should not need to insert the whole of SplitKit just to determine a good insertion point. I think what we should do instead is:

• Factor the code in SplitKit::computeLastSplitPoint out into an independent function which is then used by SplitKit and the InlineSpiller.
• I don't know how many queries the InlineSpiller will make, but maybe we can live without the caching logic in SplitKit here? Otherwise the best action would be to pull that out into a custom class as well which is then used by SplitKit and the InlinerSpiller.

[qcolombet]

Hi Wei,

I’ll second Matthias that we should not need the full split kit here and refactoring should be the way to go.
I would however like to keep the caching mechanism at least in split kit. So, like pretty much Matthias said:

• Introduce a utility function to query the last split point.
• Introduce a class that does the caching on top of that utility function. (That could even be an analysis pass, but that is probably overkill.)

That way if we have users that do not want the caching mechanism (for hoist spill?) they have a direct access to the utility function, otherwise they use the class (for split kit).

Couple of comments on the test case:
I believe this is a test case reduced by bug point, and I believe you can make it smaller and more robust to other changes. Basically come-up with a simple CFG pattern where the spill hoisting is triggered (a diamond should be enough, right), add a lpad at the strategic point, then add a few inlineasm nop with side effects clobbering all the registers (or at least a lot o them) to create high register pressure points where need be.

I know this is a hassle but there are reasons why I am asking this:

1. This kind of test cases happens to work because we are not removing undef branches and such. (We could imagine this won’t stand in the future.)
2. When the test fails because of regalloc (or other) changes, this is pretty much impossible to keep the coverage they were providing and we unfortunately just remove them :(.

Cheers,
-Quentin

test/CodeGen/X86/hoist-spill-lpad.ll

9

Could we use simpler name for the function :).

[wmi]

Matthias, Quentin and Eric, thanks for the suggestions. I separated the extraction of LastSplitPoint into another patch. I think it is still beneficial to use cache for hoistspill case, so both SplitAnalysis and HoistSpillHelper will use the LSplitPointAnalysis class.

I will start to work on the testcase now.

[wmi]

Create a testcase hoist-spill-lpad.ll based on hoist-spill-lpad.cc
update patch based on http://reviews.llvm.org/D20027

[MatzeB]

You should avoid unnecessary heap allocation of the analysis (see below).
As for the testcase I believe what Quentin was asking was not to create a new .cc file as a test but rather to simplify and cleanup the hoist-spill-lpad.ll according to his suggestions.

lib/CodeGen/InlineSpiller.cpp

72

This comment doesn't contain any additional information over what the user would found in the description of the InsertPointAnalysis class. I'd leave it out.

72–73

This should better be a member instead of being allocated on the heap. You can add a reset() method to InsertPointAnalysis to enable this.

[wmi]

As for the testcase I believe what Quentin was asking was not to create a new .cc file as a test but rather to simplify and cleanup the hoist-spill-lpad.ll according to his suggestions.

hoist-spill-lpad.ll is a new testcase generated from the .cc file. I uploaded the .cc file too for easier review. I think the
new hoist-spill-lpad.ll testcase will be relatively stable for other compiler changes.

Thanks,
Wei.

lib/CodeGen/InlineSpiller.cpp

72

will remove it.

72–73

ok, I will make InsertPointAnalysis a member of HoistSpillHelper. reset() is not needed because the lifetimes of InsertPointAnalysis, the LastSplitPoint[] cache and HoistSpillHelper will be the same. When we only reset InsertPointAnalysis::CurLI, the cache is still valid.

[wmi]

Make InsertPointAnalysis a member in class HoistSpillHelper.

[MatzeB]

So does the LastInsertPointAnalysis cache depend on the current LiveInterval?

• If so then we should not make it a member of the analysis class and just pass the liveinterval as a parameter in each query.
• If however the cache does depend on the current interval then we miss a cache clear here when we change the current interval.

[wmi]

So does the LastInsertPointAnalysis cache depend on the current LiveInterval?

• If so then we should not make it a member of the analysis class and just pass the liveinterval as a parameter in each query.
• If however the cache does depend on the current interval then we miss a cache clear here when we change the current interval.

No, LastInsertPoint cache doesn't depend on current LiveInterval. The
cache only records the two possible insert points of a BB - Before
BB's FirstTerminator, and before the last call if BB has landingpad
successor, which are unrelated with LiveInterval. The cache is used to
accelerate the determination of the final insert point to insert
spill/split for current LiveInterval.

Thanks,
Wei.

[MatzeB]

In D19884#427795, @wmi wrote:

So does the LastInsertPointAnalysis cache depend on the current LiveInterval?

• If so then we should not make it a member of the analysis class and just pass the liveinterval as a parameter in each query.
• If however the cache does depend on the current interval then we miss a cache clear here when we change the current interval.

No, LastInsertPoint cache doesn't depend on current LiveInterval. The
cache only records the two possible insert points of a BB - Before
BB's FirstTerminator, and before the last call if BB has landingpad
successor, which are unrelated with LiveInterval. The cache is used to
accelerate the determination of the final insert point to insert
spill/split for current LiveInterval.

Thanks,
Wei.

Ok then this patch LGTM.

I would apreciate it, if you could change current live interval to just be passed to the InsertAnalaysis queries instead of being a member in a follow-up commit.

[wmi]

Ok, I will do that. Thanks to you, Quentin and Eric for the helpful comments!

Wei.

[MatzeB]

This was committed in r269249 (I guess phab didn't pickup the differential revision line because it had a dot at the end)

hoist-spill-lpad.cc

+long a[20];
+void goo();
+
+void foo() {
+  long r1;
+
+  r1 = a[1];
+
+  try {
+    goo();
+  } catch (int param) {
+    a[2] = r1;
+    asm volatile ("":::"%rax", "%rbx", "%rcx", "%rdx", "%rsi", "%rdi", "%rbp", "%r8", "%r9", "%r10", "%r11", "%r12", "%r13", "%r14", "%r15", "memory");
+    a[3] = r1;
+  }
+
+  a[4] = r1;
+  asm volatile ("":::"%rax", "%rbx", "%rcx", "%rdx", "%rsi", "%rdi", "%rbp", "%r8", "%r9", "%r10", "%r11", "%r12", "%r13", "%r14", "%r15", "memory");
+  a[5] = r1;
+}
+

lib/CodeGen/InlineSpiller.cpp

 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // The inline spiller modifies the machine function directly instead of
 // inserting spills and restores in VirtRegMap.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Spiller.h"
+#include "SplitKit.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
class HoistSpillHelper : private LiveRangeEdit::Delegate {
   MachineLoopInfo &Loops;
   VirtRegMap &VRM;
   MachineFrameInfo &MFI;
   MachineRegisterInfo &MRI;
   const TargetInstrInfo &TII;
   const TargetRegisterInfo &TRI;
   const MachineBlockFrequencyInfo &MBFI;
 
+  InsertPointAnalysis IPA;
+
   // Map from StackSlot to its original register.
   DenseMap<int, unsigned> StackSlotToReg;
   // Map from pair of (StackSlot and Original VNI) to a set of spills which
   // have the same stackslot and have equal values defined by Original VNI.
   // These spills are mergeable and are hoist candiates.
   typedef MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>
       MergeableSpillsMap;
   MergeableSpillsMap MergeableSpills;
HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
       : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
         LSS(pass.getAnalysis<LiveStacks>()),
         AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
         MDT(pass.getAnalysis<MachineDominatorTree>()),
         Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
         MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
         TII(*mf.getSubtarget().getInstrInfo()),
         TRI(*mf.getSubtarget().getRegisterInfo()),
-        MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
+        MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
+        IPA(LIS, mf.getNumBlockIDs()) {}
 
   void addToMergeableSpills(MachineInstr *Spill, int StackSlot,
                             unsigned Original);
   bool rmFromMergeableSpills(MachineInstr *Spill, int StackSlot);
   void hoistAllSpills();
   void LRE_DidCloneVirtReg(unsigned, unsigned) override;
 };
 

 }
 
 /// Check BB to see if it is a possible target BB to place a hoisted spill,
 /// i.e., there should be a living sibling of OrigReg at the insert point.
 ///
 bool HoistSpillHelper::isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI,
                                      MachineBasicBlock &BB, unsigned &LiveReg) {
   SlotIndex Idx;
-  MachineBasicBlock::iterator MI = BB.getFirstTerminator();
+  MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(BB);
   if (MI != BB.end())
     Idx = LIS.getInstructionIndex(*MI);
   else
     Idx = LIS.getMBBEndIdx(&BB).getPrevSlot();
   SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg];
   assert((LIS.getInterval(OrigReg)).getVNInfoAt(Idx) == &OrigVNI &&
          "Unexpected VNI");
 
for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
     if (!MRI.def_empty(Reg))
       Virt2SiblingsMap[Original].insert(Reg);
   }
 
   // Each entry in MergeableSpills contains a spill set with equal values.
   for (auto &Ent : MergeableSpills) {
     int Slot = Ent.first.first;
     unsigned OrigReg = SlotToOrigReg[Slot];
+    LiveInterval &OrigLI = LIS.getInterval(OrigReg);
+    IPA.setInterval(&OrigLI);
     VNInfo *OrigVNI = Ent.first.second;
     SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
     if (Ent.second.empty())
       continue;
 
     DEBUG({
       dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
              << "Equal spills in BB: ";
       for (const auto spill : EqValSpills)
         dbgs() << spill->getParent()->getNumber() << " ";
       dbgs() << "\n";
     });
 
     // SpillsToRm is the spill set to be removed from EqValSpills.
     SmallVector<MachineInstr *, 16> SpillsToRm;
     // SpillsToIns is the spill set to be newly inserted after hoisting.
     DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;
 
     runHoistSpills(OrigReg, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
 
     DEBUG({
       dbgs() << "Finally inserted spills in BB: ";
       for (const auto Ispill : SpillsToIns)
         dbgs() << Ispill.first->getNumber() << " ";
       dbgs() << "\nFinally removed spills in BB: ";
       for (const auto Rspill : SpillsToRm)
         dbgs() << Rspill->getParent()->getNumber() << " ";
       dbgs() << "\n";
     });
 
     // Stack live range update.
     LiveInterval &StackIntvl = LSS.getInterval(Slot);
-    if (!SpillsToIns.empty() || !SpillsToRm.empty()) {
-      LiveInterval &OrigLI = LIS.getInterval(OrigReg);
+    if (!SpillsToIns.empty() || !SpillsToRm.empty())
       StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
                                      StackIntvl.getValNumInfo(0));
-    }
 
     // Insert hoisted spills.
     for (auto const Insert : SpillsToIns) {
       MachineBasicBlock *BB = Insert.first;
       unsigned LiveReg = Insert.second;
-      MachineBasicBlock::iterator MI = BB->getFirstTerminator();
+      MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(*BB);
       TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot,
                               MRI.getRegClass(LiveReg), &TRI);
       LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI);
       ++NumSpills;
     }
 
     // Remove redundent spills or change them to dead instructions.
     NumSpills -= SpillsToRm.size();

test/CodeGen/X86/hoist-spill-lpad.ll

+; RUN: llc < %s | FileCheck %s
+;
+; PR27612. The following spill is hoisted from two locations: the fall
+; through succ block and the landingpad block of a call which may throw
+; exception. If it is not hoisted before the call, the spill will be
+; missing on the landingpad path.
+;
+; CHECK-LABEL: _Z3foov:
+; CHECK: movq  %rbx, (%rsp)          # 8-byte Spill
+; CHECK-NEXT: callq _Z3goov
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@a = global [20 x i64] zeroinitializer, align 16
+@_ZTIi = external constant i8*
+
+; Function Attrs: uwtable
+define void @_Z3foov() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %tmp = load i64, i64* getelementptr inbounds ([20 x i64], [20 x i64]* @a, i64 0, i64 1), align 8
+  invoke void @_Z3goov()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %tmp1 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp2 = extractvalue { i8*, i32 } %tmp1, 1
+  %tmp3 = tail call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %tmp2, %tmp3
+  br i1 %matches, label %catch, label %ehcleanup
+
+catch:                                            ; preds = %lpad
+  %tmp4 = extractvalue { i8*, i32 } %tmp1, 0
+  %tmp5 = tail call i8* @__cxa_begin_catch(i8* %tmp4)
+  store i64 %tmp, i64* getelementptr inbounds ([20 x i64], [20 x i64]* @a, i64 0, i64 2), align 16
+  tail call void asm sideeffect "", "~{rax},~{rbx},~{rcx},~{rdx},~{rsi},~{rdi},~{rbp},~{r8},~{r9},~{r10},~{r11},~{r12},~{r13},~{r14},~{r15},~{memory},~{dirflag},~{fpsr},~{flags}"()
+  store i64 %tmp, i64* getelementptr inbounds ([20 x i64], [20 x i64]* @a, i64 0, i64 3), align 8
+  tail call void @__cxa_end_catch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %catch, %entry
+  store i64 %tmp, i64* getelementptr inbounds ([20 x i64], [20 x i64]* @a, i64 0, i64 4), align 16
+  tail call void asm sideeffect "", "~{rax},~{rbx},~{rcx},~{rdx},~{rsi},~{rdi},~{rbp},~{r8},~{r9},~{r10},~{r11},~{r12},~{r13},~{r14},~{r15},~{memory},~{dirflag},~{fpsr},~{flags}"()
+  store i64 %tmp, i64* getelementptr inbounds ([20 x i64], [20 x i64]* @a, i64 0, i64 5), align 8
+  ret void
+
+ehcleanup:                                        ; preds = %lpad
+  resume { i8*, i32 } %tmp1
+}
+
+declare void @_Z3goov()
+
+declare i32 @__gxx_personality_v0(...)
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()