[patch] Merge to trunk from Graphite branch

[Sebastian Pop]

On Tue, Mar 16, 2010 at 09:38, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Tue, 16 Mar 2010, Sebastian Pop wrote:
>
>> > In Toon's testcase from
>> > http://gcc.gnu.org/ml/gcc-patches/2010-03/msg00515.html vectorization fails
>> > because scev analysis failure: "evolution of offset is not affine." It
>> > probably gets confused by
>> >
>> >  # graphite_IV.22_66 = PHI <0(4), graphite_IV.22_67(6)>
>> >  var.23_77 = (character(kind=4)) graphite_IV.22_66;
>> >  D.1214_68 = (integer(kind=4)) var.23_77;
>> >  i_69 = D.1214_68 + 1;
>> >  D.1192_70 = (integer(kind=8)) i_69;
>> >  D.1193_71 = D.1192_70 + -1;
>> >  D.1194_72 = (*a_39(D))[D.1193_71];
>> >
>> >  instead (without Graphite)
>> >
>> >  # i_1 = PHI <1(3), i_48(5)>
>> >  D.1192_37 = (integer(kind=8)) i_1;
>> >  D.1193_38 = D.1192_37 + -1;
>> >  D.1194_40 = (*a_39(D))[D.1193_38];
>> >
>>
>> Looks like the scev analysis fails because of too many casts
>> on the way, otherwise I see no particular difficulty in the code
>> generated by Graphite.
>
> Both sequences aren't equivalent, so my guess would be that the
> transformation done by graphite actually is buggy or at least suboptimal.
> The difference lies in the overflow behaviour.  Without graphite, i_1 has
> undefined overflow, as D.1192_37 too, hence we can look through the
> conversion.  With graphite var.23_77 (of unsigned type) has defined
> overflow semantics, hence we can't look through that conversion.
>

Right, the new induction variable that we create does not maintain the
signedness of the original IV.  This is due to IV canonicalization
that systematically creates unsigned IVs.  The usual example of why we
need to generate an unsigned IV is due to the fact that with signed
IVs we can generate a loop that rolls for MAX iterations, with MAX the
maximal value of the unsigned type:

  char i;
  for (i = -127; i < 128; i++)
    S;

This loop runs for 255 iterations, and thus in the IV canonical form,
that is one IV per loop, IV->base = 0, and IV->step = 1, the type of
the IV should be unsigned char.

The fix that I am proposing to preserve the signedness of the original
IVs, is to remove the need for the IV canonicalization.  I am
preparing a set of patches for doing that.

Sebastian