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

1397

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

1397

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

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

1397

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

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

1397

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

lib/CodeGen/SplitKit.h

124–126

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

124–127

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.

[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

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

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

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

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

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)

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;
 
+  // Used to find out LastSplitPoint of BB.
+  std::unique_ptr<SplitAnalysis> SA;
+
   // 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;

 }
 
 /// 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 = SA->getLastSplitPointIter(&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");
 

 /// where we consider to hoist the spills. We iterate the WorkSet in bottom-up
 /// order, and for each node, we will decide whether to hoist spills inside
 /// its subtree to that node. In this way, we can get benefit locally even if
 /// hoisting all the equal spills to one cold place is impossible.
 ///
 void HoistSpillHelper::hoistAllSpills() {
   SmallVector<unsigned, 4> NewVRegs;
   LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
+  SA.reset(new SplitAnalysis(VRM, LIS, Loops));
 
   // Save the mapping between stackslot and its original reg.
   DenseMap<int, unsigned> SlotToOrigReg;
   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
     int Slot = VRM.getStackSlot(Reg);
     if (Slot != VirtRegMap::NO_STACK_SLOT)
       SlotToOrigReg[Slot] = VRM.getOriginal(Reg);
for (auto &Ent : MergeableSpills) {
     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";
     });
 
+    LiveInterval &OrigLI = LIS.getInterval(OrigReg);
+    // Skip analyzeUses because SA is only used to get LastSplitPoint of BB.
+    SA->analyze(&OrigLI, true);
+
     // 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 = SA->getLastSplitPointIter(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();

lib/CodeGen/SplitKit.h

private:
 
   /// calcLiveBlockInfo - Compute per-block information about CurLI.
   bool calcLiveBlockInfo();
 
 public:
   SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
                 const MachineLoopInfo &mli);
 
   /// analyze - set CurLI to the specified interval, and analyze how it may be
-  /// split.
-  void analyze(const LiveInterval *li);
+  /// split. If SkipAnalyze is true, skip the analyzeUses call.
+  void analyze(const LiveInterval *li, bool SkipAnalyze = false);
 
   /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
   /// by analyze(). This really shouldn't happen, but sometimes the coalescer
   /// can create live ranges that end in mid-air.
   bool didRepairRange() const { return DidRepairRange; }
 
   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
   /// new interval.
   void clear();

lib/CodeGen/SplitKit.cpp

bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
   // Range containing Idx should begin at Idx.
   if (I != Orig.end() && I->start <= Idx)
     return I->start == Idx;
 
   // Range does not contain Idx, previous must end at Idx.
   return I != Orig.begin() && (--I)->end == Idx;
 }
 
-void SplitAnalysis::analyze(const LiveInterval *li) {
+void SplitAnalysis::analyze(const LiveInterval *li, bool SkipAnalyze) {
   clear();
   CurLI = li;
+  if (!SkipAnalyze)
     analyzeUses();
 }
 
 
 //===----------------------------------------------------------------------===//
 //                               Split Editor
 //===----------------------------------------------------------------------===//
 
 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.

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: _Z5CheckIZ4mainE3$_0EvT_:
+; CHECK: movq %r14, 16(%rbx)          # 8-byte Spill
+; CHECK-NEXT: callq _ZlsIiEv1CIT_Ej
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%class.basic_stringstream.2.110 = type { i8 }
+%class.F.3.111 = type { i8 }
+%class.A.1.109 = type { %class.allocator.0.108 }
+%class.allocator.0.108 = type { i8 }
+
+@_ZTIi = external constant i8*
[e-mail]_ctors = external global [1 x { i32, void ()*, i8* }]
+@__asan_option_detect_stack_use_after_return = external global i32
+@__asan_gen_ = external unnamed_addr constant [36 x i8], align 1
+@__asan_gen_.1 = external unnamed_addr constant [17 x i8], align 1
+@__asan_gen_.2 = external unnamed_addr constant [17 x i8], align 1
+
+declare i32 @main()
+
+define internal fastcc void @"_Z5CheckIZ4mainE3$_0EvT_"() unnamed_addr personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  br i1 undef, label %bb, label %bb1
+
+bb:                                               ; preds = %entry
+  %tmp = call i64 @__asan_stack_malloc_1(i64 96)
+  br label %bb1
+
+bb1:                                              ; preds = %bb, %entry
+  %tmp2 = phi i64 [ 0, %entry ], [ %tmp, %bb ]
+  br i1 undef, label %bb3, label %bb4
+
+bb3:                                              ; preds = %bb1
+  %MyAlloca = alloca i8, i64 96, align 32
+  br label %bb4
+
+bb4:                                              ; preds = %bb3, %bb1
+  %tmp5 = phi i64 [ %tmp2, %bb1 ], [ 0, %bb3 ]
+  %tmp6 = add i64 %tmp5, 32
+  %tmp7 = inttoptr i64 %tmp6 to %class.basic_stringstream.2.110*
+  %tmp8 = add i64 %tmp5, 48
+  %tmp9 = inttoptr i64 %tmp8 to %class.F.3.111*
+  %tmp10 = add i64 %tmp5, 64
+  %tmp11 = inttoptr i64 %tmp10 to %class.A.1.109*
+  %tmp12 = lshr i64 %tmp5, 3
+  %tmp13 = add i64 %tmp12, 2147450880
+  %tmp14 = add i64 %tmp13, 0
+  %tmp15 = inttoptr i64 %tmp14 to i64*
+  store i64 -1008258751386226191, i64* %tmp15
+  invoke void @_ZlsIiEv1CIT_Ej(i32 0)
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:                                      ; preds = %bb4
+  invoke void @_ZN18basic_stringstream5m_fn1Ev(%class.A.1.109* nonnull sret %tmp11, %class.basic_stringstream.2.110* nonnull %tmp7)
+          to label %invoke.cont2 unwind label %lpad
+
+invoke.cont2:                                     ; preds = %invoke.cont
+  invoke void @_ZN1FC2E1A(%class.F.3.111* nonnull %tmp9, %class.A.1.109* nonnull %tmp11)
+          to label %try.cont unwind label %lpad3
+
+lpad:                                             ; preds = %invoke.cont, %bb4
+  %tmp16 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp17 = extractvalue { i8*, i32 } %tmp16, 0
+  br label %ehcleanup
+
+lpad3:                                            ; preds = %invoke.cont2
+  %tmp18 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp19 = extractvalue { i8*, i32 } %tmp18, 1
+  br label %ehcleanup
+
+ehcleanup:                                        ; preds = %lpad3, %lpad
+  %ehselector.slot.0 = phi i32 [ %tmp19, %lpad3 ], [ undef, %lpad ]
+  %exn.slot.0 = phi i8* [ undef, %lpad3 ], [ %tmp17, %lpad ]
+  call void @_ZN18basic_stringstreamD1Ev(%class.basic_stringstream.2.110* nonnull %tmp7)
+  %matches = icmp eq i32 %ehselector.slot.0, undef
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %ehcleanup
+  %tmp20 = call i8* @__cxa_begin_catch(i8* %exn.slot.0)
+  br label %try.cont
+
+try.cont:                                         ; preds = %catch, %invoke.cont2
+  %tmp21 = icmp ne i64 %tmp2, 0
+  br i1 %tmp21, label %bb22, label %bb25
+
+bb22:                                             ; preds = %try.cont
+  %tmp23 = add i64 %tmp13, 8
+  %tmp24 = inttoptr i64 %tmp23 to i64*
+  store i64 -723401728380766731, i64* %tmp24
+  br label %bb25
+
+bb25:                                             ; preds = %bb22, %try.cont
+  ret void
+
+eh.resume:                                        ; preds = %ehcleanup
+  resume { i8*, i32 } undef
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+
+declare void @_ZlsIiEv1CIT_Ej(i32)
+
+declare i32 @__gxx_personality_v0(...)
+
+declare void @_ZN18basic_stringstream5m_fn1Ev(%class.A.1.109* sret, %class.basic_stringstream.2.110*)
+
+declare void @_ZN1FC2E1A(%class.F.3.111*, %class.A.1.109* nocapture readnone) unnamed_addr align 2
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+declare void @_ZN18basic_stringstreamD1Ev(%class.basic_stringstream.2.110*) unnamed_addr
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()
+
+declare i64 @__asan_stack_malloc_1(i64)