Invalid register allocation

[asl]

Bugzilla Link	2465
Resolution	FIXED
Resolved on	Nov 07, 2018 00:17
Version	trunk
OS	Linux
Attachments	Bytecode in questions
CC	@efriedma-quic

Extended Description

Consider the attached .ll file (sorry, I wasn't be able to reduce it).

in bb27.i.i74 we're seeing:

bb27.i.i74: ; preds = %bb14.i.i
%tmp30.i.i69 = getelementptr i8* %tmp1097, i32 %x_addr.0.i.i ; <i8*> [#uses=1]
%tmp31.i.i70 = load i8* %tmp30.i.i69, align 1 ; [#uses=2]
%tmp34.i.i71 = getelementptr i8* %tmp1094, i32 %y.0.i.i ; <i8*> [#uses=1]
%tmp35.i.i72 = load i8* %tmp34.i.i71, align 1 ; [#uses=1]
%tmp36.i.i73 = icmp eq i8 %tmp31.i.i70, %tmp35.i.i72 ; [#uses=1]
zext i8 %tmp31.i.i70 to i32 ; :1418 [#uses=2]
%tmp1.i2918 = and i32 %1418, 1 ; [#uses=1]
%tmp2.i2919 = xor i32 %tmp1.i2918, 1 ; [#uses=1]
%tmp4.i2920 = sub i32 0, %1418 ; [#uses=1]
%tmp.i2921 = icmp ne i32 %tmp2.i2919, %tmp4.i2920 ; [#uses=1]
and i1 %tmp36.i.i73, %tmp.i2921 ; :1419 [#uses=1]
br i1 %1419, label %bb9.i.i, label %snake.exit.i

so, two GEPs plus some innocent bit plays.

These are codegen'ed into:

LBB5_811: # bb27.i.i74
movl 208(%esp), %ecx
movb (%ecx,%ebp), %al
movzbl %al, %ecx
movl %ecx, %edx
andl $1, %edx
negl %ecx
xorl $1, %edx
movl 204(%esp), %ebx
cmpb (%ebx,%ecx), %al
jne LBB5_813 # bb14.i.i.snake.exit.i_crit_edge

Note, that
%tmp35.i.i72 = load i8* %tmp34.i.i71, align 1 ; [#uses=1]
%tmp36.i.i73 = icmp eq i8 %tmp31.i.i70, %tmp35.i.i72 ;

is turned into

    movl    204(%esp), %ebx
    cmpb    (%ebx,%ecx), %al

which is definitely incorrect, since %ecx was already clobbered by computations.

If I run opt -std-compile-opts before, result is pretty sane:

LBB5_744: # bb27.i.i74
movl 208(%esp), %esi
movb (%esi,%edx), %bl
movzbl %bl, %esi
movl %esi, %ebp
negl %ebp
andl $1, %esi
xorl $1, %esi
cmpl %ebp, %esi
movl 204(%esp), %esi
movb (%esi,%eax), %bh
je LBB5_746 # bb14.i.i.snake.exit.i_crit_edge

here %eax and %edx are liveins from prev BBs, where GEP indices were calculated.

[efriedma-quic]

Would you mind posting C code as well? The bytecode as posted will only work on Windows.

[asl]

Would you mind posting C code as well? The bytecode as posted will only work
on Windows.

Yes, I know. There is no C code, unfortunately. Bytecode in question was produced by some LLVM IR-to-IR transformation.

[llvmbot]

This looks like a coalescing bug:

before -
44580 %reg1834 = MOV32rr %reg5798
44584 JGE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>
bb14.i.i:
44588 CMP32rr %reg5797, %reg5798, %EFLAGS
44592 JE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>
bb14.i.i:
44596 TEST8ri %reg5799, 1, %EFLAGS
44600 JNE mbb<bb27.i.i74,0x15093b0>, %EFLAGS<imp-use,kill>
bb14.i.i.snake.exit.i_crit_edge:
44604 %reg6383 = MOV32rr %reg1833
44608 JMP mbb<snake.exit.i,0x1509450>
bb27.i.i74:
44612 %reg5810 = MOV8rm %reg1755, 1, %reg1833, 0, Mem:LD(1,1) [tmp30.i.i69 + 0]
44616 %reg5811 = MOVZX32rr8 %reg5810
44620 %reg5812 = MOV32rr %reg5811
44624 %reg5812 = AND32ri8 %reg5812, 1, %EFLAGS<imp-def,dead>
44628 %reg5809 = MOV32rr %reg5811
44632 %reg5809 = NEG32r %reg5809, %EFLAGS<imp-def,dead>
44636 %reg5808 = MOV32rr %reg5812
44640 %reg5808 = XOR32ri8 %reg5808, 1, %EFLAGS<imp-def,dead>
44644 CMP8rm %reg5810, %reg1754, 1, %reg1834, 0, %EFLAGS, Mem:LD(1,1) [tmp34.i.i71 + 0]
44648 JNE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>

LiveInterval of r1834 looks right.
%reg1834,0 = [44420,44474:0)[44582,44595:0)[44596,44603:0)[44612,44651:0)[44652,44663:0) 0@44582-(44474)

after -
44576 CMP32rr %reg6377, %reg1781, %EFLAGS
44584 JGE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>
bb14.i.i:
44588 CMP32rr %reg5797, %reg6377, %EFLAGS
44592 JE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>
bb14.i.i:
44596 TEST8ri %reg5799, 1, %EFLAGS
44600 JNE mbb<bb27.i.i74,0x15093b0>, %EFLAGS<imp-use,kill>
bb14.i.i.snake.exit.i_crit_edge:
44604 %reg6377 = MOV32rr %reg1833
44608 JMP mbb<snake.exit.i,0x1509450>
bb27.i.i74:
44612 %reg5810 = MOV8rm %reg1755, 1, %reg1833, 0, Mem:LD(1,1) [tmp30.i.i69 + 0]
44616 %reg5809 = MOVZX32rr8 %reg5810
44620 %reg5808 = MOV32rr %reg5809
44624 %reg5808 = AND32ri8 %reg5808, 1, %EFLAGS<imp-def,dead>
44632 %reg5809 = NEG32r %reg5809, %EFLAGS<imp-def,dead>
44640 %reg5808 = XOR32ri8 %reg5808, 1, %EFLAGS<imp-def,dead>
44644 CMP8rm %reg5810, %reg1754, 1, %reg6377, 0, %EFLAGS, Mem:LD(1,1) [tmp34.i.i71 + 0]
44648 JNE mbb<bb14.i.i.snake.exit.i_crit_edge,0x1509310>, %EFLAGS<imp-use,kill>

LiveInterval of r6377 -
%reg6377,1375.46 = [43906,43930:7)[43930,44008:4)[44050,44060:8)[44134,44142:12)[44142,44191:9)[44192,44200:9)[44214,44230:13)[44230,44291:10)[44292,44299:10)[44300,44308:10)[44310,44312:11)
[44312,44392:5)[44392,44420:2)[44480,44562:1)[44562,44595:3)[44606,44612:6)[44664,44702:0) 0@?-(44702) 1@?-(44562) 2@?-(phi) 3@44562-(phi) 4@43930-(phi) 5@?-(44384 44392 phi) 6@44606-(44612
phi) 7@43906-(43930) 8@44050-(phi) 9@44142-(44200 phi) 10@44230-(44308 phi) 11@44310-(44312 phi) 12@44134-(44142) 13@44214-(44230)

Notice val#3 is defined on 44562. It's live range ended at 44595. It's missing from 44612 - 44646.

[llvmbot]

Fixed. Now the BB looks like this:

LBB5_811: # bb27.i.i74
movl 208(%esp), %ecx
movb (%ecx,%ebp), %al
movzbl %al, %ecx
movl %ecx, %edx
andl $1, %edx
negl %ecx
xorl $1, %edx
movl 204(%esp), %ebx
cmpb (%ebx,%ecx), %al
jne LBB5_813 # bb14.i.i.snake.exit.i_crit_edge

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080616/063792.html

[asl]

Fixed. Now the BB looks like this:

LBB5_811: # bb27.i.i74
movl 208(%esp), %ecx
movb (%ecx,%ebp), %al
movzbl %al, %ecx
movl %ecx, %edx
andl $1, %edx
negl %ecx
xorl $1, %edx
movl 204(%esp), %ebx
cmpb (%ebx,%ecx), %al
jne LBB5_813 # bb14.i.i.snake.exit.i_crit_edge

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080616/063792.html

Erm, and what's the difference? %ecx here is still clobbered

[llvmbot]

Sorry, copy and paste error:

    movl    204(%esp), %eax
movb    (%eax,%ebx), %al
movzbl  %al, %edx
    movl    %edx, %edi
    andl    $1, %edi
    negl    %edx
    xorl    $1, %edi
    movl    200(%esp), %ebp
    cmpb    (%ebp,%ecx), %al

[asl]

Sorry, copy and paste error:

    movl    204(%esp), %eax
    movb    (%eax,%ebx), %al
    movzbl  %al, %edx
    movl    %edx, %edi
    andl    $1, %edi
    negl    %edx
    xorl    $1, %edi
    movl    200(%esp), %ebp
    cmpb    (%ebp,%ecx), %al

Thanks!