[cfe-dev] Loop invariant and strength reduction
damien.llvm at gmail.com
Thu Feb 24 16:36:32 PST 2011
OK, I am wrong to a large extent.
For the following piece of code (see at the end of the message), the backend
still does generate a multiplication, but not inside the inner loop and does
not use indirect addressing as I said.
But still, it does use a multiplication (some targets might not even support
multiplications: e.g. some microcontrollers).
Basically the multiplication is done to update the pointer at the end of the
loop, the backend converts:
n times: ptr+=incr
1 time: ptr += n * incr;
And the backend is using a copy of the pointer for the inner loop that is
ptr_copy += incr;
so that there is no multiplication nor indirect addressing inside the inner
Anyway, thank you for the explanations on canonicalization.
===== Sample Code =====
Basically, this piece of code iterates on a list of concatenated arrays and
find the last array that has at least a value different from zero.
Compiled with llvm2.8 using:
clang -emit-llvm -O2 -S myfile.c -o myfile.ll
llc -O2 myfile.ll
int f(int *ptr, int incr, int *array_length, int narray)
int r = narray+1;
int n = *array_length;
r = narray;
ptr += incr;
On Thu, Feb 24, 2011 at 3:57 PM, John McCall <rjmccall at apple.com> wrote:
> On Feb 24, 2011, at 3:49 PM, Damien Vincent wrote:
> > OK, I wanted to simplify the example and it turns out that the backend
> optimizer is able to generate code without any multiplication.
> > But what if the backend cannot derive an IR without multiplication ? What
> was a simple code at the beginning might become more complicated...
> > I will simplify my example (but not that much) and post it on the mailing
> There are people who can speak to this better than I can, but my
> understanding is that the optimizers only do this transformation for loops
> that fit the narrow definition of canonical form that they expect the
> target-independent optimizer to be able to lower efficiently. By all means,
> though, if you can find a counter-example, that's something we want to know
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cfe-dev