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
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?
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
}
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 toNice! 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
On Sep 3, 2008, at 10:44 PM, Evan Cheng wrote:> 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. >We certainly do! :-) One word of advice, if you're working to get your code accepted into the mainline, you'll want to start using the SVN top-of-tree soon. We don't back port fixes to previous releases (because our release cycle is short), so you won't necessarily get Evan's fix below. Cheers! -bw>> >> 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 > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev