[llvm-dev] Fwd: Strength reduction in loops

[Jingyue Wu via llvm-dev]

Hi Will,

I believe the reason you still see multiplies with "clang -emit-llvm" is
that LoopStrengthReduction is not in the target-independent optimization
pipeline. It runs in the target-specific IR optimizer.

If you take the IR emitted with "clang -emit-llvm" and run "llc foo.ll
-print-after-all", you should be able to see the IR right after applying
LSR. The x86 backend adds LoopStrengthReduce to its target-specific
pipeline here
<https://github.com/llvm-mirror/llvm/blob/b1415e7ebadc135ddad990a19d30aed8757587da/lib/CodeGen/Passes.cpp#L412>.
If you want LLVM to run LSR for your backend, make sure your
TargetPassConfig adds LSR or calls the generic
TargetPassConfig::addIRPasses (e.g. see how the NVPTX backend adds LSR
<https://github.com/llvm-mirror/llvm/blob/b1415e7ebadc135ddad990a19d30aed8757587da/lib/Target/NVPTX/NVPTXTargetMachine.cpp#L169>
).

On Mon, Jan 4, 2016 at 1:30 PM, Will via llvm-dev <llvm-dev at lists.llvm.org>
wrote:

> 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 guess Clang doesn't consume per-optimization flags such as -loop-reduce.
opt takes them. So, try "opt -loop-reduce unopt.ll -o opt.ll".


>
> 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
> > 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
>>
>
>
>
> _______________________________________________
> 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/e6707cd8/attachment.html>