[llvm-dev] LoopVectorize fails to vectorize code with condition on reduction

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 code with condition on reduction

div code via llvm-dev
   Hello.
     I'm not able to vectorize this simple C loop doing basically what could be called
predicated sum-reduction:
       #define NMAX 1000
       int colOccupied[NMAX];
       void Func(int N) {
         int numSol = 0;
         for (int c = 0; c < N; c++) {
             if (colOccupied[c] == 0)
                 numSol++;
         }
         return numSol;
       }

     The compiler command I used was:
         clang -O3 -emit-llvm -S -mllvm -debug -ffast-math A.cpp -fvectorize -mllvm
-force-vector-width=16

     Following is the output of LLVM's opt explaining why it fails to vectorize:
        LV: Checking a loop in "_Z6Queensi" from A_DFS_last_level_wo_rec.cpp
        LV: Loop hints: force=? width=16 unroll=0
        LV: Found a loop: for.body
        LV: PHI is not a poly recurrence.
        LV: PHI is not a poly recurrence.
        LV: Found an unidentified PHI.  %2 = phi i32 [ 0, %for.body.lr.ph ], [ %4, %for.inc ]
        LV: Can't vectorize the instructions or CFG
        LV: Not vectorizing: Cannot prove legality.

   This was obtained with the latest LLVM - SVN rev 334367, from Jun 10 2018.

   Could you please tell me why do you think LoopVectorize is not being able to vectorize
the above C code.


   BTW, I was hoping that LoopVectorize can change the code to be amenable to simple
if-conversion like the following C code manually transformed:
       void Func_manually_transformed(int N) {
         int numSol = 0;
         for (int c = 0; c < N; c++) {
             if (colOccupied[c] == 0)
                 select[c] = 1;
             else
                 select[c] = 0;
             numSol += select[c];
         }
         return numSol;
       }
     Note that this manually transformed code is being vectorized by LLVM.

   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 code with condition on reduction

div code via llvm-dev
Hi,

On 11/06/2018 10:40, Alex Susu via llvm-dev wrote:

>    Hello.
>      I'm not able to vectorize this simple C loop doing basically what
> could be called predicated sum-reduction:
>        #define NMAX 1000
>        int colOccupied[NMAX];
>        void Func(int N) {
>          int numSol = 0;
>          for (int c = 0; c < N; c++) {
>              if (colOccupied[c] == 0)
>                  numSol++;
>          }
>          return numSol;
>        }
>
>      The compiler command I used was:
>          clang -O3 -emit-llvm -S -mllvm -debug -ffast-math A.cpp
> -fvectorize -mllvm -force-vector-width=16
>
>      Following is the output of LLVM's opt explaining why it fails to
> vectorize:
>         LV: Checking a loop in "_Z6Queensi" from
> A_DFS_last_level_wo_rec.cpp
>         LV: Loop hints: force=? width=16 unroll=0
>         LV: Found a loop: for.body
>         LV: PHI is not a poly recurrence.
>         LV: PHI is not a poly recurrence.
>         LV: Found an unidentified PHI.  %2 = phi i32 [ 0,
> %for.body.lr.ph ], [ %4, %for.inc ]
>         LV: Can't vectorize the instructions or CFG
>         LV: Not vectorizing: Cannot prove legality.
>
>    This was obtained with the latest LLVM - SVN rev 334367, from Jun 10
> 2018.
>
>    Could you please tell me why do you think LoopVectorize is not being
> able to vectorize the above C code.
>

For me, a recent build of LLVM/Clang vectorizes the loop in Func on X86.
The debug output you posted indicates that the loop comes from function
called Queens. Is this the same function/loop as in Func?

Cheers,
Florian
_______________________________________________
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 code with condition on reduction

div code via llvm-dev
   Hi, Florian,
     Yes, I've posted the right output - the small inadvertence is insignificant - the
name of the function is really Func() and not Queens() - sorry for the "typo".

     I'm really surprised LLVM is able to vectorize for you - are you maybe using a
different loop vectorizer (maybe RV, which I understand it's able to vectorize such loops)
instead of LLVM's LoopVectorize+VPlan? Can you maybe post the debug output of opt when it
says it vectorizes the loop in the Func (not the Func_manually_transformed) function.

   Thank you,
     Alex

On 6/11/2018 12:53 PM, Florian Hahn wrote:

> Hi,
>
> On 11/06/2018 10:40, Alex Susu via llvm-dev wrote:
>>    Hello.
>>      I'm not able to vectorize this simple C loop doing basically what could be called
>> predicated sum-reduction:
>>        #define NMAX 1000
>>        int colOccupied[NMAX];
>>        void Func(int N) {
>>          int numSol = 0;
>>          for (int c = 0; c < N; c++) {
>>              if (colOccupied[c] == 0)
>>                  numSol++;
>>          }
>>          return numSol;
>>        }
>>
>>      The compiler command I used was:
>>          clang -O3 -emit-llvm -S -mllvm -debug -ffast-math A.cpp -fvectorize -mllvm
>> -force-vector-width=16
>>
>>      Following is the output of LLVM's opt explaining why it fails to vectorize:
>>         LV: Checking a loop in "_Z6Funci" from A_DFS_last_level_wo_rec.cpp
>>         LV: Loop hints: force=? width=16 unroll=0
>>         LV: Found a loop: for.body
>>         LV: PHI is not a poly recurrence.
>>         LV: PHI is not a poly recurrence.
>>         LV: Found an unidentified PHI.  %2 = phi i32 [ 0, %for.body.lr.ph ], [ %4,
>> %for.inc ]
>>         LV: Can't vectorize the instructions or CFG
>>         LV: Not vectorizing: Cannot prove legality.
>>
>>    This was obtained with the latest LLVM - SVN rev 334367, from Jun 10 2018.
>>
>>    Could you please tell me why do you think LoopVectorize is not being able to
>> vectorize the above C code.
>>
>
> For me, a recent build of LLVM/Clang vectorizes the loop in Func on X86. The debug output
> you posted indicates that the loop comes from function called Queens. Is this the same
> function/loop as in Func?
>
> Cheers,
> Florian
>
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev