1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements induction variable simplification. It does
11 // not define any actual pass or policy, but provides a single function to
12 // simplify a loop's induction variables based on ScalarEvolution.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
31 
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "indvars"
35 
36 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
37 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
38 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
39 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
40 
41 namespace {
42   /// This is a utility for simplifying induction variables
43   /// based on ScalarEvolution. It is the primary instrument of the
44   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
45   /// other loop passes that preserve SCEV.
46   class SimplifyIndvar {
47     Loop             *L;
48     LoopInfo         *LI;
49     ScalarEvolution  *SE;
50     DominatorTree    *DT;
51 
52     SmallVectorImpl<WeakVH> &DeadInsts;
53 
54     bool Changed;
55 
56   public:
SimplifyIndvar(Loop * Loop,ScalarEvolution * SE,DominatorTree * DT,LoopInfo * LI,SmallVectorImpl<WeakVH> & Dead)57     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
58                    LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
59         : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
60       assert(LI && "IV simplification requires LoopInfo");
61     }
62 
hasChanged() const63     bool hasChanged() const { return Changed; }
64 
65     /// Iteratively perform simplification on a worklist of users of the
66     /// specified induction variable. This is the top-level driver that applies
67     /// all simplifications to users of an IV.
68     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
69 
70     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
71 
72     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
73 
74     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
75     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
76     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
77                               bool IsSigned);
78     bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
79 
80     Instruction *splitOverflowIntrinsic(Instruction *IVUser,
81                                         const DominatorTree *DT);
82   };
83 }
84 
85 /// Fold an IV operand into its use.  This removes increments of an
86 /// aligned IV when used by a instruction that ignores the low bits.
87 ///
88 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
89 ///
90 /// Return the operand of IVOperand for this induction variable if IVOperand can
91 /// be folded (in case more folding opportunities have been exposed).
92 /// Otherwise return null.
foldIVUser(Instruction * UseInst,Instruction * IVOperand)93 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
94   Value *IVSrc = nullptr;
95   unsigned OperIdx = 0;
96   const SCEV *FoldedExpr = nullptr;
97   switch (UseInst->getOpcode()) {
98   default:
99     return nullptr;
100   case Instruction::UDiv:
101   case Instruction::LShr:
102     // We're only interested in the case where we know something about
103     // the numerator and have a constant denominator.
104     if (IVOperand != UseInst->getOperand(OperIdx) ||
105         !isa<ConstantInt>(UseInst->getOperand(1)))
106       return nullptr;
107 
108     // Attempt to fold a binary operator with constant operand.
109     // e.g. ((I + 1) >> 2) => I >> 2
110     if (!isa<BinaryOperator>(IVOperand)
111         || !isa<ConstantInt>(IVOperand->getOperand(1)))
112       return nullptr;
113 
114     IVSrc = IVOperand->getOperand(0);
115     // IVSrc must be the (SCEVable) IV, since the other operand is const.
116     assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
117 
118     ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
119     if (UseInst->getOpcode() == Instruction::LShr) {
120       // Get a constant for the divisor. See createSCEV.
121       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
122       if (D->getValue().uge(BitWidth))
123         return nullptr;
124 
125       D = ConstantInt::get(UseInst->getContext(),
126                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
127     }
128     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
129   }
130   // We have something that might fold it's operand. Compare SCEVs.
131   if (!SE->isSCEVable(UseInst->getType()))
132     return nullptr;
133 
134   // Bypass the operand if SCEV can prove it has no effect.
135   if (SE->getSCEV(UseInst) != FoldedExpr)
136     return nullptr;
137 
138   DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
139         << " -> " << *UseInst << '\n');
140 
141   UseInst->setOperand(OperIdx, IVSrc);
142   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
143 
144   ++NumElimOperand;
145   Changed = true;
146   if (IVOperand->use_empty())
147     DeadInsts.emplace_back(IVOperand);
148   return IVSrc;
149 }
150 
151 /// SimplifyIVUsers helper for eliminating useless
152 /// comparisons against an induction variable.
eliminateIVComparison(ICmpInst * ICmp,Value * IVOperand)153 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
154   unsigned IVOperIdx = 0;
155   ICmpInst::Predicate Pred = ICmp->getPredicate();
156   if (IVOperand != ICmp->getOperand(0)) {
157     // Swapped
158     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
159     IVOperIdx = 1;
160     Pred = ICmpInst::getSwappedPredicate(Pred);
161   }
162 
163   // Get the SCEVs for the ICmp operands.
164   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
165   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
166 
167   // Simplify unnecessary loops away.
168   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
169   S = SE->getSCEVAtScope(S, ICmpLoop);
170   X = SE->getSCEVAtScope(X, ICmpLoop);
171 
172   ICmpInst::Predicate InvariantPredicate;
173   const SCEV *InvariantLHS, *InvariantRHS;
174 
175   // If the condition is always true or always false, replace it with
176   // a constant value.
177   if (SE->isKnownPredicate(Pred, S, X)) {
178     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
179     DeadInsts.emplace_back(ICmp);
180     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
181   } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
182     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
183     DeadInsts.emplace_back(ICmp);
184     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
185   } else if (isa<PHINode>(IVOperand) &&
186              SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
187                                           InvariantPredicate, InvariantLHS,
188                                           InvariantRHS)) {
189 
190     // Rewrite the comparison to a loop invariant comparison if it can be done
191     // cheaply, where cheaply means "we don't need to emit any new
192     // instructions".
193 
194     Value *NewLHS = nullptr, *NewRHS = nullptr;
195 
196     if (S == InvariantLHS || X == InvariantLHS)
197       NewLHS =
198           ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
199 
200     if (S == InvariantRHS || X == InvariantRHS)
201       NewRHS =
202           ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
203 
204     for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
205       if (NewLHS && NewRHS)
206         break;
207 
208       const SCEV *IncomingS = SE->getSCEV(Incoming);
209 
210       if (!NewLHS && IncomingS == InvariantLHS)
211         NewLHS = Incoming;
212       if (!NewRHS && IncomingS == InvariantRHS)
213         NewRHS = Incoming;
214     }
215 
216     if (!NewLHS || !NewRHS)
217       // We could not find an existing value to replace either LHS or RHS.
218       // Generating new instructions has subtler tradeoffs, so avoid doing that
219       // for now.
220       return;
221 
222     DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
223     ICmp->setPredicate(InvariantPredicate);
224     ICmp->setOperand(0, NewLHS);
225     ICmp->setOperand(1, NewRHS);
226   } else
227     return;
228 
229   ++NumElimCmp;
230   Changed = true;
231 }
232 
233 /// SimplifyIVUsers helper for eliminating useless
234 /// remainder operations operating on an induction variable.
eliminateIVRemainder(BinaryOperator * Rem,Value * IVOperand,bool IsSigned)235 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
236                                       Value *IVOperand,
237                                       bool IsSigned) {
238   // We're only interested in the case where we know something about
239   // the numerator.
240   if (IVOperand != Rem->getOperand(0))
241     return;
242 
243   // Get the SCEVs for the ICmp operands.
244   const SCEV *S = SE->getSCEV(Rem->getOperand(0));
245   const SCEV *X = SE->getSCEV(Rem->getOperand(1));
246 
247   // Simplify unnecessary loops away.
248   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
249   S = SE->getSCEVAtScope(S, ICmpLoop);
250   X = SE->getSCEVAtScope(X, ICmpLoop);
251 
252   // i % n  -->  i  if i is in [0,n).
253   if ((!IsSigned || SE->isKnownNonNegative(S)) &&
254       SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
255                            S, X))
256     Rem->replaceAllUsesWith(Rem->getOperand(0));
257   else {
258     // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
259     const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
260     if (IsSigned && !SE->isKnownNonNegative(LessOne))
261       return;
262 
263     if (!SE->isKnownPredicate(IsSigned ?
264                               ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
265                               LessOne, X))
266       return;
267 
268     ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
269                                   Rem->getOperand(0), Rem->getOperand(1));
270     SelectInst *Sel =
271       SelectInst::Create(ICmp,
272                          ConstantInt::get(Rem->getType(), 0),
273                          Rem->getOperand(0), "tmp", Rem);
274     Rem->replaceAllUsesWith(Sel);
275   }
276 
277   DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
278   ++NumElimRem;
279   Changed = true;
280   DeadInsts.emplace_back(Rem);
281 }
282 
283 /// Eliminate an operation that consumes a simple IV and has no observable
284 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
285 /// but UseInst may not be.
eliminateIVUser(Instruction * UseInst,Instruction * IVOperand)286 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
287                                      Instruction *IVOperand) {
288   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
289     eliminateIVComparison(ICmp, IVOperand);
290     return true;
291   }
292   if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
293     bool IsSigned = Rem->getOpcode() == Instruction::SRem;
294     if (IsSigned || Rem->getOpcode() == Instruction::URem) {
295       eliminateIVRemainder(Rem, IVOperand, IsSigned);
296       return true;
297     }
298   }
299 
300   if (eliminateIdentitySCEV(UseInst, IVOperand))
301     return true;
302 
303   return false;
304 }
305 
306 /// Eliminate any operation that SCEV can prove is an identity function.
eliminateIdentitySCEV(Instruction * UseInst,Instruction * IVOperand)307 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
308                                            Instruction *IVOperand) {
309   if (!SE->isSCEVable(UseInst->getType()) ||
310       (UseInst->getType() != IVOperand->getType()) ||
311       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
312     return false;
313 
314   // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
315   // dominator tree, even if X is an operand to Y.  For instance, in
316   //
317   //     %iv = phi i32 {0,+,1}
318   //     br %cond, label %left, label %merge
319   //
320   //   left:
321   //     %X = add i32 %iv, 0
322   //     br label %merge
323   //
324   //   merge:
325   //     %M = phi (%X, %iv)
326   //
327   // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
328   // %M.replaceAllUsesWith(%X) would be incorrect.
329 
330   if (isa<PHINode>(UseInst))
331     // If UseInst is not a PHI node then we know that IVOperand dominates
332     // UseInst directly from the legality of SSA.
333     if (!DT || !DT->dominates(IVOperand, UseInst))
334       return false;
335 
336   if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
337     return false;
338 
339   DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
340 
341   UseInst->replaceAllUsesWith(IVOperand);
342   ++NumElimIdentity;
343   Changed = true;
344   DeadInsts.emplace_back(UseInst);
345   return true;
346 }
347 
348 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
349 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
strengthenOverflowingOperation(BinaryOperator * BO,Value * IVOperand)350 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
351                                                     Value *IVOperand) {
352 
353   // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
354   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
355     return false;
356 
357   const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
358                                                SCEV::NoWrapFlags);
359 
360   switch (BO->getOpcode()) {
361   default:
362     return false;
363 
364   case Instruction::Add:
365     GetExprForBO = &ScalarEvolution::getAddExpr;
366     break;
367 
368   case Instruction::Sub:
369     GetExprForBO = &ScalarEvolution::getMinusSCEV;
370     break;
371 
372   case Instruction::Mul:
373     GetExprForBO = &ScalarEvolution::getMulExpr;
374     break;
375   }
376 
377   unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
378   Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
379   const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
380   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
381 
382   bool Changed = false;
383 
384   if (!BO->hasNoUnsignedWrap()) {
385     const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
386     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
387       SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
388       SCEV::FlagAnyWrap);
389     if (ExtendAfterOp == OpAfterExtend) {
390       BO->setHasNoUnsignedWrap();
391       SE->forgetValue(BO);
392       Changed = true;
393     }
394   }
395 
396   if (!BO->hasNoSignedWrap()) {
397     const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
398     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
399       SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
400       SCEV::FlagAnyWrap);
401     if (ExtendAfterOp == OpAfterExtend) {
402       BO->setHasNoSignedWrap();
403       SE->forgetValue(BO);
404       Changed = true;
405     }
406   }
407 
408   return Changed;
409 }
410 
411 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
412 /// analysis and optimization.
413 ///
414 /// \return A new value representing the non-overflowing add if possible,
415 /// otherwise return the original value.
splitOverflowIntrinsic(Instruction * IVUser,const DominatorTree * DT)416 Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
417                                                     const DominatorTree *DT) {
418   IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
419   if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
420     return IVUser;
421 
422   // Find a branch guarded by the overflow check.
423   BranchInst *Branch = nullptr;
424   Instruction *AddVal = nullptr;
425   for (User *U : II->users()) {
426     if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
427       if (ExtractInst->getNumIndices() != 1)
428         continue;
429       if (ExtractInst->getIndices()[0] == 0)
430         AddVal = ExtractInst;
431       else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
432         Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
433     }
434   }
435   if (!AddVal || !Branch)
436     return IVUser;
437 
438   BasicBlock *ContinueBB = Branch->getSuccessor(1);
439   if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
440     return IVUser;
441 
442   // Check if all users of the add are provably NSW.
443   bool AllNSW = true;
444   for (Use &U : AddVal->uses()) {
445     if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
446       BasicBlock *UseBB = UseInst->getParent();
447       if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
448         UseBB = PHI->getIncomingBlock(U);
449       if (!DT->dominates(ContinueBB, UseBB)) {
450         AllNSW = false;
451         break;
452       }
453     }
454   }
455   if (!AllNSW)
456     return IVUser;
457 
458   // Go for it...
459   IRBuilder<> Builder(IVUser);
460   Instruction *AddInst = dyn_cast<Instruction>(
461     Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
462 
463   // The caller expects the new add to have the same form as the intrinsic. The
464   // IV operand position must be the same.
465   assert((AddInst->getOpcode() == Instruction::Add &&
466           AddInst->getOperand(0) == II->getOperand(0)) &&
467          "Bad add instruction created from overflow intrinsic.");
468 
469   AddVal->replaceAllUsesWith(AddInst);
470   DeadInsts.emplace_back(AddVal);
471   return AddInst;
472 }
473 
474 /// Add all uses of Def to the current IV's worklist.
pushIVUsers(Instruction * Def,SmallPtrSet<Instruction *,16> & Simplified,SmallVectorImpl<std::pair<Instruction *,Instruction * >> & SimpleIVUsers)475 static void pushIVUsers(
476   Instruction *Def,
477   SmallPtrSet<Instruction*,16> &Simplified,
478   SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
479 
480   for (User *U : Def->users()) {
481     Instruction *UI = cast<Instruction>(U);
482 
483     // Avoid infinite or exponential worklist processing.
484     // Also ensure unique worklist users.
485     // If Def is a LoopPhi, it may not be in the Simplified set, so check for
486     // self edges first.
487     if (UI != Def && Simplified.insert(UI).second)
488       SimpleIVUsers.push_back(std::make_pair(UI, Def));
489   }
490 }
491 
492 /// Return true if this instruction generates a simple SCEV
493 /// expression in terms of that IV.
494 ///
495 /// This is similar to IVUsers' isInteresting() but processes each instruction
496 /// non-recursively when the operand is already known to be a simpleIVUser.
497 ///
isSimpleIVUser(Instruction * I,const Loop * L,ScalarEvolution * SE)498 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
499   if (!SE->isSCEVable(I->getType()))
500     return false;
501 
502   // Get the symbolic expression for this instruction.
503   const SCEV *S = SE->getSCEV(I);
504 
505   // Only consider affine recurrences.
506   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
507   if (AR && AR->getLoop() == L)
508     return true;
509 
510   return false;
511 }
512 
513 /// Iteratively perform simplification on a worklist of users
514 /// of the specified induction variable. Each successive simplification may push
515 /// more users which may themselves be candidates for simplification.
516 ///
517 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
518 /// instructions in-place during analysis. Rather than rewriting induction
519 /// variables bottom-up from their users, it transforms a chain of IVUsers
520 /// top-down, updating the IR only when it encounters a clear optimization
521 /// opportunity.
522 ///
523 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
524 ///
simplifyUsers(PHINode * CurrIV,IVVisitor * V)525 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
526   if (!SE->isSCEVable(CurrIV->getType()))
527     return;
528 
529   // Instructions processed by SimplifyIndvar for CurrIV.
530   SmallPtrSet<Instruction*,16> Simplified;
531 
532   // Use-def pairs if IV users waiting to be processed for CurrIV.
533   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
534 
535   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
536   // called multiple times for the same LoopPhi. This is the proper thing to
537   // do for loop header phis that use each other.
538   pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
539 
540   while (!SimpleIVUsers.empty()) {
541     std::pair<Instruction*, Instruction*> UseOper =
542       SimpleIVUsers.pop_back_val();
543     Instruction *UseInst = UseOper.first;
544 
545     // Bypass back edges to avoid extra work.
546     if (UseInst == CurrIV) continue;
547 
548     if (V && V->shouldSplitOverflowInstrinsics()) {
549       UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
550       if (!UseInst)
551         continue;
552     }
553 
554     Instruction *IVOperand = UseOper.second;
555     for (unsigned N = 0; IVOperand; ++N) {
556       assert(N <= Simplified.size() && "runaway iteration");
557 
558       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
559       if (!NewOper)
560         break; // done folding
561       IVOperand = dyn_cast<Instruction>(NewOper);
562     }
563     if (!IVOperand)
564       continue;
565 
566     if (eliminateIVUser(UseOper.first, IVOperand)) {
567       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
568       continue;
569     }
570 
571     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
572       if (isa<OverflowingBinaryOperator>(BO) &&
573           strengthenOverflowingOperation(BO, IVOperand)) {
574         // re-queue uses of the now modified binary operator and fall
575         // through to the checks that remain.
576         pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
577       }
578     }
579 
580     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
581     if (V && Cast) {
582       V->visitCast(Cast);
583       continue;
584     }
585     if (isSimpleIVUser(UseOper.first, L, SE)) {
586       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
587     }
588   }
589 }
590 
591 namespace llvm {
592 
anchor()593 void IVVisitor::anchor() { }
594 
595 /// Simplify instructions that use this induction variable
596 /// by using ScalarEvolution to analyze the IV's recurrence.
simplifyUsersOfIV(PHINode * CurrIV,ScalarEvolution * SE,DominatorTree * DT,LoopInfo * LI,SmallVectorImpl<WeakVH> & Dead,IVVisitor * V)597 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
598                        LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead,
599                        IVVisitor *V) {
600   SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
601   SIV.simplifyUsers(CurrIV, V);
602   return SIV.hasChanged();
603 }
604 
605 /// Simplify users of induction variables within this
606 /// loop. This does not actually change or add IVs.
simplifyLoopIVs(Loop * L,ScalarEvolution * SE,DominatorTree * DT,LoopInfo * LI,SmallVectorImpl<WeakVH> & Dead)607 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
608                      LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead) {
609   bool Changed = false;
610   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
611     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead);
612   }
613   return Changed;
614 }
615 
616 } // namespace llvm
617