Fix bug 22641

[sanjoy]

Summary

Fix bug 22641 by partially reinstating the original change for D7331.

Point to note: 22641 is _not_ caused by SCEV "forgetting" control flow. PreAR is marked as nuw by SCEV itself when it sees that Start + BECount * Step won't overflow for PreAR (since BECount is 0).

[atrick]

Wow! Thank you Sanjoy. This is an awesome catch and these test cases are invaluable.

I think the most obvious bug here is my implicit assumption that the step is positive. So we're looking at a post-increment recurrence and calling it PreAR. Maybe we should have a comment about that?

That said, I think your proposed check makes sense:
!isa<SCEVCouldNotCompute>(BECount) && SE->isKnownPositive(BECount)

I like that better than checking the ExitingBlock. Sorry if you proposed that earlier and I directed you down the wrong path. At least we got a great test case out of it.

[sanjoy]

I think the most obvious bug here is my implicit assumption that the step is positive. So we're looking at a post-increment recurrence and calling it PreAR. Maybe we should have a comment about that?

I'm not sure if I understand you -- what does the sign (or
non-zeroness) of step have to do with this transform? From
AR={S+X,+,X} we constructed PreAR={S,+,X} so isn't PreAR the
pre-increment recurrence for AR irrespective of the sign of X?

• Sanjoy

[atrick]

You're right. The direction of the Step shouldn't matter. That was my code's original intention, and it looks like that's valid.

I asked that question because I thought the test case was failed when postinc recurrence was marked NUW but the preinc recurrence was not. Now I can see that *any* recurrence on this loop will be NUW. That may make sense in theory, but could cause some real practical problems within SCEV. It looks like you already caught one in SCEVExpander.

My main takeaway from this is that the recurrence's wrapping flags are a property of the pre-incremented value within the loop. So that IV increment may actually wrap on the last iteration. I've been making the assumption that the post-incremented value would be tested on the last iteration and was guaranteed not to wrap. That's slightly shady because the value might not actually be used (and isn't even "consumed" by a phi), but it seemed to be the expectation based on other code I'd seen.

Do you have a better explanation?

[sanjoy]

I asked that question because I thought the test case was failed when postinc recurrence was marked NUW but the preinc recurrence was not. Now I can see that *any* recurrence on this loop will be NUW. That may make sense in theory, but could cause some real practical problems within SCEV. It looks like you already caught one in SCEVExpander.

(fwiw, I had this exact same discussion with Philip a few hours ago).

This is very similar to the discussion we had w.r.t. the <nw> flag.
Given that the algebraic condition that decides if a recurrence is
<nw> is satisfied by BECount == 0, all recurrences in a loop that
never takes a backedge are trivially <nw>. The same is true for <nuw>
and <nsw>, as far as I can tell.

My main takeaway from this is that the recurrence's wrapping flags are a property of the pre-incremented value within the loop. So that IV increment may actually wrap on the last iteration. I've been making the assumption that the post-incremented value would be tested on the last iteration and was guaranteed not to wrap. That's slightly shady because the value might not actually be used (and isn't even "consumed" by a phi), but it seemed to be the expectation based on other code I'd seen.

I agree; that is my mental model also -- the "next" value of a SCEV is
computed as loop takes the backedge, and that is when all the nuw,
nsw, nw flags apply. In this sense, add recs have a very structured
form of control dependence.

Unless we allow this, we won't be able to mark add recs as nuw/nsw/nw
for loops with variable trip count. I also don't think this is very
problematic (though a little subtle, I'll have to admit) -- we just
have be very explicit that the no-wrap flags on a add rec are valid
for that scev only; and do not apply to the pre-inc or post-inc
version of that scev. So sext({S,+,X}<nsw>) is still {sext S,+,sext
X} and {S,+,1}<nsw> is still always sge 1. {S,+,X}+X == {S+X,+,X} is
a totally different scev and the no-wrap behavior of the former does
not apply to the latter.

Does this sound sensible?

I'll check in a change that adds some more elaborate comments
detailing whatever we decide once we've reached a fixed point.

• Sanjoy

Do you have a better explanation?

http://reviews.llvm.org/D7808

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

if (SE.getAddExpr(Requested->getStart(),
                     SE.getNegativeSCEV(Requested)) == Phi) {
     InvertStep = true;
     return true;
   }
 
   return false;
 }
 
+static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
+  if (!isa<IntegerType>(AR->getType()))
+    return false;
+
+  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
+  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
+  const SCEV *Step = AR->getStepRecurrence(SE);
+  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
+                                            SE.getSignExtendExpr(AR, WideTy));
+  const SCEV *ExtendAfterOp =
+    SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
+  return ExtendAfterOp == OpAfterExtend;
+}
+
+static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
+  if (!isa<IntegerType>(AR->getType()))
+    return false;
+
+  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
+  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
+  const SCEV *Step = AR->getStepRecurrence(SE);
+  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
+                                            SE.getZeroExtendExpr(AR, WideTy));
+  const SCEV *ExtendAfterOp =
+    SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
+  return ExtendAfterOp == OpAfterExtend;
+}
+
 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
 /// the base addrec, which is the addrec without any non-loop-dominating
 /// values, and return the PHI.
 PHINode *
 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
                                         const Loop *L,
                                         Type *ExpandTy,
                                         Type *IntTy,
for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
 
     // Create a step value and add it to the PHI.
     // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
     // instructions at IVIncInsertPos.
     Instruction *InsertPos = L == IVIncInsertLoop ?
       IVIncInsertPos : Pred->getTerminator();
     Builder.SetInsertPoint(InsertPos);
     Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
+
     if (isa<OverflowingBinaryOperator>(IncV)) {
-      if (Normalized->getNoWrapFlags(SCEV::FlagNUW))
+      if (IsIncrementNUW(SE, Normalized))
         cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
-      if (Normalized->getNoWrapFlags(SCEV::FlagNSW))
+      if (IsIncrementNSW(SE, Normalized))
         cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
     }
     PN->addIncoming(IncV, Pred);
   }
 
   // After expanding subexpressions, restore the PostIncLoops set so the caller
   // can ensure that IVIncrement dominates the current uses.
   PostIncLoops = SavedPostIncLoops;

llvm/trunk/test/Analysis/ScalarEvolution/scev-expander-incorrect-nowrap.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+declare void @use(i32)
+declare void @use.i8(i8)
+
+define void @f() {
+; CHECK-LABEL: @f
+ entry:
+  br label %loop
+
+ loop:
+; The only use for idx.mirror is to induce an nuw for %idx.  It does
+; not induce an nuw for %idx.inc
+  %idx.mirror = phi i8 [ -6, %entry ], [ %idx.mirror.inc, %loop ]
+  %idx = phi i8 [ -5, %entry ], [ %idx.inc, %loop ]
+
+  %idx.sext = sext i8 %idx to i32
+  call void @use(i32 %idx.sext)
+
+  %idx.mirror.inc = add nuw i8 %idx.mirror, 1
+  call void @use.i8(i8 %idx.mirror.inc)
+
+  %idx.inc = add i8 %idx, 1
+; CHECK-NOT: %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
+  %cmp = icmp ugt i8 %idx.inc, 0
+  br i1 %cmp, label %loop, label %exit
+
+ exit:
+  ret void
+}

llvm/trunk/test/Analysis/ScalarEvolution/zext-signed-addrec.ll

 ; CHECK: %lsr.iv = phi i32 [ %lsr.iv.next, %if.end ], [ 258, %for.cond1.preheader.for.cond1.preheader.split_crit_edge ]
   %indvars.iv = phi i32 [ 1, %for.cond1.preheader.for.cond1.preheader.split_crit_edge ], [ %indvars.iv.next, %if.end ]
 
   %2 = phi i8 [ 1, %for.cond1.preheader.for.cond1.preheader.split_crit_edge ], [ %dec, %if.end ]
   %conv7 = mul i32 %indvars.iv, 258
   %shl = and i32 %conv7, 510
   store i32 %shl, i32* @c, align 4
 
-; CHECK: %lsr.iv.next = add i32 %lsr.iv, -258
+; CHECK: %lsr.iv.next = add nsw i32 %lsr.iv, -258
   %dec = add i8 %2, -1
 
   %cmp2 = icmp sgt i8 %dec, -1
   %indvars.iv.next = add i32 %indvars.iv, -1
   br i1 %cmp2, label %if.end, label %for.inc8
 
 for.inc8:                                         ; preds = %if.end
   store i32 0, i32* @d, align 4

llvm/trunk/test/CodeGen/AArch64/arm64-scaled_iv.ll

 ; CHECK: [[IV:%[^ ]+]] = phi i64 [ [[IVNEXT:%[^,]+]], %for.body ], [ 0, %entry ]
 ; Only one induction variable should have been generated.
 ; CHECK-NOT: phi
   %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
   %tmp = add nsw i64 %indvars.iv, -1
   %arrayidx = getelementptr inbounds double* %b, i64 %tmp
   %tmp1 = load double* %arrayidx, align 8
 ; The induction variable should carry the scaling factor: 1 * 8 = 8.
-; CHECK: [[IVNEXT]] = add nuw i64 [[IV]], 8
+; CHECK: [[IVNEXT]] = add nuw nsw i64 [[IV]], 8
   %indvars.iv.next = add i64 %indvars.iv, 1
   %arrayidx2 = getelementptr inbounds double* %c, i64 %indvars.iv.next
   %tmp2 = load double* %arrayidx2, align 8
   %mul = fmul double %tmp1, %tmp2
   %arrayidx4 = getelementptr inbounds double* %a, i64 %indvars.iv
   store double %mul, double* %arrayidx4, align 8
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 ; Comparison should be 19 * 8 = 152.
 ; CHECK: icmp eq i32 {{%[^,]+}}, 152
   %exitcond = icmp eq i32 %lftr.wideiv, 20
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

llvm/trunk/test/CodeGen/X86/avoid_complex_am.ll

 ; CHECK: [[IV:%[^ ]+]] = phi i64 [ [[IVNEXT:%[^,]+]], %for.body ], [ 0, %entry ]
 ; Only one induction variable should have been generated.
 ; CHECK-NOT: phi
   %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
   %tmp = add nsw i64 %indvars.iv, -1
   %arrayidx = getelementptr inbounds double* %b, i64 %tmp
   %tmp1 = load double* %arrayidx, align 8
 ; The induction variable should carry the scaling factor: 1.
-; CHECK: [[IVNEXT]] = add nuw i64 [[IV]], 1
+; CHECK: [[IVNEXT]] = add nuw nsw i64 [[IV]], 1
   %indvars.iv.next = add i64 %indvars.iv, 1
   %arrayidx2 = getelementptr inbounds double* %c, i64 %indvars.iv.next
   %tmp2 = load double* %arrayidx2, align 8
   %mul = fmul double %tmp1, %tmp2
   %arrayidx4 = getelementptr inbounds double* %a, i64 %indvars.iv
   store double %mul, double* %arrayidx4, align 8
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 ; Comparison should be 19 * 1 = 19.
 ; CHECK: icmp eq i32 {{%[^,]+}}, 19
   %exitcond = icmp eq i32 %lftr.wideiv, 20
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

llvm/trunk/test/Transforms/IndVarSimplify/overflowcheck.ll

 ; RUN: opt < %s -indvars -liv-reduce -S | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx"
 
 ; CHECK-LABEL: @addwithoverflow
 ; CHECK-LABEL: loop1:
 ; CHECK-NOT: zext
 ; CHECK: add nsw
 ; CHECK: @llvm.sadd.with.overflow
 ; CHECK-LABEL: loop2:
 ; CHECK-NOT: extractvalue
-; CHECK: add nuw nsw
+; CHECK: add nuw
 ; CHECK: @llvm.sadd.with.overflow
 ; CHECK-LABEL: loop3:
 ; CHECK-NOT: extractvalue
 ; CHECK: ret
 define i64 @addwithoverflow(i32 %n, i64* %a) {
 entry:
   br label %loop0
 

llvm/trunk/test/Transforms/IndVarSimplify/pr20680.ll

for.cond2.for.inc13_crit_edge.us-lcssa:           ; preds = %for.cond2.for.inc13_crit_edge.us-lcssa.us-lcssa, %for.cond2.for.inc13_crit_edge.us-lcssa.us-lcssa.us
   br label %for.cond2.for.inc13_crit_edge
 
 for.cond2.for.inc13_crit_edge:                    ; preds = %for.cond2.for.inc13_crit_edge.us-lcssa, %for.cond2.for.inc13_crit_edge.us-lcssa.us
   %cond.lcssa = phi i32 [ %cond.lcssa.ph, %for.cond2.for.inc13_crit_edge.us-lcssa ], [ %cond.lcssa.ph.us, %for.cond2.for.inc13_crit_edge.us-lcssa.us ]
   store i32 %cond.lcssa, i32* @c, align 4
   br label %for.inc13
 
 ; CHECK: [[for_inc13]]:
-; CHECK-NEXT: %[[indvars_iv_next]] = add nuw nsw i32 %[[indvars_iv]], 1
-; CHECK-NEXT: %[[exitcond4:.*]] = icmp ne i32 %[[indvars_iv]], -1
+; CHECK-NEXT: %[[indvars_iv_next]] = add nsw i32 %[[indvars_iv]], 1
+; CHECK-NEXT: %[[exitcond4:.*]] = icmp ne i32 %[[indvars_iv_next]], 0
 ; CHECK-NEXT: br i1 %[[exitcond4]], label %[[for_cond2_preheader]], label %[[for_end15:.*]]
 for.inc13:                                        ; preds = %for.cond2.for.inc13_crit_edge, %for.cond2.preheader
   %inc14 = add i8 %storemerge15, 1
   %cmp = icmp ugt i8 %inc14, 50
   br i1 %cmp, label %for.cond2.preheader, label %for.end15
 
 ; CHECK: [[for_end15]]:
 ; CHECK-NEXT: ret void
 for.end15:                                        ; preds = %for.inc13
   ret void
 }

llvm/trunk/test/Transforms/LoopStrengthReduce/count-to-zero.ll

bb2:                                              ; preds = %bb1
   br label %bb7
 
 bb3:                                              ; preds = %bb1
   %tmp2 = icmp slt i32 %c_addr.1, 10              ; <i1> [#uses=1]
   %tmp3 = add nsw i32 %c_addr.1, 1                ; <i32> [#uses=1]
   %tmp4 = add i32 %c_addr.1, -1                   ; <i32> [#uses=1]
   %c_addr.1.be = select i1 %tmp2, i32 %tmp3, i32 %tmp4 ; <i32> [#uses=1]
   %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=1]
-; CHECK: add i32 %lsr.iv, -1
+; CHECK: add nsw i32 %lsr.iv, -1
   br label %bb6
 
 bb6:                                              ; preds = %bb3, %entry
   %indvar = phi i32 [ %indvar.next, %bb3 ], [ 0, %entry ] ; <i32> [#uses=2]
   %c_addr.1 = phi i32 [ %c_addr.1.be, %bb3 ], [ %c, %entry ] ; <i32> [#uses=7]
   %tmp5 = icmp eq i32 %indvar, 9999               ; <i1> [#uses=1]
 ; CHECK: icmp eq i32 %lsr.iv, 0
   %tmp6 = icmp eq i32 %c_addr.1, 100              ; <i1> [#uses=1]

llvm/trunk/test/Transforms/LoopStrengthReduce/uglygep.ll

 define fastcc void @TransformLine() nounwind {
 ; CHECK-LABEL: @TransformLine(
 bb:
   br label %loop0
 
 ; CHECK: loop0:
 ; Induction variable is initialized to -2.
 ; CHECK-NEXT: [[PHIIV:%[^ ]+]] = phi i32 [ [[IVNEXT:%[^ ]+]], %loop0 ], [ -2, %bb ]
-; CHECK-NEXT: [[IVNEXT]] = add i32 [[PHIIV]], 1
+; CHECK-NEXT: [[IVNEXT]] = add nuw nsw i32 [[PHIIV]], 1
 ; CHECK-NEXT: br i1 false, label %loop0, label %bb0
 loop0:                                            ; preds = %loop0, %bb
   %i0 = phi i32 [ %i0.next, %loop0 ], [ 0, %bb ]  ; <i32> [#uses=2]
   %i0.next = add i32 %i0, 1                       ; <i32> [#uses=1]
   br i1 false, label %loop0, label %bb0
 
 bb0:                                              ; preds = %loop0
   br label %loop1