X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyIndVar.cpp;h=58715fa4bef1aafb4abdaafec8787b0e9be235a0;hb=ca9d3aa064061bc7f3fc7d31bd77163024c7d3c7;hp=5ee1eb189799faefc37e15146d51576392d4936c;hpb=24f48ece526d81e7a3138f4cff57171b7de9e02f;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyIndVar.cpp b/lib/Transforms/Utils/SimplifyIndVar.cpp index 5ee1eb18979..58715fa4bef 100644 --- a/lib/Transforms/Utils/SimplifyIndVar.cpp +++ b/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -13,56 +13,50 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "indvars" - -#include "llvm/Instructions.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/IVUsers.h" +#include "llvm/Transforms/Utils/SimplifyIndVar.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/SimplifyIndVar.h" -#include "llvm/Target/TargetData.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" using namespace llvm; +#define DEBUG_TYPE "indvars" + STATISTIC(NumElimIdentity, "Number of IV identities eliminated"); STATISTIC(NumElimOperand, "Number of IV operands folded into a use"); STATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); namespace { - /// SimplifyIndvar - This is a utility for simplifying induction variables + /// This is a utility for simplifying induction variables /// based on ScalarEvolution. It is the primary instrument of the /// IndvarSimplify pass, but it may also be directly invoked to cleanup after /// other loop passes that preserve SCEV. class SimplifyIndvar { Loop *L; LoopInfo *LI; - DominatorTree *DT; ScalarEvolution *SE; - IVUsers *IU; // NULL for DisableIVRewrite - const TargetData *TD; // May be NULL + DominatorTree *DT; SmallVectorImpl &DeadInsts; bool Changed; public: - SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead, IVUsers *IVU = NULL) : - L(Loop), - LI(LPM->getAnalysisIfAvailable()), - SE(SE), - IU(IVU), - TD(LPM->getAnalysisIfAvailable()), - DeadInsts(Dead), - Changed(false) { + SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI,SmallVectorImpl &Dead) + : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) { assert(LI && "IV simplification requires LoopInfo"); } @@ -70,19 +64,25 @@ namespace { /// 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. - void simplifyUsers(PHINode *CurrIV, IVVisitor *V = NULL); + /// 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, bool IsSigned); + bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand); + + Instruction *splitOverflowIntrinsic(Instruction *IVUser, + const DominatorTree *DT); }; } -/// foldIVUser - Fold an IV operand into its use. This removes increments of an +/// Fold an IV operand into its use. This removes increments of an /// aligned IV when used by a instruction that ignores the low bits. /// /// IVOperand is guaranteed SCEVable, but UseInst may not be. @@ -91,25 +91,25 @@ namespace { /// be folded (in case more folding opportunities have been exposed). /// Otherwise return null. Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) { - Value *IVSrc = 0; + Value *IVSrc = nullptr; unsigned OperIdx = 0; - const SCEV *FoldedExpr = 0; + const SCEV *FoldedExpr = nullptr; switch (UseInst->getOpcode()) { default: - return 0; + return nullptr; 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(UseInst->getOperand(1))) - return 0; + return nullptr; // Attempt to fold a binary operator with constant operand. // e.g. ((I + 1) >> 2) => I >> 2 - if (IVOperand->getNumOperands() != 2 || - !isa(IVOperand->getOperand(1))) - return 0; + if (!isa(IVOperand) + || !isa(IVOperand->getOperand(1))) + return nullptr; IVSrc = IVOperand->getOperand(0); // IVSrc must be the (SCEVable) IV, since the other operand is const. @@ -120,20 +120,20 @@ Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) // Get a constant for the divisor. See createSCEV. uint32_t BitWidth = cast(UseInst->getType())->getBitWidth(); if (D->getValue().uge(BitWidth)) - return 0; + return nullptr; D = ConstantInt::get(UseInst->getContext(), - APInt(BitWidth, 1).shl(D->getZExtValue())); + APInt::getOneBitSet(BitWidth, 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 0; + return nullptr; // Bypass the operand if SCEV can prove it has no effect. if (SE->getSCEV(UseInst) != FoldedExpr) - return 0; + return nullptr; DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand << " -> " << *UseInst << '\n'); @@ -144,11 +144,11 @@ Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) ++NumElimOperand; Changed = true; if (IVOperand->use_empty()) - DeadInsts.push_back(IVOperand); + DeadInsts.emplace_back(IVOperand); return IVSrc; } -/// eliminateIVComparison - SimplifyIVUsers helper for eliminating useless +/// SimplifyIVUsers helper for eliminating useless /// comparisons against an induction variable. void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { unsigned IVOperIdx = 0; @@ -169,22 +169,68 @@ void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { 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(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(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); } -/// eliminateIVRemainder - SimplifyIVUsers helper for eliminating useless +/// SimplifyIVUsers helper for eliminating useless /// remainder operations operating on an induction variable. void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand, @@ -210,8 +256,7 @@ void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, 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; @@ -221,8 +266,7 @@ void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, return; ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, - Rem->getOperand(0), Rem->getOperand(1), - "tmp"); + Rem->getOperand(0), Rem->getOperand(1)); SelectInst *Sel = SelectInst::Create(ICmp, ConstantInt::get(Rem->getType(), 0), @@ -230,20 +274,15 @@ void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, Rem->replaceAllUsesWith(Sel); } - // Inform IVUsers about the new users. - if (IU) { - if (Instruction *I = dyn_cast(Rem->getOperand(0))) - IU->AddUsersIfInteresting(I); - } DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); ++NumElimRem; Changed = true; - DeadInsts.push_back(Rem); + DeadInsts.emplace_back(Rem); } -/// eliminateIVUser - 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(UseInst)) { @@ -258,42 +297,199 @@ bool SimplifyIndvar::eliminateIVUser(Instruction *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(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; } -/// pushIVUsers - Add all uses of Def to the current IV's worklist. +/// Annotate BO with nsw / nuw if it provably does not signed-overflow / +/// unsigned-overflow. Returns true if anything changed, false otherwise. +bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO, + Value *IVOperand) { + + // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`. + if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap()) + return false; + + const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *, + SCEV::NoWrapFlags); + + switch (BO->getOpcode()) { + default: + return false; + + case Instruction::Add: + GetExprForBO = &ScalarEvolution::getAddExpr; + break; + + case Instruction::Sub: + GetExprForBO = &ScalarEvolution::getMinusSCEV; + break; + + case Instruction::Mul: + GetExprForBO = &ScalarEvolution::getMulExpr; + break; + } + + unsigned BitWidth = cast(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)); + + bool Changed = false; + + 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->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; + } + } + + return Changed; +} + +/// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow +/// analysis and optimization. /// +/// \return A new value representing the non-overflowing add if possible, +/// otherwise return the original value. +Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser, + const DominatorTree *DT) { + IntrinsicInst *II = dyn_cast(IVUser); + if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow) + return IVUser; + + // Find a branch guarded by the overflow check. + BranchInst *Branch = nullptr; + Instruction *AddVal = nullptr; + for (User *U : II->users()) { + if (ExtractValueInst *ExtractInst = dyn_cast(U)) { + if (ExtractInst->getNumIndices() != 1) + continue; + if (ExtractInst->getIndices()[0] == 0) + AddVal = ExtractInst; + else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse()) + Branch = dyn_cast(ExtractInst->user_back()); + } + } + if (!AddVal || !Branch) + return IVUser; + + BasicBlock *ContinueBB = Branch->getSuccessor(1); + if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB)) + return IVUser; + + // Check if all users of the add are provably NSW. + bool AllNSW = true; + for (Use &U : AddVal->uses()) { + if (Instruction *UseInst = dyn_cast(U.getUser())) { + BasicBlock *UseBB = UseInst->getParent(); + if (PHINode *PHI = dyn_cast(UseInst)) + UseBB = PHI->getIncomingBlock(U); + if (!DT->dominates(ContinueBB, UseBB)) { + AllNSW = false; + break; + } + } + } + if (!AllNSW) + return IVUser; + + // Go for it... + IRBuilder<> Builder(IVUser); + Instruction *AddInst = dyn_cast( + Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1))); + + // The caller expects the new add to have the same form as the intrinsic. The + // IV operand position must be the same. + assert((AddInst->getOpcode() == Instruction::Add && + AddInst->getOperand(0) == II->getOperand(0)) && + "Bad add instruction created from overflow intrinsic."); + + AddVal->replaceAllUsesWith(AddInst); + DeadInsts.emplace_back(AddVal); + return AddInst; +} + +/// Add all uses of Def to the current IV's worklist. static void pushIVUsers( Instruction *Def, SmallPtrSet &Simplified, SmallVectorImpl< std::pair > &SimpleIVUsers) { - for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end(); - UI != E; ++UI) { - Instruction *User = cast(*UI); + for (User *U : Def->users()) { + Instruction *UI = cast(U); // Avoid infinite or exponential worklist processing. // Also ensure unique worklist users. // If Def is a LoopPhi, it may not be in the Simplified set, so check for // self edges first. - if (User != Def && Simplified.insert(User)) - SimpleIVUsers.push_back(std::make_pair(User, Def)); + if (UI != Def && Simplified.insert(UI).second) + SimpleIVUsers.push_back(std::make_pair(UI, Def)); } } -/// isSimpleIVUser - Return true if this instruction generates a simple SCEV +/// Return true if this instruction generates a simple SCEV /// expression in terms of that IV. /// /// This is similar to IVUsers' isInteresting() but processes each instruction @@ -314,15 +510,15 @@ static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) { return false; } -/// simplifyUsers - Iteratively perform simplification on a worklist of users +/// Iteratively perform simplification on a worklist of users /// of the specified induction variable. Each successive simplification may push /// more users which may themselves be candidates for simplification. /// /// 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. /// @@ -344,8 +540,16 @@ void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) { while (!SimpleIVUsers.empty()) { std::pair UseOper = SimpleIVUsers.pop_back_val(); + Instruction *UseInst = UseOper.first; + // Bypass back edges to avoid extra work. - if (UseOper.first == CurrIV) continue; + if (UseInst == CurrIV) continue; + + if (V && V->shouldSplitOverflowInstrinsics()) { + UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree()); + if (!UseInst) + continue; + } Instruction *IVOperand = UseOper.second; for (unsigned N = 0; IVOperand; ++N) { @@ -363,6 +567,16 @@ void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) { pushIVUsers(IVOperand, Simplified, SimpleIVUsers); continue; } + + if (BinaryOperator *BO = dyn_cast(UseOper.first)) { + if (isa(BO) && + strengthenOverflowingOperation(BO, IVOperand)) { + // re-queue uses of the now modified binary operator and fall + // through to the checks that remain. + pushIVUsers(IVOperand, Simplified, SimpleIVUsers); + } + } + CastInst *Cast = dyn_cast(UseOper.first); if (V && Cast) { V->visitCast(Cast); @@ -376,58 +590,29 @@ void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) { namespace llvm { -/// simplifyUsersOfIV - Simplify instructions that use this induction variable +void IVVisitor::anchor() { } + +/// 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 &Dead, IVVisitor *V) +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead, IVVisitor *V) { - LoopInfo *LI = &LPM->getAnalysis(); - SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead); + LoopInfo *LI = &LPM->getAnalysis().getLoopInfo(); + + SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead); SIV.simplifyUsers(CurrIV, V); return SIV.hasChanged(); } -/// simplifyLoopIVs - Simplify users of induction variables within this +/// 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 &Dead) { +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead) { bool Changed = false; for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { - Changed |= simplifyUsersOfIV(cast(I), SE, LPM, Dead); + Changed |= simplifyUsersOfIV(cast(I), SE, DT, LPM, Dead); } return Changed; } -/// simplifyIVUsers - Perform simplification on instructions recorded by the -/// IVUsers pass. -/// -/// This is the old approach to IV simplification to be replaced by -/// SimplifyLoopIVs. -bool simplifyIVUsers(IVUsers *IU, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead) { - SimplifyIndvar SIV(IU->getLoop(), SE, LPM, Dead); - - // Each round of simplification involves a round of eliminating operations - // followed by a round of widening IVs. A single IVUsers worklist is used - // across all rounds. The inner loop advances the user. If widening exposes - // more uses, then another pass through the outer loop is triggered. - for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) { - Instruction *UseInst = I->getUser(); - Value *IVOperand = I->getOperandValToReplace(); - - if (ICmpInst *ICmp = dyn_cast(UseInst)) { - SIV.eliminateIVComparison(ICmp, IVOperand); - continue; - } - if (BinaryOperator *Rem = dyn_cast(UseInst)) { - bool IsSigned = Rem->getOpcode() == Instruction::SRem; - if (IsSigned || Rem->getOpcode() == Instruction::URem) { - SIV.eliminateIVRemainder(Rem, IVOperand, IsSigned); - continue; - } - } - } - return SIV.hasChanged(); -} - } // namespace llvm