diff options
author | Andrew Trick <atrick@apple.com> | 2011-07-18 18:21:35 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2011-07-18 18:21:35 +0000 |
commit | 5241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5 (patch) | |
tree | fe4f13a21d370fc090376c163b1726a54a76103d /lib/Transforms/Scalar/IndVarSimplify.cpp | |
parent | 3f6a8dd4ceff2da64edc18f09444c9f3c7103793 (diff) | |
download | llvm-5241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5.tar.gz llvm-5241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5.tar.bz2 llvm-5241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5.tar.xz |
indvars: Added isHighCostExpansion. Avoid generating extra ops in the
preheader for the sole purpose of LFTR, since LFTR itself is usually not
a clear optimization.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135409 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
-rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 68 |
1 files changed, 51 insertions, 17 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index cf75448aa2..3f7f5cefb4 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1448,6 +1448,54 @@ void IndVarSimplify::SimplifyCongruentIVs(Loop *L) { // LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. //===----------------------------------------------------------------------===// +// Check for expressions that ScalarEvolution generates to compute +// 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, + ScalarEvolution *SE) { + // 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 + // find a UDiv in the code with some simple searching, assume the former and + // forego rewriting the loop. + if (isa<SCEVUDivExpr>(S)) { + ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); + if (!OrigCond) return true; + const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); + R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); + if (R != S) { + const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); + L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); + if (L != S) + return true; + } + } + + if (!DisableIVRewrite) + return false; + + // Recurse past add expressions, which commonly occur in the + // BackedgeTakenCount. They may already exist in program code, and if not, + // they are not too expensive rematerialize. + if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { + for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); + I != E; ++I) { + if (isHighCostExpansion(*I, BI, SE)) + return true; + } + return false; + } + + // HowManyLessThans uses a Max expression whenever the loop is not guarded by + // the exit condition. + if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S)) + return true; + + // If we haven't recognized an expensive SCEV patter, assume its an expression + // produced by program code. + return false; +} + /// canExpandBackedgeTakenCount - Return true if this loop's backedge taken /// count expression can be safely and cheaply expanded into an instruction /// sequence that can be used by LinearFunctionTestReplace. @@ -1465,23 +1513,9 @@ static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { if (!BI) return false; - // Special case: If the backedge-taken count is a UDiv, it's very likely a - // UDiv that ScalarEvolution produced in order to compute a precise - // expression, rather than a UDiv from the user's code. If we can't find a - // UDiv in the code with some simple searching, assume the former and forego - // rewriting the loop. - if (isa<SCEVUDivExpr>(BackedgeTakenCount)) { - ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); - if (!OrigCond) return false; - const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); - R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); - if (R != BackedgeTakenCount) { - const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); - L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); - if (L != BackedgeTakenCount) - return false; - } - } + if (isHighCostExpansion(BackedgeTakenCount, BI, SE)) + return false; + return true; } |