[cfe-dev] Loop invariant and strength reduction
rjmccall at apple.com
Thu Feb 24 15:33:56 PST 2011
On Feb 24, 2011, at 3:25 PM, Damien Vincent wrote:
> When I compile to llvm (using -emit-llvm -O2 -S) the following piece of code:
> int f(int *ptr, int incr, int n)
> int r = n+1;
> r = n;
> ptr += incr;
> } while(n!=0);
> return r;
> clang notices the index can be generated using a multiplication ( ptr[incr * loopindex] ) and generates some code which is at least as complicated (a multiplication is more or at least as complex as an addition + the generated code uses indirect addressing instead of direct addressing which is sometimes more complex).
> I am new to clang but I was thinking a compiler should do some strength reduction (and not the other way !).
> Could you explain me why clang replaces this addition+direct addressing by a multiplication + indirect addressing ?
The optimizer is canonicalizing the loop, which the backend then lowers to a more efficient form:
_f: ## @f
## BB#0: ## %entry
movq %rsp, %rbp
leal -1(%rdx), %ecx
movslq %esi, %rsi
shlq $2, %rsi
leal 1(%rdx), %eax
.align 4, 0x90
LBB0_1: ## %do.body
## =>This Inner Loop Header: Depth=1
cmpl $0, (%rdi)
cmovnel %edx, %eax
addq %rsi, %rdi
## BB#2: ## %do.end
LLVM's backend optimizers are quite powerful; don't assume that the IR is the last word on the subject.
More information about the cfe-dev