[regalloc][WinEH] Do not mark intervals as not spillable if they contain a regmask

[andrew.w.kaylor]

Summary

Currently VirtRegAuxInfo::calculateSpillWeightAndHint() marks an interval as not spillable if no live segments in the interval span instructions. However, if the interval contains a regmask location (particularly a Windows EH unwind edge, which clobbers all registers) spilling may be required. This patch adds a check for regmasks before marking an interval as not spillable.

The included test case was reduced from a C++ program that failed to compile, reporting "LLVM ERROR: ran out of registers during register allocation." In the failing case, the greedy register allocator split an interval to the point that it contained the following two ranges: [536r,584r:0)[608B,624r:0) with a copy def at 536 (in BB#3) and a use at 624 (in BB#5). Because no live segments in the interval span instructions the interval was marked as not spillable. However, because 608B was the start of an EH pad block, there were no legal registers for the interval.

[qcolombet]

Hi Andy,

LGTM modulo I would like the test case to be a more strict on the checks.

Thanks,
-Quentin

test/CodeGen/X86/regalloc-spill-at-ehpad.ll

9 ↗

(On Diff #46722)

Could you check that the splitting you expect occur?

[rnk]

Nice fix!

include/llvm/CodeGen/LiveInterval.h

550 ↗

(On Diff #46722)

This seems like it shouldn't be inline.

test/CodeGen/X86/regalloc-spill-at-ehpad.ll

9 ↗

(On Diff #46722)

+1

[andrew.w.kaylor]

Updating the test to verify that the value used in the catch handler is reloaded.

[andrew.w.kaylor]

test/CodeGen/X86/regalloc-spill-at-ehpad.ll

10 ↗

(On Diff #46819)

I'm not sure I can verify the actual split without dumping the debug output. I could do that, I suppose, but the important thing isn't that a particular interval is split but rather than the value is spilled across the unwind edge. I don't want the test to become flaky if the interval splitting algorithm is updated.

I've added a check to verify that the value is reloaded in the catch handler.

[andrew.w.kaylor]

include/llvm/CodeGen/LiveInterval.h

550 ↗

(On Diff #46819)

Sorry. I missed this comment before uploading changes. I can move this to the implementation file.

[andrew.w.kaylor]

Moved containsRegMask implementation to the LiveInterval.cpp file.

[MatzeB]

include/llvm/CodeGen/LiveInterval.h

550 ↗

(On Diff #46844)

I'd rather call this function something like liveAtIndexes() and also talk about indexes instead of regmasks in the comment. The comments in the header and implementation should just talk about SlotIndexes. The details about regmasks and spilling can be mentioned where this function is used.

[MatzeB]

lib/CodeGen/LiveInterval.cpp

757–762 ↗

(On Diff #46844)

This does not need to be a quadratic algorithm as the regmaskslots and segments are both sorted!

I'd initialize an iterator with segments.begin(), loop over the RegMaskSlots and use advanceTo() to check each index.

[andrew.w.kaylor]

include/llvm/CodeGen/LiveInterval.h

550 ↗

(On Diff #46844)

OK. I'll make that change.

lib/CodeGen/LiveInterval.cpp

757–762 ↗

(On Diff #46844)

I don't think this is quadratic the way I've implemented it. The inner while loop just advances the slot iterator from wherever it was (at the start of the current for loop iteration) to the first slot that is at or after the start of the current segment. This will never visit any slot from RegMaskSlots or any segment more than once.

I think that what you are suggesting would accomplish the same thing, just switching the hierarchy of the two loops and using advanceTo in place of the inner loop. I'm happy to do it that way if you think it reads better. I admit that the way I have written this code it does look quadratic.

[MatzeB]

lib/CodeGen/LiveInterval.cpp

757–762 ↗

(On Diff #46844)

You are right your code is not quadratic. It would still be nice to rewrite it using advanceTo() maybe also using find(RegMaskSlots.front()) to initialize the iterator as that uses a binary search algorithm.

[andrew.w.kaylor]

Renamed containsRegMask() to isLiveAtIndexes() and revised the implementation as suggested.

[andrew.w.kaylor]

Is there anything else you'd like to see changed in this or is it OK to commit now?

[MatzeB]

LGTM too

llvm/trunk/include/llvm/CodeGen/LiveInterval.h

public:
     bool isZeroLength(SlotIndexes *Indexes) const {
       for (const Segment &S : segments)
         if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
             S.end.getBaseIndex())
           return false;
       return true;
     }
 
+    // Returns true if any segment in the live range contains any of the
+    // provided slot indexes.  Slots which occur in holes between
+    // segments will not cause the function to return true.
+    bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
+
     bool operator<(const LiveRange& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return thisIndex < otherIndex;
     }
 
     /// Flush segment set into the regular segment vector.
     /// The method is to be called after the live range

llvm/trunk/lib/CodeGen/CalcSpillWeights.cpp

if (unsigned hint = hintPhys ? hintPhys : hintVirt) {
     // Weakly boost the spill weight of hinted registers.
     totalWeight *= 1.01F;
   }
 
   // If the live interval was already unspillable, leave it that way.
   if (!Spillable)
     return;
 
-  // Mark li as unspillable if all live ranges are tiny.
-  if (li.isZeroLength(LIS.getSlotIndexes())) {
+  // Mark li as unspillable if all live ranges are tiny and the interval
+  // is not live at any reg mask.  If the interval is live at a reg mask
+  // spilling may be required.
+  if (li.isZeroLength(LIS.getSlotIndexes()) &&
+      !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
     li.markNotSpillable();
     return;
   }
 
   // If all of the definitions of the interval are re-materializable,
   // it is a preferred candidate for spilling.
   // FIXME: this gets much more complicated once we support non-trivial
   // re-materialization.
   if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
     totalWeight *= 0.5F;
 
   li.weight = normalize(totalWeight, li.getSize(), numInstr);
 }

llvm/trunk/lib/CodeGen/LiveInterval.cpp

void LiveRange::flushSegmentSet() {
   assert(
       segments.empty() &&
       "segment set can be used only initially before switching to the array");
   segments.append(segmentSet->begin(), segmentSet->end());
   segmentSet = nullptr;
   verify();
 }
 
+bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const {
+  ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
+  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
+
+  // If there are no regmask slots, we have nothing to search.
+  if (SlotI == SlotE)
+    return false;
+
+  // Start our search at the first segment that ends after the first slot.
+  const_iterator SegmentI = find(*SlotI);
+  const_iterator SegmentE = end();
+
+  // If there are no segments that end after the first slot, we're done.
+  if (SegmentI == SegmentE)
+    return false;
+
+  // Look for each slot in the live range.
+  for ( ; SlotI != SlotE; ++SlotI) {
+    // Go to the next segment that ends after the current slot.
+    // The slot may be within a hole in the range.
+    SegmentI = advanceTo(SegmentI, *SlotI);
+    if (SegmentI == SegmentE)
+      return false;
+
+    // If this segment contains the slot, we're done.
+    if (SegmentI->contains(*SlotI))
+      return true;
+    // Otherwise, look for the next slot.
+  }
+
+  // We didn't find a segment containing any of the slots.
+  return false;
+}
+
 void LiveInterval::freeSubRange(SubRange *S) {
   S->~SubRange();
   // Memory was allocated with BumpPtr allocator and is not freed here.
 }
 
 void LiveInterval::removeEmptySubRanges() {
   SubRange **NextPtr = &SubRanges;
   SubRange *I = *NextPtr;

llvm/trunk/test/CodeGen/X86/regalloc-spill-at-ehpad.ll

+; RUN: llc -regalloc=greedy -mtriple=x86_64-pc-windows-msvc  < %s -o - | FileCheck %s
+
+; This test checks for proper handling of a condition where the greedy register
+; allocator encounters a very short interval that contains no uses but does
+; contain an EH pad unwind edge, which requires spilling.  Previously the
+; register allocator marked a interval like this as unspillable, resulting in
+; a compilation failure.
+
+
+; The following checks that the value %p is reloaded within the catch handler.
+; CHECK-LABEL: "?catch$8@?0?test@4HA":
+; CHECK:           .seh_endprologue
+; CHECK:           movq    -16(%rbp), %rax
+; CHECK:           movb    $0, (%rax)
+
+define i32* @test(i32* %a) personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  %call = call i32 @f()
+  %p = bitcast i32* %a to i8*
+  br i1 undef, label %if.end, label %if.else
+
+if.else:                                          ; preds = %entry
+  br i1 undef, label %cond.false.i, label %if.else.else
+
+if.else.else:                                     ; preds = %if.else
+  br i1 undef, label %cond.true.i, label %cond.false.i
+
+cond.true.i:                                      ; preds = %if.else.else
+  br label %invoke.cont
+
+cond.false.i:                                     ; preds = %if.else.else, %if.else
+  %call.i = invoke i32 @f()
+          to label %invoke.cont unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %cond.false.i
+  %tmp0 = catchswitch within none [label %catch] unwind label %ehcleanup
+
+catch:                                            ; preds = %catch.dispatch
+  %tmp1 = catchpad within %tmp0 [i8* null, i32 64, i8* null]
+  %p.0 = getelementptr inbounds i8, i8* %p, i64 0
+  store i8 0, i8* %p.0, align 8
+  invoke void @_CxxThrowException(i8* null, %eh.ThrowInfo* null) [ "funclet"(token %tmp1) ]
+          to label %noexc unwind label %ehcleanup
+
+noexc:                                            ; preds = %catch
+  unreachable
+
+invoke.cont:                                      ; preds = %cond.false.i, %cond.true.i
+  %cond.i = phi i32 [ %call, %cond.true.i ], [ %call.i, %cond.false.i ]
+  %cmp = icmp eq i32 %cond.i, -1
+  %tmp3 = select i1 %cmp, i32 4, i32 0
+  br label %if.end
+
+if.end:                                           ; preds = %invoke.cont, %entry
+  %state.0 = phi i32 [ %tmp3, %invoke.cont ], [ 4, %entry ]
+  %p.1 = getelementptr inbounds i8, i8* %p, i64 0
+  invoke void @g(i8* %p.1, i32 %state.0)
+          to label %invoke.cont.1 unwind label %ehcleanup
+
+invoke.cont.1:                                    ; preds = %if.end
+  ret i32* %a
+
+ehcleanup:                                        ; preds = %if.end, %catch, %catch.dispatch
+  %tmp4 = cleanuppad within none []
+  cleanupret from %tmp4 unwind to caller
+}
+
+%eh.ThrowInfo = type { i32, i32, i32, i32 }
+
+declare i32 @__CxxFrameHandler3(...)
+
+declare void @_CxxThrowException(i8*, %eh.ThrowInfo*)
+
+declare i32 @f()
+declare void @g(i8*, i32)