<br>
OK, I am wrong to a large extent.<br>
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.<br>
But still, it does use a multiplication (some targets might not even support multiplications: e.g. some microcontrollers).<br>
<br>
Basically the multiplication is done to update the pointer at the end of the loop, the backend converts:<br>
n times: ptr+=incr<br>
to<br>
1 time: ptr += n * incr;<br>
<br>
And the backend is using a copy of the pointer for the inner loop that is incremented by:<br>
ptr_copy += incr;<br>
so that there is no multiplication nor indirect addressing inside the inner loop.<br>
<br>
Anyway, thank you for the explanations on canonicalization.<br>
<br>
  Damien<br>
<br>
<br>
===== Sample Code =====<br>
<br>
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.<br>
<br>
Compiled with llvm2.8 using:<br>
clang  -emit-llvm -O2 -S myfile.c -o myfile.ll<br>
llc -O2 myfile.ll<br>
<br>
<br>
int f(int *ptr, int incr, int *array_length, int narray)<br>
{<br>
  int r = narray+1;<br>
<br>
  do<br>
  {<br>
    int n = *array_length;<br>
<br>
    do<br>
    {<br>
      if(*ptr!=0)<br>
        r = narray;<br>
      ptr += incr;<br>
      n--;<br>
    } while(n!=0);<br>
<br>
    array_length++;<br>
    narray--;<br>
  } while(narray!=0);<br>
<br>
  return r;<br>
}<br><br><div class="gmail_quote">On Thu, Feb 24, 2011 at 3:57 PM, John McCall <span dir="ltr"><<a href="mailto:rjmccall@apple.com">rjmccall@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="im">On Feb 24, 2011, at 3:49 PM, Damien Vincent wrote:<br>
> OK, I wanted to simplify the example and it turns out that the backend optimizer is able to generate code without any multiplication.<br>
> But what if the backend cannot derive an IR without multiplication ? What was a simple code at the beginning might become more complicated...<br>
><br>
> I will simplify my example (but not that much) and post it on the mailing list.<br>
<br>
</div>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 about.<br>

<font color="#888888"><br>
John.</font></blockquote></div><br>