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
Sanjay Patel via llvm-dev
2016-Jan-04 16:31 UTC
[llvm-dev] Fwd: Strength reduction in loops
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>
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>