diff options
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 761 |
1 files changed, 630 insertions, 131 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 09d569a..04ee7c8 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -52,20 +52,30 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Target/TargetData.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" using namespace llvm; STATISTIC(NumRemoved , "Number of aux indvars removed"); +STATISTIC(NumWidened , "Number of indvars widened"); STATISTIC(NumInserted, "Number of canonical indvars added"); STATISTIC(NumReplaced, "Number of exit values replaced"); STATISTIC(NumLFTR , "Number of loop exit tests replaced"); +STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); +STATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); +STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); + +// DisableIVRewrite mode currently affects IVUsers, so is defined in libAnalysis +// and referenced here. +namespace llvm { + extern bool DisableIVRewrite; +} namespace { class IndVarSimplify : public LoopPass { @@ -73,12 +83,13 @@ namespace { LoopInfo *LI; ScalarEvolution *SE; DominatorTree *DT; + TargetData *TD; SmallVector<WeakVH, 16> DeadInsts; bool Changed; public: static char ID; // Pass identification, replacement for typeid - IndVarSimplify() : LoopPass(ID) { + IndVarSimplify() : LoopPass(ID), IU(0), LI(0), SE(0), DT(0), TD(0) { initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); } @@ -101,15 +112,18 @@ namespace { private: bool isValidRewrite(Value *FromVal, Value *ToVal); - void EliminateIVComparisons(); - void EliminateIVRemainders(); + void SimplifyIVUsers(SCEVExpander &Rewriter); + void EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); + void EliminateIVRemainder(BinaryOperator *Rem, + Value *IVOperand, + bool IsSigned, + PHINode *IVPhi); void RewriteNonIntegerIVs(Loop *L); ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, - PHINode *IndVar, - BasicBlock *ExitingBlock, - BranchInst *BI, - SCEVExpander &Rewriter); + PHINode *IndVar, + SCEVExpander &Rewriter); + void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); @@ -122,7 +136,7 @@ namespace { char IndVarSimplify::ID = 0; INITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", - "Canonicalize Induction Variables", false, false) + "Induction Variable Simplification", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTree) INITIALIZE_PASS_DEPENDENCY(LoopInfo) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) @@ -130,7 +144,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LCSSA) INITIALIZE_PASS_DEPENDENCY(IVUsers) INITIALIZE_PASS_END(IndVarSimplify, "indvars", - "Canonicalize Induction Variables", false, false) + "Induction Variable Simplification", false, false) Pass *llvm::createIndVarSimplifyPass() { return new IndVarSimplify(); @@ -183,17 +197,23 @@ bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { return true; } -/// LinearFunctionTestReplace - This method rewrites the exit condition of the -/// loop to be a canonical != comparison against the incremented loop induction -/// variable. This pass is able to rewrite the exit tests of any loop where the -/// SCEV analysis can determine a loop-invariant trip count of the loop, which -/// is actually a much broader range than just linear tests. -ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, - const SCEV *BackedgeTakenCount, - PHINode *IndVar, - BasicBlock *ExitingBlock, - BranchInst *BI, - SCEVExpander &Rewriter) { +/// 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. +static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { + const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); + if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || + BackedgeTakenCount->isZero()) + return false; + + if (!L->getExitingBlock()) + return false; + + // Can't rewrite non-branch yet. + BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); + 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 @@ -201,23 +221,68 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, // rewriting the loop. if (isa<SCEVUDivExpr>(BackedgeTakenCount)) { ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); - if (!OrigCond) return 0; + 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 0; + return false; } } + return true; +} + +/// getBackedgeIVType - Get the widest type used by the loop test after peeking +/// through Truncs. +/// +/// TODO: Unnecessary once LinearFunctionTestReplace is removed. +static const Type *getBackedgeIVType(Loop *L) { + if (!L->getExitingBlock()) + return 0; + + // Can't rewrite non-branch yet. + BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); + if (!BI) + return 0; + + ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); + if (!Cond) + return 0; + + const Type *Ty = 0; + for(User::op_iterator OI = Cond->op_begin(), OE = Cond->op_end(); + OI != OE; ++OI) { + assert((!Ty || Ty == (*OI)->getType()) && "bad icmp operand types"); + TruncInst *Trunc = dyn_cast<TruncInst>(*OI); + if (!Trunc) + continue; + + return Trunc->getSrcTy(); + } + return Ty; +} + +/// LinearFunctionTestReplace - This method rewrites the exit condition of the +/// loop to be a canonical != comparison against the incremented loop induction +/// variable. This pass is able to rewrite the exit tests of any loop where the +/// SCEV analysis can determine a loop-invariant trip count of the loop, which +/// is actually a much broader range than just linear tests. +ICmpInst *IndVarSimplify:: +LinearFunctionTestReplace(Loop *L, + const SCEV *BackedgeTakenCount, + PHINode *IndVar, + SCEVExpander &Rewriter) { + assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); + BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); // If the exiting block is not the same as the backedge block, we must compare // against the preincremented value, otherwise we prefer to compare against // the post-incremented value. Value *CmpIndVar; const SCEV *RHS = BackedgeTakenCount; - if (ExitingBlock == L->getLoopLatch()) { + if (L->getExitingBlock() == L->getLoopLatch()) { // Add one to the "backedge-taken" count to get the trip count. // If this addition may overflow, we have to be more pessimistic and // cast the induction variable before doing the add. @@ -240,7 +305,7 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, // The BackedgeTaken expression contains the number of times that the // backedge branches to the loop header. This is one less than the // number of times the loop executes, so use the incremented indvar. - CmpIndVar = IndVar->getIncomingValueForBlock(ExitingBlock); + CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock()); } else { // We have to use the preincremented value... RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, @@ -418,96 +483,519 @@ void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { SE->forgetLoop(L); } -void IndVarSimplify::EliminateIVComparisons() { - // Look for ICmp users. - for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E; ++I) { - IVStrideUse &UI = *I; - ICmpInst *ICmp = dyn_cast<ICmpInst>(UI.getUser()); - if (!ICmp) continue; - - bool Swapped = UI.getOperandValToReplace() == ICmp->getOperand(1); - ICmpInst::Predicate Pred = ICmp->getPredicate(); - if (Swapped) Pred = ICmpInst::getSwappedPredicate(Pred); - - // Get the SCEVs for the ICmp operands. - const SCEV *S = IU->getReplacementExpr(UI); - const SCEV *X = SE->getSCEV(ICmp->getOperand(!Swapped)); - - // Simplify unnecessary loops away. - const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); - S = SE->getSCEVAtScope(S, ICmpLoop); - X = SE->getSCEVAtScope(X, ICmpLoop); - - // If the condition is always true or always false, replace it with - // a constant value. - if (SE->isKnownPredicate(Pred, S, X)) - ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); - else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) - ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); - else - continue; +namespace { + // Collect information about induction variables that are used by sign/zero + // extend operations. This information is recorded by CollectExtend and + // provides the input to WidenIV. + struct WideIVInfo { + const Type *WidestNativeType; // Widest integer type created [sz]ext + bool IsSigned; // Was an sext user seen before a zext? + + WideIVInfo() : WidestNativeType(0), IsSigned(false) {} + }; + typedef std::map<PHINode *, WideIVInfo> WideIVMap; +} + +/// CollectExtend - Update information about the induction variable that is +/// extended by this sign or zero extend operation. This is used to determine +/// the final width of the IV before actually widening it. +static void CollectExtend(CastInst *Cast, PHINode *Phi, bool IsSigned, + WideIVMap &IVMap, ScalarEvolution *SE, + const TargetData *TD) { + const Type *Ty = Cast->getType(); + uint64_t Width = SE->getTypeSizeInBits(Ty); + if (TD && !TD->isLegalInteger(Width)) + return; - DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); - DeadInsts.push_back(ICmp); + WideIVInfo &IVInfo = IVMap[Phi]; + if (!IVInfo.WidestNativeType) { + IVInfo.WidestNativeType = SE->getEffectiveSCEVType(Ty); + IVInfo.IsSigned = IsSigned; + return; } + + // We extend the IV to satisfy the sign of its first user, arbitrarily. + if (IVInfo.IsSigned != IsSigned) + return; + + if (Width > SE->getTypeSizeInBits(IVInfo.WidestNativeType)) + IVInfo.WidestNativeType = SE->getEffectiveSCEVType(Ty); } -void IndVarSimplify::EliminateIVRemainders() { - // Look for SRem and URem users. - for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E; ++I) { - IVStrideUse &UI = *I; - BinaryOperator *Rem = dyn_cast<BinaryOperator>(UI.getUser()); - if (!Rem) continue; +namespace { +/// WidenIV - The goal of this transform is to remove sign and zero extends +/// without creating any new induction variables. To do this, it creates a new +/// phi of the wider type and redirects all users, either removing extends or +/// inserting truncs whenever we stop propagating the type. +/// +class WidenIV { + PHINode *OrigPhi; + const Type *WideType; + bool IsSigned; + + IVUsers *IU; + LoopInfo *LI; + Loop *L; + ScalarEvolution *SE; + DominatorTree *DT; + SmallVectorImpl<WeakVH> &DeadInsts; + + PHINode *WidePhi; + Instruction *WideInc; + const SCEV *WideIncExpr; + + SmallPtrSet<Instruction*,16> Processed; + +public: + WidenIV(PHINode *PN, const WideIVInfo &IVInfo, IVUsers *IUsers, + LoopInfo *LInfo, ScalarEvolution *SEv, DominatorTree *DTree, + SmallVectorImpl<WeakVH> &DI) : + OrigPhi(PN), + WideType(IVInfo.WidestNativeType), + IsSigned(IVInfo.IsSigned), + IU(IUsers), + LI(LInfo), + L(LI->getLoopFor(OrigPhi->getParent())), + SE(SEv), + DT(DTree), + DeadInsts(DI), + WidePhi(0), + WideInc(0), + WideIncExpr(0) { + assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); + } - bool isSigned = Rem->getOpcode() == Instruction::SRem; - if (!isSigned && Rem->getOpcode() != Instruction::URem) - continue; + bool CreateWideIV(SCEVExpander &Rewriter); - // We're only interested in the case where we know something about - // the numerator. - if (UI.getOperandValToReplace() != Rem->getOperand(0)) - continue; +protected: + Instruction *CloneIVUser(Instruction *NarrowUse, + Instruction *NarrowDef, + Instruction *WideDef); - // Get the SCEVs for the ICmp operands. - const SCEV *S = SE->getSCEV(Rem->getOperand(0)); - const SCEV *X = SE->getSCEV(Rem->getOperand(1)); - - // Simplify unnecessary loops away. - const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); - S = SE->getSCEVAtScope(S, ICmpLoop); - X = SE->getSCEVAtScope(X, ICmpLoop); - - // i % n --> i if i is in [0,n). - if ((!isSigned || SE->isKnownNonNegative(S)) && - SE->isKnownPredicate(isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - S, X)) - 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)); - if ((!isSigned || SE->isKnownNonNegative(LessOne)) && - SE->isKnownPredicate(isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - LessOne, X)) { - ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, - Rem->getOperand(0), Rem->getOperand(1), - "tmp"); - SelectInst *Sel = - SelectInst::Create(ICmp, - ConstantInt::get(Rem->getType(), 0), - Rem->getOperand(0), "tmp", Rem); - Rem->replaceAllUsesWith(Sel); - } else + const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); + + Instruction *WidenIVUse(Instruction *NarrowUse, + Instruction *NarrowDef, + Instruction *WideDef); +}; +} // anonymous namespace + +/// SimplifyIVUsers - Iteratively perform simplification on IVUsers within this +/// loop. IVUsers is treated as a worklist. Each successive simplification may +/// push more users which may themselves be candidates for simplification. +/// +void IndVarSimplify::SimplifyIVUsers(SCEVExpander &Rewriter) { + WideIVMap IVMap; + + // 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(), E = IU->end(); I != E;) { + for(; I != E; ++I) { + Instruction *UseInst = I->getUser(); + Value *IVOperand = I->getOperandValToReplace(); + + if (DisableIVRewrite) { + if (CastInst *Cast = dyn_cast<CastInst>(UseInst)) { + bool IsSigned = Cast->getOpcode() == Instruction::SExt; + if (IsSigned || Cast->getOpcode() == Instruction::ZExt) { + CollectExtend(Cast, I->getPhi(), IsSigned, IVMap, SE, TD); + continue; + } + } + } + if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { + EliminateIVComparison(ICmp, IVOperand); continue; + } + if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { + bool IsSigned = Rem->getOpcode() == Instruction::SRem; + if (IsSigned || Rem->getOpcode() == Instruction::URem) { + EliminateIVRemainder(Rem, IVOperand, IsSigned, I->getPhi()); + continue; + } + } + } + for (WideIVMap::const_iterator I = IVMap.begin(), E = IVMap.end(); + I != E; ++I) { + WidenIV Widener(I->first, I->second, IU, LI, SE, DT, DeadInsts); + if (Widener.CreateWideIV(Rewriter)) + Changed = true; } + } +} - // Inform IVUsers about the new users. - if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) - IU->AddUsersIfInteresting(I); +static Value *getExtend( Value *NarrowOper, const Type *WideType, + bool IsSigned, IRBuilder<> &Builder) { + return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : + Builder.CreateZExt(NarrowOper, WideType); +} - DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); - DeadInsts.push_back(Rem); +/// CloneIVUser - Instantiate a wide operation to replace a narrow +/// operation. This only needs to handle operations that can evaluation to +/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. +Instruction *WidenIV::CloneIVUser(Instruction *NarrowUse, + Instruction *NarrowDef, + Instruction *WideDef) { + unsigned Opcode = NarrowUse->getOpcode(); + switch (Opcode) { + default: + return 0; + case Instruction::Add: + case Instruction::Mul: + case Instruction::UDiv: + case Instruction::Sub: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + DEBUG(dbgs() << "Cloning IVUser: " << *NarrowUse << "\n"); + + IRBuilder<> Builder(NarrowUse); + + // Replace NarrowDef operands with WideDef. Otherwise, we don't know + // anything about the narrow operand yet so must insert a [sz]ext. It is + // probably loop invariant and will be folded or hoisted. If it actually + // comes from a widened IV, it should be removed during a future call to + // WidenIVUse. + Value *LHS = (NarrowUse->getOperand(0) == NarrowDef) ? WideDef : + getExtend(NarrowUse->getOperand(0), WideType, IsSigned, Builder); + Value *RHS = (NarrowUse->getOperand(1) == NarrowDef) ? WideDef : + getExtend(NarrowUse->getOperand(1), WideType, IsSigned, Builder); + + BinaryOperator *NarrowBO = cast<BinaryOperator>(NarrowUse); + BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), + LHS, RHS, + NarrowBO->getName()); + Builder.Insert(WideBO); + if (NarrowBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); + if (NarrowBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); + + return WideBO; } + llvm_unreachable(0); +} + +// GetWideRecurrence - Is this instruction potentially interesting from IVUsers' +// perspective after widening it's type? In other words, can the extend be +// safely hoisted out of the loop with SCEV reducing the value to a recurrence +// on the same loop. If so, return the sign or zero extended +// recurrence. Otherwise return NULL. +const SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { + if (!SE->isSCEVable(NarrowUse->getType())) + return 0; + + const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); + const SCEV *WideExpr = IsSigned ? + SE->getSignExtendExpr(NarrowExpr, WideType) : + SE->getZeroExtendExpr(NarrowExpr, WideType); + const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); + if (!AddRec || AddRec->getLoop() != L) + return 0; + + return AddRec; +} + +/// HoistStep - Attempt to hoist an IV increment above a potential use. +/// +/// To successfully hoist, two criteria must be met: +/// - IncV operands dominate InsertPos and +/// - InsertPos dominates IncV +/// +/// Meeting the second condition means that we don't need to check all of IncV's +/// existing uses (it's moving up in the domtree). +/// +/// This does not yet recursively hoist the operands, although that would +/// not be difficult. +static bool HoistStep(Instruction *IncV, Instruction *InsertPos, + const DominatorTree *DT) +{ + if (DT->dominates(IncV, InsertPos)) + return true; + + if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) + return false; + + if (IncV->mayHaveSideEffects()) + return false; + + // Attempt to hoist IncV + for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); + OI != OE; ++OI) { + Instruction *OInst = dyn_cast<Instruction>(OI); + if (OInst && !DT->dominates(OInst, InsertPos)) + return false; + } + IncV->moveBefore(InsertPos); + return true; +} + +/// WidenIVUse - Determine whether an individual user of the narrow IV can be +/// widened. If so, return the wide clone of the user. +Instruction *WidenIV::WidenIVUse(Instruction *NarrowUse, + Instruction *NarrowDef, + Instruction *WideDef) { + // To be consistent with IVUsers, stop traversing the def-use chain at + // inner-loop phis or post-loop phis. + if (isa<PHINode>(NarrowUse) && LI->getLoopFor(NarrowUse->getParent()) != L) + return 0; + + // Handle data flow merges and bizarre phi cycles. + if (!Processed.insert(NarrowUse)) + return 0; + + // Our raison d'etre! Eliminate sign and zero extension. + if (IsSigned ? isa<SExtInst>(NarrowUse) : isa<ZExtInst>(NarrowUse)) { + Value *NewDef = WideDef; + if (NarrowUse->getType() != WideType) { + unsigned CastWidth = SE->getTypeSizeInBits(NarrowUse->getType()); + unsigned IVWidth = SE->getTypeSizeInBits(WideType); + if (CastWidth < IVWidth) { + // The cast isn't as wide as the IV, so insert a Trunc. + IRBuilder<> Builder(NarrowUse); + NewDef = Builder.CreateTrunc(WideDef, NarrowUse->getType()); + } + else { + // A wider extend was hidden behind a narrower one. This may induce + // another round of IV widening in which the intermediate IV becomes + // dead. It should be very rare. + DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi + << " not wide enough to subsume " << *NarrowUse << "\n"); + NarrowUse->replaceUsesOfWith(NarrowDef, WideDef); + NewDef = NarrowUse; + } + } + if (NewDef != NarrowUse) { + DEBUG(dbgs() << "INDVARS: eliminating " << *NarrowUse + << " replaced by " << *WideDef << "\n"); + ++NumElimExt; + NarrowUse->replaceAllUsesWith(NewDef); + DeadInsts.push_back(NarrowUse); + } + // Now that the extend is gone, expose it's uses to IVUsers for potential + // further simplification within SimplifyIVUsers. + IU->AddUsersIfInteresting(WideDef, WidePhi); + + // No further widening is needed. The deceased [sz]ext had done it for us. + return 0; + } + const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(NarrowUse); + if (!WideAddRec) { + // This user does not evaluate to a recurence after widening, so don't + // follow it. Instead insert a Trunc to kill off the original use, + // eventually isolating the original narrow IV so it can be removed. + IRBuilder<> Builder(NarrowUse); + Value *Trunc = Builder.CreateTrunc(WideDef, NarrowDef->getType()); + NarrowUse->replaceUsesOfWith(NarrowDef, Trunc); + return 0; + } + // Reuse the IV increment that SCEVExpander created as long as it dominates + // NarrowUse. + Instruction *WideUse = 0; + if (WideAddRec == WideIncExpr && HoistStep(WideInc, NarrowUse, DT)) { + WideUse = WideInc; + } + else { + WideUse = CloneIVUser(NarrowUse, NarrowDef, WideDef); + if (!WideUse) + return 0; + } + // GetWideRecurrence ensured that the narrow expression could be extended + // outside the loop without overflow. This suggests that the wide use + // evaluates to the same expression as the extended narrow use, but doesn't + // absolutely guarantee it. Hence the following failsafe check. In rare cases + // where it fails, we simple throw away the newly created wide use. + if (WideAddRec != SE->getSCEV(WideUse)) { + DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse + << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); + DeadInsts.push_back(WideUse); + return 0; + } + + // Returning WideUse pushes it on the worklist. + return WideUse; +} + +/// CreateWideIV - Process a single induction variable. First use the +/// SCEVExpander to create a wide induction variable that evaluates to the same +/// recurrence as the original narrow IV. Then use a worklist to forward +/// traverse the narrow IV's def-use chain. After WidenIVUse as processed all +/// interesting IV users, the narrow IV will be isolated for removal by +/// DeleteDeadPHIs. +/// +/// It would be simpler to delete uses as they are processed, but we must avoid +/// invalidating SCEV expressions. +/// +bool WidenIV::CreateWideIV(SCEVExpander &Rewriter) { + // Is this phi an induction variable? + const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); + if (!AddRec) + return false; + + // Widen the induction variable expression. + const SCEV *WideIVExpr = IsSigned ? + SE->getSignExtendExpr(AddRec, WideType) : + SE->getZeroExtendExpr(AddRec, WideType); + + assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && + "Expect the new IV expression to preserve its type"); + + // Can the IV be extended outside the loop without overflow? + AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); + if (!AddRec || AddRec->getLoop() != L) + return false; + + // An AddRec must have loop-invariant operands. Since this AddRec it + // materialized by a loop header phi, the expression cannot have any post-loop + // operands, so they must dominate the loop header. + assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && + SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) + && "Loop header phi recurrence inputs do not dominate the loop"); + + // The rewriter provides a value for the desired IV expression. This may + // either find an existing phi or materialize a new one. Either way, we + // expect a well-formed cyclic phi-with-increments. i.e. any operand not part + // of the phi-SCC dominates the loop entry. + Instruction *InsertPt = L->getHeader()->begin(); + WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); + + // Remembering the WideIV increment generated by SCEVExpander allows + // WidenIVUse to reuse it when widening the narrow IV's increment. We don't + // employ a general reuse mechanism because the call above is the only call to + // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. + if (BasicBlock *LatchBlock = L->getLoopLatch()) { + WideInc = + cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); + WideIncExpr = SE->getSCEV(WideInc); + } + + DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); + ++NumWidened; + + // Traverse the def-use chain using a worklist starting at the original IV. + assert(Processed.empty() && "expect initial state" ); + + // Each worklist entry has a Narrow def-use link and Wide def. + SmallVector<std::pair<Use *, Instruction *>, 8> NarrowIVUsers; + for (Value::use_iterator UI = OrigPhi->use_begin(), + UE = OrigPhi->use_end(); UI != UE; ++UI) { + NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WidePhi)); + } + while (!NarrowIVUsers.empty()) { + Use *NarrowDefUse; + Instruction *WideDef; + tie(NarrowDefUse, WideDef) = NarrowIVUsers.pop_back_val(); + + // Process a def-use edge. This may replace the use, so don't hold a + // use_iterator across it. + Instruction *NarrowDef = cast<Instruction>(NarrowDefUse->get()); + Instruction *NarrowUse = cast<Instruction>(NarrowDefUse->getUser()); + Instruction *WideUse = WidenIVUse(NarrowUse, NarrowDef, WideDef); + + // Follow all def-use edges from the previous narrow use. + if (WideUse) { + for (Value::use_iterator UI = NarrowUse->use_begin(), + UE = NarrowUse->use_end(); UI != UE; ++UI) { + NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WideUse)); + } + } + // WidenIVUse may have removed the def-use edge. + if (NarrowDef->use_empty()) + DeadInsts.push_back(NarrowDef); + } + return true; +} + +void IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { + unsigned IVOperIdx = 0; + ICmpInst::Predicate Pred = ICmp->getPredicate(); + if (IVOperand != ICmp->getOperand(0)) { + // Swapped + assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); + IVOperIdx = 1; + Pred = ICmpInst::getSwappedPredicate(Pred); + } + + // Get the SCEVs for the ICmp operands. + const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx)); + const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx)); + + // Simplify unnecessary loops away. + const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); + S = SE->getSCEVAtScope(S, ICmpLoop); + X = SE->getSCEVAtScope(X, ICmpLoop); + + // If the condition is always true or always false, replace it with + // a constant value. + if (SE->isKnownPredicate(Pred, S, X)) + ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); + else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) + ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); + else + return; + + DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); + ++NumElimCmp; + Changed = true; + DeadInsts.push_back(ICmp); +} + +void IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem, + Value *IVOperand, + bool IsSigned, + PHINode *IVPhi) { + // We're only interested in the case where we know something about + // the numerator. + if (IVOperand != Rem->getOperand(0)) + return; + + // Get the SCEVs for the ICmp operands. + const SCEV *S = SE->getSCEV(Rem->getOperand(0)); + const SCEV *X = SE->getSCEV(Rem->getOperand(1)); + + // Simplify unnecessary loops away. + const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); + S = SE->getSCEVAtScope(S, ICmpLoop); + X = SE->getSCEVAtScope(X, ICmpLoop); + + // i % n --> i if i is in [0,n). + if ((!IsSigned || SE->isKnownNonNegative(S)) && + SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + S, X)) + 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)); + if (IsSigned && !SE->isKnownNonNegative(LessOne)) + return; + + if (!SE->isKnownPredicate(IsSigned ? + ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + LessOne, X)) + return; + + ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, + Rem->getOperand(0), Rem->getOperand(1), + "tmp"); + SelectInst *Sel = + SelectInst::Create(ICmp, + ConstantInt::get(Rem->getType(), 0), + Rem->getOperand(0), "tmp", Rem); + Rem->replaceAllUsesWith(Sel); + } + + // Inform IVUsers about the new users. + if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) + IU->AddUsersIfInteresting(I, IVPhi); + + DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); + ++NumElimRem; + Changed = true; + DeadInsts.push_back(Rem); } bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { @@ -526,6 +1014,8 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { LI = &getAnalysis<LoopInfo>(); SE = &getAnalysis<ScalarEvolution>(); DT = &getAnalysis<DominatorTree>(); + TD = getAnalysisIfAvailable<TargetData>(); + DeadInsts.clear(); Changed = false; @@ -533,11 +1023,12 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // transform them to use integer recurrences. RewriteNonIntegerIVs(L); - BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); // Create a rewriter object which we'll use to transform the code with. SCEVExpander Rewriter(*SE); + if (DisableIVRewrite) + Rewriter.disableCanonicalMode(); // Check to see if this loop has a computable loop-invariant execution count. // If so, this means that we can compute the final value of any expressions @@ -548,33 +1039,42 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) RewriteLoopExitValues(L, Rewriter); - // Simplify ICmp IV users. - EliminateIVComparisons(); - - // Simplify SRem and URem IV users. - EliminateIVRemainders(); + // Eliminate redundant IV users. + SimplifyIVUsers(Rewriter); // Compute the type of the largest recurrence expression, and decide whether // a canonical induction variable should be inserted. const Type *LargestType = 0; bool NeedCannIV = false; - if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { - LargestType = BackedgeTakenCount->getType(); - LargestType = SE->getEffectiveSCEVType(LargestType); + bool ExpandBECount = canExpandBackedgeTakenCount(L, SE); + if (ExpandBECount) { // If we have a known trip count and a single exit block, we'll be // rewriting the loop exit test condition below, which requires a // canonical induction variable. - if (ExitingBlock) - NeedCannIV = true; - } - for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { - const Type *Ty = - SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); + NeedCannIV = true; + const Type *Ty = BackedgeTakenCount->getType(); + if (DisableIVRewrite) { + // In this mode, SimplifyIVUsers may have already widened the IV used by + // the backedge test and inserted a Trunc on the compare's operand. Get + // the wider type to avoid creating a redundant narrow IV only used by the + // loop test. + LargestType = getBackedgeIVType(L); + } if (!LargestType || SE->getTypeSizeInBits(Ty) > + SE->getTypeSizeInBits(LargestType)) + LargestType = SE->getEffectiveSCEVType(Ty); + } + if (!DisableIVRewrite) { + for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { + NeedCannIV = true; + const Type *Ty = + SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); + if (!LargestType || + SE->getTypeSizeInBits(Ty) > SE->getTypeSizeInBits(LargestType)) - LargestType = Ty; - NeedCannIV = true; + LargestType = Ty; + } } // Now that we know the largest of the induction variable expressions @@ -614,19 +1114,17 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // If we have a trip count expression, rewrite the loop's exit condition // using it. We can currently only handle loops with a single exit. ICmpInst *NewICmp = 0; - if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && - !BackedgeTakenCount->isZero() && - ExitingBlock) { + if (ExpandBECount) { + assert(canExpandBackedgeTakenCount(L, SE) && + "canonical IV disrupted BackedgeTaken expansion"); assert(NeedCannIV && "LinearFunctionTestReplace requires a canonical induction variable"); - // Can't rewrite non-branch yet. - if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) - NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, - ExitingBlock, BI, Rewriter); + NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, + Rewriter); } - // Rewrite IV-derived expressions. - RewriteIVExpressions(L, Rewriter); + if (!DisableIVRewrite) + RewriteIVExpressions(L, Rewriter); // Clear the rewriter cache, because values that are in the rewriter's cache // can be deleted in the loop below, causing the AssertingVH in the cache to @@ -649,7 +1147,8 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // For completeness, inform IVUsers of the IV use in the newly-created // loop exit test instruction. if (NewICmp) - IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); + IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)), + IndVar); // Clean up dead instructions. Changed |= DeleteDeadPHIs(L->getHeader()); @@ -1080,5 +1579,5 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { } // Add a new IVUsers entry for the newly-created integer PHI. - IU->AddUsersIfInteresting(NewPHI); + IU->AddUsersIfInteresting(NewPHI, NewPHI); } |
