#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Loop *L;
LoopInfo *LI;
ScalarEvolution *SE;
- const DataLayout *DL; // May be NULL
+ DominatorTree *DT;
SmallVectorImpl<WeakVH> &DeadInsts;
bool Changed;
public:
- SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LoopInfo *LI,
- const DataLayout *DL, SmallVectorImpl<WeakVH> &Dead,
- IVUsers *IVU = nullptr)
- : L(Loop), LI(LI), SE(SE), DL(DL), DeadInsts(Dead), Changed(false) {
+ SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
+ LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
+ : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
assert(LI && "IV simplification requires LoopInfo");
}
/// Iteratively perform simplification on a worklist of users of the
/// specified induction variable. This is the top-level driver that applies
- /// all simplicitions to users of an IV.
+ /// all simplifications to users of an IV.
void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
+ bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
+
bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
++NumElimOperand;
Changed = true;
if (IVOperand->use_empty())
- DeadInsts.push_back(IVOperand);
+ DeadInsts.emplace_back(IVOperand);
return IVSrc;
}
S = SE->getSCEVAtScope(S, ICmpLoop);
X = SE->getSCEVAtScope(X, ICmpLoop);
+ ICmpInst::Predicate InvariantPredicate;
+ const SCEV *InvariantLHS, *InvariantRHS;
+
// If the condition is always true or always false, replace it with
// a constant value.
- if (SE->isKnownPredicate(Pred, S, X))
+ if (SE->isKnownPredicate(Pred, S, X)) {
ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
- else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
+ DeadInsts.emplace_back(ICmp);
+ DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
+ } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
- else
+ DeadInsts.emplace_back(ICmp);
+ DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
+ } else if (isa<PHINode>(IVOperand) &&
+ SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
+ InvariantPredicate, InvariantLHS,
+ InvariantRHS)) {
+
+ // Rewrite the comparison to a loop invariant comparison if it can be done
+ // cheaply, where cheaply means "we don't need to emit any new
+ // instructions".
+
+ Value *NewLHS = nullptr, *NewRHS = nullptr;
+
+ if (S == InvariantLHS || X == InvariantLHS)
+ NewLHS =
+ ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
+
+ if (S == InvariantRHS || X == InvariantRHS)
+ NewRHS =
+ ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
+
+ for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
+ if (NewLHS && NewRHS)
+ break;
+
+ const SCEV *IncomingS = SE->getSCEV(Incoming);
+
+ if (!NewLHS && IncomingS == InvariantLHS)
+ NewLHS = Incoming;
+ if (!NewRHS && IncomingS == InvariantRHS)
+ NewRHS = Incoming;
+ }
+
+ if (!NewLHS || !NewRHS)
+ // We could not find an existing value to replace either LHS or RHS.
+ // Generating new instructions has subtler tradeoffs, so avoid doing that
+ // for now.
+ return;
+
+ DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
+ ICmp->setPredicate(InvariantPredicate);
+ ICmp->setOperand(0, NewLHS);
+ ICmp->setOperand(1, NewRHS);
+ } else
return;
- DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
++NumElimCmp;
Changed = true;
- DeadInsts.push_back(ICmp);
}
/// SimplifyIVUsers helper for eliminating useless
Rem->replaceAllUsesWith(Rem->getOperand(0));
else {
// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
- const SCEV *LessOne =
- SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
+ const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
if (IsSigned && !SE->isKnownNonNegative(LessOne))
return;
DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
++NumElimRem;
Changed = true;
- DeadInsts.push_back(Rem);
+ DeadInsts.emplace_back(Rem);
}
-/// Eliminate an operation that consumes a simple IV and has
-/// no observable side-effect given the range of IV values.
-/// IVOperand is guaranteed SCEVable, but UseInst may not be.
+/// Eliminate an operation that consumes a simple IV and has no observable
+/// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
+/// but UseInst may not be.
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
Instruction *IVOperand) {
if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
}
}
- // Eliminate any operation that SCEV can prove is an identity function.
+ if (eliminateIdentitySCEV(UseInst, IVOperand))
+ return true;
+
+ return false;
+}
+
+/// Eliminate any operation that SCEV can prove is an identity function.
+bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
+ Instruction *IVOperand) {
if (!SE->isSCEVable(UseInst->getType()) ||
(UseInst->getType() != IVOperand->getType()) ||
(SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
return false;
+ // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
+ // dominator tree, even if X is an operand to Y. For instance, in
+ //
+ // %iv = phi i32 {0,+,1}
+ // br %cond, label %left, label %merge
+ //
+ // left:
+ // %X = add i32 %iv, 0
+ // br label %merge
+ //
+ // merge:
+ // %M = phi (%X, %iv)
+ //
+ // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
+ // %M.replaceAllUsesWith(%X) would be incorrect.
+
+ if (isa<PHINode>(UseInst))
+ // If UseInst is not a PHI node then we know that IVOperand dominates
+ // UseInst directly from the legality of SSA.
+ if (!DT || !DT->dominates(IVOperand, UseInst))
+ return false;
+
+ if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
+ return false;
+
DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
UseInst->replaceAllUsesWith(IVOperand);
++NumElimIdentity;
Changed = true;
- DeadInsts.push_back(UseInst);
+ DeadInsts.emplace_back(UseInst);
return true;
}
bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
Value *IVOperand) {
- // Currently we only handle instructions of the form "add <indvar> <value>"
- unsigned Op = BO->getOpcode();
- if (Op != Instruction::Add)
+ // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
+ if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
return false;
- // If BO is already both nuw and nsw then there is nothing left to do
- if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
+ const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
+ SCEV::NoWrapFlags);
+
+ switch (BO->getOpcode()) {
+ default:
return false;
- IntegerType *IT = cast<IntegerType>(IVOperand->getType());
- Value *OtherOperand = nullptr;
- if (BO->getOperand(0) == IVOperand) {
- OtherOperand = BO->getOperand(1);
- } else {
- assert(BO->getOperand(1) == IVOperand && "only other use!");
- OtherOperand = BO->getOperand(0);
+ case Instruction::Add:
+ GetExprForBO = &ScalarEvolution::getAddExpr;
+ break;
+
+ case Instruction::Sub:
+ GetExprForBO = &ScalarEvolution::getMinusSCEV;
+ break;
+
+ case Instruction::Mul:
+ GetExprForBO = &ScalarEvolution::getMulExpr;
+ break;
}
- bool Changed = false;
- const SCEV *OtherOpSCEV = SE->getSCEV(OtherOperand);
- if (OtherOpSCEV == SE->getCouldNotCompute())
- return false;
+ unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
+ Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
+ const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
+ const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
- const SCEV *IVOpSCEV = SE->getSCEV(IVOperand);
- const SCEV *ZeroSCEV = SE->getConstant(IVOpSCEV->getType(), 0);
+ bool Changed = false;
- if (!BO->hasNoSignedWrap()) {
- // Upgrade the add to an "add nsw" if we can prove that it will never
- // sign-overflow or sign-underflow.
-
- const SCEV *SignedMax =
- SE->getConstant(APInt::getSignedMaxValue(IT->getBitWidth()));
- const SCEV *SignedMin =
- SE->getConstant(APInt::getSignedMinValue(IT->getBitWidth()));
-
- // The addition "IVOperand + OtherOp" does not sign-overflow if the result
- // is sign-representable in 2's complement in the given bit-width.
- //
- // If OtherOp is SLT 0, then for an IVOperand in [SignedMin - OtherOp,
- // SignedMax], "IVOperand + OtherOp" is in [SignedMin, SignedMax + OtherOp].
- // Everything in [SignedMin, SignedMax + OtherOp] is representable since
- // SignedMax + OtherOp is at least -1.
- //
- // If OtherOp is SGE 0, then for an IVOperand in [SignedMin, SignedMax -
- // OtherOp], "IVOperand + OtherOp" is in [SignedMin + OtherOp, SignedMax].
- // Everything in [SignedMin + OtherOp, SignedMax] is representable since
- // SignedMin + OtherOp is at most -1.
- //
- // It follows that for all values of IVOperand in [SignedMin - smin(0,
- // OtherOp), SignedMax - smax(0, OtherOp)] the result of the add is
- // representable (i.e. there is no sign-overflow).
-
- const SCEV *UpperDelta = SE->getSMaxExpr(ZeroSCEV, OtherOpSCEV);
- const SCEV *UpperLimit = SE->getMinusSCEV(SignedMax, UpperDelta);
-
- bool NeverSignedOverflows =
- SE->isKnownPredicate(ICmpInst::ICMP_SLE, IVOpSCEV, UpperLimit);
-
- if (NeverSignedOverflows) {
- const SCEV *LowerDelta = SE->getSMinExpr(ZeroSCEV, OtherOpSCEV);
- const SCEV *LowerLimit = SE->getMinusSCEV(SignedMin, LowerDelta);
-
- bool NeverSignedUnderflows =
- SE->isKnownPredicate(ICmpInst::ICMP_SGE, IVOpSCEV, LowerLimit);
- if (NeverSignedUnderflows) {
- BO->setHasNoSignedWrap(true);
- Changed = true;
- }
+ if (!BO->hasNoUnsignedWrap()) {
+ const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
+ const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
+ SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
+ SCEV::FlagAnyWrap);
+ if (ExtendAfterOp == OpAfterExtend) {
+ BO->setHasNoUnsignedWrap();
+ SE->forgetValue(BO);
+ Changed = true;
}
}
- if (!BO->hasNoUnsignedWrap()) {
- // Upgrade the add computing "IVOperand + OtherOp" to an "add nuw" if we can
- // prove that it will never unsigned-overflow (i.e. the result will always
- // be representable in the given bit-width).
- //
- // "IVOperand + OtherOp" is unsigned-representable in 2's complement iff it
- // does not produce a carry. "IVOperand + OtherOp" produces no carry iff
- // IVOperand ULE (UnsignedMax - OtherOp).
-
- const SCEV *UnsignedMax =
- SE->getConstant(APInt::getMaxValue(IT->getBitWidth()));
- const SCEV *UpperLimit = SE->getMinusSCEV(UnsignedMax, OtherOpSCEV);
-
- bool NeverUnsignedOverflows =
- SE->isKnownPredicate(ICmpInst::ICMP_ULE, IVOpSCEV, UpperLimit);
-
- if (NeverUnsignedOverflows) {
- BO->setHasNoUnsignedWrap(true);
+ if (!BO->hasNoSignedWrap()) {
+ const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
+ const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
+ SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
+ SCEV::FlagAnyWrap);
+ if (ExtendAfterOp == OpAfterExtend) {
+ BO->setHasNoSignedWrap();
+ SE->forgetValue(BO);
Changed = true;
}
}
"Bad add instruction created from overflow intrinsic.");
AddVal->replaceAllUsesWith(AddInst);
- DeadInsts.push_back(AddVal);
+ DeadInsts.emplace_back(AddVal);
return AddInst;
}
/// This algorithm does not require IVUsers analysis. Instead, it simplifies
/// instructions in-place during analysis. Rather than rewriting induction
/// variables bottom-up from their users, it transforms a chain of IVUsers
-/// top-down, updating the IR only when it encouters a clear optimization
-/// opportunitiy.
+/// top-down, updating the IR only when it encounters a clear optimization
+/// opportunity.
///
/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
///
/// Simplify instructions that use this induction variable
/// by using ScalarEvolution to analyze the IV's recurrence.
-bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
- SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
+bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
+ LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
{
- DataLayoutPass *DLP = LPM->getAnalysisIfAvailable<DataLayoutPass>();
LoopInfo *LI = &LPM->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI,
- DLP ? &DLP->getDataLayout() : nullptr, Dead);
+
+ SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
SIV.simplifyUsers(CurrIV, V);
return SIV.hasChanged();
}
/// Simplify users of induction variables within this
/// loop. This does not actually change or add IVs.
-bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM,
- SmallVectorImpl<WeakVH> &Dead) {
+bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
+ LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead) {
bool Changed = false;
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
- Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
+ Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LPM, Dead);
}
return Changed;
}
projects / oota-llvm.git / blobdiff