LLVM API Documentation

SimplifyIndVar.cpp
Go to the documentation of this file.
00001 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements induction variable simplification. It does
00011 // not define any actual pass or policy, but provides a single function to
00012 // simplify a loop's induction variables based on ScalarEvolution.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
00017 #include "llvm/ADT/STLExtras.h"
00018 #include "llvm/ADT/SmallVector.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Analysis/IVUsers.h"
00021 #include "llvm/Analysis/LoopInfo.h"
00022 #include "llvm/Analysis/LoopPass.h"
00023 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
00024 #include "llvm/IR/DataLayout.h"
00025 #include "llvm/IR/Dominators.h"
00026 #include "llvm/IR/IRBuilder.h"
00027 #include "llvm/IR/Instructions.h"
00028 #include "llvm/IR/IntrinsicInst.h"
00029 #include "llvm/Support/CommandLine.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/raw_ostream.h"
00032 
00033 using namespace llvm;
00034 
00035 #define DEBUG_TYPE "indvars"
00036 
00037 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
00038 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
00039 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
00040 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
00041 
00042 namespace {
00043   /// This is a utility for simplifying induction variables
00044   /// based on ScalarEvolution. It is the primary instrument of the
00045   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
00046   /// other loop passes that preserve SCEV.
00047   class SimplifyIndvar {
00048     Loop             *L;
00049     LoopInfo         *LI;
00050     ScalarEvolution  *SE;
00051     const DataLayout *DL; // May be NULL
00052 
00053     SmallVectorImpl<WeakVH> &DeadInsts;
00054 
00055     bool Changed;
00056 
00057   public:
00058     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM,
00059                    SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = nullptr) :
00060       L(Loop),
00061       LI(LPM->getAnalysisIfAvailable<LoopInfo>()),
00062       SE(SE),
00063       DeadInsts(Dead),
00064       Changed(false) {
00065       DataLayoutPass *DLP = LPM->getAnalysisIfAvailable<DataLayoutPass>();
00066       DL = DLP ? &DLP->getDataLayout() : nullptr;
00067       assert(LI && "IV simplification requires LoopInfo");
00068     }
00069 
00070     bool hasChanged() const { return Changed; }
00071 
00072     /// Iteratively perform simplification on a worklist of users of the
00073     /// specified induction variable. This is the top-level driver that applies
00074     /// all simplicitions to users of an IV.
00075     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
00076 
00077     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
00078 
00079     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
00080     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
00081     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
00082                               bool IsSigned);
00083 
00084     Instruction *splitOverflowIntrinsic(Instruction *IVUser,
00085                                         const DominatorTree *DT);
00086   };
00087 }
00088 
00089 /// Fold an IV operand into its use.  This removes increments of an
00090 /// aligned IV when used by a instruction that ignores the low bits.
00091 ///
00092 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
00093 ///
00094 /// Return the operand of IVOperand for this induction variable if IVOperand can
00095 /// be folded (in case more folding opportunities have been exposed).
00096 /// Otherwise return null.
00097 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
00098   Value *IVSrc = nullptr;
00099   unsigned OperIdx = 0;
00100   const SCEV *FoldedExpr = nullptr;
00101   switch (UseInst->getOpcode()) {
00102   default:
00103     return nullptr;
00104   case Instruction::UDiv:
00105   case Instruction::LShr:
00106     // We're only interested in the case where we know something about
00107     // the numerator and have a constant denominator.
00108     if (IVOperand != UseInst->getOperand(OperIdx) ||
00109         !isa<ConstantInt>(UseInst->getOperand(1)))
00110       return nullptr;
00111 
00112     // Attempt to fold a binary operator with constant operand.
00113     // e.g. ((I + 1) >> 2) => I >> 2
00114     if (!isa<BinaryOperator>(IVOperand)
00115         || !isa<ConstantInt>(IVOperand->getOperand(1)))
00116       return nullptr;
00117 
00118     IVSrc = IVOperand->getOperand(0);
00119     // IVSrc must be the (SCEVable) IV, since the other operand is const.
00120     assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
00121 
00122     ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
00123     if (UseInst->getOpcode() == Instruction::LShr) {
00124       // Get a constant for the divisor. See createSCEV.
00125       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
00126       if (D->getValue().uge(BitWidth))
00127         return nullptr;
00128 
00129       D = ConstantInt::get(UseInst->getContext(),
00130                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
00131     }
00132     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
00133   }
00134   // We have something that might fold it's operand. Compare SCEVs.
00135   if (!SE->isSCEVable(UseInst->getType()))
00136     return nullptr;
00137 
00138   // Bypass the operand if SCEV can prove it has no effect.
00139   if (SE->getSCEV(UseInst) != FoldedExpr)
00140     return nullptr;
00141 
00142   DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
00143         << " -> " << *UseInst << '\n');
00144 
00145   UseInst->setOperand(OperIdx, IVSrc);
00146   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
00147 
00148   ++NumElimOperand;
00149   Changed = true;
00150   if (IVOperand->use_empty())
00151     DeadInsts.push_back(IVOperand);
00152   return IVSrc;
00153 }
00154 
00155 /// SimplifyIVUsers helper for eliminating useless
00156 /// comparisons against an induction variable.
00157 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
00158   unsigned IVOperIdx = 0;
00159   ICmpInst::Predicate Pred = ICmp->getPredicate();
00160   if (IVOperand != ICmp->getOperand(0)) {
00161     // Swapped
00162     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
00163     IVOperIdx = 1;
00164     Pred = ICmpInst::getSwappedPredicate(Pred);
00165   }
00166 
00167   // Get the SCEVs for the ICmp operands.
00168   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
00169   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
00170 
00171   // Simplify unnecessary loops away.
00172   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
00173   S = SE->getSCEVAtScope(S, ICmpLoop);
00174   X = SE->getSCEVAtScope(X, ICmpLoop);
00175 
00176   // If the condition is always true or always false, replace it with
00177   // a constant value.
00178   if (SE->isKnownPredicate(Pred, S, X))
00179     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
00180   else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
00181     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
00182   else
00183     return;
00184 
00185   DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
00186   ++NumElimCmp;
00187   Changed = true;
00188   DeadInsts.push_back(ICmp);
00189 }
00190 
00191 /// SimplifyIVUsers helper for eliminating useless
00192 /// remainder operations operating on an induction variable.
00193 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
00194                                       Value *IVOperand,
00195                                       bool IsSigned) {
00196   // We're only interested in the case where we know something about
00197   // the numerator.
00198   if (IVOperand != Rem->getOperand(0))
00199     return;
00200 
00201   // Get the SCEVs for the ICmp operands.
00202   const SCEV *S = SE->getSCEV(Rem->getOperand(0));
00203   const SCEV *X = SE->getSCEV(Rem->getOperand(1));
00204 
00205   // Simplify unnecessary loops away.
00206   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
00207   S = SE->getSCEVAtScope(S, ICmpLoop);
00208   X = SE->getSCEVAtScope(X, ICmpLoop);
00209 
00210   // i % n  -->  i  if i is in [0,n).
00211   if ((!IsSigned || SE->isKnownNonNegative(S)) &&
00212       SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
00213                            S, X))
00214     Rem->replaceAllUsesWith(Rem->getOperand(0));
00215   else {
00216     // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
00217     const SCEV *LessOne =
00218       SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
00219     if (IsSigned && !SE->isKnownNonNegative(LessOne))
00220       return;
00221 
00222     if (!SE->isKnownPredicate(IsSigned ?
00223                               ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
00224                               LessOne, X))
00225       return;
00226 
00227     ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
00228                                   Rem->getOperand(0), Rem->getOperand(1));
00229     SelectInst *Sel =
00230       SelectInst::Create(ICmp,
00231                          ConstantInt::get(Rem->getType(), 0),
00232                          Rem->getOperand(0), "tmp", Rem);
00233     Rem->replaceAllUsesWith(Sel);
00234   }
00235 
00236   DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
00237   ++NumElimRem;
00238   Changed = true;
00239   DeadInsts.push_back(Rem);
00240 }
00241 
00242 /// Eliminate an operation that consumes a simple IV and has
00243 /// no observable side-effect given the range of IV values.
00244 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
00245 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
00246                                      Instruction *IVOperand) {
00247   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
00248     eliminateIVComparison(ICmp, IVOperand);
00249     return true;
00250   }
00251   if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
00252     bool IsSigned = Rem->getOpcode() == Instruction::SRem;
00253     if (IsSigned || Rem->getOpcode() == Instruction::URem) {
00254       eliminateIVRemainder(Rem, IVOperand, IsSigned);
00255       return true;
00256     }
00257   }
00258 
00259   // Eliminate any operation that SCEV can prove is an identity function.
00260   if (!SE->isSCEVable(UseInst->getType()) ||
00261       (UseInst->getType() != IVOperand->getType()) ||
00262       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
00263     return false;
00264 
00265   DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
00266 
00267   UseInst->replaceAllUsesWith(IVOperand);
00268   ++NumElimIdentity;
00269   Changed = true;
00270   DeadInsts.push_back(UseInst);
00271   return true;
00272 }
00273 
00274 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
00275 /// analysis and optimization.
00276 ///
00277 /// \return A new value representing the non-overflowing add if possible,
00278 /// otherwise return the original value.
00279 Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
00280                                                     const DominatorTree *DT) {
00281   IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
00282   if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
00283     return IVUser;
00284 
00285   // Find a branch guarded by the overflow check.
00286   BranchInst *Branch = nullptr;
00287   Instruction *AddVal = nullptr;
00288   for (User *U : II->users()) {
00289     if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
00290       if (ExtractInst->getNumIndices() != 1)
00291         continue;
00292       if (ExtractInst->getIndices()[0] == 0)
00293         AddVal = ExtractInst;
00294       else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
00295         Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
00296     }
00297   }
00298   if (!AddVal || !Branch)
00299     return IVUser;
00300 
00301   BasicBlock *ContinueBB = Branch->getSuccessor(1);
00302   if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
00303     return IVUser;
00304 
00305   // Check if all users of the add are provably NSW.
00306   bool AllNSW = true;
00307   for (Use &U : AddVal->uses()) {
00308     if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
00309       BasicBlock *UseBB = UseInst->getParent();
00310       if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
00311         UseBB = PHI->getIncomingBlock(U);
00312       if (!DT->dominates(ContinueBB, UseBB)) {
00313         AllNSW = false;
00314         break;
00315       }
00316     }
00317   }
00318   if (!AllNSW)
00319     return IVUser;
00320 
00321   // Go for it...
00322   IRBuilder<> Builder(IVUser);
00323   Instruction *AddInst = dyn_cast<Instruction>(
00324     Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
00325 
00326   // The caller expects the new add to have the same form as the intrinsic. The
00327   // IV operand position must be the same.
00328   assert((AddInst->getOpcode() == Instruction::Add &&
00329           AddInst->getOperand(0) == II->getOperand(0)) &&
00330          "Bad add instruction created from overflow intrinsic.");
00331 
00332   AddVal->replaceAllUsesWith(AddInst);
00333   DeadInsts.push_back(AddVal);
00334   return AddInst;
00335 }
00336 
00337 /// Add all uses of Def to the current IV's worklist.
00338 static void pushIVUsers(
00339   Instruction *Def,
00340   SmallPtrSet<Instruction*,16> &Simplified,
00341   SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
00342 
00343   for (User *U : Def->users()) {
00344     Instruction *UI = cast<Instruction>(U);
00345 
00346     // Avoid infinite or exponential worklist processing.
00347     // Also ensure unique worklist users.
00348     // If Def is a LoopPhi, it may not be in the Simplified set, so check for
00349     // self edges first.
00350     if (UI != Def && Simplified.insert(UI).second)
00351       SimpleIVUsers.push_back(std::make_pair(UI, Def));
00352   }
00353 }
00354 
00355 /// Return true if this instruction generates a simple SCEV
00356 /// expression in terms of that IV.
00357 ///
00358 /// This is similar to IVUsers' isInteresting() but processes each instruction
00359 /// non-recursively when the operand is already known to be a simpleIVUser.
00360 ///
00361 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
00362   if (!SE->isSCEVable(I->getType()))
00363     return false;
00364 
00365   // Get the symbolic expression for this instruction.
00366   const SCEV *S = SE->getSCEV(I);
00367 
00368   // Only consider affine recurrences.
00369   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
00370   if (AR && AR->getLoop() == L)
00371     return true;
00372 
00373   return false;
00374 }
00375 
00376 /// Iteratively perform simplification on a worklist of users
00377 /// of the specified induction variable. Each successive simplification may push
00378 /// more users which may themselves be candidates for simplification.
00379 ///
00380 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
00381 /// instructions in-place during analysis. Rather than rewriting induction
00382 /// variables bottom-up from their users, it transforms a chain of IVUsers
00383 /// top-down, updating the IR only when it encouters a clear optimization
00384 /// opportunitiy.
00385 ///
00386 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
00387 ///
00388 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
00389   if (!SE->isSCEVable(CurrIV->getType()))
00390     return;
00391 
00392   // Instructions processed by SimplifyIndvar for CurrIV.
00393   SmallPtrSet<Instruction*,16> Simplified;
00394 
00395   // Use-def pairs if IV users waiting to be processed for CurrIV.
00396   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
00397 
00398   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
00399   // called multiple times for the same LoopPhi. This is the proper thing to
00400   // do for loop header phis that use each other.
00401   pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
00402 
00403   while (!SimpleIVUsers.empty()) {
00404     std::pair<Instruction*, Instruction*> UseOper =
00405       SimpleIVUsers.pop_back_val();
00406     Instruction *UseInst = UseOper.first;
00407 
00408     // Bypass back edges to avoid extra work.
00409     if (UseInst == CurrIV) continue;
00410 
00411     if (V && V->shouldSplitOverflowInstrinsics()) {
00412       UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
00413       if (!UseInst)
00414         continue;
00415     }
00416 
00417     Instruction *IVOperand = UseOper.second;
00418     for (unsigned N = 0; IVOperand; ++N) {
00419       assert(N <= Simplified.size() && "runaway iteration");
00420 
00421       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
00422       if (!NewOper)
00423         break; // done folding
00424       IVOperand = dyn_cast<Instruction>(NewOper);
00425     }
00426     if (!IVOperand)
00427       continue;
00428 
00429     if (eliminateIVUser(UseOper.first, IVOperand)) {
00430       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
00431       continue;
00432     }
00433     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
00434     if (V && Cast) {
00435       V->visitCast(Cast);
00436       continue;
00437     }
00438     if (isSimpleIVUser(UseOper.first, L, SE)) {
00439       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
00440     }
00441   }
00442 }
00443 
00444 namespace llvm {
00445 
00446 void IVVisitor::anchor() { }
00447 
00448 /// Simplify instructions that use this induction variable
00449 /// by using ScalarEvolution to analyze the IV's recurrence.
00450 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
00451                        SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
00452 {
00453   LoopInfo *LI = &LPM->getAnalysis<LoopInfo>();
00454   SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead);
00455   SIV.simplifyUsers(CurrIV, V);
00456   return SIV.hasChanged();
00457 }
00458 
00459 /// Simplify users of induction variables within this
00460 /// loop. This does not actually change or add IVs.
00461 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM,
00462                      SmallVectorImpl<WeakVH> &Dead) {
00463   bool Changed = false;
00464   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
00465     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
00466   }
00467   return Changed;
00468 }
00469 
00470 } // namespace llvm