From 6378bdb2ddbd011d8882a304a16f31351e08954b Mon Sep 17 00:00:00 2001 From: Daniil Fukalov Date: Mon, 6 Feb 2017 12:38:06 +0000 Subject: [SCEV] limit recursion depth and operands number in getAddExpr for a quite big function with source like %add = add nsw i32 %mul, %conv %mul1 = mul nsw i32 %add, %conv %add2 = add nsw i32 %mul1, %add %mul3 = mul nsw i32 %add2, %add ; repeat couple of thousands times that can be produced by loop unroll, getAddExpr() tries to recursively construct SCEV and runs almost infinite time. Added recursion depth restriction (with new parameter to set it) Reviewers: sanjoy Subscribers: hfinkel, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D28158 llvm-svn: 294181 --- llvm/unittests/Analysis/ScalarEvolutionTest.cpp | 28 +++++++++++++++++++++++++ 1 file changed, 28 insertions(+) (limited to 'llvm/unittests/Analysis') diff --git a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp index 752cc812824..52368a89884 100644 --- a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp +++ b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp @@ -532,5 +532,33 @@ TEST_F(ScalarEvolutionsTest, SCEVCompareComplexity) { EXPECT_NE(nullptr, SE.getSCEV(Acc[0])); } +TEST_F(ScalarEvolutionsTest, SCEVAddExpr) { + Type *Ty32 = Type::getInt32Ty(Context); + Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32}; + + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), ArgTys, false); + Function *F = cast(M.getOrInsertFunction("f", FTy)); + + Argument *A1 = &*F->arg_begin(); + Argument *A2 = &*(std::next(F->arg_begin())); + BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); + + Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB); + Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB); + Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB); + Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB); + Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB); + for (int i = 0; i < 1000; i++) { + Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB); + Add1 = Add2; + Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB); + } + + ReturnInst::Create(Context, nullptr, EntryBB); + ScalarEvolution SE = buildSE(*F); + EXPECT_NE(nullptr, SE.getSCEV(Mul1)); +} + } // end anonymous namespace } // end namespace llvm -- cgit v1.2.3