[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

Could you check that the splitting you expect occur?

[rnk]

Nice fix!

include/llvm/CodeGen/LiveInterval.h

550

This seems like it shouldn't be inline.

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

9

+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

11

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

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

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

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

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 interval contains one of the
+    // provided regmask slots.  In the presence of a regmask, spilling
+    // the interval may be required.
+    bool containsRegMask(ArrayRef<SlotIndex> RegMaskSlots) const {
+      ArrayRef<SlotIndex>::iterator SlotI = RegMaskSlots.begin();
+      ArrayRef<SlotIndex>::iterator SlotE = RegMaskSlots.end();
+      // If there are no regmask slots, we have nothing to search.
+      if (SlotI == SlotE)
+        return false;
+      // Otherwise, see if any regmask is contained by any of our segments.
+      for (const Segment &S : segments) {
+        // Find the first regmask slot at or after this segment start.
+        while (*SlotI < S.start)
+          if (++SlotI == SlotE)
+            return false;
+        // If the segment contains this slot, we have our answer.
+        if (S.contains(*SlotI))
+          return true;
+        // Otherwise, continue to the next segment.
+      }
+      return false;
+    }
+
     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

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
+  // does not contain any reg masks (which may require spilling).
+  if (li.isZeroLength(LIS.getSlotIndexes()) &&
+      !li.containsRegMask(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);
 }

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.
+
+; CHECK-NOT: LLVM ERROR
+
+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)