Fix bug 22641

The bug was a result of getPreStartForExtend interpreting nsw/nuw
flags on an add recurrence more strongly than is legal.  {S,+,X}<nsw>
implies S+X is nsw only if the backedge of the loop is taken at least
once.

Differential Revision: http://reviews.llvm.org/D7808

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@230275 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 59f19a002eccc9fc4a51106a1a71afdf8a9eae06..ef9557132fcf29b2376d201f723061f5a4885af6 100644 (file)
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1063,6 +1063,34 @@ static bool canBeCheaplyTransformed(ScalarEvolution &SE,
   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.
@@ -1213,10 +1241,11 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
       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);

diff --git a/test/Analysis/ScalarEvolution/scev-expander-incorrect-nowrap.ll b/test/Analysis/ScalarEvolution/scev-expander-incorrect-nowrap.ll
new file mode 100644 (file)
index 0000000..012cad7
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/scev-expander-incorrect-nowrap.ll
@@ -0,0 +1,30 @@
+; 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
+}

diff --git a/test/Analysis/ScalarEvolution/zext-signed-addrec.ll b/test/Analysis/ScalarEvolution/zext-signed-addrec.ll
index 27aed3b0da1b33a9d8577b19cc5803c64e91c793..43698204a722ab9623f2b7674b4cd80005dad0e3 100644 (file)
--- a/test/Analysis/ScalarEvolution/zext-signed-addrec.ll
+++ b/test/Analysis/ScalarEvolution/zext-signed-addrec.ll
@@ -43,7 +43,7 @@ if.end:                                           ; preds = %if.end, %for.cond1.
   %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

diff --git a/test/CodeGen/AArch64/arm64-scaled_iv.ll b/test/CodeGen/AArch64/arm64-scaled_iv.ll
index 63428df9610c6cbb575a4dd035188abe15f19673..987373e542afbebf926f0d69d749d5f0a9655da2 100644 (file)
--- a/test/CodeGen/AArch64/arm64-scaled_iv.ll
+++ b/test/CodeGen/AArch64/arm64-scaled_iv.ll
@@ -20,7 +20,7 @@ for.body:                                         ; preds = %for.body, %entry
   %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

diff --git a/test/CodeGen/X86/avoid_complex_am.ll b/test/CodeGen/X86/avoid_complex_am.ll
index e5e7bd23a641edea8720ab34df47661fbc48e0c7..7f095190ab8f8132f7a1e338b8c258ca65e46817 100644 (file)
--- a/test/CodeGen/X86/avoid_complex_am.ll
+++ b/test/CodeGen/X86/avoid_complex_am.ll
@@ -22,7 +22,7 @@ for.body:                                         ; preds = %for.body, %entry
   %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

diff --git a/test/Transforms/IndVarSimplify/overflowcheck.ll b/test/Transforms/IndVarSimplify/overflowcheck.ll
index 2603f363ab6064a4d2cbe73ce89e2fdff596d982..3864c6c0cfbbd0bdfe1c341c20131118f3c7a5ba 100644 (file)
--- a/test/Transforms/IndVarSimplify/overflowcheck.ll
+++ b/test/Transforms/IndVarSimplify/overflowcheck.ll
@@ -9,7 +9,7 @@ target triple = "x86_64-apple-macosx"
 ; 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

diff --git a/test/Transforms/IndVarSimplify/pr20680.ll b/test/Transforms/IndVarSimplify/pr20680.ll
index 88a7fd765d0bd68fe40cb74640f552f8ad902c9a..716e013603a3ef60710cd4eb468424eba05131a1 100644 (file)
--- a/test/Transforms/IndVarSimplify/pr20680.ll
+++ b/test/Transforms/IndVarSimplify/pr20680.ll
@@ -204,8 +204,8 @@ for.cond2.for.inc13_crit_edge:                    ; preds = %for.cond2.for.inc13
   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

diff --git a/test/Transforms/LoopStrengthReduce/count-to-zero.ll b/test/Transforms/LoopStrengthReduce/count-to-zero.ll
index feb79f8a0c71bfe816fdfc18b574de33213c043c..0e96f02904d91ad067b145b12bd981237d48039b 100644 (file)
--- a/test/Transforms/LoopStrengthReduce/count-to-zero.ll
+++ b/test/Transforms/LoopStrengthReduce/count-to-zero.ll
@@ -19,7 +19,7 @@ bb3:                                              ; preds = %bb1
   %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

diff --git a/test/Transforms/LoopStrengthReduce/uglygep.ll b/test/Transforms/LoopStrengthReduce/uglygep.ll
index 4562d29a0a20b5fce47c689cccaeb49328285d6f..515508734159f61b236ba8c03ea14696a561c1ba 100644 (file)
--- a/test/Transforms/LoopStrengthReduce/uglygep.ll
+++ b/test/Transforms/LoopStrengthReduce/uglygep.ll
@@ -59,7 +59,7 @@ bb:
 ; 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]