[LLVMdev] scev questions

[Nick Lewycky]

On 22 August 2013 13:24, Redmond, Paul <paul.redmond at intel.com> wrote:

> Hi,
>
> I'm trying to get the following loop to vectorize (simple reduction):
>
> unsigned int sum2(unsigned int *a, int len){
>   unsigned int s = 0;
>   for (int i = 0; i < len; i += 4)
>     s += *a++;
>   return s;
> }
>
>
> The loop fails to vectorize because SCEV could not compute the loop exit
> count. It appears SCEV cannot handle the non-unit increment of the loop
> counter. Is this a known limitation of SCEV or is there something that can
> be improved (and if so where should I start looking?)
>

It's a known limitation, see ScalarEvolution.cpp:5568.

The fundamental problem is that len in your example could be (unsigned) -1,
-2 or -3, in which case your loop is infinite.

Nick


> Here's the IR for the loop and the SCEV dump:
>
> for.body:                                         ; preds =
> %for.body.lr.ph, %for.body
>   %i.07 = phi i32 [ 0, %for.body.lr.ph ], [ %add1, %for.body ]
>   %s.06 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
>   %a.addr.05 = phi i32* [ %a, %for.body.lr.ph ], [ %incdec.ptr, %for.body
> ]
>   %incdec.ptr = getelementptr inbounds i32* %a.addr.05, i64 1
>   %0 = load i32* %a.addr.05, align 4, !tbaa !0
>   %add = add i32 %0, %s.06
>   %add1 = add nsw i32 %i.07, 4
>   %cmp = icmp slt i32 %add1, %len
>   br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
>
>
> Classifying expressions for: @_Z4sum2Pji
> %i.07 = phi i32 [ 0, %for.body.lr.ph ], [ %add1, %for.body ]
> --> {0,+,4}<nuw><nsw><%for.body>         Exits: <<Unknown>>
> %s.06 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
> --> %s.06        Exits: <<Unknown>>
> %a.addr.05 = phi i32* [ %a, %for.body.lr.ph ], [ %incdec.ptr, %for.body ]
> --> {%a,+,4}<nw><%for.body>      Exits: <<Unknown>>
> %incdec.ptr = getelementptr inbounds i32* %a.addr.05, i64 1
> --> {(4 + %a),+,4}<nw><%for.body>        Exits: <<Unknown>>
> %0 = load i32* %a.addr.05, align 4, !tbaa !0
> --> %0   Exits: <<Unknown>>
> %add = add i32 %0, %s.06
> --> (%0 + %s.06)         Exits: <<Unknown>>
> %add1 = add nsw i32 %i.07, 4
> --> {4,+,4}<nuw><nsw><%for.body>         Exits: <<Unknown>>
> %add.lcssa = phi i32 [ %add, %for.body ]
> --> %add.lcssa
> %s.0.lcssa = phi i32 [ %add.lcssa, %for.cond.for.end_crit_edge ], [ 0,
> %entry ]
> --> %s.0.lcssa
> Determining loop execution counts for: @_Z4sum2Pji
> Loop %for.body: Unpredictable backedge-taken count.
> Loop %for.body: Unpredictable max backedge-taken count.
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/3dff4ced/attachment.html>