Index: llvm/trunk/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/trunk/include/llvm/Analysis/ScalarEvolution.h +++ llvm/trunk/include/llvm/Analysis/ScalarEvolution.h @@ -409,6 +409,32 @@ } }; +struct ExitLimitQuery { + ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) + : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {} + + const Loop *L; + BasicBlock *ExitingBlock; + bool AllowPredicates; +}; + +template <> struct DenseMapInfo { + static inline ExitLimitQuery getEmptyKey() { + return ExitLimitQuery(nullptr, nullptr, true); + } + static inline ExitLimitQuery getTombstoneKey() { + return ExitLimitQuery(nullptr, nullptr, false); + } + static unsigned getHashValue(ExitLimitQuery Val) { + return hash_combine(hash_combine(Val.L, Val.ExitingBlock), + Val.AllowPredicates); + } + static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) { + return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock && + LHS.AllowPredicates == RHS.AllowPredicates; + } +}; + /// The main scalar evolution driver. Because client code (intentionally) /// can't do much with the SCEV objects directly, they must ask this class /// for services. @@ -584,6 +610,8 @@ !isa(MaxNotTaken); } + bool hasOperand(const SCEV *S) const; + /// Test whether this ExitLimit contains all information. bool hasFullInfo() const { return !isa(ExactNotTaken); @@ -704,6 +732,9 @@ /// function as they are computed. DenseMap PredicatedBackedgeTakenCounts; + // Cache the calculated exit limits for the loops. + DenseMap ExitLimits; + /// This map contains entries for all of the PHI instructions that we /// attempt to compute constant evolutions for. This allows us to avoid /// potentially expensive recomputation of these properties. An instruction @@ -856,6 +887,9 @@ ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates = false); + ExitLimit computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock, + bool AllowPredicates = false); + /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of ExitCond, /// TBB, and FBB. @@ -1095,8 +1129,9 @@ /// to be a constant. Optional computeConstantDifference(const SCEV *LHS, const SCEV *RHS); - /// Drop memoized information computed for S. - void forgetMemoizedResults(const SCEV *S); + /// Drop memoized information computed for S. Only erase Exit Limits info if + /// we expect that the operation we have made is going to change it. + void forgetMemoizedResults(const SCEV *S, bool EraseExitLimit = true); /// Return an existing SCEV for V if there is one, otherwise return nullptr. const SCEV *getExistingSCEV(Value *V); Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolution.cpp +++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp @@ -6200,7 +6200,7 @@ // own when it gets to that point. if (!isa(I) || !isa(Old)) { eraseValueFromMap(It->first); - forgetMemoizedResults(Old); + forgetMemoizedResults(Old, false); } if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); @@ -6264,6 +6264,12 @@ PushDefUseChildren(I, Worklist); } + for (auto I = ExitLimits.begin(); I != ExitLimits.end(); ++I) { + auto &Query = I->first; + if (Query.L == L) + ExitLimits.erase(I); + } + // Forget all contained loops too, to avoid dangling entries in the // ValuesAtScopes map. for (Loop *I : *L) @@ -6526,6 +6532,18 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) { + ExitLimitQuery Query(L, ExitingBlock, AllowPredicates); + auto MaybeEL = ExitLimits.find(Query); + if (MaybeEL != ExitLimits.end()) + return MaybeEL->second; + ExitLimit EL = computeExitLimitImpl(L, ExitingBlock, AllowPredicates); + ExitLimits.insert({Query, EL}); + return EL; +} + +ScalarEvolution::ExitLimit +ScalarEvolution::computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock, + bool AllowPredicates) { // Okay, we've chosen an exiting block. See what condition causes us to exit // at this block and remember the exit block and whether all other targets @@ -10408,6 +10426,7 @@ BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)), PredicatedBackedgeTakenCounts( std::move(Arg.PredicatedBackedgeTakenCounts)), + ExitLimits(std::move(Arg.ExitLimits)), ConstantEvolutionLoopExitValue( std::move(Arg.ConstantEvolutionLoopExitValue)), ValuesAtScopes(std::move(Arg.ValuesAtScopes)), @@ -10810,7 +10829,16 @@ return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; }); } -void ScalarEvolution::forgetMemoizedResults(const SCEV *S) { +bool ScalarEvolution::ExitLimit::hasOperand(const SCEV *S) const { + auto IsS = [&](const SCEV *X) { return S == X; }; + auto ContainsS = [&](const SCEV *X) { + return !isa(X) && SCEVExprContains(X, IsS); + }; + return ContainsS(ExactNotTaken) || ContainsS(MaxNotTaken); +} + +void +ScalarEvolution::forgetMemoizedResults(const SCEV *S, bool EraseExitLimit) { ValuesAtScopes.erase(S); LoopDispositions.erase(S); BlockDispositions.erase(S); @@ -10843,6 +10871,13 @@ RemoveSCEVFromBackedgeMap(BackedgeTakenCounts); RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts); + + // TODO: There is a suspicion that we only need to do it when there is a + // SCEVUnknown somewhere inside S. Need to check this. + if (EraseExitLimit) + for (auto I = ExitLimits.begin(), E = ExitLimits.end(); I != E; ++I) + if (I->second.hasOperand(S)) + ExitLimits.erase(I); } void ScalarEvolution::verify() const { Index: llvm/trunk/test/Analysis/ScalarEvolution/cache_loop_exit_limit.ll =================================================================== --- llvm/trunk/test/Analysis/ScalarEvolution/cache_loop_exit_limit.ll +++ llvm/trunk/test/Analysis/ScalarEvolution/cache_loop_exit_limit.ll @@ -0,0 +1,253 @@ +; RUN: opt -scalar-evolution-max-arith-depth=4 -scalar-evolution-max-add-rec-size=4 -loop-reduce -S < %s | FileCheck %s + +; Check that the test does not hang. +define void @test_01(i32* nocapture %a) local_unnamed_addr { + +; CHECK-LABEL: @test_01( + +while.body.outer: + %arrayidx2 = getelementptr inbounds i32, i32* %a, i64 96 + %arrayidx2.promoted50 = load i32, i32* %arrayidx2, align 1 + %a.promoted = load i32, i32* %a, align 1 + %add347.peel = xor i32 %arrayidx2.promoted50, -1 + %tobool48.peel = icmp eq i32 %a.promoted, %add347.peel + br i1 %tobool48.peel, label %while.body.preheader, label %while.body4.preheader + +while.body.preheader: ; preds = %while.body.outer + %tobool48 = icmp eq i32 %a.promoted, 1 + br label %while.body + +while.body: ; preds = %while.body.preheader, %while.body + br i1 %tobool48, label %while.body, label %while.body4.preheader.loopexit + +while.body4.preheader.loopexit: ; preds = %while.body + br label %while.body4.preheader + +while.body4.preheader: ; preds = %while.body4.preheader.loopexit, %while.body.outer + br label %while.body4 + +while.body4: ; preds = %while.body4.preheader, %while.end.22 + %0 = phi i32 [ %mul.22, %while.end.22 ], [ %arrayidx2.promoted50, %while.body4.preheader ] + %mul = mul nsw i32 %0, %0 + br label %while.cond17 + +while.cond17: ; preds = %while.cond17, %while.body4 + %add22.sink = phi i32 [ %add22, %while.cond17 ], [ %mul, %while.body4 ] + %cmp = icmp slt i32 %add22.sink, 0 + %add22 = add nsw i32 %add22.sink, 1024 + br i1 %cmp, label %while.cond17, label %while.end + +while.end: ; preds = %while.cond17 + %mul.1 = mul nsw i32 %add22.sink, %add22.sink + br label %while.cond17.1 + +while.cond17.1: ; preds = %while.cond17.1, %while.end + %add22.sink.1 = phi i32 [ %add22.1, %while.cond17.1 ], [ %mul.1, %while.end ] + %cmp.1 = icmp slt i32 %add22.sink.1, 0 + %add22.1 = add nsw i32 %add22.sink.1, 2048 + br i1 %cmp.1, label %while.cond17.1, label %while.end.1 + +while.end.1: ; preds = %while.cond17.1 + %mul.2 = mul nsw i32 %add22.sink.1, %add22.sink.1 + br label %while.cond17.2 + +while.cond17.2: ; preds = %while.cond17.2, %while.end.1 + %add22.sink.2 = phi i32 [ %add22.2, %while.cond17.2 ], [ %mul.2, %while.end.1 ] + %cmp.2 = icmp slt i32 %add22.sink.2, 0 + %add22.2 = add nsw i32 %add22.sink.2, 4096 + br i1 %cmp.2, label %while.cond17.2, label %while.end.2 + +while.end.2: ; preds = %while.cond17.2 + %mul.3 = mul nsw i32 %add22.sink.2, %add22.sink.2 + br label %while.cond17.3 + +while.cond17.3: ; preds = %while.cond17.3, %while.end.2 + %add22.sink.3 = phi i32 [ %add22.3, %while.cond17.3 ], [ %mul.3, %while.end.2 ] + %cmp.3 = icmp slt i32 %add22.sink.3, 0 + %add22.3 = add nsw i32 %add22.sink.3, 8192 + br i1 %cmp.3, label %while.cond17.3, label %while.end.3 + +while.end.3: ; preds = %while.cond17.3 + %mul.4 = mul nsw i32 %add22.sink.3, %add22.sink.3 + br label %while.cond17.4 + +while.cond17.4: ; preds = %while.cond17.4, %while.end.3 + %add22.sink.4 = phi i32 [ %add22.4, %while.cond17.4 ], [ %mul.4, %while.end.3 ] + %cmp.4 = icmp slt i32 %add22.sink.4, 0 + %add22.4 = add nsw i32 %add22.sink.4, 16384 + br i1 %cmp.4, label %while.cond17.4, label %while.end.4 + +while.end.4: ; preds = %while.cond17.4 + %mul.5 = mul nsw i32 %add22.sink.4, %add22.sink.4 + br label %while.cond17.5 + +while.cond17.5: ; preds = %while.cond17.5, %while.end.4 + %add22.sink.5 = phi i32 [ %add22.5, %while.cond17.5 ], [ %mul.5, %while.end.4 ] + %cmp.5 = icmp slt i32 %add22.sink.5, 0 + %add22.5 = add nsw i32 %add22.sink.5, 32768 + br i1 %cmp.5, label %while.cond17.5, label %while.end.5 + +while.end.5: ; preds = %while.cond17.5 + %mul.6 = mul nsw i32 %add22.sink.5, %add22.sink.5 + br label %while.cond17.6 + +while.cond17.6: ; preds = %while.cond17.6, %while.end.5 + %add22.sink.6 = phi i32 [ %add22.6, %while.cond17.6 ], [ %mul.6, %while.end.5 ] + %cmp.6 = icmp slt i32 %add22.sink.6, 0 + %add22.6 = add nsw i32 %add22.sink.6, 65536 + br i1 %cmp.6, label %while.cond17.6, label %while.end.6 + +while.end.6: ; preds = %while.cond17.6 + %mul.7 = mul nsw i32 %add22.sink.6, %add22.sink.6 + br label %while.cond17.7 + +while.cond17.7: ; preds = %while.cond17.7, %while.end.6 + %add22.sink.7 = phi i32 [ %add22.7, %while.cond17.7 ], [ %mul.7, %while.end.6 ] + %cmp.7 = icmp slt i32 %add22.sink.7, 0 + %add22.7 = add nsw i32 %add22.sink.7, 131072 + br i1 %cmp.7, label %while.cond17.7, label %while.end.7 + +while.end.7: ; preds = %while.cond17.7 + %mul.8 = mul nsw i32 %add22.sink.7, %add22.sink.7 + br label %while.cond17.8 + +while.cond17.8: ; preds = %while.cond17.8, %while.end.7 + %add22.sink.8 = phi i32 [ %add22.8, %while.cond17.8 ], [ %mul.8, %while.end.7 ] + %cmp.8 = icmp slt i32 %add22.sink.8, 0 + %add22.8 = add nsw i32 %add22.sink.8, 262144 + br i1 %cmp.8, label %while.cond17.8, label %while.end.8 + +while.end.8: ; preds = %while.cond17.8 + %mul.9 = mul nsw i32 %add22.sink.8, %add22.sink.8 + br label %while.cond17.9 + +while.cond17.9: ; preds = %while.cond17.9, %while.end.8 + %add22.sink.9 = phi i32 [ %add22.9, %while.cond17.9 ], [ %mul.9, %while.end.8 ] + %cmp.9 = icmp slt i32 %add22.sink.9, 0 + %add22.9 = add nsw i32 %add22.sink.9, 524288 + br i1 %cmp.9, label %while.cond17.9, label %while.end.9 + +while.end.9: ; preds = %while.cond17.9 + %mul.10 = mul nsw i32 %add22.sink.9, %add22.sink.9 + br label %while.cond17.10 + +while.cond17.10: ; preds = %while.cond17.10, %while.end.9 + %add22.sink.10 = phi i32 [ %add22.10, %while.cond17.10 ], [ %mul.10, %while.end.9 ] + %cmp.10 = icmp slt i32 %add22.sink.10, 0 + %add22.10 = add nsw i32 %add22.sink.10, 1048576 + br i1 %cmp.10, label %while.cond17.10, label %while.end.10 + +while.end.10: ; preds = %while.cond17.10 + %mul.11 = mul nsw i32 %add22.sink.10, %add22.sink.10 + br label %while.cond17.11 + +while.cond17.11: ; preds = %while.cond17.11, %while.end.10 + %add22.sink.11 = phi i32 [ %add22.11, %while.cond17.11 ], [ %mul.11, %while.end.10 ] + %cmp.11 = icmp slt i32 %add22.sink.11, 0 + %add22.11 = add nsw i32 %add22.sink.11, 2097152 + br i1 %cmp.11, label %while.cond17.11, label %while.end.11 + +while.end.11: ; preds = %while.cond17.11 + %mul.12 = mul nsw i32 %add22.sink.11, %add22.sink.11 + br label %while.cond17.12 + +while.cond17.12: ; preds = %while.cond17.12, %while.end.11 + %add22.sink.12 = phi i32 [ %add22.12, %while.cond17.12 ], [ %mul.12, %while.end.11 ] + %cmp.12 = icmp slt i32 %add22.sink.12, 0 + %add22.12 = add nsw i32 %add22.sink.12, 4194304 + br i1 %cmp.12, label %while.cond17.12, label %while.end.12 + +while.end.12: ; preds = %while.cond17.12 + %mul.13 = mul nsw i32 %add22.sink.12, %add22.sink.12 + br label %while.cond17.13 + +while.cond17.13: ; preds = %while.cond17.13, %while.end.12 + %add22.sink.13 = phi i32 [ %add22.13, %while.cond17.13 ], [ %mul.13, %while.end.12 ] + %cmp.13 = icmp slt i32 %add22.sink.13, 0 + %add22.13 = add nsw i32 %add22.sink.13, 8388608 + br i1 %cmp.13, label %while.cond17.13, label %while.end.13 + +while.end.13: ; preds = %while.cond17.13 + %mul.14 = mul nsw i32 %add22.sink.13, %add22.sink.13 + br label %while.cond17.14 + +while.cond17.14: ; preds = %while.cond17.14, %while.end.13 + %add22.sink.14 = phi i32 [ %add22.14, %while.cond17.14 ], [ %mul.14, %while.end.13 ] + %cmp.14 = icmp slt i32 %add22.sink.14, 0 + %add22.14 = add nsw i32 %add22.sink.14, 16777216 + br i1 %cmp.14, label %while.cond17.14, label %while.end.14 + +while.end.14: ; preds = %while.cond17.14 + %mul.15 = mul nsw i32 %add22.sink.14, %add22.sink.14 + br label %while.cond17.15 + +while.cond17.15: ; preds = %while.cond17.15, %while.end.14 + %add22.sink.15 = phi i32 [ %add22.15, %while.cond17.15 ], [ %mul.15, %while.end.14 ] + %cmp.15 = icmp slt i32 %add22.sink.15, 0 + %add22.15 = add nsw i32 %add22.sink.15, 33554432 + br i1 %cmp.15, label %while.cond17.15, label %while.end.15 + +while.end.15: ; preds = %while.cond17.15 + %mul.16 = mul nsw i32 %add22.sink.15, %add22.sink.15 + br label %while.cond17.16 + +while.cond17.16: ; preds = %while.cond17.16, %while.end.15 + %add22.sink.16 = phi i32 [ %add22.16, %while.cond17.16 ], [ %mul.16, %while.end.15 ] + %cmp.16 = icmp slt i32 %add22.sink.16, 0 + %add22.16 = add nsw i32 %add22.sink.16, 67108864 + br i1 %cmp.16, label %while.cond17.16, label %while.end.16 + +while.end.16: ; preds = %while.cond17.16 + %mul.17 = mul nsw i32 %add22.sink.16, %add22.sink.16 + br label %while.cond17.17 + +while.cond17.17: ; preds = %while.cond17.17, %while.end.16 + %add22.sink.17 = phi i32 [ %add22.17, %while.cond17.17 ], [ %mul.17, %while.end.16 ] + %cmp.17 = icmp slt i32 %add22.sink.17, 0 + %add22.17 = add nsw i32 %add22.sink.17, 134217728 + br i1 %cmp.17, label %while.cond17.17, label %while.end.17 + +while.end.17: ; preds = %while.cond17.17 + %mul.18 = mul nsw i32 %add22.sink.17, %add22.sink.17 + br label %while.cond17.18 + +while.cond17.18: ; preds = %while.cond17.18, %while.end.17 + %add22.sink.18 = phi i32 [ %add22.18, %while.cond17.18 ], [ %mul.18, %while.end.17 ] + %cmp.18 = icmp slt i32 %add22.sink.18, 0 + %add22.18 = add nsw i32 %add22.sink.18, 268435456 + br i1 %cmp.18, label %while.cond17.18, label %while.end.18 + +while.end.18: ; preds = %while.cond17.18 + %mul.19 = mul nsw i32 %add22.sink.18, %add22.sink.18 + br label %while.cond17.19 + +while.cond17.19: ; preds = %while.cond17.19, %while.end.18 + %add22.sink.19 = phi i32 [ %add22.19, %while.cond17.19 ], [ %mul.19, %while.end.18 ] + %cmp.19 = icmp slt i32 %add22.sink.19, 0 + %add22.19 = add nsw i32 %add22.sink.19, 536870912 + br i1 %cmp.19, label %while.cond17.19, label %while.end.19 + +while.end.19: ; preds = %while.cond17.19 + %mul.20 = mul nsw i32 %add22.sink.19, %add22.sink.19 + br label %while.cond17.20 + +while.cond17.20: ; preds = %while.cond17.20, %while.end.19 + %add22.sink.20 = phi i32 [ %add22.20, %while.cond17.20 ], [ %mul.20, %while.end.19 ] + %cmp.20 = icmp slt i32 %add22.sink.20, 0 + %add22.20 = add nsw i32 %add22.sink.20, 1073741824 + br i1 %cmp.20, label %while.cond17.20, label %while.end.20 + +while.end.20: ; preds = %while.cond17.20 + %mul.21 = mul nsw i32 %add22.sink.20, %add22.sink.20 + br label %while.cond17.21 + +while.cond17.21: ; preds = %while.cond17.21, %while.end.20 + %add22.sink.21 = phi i32 [ %add22.21, %while.cond17.21 ], [ %mul.21, %while.end.20 ] + %cmp.21 = icmp slt i32 %add22.sink.21, 0 + %add22.21 = or i32 %add22.sink.21, -2147483648 + br i1 %cmp.21, label %while.cond17.21, label %while.end.22 + +while.end.22: ; preds = %while.cond17.21 + %mul.22 = mul nsw i32 %add22.sink.21, %add22.sink.21 + br label %while.body4 +} Index: llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp +++ llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp @@ -930,5 +930,165 @@ EXPECT_FALSE(verifyFunction(*F, &errs())); } +// Make sure that SCEV invalidates exit limits after invalidating the values it +// depends on when we forget a loop. +TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) { + /* + * Create the following code: + * func(i64 addrspace(10)* %arg) + * top: + * br label %L.ph + * L.ph: + * br label %L + * L: + * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] + * %add = add i64 %phi2, 1 + * %cond = icmp slt i64 %add, 1000; then becomes 2000. + * br i1 %cond, label %post, label %L2 + * post: + * ret void + * + */ + + // Create a module with non-integral pointers in it's datalayout + Module NIM("nonintegral", Context); + std::string DataLayout = M.getDataLayoutStr(); + if (!DataLayout.empty()) + DataLayout += "-"; + DataLayout += "ni:10"; + NIM.setDataLayout(DataLayout); + + Type *T_int64 = Type::getInt64Ty(Context); + Type *T_pint64 = T_int64->getPointerTo(10); + + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); + Function *F = cast(NIM.getOrInsertFunction("foo", FTy)); + + Argument *Arg = &*F->arg_begin(); + + BasicBlock *Top = BasicBlock::Create(Context, "top", F); + BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); + BasicBlock *L = BasicBlock::Create(Context, "L", F); + BasicBlock *Post = BasicBlock::Create(Context, "post", F); + + IRBuilder<> Builder(Top); + Builder.CreateBr(LPh); + + Builder.SetInsertPoint(LPh); + Builder.CreateBr(L); + + Builder.SetInsertPoint(L); + PHINode *Phi = Builder.CreatePHI(T_int64, 2); + auto *Add = cast( + Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); + auto *Limit = ConstantInt::get(T_int64, 1000); + auto *Cond = cast( + Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond")); + auto *Br = cast(Builder.CreateCondBr(Cond, L, Post)); + Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); + Phi->addIncoming(Add, L); + + Builder.SetInsertPoint(Post); + Builder.CreateRetVoid(); + + ScalarEvolution SE = buildSE(*F); + auto *Loop = LI->getLoopFor(L); + const SCEV *EC = SE.getBackedgeTakenCount(Loop); + EXPECT_FALSE(isa(EC)); + + SE.forgetLoop(Loop); + Br->eraseFromParent(); + Cond->eraseFromParent(); + + Builder.SetInsertPoint(L); + Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), + "new.cond"); + Builder.CreateCondBr(Cond, L, Post); + const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); + EXPECT_NE(EC, NewEC); +} + +// Make sure that SCEV invalidates exit limits after invalidating the values it +// depends on when we forget a value. +TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) { + /* + * Create the following code: + * func(i64 addrspace(10)* %arg) + * top: + * br label %L.ph + * L.ph: + * %load = load i64 addrspace(10)* %arg + * br label %L + * L: + * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] + * %add = add i64 %phi2, 1 + * %cond = icmp slt i64 %add, %load ; then becomes 2000. + * br i1 %cond, label %post, label %L2 + * post: + * ret void + * + */ + + // Create a module with non-integral pointers in it's datalayout + Module NIM("nonintegral", Context); + std::string DataLayout = M.getDataLayoutStr(); + if (!DataLayout.empty()) + DataLayout += "-"; + DataLayout += "ni:10"; + NIM.setDataLayout(DataLayout); + + Type *T_int64 = Type::getInt64Ty(Context); + Type *T_pint64 = T_int64->getPointerTo(10); + + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); + Function *F = cast(NIM.getOrInsertFunction("foo", FTy)); + + Argument *Arg = &*F->arg_begin(); + + BasicBlock *Top = BasicBlock::Create(Context, "top", F); + BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); + BasicBlock *L = BasicBlock::Create(Context, "L", F); + BasicBlock *Post = BasicBlock::Create(Context, "post", F); + + IRBuilder<> Builder(Top); + Builder.CreateBr(LPh); + + Builder.SetInsertPoint(LPh); + auto *Load = cast(Builder.CreateLoad(T_int64, Arg, "load")); + Builder.CreateBr(L); + + Builder.SetInsertPoint(L); + PHINode *Phi = Builder.CreatePHI(T_int64, 2); + auto *Add = cast( + Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); + auto *Cond = cast( + Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond")); + auto *Br = cast(Builder.CreateCondBr(Cond, L, Post)); + Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); + Phi->addIncoming(Add, L); + + Builder.SetInsertPoint(Post); + Builder.CreateRetVoid(); + + ScalarEvolution SE = buildSE(*F); + auto *Loop = LI->getLoopFor(L); + const SCEV *EC = SE.getBackedgeTakenCount(Loop); + EXPECT_FALSE(isa(EC)); + + SE.forgetValue(Load); + Br->eraseFromParent(); + Cond->eraseFromParent(); + Load->eraseFromParent(); + + Builder.SetInsertPoint(L); + Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), + "new.cond"); + Builder.CreateCondBr(Cond, L, Post); + const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); + EXPECT_NE(EC, NewEC); +} + } // end anonymous namespace } // end namespace llvm