[patch] Merge to trunk from Graphite branch

[Sebastian Pop]

On Tue, Mar 16, 2010 at 08:24, Ira Rosen <IRAR@il.ibm.com> wrote:
>
>
> dominiq@lps.ens.fr (Dominique Dhumieres) wrote on 16/03/2010 12:07:42 AM:
>
>> The missed vectorization seems related to the loop index being unknown:
>> if I replace 'do i = 1, n' with 'do i = 1, nl' with nl set to
>> some given value (say 100) the loop vectorize with -fgraphite-identity.
>>

Ok, I should look at the computation of niter on the code generated
by Graphite to see why it fails.

>
> In gas_dyn vectorization fails because Graphite inserts statements in latch
> blocks, e.g. (line 409),
>
> <bb 12>:
>  # ivtmp.2047_274 = PHI <ivtmp.2047_275(13), 0(11)>
>  D.7535_276 = (integer(kind=8)) ivtmp.2047_274;
>  S.26_217 = D.7535_276 + 1;
>  D.4310_112 = S.26_217 + -1;
>  (*gamma_113(D))[D.4310_112] = D.4292_73;
>  if (ivtmp.2047_274 < D.7533_233)
>    goto <bb 13>;
>  else
>    goto <bb 14>;
>
> <bb 13>:
>  ivtmp.2047_275 = ivtmp.2047_274 + 1;  <============= this statement
>  goto <bb 12>;
>

This is how the IV canonicalization is inserting the IV bumping.
I will try to put this stmt before the exit condition in the header bb.

Why is the vectorizer so picky about the latch bb to be empty?
Probably we should fix the vectorizer for this particular case?

> 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.  I will give a look at this as well.

Thanks for the detailed analysis of the missed vectorization cases,
Sebastian