[llvm-dev] [SCEV] Why is backedge-taken count <nsw> instead of <nuw>?

[Friedman, Eli via llvm-dev]

On 8/15/2018 12:21 PM, Alexandre Isoard via llvm-dev wrote:
> Hello,
>
> If I run clang on the following code:
>
>     void func(unsigned n) {
>       for (unsigned long x = 1; x < n; ++x)
>         dummy(x);
>     }
>
>
> I get the following llvm ir:
>
>     define void @func(i32 %n) {
>     entry:
>       %conv = zext i32 %n to i64
>       %cmp5 = icmp ugt i32 %n, 1
>       br i1 %cmp5, label %for.body, label %for.cond.cleanup
>     for.cond.cleanup:                                 ; preds =
>     %for.body, %entry
>       ret void
>     for.body:                                         ; preds =
>     %entry, %for.body
>       %x.06 = phi i64 [ %inc, %for.body ], [ 1, %entry ]
>       tail call void @dummy(i64 %x.06) #2
>       %inc = add nuw nsw i64 %x.06, 1
>       %exitcond = icmp eq i64 %inc, %conv
>       br i1 %exitcond, label %for.cond.cleanup, label %for.body
>     }
>
>
> Over which, SCEV will provide the following analysis:
>
>     Printing analysis 'Scalar Evolution Analysis' for function 'func':
>     Classifying expressions for: @func
>       %conv = zext i32 %n to i64
>       -->  (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)
>       %x.06 = phi i64 [ %inc, %for.body ], [ 1, %entry ]
>       -->  {1,+,1}<nuw><nsw><%for.body> U: [1,-9223372036854775808) S:
>     [1,-9223372036854775808)Exits: (-1 + (zext i32 %n to
>     i64))LoopDispositions: { %for.body: Computable }
>       %inc = add nuw nsw i64 %x.06, 1
>       -->  {2,+,1}<nuw><%for.body> U: [2,0) S: [2,0)Exits: (zext i32
>     %n to i64)LoopDispositions: { %for.body: Computable }
>     Determining loop execution counts for: @func
>     Loop %for.body: backedge-taken count is (-2 + (zext i32 %n to
>     i64))<nsw>
>     Loop %for.body: max backedge-taken count is -2
>     Loop %for.body: Predicated backedge-taken count is (-2 + (zext i32
>     %n to i64))<nsw>
>      Predicates:
>     Loop %for.body: Trip multiple is 1
>
>
> Now, I was surprised by the max backedge-taken count being -2, and I 
> suspect it is due to the backedge-taken count being marked as <nsw> 
> instead of <nuw>.
>
> Is that on purpose, is that a bug, or is my analysis incorrect? I am 
> not sure where to fix that issue.

The backedge-taken count isn't nuw because nsw/nuw markings aren't 
flow-sensitive: there isn't any way to mark the trip count as nuw 
without marking every computation of `(long)n-2` as nuw.

There's some code in ScalarEvolution::howFarToZero to try to refine the 
max backedge-taken count in some cases, but it isn't very general.  See 
https://reviews.llvm.org/D28536 .

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180815/0bbf8df3/attachment.html>