x86 backend misses read-modify-write opportunity

[nlewycky]

Bugzilla Link	1160
Resolution	LATER
Resolved on	Sep 26, 2007 01:31
Version	trunk
OS	Linux
CC	@asl,@lattner

Extended Description

This small program produces bad x86 assembly code:

unsigned int huge[2048];
unsigned int target[2048];

extern void foo();

int main(int argc, char *argv[])
{
foo();

for (unsigned int i = 0; i < 2048; i++)
{
target[i] |= huge[i];
}

unsigned int x = 0;
for (unsigned int i = 0; i < 2048; i++)
{
x += target[i];
}

return x;
}

There are two problems with the resulting x86 assembly.

For the body of the first loop, LLVM produces:

    movl huge(,%eax,4), %ecx
    orl target(,%eax,4), %ecx
    movl %ecx, target(,%eax,4)

when it should really be loading from huge, then or'ing into target.

In the second loop, LLVM mis-predicts the exit branch, which is inexcusable
seeing as the loop is countable:

.LBB1_5: #bb23
cmpl $2048, %ecx
jne .LBB1_3 #bb15 <--- should be reversed
.LBB1_6: #bb27
addl $4, %esp
ret
.LBB1_3: #bb15
addl target(,%ecx,4), %eax
incl %ecx
jmp .LBB1_5 #bb23

[asl]

llvm-gcc -O3 produces the folowing LLVM code:

target datalayout = "e-p:32:32"
target triple = "i686-pc-linux-gnu"
@​huge = global [2048 x i32] zeroinitializer, align 32 ; <[2048 x
i32]> [#uses=2]
@​target = global [2048 x i32] zeroinitializer, align 32 ; <[2048 x
i32]> [#uses=3]

implementation ; Functions:

define i32 @​main(i32 %argc, i8** %argv) {
entry:
tail call void @​_Z3foov( )
br label %bb

bb: ; preds = %bb, %entry
%i.0.0 = phi i32 [ 0, %entry ], [ %indvar.next, %bb ] ;
[#uses=3]
%tmp2 = getelementptr [2048 x i32]* @​target, i32 0, i32 %i.0.0
; <i32*> [#uses=2]
%tmp3 = load i32* %tmp2 ; [#uses=1]
%tmp5 = getelementptr [2048 x i32]* @​huge, i32 0, i32 %i.0.0
; <i32*> [#uses=1]
%tmp6 = load i32* %tmp5 ; [#uses=1]
%tmp7 = or i32 %tmp6, %tmp3 ; [#uses=1]
store i32 %tmp7, i32* %tmp2
%indvar.next = add i32 %i.0.0, 1 ; [#uses=2]
%exitcond = icmp eq i32 %indvar.next, 2048 ; [#uses=1]
br i1 %exitcond, label %bb23, label %bb

bb15: ; preds = %bb23
%tmp17 = getelementptr [2048 x i32]* @​target, i32 0, i32 %i14.0
; <i32*> [#uses=1]
%tmp18 = load i32* %tmp17 ; [#uses=1]
%tmp20 = add i32 %tmp18, %x.0 ; [#uses=1]
%indvar.next37 = add i32 %i14.0, 1 ; [#uses=1]
br label %bb23

bb23: ; preds = %bb, %bb15
%i14.0 = phi i32 [ %indvar.next37, %bb15 ], [ 0, %bb ] ;
[#uses=3]
%x.0 = phi i32 [ %tmp20, %bb15 ], [ 0, %bb ] ; [#uses=2]
%exitcond38 = icmp eq i32 %i14.0, 2048 ; [#uses=1]
br i1 %exitcond38, label %bb27, label %bb15

bb27: ; preds = %bb23
ret i32 %x.0
}

So, the problem is definitely not in codegen, but in some optimization passes.

[asl]

Err, sorry. Only the first case is optimizer issue. The second - codegen.

[asl]

So, if I comment the first loop generated assembler code for second loop is fine:

.LBB1_1: #bb7
addl target(,%ecx,4), %eax
incl %ecx
cmpl $2048, %ecx
jne .LBB1_1 #bb7
.LBB1_3: #bb9
movl %ebp, %esp
popl %ebp
ret

[nlewycky]

I'm not sure the intermediate code is the problem with the first loop. It has to
fundamentally come down to these operations:

%A = load i32* %huge_ptr
%B = load i32* %target_ptr
%C = or i32 %A, %B
store i32 %C, i32* %target_ptr

How else would it be written?

[lattner]

This looks like the X86 backend isn't matching RMW instructions aggressively enough. Here's a
reduced testcase:

define void @​test(i32* %huge_ptr, i32* %target_ptr) {
%A = load i32* %huge_ptr ; [#uses=1]
%B = load i32* %target_ptr ; [#uses=1]
%C = or i32 %A, %B ; [#uses=1]
store i32 %C, i32* %target_ptr
ret void
}

$ llvm-as < t.ll | llc -march=x86-64

_test:
movl (%rdi), %eax
orl (%rsi), %eax
movl %eax, (%rsi)
ret

That should be something like:

_test:
movl (%rdi), %eax
orl %eax, (%rsi)
ret

-Chris

[llvmbot]

Fixed:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046911.html
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047158.html
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047160.html

[llvmbot]

Oops. Ignore my previous comments.

[llvmbot]

Code quality bugs are "enhancements"

[lattner]

Some progress on this bug. With -static, we now produce pretty nice code for the first loop, but we still don't get the RMW thing correct:

LBB1_1: # bb
movl _huge(,%eax,4), %ecx
orl _target(,%eax,4), %ecx
movl %ecx, _target(,%eax,4)
incl %eax
cmpl $2048, %eax
jne LBB1_1 # bb

I entered the reduced testcase into the README.txt file here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070924/053908.html

In the second loop, we are now producing nice simple code with no branches in it:

LBB1_3: # bb18
addl _target(,%ecx,4), %eax
incl %ecx
cmpl $2048, %ecx
jne LBB1_3 # bb18

Thus this bug is subsumed by the readme entry. Closing.

-Chris