Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1727,6 +1727,14 @@ Value *ExitCond, bool ExitIfTrue, bool ControlsExit, bool AllowPredicates); + /// Given a condition of the form (Pred IV, RHS) which controls some exit in + /// IV's loop, prove the strongest wrap flags we can from the fact that a + /// mustprogress loop is assumed to be finite. ControlsExit is true if and + /// only if this condition controls the loop's sole exit. + SCEV::NoWrapFlags + computeNoWrapFromExitICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV, + const SCEV *RHS, bool ControlsExit); + /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of the ICmpInst /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -7902,6 +7902,56 @@ { &EL0.Predicates, &EL1.Predicates }); } +SCEV::NoWrapFlags +ScalarEvolution::computeNoWrapFromExitICmp(ICmpInst::Predicate Pred, + const SCEVAddRecExpr *IV, + const SCEV *RHS, + bool ControlsExit) { + + // Can we prove this loop *must* be UB if overflow of IV occurs? + // Reasoning goes as follows: + // * Suppose the IV did self wrap. + // * If Stride evenly divides the iteration space, then once wrap + // occurs, the loop must revisit the same values. + // * We know that RHS is invariant, and that none of those values + // caused this exit to be taken previously. Thus, this exit is + // dynamically dead. + // * If this is the sole exit, then a dead exit implies the loop + // must be infinite if there are no abnormal exits. + // * If the loop were infinite, then it must either not be mustprogress + // or have side effects. Otherwise, it must be UB. + // * It can't (by assumption), be UB so we have contradicted our + // premise and can conclude the IV did not in fact self-wrap. + + const Loop *L = IV->getLoop(); + + if (!isLoopInvariant(RHS, L)) + return SCEV::FlagAnyWrap; + + auto *Stride = IV->getStepRecurrence(*this); + auto *StrideC = dyn_cast(Stride); + if (!StrideC || !StrideC->getAPInt().isPowerOf2()) + return SCEV::FlagAnyWrap; + + if (!ControlsExit || !loopHasNoAbnormalExits(L)) + return SCEV::FlagAnyWrap; + + if (!loopIsFiniteByAssumption(L)) + return SCEV::FlagAnyWrap; + + if (ICmpInst::isEquality(Pred)) + return SCEV::FlagNW; + + // From no-self-wrap, we need to then prove no-(un)signed-wrap. We'll + // describe the logic in terms of LT, but analogous arguments can be made + // for each of the non-equality predicates. Every (un)signed-wrapped, + // but not self-wrapped value must be LT than the last value before + // (un)signed wrap. Since we know that last value didn't exit, nor + // will any smaller one. + + return ICmpInst::isSigned(Pred) ? SCEV::FlagNSW : SCEV::FlagNUW; +} + ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, @@ -9376,12 +9426,21 @@ return ExitLimit(Distance, getConstant(MaxBECount), false, Predicates); } + auto isNoSelfWrap = [&]() -> bool { + if (AddRec->hasNoSelfWrap()) + return true; + auto WrapFlags = + computeNoWrapFromExitICmp(ICmpInst::ICMP_NE, AddRec, + getZero(AddRec->getType()), ControlsExit); + return WrapFlags & SCEV::FlagNW; + }; + // If the condition controls loop exit (the loop exits only if the expression // is true) and the addition is no-wrap we can use unsigned divide to // compute the backedge count. In this case, the step may not divide the // distance, but we don't care because if the condition is "missed" the loop // will have undefined behavior due to wrapping. - if (ControlsExit && AddRec->hasNoSelfWrap() && + if (ControlsExit && isNoSelfWrap() && loopHasNoAbnormalExits(AddRec->getLoop())) { const SCEV *Exact = getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); @@ -11479,38 +11538,8 @@ !loopIsFiniteByAssumption(L)) return getCouldNotCompute(); } else if (!Stride->isOne() && !NoWrap) { - auto isUBOnWrap = [&]() { - // Can we prove this loop *must* be UB if overflow of IV occurs? - // Reasoning goes as follows: - // * Suppose the IV did self wrap. - // * If Stride evenly divides the iteration space, then once wrap - // occurs, the loop must revisit the same values. - // * We know that RHS is invariant, and that none of those values - // caused this exit to be taken previously. Thus, this exit is - // dynamically dead. - // * If this is the sole exit, then a dead exit implies the loop - // must be infinite if there are no abnormal exits. - // * If the loop were infinite, then it must either not be mustprogress - // or have side effects. Otherwise, it must be UB. - // * It can't (by assumption), be UB so we have contradicted our - // premise and can conclude the IV did not in fact self-wrap. - // From no-self-wrap, we need to then prove no-(un)signed-wrap. This - // follows trivially from the fact that every (un)signed-wrapped, but - // not self-wrapped value must be LT than the last value before - // (un)signed wrap. Since we know that last value didn't exit, nor - // will any smaller one. - - if (!isLoopInvariant(RHS, L)) - return false; - - auto *StrideC = dyn_cast(Stride); - if (!StrideC || !StrideC->getAPInt().isPowerOf2()) - return false; - - if (!ControlsExit || !loopHasNoAbnormalExits(L)) - return false; - - return loopIsFiniteByAssumption(L); + auto isUBOnWrap = [&]() -> bool { + return WrapType & computeNoWrapFromExitICmp(Cond, IV, RHS, ControlsExit); }; // Avoid proven overflow cases: this will ensure that the backedge taken Index: llvm/test/Analysis/ScalarEvolution/ne-overflow.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/ScalarEvolution/ne-overflow.ll @@ -0,0 +1,187 @@ + +; RUN: opt %s -analyze -scalar-evolution -enable-new-pm=0 -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; A collection of tests focused on exercising logic to prove no-unsigned wrap +; from mustprogress semantics of loops. + +; CHECK: Determining loop execution counts for: @test +; CHECK: Loop %for.body: backedge-taken count is ((-2 + %N) /u 2) +; CHECK: Determining loop execution counts for: @test_preinc +; CHECK: Loop %for.body: backedge-taken count is (%N /u 2) +; CHECK: Determining loop execution counts for: @test_well_defined_infinite_st +; CHECK: Loop %for.body: Unpredictable backedge-taken count. +; CHECK: Determining loop execution counts for: @test_well_defined_infinite_ld +; CHECK: Loop %for.body: Unpredictable backedge-taken count. +; CHECK: Determining loop execution counts for: @test_no_mustprogress +; CHECK: Loop %for.body: Unpredictable backedge-taken count. +; CHECK: Determining loop execution counts for: @test_1024 +; CHECK: Loop %for.body: backedge-taken count is ((-1024 + %N) /u 1024) +; CHECK: Determining loop execution counts for: @test_uneven_divide +; CHECK: Loop %for.body: backedge-taken count is (-1 + (-1431655765 * %N)) +; CHECK: Determining loop execution counts for: @test_non_invariant_rhs +; CHECK: Loop %for.body: Unpredictable backedge-taken count. +; CHECK: Determining loop execution counts for: @test_abnormal_exit +; CHECK: Loop %for.body: Unpredictable backedge-taken count. +; CHECK: Determining loop execution counts for: @test_other_exit +; CHECK: Loop %for.body: Unpredictable backedge-taken count. + +define void @test(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +define void @test_preinc(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %cmp = icmp ne i32 %iv, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void + +} + +@G = external global i32 + +define void @test_well_defined_infinite_st(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + store volatile i32 0, i32* @G + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +define void @test_well_defined_infinite_ld(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %val = load volatile i32, i32* @G + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +define void @test_no_mustprogress(i32 %N) { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void + +} + + +define void @test_1024(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 1024 + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +define void @test_uneven_divide(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 3 + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +define void @test_non_invariant_rhs() mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %N = load i32, i32* @G + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +declare void @mayexit() + +define void @test_abnormal_exit(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + call void @mayexit() + %cmp = icmp ne i32 %iv.next, %N + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + + +define void @test_other_exit(i32 %N) mustprogress { +entry: + br label %for.body + +for.body: + %iv = phi i32 [ %iv.next, %for.latch ], [ 0, %entry ] + %iv.next = add i32 %iv, 2 + %cmp1 = icmp ne i32 %iv.next, 20 + br i1 %cmp1, label %for.latch, label %for.cond.cleanup + +for.latch: + %cmp2 = icmp ne i32 %iv.next, %N + br i1 %cmp2, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: + ret void +} + +