[LLVMdev] Codegen/Register allocation question.

[Evan Cheng]

On Sep 3, 2008, at 5:58 AM, Lang Hames wrote:

> Hi LLVMers,
>
> I have finally sorted out licensing issues and found some time, so I'm
> trying to port my PBQP register allocator to 2.4 in order to

Nice! We would definitely welcome your contribution.

>
> contribute it (if you want it). I've run into a bug that has me
> confused though.
>
> I'm currently failing the following assertion:
>
> llc: VirtRegMap.cpp:1733:
> void<unnamed>::LocalSpiller::RewriteMBB(llvm::MachineBasicBlock&,
> llvm::VirtRegMap&): Assertion `KillRegs[0] == Dst' failed.

>
>
> when attempting to allocate this machine function:
>
> entry:
> 4       %reg1024<def,dead> = MOV32rr %EDI<kill>
> 12      %reg1025<def,dead> = MOV64rr %RSI<kill>
> 20      ADJCALLSTACKDOWN 0, %ESP<imp-def>, %EFLAGS<imp-def,dead>,  
> %ESP<imp-use>
> 28      %reg1026<def> = MOV8ri 4
> 36      %reg1027<def> = FsFLD0SD
> 44      %reg1028<def> = LEA64r %reg0, 1, %reg0, <ga:.str1>
> 52      %RDI<def> = MOV64rr %reg1028<kill>
> 60      %XMM0<def> = FsMOVAPDrr %reg1027
> 68      %XMM1<def> = FsMOVAPDrr %reg1027
> 76      %XMM2<def> = FsMOVAPDrr %reg1027
> 84      %XMM3<def> = FsMOVAPDrr %reg1027<kill>
> 92      %AL<def> = MOV8rr %reg1026<kill>
> 100     CALL64pcrel32 <ga:printf>, %RDI<kill>, %XMM0<kill>,
> %XMM1<kill>, %XMM2<kill>, %XMM3<kill>, %AL<kill>, %RAX<imp-def>,
> %RCX<imp-def,dead>, %RDX<imp-def,dead>, %RSI<imp-def,dead>,
> %RDI<imp-def,dead>, %R8<imp-def,dead>, %R9<imp-def,dead>,
> %R10<imp-def,dead>, %R11<imp-def,dead>, %FP0<imp-def,dead>,
> %FP1<imp-def,dead>, %FP2<imp-def,dead>, %FP3<imp-def,dead>,
> %FP4<imp-def,dead>, %FP5<imp-def,dead>, %FP6<imp-def,dead>,
> %ST0<imp-def,dead>, %ST1<imp-def,dead>, %MM0<imp-def,dead>,
> %MM1<imp-def,dead>, %MM2<imp-def,dead>, %MM3<imp-def,dead>,
> %MM4<imp-def,dead>, %MM5<imp-def,dead>, %MM6<imp-def,dead>,
> %MM7<imp-def,dead>, %XMM0<imp-def,dead>, %XMM1<imp-def,dead>,
> %XMM2<imp-def,dead>, %XMM3<imp-def,dead>, %XMM4<imp-def,dead>,
> %XMM5<imp-def,dead>, %XMM6<imp-def,dead>, %XMM7<imp-def,dead>,
> %XMM8<imp-def,dead>, %XMM9<imp-def,dead>, %XMM10<imp-def,dead>,
> %XMM11<imp-def,dead>, %XMM12<imp-def,dead>, %XMM13<imp-def,dead>,
> %XMM14<imp-def,dead>, %XMM15<imp-def,dead>, %EFLAGS<imp-def,dead>,
> %EAX<imp-def>, %ECX<imp-def,dead>, %EDI<imp-def,dead>,
> %EDX<imp-def,dead>, %ESI<imp-def,dead>
> 108     ADJCALLSTACKUP 0, 0, %ESP<imp-def>, %EFLAGS<imp-def,dead>,  
> %ESP<imp-use>
> 116     %reg1029<def,dead> = MOV32rr %EAX, %RAX<imp-use,kill>
> 124     %reg1030<def> = MOV32r0 %EFLAGS<imp-def,dead>
> 132     %EAX<def> = MOV32rr %reg1030<kill>
> 140     RET %EAX<imp-use,kill>, %AX<imp-use,kill>
>
>
> ********** REGISTER MAP **********
> [reg1024 -> EAX]
> [reg1025 -> R10]
> [reg1026 -> AH]
> [reg1027 -> XMM10]
> [reg1028 -> R10]
> [reg1029 -> EAX]
> [reg1030 -> EAX]
>
>
> The failure occurs when the spiller tries to eliminate the assignment
>
> 116     %reg1029<def,dead> = MOV32rr %EAX, %RAX<imp-use,kill>
>
> after reg1029 is assigned EAX. It occurs because EAX isn't listed as
> killed, so InvalidateKills doesn't return it in KillRegs (but does
> return RAX).
>
> Is this a bug (was EAX supposed to be marked killed?), or was the
> register allocator supposed to mark EAX as killed? (doesn't seem as if
> it should - it was killed before regalloc got involved).
> Or have I missed something else?

It's a bug. The assertion is too strict. I've fixed it.
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080901/066733.html

Evan

>
>
> bugpoint produced bytecode is attached, but I don't suppose it's much
> help without the allocator. That's packaged as an LLVM project at the
> moment - so if it'll help you debug I can send you a copy.
>
> Cheers,
> Lang.
>
>
>
>
> --------- Bugpoint reduced bytecode from
> SingleSource/Vector/Output/build.llvm.bc ---------
>
> ; ModuleID = 'bugpoint-reduced-simplified.bc'
> target datalayout =
> "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32- 
> f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
> target triple = "x86_64-pc-linux-gnu"
> @.str1 = external constant [13 x i8]            ; <[13 x i8]*>  
> [#uses=1]
>
> declare i32 @printf(i8* noalias, ...) nounwind
>
> define i32 @main(i32 %argc, i8** %Argv) nounwind {
> entry:
>        %tmp25.i14 = call i32 (i8*, ...)* @printf( i8* noalias
> getelementptr ([13 x i8]* @.str1, i32 0, i64 0), double 0.000000e+00,
> double 0.000000e+00, double 0.000000e+00, double 0.000000e+00 )
> nounwind           ; <i32> [#uses=0]
>        ret i32 0
> }
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev