LLVM greedy register allocator does not know how to split live variables across register classes

[shepmaster]

(See below for a further minimized example)

Error message

LLVM ERROR: ran out of registers during register allocation

So from my testing, it seams like the allocator reserves the Z register for the ICALL instruction and then the register class ptrdispregs only has 1 register left and we can't use Y for source and destination.

• @brainlag

Reproduction

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "bugpoint-output-650d16e.bc"
target datalayout = "e-p:16:16:16-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-n8"
target triple = "avr"

%FmtFormatter.5.12.19.26.33.40.54.68.75.82.89.192 = type { i32, [0 x i8], i32, [0 x i8], %"Option<usize>.0.7.14.21.28.35.49.63.70.77.84.187", [0 x i8], %"Option<usize>.0.7.14.21.28.35.49.63.70.77.84.187", [0 x i8], { i8*, void (i8*)** }, [0 x i8], %"Iter<fmt::ArgumentV1>.4.11.18.25.32.39.53.67.74.81.88.191", [0 x i8], { %ArgumentV1.2.9.16.23.30.37.51.65.72.79.86.189*, i16 }, [0 x i8], i8, [3 x i8] }
%"Option<usize>.0.7.14.21.28.35.49.63.70.77.84.187" = type { i16, [0 x i16], [1 x i16] }
%"Iter<fmt::ArgumentV1>.4.11.18.25.32.39.53.67.74.81.88.191" = type { %ArgumentV1.2.9.16.23.30.37.51.65.72.79.86.189*, [0 x i8], %ArgumentV1.2.9.16.23.30.37.51.65.72.79.86.189*, [0 x i8], %"PhantomData<&fmt::ArgumentV1>.3.10.17.24.31.38.52.66.73.80.87.190", [0 x i8] }
%ArgumentV1.2.9.16.23.30.37.51.65.72.79.86.189 = type { %Void.1.8.15.22.29.36.50.64.71.78.85.188*, [0 x i8], i8 (%Void.1.8.15.22.29.36.50.64.71.78.85.188*, %FmtFormatter.5.12.19.26.33.40.54.68.75.82.89.192*)*, [0 x i8] }
%Void.1.8.15.22.29.36.50.64.71.78.85.188 = type { {}, [0 x i8] }
%"PhantomData<&fmt::ArgumentV1>.3.10.17.24.31.38.52.66.73.80.87.190" = type {}
%EscapeUnicode.6.13.20.27.34.41.55.69.76.83.90.193 = type { i32, [0 x i8], i16, [0 x i8], i8, [1 x i8] }

@str.2y = external constant [7 x i8]

; Function Attrs: uwtable
define void @EscapeDefaultStateDebug(%FmtFormatter.5.12.19.26.33.40.54.68.75.82.89.192* dereferenceable(32)) unnamed_addr #0 personality i32 (...)* @rust_eh_personality {
start:
  %_47 = alloca %EscapeUnicode.6.13.20.27.34.41.55.69.76.83.90.193*, align 2
  switch i2 undef, label %bb4 [
    i2 0, label %_ZN4core3fmt8builders10DebugTuple6finish17h8f1e007edfc4d0a6E.exit
  ]

_ZN4core3fmt8builders10DebugTuple6finish17h8f1e007edfc4d0a6E.exit: ; preds = %start
  ret void

bb4:                                              ; preds = %start
  %1 = getelementptr inbounds %FmtFormatter.5.12.19.26.33.40.54.68.75.82.89.192, %FmtFormatter.5.12.19.26.33.40.54.68.75.82.89.192* %0, i16 0, i32 8, i32 1
  %2 = load void (i8*)**, void (i8*)*** %1, align 2, !noalias !0, !nonnull !9
  %3 = getelementptr inbounds void (i8*)*, void (i8*)** %2, i16 3
  %4 = bitcast void (i8*)** %3 to i8 ({}*, i8*, i16)**
  %5 = load i8 ({}*, i8*, i16)*, i8 ({}*, i8*, i16)** %4, align 2, !invariant.load !9, !noalias !0, !nonnull !9
  %6 = tail call i8 %5({}* nonnull undef, i8* noalias nonnull readonly getelementptr inbounds ([7 x i8], [7 x i8]* @str.2y, i16 0, i16 0), i16 7), !noalias !10
  unreachable
}

declare i32 @rust_eh_personality(...) unnamed_addr

attributes #0 = { uwtable }

!0 = !{!1, !3, !5, !6, !8}
!1 = distinct !{!1, !2, !"_ZN4core3fmt9Formatter9write_str17hf8083fd39f1b0c0cE: argument 0"}
!2 = distinct !{!2, !"_ZN4core3fmt9Formatter9write_str17hf8083fd39f1b0c0cE"}
!3 = distinct !{!3, !4, !"_ZN4core3fmt8builders15debug_tuple_new17ha94131b12062f03fE: argument 0"}
!4 = distinct !{!4, !"_ZN4core3fmt8builders15debug_tuple_new17ha94131b12062f03fE"}
!5 = distinct !{!5, !4, !"_ZN4core3fmt8builders15debug_tuple_new17ha94131b12062f03fE: argument 1"}
!6 = distinct !{!6, !7, !"_ZN4core3fmt9Formatter11debug_tuple17hadc8e3bda8cfb00cE: argument 0"}
!7 = distinct !{!7, !"_ZN4core3fmt9Formatter11debug_tuple17hadc8e3bda8cfb00cE"}
!8 = distinct !{!8, !7, !"_ZN4core3fmt9Formatter11debug_tuple17hadc8e3bda8cfb00cE: argument 1"}
!9 = !{}
!10 = !{!3, !6}

I'm not actually sure if Rust or LLVM should be handling this...

[shepmaster]

The debug log from llc

[shepmaster]

And the machine code when we are doing register allocation

# Machine code for function EscapeDefaultStateDebug: NoPHIs, TracksLiveness
Frame Objects:
  fi#0: size=2, align=2, at location [SP+2]
Function Live Ins: %R25R24 in %vreg0

BB#0: derived from LLVM BB %start
    Live Ins: %R25R24
	%vreg11<def> = COPY %R25R24; DREGS:%vreg11
	%vreg1<def> = LDIRdK 0; LD8:%vreg1
	CPIRdK %vreg1, 0, %SREG<imp-def>, %SREG<imp-use,kill>; LD8:%vreg1
	BRNEk <BB#2>, %SREG<imp-use,kill>
	RJMPk <BB#1>
    Successors according to CFG: BB#1(0x7ffff800 / 0x80000000 = 100.00%) BB#2(0x00000800 / 0x80000000 = 0.00%)

BB#1: derived from LLVM BB %_ZN4core3fmt8builders10DebugTuple6finish17h8f1e007edfc4d0a6E.exit
    Predecessors according to CFG: BB#0
	RET

BB#2: derived from LLVM BB %bb4
    Predecessors according to CFG: BB#0
	%vreg13<def> = COPY %vreg11; DREGS:%vreg13,%vreg11
	%vreg14<def> = COPY %vreg13; PTRDISPREGS:%vreg14 DREGS:%vreg13
	%vreg5<earlyclobber,def> = LDDWRdPtrQ %vreg14, 18; mem:LD2[%2](noalias=!1,!3,!5,!6,!8)(dereferenceable) PTRDISPREGS:%vreg5,%vreg14
	%vreg4<earlyclobber,def> = LDDWRdPtrQ %vreg5, 6; mem:LD2[%5](noalias=!1,!3,!5,!6,!8)(invariant) DREGS:%vreg4 PTRDISPREGS:%vreg5
	ADJCALLSTACKDOWN 0, %SP<imp-def,dead>, %SREG<imp-def,dead>, %SP<imp-use>
	%vreg6<def> = LDIWRdK <ga:@str.2y>; DLDREGS:%vreg6
	%vreg7<def> = LDIWRdK 7; DLDREGS:%vreg7
	%R23R22<def> = COPY %vreg6; DLDREGS:%vreg6
	%R21R20<def> = COPY %vreg7; DLDREGS:%vreg7
	%R31R30<def> = COPY %vreg4; DREGS:%vreg4
	ICALL %R31R30, %R25R24<undef>, %R23R22, %R21R20, <regmask %R2 %R3 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %R12 %R13 %R14 %R15 %R16 %R17 %R28 %R29 %R3R2 %R5R4 %R7R6 %R9R8 %R11R10 %R13R12 %R15R14 %R17R16 %R29R28>, %SP<imp-use>, %R31R30<imp-use>, %SP<imp-def>, %R24<imp-def,dead>
	ADJCALLSTACKUP 0, 0, %SP<imp-def,dead>, %SREG<imp-def,dead>, %SP<imp-use>

# End machine code for function EscapeDefaultStateDebug.

[dylanmckay]

This is almost certainly related to avr-llvm/llvm#1. The bug was really hard to fix (I had to figure out how the greedy register allocator worked and make a change to it so that it would attempt to split unspillable live ranges.

I'm surprised to see this again. Hopefully it's easier to solve this time lol

[shepmaster]

One thing I notice but don't know if it's important: When selectOrSplit PTRDISPREGS is called at the end of the debug log, it doesn't pick R29R28, only R31R30. That seems like it would artifically increase the contention of registers.

[dylanmckay]

That may be because R29R28 is the frame pointer register, which is enabled for functions in a few cases including if there was a stack spill.

[shepmaster]

One thing I haven't been able to figure out yet: why would something be unspillable? With 32 registers, it seems like it should be conceptually pretty hard to actually run out...

[dylanmckay]

There may be 32 general purpose registers, but all of the IO instructions only support using pointers from the X, Y, and Z registers. If a function has at least one stack spill, the Y register becomes the frame pointer, and that means we can only have two pointers in registers at a time in some cases. Pointer-heavy code will quite quickly require a lot of spilling and loading of registers.

…

On 30/04/2017 11:55 am, "Jake Goulding" ***@***.***> wrote: One thing I haven't been able to figure out yet: *why* would something be unspillable? With 32 registers, it seems like it should be conceptually pretty hard to actually run out... — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#37 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHXUr86nYMMyPanp69dZtBkX1Z76i5a2ks5r084MgaJpZM4NLe-4> .

[shepmaster]

only support using pointers from the X, Y, and Z registers.

only have two pointers in registers at a time in some cases.

But in this case, it looks like we are using PTRDISPREGS which only has 2 registers, Y and Z. If Y is taken up, then we only have Z, which fits with the output. Is using this register class, instead of PTRREGS suspicious at all?

[dylanmckay]

Is using this register class, instead of PTRREGS suspicious at all?

Nah, it looks like it's PTRDISPREGS because the instruction is lddw, which (I can't remember why) but it only supports a small set of registers, named PTRDISPREGS because they can only be used in thie displacement instructions.

[shepmaster]

I've been trying to comment out parts of libcore to get to the next error, but it feels like this is occurring for every implementation of core::fmt::Debug, of which there are a lot... probably means it's an important issue.

[dylanmckay]

I've got an unfinished patch locally for #38 which may reduce the number of these (reserve the frame pointer in less cases).

[shepmaster]

The alloca definitely plays a part - the resulting value is never used when it fails, but removing that line cause the compilation to succeed. Some quick searching seems to indicate that a frame pointer is often used when alloca is.

[shepmaster]

I'm continuing to try to drive down the example size. This is what I have now:

source_filename = "bugpoint-output-87a64d6.bc"
target datalayout = "e-p:16:16:16-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-n8"
target triple = "avr"

%"fmt::Formatter" = type { i32, { i8*, void (i8*)** } }

@str.1b = external constant [0 x i8]

define void @"TryFromIntError::Debug"(%"fmt::Formatter"* dereferenceable(32)) unnamed_addr #0 personality i32 (...)* @rust_eh_personality {
start:
  %builder = alloca i8, align 8
  %1 = getelementptr inbounds %"fmt::Formatter", %"fmt::Formatter"* %0, i16 0, i32 1
  %2 = bitcast { i8*, void (i8*)** }* %1 to {}**
  %3 = load {}*, {}** %2, align 2
  %4 = getelementptr inbounds %"fmt::Formatter", %"fmt::Formatter"* %0, i16 0, i32 1, i32 1
  %5 = load void (i8*)**, void (i8*)*** %4, align 2
  %6 = getelementptr inbounds void (i8*)*, void (i8*)** %5, i16 3
  %7 = bitcast void (i8*)** %6 to i8 ({}*, i8*, i16)**
  %8 = load i8 ({}*, i8*, i16)*, i8 ({}*, i8*, i16)** %7, align 2
  %9 = tail call i8 %8({}* nonnull %3, i8* noalias nonnull readonly getelementptr inbounds ([0 x i8], [0 x i8]* @str.1b, i16 0, i16 0), i16 15)
  unreachable
}

declare i32 @rust_eh_personality(...) unnamed_addr

attributes #0 = { uwtable }

Things I've noticed:

• Removing alloca - compiles. My guess is that alloca is triggering the frame pointer, reducing available registers.
• Removing the first member of Formatter - compiles. My guess is that this allows us to use the non-displacement instructions.