This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by andrew.w.kaylor on Feb 2 2016, 4:52 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

andrew.w.kaylor retitled this revision from to [regalloc][WinEH] Do not mark intervals as not spillable if they contain a regmask.
andrew.w.kaylor updated this object.
andrew.w.kaylor set the repository for this revision to rL LLVM.
andrew.w.kaylor added a subscriber: llvm-commits.

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 edited edge metadata.Feb 3 2016, 10:08 AM

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 edited edge metadata.

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

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.

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.

Moved containsRegMask implementation to the LiveInterval.cpp file.

MatzeB added inline comments.Feb 3 2016, 3:55 PM
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 added inline comments.Feb 3 2016, 4:00 PM
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 added inline comments.Feb 3 2016, 5:53 PM
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 added inline comments.Feb 3 2016, 5:58 PM
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.

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

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

MatzeB accepted this revision.Feb 8 2016, 1:23 PM
MatzeB edited edge metadata.

LGTM too

This revision is now accepted and ready to land.Feb 8 2016, 1:23 PM
This revision was automatically updated to reflect the committed changes.