[llvm-dev] LoopVectorize fails to vectorize more complex loops

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] LoopVectorize fails to vectorize more complex loops

Zhizhou Yang via llvm-dev
   Hello.
     Could you please tell me why the first loop of the following program (also maybe the
commented loop) doesn't get vectorized with LoopVectorize (from a recent LLVM build from
the SVN repository from Jun 2018)?

typedef short TYPE;
TYPE data[1400][1200];

void kernel_covariance(int m, int n, TYPE mean[1200]) {
   int i, j, k;

   for (j = 0; j < m; j++)
     {
       mean[j] = 0.0;
       for (i = 0; i < n; i++)
         mean[j] += data[j][i];
       //mean[j] /= float_n;
     }

   // This loop gets vectorized
   for (i = 0; i < n; i++)
     for (j = 0; j < m; j++)
       data[i][j] -= mean[j];

   /*
   // This loop doesn't get vectorized either:
   for (i = 0; i < m; i++)
     for (j = i; j < m; j++)
       {
         cov[i][j] = 0.0;
         for (k = 0; k < n; k++)
           cov[i][j] += data[i][k] * data[j][k];
           sum += data[i][k] * data[j][k];
         cov[i][j] /= (float_n - 1.0);
         cov[j][i] = cov[i][j];
       }
   */
}

   For the first loop I get the following debug info from clang and opt:
     LV: Checking a loop in "kernel_covariance" from test.c:10:7
     LV: Loop hints: force=? width=0 unroll=0
     LV: Found a loop: for.body3.us
     LV: PHI is not a poly recurrence.
     LV: PHI is not a poly recurrence.
     LV: Found an unidentified PHI.  %2 = phi i16 [ 0, %for.body.us ], [ %add.us,
%for.body3.us ], !dbg !48
     LV: Can't vectorize the instructions or CFG
     LV: Not vectorizing: Cannot prove legality.

   Thank you,
     Alex
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] LoopVectorize fails to vectorize more complex loops

Zhizhou Yang via llvm-dev
Hi Alex,

This seems like LICM problem, where it's not able to promote the memory reference to scalar because of unknown aliasing.
This result recurrence store remain in the loop body and loop vectorization fails to vectorize.
Loop Versioning LICM pass can help in this case.

- Ashutosh

-----Original Message-----
From: llvm-dev [mailto:[hidden email]] On Behalf Of Alex Susu via llvm-dev
Sent: Saturday, July 7, 2018 6:22 AM
To: llvm-dev <[hidden email]>
Subject: [llvm-dev] LoopVectorize fails to vectorize more complex loops

   Hello.
     Could you please tell me why the first loop of the following program (also maybe the commented loop) doesn't get vectorized with LoopVectorize (from a recent LLVM build from the SVN repository from Jun 2018)?

typedef short TYPE;
TYPE data[1400][1200];

void kernel_covariance(int m, int n, TYPE mean[1200]) {
   int i, j, k;

   for (j = 0; j < m; j++)
     {
       mean[j] = 0.0;
       for (i = 0; i < n; i++)
         mean[j] += data[j][i];
       //mean[j] /= float_n;
     }

   // This loop gets vectorized
   for (i = 0; i < n; i++)
     for (j = 0; j < m; j++)
       data[i][j] -= mean[j];

   /*
   // This loop doesn't get vectorized either:
   for (i = 0; i < m; i++)
     for (j = i; j < m; j++)
       {
         cov[i][j] = 0.0;
         for (k = 0; k < n; k++)
           cov[i][j] += data[i][k] * data[j][k];
           sum += data[i][k] * data[j][k];
         cov[i][j] /= (float_n - 1.0);
         cov[j][i] = cov[i][j];
       }
   */
}

   For the first loop I get the following debug info from clang and opt:
     LV: Checking a loop in "kernel_covariance" from test.c:10:7
     LV: Loop hints: force=? width=0 unroll=0
     LV: Found a loop: for.body3.us
     LV: PHI is not a poly recurrence.
     LV: PHI is not a poly recurrence.
     LV: Found an unidentified PHI.  %2 = phi i16 [ 0, %for.body.us ], [ %add.us, %for.body3.us ], !dbg !48
     LV: Can't vectorize the instructions or CFG
     LV: Not vectorizing: Cannot prove legality.

   Thank you,
     Alex
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] LoopVectorize fails to vectorize more complex loops

Zhizhou Yang via llvm-dev
Agreed on the aliasing issue. You could also rewrite your loop like this:

   for (j = 0; j < m; j++)
     {
       TYPE red = 0.0;
       for (i = 0; i < n; i++)
           red += data[j][i];
       mean[j] = red;
     }

Diego

> -----Original Message-----
> From: llvm-dev [mailto:[hidden email]] On Behalf Of
> Nema, Ashutosh via llvm-dev
> Sent: Friday, July 6, 2018 7:48 PM
> To: Alex Susu <[hidden email]>
> Cc: [hidden email]
> Subject: Re: [llvm-dev] LoopVectorize fails to vectorize more complex loops
>
> Hi Alex,
>
> This seems like LICM problem, where it's not able to promote the memory
> reference to scalar because of unknown aliasing.
> This result recurrence store remain in the loop body and loop vectorization
> fails to vectorize.
> Loop Versioning LICM pass can help in this case.
>
> - Ashutosh
>
> -----Original Message-----
> From: llvm-dev [mailto:[hidden email]] On Behalf Of Alex
> Susu via llvm-dev
> Sent: Saturday, July 7, 2018 6:22 AM
> To: llvm-dev <[hidden email]>
> Subject: [llvm-dev] LoopVectorize fails to vectorize more complex loops
>
>    Hello.
>      Could you please tell me why the first loop of the following program (also
> maybe the commented loop) doesn't get vectorized with LoopVectorize
> (from a recent LLVM build from the SVN repository from Jun 2018)?
>
> typedef short TYPE;
> TYPE data[1400][1200];
>
> void kernel_covariance(int m, int n, TYPE mean[1200]) {
>    int i, j, k;
>
>    for (j = 0; j < m; j++)
>      {
>        mean[j] = 0.0;
>        for (i = 0; i < n; i++)
>          mean[j] += data[j][i];
>        //mean[j] /= float_n;
>      }
>
>    // This loop gets vectorized
>    for (i = 0; i < n; i++)
>      for (j = 0; j < m; j++)
>        data[i][j] -= mean[j];
>
>    /*
>    // This loop doesn't get vectorized either:
>    for (i = 0; i < m; i++)
>      for (j = i; j < m; j++)
>        {
>          cov[i][j] = 0.0;
>          for (k = 0; k < n; k++)
>            cov[i][j] += data[i][k] * data[j][k];
>            sum += data[i][k] * data[j][k];
>          cov[i][j] /= (float_n - 1.0);
>          cov[j][i] = cov[i][j];
>        }
>    */
> }
>
>    For the first loop I get the following debug info from clang and opt:
>      LV: Checking a loop in "kernel_covariance" from test.c:10:7
>      LV: Loop hints: force=? width=0 unroll=0
>      LV: Found a loop: for.body3.us
>      LV: PHI is not a poly recurrence.
>      LV: PHI is not a poly recurrence.
>      LV: Found an unidentified PHI.  %2 = phi i16 [ 0, %for.body.us ], [ %add.us,
> %for.body3.us ], !dbg !48
>      LV: Can't vectorize the instructions or CFG
>      LV: Not vectorizing: Cannot prove legality.
>
>    Thank you,
>      Alex
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev