diff options
author | Andrew Trick <atrick@apple.com> | 2011-08-06 07:00:37 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2011-08-06 07:00:37 +0000 |
commit | 06988bcf6a5c74e81cf7e76f06a686aa822ec00a (patch) | |
tree | ff0b2f17005dae608bc8820f0a33b32e716d77d0 /lib/Transforms/Scalar/IndVarSimplify.cpp | |
parent | ccfa446450c9e3e0b3591343c4c5bea1e4cdc043 (diff) | |
download | llvm-06988bcf6a5c74e81cf7e76f06a686aa822ec00a.tar.gz llvm-06988bcf6a5c74e81cf7e76f06a686aa822ec00a.tar.bz2 llvm-06988bcf6a5c74e81cf7e76f06a686aa822ec00a.tar.xz |
Made SCEV's UDiv expressions more canonical. When dividing a
recurrence, the initial values low bits can sometimes be ignored.
To take advantage of this, added FoldIVUser to IndVarSimplify to fold
an IV operand into a udiv/lshr if the operator doesn't affect the
result.
-indvars -disable-iv-rewrite now transforms
i = phi i4
i1 = i0 + 1
idx = i1 >> (2 or more)
i4 = i + 4
into
i = phi i4
idx = i0 >> ...
i4 = i + 4
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137013 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
-rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index f2c69a258c..e40d72979e 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -70,6 +70,7 @@ STATISTIC(NumInserted , "Number of canonical indvars added"); STATISTIC(NumReplaced , "Number of exit values replaced"); STATISTIC(NumLFTR , "Number of loop exit tests replaced"); STATISTIC(NumElimIdentity, "Number of IV identities eliminated"); +STATISTIC(NumElimOperand, "Number of IV operands folded into a use"); STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); STATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); @@ -142,6 +143,8 @@ namespace { Value *IVOperand, bool IsSigned); + bool FoldIVUser(Instruction *UseInst, Instruction *IVOperand); + void SimplifyCongruentIVs(Loop *L); void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); @@ -1298,6 +1301,66 @@ bool IndVarSimplify::EliminateIVUser(Instruction *UseInst, return true; } +/// FoldIVUser - Fold an IV operand into its use. This removes increments of an +/// aligned IV when used by a instruction that ignores the low bits. +bool IndVarSimplify::FoldIVUser(Instruction *UseInst, Instruction *IVOperand) { + Value *IVSrc = 0; + unsigned OperIdx = 0; + const SCEV *FoldedExpr = 0; + switch (UseInst->getOpcode()) { + default: + return false; + case Instruction::UDiv: + case Instruction::LShr: + // We're only interested in the case where we know something about + // the numerator and have a constant denominator. + if (IVOperand != UseInst->getOperand(OperIdx) || + !isa<ConstantInt>(UseInst->getOperand(1))) + return false; + + // Attempt to fold a binary operator with constant operand. + // e.g. ((I + 1) >> 2) => I >> 2 + if (IVOperand->getNumOperands() != 2 || + !isa<ConstantInt>(IVOperand->getOperand(1))) + return false; + + IVSrc = IVOperand->getOperand(0); + // IVSrc must be the (SCEVable) IV, since the other operand is const. + assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand"); + + ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1)); + if (UseInst->getOpcode() == Instruction::LShr) { + // Get a constant for the divisor. See createSCEV. + uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth(); + if (D->getValue().uge(BitWidth)) + return false; + + D = ConstantInt::get(UseInst->getContext(), + APInt(BitWidth, 1).shl(D->getZExtValue())); + } + FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D)); + } + // We have something that might fold it's operand. Compare SCEVs. + if (!SE->isSCEVable(UseInst->getType())) + return false; + + // Bypass the operand if SCEV can prove it has no effect. + if (SE->getSCEV(UseInst) != FoldedExpr) + return false; + + DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand + << " -> " << *UseInst << '\n'); + + UseInst->setOperand(OperIdx, IVSrc); + assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper"); + + ++NumElimOperand; + Changed = true; + if (IVOperand->use_empty()) + DeadInsts.push_back(IVOperand); + return true; +} + /// pushIVUsers - Add all uses of Def to the current IV's worklist. /// static void pushIVUsers( @@ -1394,6 +1457,8 @@ void IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) { // Bypass back edges to avoid extra work. if (UseOper.first == CurrIV) continue; + FoldIVUser(UseOper.first, UseOper.second); + if (EliminateIVUser(UseOper.first, UseOper.second)) { pushIVUsers(UseOper.second, Simplified, SimpleIVUsers); continue; |