[llvm-dev] Fwd: Strength reduction in loops

[Will via llvm-dev]

Thx for trying, Sanjay.

Now that I try and compile x86_64, I too see addq: clang -Os lsr.c -S -o -

But when I compile clang -Os lsr.c -S -emit-llvm -o -, I see multiplies :(

I even tried clang -Os hello48.c -S -emit-llvm -loop-reduce 
-loop-strength-reduce -o - for good measure.  Still multiples :(

I am using a variety of LLVM versions; you are presumably using the 
bleeding edge.  Do you also get multiplies in the IR?

(I am working on a backend which is not x86_64)

thousand thanks,
Will

On 04/01/16 17:31, Sanjay Patel wrote:
> 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 <mailto: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 <mailto: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/74e431e6/attachment.html>