[LLVMdev] Auto-vectorization and phi nodes

[Vesa Norilo]

Hi Nadav and Hal and thanks for the help!

To the best of my understanding, indvars doesn't complain and an 
induction variable is detected. However, the loop vectorizer says:

LV: Checking a loop in "add_vector"
LV: Found a loop: Loop
LV: Found an induction variable.
LV: Found an unidentified PHI.  %a.ptr = phi float* [ %a, %Top ], [ 
%a.next, %Loop ]
LV: Can't vectorize the instructions or CFG
LV: Not vectorizing.

Should indvars have changed this phi node into something else earlier 
during optimization?

In case I missed something important from the log, I put it all up here:
http://pastebin.com/yBS5RhVN

The IR fed into opt is at the end of the log, functionally unchanged. My 
command line is opt -S -O3 -vectorize-loops -force-vector-width=8 -debug

Thanks again!
Vesa


19.2.2013 19:22, Nadav Rotem kirjoitti:
> Hi Vesa,
>
> The pass IndVars changes the induction variables to allow SCEV to analyze them and enable other optimizations. This is the canonicalization phase.  Later on, LSR lowers the canonicalized induction variables to induction variables that map nicely to the target's addressing modes. In many cases it can remove some of the induction variables.
>
> I suspect that the loop vectorizer does not vectorize the code because SCEV fails to detect the induction variable.   Can you run the loop vectorizer with the '-debug' option and check why it fails ?
>
> Thanks,
> Nadav
>
>
> On Feb 19, 2013, at 7:51 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>> ----- Original Message -----
>>> From: "Vesa Norilo" <vnorilo at siba.fi>
>>> To: llvmdev at cs.uiuc.edu
>>> Sent: Tuesday, February 19, 2013 4:40:26 AM
>>> Subject: [LLVMdev] Auto-vectorization and phi nodes
>>>
>>> Hi all,
>>>
>>> Sorry if this is a dumb or FAQ or the wrong list!
>>>
>>> I'm currently investigating LLVM vectorization of my generated code.
>>> My
>>> codegen emits a lot of recursions that step through arrays via
>>> pointers.
>>> The recursions are nicely optimized into loops, but the loop
>>> vectorization can't seem to work on them because of phi nodes that
>>> point
>>> to gep nodes.
>>>
>>> Some simple IR to demonstrate; it vectorizes nicely with opt -O3
>>> -vectorize-loops -force-vector-width until I uncomment the phi/gep
>>> nodes.
>>>
>>> define void @add_vector(float* noalias %a, float* noalias %b, float*
>>> noalias %c, i32 %num)
>>> {
>>> Top:
>>>          br label %Loop
>>> Loop:
>>>          %i = phi i32 [0,%Top],[%i.next,%Loop]
>>>
>>> ;        phi and gep - won't vectorize
>>> ;        %a.ptr = phi float* [%a,%Top],[%a.next,%Loop]
>>> ;        %b.ptr = phi float* [%b,%Top],[%b.next,%Loop]
>>> ;        %c.ptr = phi float* [%c,%Top],[%c.next,%Loop]
>>>
>>> ;        %a.next = getelementptr float* %a.ptr, i32 1
>>> ;        %b.next = getelementptr    float* %b.ptr, i32 1
>>> ;        %c.next = getelementptr float* %c.ptr, i32 1
>>>
>>> ;        induction variable as index - will vectorize
>>>          %a.ptr = getelementptr float* %a, i32 %i
>>>          %b.ptr = getelementptr float* %b, i32 %i
>>>          %c.ptr = getelementptr float* %c, i32 %i
>>>
>>>          %a.val = load float* %a.ptr
>>>          %b.val = load float* %b.ptr
>>>          %sum = fadd float %a.val, %b.val
>>>          store float %sum, float* %c.ptr
>>>
>>>          %i.next = add i32 %i, 1
>>>          %more = icmp slt i32 %i.next, %num
>>>          br i1 %more, label %Loop, label %End
>>> End:
>>>          ret void
>>> }
>>>
>>> So it seems that the loop vectorizer would like the pointer stepping
>>> to
>>> be converted to base+index. However as expected, clang doesn't care
>>> whether C code is written as pointer arithmetic or table index.
>>>
>>> Is there a pass that converts simple pointer arithmetic to
>>> base+index?
>> As I recall, loop strength reduction can do this; but that happens only very late in the compilation process (well after vectorization). It would probably be better to update the loop vectorizer to deal with this directly. Nadav?
>>
>> -Hal
>>
>>> If not, should I write one (shouldn't be too hard for my limited use
>>> case) or try to emit more vector-friendly code from the front end?
>>>
>>> Thanks a bunch!
>>> Vesa Norilo
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>