[4.5] Find more autoinc addressing for induction variables

[Bernd Schmidt]

Steven Bosscher wrote:

> But in any case I think the patch should not go onto the trunk in its
> current form for other technical reasons.

And these would be...?  So far you've only given alternatives which 
aren't equivalent and wouldn't work.

> FWIW I do understand the important of this optimization and I know
> auto-inc/dec support in GCC should be improved. But there has to be a
> cheaper and easier, more generic way

Feel free to suggest one if one occurs to you that actually works.  As 
long as you don't have a realistic suggestion, "there has to be" isn't 
patch review, it's wishful thinking and obstructionism.  I'm trying to 
solve a long-standing problem with gcc here.

> (one that can also be extended to handle more than just FORM_POST_INC).

As far as I understood the code in auto-inc-dec.c, it can also generate 
preincrement if we find such a candidate.  If we have a memory reference 
with offset 4, followed by an inc by 4, that can be turned into 
preincrement.  If my ivopts patch works as intended, it should generate 
such cases for targets that have preincrement, but I haven't had a 
chance to test this.

We could look for increment/memory reference pairs in the other order, 
but given how most loops are structured, that seems unlikely to trigger 
very often - bivs tend to be incremented at the end.

>> x = &y[0];
>> for (i = 0; i < n; i++) {
>>  for (j = 0; j < m; j++) {
>>    foo (*x);
>>    if (bar ())
>>      break;
>>    x++;
>>  }
>> }
>>
>> If the outer loop isn't there, or the initialization is moved into it, we
>> can use autoincrement, but here we need to avoid doing so.
> 
> Would things simplify if you can make sure that B and C are in the
> same loop?  This is easy to test (they must have the same
> loop_father).

That's a necessary condition, and I've experimented with using it to 
bail out early if it isn't true.  However, it didn't seem to have any 
effect on run time.
It's not a sufficient condition, since either one may be inside an if 
statement.  Also, if you look at the example above, you'll find that 
both B and C _are_ in the same loop; whether we can use autoinc depends 
on the code _outside_ the loop.

> Thanks for the test case.
> Are you preparing an updated tree-ssa-loop-ivopts patch or can I use
> the one you already posted?

I'll send another one out eventually; I'll probably try for another 
improvement in the heuristic first.  For testing on the Blackfin, you 
can use either one of the versions I already posted.


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif