SimplifyIndVar.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
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#define DEBUG_TYPE "indvars"
17
18#include "llvm/Transforms/Utils/SimplifyIndVar.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/Analysis/IVUsers.h"
23#include "llvm/Analysis/LoopInfo.h"
24#include "llvm/Analysis/LoopPass.h"
25#include "llvm/Analysis/ScalarEvolutionExpressions.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/Instructions.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/raw_ostream.h"
34
35using namespace llvm;
36
37STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
38STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
39STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
40STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
41
42namespace {
43  /// SimplifyIndvar - This is a utility for simplifying induction variables
44  /// based on ScalarEvolution. It is the primary instrument of the
45  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
46  /// other loop passes that preserve SCEV.
47  class SimplifyIndvar {
48    Loop             *L;
49    LoopInfo         *LI;
50    ScalarEvolution  *SE;
51    const DataLayout *DL; // May be NULL
52
53    SmallVectorImpl<WeakVH> &DeadInsts;
54
55    bool Changed;
56
57  public:
58    SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM,
59                   SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = NULL) :
60      L(Loop),
61      LI(LPM->getAnalysisIfAvailable<LoopInfo>()),
62      SE(SE),
63      DeadInsts(Dead),
64      Changed(false) {
65      DataLayoutPass *DLP = LPM->getAnalysisIfAvailable<DataLayoutPass>();
66      DL = DLP ? &DLP->getDataLayout() : 0;
67      assert(LI && "IV simplification requires LoopInfo");
68    }
69
70    bool hasChanged() const { return Changed; }
71
72    /// Iteratively perform simplification on a worklist of users of the
73    /// specified induction variable. This is the top-level driver that applies
74    /// all simplicitions to users of an IV.
75    void simplifyUsers(PHINode *CurrIV, IVVisitor *V = NULL);
76
77    Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
78
79    bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
80    void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
81    void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
82                              bool IsSigned);
83
84    Instruction *splitOverflowIntrinsic(Instruction *IVUser,
85                                        const DominatorTree *DT);
86  };
87}
88
89/// foldIVUser - Fold an IV operand into its use.  This removes increments of an
90/// aligned IV when used by a instruction that ignores the low bits.
91///
92/// IVOperand is guaranteed SCEVable, but UseInst may not be.
93///
94/// Return the operand of IVOperand for this induction variable if IVOperand can
95/// be folded (in case more folding opportunities have been exposed).
96/// Otherwise return null.
97Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
98  Value *IVSrc = 0;
99  unsigned OperIdx = 0;
100  const SCEV *FoldedExpr = 0;
101  switch (UseInst->getOpcode()) {
102  default:
103    return 0;
104  case Instruction::UDiv:
105  case Instruction::LShr:
106    // We're only interested in the case where we know something about
107    // the numerator and have a constant denominator.
108    if (IVOperand != UseInst->getOperand(OperIdx) ||
109        !isa<ConstantInt>(UseInst->getOperand(1)))
110      return 0;
111
112    // Attempt to fold a binary operator with constant operand.
113    // e.g. ((I + 1) >> 2) => I >> 2
114    if (!isa<BinaryOperator>(IVOperand)
115        || !isa<ConstantInt>(IVOperand->getOperand(1)))
116      return 0;
117
118    IVSrc = IVOperand->getOperand(0);
119    // IVSrc must be the (SCEVable) IV, since the other operand is const.
120    assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
121
122    ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
123    if (UseInst->getOpcode() == Instruction::LShr) {
124      // Get a constant for the divisor. See createSCEV.
125      uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
126      if (D->getValue().uge(BitWidth))
127        return 0;
128
129      D = ConstantInt::get(UseInst->getContext(),
130                           APInt::getOneBitSet(BitWidth, D->getZExtValue()));
131    }
132    FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
133  }
134  // We have something that might fold it's operand. Compare SCEVs.
135  if (!SE->isSCEVable(UseInst->getType()))
136    return 0;
137
138  // Bypass the operand if SCEV can prove it has no effect.
139  if (SE->getSCEV(UseInst) != FoldedExpr)
140    return 0;
141
142  DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
143        << " -> " << *UseInst << '\n');
144
145  UseInst->setOperand(OperIdx, IVSrc);
146  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
147
148  ++NumElimOperand;
149  Changed = true;
150  if (IVOperand->use_empty())
151    DeadInsts.push_back(IVOperand);
152  return IVSrc;
153}
154
155/// eliminateIVComparison - SimplifyIVUsers helper for eliminating useless
156/// comparisons against an induction variable.
157void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
158  unsigned IVOperIdx = 0;
159  ICmpInst::Predicate Pred = ICmp->getPredicate();
160  if (IVOperand != ICmp->getOperand(0)) {
161    // Swapped
162    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
163    IVOperIdx = 1;
164    Pred = ICmpInst::getSwappedPredicate(Pred);
165  }
166
167  // Get the SCEVs for the ICmp operands.
168  const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
169  const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
170
171  // Simplify unnecessary loops away.
172  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
173  S = SE->getSCEVAtScope(S, ICmpLoop);
174  X = SE->getSCEVAtScope(X, ICmpLoop);
175
176  // If the condition is always true or always false, replace it with
177  // a constant value.
178  if (SE->isKnownPredicate(Pred, S, X))
179    ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
180  else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
181    ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
182  else
183    return;
184
185  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
186  ++NumElimCmp;
187  Changed = true;
188  DeadInsts.push_back(ICmp);
189}
190
191/// eliminateIVRemainder - SimplifyIVUsers helper for eliminating useless
192/// remainder operations operating on an induction variable.
193void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
194                                      Value *IVOperand,
195                                      bool IsSigned) {
196  // We're only interested in the case where we know something about
197  // the numerator.
198  if (IVOperand != Rem->getOperand(0))
199    return;
200
201  // Get the SCEVs for the ICmp operands.
202  const SCEV *S = SE->getSCEV(Rem->getOperand(0));
203  const SCEV *X = SE->getSCEV(Rem->getOperand(1));
204
205  // Simplify unnecessary loops away.
206  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
207  S = SE->getSCEVAtScope(S, ICmpLoop);
208  X = SE->getSCEVAtScope(X, ICmpLoop);
209
210  // i % n  -->  i  if i is in [0,n).
211  if ((!IsSigned || SE->isKnownNonNegative(S)) &&
212      SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
213                           S, X))
214    Rem->replaceAllUsesWith(Rem->getOperand(0));
215  else {
216    // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
217    const SCEV *LessOne =
218      SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
219    if (IsSigned && !SE->isKnownNonNegative(LessOne))
220      return;
221
222    if (!SE->isKnownPredicate(IsSigned ?
223                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
224                              LessOne, X))
225      return;
226
227    ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
228                                  Rem->getOperand(0), Rem->getOperand(1));
229    SelectInst *Sel =
230      SelectInst::Create(ICmp,
231                         ConstantInt::get(Rem->getType(), 0),
232                         Rem->getOperand(0), "tmp", Rem);
233    Rem->replaceAllUsesWith(Sel);
234  }
235
236  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
237  ++NumElimRem;
238  Changed = true;
239  DeadInsts.push_back(Rem);
240}
241
242/// eliminateIVUser - Eliminate an operation that consumes a simple IV and has
243/// no observable side-effect given the range of IV values.
244/// IVOperand is guaranteed SCEVable, but UseInst may not be.
245bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
246                                     Instruction *IVOperand) {
247  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
248    eliminateIVComparison(ICmp, IVOperand);
249    return true;
250  }
251  if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
252    bool IsSigned = Rem->getOpcode() == Instruction::SRem;
253    if (IsSigned || Rem->getOpcode() == Instruction::URem) {
254      eliminateIVRemainder(Rem, IVOperand, IsSigned);
255      return true;
256    }
257  }
258
259  // Eliminate any operation that SCEV can prove is an identity function.
260  if (!SE->isSCEVable(UseInst->getType()) ||
261      (UseInst->getType() != IVOperand->getType()) ||
262      (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
263    return false;
264
265  DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
266
267  UseInst->replaceAllUsesWith(IVOperand);
268  ++NumElimIdentity;
269  Changed = true;
270  DeadInsts.push_back(UseInst);
271  return true;
272}
273
274/// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
275/// analysis and optimization.
276///
277/// \return A new value representing the non-overflowing add if possible,
278/// otherwise return the original value.
279Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
280                                                    const DominatorTree *DT) {
281  IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
282  if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
283    return IVUser;
284
285  // Find a branch guarded by the overflow check.
286  BranchInst *Branch = 0;
287  Instruction *AddVal = 0;
288  for (User *U : II->users()) {
289    if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
290      if (ExtractInst->getNumIndices() != 1)
291        continue;
292      if (ExtractInst->getIndices()[0] == 0)
293        AddVal = ExtractInst;
294      else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
295        Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
296    }
297  }
298  if (!AddVal || !Branch)
299    return IVUser;
300
301  BasicBlock *ContinueBB = Branch->getSuccessor(1);
302  if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
303    return IVUser;
304
305  // Check if all users of the add are provably NSW.
306  bool AllNSW = true;
307  for (Use &U : AddVal->uses()) {
308    if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
309      BasicBlock *UseBB = UseInst->getParent();
310      if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
311        UseBB = PHI->getIncomingBlock(U);
312      if (!DT->dominates(ContinueBB, UseBB)) {
313        AllNSW = false;
314        break;
315      }
316    }
317  }
318  if (!AllNSW)
319    return IVUser;
320
321  // Go for it...
322  IRBuilder<> Builder(IVUser);
323  Instruction *AddInst = dyn_cast<Instruction>(
324    Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
325
326  // The caller expects the new add to have the same form as the intrinsic. The
327  // IV operand position must be the same.
328  assert((AddInst->getOpcode() == Instruction::Add &&
329          AddInst->getOperand(0) == II->getOperand(0)) &&
330         "Bad add instruction created from overflow intrinsic.");
331
332  AddVal->replaceAllUsesWith(AddInst);
333  DeadInsts.push_back(AddVal);
334  return AddInst;
335}
336
337/// pushIVUsers - Add all uses of Def to the current IV's worklist.
338///
339static void pushIVUsers(
340  Instruction *Def,
341  SmallPtrSet<Instruction*,16> &Simplified,
342  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
343
344  for (User *U : Def->users()) {
345    Instruction *UI = cast<Instruction>(U);
346
347    // Avoid infinite or exponential worklist processing.
348    // Also ensure unique worklist users.
349    // If Def is a LoopPhi, it may not be in the Simplified set, so check for
350    // self edges first.
351    if (UI != Def && Simplified.insert(UI))
352      SimpleIVUsers.push_back(std::make_pair(UI, Def));
353  }
354}
355
356/// isSimpleIVUser - Return true if this instruction generates a simple SCEV
357/// expression in terms of that IV.
358///
359/// This is similar to IVUsers' isInteresting() but processes each instruction
360/// non-recursively when the operand is already known to be a simpleIVUser.
361///
362static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
363  if (!SE->isSCEVable(I->getType()))
364    return false;
365
366  // Get the symbolic expression for this instruction.
367  const SCEV *S = SE->getSCEV(I);
368
369  // Only consider affine recurrences.
370  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
371  if (AR && AR->getLoop() == L)
372    return true;
373
374  return false;
375}
376
377/// simplifyUsers - Iteratively perform simplification on a worklist of users
378/// of the specified induction variable. Each successive simplification may push
379/// more users which may themselves be candidates for simplification.
380///
381/// This algorithm does not require IVUsers analysis. Instead, it simplifies
382/// instructions in-place during analysis. Rather than rewriting induction
383/// variables bottom-up from their users, it transforms a chain of IVUsers
384/// top-down, updating the IR only when it encouters a clear optimization
385/// opportunitiy.
386///
387/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
388///
389void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
390  if (!SE->isSCEVable(CurrIV->getType()))
391    return;
392
393  // Instructions processed by SimplifyIndvar for CurrIV.
394  SmallPtrSet<Instruction*,16> Simplified;
395
396  // Use-def pairs if IV users waiting to be processed for CurrIV.
397  SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
398
399  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
400  // called multiple times for the same LoopPhi. This is the proper thing to
401  // do for loop header phis that use each other.
402  pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
403
404  while (!SimpleIVUsers.empty()) {
405    std::pair<Instruction*, Instruction*> UseOper =
406      SimpleIVUsers.pop_back_val();
407    Instruction *UseInst = UseOper.first;
408
409    // Bypass back edges to avoid extra work.
410    if (UseInst == CurrIV) continue;
411
412    if (V && V->shouldSplitOverflowInstrinsics()) {
413      UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
414      if (!UseInst)
415        continue;
416    }
417
418    Instruction *IVOperand = UseOper.second;
419    for (unsigned N = 0; IVOperand; ++N) {
420      assert(N <= Simplified.size() && "runaway iteration");
421
422      Value *NewOper = foldIVUser(UseOper.first, IVOperand);
423      if (!NewOper)
424        break; // done folding
425      IVOperand = dyn_cast<Instruction>(NewOper);
426    }
427    if (!IVOperand)
428      continue;
429
430    if (eliminateIVUser(UseOper.first, IVOperand)) {
431      pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
432      continue;
433    }
434    CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
435    if (V && Cast) {
436      V->visitCast(Cast);
437      continue;
438    }
439    if (isSimpleIVUser(UseOper.first, L, SE)) {
440      pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
441    }
442  }
443}
444
445namespace llvm {
446
447void IVVisitor::anchor() { }
448
449/// simplifyUsersOfIV - Simplify instructions that use this induction variable
450/// by using ScalarEvolution to analyze the IV's recurrence.
451bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
452                       SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
453{
454  LoopInfo *LI = &LPM->getAnalysis<LoopInfo>();
455  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead);
456  SIV.simplifyUsers(CurrIV, V);
457  return SIV.hasChanged();
458}
459
460/// simplifyLoopIVs - Simplify users of induction variables within this
461/// loop. This does not actually change or add IVs.
462bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM,
463                     SmallVectorImpl<WeakVH> &Dead) {
464  bool Changed = false;
465  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
466    Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
467  }
468  return Changed;
469}
470
471} // namespace llvm
472