[cfe-dev] Loop invariant and strength reduction

[Damien Vincent]

Thanks.

OK, I wanted to simplify the example and it turns out that the backend
optimizer is able to generate code without any multiplication.
But what if the backend cannot derive an IR without multiplication ? What
was a simple code at the beginning might become more complicated...

I will simplify my example (but not that much) and post it on the mailing
list.

Damien


On Thu, Feb 24, 2011 at 3:33 PM, John McCall <rjmccall at apple.com> wrote:

> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20110224/2267e06a/attachment.html>