llvm dev - Feb 2018 - Pattern not recognized as reduction

Reduction Not Captured By LLVM

CODE_1

------------------------------------------------------------
------------------------------------------------------------
--------------------

#include <stdio.h>

int main()

{

       int sum[1000]={1,2,3,4};

       for (int i=1;i<1000;i++)

       {

               sum[0]  +=sum[i-1];

       }

}

------------------------------------------------------------
------------------------------------------------------------
--------------------

In the code given above, we tried to run the vectorization pass of LLVM.
The remark emitted by vectorizer says the following :-

REMARKS_1

------------------------------------------------------------
-------------------------------------------------------------------

test6.c:8:11: remark: loop not vectorized: value that could not be
identified as reduction is used outside the loop [-Rpass-analysis=loop-
vectorize]

  sum[0] += sum[i-1];

         ^

test6.c:6:3: remark: loop not vectorized: unsafe dependent memory
operations in loop. Use #pragma loop distribute(enable) to allow loop
distribution to attempt to

     isolate the offending operations into a separate loop
[-Rpass-analysis=loop-vectorize]

 for(int i=100;i<1000;i++)

 ^

------------------------------------------------------------
-------------------------------------------------------------------

The command used for capturing the remarks from above code is

clang -O3 -ffast-math -mavx2 -Rpass=loop-vectorize
-Rpass-analysis=loop-vectorize file.c



On the other hand , if we replace in the same code sum[0] by x and making
very slight changes , it gets vectorized and prints the following remarks :





CODE_2

------------------------------------------------------------
---------------------------------------------------------

#include <stdio.h>

int main()

{

      int sum[1000]={1,2,3,4};

      int x = 0;

      for (int i=1;i<1000;i++)

      {

              x  +=sum[i-1];

      }

      sum[0] = x;

      return sum[0];

}

------------------------------------------------------------
------------------------------------------------------------
--------------------

REMARKS_2

------------------------------------------------------------
-------------------------------------------------------------------

test6.c:6:3: remark: vectorized loop (vectorization width: 8, interleaved
count: 4) [-Rpass=loop-vectorize]

 for(int i=100;i<1000;i++)

 ^

------------------------------------------------------------
-------------------------------------------------------------------




Q : Why sum[0] += sum[i-1] is not identified as reduction by LLVM ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180212/4af5602e/attachment.html>

Hi,

LoopVectorizer only deals with reductions in registers, not in memory. In
your original example, the running sum is stored back to memory at every
iteration. There's no way to do that with vector instructions.

Cheers,
Philip

2018-02-12 8:41 GMT+01:00 Himanshu Shukla via llvm-dev <
llvm-dev at lists.llvm.org>:
> Reduction Not Captured By LLVM
>
> CODE_1
>
> ------------------------------------------------------------
> ------------------------------------------------------------
> --------------------
>
> #include <stdio.h>
>
> int main()
>
> {
>
>        int sum[1000]={1,2,3,4};
>
>        for (int i=1;i<1000;i++)
>
>        {
>
>                sum[0]  +=sum[i-1];
>
>        }
>
> }
>
> ------------------------------------------------------------
> ------------------------------------------------------------
> --------------------
>
> In the code given above, we tried to run the vectorization pass of LLVM.
> The remark emitted by vectorizer says the following :-
>
> REMARKS_1
>
> ------------------------------------------------------------
> -------------------------------------------------------------------
>
> test6.c:8:11: remark: loop not vectorized: value that could not be
> identified as reduction is used outside the loop
> [-Rpass-analysis=loop-vectorize]
>
>   sum[0] += sum[i-1];
>
>          ^
>
> test6.c:6:3: remark: loop not vectorized: unsafe dependent memory
> operations in loop. Use #pragma loop distribute(enable) to allow loop
> distribution to attempt to
>
>      isolate the offending operations into a separate loop
> [-Rpass-analysis=loop-vectorize]
>
>  for(int i=100;i<1000;i++)
>
>  ^
>
> ------------------------------------------------------------
> -------------------------------------------------------------------
>
> The command used for capturing the remarks from above code is
>
> clang -O3 -ffast-math -mavx2 -Rpass=loop-vectorize
> -Rpass-analysis=loop-vectorize file.c
>
>
>
> On the other hand , if we replace in the same code sum[0] by x and making
> very slight changes , it gets vectorized and prints the following remarks :
>
>
>
>
>
> CODE_2
>
> ------------------------------------------------------------
> ---------------------------------------------------------
>
> #include <stdio.h>
>
> int main()
>
> {
>
>       int sum[1000]={1,2,3,4};
>
>       int x = 0;
>
>       for (int i=1;i<1000;i++)
>
>       {
>
>               x  +=sum[i-1];
>
>       }
>
>       sum[0] = x;
>
>       return sum[0];
>
> }
>
> ------------------------------------------------------------
> ------------------------------------------------------------
> --------------------
>
> REMARKS_2
>
> ------------------------------------------------------------
> -------------------------------------------------------------------
>
> test6.c:6:3: remark: vectorized loop (vectorization width: 8, interleaved
> count: 4) [-Rpass=loop-vectorize]
>
>  for(int i=100;i<1000;i++)
>
>  ^
>
> ------------------------------------------------------------
> -------------------------------------------------------------------
>
>
>
>
> Q : Why sum[0] += sum[i-1] is not identified as reduction by LLVM ?
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180214/f6bc9eec/attachment.html>