[lno] [RFC] if-conversion and auto vectorizer

[Dorit Naishlos]

> I am not at all sure what you want to achieve with this transformation;
> it seems to me that you haven't done anything that could possibly make
> vectorizer's work easier.

I think Devang's example showed an intermediate stage in the development of
the transformation. The final goal of the transformation is to transform a
multi-block loop like the following:

LOOP:
      if (A[i] > 0)
         {
           A[i] = A[i] + C[i];
           B[i] = A[i] + 1;
         }
       else
         {
           A[i] = D[i];
         }

into straight-line single block loop:

LOOP:
[1]   C = CMP A[i] > 0
[2]   A_then = A[i] + c[i]
[3]   A[i] = "SELECT" C ? A_then : A[i]
[4]   B_then = A[i] + 1
[5]   B[i] = "SELECT" C ? B_then : B[i]
[6]   A_else = D[i]
[7]   A[i] = "SELECT" ^C ? A_else : A[i]

[3]&[7] would be merged (by an additional pass, or directly) to obtain the
following optimized code:

LOOP:
[1]   C = CMP A[i] > 0
[2]   A_then = A[i] + c[i]
[3]   B_then = A[i] + 1
[4]   B[i] = "SELECT" C ? B_then : B[i]
[5]   A_else = D[i]
[6]   A[i] = "SELECT" C ? A_then : A_else

(This is also where special idioms like saturation, would be recognized.)

dorit




                                                                                                                                      
                      Zdenek Dvorak                                                                                                   
                      <rakdver@atrey.karlin.m        To:       Devang Patel <dpatel@apple.com>                                        
                      ff.cuni.cz>                    cc:       "gcc@gcc.gnu.org list" <gcc@gcc.gnu.org>, Jason Merrill                
                                                      <jason@redhat.com>, Dorit Naishlos/Haifa/IBM@IBMIL, Richard Henderson           
                      13/03/2004 11:24                <rth@redhat.com>, Diego Novillo <dnovillo@redhat.com>                           
                                                     Subject:  Re: [lno] [RFC] if-conversion and auto vectorizer                      
                                                                                                                                      




Hello,

> OK. So far I have coded transformation to transform
>
> bar ()
> {
>   int A[N+1], B[N+1], C[N+1], D[N+1];
>   int i;
>
>   for (i = 1; i<N; i++)
>     {
>       if (A[i] > 0)
>         {
>           A[i] = A[i] + C[i];
>           B[i] = A[i] + 1;
>         }
>       else
>         {
>           A[i] = D[i];
>           B[i] = D[i] + 1;
>         }
>     }
>   ibar(A);
>   ibar(B);
> }
>
> into :
>
> bar ()
> {
>   int i;
>   int D[17];
>   int C[17];
>   int B[17];
>   int A[17];
>   int T.5;
>   int T.4;
>   int T.3;
>   int T.2;
>   int T.1;
>   int T.0;
>
>   # BLOCK 0
>   # PRED: ENTRY [100.0%]  (fallthru,exec)
>   # SUCC: 1 [100.0%]  (fallthru,exec)
>
>   # BLOCK 1
>   # PRED: 6 [100.0%]  (fallthru) 0 [100.0%]  (fallthru,exec)
>   # i_1 = PHI <1(0), i_15(6)>;
> <L0>:;
>   T.0_3 = if (1)
>     {
>       A[i_1];
>     };
>   if (T.0_3 > 0) goto <L1>; else goto <L2>;
>   # SUCC: 3 [21.0%]  (false,exec) 2 [79.0%]  (true,exec)
>
>   # BLOCK 2
>   # PRED: 1 [79.0%]  (true,exec)
> <L1>:;
>   T.1_9 = if (1 && T.0_3 > 0)

why this "1 &&" part?

>     {
>       C[i_1];
>     };
>   T.2_10 = if (1 && T.0_3 > 0)
>     {
>       T.0_3 + T.1_9;
>     };
>   A[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.2_10
>     };
>   T.3_12 = if (1 && T.0_3 > 0)
>     {
>       T.2_10 + 1;
>     };
>   B[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.3_12
>     };
>   goto <bb 4> (<L3>);
>   # SUCC: 4 [100.0%]  (fallthru,exec)
>
>   # BLOCK 3
>   # PRED: 1 [21.0%]  (false,exec)
> <L2>:;
>   T.4_5 = if (1 && !(T.0_3 > 0))
>     {
>       D[i_1];
>     };
>   A[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5
>     };
>   T.5_7 = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5 + 1;
>     };
>   B[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.5_7
>     };
>   # SUCC: 4 [100.0%]  (fallthru,exec)
>
>   # BLOCK 4
>   # PRED: 3 [100.0%]  (fallthru,exec) 2 [100.0%]  (fallthru,exec)
> <L3>:;
>   i_15 = i_1 + 1;
>   if (i_15 <= 15) goto <L8>; else goto <L5>;
>   # SUCC: 5 [11.0%]  (false,exec) 6 [89.0%]  (true,exec)
>
>   # BLOCK 6
>   # PRED: 4 [89.0%]  (true,exec)
> <L8>:;
>   goto <bb 1> (<L0>);
>   # SUCC: 1 [100.0%]  (fallthru)
>
>   # BLOCK 5
>   # PRED: 4 [11.0%]  (false,exec)
> <L5>:;
>   ibar (&A);
>   ibar (&B);
>   return;
>   # SUCC: EXIT [100.0%]
>
> }
>
> I spent lot of time unnecessary to create super block inside loop by
> merging block 2 and 3 into block 1.
>
> If vectorizer can not vectorize this loop then it will be reverted to
> original form using loop versioning. Am I on the right track ?

I am not at all sure what you want to achieve with this transformation;
it seems to me that you haven't done anything that could possibly make
vectorizer's work easier.

Zdenek