[PATCH] [RFC] loop index promotion pass

[Richard Guenther]

On Wed, May 20, 2009 at 3:39 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> On Wed, May 20, 2009 at 10:51:05AM +0200, Richard Guenther wrote:
>> On Wed, May 20, 2009 at 12:48 AM, Mark Mitchell <mark@codesourcery.com> wrote:
>> > I think we should accept the patch (modulo, of course, any fixes
>> > required in the ordinary course of review), unless someone sees a
>> > better, and relatively easy, way to provide the same benefit. ?We can
>> > always rip it out if there turns out to be a better way.
>>
>> I'd like to see compile-time numbers.  And I am not convinced
>> (after looking at the testcase) that this transformation is valid
>> unless you can prove that the narrower IVs do not wrap.
>> Nathan, can you convince me that you are properly checking
>> if the transformation is valid?
>
> The function analyze_loop_index_definition_pattern aims to do exactly
> that.  The idea is that if we have:
>
>  for (index = start; index < end; index += incr)
>
> If INDEX is not modified elsewhere in the loop, INDEX and END are of the
> same type, and INCR is 1, then we know overflow does not occur.  This
> assumes INDEX is signed: I see after looking at
> analyze_loop_index_definition_pattern that it has comments about the
> safety of the transformation if INDEX is unsigned, but it never checks
> for TYPE_UNSIGNED.  Those checks might have gotten lost in the
> conversion to tuples; I will need to fix that.

Hmm.  So use simple_iv () to check if INDEX is of this kind.  Indeed
most of this would fit better in IVOPTs (simply add promoted
candidates and adjust their cost) like steven said.

Note that IVOPTs even can create complex uses of a promoted IV,
like inserting truncations if they are necessary - you seem to
disqualify most complex uses.

The idea of promoting IVs to the natural integer type of the machine
is good - see also Sebastians post about this.

Zdenek, is there a reason why doing the promotion in IVOPTs would
not work?

Thanks,
Richard.