[ARM] Assert in register allocation during last chance recoloring

[llvmbot]

Bugzilla Link	31122
Version	trunk
OS	Linux
Attachments	Test case for register allocation
Reporter	LLVM Bugzilla Contributor
CC	@compnerd,@mikaelholmen,@qcolombet,@VerenaBeckham

Extended Description

There are two parts to this problem. Compiled using "llc -debug-only=regalloc test.ll", the attached test case fails with

VirtRegMap.h:119: void llvm::VirtRegMap::clearVirt(unsigned int): Assertion `Virt2PhysMap[virtReg] != NO_PHYS_REG && "attempt to clear a not assigned virtual register"' failed.

The code looks like:

   %vreg647<def> = COPY %vreg645; QQQQPR_with_dsub_7_then_ssub_0:%vreg647 QQQQPR:%vreg645
    %vreg657<def> = COPY %vreg655; QQQQPR_with_dsub_7_then_ssub_0:%vreg657 QQQQPR:%vreg655
    %vreg679<def> = COPY %vreg678; QPR_VFP2:%vreg679 QPR:%vreg678
    %vreg657:dsub_7_then_ssub_0<def> = VDIVS %vreg679:ssub_2, %vreg647:dsub_7_then_ssub_0, pred:14, pred:%noreg; QQQQPR_with_dsub_7_then_ssub_0:%vreg657,%vreg647 QPR_VFP2:%vreg679
    %vreg659<def> = COPY %vreg657; QQQQPR:%vreg659 QQQQPR_with_dsub_7_then_ssub_0:%vreg657

This problem occurs during last chance recoloring, where %vreg679 doesn’t get allocated (and is marked as not spillable), so last chance recoloring kicks in. It tries to allocate Q0 to %vreg679, where Q0 is assigned to %vreg647, which interferes with %vreg679. Upon trying to allocate a register to %vreg647, %vreg679 gets evicted from Q0. But %vreg679 is a fixed register, so it shouldn’t get evicted. Recoloring is thus deemed successful, and upon returning from tryRecoloringCandidates, we assert when trying to unassign %vreg679.

I can get around this by moving the virtual register under consideration in tryLastChanceRecoloring (%vreg679) to RS_Done stage right before the call to tryRecolringCandidates, and then restoring the original stage afterward. This prevents the eviction of %vreg679 during recoloring. Alternatively, I can check FixedRegisters in canEvictInterference and return false.

After this assert is gone, I run into “LLVM ERROR: ran out of registers during register allocation”.

To get past this problem, we may need to spill an actual physical register to free it up for %vreg679 if last chance recoloring fails.

[f801a291-0912-4cf9-8034-e27201f4aacc]

Was this ever fixed upstream?

[llvmbot]

Thanks, Quentin!

I got around it for now by modifying the coalescing heuristic. I need to generalize it a little more before I can upstream it. Basically, it prevents coalescing when the rewritten instruction would need more register units allocated than are available. Could be improved by checking for interfering live ranges, such as

QQQQ_restricted = S, QQQQ_restricted <=== won't get coalesced now, but could be coalesced if the two QQQQ live ranges don't interfere

As for subregister liveness tracking, I ran into some bugs when I enabled it. I'll find some time to look into them.

[qcolombet]

Quick and dirty patch Attached a quick and dirty patch. When we are in a recoloring session we disallow anything that messes up with live-ranges.

This weakens the whole last chance recoloring feature, but given the edge cases are hardly tested and not that useful, this may be a price worth to pay as it gets us simplicity.

Anyhow, I'm still investigating the other issue I had to see if I should push this patch.

[qcolombet]

Like you noticed, when the assertion is fixed the allocator will still run out of registers for your test case. Playing with TargetRegisterInfo::shouldCoalesce is indeed your best bet for this problem.

[qcolombet]

I can get around this by moving the virtual register under consideration in tryLastChanceRecoloring (%vreg679) to RS_Done stage right before the call to tryRecolringCandidates, and then restoring the original stage afterward. This prevents the eviction of %vreg679 during recoloring. Alternatively, I can check FixedRegisters in canEvictInterference and return false.

Both would work. Let me think a little bit more on the solution before deciding the way to go. In particular I believe there is a related issue and I'd like to see if any of those solution would work.

[llvmbot]

Modifying the coalescing heuristic should get this allocated (e.g. via ARMRegisterInfo::shouldCoalesce) without subregister liveness tracking.

I'll work on that fix while I do an evaluation of subregister liveness tracking on ARM. My previous comment of the original C++ file running into the same problem with subregister liveness tracking may not be true, as I was using an older build.

[llvmbot]

Enabling subregister liveness tracking for ARM gets the registers allocated, but I run into the same issues when compiling the original (unreduced) C++ file when subregister liveness tracking is enabled.

[llvmbot]

@llvm/issue-subscribers-backend-arm

[nickdesaulniers]

The provided test case has bitrot, making this too difficult to reproduce with llc-15. Please reopen with newer test case, or one not IR based.