chandlerc
commented
9 years ago OK, but is this a combine bug? I think not. That assembly produced by LLVM is just BAD. Really bad. Here is a trivial and obvious re-register allocation of it. The key thing is to set up the accumulated register in %eax, and copy to %edi for the comparison. % cat write.s
.text .file "" .globl _Z1fjPh .align 16, 0x90 .type _Z1fjPh,@function _Z1fjPh: # @_Z1fjPh .cfi_startproc BB#0: # %entry
movl %edi, %eax cmpl $128, %eax jb .LBB0_1 .align 16, 0x90.LBB0_2: # %while.body
=>This Inner Loop Header: Depth=1
orl $128, %eax movb %al, (%rsi) movl %eax, %edi shrl $7, %eax incq %rsi cmpl $16383, %edi # imm = 0x3FFF ja .LBB0_2.LBB0_1: movb %al, (%rsi) incq %rsi movq %rsi, %rax retq .Ltmp0: .size _Z1fjPh, .Ltmp0-_Z1fjPh .cfi_endproc
.ident "clang version 3.7.0 (trunk 227279) (llvm/trunk 227300)" .section ".note.GNU-stack","",@progbits
Arrrg, this section was stale. The above code is just wrong. Ignore it. What I actually benchmarked was as follows. It requires both better register allocation by continuing to use %edi out of the loop, and realizing that we can compare against %eax even after or-ing in 128 because that couldn't have changed the result. Anyways, sorry for the confusion. Here is the code I actually measured at this phase of the writeup:
.text
.file "<stdin>"
.globl _Z1fjPh
.align 16, 0x90
.type _Z1fjPh,@function_Z1fjPh: # @_Z1fjPh .cfi_startproc
BB#0: # %entry
cmpl $128, %edi
jb .LBB0_1
.align 16, 0x90.LBB0_2: # %while.body
=>This Inner Loop Header: Depth=1
movl %edi, %eax
orl $128, %eax
movb %al, (%rsi)
shrl $7, %edi
incq %rsi
cmpl $16383, %eax # imm = 0x3FFF
ja .LBB0_2.LBB0_1: movb %dil, (%rsi) incq %rsi movq %rsi, %rax retq .Ltmp0: .size _Z1fjPh, .Ltmp0-_Z1fjPh .cfi_endproc
.ident "clang version 3.7.0 (trunk 227279) (llvm/trunk 227300)"
.section ".note.GNU-stack","",@progbits
Extended Description
Consider the function:
uint8 f(uint32 value, uint8 target) { while (value >= 0x80) { target = static_cast(value | 0x80);
value >>= 7;
++target;
}
target = static_cast(value);
return target + 1;
}
For, this function, "clang -O2 -S" generates:
.LBB0_2: # %while.body
=>This Inner Loop Header: Depth=1
.LBB0_1: movl %edi, %eax .LBB0_3: # %while.end movb %al, (%rsi) incq %rsi movq %rsi, %rax retq
Which seems quite inefficient. There are several unnecessary moves. GCC instead translates this to:
.L3: movl %edi, %eax addq $1, %rsi shrl $7, %edi orl $-128, %eax movb %al, -1(%rsi) .L4: cmpl $127, %edi ja .L3 movb %dil, (%rsi) leaq 1(%rsi), %rax ret
The LLVM IR generated by clang here already generates code that is very similar to the final output (with instcombine folding the shift into the compare). If I prevent this folding by adding "if (!Shr->hasOneUse()) return nullptr;" in InstCombiner::FoldICmpShrCst() (lib/Transforms/InstCombine/InstCombineCompares.cpp), then LLVM's code gets somewhat better, but I suspect that LLVM should really be able to lower the IR better.