Strength reduction in loops

Project Infrastructure LLVM Dev List Archives
1

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?

(Strength reduction - Wikipedia 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." :slight_smile: )

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

2

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

3

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 :frowning:

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

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

4

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. 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).