[llvm-dev] Fwd: Strength reduction in loops

[Will via llvm-dev]

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