From 86d34100cf164f6ba5c0c2344b7dff86cc0a0980 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Mon, 12 Dec 2011 22:46:16 +0000 Subject: Indvars: guard against exponential behavior in isHighCostExpansion. This should always be done as a matter of principal. I don't have a case that exposes the problem. I just noticed this recently while scanning the code and realized I meant to fix it long ago. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146438 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/IndVarSimplify.cpp | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp') diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 1176cc9a04..6d52b22e01 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1238,7 +1238,11 @@ void IndVarSimplify::SimplifyAndExtend(Loop *L, /// BackedgeTakenInfo. If these expressions have not been reduced, then /// expanding them may incur additional cost (albeit in the loop preheader). static bool isHighCostExpansion(const SCEV *S, BranchInst *BI, + SmallPtrSet &Processed, ScalarEvolution *SE) { + if (!Processed.insert(S)) + return false; + // If the backedge-taken count is a UDiv, it's very likely a UDiv that // ScalarEvolution's HowFarToZero or HowManyLessThans produced to compute a // precise expression, rather than a UDiv from the user's code. If we can't @@ -1266,7 +1270,7 @@ static bool isHighCostExpansion(const SCEV *S, BranchInst *BI, if (const SCEVAddExpr *Add = dyn_cast(S)) { for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); I != E; ++I) { - if (isHighCostExpansion(*I, BI, SE)) + if (isHighCostExpansion(*I, BI, Processed, SE)) return true; } return false; @@ -1309,7 +1313,8 @@ static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { if (!BI) return false; - if (isHighCostExpansion(BackedgeTakenCount, BI, SE)) + SmallPtrSet Processed; + if (isHighCostExpansion(BackedgeTakenCount, BI, Processed, SE)) return false; return true; -- cgit v1.2.3