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

[Sanjoy Das]

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