[llvm-dev] Fwd: Strength reduction in loops

[Sanjay Patel via llvm-dev]

This should be handled in:
https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/LoopStrengthReduce.cpp

And it seems to work for both of your examples (x86-64 target):
$ ./clang -Os lsr.c -S -o - | grep addq
    addq    (%rsi), %rax
    addq    $96, %rsi   ; 12 * 8 bytes
    addq    $44, %rbx  ; 11 * 4 bytes


On Mon, Jan 4, 2016 at 3:27 AM, Will via llvm-dev <llvm-dev at lists.llvm.org>
wrote:

> Here is a simple loop:
>
> long foo(int len, long* s) {
>     long sum = 0;
>     for (int i=0; i<len; i++)
>         sum += s[i*12];
>     return sum;
> }
>
> There is a multiplication in each loop iteration.  Can this be turned
> into addition, and is there already a pass that does?
>
> (https://en.wikipedia.org/wiki/Strength_reduction uses this very
> situation as an example in the opening paragraph:
>
> "In software engineering, strength reduction is a compiler optimization
> where expensive operations are replaced with equivalent but less
> expensive operations. The classic example of strength reduction converts
> "strong" multiplications inside a loop into "weaker" additions –
> something that frequently occurs in array addressing." :) )
>
> And here is another loop:
>
> extern void foo(int);
>
> typedef struct {int i; int a[10];} S;
>
> void bar(S* A) {
>     for(int i = 50; i < 400;i++)
>         foo(A[i].i);
> }
>
> In this case, there is a multiplication in each loop iteration 'hidden'
> in the GEP.  Can this be turned into addition too?
>
> I was hoping the loop-reduce pass would do this kind of thing; should it?
>
> Thx
> Will
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160104/cb62e09b/attachment-0001.html>