Index: lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp =================================================================== --- lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -700,6 +700,20 @@ SE.getConstant(Max)); } +static bool isKnownNonNegative(const SCEV *BoundSCEV, Loop *L, + ScalarEvolution &SE) { + if (SE.isKnownNonNegative(BoundSCEV)) + return true; + if (SE.isKnownNegative(BoundSCEV)) + return false; + + Type *Ty = BoundSCEV->getType(); + return (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, + SE.getConstant(Ty, 0, true)) || + SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGE, BoundSCEV, + SE.getConstant(Ty, 0, false))); +} + /// Given a loop with an deccreasing induction variable, is it possible to /// safely calculate the bounds of a new loop using the given Predicate. static bool isSafeDecreasingBound(const SCEV *Start, @@ -919,8 +933,7 @@ // Currently we only work with induction variables that have been proved to // not wrap. This restriction can potentially be lifted in the future. - - if (!HasNoSignedWrap(AR)) + if (!HasNoSignedWrap(AR) && !AR->hasNoUnsignedWrap()) return false; if (const SCEVConstant *StepExpr = @@ -956,19 +969,19 @@ bool DecreasedRightValueByOne = false; if (StepCI->isOne()) { // Try to turn eq/ne predicates to those we can work with. - if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1) + if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1) { // while (++i != len) { while (++i < len) { // ... ---> ... // } } // If both parts are known non-negative, it is profitable to use // unsigned comparison in increasing loop. This allows us to make the // comparison check against "RightSCEV + 1" more optimistic. - if (SE.isKnownNonNegative(IndVarStart) && - SE.isKnownNonNegative(RightSCEV)) + if (isKnownNonNegative(IndVarStart, &L, SE) && + isKnownNonNegative(RightSCEV, &L, SE)) Pred = ICmpInst::ICMP_ULT; else Pred = ICmpInst::ICMP_SLT; - else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) { + } else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) { // while (true) { while (true) { // if (++i == len) ---> if (++i > len - 1) // break; break; Index: test/Transforms/IRCE/stride_more_than_1.ll =================================================================== --- test/Transforms/IRCE/stride_more_than_1.ll +++ test/Transforms/IRCE/stride_more_than_1.ll @@ -4,7 +4,7 @@ ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop
,%in.bounds ; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop
,%in.bounds ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop
,%in.bounds -; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop
,%in.bounds +; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop
,%in.bounds ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop
,%in.bounds ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop
,%in.bounds ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop
,%in.bounds @@ -206,12 +206,19 @@ ret void } -; IV = 0; IV ,%if.else,%for.inc ; CHECK: irce: in function signed_var_imm_dec_ne: constrained Loop at depth 1 containing: %for.body
,%if.else,%for.inc ; CHECK-NOT: irce: in function signed_var_imm_dec_eq: constrained Loop at depth 1 containing: %for.body
,%if.else,%for.inc +; CHECK: irce: in function test_inc_eq_var_nuw: constrained Loop at depth 1 containing: %for.body
,%if.else,%if.then,%for.inc +; CHECK: irce: in function test_inc_ne_var_nuw: constrained Loop at depth 1 containing: %for.body
,%if.else,%if.then,%for.inc +; CHECK: irce: in function test_inc_ult_var_nuw: constrained Loop at depth 1 containing: %for.body
,%if.else,%if.then,%for.inc +; CHECK: irce: in function test_dec_ult_ugt_var_imm_nuw: constrained Loop at depth 1 containing: %for.body
,%if.else,%if.then,%for.inc ; CHECK-LABEL: test_inc_eq( ; CHECK: main.exit.selector: @@ -55,7 +59,7 @@ ; CHECK-LABEL: test_inc_ne ; CHECK: main.exit.selector: ; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ] -; CHECK: [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], %N +; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N ; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit define void @test_inc_ne(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) { entry: @@ -321,6 +325,7 @@ br i1 %cmp, label %for.body, label %for.cond.cleanup } +; CHECK-LABEL: signed_var_imm_dec_eq define void @signed_var_imm_dec_eq(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %M) { entry: %cmp14 = icmp slt i32 %M, 1024 @@ -352,3 +357,171 @@ %cmp = icmp eq i32 %dec, %M br i1 %cmp, label %for.cond.cleanup, label %for.body } + +; CHECK-LABEL: test_inc_eq_var_nuw( +; CHECK: main.exit.selector: +; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ] +; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N +; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit +define void @test_inc_eq_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) { +entry: + %cmp16 = icmp ugt i32 %N, 0 + br i1 %cmp16, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void + +for.body: + %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ] + %cmp1 = icmp ult i32 %i.017, %M + %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017 + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017 + %1 = load i32, i32* %arrayidx2, align 4 + br i1 %cmp1, label %if.then, label %if.else + +if.then: + %sub = sub i32 %0, %1 + %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017 + %2 = load i32, i32* %arrayidx3, align 4 + %add = add nsw i32 %sub, %2 + store i32 %add, i32* %arrayidx3, align 4 + br label %for.inc + +if.else: + %add6 = add nsw i32 %1, %0 + %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017 + store i32 %add6, i32* %arrayidx7, align 4 + br label %for.inc + +for.inc: + %inc = add nuw i32 %i.017, 1 + %exitcond = icmp eq i32 %inc, %N + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} + +; CHECK-LABEL: test_inc_ne_var_nuw +; CHECK: main.exit.selector: +; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ] +; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N +; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit +define void @test_inc_ne_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) { +entry: + %cmp16 = icmp ugt i32 %N, 0 + br i1 %cmp16, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void + +for.body: + %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ] + %cmp1 = icmp ult i32 %i.017, %M + %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017 + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017 + %1 = load i32, i32* %arrayidx2, align 4 + br i1 %cmp1, label %if.then, label %if.else + +if.then: + %sub = sub i32 %0, %1 + %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017 + %2 = load i32, i32* %arrayidx3, align 4 + %add = add nsw i32 %sub, %2 + store i32 %add, i32* %arrayidx3, align 4 + br label %for.inc + +if.else: + %add6 = add nsw i32 %1, %0 + %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017 + store i32 %add6, i32* %arrayidx7, align 4 + br label %for.inc + +for.inc: + %inc = add nuw i32 %i.017, 1 + %exitcond = icmp ne i32 %inc, %N + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + +; CHECK-LABEL: test_inc_ult_var_nuw +; CHECK: main.exit.selector: +; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ] +; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N +; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit +define void @test_inc_ult_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) { +entry: + %cmp16 = icmp ugt i32 %N, 0 + br i1 %cmp16, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void + +for.body: + %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ] + %cmp1 = icmp ult i32 %i.017, %M + %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017 + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017 + %1 = load i32, i32* %arrayidx2, align 4 + br i1 %cmp1, label %if.then, label %if.else + +if.then: + %sub = sub i32 %0, %1 + %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017 + %2 = load i32, i32* %arrayidx3, align 4 + %add = add nsw i32 %sub, %2 + store i32 %add, i32* %arrayidx3, align 4 + br label %for.inc + +if.else: + %add6 = add nsw i32 %1, %0 + %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017 + store i32 %add6, i32* %arrayidx7, align 4 + br label %for.inc + +for.inc: + %inc = add nuw i32 %i.017, 1 + %exitcond = icmp ult i32 %inc, %N + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + +; CHECK-LABEL: test_dec_ult_ugt_var_imm_nuw( +; CHECK: for.body: +; CHECK: [[IV:%[^ ]+]] = phi i32 [ %inc, %for.inc ], [ %i.017.preloop.copy, %mainloop ] +; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[IV]], %M +; CHECK: br i1 true, label %if.then, label %if.else +define void @test_dec_ult_ugt_var_imm_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) { +entry: + br label %for.body + +for.cond.cleanup: + ret void + +for.body: + %i.017 = phi i32 [ %inc, %for.inc ], [ 1024, %entry ] + %cmp1 = icmp ult i32 %i.017, %M + %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017 + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017 + %1 = load i32, i32* %arrayidx2, align 4 + br i1 %cmp1, label %if.then, label %if.else + +if.then: + %sub = sub i32 %0, %1 + %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017 + %2 = load i32, i32* %arrayidx3, align 4 + %add = add nsw i32 %sub, %2 + store i32 %add, i32* %arrayidx3, align 4 + br label %for.inc + +if.else: + %add6 = add nsw i32 %1, %0 + %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017 + store i32 %add6, i32* %arrayidx7, align 4 + br label %for.inc + +for.inc: + %inc = add nuw i32 %i.017, -1 + %exitcond = icmp ugt i32 %inc, 0 + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} +