From 8d16a81c331e641b12464d32a0c35d819ab1b5ee Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Mon, 23 Feb 2015 23:22:58 +0000 Subject: [PATCH] Bugfix: SCEVExpander incorrectly marks increment operations as no-wrap 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 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. NOTE: this change was landed with an incorrect commit message in rL230275 and was reverted for that reason in rL230279. This commit message is the correct one. Differential Revision: http://reviews.llvm.org/D7778 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@230280 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolutionExpander.cpp | 33 +++++++++++++++++-- .../scev-expander-incorrect-nowrap.ll | 30 +++++++++++++++++ .../ScalarEvolution/zext-signed-addrec.ll | 2 +- test/CodeGen/AArch64/arm64-scaled_iv.ll | 2 +- test/CodeGen/X86/avoid_complex_am.ll | 2 +- .../IndVarSimplify/overflowcheck.ll | 2 +- test/Transforms/IndVarSimplify/pr20680.ll | 4 +-- .../LoopStrengthReduce/count-to-zero.ll | 2 +- test/Transforms/LoopStrengthReduce/uglygep.ll | 2 +- 9 files changed, 69 insertions(+), 10 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/scev-expander-incorrect-nowrap.ll diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 59f19a002ec..ef9557132fc 100644 --- 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(AR->getType())) + return false; + + unsigned BitWidth = cast(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(AR->getType())) + return false; + + unsigned BitWidth = cast(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(IncV)) { - if (Normalized->getNoWrapFlags(SCEV::FlagNUW)) + if (IsIncrementNUW(SE, Normalized)) cast(IncV)->setHasNoUnsignedWrap(); - if (Normalized->getNoWrapFlags(SCEV::FlagNSW)) + if (IsIncrementNSW(SE, Normalized)) cast(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 index 00000000000..012cad743df --- /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 27aed3b0da1..43698204a72 100644 --- 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 63428df9610..987373e542a 100644 --- 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 e5e7bd23a64..7f095190ab8 100644 --- 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 2603f363ab6..3864c6c0cfb 100644 --- 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 88a7fd765d0..716e013603a 100644 --- 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 feb79f8a0c7..0e96f02904d 100644 --- 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 ; [#uses=1] %c_addr.1.be = select i1 %tmp2, i32 %tmp3, i32 %tmp4 ; [#uses=1] %indvar.next = add i32 %indvar, 1 ; [#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 4562d29a0a2..51550873415 100644 --- 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 ] ; [#uses=2] -- 2.34.1