[LLVMdev] confusion w.r.t. scalar evolution and nuw

[David Majnemer]

Seems like it's a bug.

We are permitted to turn 'sub nsw i32 %x, 1' into 'add nsw i32 %x, -1'

We are *not* permitted to turn 'sub nuw i32 %x, 1' into 'add nuw i32 %x, -1'

I don't think we are permitted to keep the nuw in your example.  We would
need something like SCEVSubRecExpr to be able to notionally represent that.



On Wed, Jan 14, 2015 at 8:05 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> I've been doing some digging in this area (scev, wrapping arithmetic),
> learning as much as I can, and have reached a point where I'm fairly
> confused about the semantics of nuw in scalar evolution expressions.
> Consider the following program:
>
> define void @foo(i32 %begin) {
>  entry:
>   br label %loop
>
>  loop:
>   %idx = phi i32 [ %begin, %entry ], [ %idx.dec, %loop ]
>   %idx.dec = sub nuw i32 %idx, 1
>   %exit.condition = icmp eq i32 %idx.dec, 0
>   br i1 %exit.condition, label %loop.exit, label %loop
>
>  loop.exit:
>   ret void
> }
>
> As long as %begin is positive, %idx.dec is not poison and the function
> has defined behavior.
>
> When I run opt -analyze -scalar-evolution on the IR, I get
>
> Printing analysis 'Scalar Evolution Analysis' for function 'foo':
> Classifying expressions for: @foo
>   %idx = phi i32 [ %begin, %entry ], [ %idx.dec, %loop ]
>   -->  {%begin,+,-1}<nuw><%loop>                Exits: 1
>   %idx.dec = sub nuw i32 %idx, 1
>   -->  {(-1 + %begin),+,-1}<nuw><%loop>         Exits: 0
> Determining loop execution counts for: @foo
> Loop %loop: backedge-taken count is (-1 + %begin)
> Loop %loop: max backedge-taken count is -1
>
> SCEV has mapped `%idx.dec' to `{(-1 + %begin),+,-1}<nuw>'!  This means
> SCEV thinks `%idx.dec' will be poison in the very first iteration if
> %begin is ult 1.
>
> As an example on how this could blow up, if %begin was constant
> (or LLVM was got smarter about ranges someday and learned to handle
> non-constant ranges) in ScalarEvolution::getUnsignedRange, the
> following code could fire:
>
>   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
>     // If there's no unsigned wrap, the value will never be less than its
>     // initial value.
>     if (AddRec->getNoWrapFlags(SCEV::FlagNUW))
>       if (const SCEVConstant *C =
> dyn_cast<SCEVConstant>(AddRec->getStart()))
>         if (!C->getValue()->isZero())
>           ConservativeResult =
>             ConservativeResult.intersectWith(
>               ConstantRange(C->getValue()->getValue(), APInt(BitWidth,
> 0)));
>
> and conclude that %idx.dec is always UGE %begin.  This is a real bug
> waiting to happen.
>
> As far as I can tell, in the presence of no-wrap flags, 'sub X Y' is
> not the same as 'add X -Y', and subtractions can be expressed as
> additions only if they don't have any no-wrap flags on them.  While
> I have not thought about nsw in depth, but it is possible there are
> similar issues with nsw as well.
>
> Is my reasoning broken at some point?  What gives?
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150114/408370e8/attachment.html>