SCEVExpander incorrectly marks increment operations as no-wrap

[sanjoy]

Summary

When emitting the increment operation, SCEVExpander marks the
operation as nuw or nsw based on the flags on the preincrement SCEV.
This is incorrect because, for instance, it is possible that {-6,+,1}
is <nuw> while {-6,+,1}+1 = {-5,+,1} is not.

This change teaches SCEV to mark the increment as nuw/nsw only if it
can explicitly prove that the increment operation won't overflow.

Apart from the attached test case, another (more realistic) manifestation
of the bug can be seen in Transforms/IndVarSimplify/pr20680.ll.

[atrick]

LGTM

[sanjoy]

Another related problem is with how SCEVExpander will sometimes emit
subtractions instead of additions. As you know, nuw and nsw flags
don't carry over from 'add X (-Y)' to 'sub X Y'. There are two
obvious ways out of this:

• don't generate subtractions
• if you do generate a subtraction, don't tag it with nuw/nsw even if

the addition is nuw/nsw.

The question I do not have the answer to is why SCEVExpander generates
subtractions at all. Is the a code-gen issue?

[atrick]

Sub X Y is the canonical form though, so what SCEVExpander does makes sense, particularly if it's trying to avoid emitting redundant instructions. But it's not very smart to throw away the nuw/nsw flags unless we know they can be inferred again later.

You're right that changing this could affect codegen. Probably only for fast-isel though, and only if InstCombine isn't going to be run. So it really only matters for LoopStrengthReduce, which probably won't be run with fast-isel.

SCEVExpander could have a mode that attempts to preserve flags, and a mode where it just always generates the sub. Or you can try to generate the sub whenever it doesn't lose the flags. However, I vote for keeping it simple and just always generating the add and letting InstCombine cleanup if it actually matters. You might then want to fix InstCombine so it doesn't convert to sub and drop the flags in these cases. (actually there should be a TargetInstCombine that drops the flags just before isel, but I digress).

Incidentally, are you more often relying on nsw/nuw to be inferred within SCEV, or are you relying more on your frontend to generate them in special situations?

[sanjoy]

SCEVExpander could have a mode that attempts to preserve flags, and a mode where it just always generates the sub. Or you can try to generate the sub whenever it doesn't lose the flags. However, I vote for keeping it simple and just always generating the add and letting InstCombine cleanup if it actually matters.

I agree -- I'll put up a patch for review shortly.

Incidentally, are you more often relying on nsw/nuw to be inferred within SCEV, or are you relying more on your frontend to generate them in special situations?

All Java-level integer arithmetic gets lowered into
potentially-wrapping operations, and it is up to scalar evolution to
prove when overflow does not happen.

Slight tangent: I noticed is that LFTR will not happen for a loop
with multiple exiting blocks. Most of the interesting loops we
generate have multiple exiting blocks due to range checks and null
checks, so this may yet be another area where we end up missing some
optimizations because of non-canonical IR.

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7778

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