[cfe-dev] Loop invariant and strength reduction

[John McCall]

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;
> 
>   do
>   {
>     if(*ptr!=0)
>       r = n;
>     ptr += incr;
>     n--;
>   } 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
Leh_func_begin0:
## BB#0:                                ## %entry
	pushq	%rbp
Ltmp0:
	movq	%rsp, %rbp
Ltmp1:
	leal	-1(%rdx), %ecx
	movslq	%esi, %rsi
	shlq	$2, %rsi
	incq	%rcx
	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
	decl	%edx
	decq	%rcx
	jne	LBB0_1
## BB#2:                                ## %do.end
	popq	%rbp
	ret

LLVM's backend optimizers are quite powerful;  don't assume that the IR is the last word on the subject.

John.