<div dir="ltr">Seems like it's a bug.<div><br></div><div>We are permitted to turn 'sub nsw i32 %x, 1' into 'add nsw i32 %x, -1'</div><div><br></div><div>We are *not* permitted to turn 'sub nuw i32 %x, 1' into 'add nuw i32 %x, -1'</div><div><br></div><div>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.</div><div><br></div><div><br></div>















<div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 14, 2015 at 8:05 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">I've been doing some digging in this area (scev, wrapping arithmetic),<br>
learning as much as I can, and have reached a point where I'm fairly<br>
confused about the semantics of nuw in scalar evolution expressions.<br>
Consider the following program:<br>
<br>
define void @foo(i32 %begin) {<br>
 entry:<br>
  br label %loop<br>
<br>
 loop:<br>
  %idx = phi i32 [ %begin, %entry ], [ %idx.dec, %loop ]<br>
  %idx.dec = sub nuw i32 %idx, 1<br>
  %exit.condition = icmp eq i32 %idx.dec, 0<br>
  br i1 %exit.condition, label %loop.exit, label %loop<br>
<br>
 loop.exit:<br>
  ret void<br>
}<br>
<br>
As long as %begin is positive, %idx.dec is not poison and the function<br>
has defined behavior.<br>
<br>
When I run opt -analyze -scalar-evolution on the IR, I get<br>
<br>
Printing analysis 'Scalar Evolution Analysis' for function 'foo':<br>
Classifying expressions for: @foo<br>
  %idx = phi i32 [ %begin, %entry ], [ %idx.dec, %loop ]<br>
  -->  {%begin,+,-1}<nuw><%loop>                Exits: 1<br>
  %idx.dec = sub nuw i32 %idx, 1<br>
  -->  {(-1 + %begin),+,-1}<nuw><%loop>         Exits: 0<br>
Determining loop execution counts for: @foo<br>
Loop %loop: backedge-taken count is (-1 + %begin)<br>
Loop %loop: max backedge-taken count is -1<br>
<br>
SCEV has mapped `%idx.dec' to `{(-1 + %begin),+,-1}<nuw>'!  This means<br>
SCEV thinks `%idx.dec' will be poison in the very first iteration if<br>
%begin is ult 1.<br>
<br>
As an example on how this could blow up, if %begin was constant<br>
(or LLVM was got smarter about ranges someday and learned to handle<br>
non-constant ranges) in ScalarEvolution::getUnsignedRange, the<br>
following code could fire:<br>
<br>
  if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {<br>
    // If there's no unsigned wrap, the value will never be less than its<br>
    // initial value.<br>
    if (AddRec->getNoWrapFlags(SCEV::FlagNUW))<br>
      if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))<br>
        if (!C->getValue()->isZero())<br>
          ConservativeResult =<br>
            ConservativeResult.intersectWith(<br>
              ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0)));<br>
<br>
and conclude that %idx.dec is always UGE %begin.  This is a real bug<br>
waiting to happen.<br>
<br>
As far as I can tell, in the presence of no-wrap flags, 'sub X Y' is<br>
not the same as 'add X -Y', and subtractions can be expressed as<br>
additions only if they don't have any no-wrap flags on them.  While<br>
I have not thought about nsw in depth, but it is possible there are<br>
similar issues with nsw as well.<br>
<br>
Is my reasoning broken at some point?  What gives?<br>
<span><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>