LLVM  9.0.0svn
IndVarSimplify.cpp
Go to the documentation of this file.
1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This transformation analyzes and transforms the induction variables (and
10 // computations derived from them) into simpler forms suitable for subsequent
11 // analysis and transformation.
12 //
13 // If the trip count of a loop is computable, this pass also makes the following
14 // changes:
15 // 1. The exit condition for the loop is canonicalized to compare the
16 // induction value against the exit value. This turns loops like:
17 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
18 // 2. Any use outside of the loop of an expression derived from the indvar
19 // is changed to compute the derived value outside of the loop, eliminating
20 // the dependence on the exit value of the induction variable. If the only
21 // purpose of the loop is to compute the exit value of some derived
22 // expression, this transformation will make the loop dead.
23 //
24 //===----------------------------------------------------------------------===//
25 
27 #include "llvm/ADT/APFloat.h"
28 #include "llvm/ADT/APInt.h"
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/None.h"
32 #include "llvm/ADT/Optional.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/ADT/SmallPtrSet.h"
35 #include "llvm/ADT/SmallVector.h"
36 #include "llvm/ADT/Statistic.h"
38 #include "llvm/Analysis/LoopInfo.h"
39 #include "llvm/Analysis/LoopPass.h"
46 #include "llvm/IR/BasicBlock.h"
47 #include "llvm/IR/Constant.h"
48 #include "llvm/IR/ConstantRange.h"
49 #include "llvm/IR/Constants.h"
50 #include "llvm/IR/DataLayout.h"
51 #include "llvm/IR/DerivedTypes.h"
52 #include "llvm/IR/Dominators.h"
53 #include "llvm/IR/Function.h"
54 #include "llvm/IR/IRBuilder.h"
55 #include "llvm/IR/InstrTypes.h"
56 #include "llvm/IR/Instruction.h"
57 #include "llvm/IR/Instructions.h"
58 #include "llvm/IR/IntrinsicInst.h"
59 #include "llvm/IR/Intrinsics.h"
60 #include "llvm/IR/Module.h"
61 #include "llvm/IR/Operator.h"
62 #include "llvm/IR/PassManager.h"
63 #include "llvm/IR/PatternMatch.h"
64 #include "llvm/IR/Type.h"
65 #include "llvm/IR/Use.h"
66 #include "llvm/IR/User.h"
67 #include "llvm/IR/Value.h"
68 #include "llvm/IR/ValueHandle.h"
69 #include "llvm/Pass.h"
70 #include "llvm/Support/Casting.h"
72 #include "llvm/Support/Compiler.h"
73 #include "llvm/Support/Debug.h"
77 #include "llvm/Transforms/Scalar.h"
82 #include <cassert>
83 #include <cstdint>
84 #include <utility>
85 
86 using namespace llvm;
87 
88 #define DEBUG_TYPE "indvars"
89 
90 STATISTIC(NumWidened , "Number of indvars widened");
91 STATISTIC(NumReplaced , "Number of exit values replaced");
92 STATISTIC(NumLFTR , "Number of loop exit tests replaced");
93 STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated");
94 STATISTIC(NumElimIV , "Number of congruent IVs eliminated");
95 
96 // Trip count verification can be enabled by default under NDEBUG if we
97 // implement a strong expression equivalence checker in SCEV. Until then, we
98 // use the verify-indvars flag, which may assert in some cases.
100  "verify-indvars", cl::Hidden,
101  cl::desc("Verify the ScalarEvolution result after running indvars"));
102 
104 
106  "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
107  cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
108  cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
109  clEnumValN(OnlyCheapRepl, "cheap",
110  "only replace exit value when the cost is cheap"),
111  clEnumValN(AlwaysRepl, "always",
112  "always replace exit value whenever possible")));
113 
115  "indvars-post-increment-ranges", cl::Hidden,
116  cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),
117  cl::init(true));
118 
119 static cl::opt<bool>
120 DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),
121  cl::desc("Disable Linear Function Test Replace optimization"));
122 
123 namespace {
124 
125 struct RewritePhi;
126 
127 class IndVarSimplify {
128  LoopInfo *LI;
129  ScalarEvolution *SE;
130  DominatorTree *DT;
131  const DataLayout &DL;
132  TargetLibraryInfo *TLI;
133  const TargetTransformInfo *TTI;
134 
136 
137  bool isValidRewrite(Value *FromVal, Value *ToVal);
138 
139  bool handleFloatingPointIV(Loop *L, PHINode *PH);
140  bool rewriteNonIntegerIVs(Loop *L);
141 
142  bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
143 
144  bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
145  bool rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
146  bool rewriteFirstIterationLoopExitValues(Loop *L);
147  bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) const;
148 
149  bool linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
150  PHINode *IndVar, SCEVExpander &Rewriter);
151 
152  bool sinkUnusedInvariants(Loop *L);
153 
154 public:
155  IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
156  const DataLayout &DL, TargetLibraryInfo *TLI,
157  TargetTransformInfo *TTI)
158  : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}
159 
160  bool run(Loop *L);
161 };
162 
163 } // end anonymous namespace
164 
165 /// Return true if the SCEV expansion generated by the rewriter can replace the
166 /// original value. SCEV guarantees that it produces the same value, but the way
167 /// it is produced may be illegal IR. Ideally, this function will only be
168 /// called for verification.
169 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
170  // If an SCEV expression subsumed multiple pointers, its expansion could
171  // reassociate the GEP changing the base pointer. This is illegal because the
172  // final address produced by a GEP chain must be inbounds relative to its
173  // underlying object. Otherwise basic alias analysis, among other things,
174  // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
175  // producing an expression involving multiple pointers. Until then, we must
176  // bail out here.
177  //
178  // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
179  // because it understands lcssa phis while SCEV does not.
180  Value *FromPtr = FromVal;
181  Value *ToPtr = ToVal;
182  if (auto *GEP = dyn_cast<GEPOperator>(FromVal)) {
183  FromPtr = GEP->getPointerOperand();
184  }
185  if (auto *GEP = dyn_cast<GEPOperator>(ToVal)) {
186  ToPtr = GEP->getPointerOperand();
187  }
188  if (FromPtr != FromVal || ToPtr != ToVal) {
189  // Quickly check the common case
190  if (FromPtr == ToPtr)
191  return true;
192 
193  // SCEV may have rewritten an expression that produces the GEP's pointer
194  // operand. That's ok as long as the pointer operand has the same base
195  // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
196  // base of a recurrence. This handles the case in which SCEV expansion
197  // converts a pointer type recurrence into a nonrecurrent pointer base
198  // indexed by an integer recurrence.
199 
200  // If the GEP base pointer is a vector of pointers, abort.
201  if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
202  return false;
203 
204  const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
205  const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
206  if (FromBase == ToBase)
207  return true;
208 
209  LLVM_DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " << *FromBase
210  << " != " << *ToBase << "\n");
211 
212  return false;
213  }
214  return true;
215 }
216 
217 /// Determine the insertion point for this user. By default, insert immediately
218 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
219 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
220 /// common dominator for the incoming blocks.
222  DominatorTree *DT, LoopInfo *LI) {
223  PHINode *PHI = dyn_cast<PHINode>(User);
224  if (!PHI)
225  return User;
226 
227  Instruction *InsertPt = nullptr;
228  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
229  if (PHI->getIncomingValue(i) != Def)
230  continue;
231 
232  BasicBlock *InsertBB = PHI->getIncomingBlock(i);
233  if (!InsertPt) {
234  InsertPt = InsertBB->getTerminator();
235  continue;
236  }
237  InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
238  InsertPt = InsertBB->getTerminator();
239  }
240  assert(InsertPt && "Missing phi operand");
241 
242  auto *DefI = dyn_cast<Instruction>(Def);
243  if (!DefI)
244  return InsertPt;
245 
246  assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
247 
248  auto *L = LI->getLoopFor(DefI->getParent());
249  assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
250 
251  for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
252  if (LI->getLoopFor(DTN->getBlock()) == L)
253  return DTN->getBlock()->getTerminator();
254 
255  llvm_unreachable("DefI dominates InsertPt!");
256 }
257 
258 //===----------------------------------------------------------------------===//
259 // rewriteNonIntegerIVs and helpers. Prefer integer IVs.
260 //===----------------------------------------------------------------------===//
261 
262 /// Convert APF to an integer, if possible.
263 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
264  bool isExact = false;
265  // See if we can convert this to an int64_t
266  uint64_t UIntVal;
267  if (APF.convertToInteger(makeMutableArrayRef(UIntVal), 64, true,
268  APFloat::rmTowardZero, &isExact) != APFloat::opOK ||
269  !isExact)
270  return false;
271  IntVal = UIntVal;
272  return true;
273 }
274 
275 /// If the loop has floating induction variable then insert corresponding
276 /// integer induction variable if possible.
277 /// For example,
278 /// for(double i = 0; i < 10000; ++i)
279 /// bar(i)
280 /// is converted into
281 /// for(int i = 0; i < 10000; ++i)
282 /// bar((double)i);
283 bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
284  unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
285  unsigned BackEdge = IncomingEdge^1;
286 
287  // Check incoming value.
288  auto *InitValueVal = dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));
289 
290  int64_t InitValue;
291  if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
292  return false;
293 
294  // Check IV increment. Reject this PN if increment operation is not
295  // an add or increment value can not be represented by an integer.
296  auto *Incr = dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));
297  if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return false;
298 
299  // If this is not an add of the PHI with a constantfp, or if the constant fp
300  // is not an integer, bail out.
301  ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
302  int64_t IncValue;
303  if (IncValueVal == nullptr || Incr->getOperand(0) != PN ||
304  !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))
305  return false;
306 
307  // Check Incr uses. One user is PN and the other user is an exit condition
308  // used by the conditional terminator.
309  Value::user_iterator IncrUse = Incr->user_begin();
310  Instruction *U1 = cast<Instruction>(*IncrUse++);
311  if (IncrUse == Incr->user_end()) return false;
312  Instruction *U2 = cast<Instruction>(*IncrUse++);
313  if (IncrUse != Incr->user_end()) return false;
314 
315  // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't
316  // only used by a branch, we can't transform it.
318  if (!Compare)
319  Compare = dyn_cast<FCmpInst>(U2);
320  if (!Compare || !Compare->hasOneUse() ||
321  !isa<BranchInst>(Compare->user_back()))
322  return false;
323 
324  BranchInst *TheBr = cast<BranchInst>(Compare->user_back());
325 
326  // We need to verify that the branch actually controls the iteration count
327  // of the loop. If not, the new IV can overflow and no one will notice.
328  // The branch block must be in the loop and one of the successors must be out
329  // of the loop.
330  assert(TheBr->isConditional() && "Can't use fcmp if not conditional");
331  if (!L->contains(TheBr->getParent()) ||
332  (L->contains(TheBr->getSuccessor(0)) &&
333  L->contains(TheBr->getSuccessor(1))))
334  return false;
335 
336  // If it isn't a comparison with an integer-as-fp (the exit value), we can't
337  // transform it.
338  ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
339  int64_t ExitValue;
340  if (ExitValueVal == nullptr ||
341  !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))
342  return false;
343 
344  // Find new predicate for integer comparison.
346  switch (Compare->getPredicate()) {
347  default: return false; // Unknown comparison.
348  case CmpInst::FCMP_OEQ:
349  case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;
350  case CmpInst::FCMP_ONE:
351  case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;
352  case CmpInst::FCMP_OGT:
353  case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;
354  case CmpInst::FCMP_OGE:
355  case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;
356  case CmpInst::FCMP_OLT:
357  case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;
358  case CmpInst::FCMP_OLE:
359  case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;
360  }
361 
362  // We convert the floating point induction variable to a signed i32 value if
363  // we can. This is only safe if the comparison will not overflow in a way
364  // that won't be trapped by the integer equivalent operations. Check for this
365  // now.
366  // TODO: We could use i64 if it is native and the range requires it.
367 
368  // The start/stride/exit values must all fit in signed i32.
369  if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
370  return false;
371 
372  // If not actually striding (add x, 0.0), avoid touching the code.
373  if (IncValue == 0)
374  return false;
375 
376  // Positive and negative strides have different safety conditions.
377  if (IncValue > 0) {
378  // If we have a positive stride, we require the init to be less than the
379  // exit value.
380  if (InitValue >= ExitValue)
381  return false;
382 
383  uint32_t Range = uint32_t(ExitValue-InitValue);
384  // Check for infinite loop, either:
385  // while (i <= Exit) or until (i > Exit)
386  if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) {
387  if (++Range == 0) return false; // Range overflows.
388  }
389 
390  unsigned Leftover = Range % uint32_t(IncValue);
391 
392  // If this is an equality comparison, we require that the strided value
393  // exactly land on the exit value, otherwise the IV condition will wrap
394  // around and do things the fp IV wouldn't.
395  if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
396  Leftover != 0)
397  return false;
398 
399  // If the stride would wrap around the i32 before exiting, we can't
400  // transform the IV.
401  if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
402  return false;
403  } else {
404  // If we have a negative stride, we require the init to be greater than the
405  // exit value.
406  if (InitValue <= ExitValue)
407  return false;
408 
409  uint32_t Range = uint32_t(InitValue-ExitValue);
410  // Check for infinite loop, either:
411  // while (i >= Exit) or until (i < Exit)
412  if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) {
413  if (++Range == 0) return false; // Range overflows.
414  }
415 
416  unsigned Leftover = Range % uint32_t(-IncValue);
417 
418  // If this is an equality comparison, we require that the strided value
419  // exactly land on the exit value, otherwise the IV condition will wrap
420  // around and do things the fp IV wouldn't.
421  if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
422  Leftover != 0)
423  return false;
424 
425  // If the stride would wrap around the i32 before exiting, we can't
426  // transform the IV.
427  if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
428  return false;
429  }
430 
432 
433  // Insert new integer induction variable.
434  PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN);
435  NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),
436  PN->getIncomingBlock(IncomingEdge));
437 
438  Value *NewAdd =
439  BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),
440  Incr->getName()+".int", Incr);
441  NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));
442 
443  ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,
444  ConstantInt::get(Int32Ty, ExitValue),
445  Compare->getName());
446 
447  // In the following deletions, PN may become dead and may be deleted.
448  // Use a WeakTrackingVH to observe whether this happens.
449  WeakTrackingVH WeakPH = PN;
450 
451  // Delete the old floating point exit comparison. The branch starts using the
452  // new comparison.
453  NewCompare->takeName(Compare);
454  Compare->replaceAllUsesWith(NewCompare);
456 
457  // Delete the old floating point increment.
458  Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
460 
461  // If the FP induction variable still has uses, this is because something else
462  // in the loop uses its value. In order to canonicalize the induction
463  // variable, we chose to eliminate the IV and rewrite it in terms of an
464  // int->fp cast.
465  //
466  // We give preference to sitofp over uitofp because it is faster on most
467  // platforms.
468  if (WeakPH) {
469  Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
470  &*PN->getParent()->getFirstInsertionPt());
471  PN->replaceAllUsesWith(Conv);
473  }
474  return true;
475 }
476 
477 bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
478  // First step. Check to see if there are any floating-point recurrences.
479  // If there are, change them into integer recurrences, permitting analysis by
480  // the SCEV routines.
481  BasicBlock *Header = L->getHeader();
482 
484  for (PHINode &PN : Header->phis())
485  PHIs.push_back(&PN);
486 
487  bool Changed = false;
488  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
489  if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i]))
490  Changed |= handleFloatingPointIV(L, PN);
491 
492  // If the loop previously had floating-point IV, ScalarEvolution
493  // may not have been able to compute a trip count. Now that we've done some
494  // re-writing, the trip count may be computable.
495  if (Changed)
496  SE->forgetLoop(L);
497  return Changed;
498 }
499 
500 namespace {
501 
502 // Collect information about PHI nodes which can be transformed in
503 // rewriteLoopExitValues.
504 struct RewritePhi {
505  PHINode *PN;
506 
507  // Ith incoming value.
508  unsigned Ith;
509 
510  // Exit value after expansion.
511  Value *Val;
512 
513  // High Cost when expansion.
514  bool HighCost;
515 
516  RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
517  : PN(P), Ith(I), Val(V), HighCost(H) {}
518 };
519 
520 } // end anonymous namespace
521 
522 //===----------------------------------------------------------------------===//
523 // rewriteLoopExitValues - Optimize IV users outside the loop.
524 // As a side effect, reduces the amount of IV processing within the loop.
525 //===----------------------------------------------------------------------===//
526 
527 bool IndVarSimplify::hasHardUserWithinLoop(const Loop *L, const Instruction *I) const {
530  Visited.insert(I);
531  WorkList.push_back(I);
532  while (!WorkList.empty()) {
533  const Instruction *Curr = WorkList.pop_back_val();
534  // This use is outside the loop, nothing to do.
535  if (!L->contains(Curr))
536  continue;
537  // Do we assume it is a "hard" use which will not be eliminated easily?
538  if (Curr->mayHaveSideEffects())
539  return true;
540  // Otherwise, add all its users to worklist.
541  for (auto U : Curr->users()) {
542  auto *UI = cast<Instruction>(U);
543  if (Visited.insert(UI).second)
544  WorkList.push_back(UI);
545  }
546  }
547  return false;
548 }
549 
550 /// Check to see if this loop has a computable loop-invariant execution count.
551 /// If so, this means that we can compute the final value of any expressions
552 /// that are recurrent in the loop, and substitute the exit values from the loop
553 /// into any instructions outside of the loop that use the final values of the
554 /// current expressions.
555 ///
556 /// This is mostly redundant with the regular IndVarSimplify activities that
557 /// happen later, except that it's more powerful in some cases, because it's
558 /// able to brute-force evaluate arbitrary instructions as long as they have
559 /// constant operands at the beginning of the loop.
560 bool IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
561  // Check a pre-condition.
562  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
563  "Indvars did not preserve LCSSA!");
564 
565  SmallVector<BasicBlock*, 8> ExitBlocks;
566  L->getUniqueExitBlocks(ExitBlocks);
567 
568  SmallVector<RewritePhi, 8> RewritePhiSet;
569  // Find all values that are computed inside the loop, but used outside of it.
570  // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
571  // the exit blocks of the loop to find them.
572  for (BasicBlock *ExitBB : ExitBlocks) {
573  // If there are no PHI nodes in this exit block, then no values defined
574  // inside the loop are used on this path, skip it.
575  PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
576  if (!PN) continue;
577 
578  unsigned NumPreds = PN->getNumIncomingValues();
579 
580  // Iterate over all of the PHI nodes.
581  BasicBlock::iterator BBI = ExitBB->begin();
582  while ((PN = dyn_cast<PHINode>(BBI++))) {
583  if (PN->use_empty())
584  continue; // dead use, don't replace it
585 
586  if (!SE->isSCEVable(PN->getType()))
587  continue;
588 
589  // It's necessary to tell ScalarEvolution about this explicitly so that
590  // it can walk the def-use list and forget all SCEVs, as it may not be
591  // watching the PHI itself. Once the new exit value is in place, there
592  // may not be a def-use connection between the loop and every instruction
593  // which got a SCEVAddRecExpr for that loop.
594  SE->forgetValue(PN);
595 
596  // Iterate over all of the values in all the PHI nodes.
597  for (unsigned i = 0; i != NumPreds; ++i) {
598  // If the value being merged in is not integer or is not defined
599  // in the loop, skip it.
600  Value *InVal = PN->getIncomingValue(i);
601  if (!isa<Instruction>(InVal))
602  continue;
603 
604  // If this pred is for a subloop, not L itself, skip it.
605  if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
606  continue; // The Block is in a subloop, skip it.
607 
608  // Check that InVal is defined in the loop.
609  Instruction *Inst = cast<Instruction>(InVal);
610  if (!L->contains(Inst))
611  continue;
612 
613  // Okay, this instruction has a user outside of the current loop
614  // and varies predictably *inside* the loop. Evaluate the value it
615  // contains when the loop exits, if possible.
616  const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
617  if (!SE->isLoopInvariant(ExitValue, L) ||
618  !isSafeToExpand(ExitValue, *SE))
619  continue;
620 
621  // Computing the value outside of the loop brings no benefit if it is
622  // definitely used inside the loop in a way which can not be optimized
623  // away.
624  if (!isa<SCEVConstant>(ExitValue) && hasHardUserWithinLoop(L, Inst))
625  continue;
626 
627  bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
628  Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
629 
630  LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
631  << '\n'
632  << " LoopVal = " << *Inst << "\n");
633 
634  if (!isValidRewrite(Inst, ExitVal)) {
635  DeadInsts.push_back(ExitVal);
636  continue;
637  }
638 
639 #ifndef NDEBUG
640  // If we reuse an instruction from a loop which is neither L nor one of
641  // its containing loops, we end up breaking LCSSA form for this loop by
642  // creating a new use of its instruction.
643  if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
644  if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
645  if (EVL != L)
646  assert(EVL->contains(L) && "LCSSA breach detected!");
647 #endif
648 
649  // Collect all the candidate PHINodes to be rewritten.
650  RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
651  }
652  }
653  }
654 
655  bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
656 
657  bool Changed = false;
658  // Transformation.
659  for (const RewritePhi &Phi : RewritePhiSet) {
660  PHINode *PN = Phi.PN;
661  Value *ExitVal = Phi.Val;
662 
663  // Only do the rewrite when the ExitValue can be expanded cheaply.
664  // If LoopCanBeDel is true, rewrite exit value aggressively.
665  if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
666  DeadInsts.push_back(ExitVal);
667  continue;
668  }
669 
670  Changed = true;
671  ++NumReplaced;
672  Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
673  PN->setIncomingValue(Phi.Ith, ExitVal);
674 
675  // If this instruction is dead now, delete it. Don't do it now to avoid
676  // invalidating iterators.
677  if (isInstructionTriviallyDead(Inst, TLI))
678  DeadInsts.push_back(Inst);
679 
680  // Replace PN with ExitVal if that is legal and does not break LCSSA.
681  if (PN->getNumIncomingValues() == 1 &&
682  LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
683  PN->replaceAllUsesWith(ExitVal);
684  PN->eraseFromParent();
685  }
686  }
687 
688  // The insertion point instruction may have been deleted; clear it out
689  // so that the rewriter doesn't trip over it later.
690  Rewriter.clearInsertPoint();
691  return Changed;
692 }
693 
694 //===---------------------------------------------------------------------===//
695 // rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
696 // they will exit at the first iteration.
697 //===---------------------------------------------------------------------===//
698 
699 /// Check to see if this loop has loop invariant conditions which lead to loop
700 /// exits. If so, we know that if the exit path is taken, it is at the first
701 /// loop iteration. This lets us predict exit values of PHI nodes that live in
702 /// loop header.
703 bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
704  // Verify the input to the pass is already in LCSSA form.
705  assert(L->isLCSSAForm(*DT));
706 
707  SmallVector<BasicBlock *, 8> ExitBlocks;
708  L->getUniqueExitBlocks(ExitBlocks);
709  auto *LoopHeader = L->getHeader();
710  assert(LoopHeader && "Invalid loop");
711 
712  bool MadeAnyChanges = false;
713  for (auto *ExitBB : ExitBlocks) {
714  // If there are no more PHI nodes in this exit block, then no more
715  // values defined inside the loop are used on this path.
716  for (PHINode &PN : ExitBB->phis()) {
717  for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();
718  IncomingValIdx != E; ++IncomingValIdx) {
719  auto *IncomingBB = PN.getIncomingBlock(IncomingValIdx);
720 
721  // We currently only support loop exits from loop header. If the
722  // incoming block is not loop header, we need to recursively check
723  // all conditions starting from loop header are loop invariants.
724  // Additional support might be added in the future.
725  if (IncomingBB != LoopHeader)
726  continue;
727 
728  // Get condition that leads to the exit path.
729  auto *TermInst = IncomingBB->getTerminator();
730 
731  Value *Cond = nullptr;
732  if (auto *BI = dyn_cast<BranchInst>(TermInst)) {
733  // Must be a conditional branch, otherwise the block
734  // should not be in the loop.
735  Cond = BI->getCondition();
736  } else if (auto *SI = dyn_cast<SwitchInst>(TermInst))
737  Cond = SI->getCondition();
738  else
739  continue;
740 
741  if (!L->isLoopInvariant(Cond))
742  continue;
743 
744  auto *ExitVal = dyn_cast<PHINode>(PN.getIncomingValue(IncomingValIdx));
745 
746  // Only deal with PHIs.
747  if (!ExitVal)
748  continue;
749 
750  // If ExitVal is a PHI on the loop header, then we know its
751  // value along this exit because the exit can only be taken
752  // on the first iteration.
753  auto *LoopPreheader = L->getLoopPreheader();
754  assert(LoopPreheader && "Invalid loop");
755  int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
756  if (PreheaderIdx != -1) {
757  assert(ExitVal->getParent() == LoopHeader &&
758  "ExitVal must be in loop header");
759  MadeAnyChanges = true;
760  PN.setIncomingValue(IncomingValIdx,
761  ExitVal->getIncomingValue(PreheaderIdx));
762  }
763  }
764  }
765  }
766  return MadeAnyChanges;
767 }
768 
769 /// Check whether it is possible to delete the loop after rewriting exit
770 /// value. If it is possible, ignore ReplaceExitValue and do rewriting
771 /// aggressively.
772 bool IndVarSimplify::canLoopBeDeleted(
773  Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
774  BasicBlock *Preheader = L->getLoopPreheader();
775  // If there is no preheader, the loop will not be deleted.
776  if (!Preheader)
777  return false;
778 
779  // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
780  // We obviate multiple ExitingBlocks case for simplicity.
781  // TODO: If we see testcase with multiple ExitingBlocks can be deleted
782  // after exit value rewriting, we can enhance the logic here.
783  SmallVector<BasicBlock *, 4> ExitingBlocks;
784  L->getExitingBlocks(ExitingBlocks);
785  SmallVector<BasicBlock *, 8> ExitBlocks;
786  L->getUniqueExitBlocks(ExitBlocks);
787  if (ExitBlocks.size() > 1 || ExitingBlocks.size() > 1)
788  return false;
789 
790  BasicBlock *ExitBlock = ExitBlocks[0];
791  BasicBlock::iterator BI = ExitBlock->begin();
792  while (PHINode *P = dyn_cast<PHINode>(BI)) {
793  Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
794 
795  // If the Incoming value of P is found in RewritePhiSet, we know it
796  // could be rewritten to use a loop invariant value in transformation
797  // phase later. Skip it in the loop invariant check below.
798  bool found = false;
799  for (const RewritePhi &Phi : RewritePhiSet) {
800  unsigned i = Phi.Ith;
801  if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
802  found = true;
803  break;
804  }
805  }
806 
807  Instruction *I;
808  if (!found && (I = dyn_cast<Instruction>(Incoming)))
809  if (!L->hasLoopInvariantOperands(I))
810  return false;
811 
812  ++BI;
813  }
814 
815  for (auto *BB : L->blocks())
816  if (llvm::any_of(*BB, [](Instruction &I) {
817  return I.mayHaveSideEffects();
818  }))
819  return false;
820 
821  return true;
822 }
823 
824 //===----------------------------------------------------------------------===//
825 // IV Widening - Extend the width of an IV to cover its widest uses.
826 //===----------------------------------------------------------------------===//
827 
828 namespace {
829 
830 // Collect information about induction variables that are used by sign/zero
831 // extend operations. This information is recorded by CollectExtend and provides
832 // the input to WidenIV.
833 struct WideIVInfo {
834  PHINode *NarrowIV = nullptr;
835 
836  // Widest integer type created [sz]ext
837  Type *WidestNativeType = nullptr;
838 
839  // Was a sext user seen before a zext?
840  bool IsSigned = false;
841 };
842 
843 } // end anonymous namespace
844 
845 /// Update information about the induction variable that is extended by this
846 /// sign or zero extend operation. This is used to determine the final width of
847 /// the IV before actually widening it.
848 static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE,
849  const TargetTransformInfo *TTI) {
850  bool IsSigned = Cast->getOpcode() == Instruction::SExt;
851  if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
852  return;
853 
854  Type *Ty = Cast->getType();
855  uint64_t Width = SE->getTypeSizeInBits(Ty);
856  if (!Cast->getModule()->getDataLayout().isLegalInteger(Width))
857  return;
858 
859  // Check that `Cast` actually extends the induction variable (we rely on this
860  // later). This takes care of cases where `Cast` is extending a truncation of
861  // the narrow induction variable, and thus can end up being narrower than the
862  // "narrow" induction variable.
863  uint64_t NarrowIVWidth = SE->getTypeSizeInBits(WI.NarrowIV->getType());
864  if (NarrowIVWidth >= Width)
865  return;
866 
867  // Cast is either an sext or zext up to this point.
868  // We should not widen an indvar if arithmetics on the wider indvar are more
869  // expensive than those on the narrower indvar. We check only the cost of ADD
870  // because at least an ADD is required to increment the induction variable. We
871  // could compute more comprehensively the cost of all instructions on the
872  // induction variable when necessary.
873  if (TTI &&
876  Cast->getOperand(0)->getType())) {
877  return;
878  }
879 
880  if (!WI.WidestNativeType) {
881  WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
882  WI.IsSigned = IsSigned;
883  return;
884  }
885 
886  // We extend the IV to satisfy the sign of its first user, arbitrarily.
887  if (WI.IsSigned != IsSigned)
888  return;
889 
890  if (Width > SE->getTypeSizeInBits(WI.WidestNativeType))
891  WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
892 }
893 
894 namespace {
895 
896 /// Record a link in the Narrow IV def-use chain along with the WideIV that
897 /// computes the same value as the Narrow IV def. This avoids caching Use*
898 /// pointers.
899 struct NarrowIVDefUse {
900  Instruction *NarrowDef = nullptr;
901  Instruction *NarrowUse = nullptr;
902  Instruction *WideDef = nullptr;
903 
904  // True if the narrow def is never negative. Tracking this information lets
905  // us use a sign extension instead of a zero extension or vice versa, when
906  // profitable and legal.
907  bool NeverNegative = false;
908 
909  NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
910  bool NeverNegative)
911  : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
912  NeverNegative(NeverNegative) {}
913 };
914 
915 /// The goal of this transform is to remove sign and zero extends without
916 /// creating any new induction variables. To do this, it creates a new phi of
917 /// the wider type and redirects all users, either removing extends or inserting
918 /// truncs whenever we stop propagating the type.
919 class WidenIV {
920  // Parameters
921  PHINode *OrigPhi;
922  Type *WideType;
923 
924  // Context
925  LoopInfo *LI;
926  Loop *L;
927  ScalarEvolution *SE;
928  DominatorTree *DT;
929 
930  // Does the module have any calls to the llvm.experimental.guard intrinsic
931  // at all? If not we can avoid scanning instructions looking for guards.
932  bool HasGuards;
933 
934  // Result
935  PHINode *WidePhi = nullptr;
936  Instruction *WideInc = nullptr;
937  const SCEV *WideIncExpr = nullptr;
939 
941  SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
942 
943  enum ExtendKind { ZeroExtended, SignExtended, Unknown };
944 
945  // A map tracking the kind of extension used to widen each narrow IV
946  // and narrow IV user.
947  // Key: pointer to a narrow IV or IV user.
948  // Value: the kind of extension used to widen this Instruction.
949  DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
950 
951  using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
952 
953  // A map with control-dependent ranges for post increment IV uses. The key is
954  // a pair of IV def and a use of this def denoting the context. The value is
955  // a ConstantRange representing possible values of the def at the given
956  // context.
957  DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
958 
959  Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
960  Instruction *UseI) {
961  DefUserPair Key(Def, UseI);
962  auto It = PostIncRangeInfos.find(Key);
963  return It == PostIncRangeInfos.end()
965  : Optional<ConstantRange>(It->second);
966  }
967 
968  void calculatePostIncRanges(PHINode *OrigPhi);
969  void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
970 
971  void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
972  DefUserPair Key(Def, UseI);
973  auto It = PostIncRangeInfos.find(Key);
974  if (It == PostIncRangeInfos.end())
975  PostIncRangeInfos.insert({Key, R});
976  else
977  It->second = R.intersectWith(It->second);
978  }
979 
980 public:
981  WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
983  bool HasGuards)
984  : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
985  L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
986  HasGuards(HasGuards), DeadInsts(DI) {
987  assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
988  ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
989  }
990 
991  PHINode *createWideIV(SCEVExpander &Rewriter);
992 
993 protected:
994  Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
995  Instruction *Use);
996 
997  Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
998  Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
999  const SCEVAddRecExpr *WideAR);
1000  Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1001 
1002  ExtendKind getExtendKind(Instruction *I);
1003 
1004  using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1005 
1006  WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1007 
1008  WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1009 
1010  const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1011  unsigned OpCode) const;
1012 
1013  Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
1014 
1015  bool widenLoopCompare(NarrowIVDefUse DU);
1016  bool widenWithVariantLoadUse(NarrowIVDefUse DU);
1017  void widenWithVariantLoadUseCodegen(NarrowIVDefUse DU);
1018 
1019  void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1020 };
1021 
1022 } // end anonymous namespace
1023 
1024 /// Perform a quick domtree based check for loop invariance assuming that V is
1025 /// used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this
1026 /// purpose.
1027 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) {
1028  Instruction *Inst = dyn_cast<Instruction>(V);
1029  if (!Inst)
1030  return true;
1031 
1032  return DT->properlyDominates(Inst->getParent(), L->getHeader());
1033 }
1034 
1035 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1036  bool IsSigned, Instruction *Use) {
1037  // Set the debug location and conservative insertion point.
1038  IRBuilder<> Builder(Use);
1039  // Hoist the insertion point into loop preheaders as far as possible.
1040  for (const Loop *L = LI->getLoopFor(Use->getParent());
1041  L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT);
1042  L = L->getParentLoop())
1044 
1045  return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1046  Builder.CreateZExt(NarrowOper, WideType);
1047 }
1048 
1049 /// Instantiate a wide operation to replace a narrow operation. This only needs
1050 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1051 /// 0 for any operation we decide not to clone.
1052 Instruction *WidenIV::cloneIVUser(NarrowIVDefUse DU,
1053  const SCEVAddRecExpr *WideAR) {
1054  unsigned Opcode = DU.NarrowUse->getOpcode();
1055  switch (Opcode) {
1056  default:
1057  return nullptr;
1058  case Instruction::Add:
1059  case Instruction::Mul:
1060  case Instruction::UDiv:
1061  case Instruction::Sub:
1062  return cloneArithmeticIVUser(DU, WideAR);
1063 
1064  case Instruction::And:
1065  case Instruction::Or:
1066  case Instruction::Xor:
1067  case Instruction::Shl:
1068  case Instruction::LShr:
1069  case Instruction::AShr:
1070  return cloneBitwiseIVUser(DU);
1071  }
1072 }
1073 
1074 Instruction *WidenIV::cloneBitwiseIVUser(NarrowIVDefUse DU) {
1075  Instruction *NarrowUse = DU.NarrowUse;
1076  Instruction *NarrowDef = DU.NarrowDef;
1077  Instruction *WideDef = DU.WideDef;
1078 
1079  LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1080 
1081  // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1082  // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1083  // invariant and will be folded or hoisted. If it actually comes from a
1084  // widened IV, it should be removed during a future call to widenIVUse.
1085  bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1086  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1087  ? WideDef
1088  : createExtendInst(NarrowUse->getOperand(0), WideType,
1089  IsSigned, NarrowUse);
1090  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1091  ? WideDef
1092  : createExtendInst(NarrowUse->getOperand(1), WideType,
1093  IsSigned, NarrowUse);
1094 
1095  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1096  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1097  NarrowBO->getName());
1098  IRBuilder<> Builder(NarrowUse);
1099  Builder.Insert(WideBO);
1100  WideBO->copyIRFlags(NarrowBO);
1101  return WideBO;
1102 }
1103 
1104 Instruction *WidenIV::cloneArithmeticIVUser(NarrowIVDefUse DU,
1105  const SCEVAddRecExpr *WideAR) {
1106  Instruction *NarrowUse = DU.NarrowUse;
1107  Instruction *NarrowDef = DU.NarrowDef;
1108  Instruction *WideDef = DU.WideDef;
1109 
1110  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1111 
1112  unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1113 
1114  // We're trying to find X such that
1115  //
1116  // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1117  //
1118  // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1119  // and check using SCEV if any of them are correct.
1120 
1121  // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1122  // correct solution to X.
1123  auto GuessNonIVOperand = [&](bool SignExt) {
1124  const SCEV *WideLHS;
1125  const SCEV *WideRHS;
1126 
1127  auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1128  if (SignExt)
1129  return SE->getSignExtendExpr(S, Ty);
1130  return SE->getZeroExtendExpr(S, Ty);
1131  };
1132 
1133  if (IVOpIdx == 0) {
1134  WideLHS = SE->getSCEV(WideDef);
1135  const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1136  WideRHS = GetExtend(NarrowRHS, WideType);
1137  } else {
1138  const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1139  WideLHS = GetExtend(NarrowLHS, WideType);
1140  WideRHS = SE->getSCEV(WideDef);
1141  }
1142 
1143  // WideUse is "WideDef `op.wide` X" as described in the comment.
1144  const SCEV *WideUse = nullptr;
1145 
1146  switch (NarrowUse->getOpcode()) {
1147  default:
1148  llvm_unreachable("No other possibility!");
1149 
1150  case Instruction::Add:
1151  WideUse = SE->getAddExpr(WideLHS, WideRHS);
1152  break;
1153 
1154  case Instruction::Mul:
1155  WideUse = SE->getMulExpr(WideLHS, WideRHS);
1156  break;
1157 
1158  case Instruction::UDiv:
1159  WideUse = SE->getUDivExpr(WideLHS, WideRHS);
1160  break;
1161 
1162  case Instruction::Sub:
1163  WideUse = SE->getMinusSCEV(WideLHS, WideRHS);
1164  break;
1165  }
1166 
1167  return WideUse == WideAR;
1168  };
1169 
1170  bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1171  if (!GuessNonIVOperand(SignExtend)) {
1172  SignExtend = !SignExtend;
1173  if (!GuessNonIVOperand(SignExtend))
1174  return nullptr;
1175  }
1176 
1177  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1178  ? WideDef
1179  : createExtendInst(NarrowUse->getOperand(0), WideType,
1180  SignExtend, NarrowUse);
1181  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1182  ? WideDef
1183  : createExtendInst(NarrowUse->getOperand(1), WideType,
1184  SignExtend, NarrowUse);
1185 
1186  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1187  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1188  NarrowBO->getName());
1189 
1190  IRBuilder<> Builder(NarrowUse);
1191  Builder.Insert(WideBO);
1192  WideBO->copyIRFlags(NarrowBO);
1193  return WideBO;
1194 }
1195 
1196 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1197  auto It = ExtendKindMap.find(I);
1198  assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1199  return It->second;
1200 }
1201 
1202 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1203  unsigned OpCode) const {
1204  if (OpCode == Instruction::Add)
1205  return SE->getAddExpr(LHS, RHS);
1206  if (OpCode == Instruction::Sub)
1207  return SE->getMinusSCEV(LHS, RHS);
1208  if (OpCode == Instruction::Mul)
1209  return SE->getMulExpr(LHS, RHS);
1210 
1211  llvm_unreachable("Unsupported opcode.");
1212 }
1213 
1214 /// No-wrap operations can transfer sign extension of their result to their
1215 /// operands. Generate the SCEV value for the widened operation without
1216 /// actually modifying the IR yet. If the expression after extending the
1217 /// operands is an AddRec for this loop, return the AddRec and the kind of
1218 /// extension used.
1219 WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
1220  // Handle the common case of add<nsw/nuw>
1221  const unsigned OpCode = DU.NarrowUse->getOpcode();
1222  // Only Add/Sub/Mul instructions supported yet.
1223  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1224  OpCode != Instruction::Mul)
1225  return {nullptr, Unknown};
1226 
1227  // One operand (NarrowDef) has already been extended to WideDef. Now determine
1228  // if extending the other will lead to a recurrence.
1229  const unsigned ExtendOperIdx =
1230  DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1231  assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1232 
1233  const SCEV *ExtendOperExpr = nullptr;
1234  const OverflowingBinaryOperator *OBO =
1235  cast<OverflowingBinaryOperator>(DU.NarrowUse);
1236  ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1237  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1238  ExtendOperExpr = SE->getSignExtendExpr(
1239  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1240  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1241  ExtendOperExpr = SE->getZeroExtendExpr(
1242  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1243  else
1244  return {nullptr, Unknown};
1245 
1246  // When creating this SCEV expr, don't apply the current operations NSW or NUW
1247  // flags. This instruction may be guarded by control flow that the no-wrap
1248  // behavior depends on. Non-control-equivalent instructions can be mapped to
1249  // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1250  // semantics to those operations.
1251  const SCEV *lhs = SE->getSCEV(DU.WideDef);
1252  const SCEV *rhs = ExtendOperExpr;
1253 
1254  // Let's swap operands to the initial order for the case of non-commutative
1255  // operations, like SUB. See PR21014.
1256  if (ExtendOperIdx == 0)
1257  std::swap(lhs, rhs);
1258  const SCEVAddRecExpr *AddRec =
1259  dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1260 
1261  if (!AddRec || AddRec->getLoop() != L)
1262  return {nullptr, Unknown};
1263 
1264  return {AddRec, ExtKind};
1265 }
1266 
1267 /// Is this instruction potentially interesting for further simplification after
1268 /// widening it's type? In other words, can the extend be safely hoisted out of
1269 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1270 /// so, return the extended recurrence and the kind of extension used. Otherwise
1271 /// return {nullptr, Unknown}.
1272 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(NarrowIVDefUse DU) {
1273  if (!SE->isSCEVable(DU.NarrowUse->getType()))
1274  return {nullptr, Unknown};
1275 
1276  const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1277  if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1278  SE->getTypeSizeInBits(WideType)) {
1279  // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1280  // index. So don't follow this use.
1281  return {nullptr, Unknown};
1282  }
1283 
1284  const SCEV *WideExpr;
1285  ExtendKind ExtKind;
1286  if (DU.NeverNegative) {
1287  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1288  if (isa<SCEVAddRecExpr>(WideExpr))
1289  ExtKind = SignExtended;
1290  else {
1291  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1292  ExtKind = ZeroExtended;
1293  }
1294  } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1295  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1296  ExtKind = SignExtended;
1297  } else {
1298  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1299  ExtKind = ZeroExtended;
1300  }
1301  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1302  if (!AddRec || AddRec->getLoop() != L)
1303  return {nullptr, Unknown};
1304  return {AddRec, ExtKind};
1305 }
1306 
1307 /// This IV user cannot be widen. Replace this use of the original narrow IV
1308 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1309 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
1310  LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1311  << *DU.NarrowUse << "\n");
1312  IRBuilder<> Builder(
1313  getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
1314  Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1315  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1316 }
1317 
1318 /// If the narrow use is a compare instruction, then widen the compare
1319 // (and possibly the other operand). The extend operation is hoisted into the
1320 // loop preheader as far as possible.
1321 bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
1322  ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1323  if (!Cmp)
1324  return false;
1325 
1326  // We can legally widen the comparison in the following two cases:
1327  //
1328  // - The signedness of the IV extension and comparison match
1329  //
1330  // - The narrow IV is always positive (and thus its sign extension is equal
1331  // to its zero extension). For instance, let's say we're zero extending
1332  // %narrow for the following use
1333  //
1334  // icmp slt i32 %narrow, %val ... (A)
1335  //
1336  // and %narrow is always positive. Then
1337  //
1338  // (A) == icmp slt i32 sext(%narrow), sext(%val)
1339  // == icmp slt i32 zext(%narrow), sext(%val)
1340  bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1341  if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1342  return false;
1343 
1344  Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1345  unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1346  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1347  assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1348 
1349  // Widen the compare instruction.
1350  IRBuilder<> Builder(
1351  getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
1352  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1353 
1354  // Widen the other operand of the compare, if necessary.
1355  if (CastWidth < IVWidth) {
1356  Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1357  DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1358  }
1359  return true;
1360 }
1361 
1362 /// If the narrow use is an instruction whose two operands are the defining
1363 /// instruction of DU and a load instruction, then we have the following:
1364 /// if the load is hoisted outside the loop, then we do not reach this function
1365 /// as scalar evolution analysis works fine in widenIVUse with variables
1366 /// hoisted outside the loop and efficient code is subsequently generated by
1367 /// not emitting truncate instructions. But when the load is not hoisted
1368 /// (whether due to limitation in alias analysis or due to a true legality),
1369 /// then scalar evolution can not proceed with loop variant values and
1370 /// inefficient code is generated. This function handles the non-hoisted load
1371 /// special case by making the optimization generate the same type of code for
1372 /// hoisted and non-hoisted load (widen use and eliminate sign extend
1373 /// instruction). This special case is important especially when the induction
1374 /// variables are affecting addressing mode in code generation.
1375 bool WidenIV::widenWithVariantLoadUse(NarrowIVDefUse DU) {
1376  Instruction *NarrowUse = DU.NarrowUse;
1377  Instruction *NarrowDef = DU.NarrowDef;
1378  Instruction *WideDef = DU.WideDef;
1379 
1380  // Handle the common case of add<nsw/nuw>
1381  const unsigned OpCode = NarrowUse->getOpcode();
1382  // Only Add/Sub/Mul instructions are supported.
1383  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1384  OpCode != Instruction::Mul)
1385  return false;
1386 
1387  // The operand that is not defined by NarrowDef of DU. Let's call it the
1388  // other operand.
1389  unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == NarrowDef ? 1 : 0;
1390  assert(DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef &&
1391  "bad DU");
1392 
1393  const SCEV *ExtendOperExpr = nullptr;
1394  const OverflowingBinaryOperator *OBO =
1395  cast<OverflowingBinaryOperator>(NarrowUse);
1396  ExtendKind ExtKind = getExtendKind(NarrowDef);
1397  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1398  ExtendOperExpr = SE->getSignExtendExpr(
1399  SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
1400  else if (ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1401  ExtendOperExpr = SE->getZeroExtendExpr(
1402  SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
1403  else
1404  return false;
1405 
1406  // We are interested in the other operand being a load instruction.
1407  // But, we should look into relaxing this restriction later on.
1408  auto *I = dyn_cast<Instruction>(NarrowUse->getOperand(ExtendOperIdx));
1409  if (I && I->getOpcode() != Instruction::Load)
1410  return false;
1411 
1412  // Verifying that Defining operand is an AddRec
1413  const SCEV *Op1 = SE->getSCEV(WideDef);
1414  const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
1415  if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1416  return false;
1417  // Verifying that other operand is an Extend.
1418  if (ExtKind == SignExtended) {
1419  if (!isa<SCEVSignExtendExpr>(ExtendOperExpr))
1420  return false;
1421  } else {
1422  if (!isa<SCEVZeroExtendExpr>(ExtendOperExpr))
1423  return false;
1424  }
1425 
1426  if (ExtKind == SignExtended) {
1427  for (Use &U : NarrowUse->uses()) {
1428  SExtInst *User = dyn_cast<SExtInst>(U.getUser());
1429  if (!User || User->getType() != WideType)
1430  return false;
1431  }
1432  } else { // ExtKind == ZeroExtended
1433  for (Use &U : NarrowUse->uses()) {
1434  ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
1435  if (!User || User->getType() != WideType)
1436  return false;
1437  }
1438  }
1439 
1440  return true;
1441 }
1442 
1443 /// Special Case for widening with variant Loads (see
1444 /// WidenIV::widenWithVariantLoadUse). This is the code generation part.
1445 void WidenIV::widenWithVariantLoadUseCodegen(NarrowIVDefUse DU) {
1446  Instruction *NarrowUse = DU.NarrowUse;
1447  Instruction *NarrowDef = DU.NarrowDef;
1448  Instruction *WideDef = DU.WideDef;
1449 
1450  ExtendKind ExtKind = getExtendKind(NarrowDef);
1451 
1452  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1453 
1454  // Generating a widening use instruction.
1455  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1456  ? WideDef
1457  : createExtendInst(NarrowUse->getOperand(0), WideType,
1458  ExtKind, NarrowUse);
1459  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1460  ? WideDef
1461  : createExtendInst(NarrowUse->getOperand(1), WideType,
1462  ExtKind, NarrowUse);
1463 
1464  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1465  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1466  NarrowBO->getName());
1467  IRBuilder<> Builder(NarrowUse);
1468  Builder.Insert(WideBO);
1469  WideBO->copyIRFlags(NarrowBO);
1470 
1471  if (ExtKind == SignExtended)
1472  ExtendKindMap[NarrowUse] = SignExtended;
1473  else
1474  ExtendKindMap[NarrowUse] = ZeroExtended;
1475 
1476  // Update the Use.
1477  if (ExtKind == SignExtended) {
1478  for (Use &U : NarrowUse->uses()) {
1479  SExtInst *User = dyn_cast<SExtInst>(U.getUser());
1480  if (User && User->getType() == WideType) {
1481  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1482  << *WideBO << "\n");
1483  ++NumElimExt;
1484  User->replaceAllUsesWith(WideBO);
1485  DeadInsts.emplace_back(User);
1486  }
1487  }
1488  } else { // ExtKind == ZeroExtended
1489  for (Use &U : NarrowUse->uses()) {
1490  ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
1491  if (User && User->getType() == WideType) {
1492  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1493  << *WideBO << "\n");
1494  ++NumElimExt;
1495  User->replaceAllUsesWith(WideBO);
1496  DeadInsts.emplace_back(User);
1497  }
1498  }
1499  }
1500 }
1501 
1502 /// Determine whether an individual user of the narrow IV can be widened. If so,
1503 /// return the wide clone of the user.
1504 Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
1505  assert(ExtendKindMap.count(DU.NarrowDef) &&
1506  "Should already know the kind of extension used to widen NarrowDef");
1507 
1508  // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1509  if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1510  if (LI->getLoopFor(UsePhi->getParent()) != L) {
1511  // For LCSSA phis, sink the truncate outside the loop.
1512  // After SimplifyCFG most loop exit targets have a single predecessor.
1513  // Otherwise fall back to a truncate within the loop.
1514  if (UsePhi->getNumOperands() != 1)
1515  truncateIVUse(DU, DT, LI);
1516  else {
1517  // Widening the PHI requires us to insert a trunc. The logical place
1518  // for this trunc is in the same BB as the PHI. This is not possible if
1519  // the BB is terminated by a catchswitch.
1520  if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1521  return nullptr;
1522 
1523  PHINode *WidePhi =
1524  PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1525  UsePhi);
1526  WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1527  IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
1528  Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1529  UsePhi->replaceAllUsesWith(Trunc);
1530  DeadInsts.emplace_back(UsePhi);
1531  LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1532  << *WidePhi << "\n");
1533  }
1534  return nullptr;
1535  }
1536  }
1537 
1538  // This narrow use can be widened by a sext if it's non-negative or its narrow
1539  // def was widended by a sext. Same for zext.
1540  auto canWidenBySExt = [&]() {
1541  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1542  };
1543  auto canWidenByZExt = [&]() {
1544  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1545  };
1546 
1547  // Our raison d'etre! Eliminate sign and zero extension.
1548  if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1549  (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1550  Value *NewDef = DU.WideDef;
1551  if (DU.NarrowUse->getType() != WideType) {
1552  unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1553  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1554  if (CastWidth < IVWidth) {
1555  // The cast isn't as wide as the IV, so insert a Trunc.
1556  IRBuilder<> Builder(DU.NarrowUse);
1557  NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1558  }
1559  else {
1560  // A wider extend was hidden behind a narrower one. This may induce
1561  // another round of IV widening in which the intermediate IV becomes
1562  // dead. It should be very rare.
1563  LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1564  << " not wide enough to subsume " << *DU.NarrowUse
1565  << "\n");
1566  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1567  NewDef = DU.NarrowUse;
1568  }
1569  }
1570  if (NewDef != DU.NarrowUse) {
1571  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1572  << " replaced by " << *DU.WideDef << "\n");
1573  ++NumElimExt;
1574  DU.NarrowUse->replaceAllUsesWith(NewDef);
1575  DeadInsts.emplace_back(DU.NarrowUse);
1576  }
1577  // Now that the extend is gone, we want to expose it's uses for potential
1578  // further simplification. We don't need to directly inform SimplifyIVUsers
1579  // of the new users, because their parent IV will be processed later as a
1580  // new loop phi. If we preserved IVUsers analysis, we would also want to
1581  // push the uses of WideDef here.
1582 
1583  // No further widening is needed. The deceased [sz]ext had done it for us.
1584  return nullptr;
1585  }
1586 
1587  // Does this user itself evaluate to a recurrence after widening?
1588  WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1589  if (!WideAddRec.first)
1590  WideAddRec = getWideRecurrence(DU);
1591 
1592  assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
1593  if (!WideAddRec.first) {
1594  // If use is a loop condition, try to promote the condition instead of
1595  // truncating the IV first.
1596  if (widenLoopCompare(DU))
1597  return nullptr;
1598 
1599  // We are here about to generate a truncate instruction that may hurt
1600  // performance because the scalar evolution expression computed earlier
1601  // in WideAddRec.first does not indicate a polynomial induction expression.
1602  // In that case, look at the operands of the use instruction to determine
1603  // if we can still widen the use instead of truncating its operand.
1604  if (widenWithVariantLoadUse(DU)) {
1605  widenWithVariantLoadUseCodegen(DU);
1606  return nullptr;
1607  }
1608 
1609  // This user does not evaluate to a recurrence after widening, so don't
1610  // follow it. Instead insert a Trunc to kill off the original use,
1611  // eventually isolating the original narrow IV so it can be removed.
1612  truncateIVUse(DU, DT, LI);
1613  return nullptr;
1614  }
1615  // Assume block terminators cannot evaluate to a recurrence. We can't to
1616  // insert a Trunc after a terminator if there happens to be a critical edge.
1617  assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
1618  "SCEV is not expected to evaluate a block terminator");
1619 
1620  // Reuse the IV increment that SCEVExpander created as long as it dominates
1621  // NarrowUse.
1622  Instruction *WideUse = nullptr;
1623  if (WideAddRec.first == WideIncExpr &&
1624  Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1625  WideUse = WideInc;
1626  else {
1627  WideUse = cloneIVUser(DU, WideAddRec.first);
1628  if (!WideUse)
1629  return nullptr;
1630  }
1631  // Evaluation of WideAddRec ensured that the narrow expression could be
1632  // extended outside the loop without overflow. This suggests that the wide use
1633  // evaluates to the same expression as the extended narrow use, but doesn't
1634  // absolutely guarantee it. Hence the following failsafe check. In rare cases
1635  // where it fails, we simply throw away the newly created wide use.
1636  if (WideAddRec.first != SE->getSCEV(WideUse)) {
1637  LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1638  << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1639  << "\n");
1640  DeadInsts.emplace_back(WideUse);
1641  return nullptr;
1642  }
1643 
1644  ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1645  // Returning WideUse pushes it on the worklist.
1646  return WideUse;
1647 }
1648 
1649 /// Add eligible users of NarrowDef to NarrowIVUsers.
1650 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
1651  const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1652  bool NonNegativeDef =
1653  SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1654  SE->getConstant(NarrowSCEV->getType(), 0));
1655  for (User *U : NarrowDef->users()) {
1656  Instruction *NarrowUser = cast<Instruction>(U);
1657 
1658  // Handle data flow merges and bizarre phi cycles.
1659  if (!Widened.insert(NarrowUser).second)
1660  continue;
1661 
1662  bool NonNegativeUse = false;
1663  if (!NonNegativeDef) {
1664  // We might have a control-dependent range information for this context.
1665  if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1666  NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1667  }
1668 
1669  NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1670  NonNegativeDef || NonNegativeUse);
1671  }
1672 }
1673 
1674 /// Process a single induction variable. First use the SCEVExpander to create a
1675 /// wide induction variable that evaluates to the same recurrence as the
1676 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1677 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1678 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1679 ///
1680 /// It would be simpler to delete uses as they are processed, but we must avoid
1681 /// invalidating SCEV expressions.
1682 PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
1683  // Is this phi an induction variable?
1684  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1685  if (!AddRec)
1686  return nullptr;
1687 
1688  // Widen the induction variable expression.
1689  const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1690  ? SE->getSignExtendExpr(AddRec, WideType)
1691  : SE->getZeroExtendExpr(AddRec, WideType);
1692 
1693  assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1694  "Expect the new IV expression to preserve its type");
1695 
1696  // Can the IV be extended outside the loop without overflow?
1697  AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1698  if (!AddRec || AddRec->getLoop() != L)
1699  return nullptr;
1700 
1701  // An AddRec must have loop-invariant operands. Since this AddRec is
1702  // materialized by a loop header phi, the expression cannot have any post-loop
1703  // operands, so they must dominate the loop header.
1704  assert(
1705  SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1706  SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1707  "Loop header phi recurrence inputs do not dominate the loop");
1708 
1709  // Iterate over IV uses (including transitive ones) looking for IV increments
1710  // of the form 'add nsw %iv, <const>'. For each increment and each use of
1711  // the increment calculate control-dependent range information basing on
1712  // dominating conditions inside of the loop (e.g. a range check inside of the
1713  // loop). Calculated ranges are stored in PostIncRangeInfos map.
1714  //
1715  // Control-dependent range information is later used to prove that a narrow
1716  // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1717  // this on demand because when pushNarrowIVUsers needs this information some
1718  // of the dominating conditions might be already widened.
1719  if (UsePostIncrementRanges)
1720  calculatePostIncRanges(OrigPhi);
1721 
1722  // The rewriter provides a value for the desired IV expression. This may
1723  // either find an existing phi or materialize a new one. Either way, we
1724  // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1725  // of the phi-SCC dominates the loop entry.
1726  Instruction *InsertPt = &L->getHeader()->front();
1727  WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));
1728 
1729  // Remembering the WideIV increment generated by SCEVExpander allows
1730  // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1731  // employ a general reuse mechanism because the call above is the only call to
1732  // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1733  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1734  WideInc =
1735  cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1736  WideIncExpr = SE->getSCEV(WideInc);
1737  // Propagate the debug location associated with the original loop increment
1738  // to the new (widened) increment.
1739  auto *OrigInc =
1740  cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1741  WideInc->setDebugLoc(OrigInc->getDebugLoc());
1742  }
1743 
1744  LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1745  ++NumWidened;
1746 
1747  // Traverse the def-use chain using a worklist starting at the original IV.
1748  assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1749 
1750  Widened.insert(OrigPhi);
1751  pushNarrowIVUsers(OrigPhi, WidePhi);
1752 
1753  while (!NarrowIVUsers.empty()) {
1754  NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1755 
1756  // Process a def-use edge. This may replace the use, so don't hold a
1757  // use_iterator across it.
1758  Instruction *WideUse = widenIVUse(DU, Rewriter);
1759 
1760  // Follow all def-use edges from the previous narrow use.
1761  if (WideUse)
1762  pushNarrowIVUsers(DU.NarrowUse, WideUse);
1763 
1764  // widenIVUse may have removed the def-use edge.
1765  if (DU.NarrowDef->use_empty())
1766  DeadInsts.emplace_back(DU.NarrowDef);
1767  }
1768 
1769  // Attach any debug information to the new PHI. Since OrigPhi and WidePHI
1770  // evaluate the same recurrence, we can just copy the debug info over.
1772  llvm::findDbgValues(DbgValues, OrigPhi);
1773  auto *MDPhi = MetadataAsValue::get(WidePhi->getContext(),
1774  ValueAsMetadata::get(WidePhi));
1775  for (auto &DbgValue : DbgValues)
1776  DbgValue->setOperand(0, MDPhi);
1777  return WidePhi;
1778 }
1779 
1780 /// Calculates control-dependent range for the given def at the given context
1781 /// by looking at dominating conditions inside of the loop
1782 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1783  Instruction *NarrowUser) {
1784  using namespace llvm::PatternMatch;
1785 
1786  Value *NarrowDefLHS;
1787  const APInt *NarrowDefRHS;
1788  if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1789  m_APInt(NarrowDefRHS))) ||
1790  !NarrowDefRHS->isNonNegative())
1791  return;
1792 
1793  auto UpdateRangeFromCondition = [&] (Value *Condition,
1794  bool TrueDest) {
1795  CmpInst::Predicate Pred;
1796  Value *CmpRHS;
1797  if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
1798  m_Value(CmpRHS))))
1799  return;
1800 
1802  TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
1803 
1804  auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
1805  auto CmpConstrainedLHSRange =
1806  ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
1807  auto NarrowDefRange =
1808  CmpConstrainedLHSRange.addWithNoSignedWrap(*NarrowDefRHS);
1809 
1810  updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
1811  };
1812 
1813  auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
1814  if (!HasGuards)
1815  return;
1816 
1817  for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
1818  Ctx->getParent()->rend())) {
1819  Value *C = nullptr;
1820  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
1821  UpdateRangeFromCondition(C, /*TrueDest=*/true);
1822  }
1823  };
1824 
1825  UpdateRangeFromGuards(NarrowUser);
1826 
1827  BasicBlock *NarrowUserBB = NarrowUser->getParent();
1828  // If NarrowUserBB is statically unreachable asking dominator queries may
1829  // yield surprising results. (e.g. the block may not have a dom tree node)
1830  if (!DT->isReachableFromEntry(NarrowUserBB))
1831  return;
1832 
1833  for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
1834  L->contains(DTB->getBlock());
1835  DTB = DTB->getIDom()) {
1836  auto *BB = DTB->getBlock();
1837  auto *TI = BB->getTerminator();
1838  UpdateRangeFromGuards(TI);
1839 
1840  auto *BI = dyn_cast<BranchInst>(TI);
1841  if (!BI || !BI->isConditional())
1842  continue;
1843 
1844  auto *TrueSuccessor = BI->getSuccessor(0);
1845  auto *FalseSuccessor = BI->getSuccessor(1);
1846 
1847  auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
1848  return BBE.isSingleEdge() &&
1849  DT->dominates(BBE, NarrowUser->getParent());
1850  };
1851 
1852  if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
1853  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
1854 
1855  if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
1856  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
1857  }
1858 }
1859 
1860 /// Calculates PostIncRangeInfos map for the given IV
1861 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
1864  Worklist.push_back(OrigPhi);
1865  Visited.insert(OrigPhi);
1866 
1867  while (!Worklist.empty()) {
1868  Instruction *NarrowDef = Worklist.pop_back_val();
1869 
1870  for (Use &U : NarrowDef->uses()) {
1871  auto *NarrowUser = cast<Instruction>(U.getUser());
1872 
1873  // Don't go looking outside the current loop.
1874  auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
1875  if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
1876  continue;
1877 
1878  if (!Visited.insert(NarrowUser).second)
1879  continue;
1880 
1881  Worklist.push_back(NarrowUser);
1882 
1883  calculatePostIncRange(NarrowDef, NarrowUser);
1884  }
1885  }
1886 }
1887 
1888 //===----------------------------------------------------------------------===//
1889 // Live IV Reduction - Minimize IVs live across the loop.
1890 //===----------------------------------------------------------------------===//
1891 
1892 //===----------------------------------------------------------------------===//
1893 // Simplification of IV users based on SCEV evaluation.
1894 //===----------------------------------------------------------------------===//
1895 
1896 namespace {
1897 
1898 class IndVarSimplifyVisitor : public IVVisitor {
1899  ScalarEvolution *SE;
1900  const TargetTransformInfo *TTI;
1901  PHINode *IVPhi;
1902 
1903 public:
1904  WideIVInfo WI;
1905 
1906  IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,
1907  const TargetTransformInfo *TTI,
1908  const DominatorTree *DTree)
1909  : SE(SCEV), TTI(TTI), IVPhi(IV) {
1910  DT = DTree;
1911  WI.NarrowIV = IVPhi;
1912  }
1913 
1914  // Implement the interface used by simplifyUsersOfIV.
1915  void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
1916 };
1917 
1918 } // end anonymous namespace
1919 
1920 /// Iteratively perform simplification on a worklist of IV users. Each
1921 /// successive simplification may push more users which may themselves be
1922 /// candidates for simplification.
1923 ///
1924 /// Sign/Zero extend elimination is interleaved with IV simplification.
1925 bool IndVarSimplify::simplifyAndExtend(Loop *L,
1926  SCEVExpander &Rewriter,
1927  LoopInfo *LI) {
1929 
1930  auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction(
1931  Intrinsic::getName(Intrinsic::experimental_guard));
1932  bool HasGuards = GuardDecl && !GuardDecl->use_empty();
1933 
1934  SmallVector<PHINode*, 8> LoopPhis;
1935  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1936  LoopPhis.push_back(cast<PHINode>(I));
1937  }
1938  // Each round of simplification iterates through the SimplifyIVUsers worklist
1939  // for all current phis, then determines whether any IVs can be
1940  // widened. Widening adds new phis to LoopPhis, inducing another round of
1941  // simplification on the wide IVs.
1942  bool Changed = false;
1943  while (!LoopPhis.empty()) {
1944  // Evaluate as many IV expressions as possible before widening any IVs. This
1945  // forces SCEV to set no-wrap flags before evaluating sign/zero
1946  // extension. The first time SCEV attempts to normalize sign/zero extension,
1947  // the result becomes final. So for the most predictable results, we delay
1948  // evaluation of sign/zero extend evaluation until needed, and avoid running
1949  // other SCEV based analysis prior to simplifyAndExtend.
1950  do {
1951  PHINode *CurrIV = LoopPhis.pop_back_val();
1952 
1953  // Information about sign/zero extensions of CurrIV.
1954  IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
1955 
1956  Changed |=
1957  simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, Rewriter, &Visitor);
1958 
1959  if (Visitor.WI.WidestNativeType) {
1960  WideIVs.push_back(Visitor.WI);
1961  }
1962  } while(!LoopPhis.empty());
1963 
1964  for (; !WideIVs.empty(); WideIVs.pop_back()) {
1965  WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts, HasGuards);
1966  if (PHINode *WidePhi = Widener.createWideIV(Rewriter)) {
1967  Changed = true;
1968  LoopPhis.push_back(WidePhi);
1969  }
1970  }
1971  }
1972  return Changed;
1973 }
1974 
1975 //===----------------------------------------------------------------------===//
1976 // linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
1977 //===----------------------------------------------------------------------===//
1978 
1979 /// Return true if this loop's backedge taken count expression can be safely and
1980 /// cheaply expanded into an instruction sequence that can be used by
1981 /// linearFunctionTestReplace.
1982 ///
1983 /// TODO: This fails for pointer-type loop counters with greater than one byte
1984 /// strides, consequently preventing LFTR from running. For the purpose of LFTR
1985 /// we could skip this check in the case that the LFTR loop counter (chosen by
1986 /// FindLoopCounter) is also pointer type. Instead, we could directly convert
1987 /// the loop test to an inequality test by checking the target data's alignment
1988 /// of element types (given that the initial pointer value originates from or is
1989 /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint).
1990 /// However, we don't yet have a strong motivation for converting loop tests
1991 /// into inequality tests.
1993  SCEVExpander &Rewriter) {
1994  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1995  if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) ||
1996  BackedgeTakenCount->isZero())
1997  return false;
1998 
1999  if (!L->getExitingBlock())
2000  return false;
2001 
2002  // Can't rewrite non-branch yet.
2003  if (!isa<BranchInst>(L->getExitingBlock()->getTerminator()))
2004  return false;
2005 
2006  if (Rewriter.isHighCostExpansion(BackedgeTakenCount, L))
2007  return false;
2008 
2009  return true;
2010 }
2011 
2012 /// Return the loop header phi IFF IncV adds a loop invariant value to the phi.
2014  Instruction *IncI = dyn_cast<Instruction>(IncV);
2015  if (!IncI)
2016  return nullptr;
2017 
2018  switch (IncI->getOpcode()) {
2019  case Instruction::Add:
2020  case Instruction::Sub:
2021  break;
2022  case Instruction::GetElementPtr:
2023  // An IV counter must preserve its type.
2024  if (IncI->getNumOperands() == 2)
2025  break;
2027  default:
2028  return nullptr;
2029  }
2030 
2031  PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));
2032  if (Phi && Phi->getParent() == L->getHeader()) {
2033  if (isLoopInvariant(IncI->getOperand(1), L, DT))
2034  return Phi;
2035  return nullptr;
2036  }
2037  if (IncI->getOpcode() == Instruction::GetElementPtr)
2038  return nullptr;
2039 
2040  // Allow add/sub to be commuted.
2041  Phi = dyn_cast<PHINode>(IncI->getOperand(1));
2042  if (Phi && Phi->getParent() == L->getHeader()) {
2043  if (isLoopInvariant(IncI->getOperand(0), L, DT))
2044  return Phi;
2045  }
2046  return nullptr;
2047 }
2048 
2049 /// Return the compare guarding the loop latch, or NULL for unrecognized tests.
2051  assert(L->getExitingBlock() && "expected loop exit");
2052 
2053  BasicBlock *LatchBlock = L->getLoopLatch();
2054  // Don't bother with LFTR if the loop is not properly simplified.
2055  if (!LatchBlock)
2056  return nullptr;
2057 
2059  assert(BI && "expected exit branch");
2060 
2061  return dyn_cast<ICmpInst>(BI->getCondition());
2062 }
2063 
2064 /// linearFunctionTestReplace policy. Return true unless we can show that the
2065 /// current exit test is already sufficiently canonical.
2066 static bool needsLFTR(Loop *L, DominatorTree *DT) {
2067  // Do LFTR to simplify the exit condition to an ICMP.
2068  ICmpInst *Cond = getLoopTest(L);
2069  if (!Cond)
2070  return true;
2071 
2072  // Do LFTR to simplify the exit ICMP to EQ/NE
2073  ICmpInst::Predicate Pred = Cond->getPredicate();
2074  if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
2075  return true;
2076 
2077  // Look for a loop invariant RHS
2078  Value *LHS = Cond->getOperand(0);
2079  Value *RHS = Cond->getOperand(1);
2080  if (!isLoopInvariant(RHS, L, DT)) {
2081  if (!isLoopInvariant(LHS, L, DT))
2082  return true;
2083  std::swap(LHS, RHS);
2084  }
2085  // Look for a simple IV counter LHS
2086  PHINode *Phi = dyn_cast<PHINode>(LHS);
2087  if (!Phi)
2088  Phi = getLoopPhiForCounter(LHS, L, DT);
2089 
2090  if (!Phi)
2091  return true;
2092 
2093  // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
2094  int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
2095  if (Idx < 0)
2096  return true;
2097 
2098  // Do LFTR if the exit condition's IV is *not* a simple counter.
2099  Value *IncV = Phi->getIncomingValue(Idx);
2100  return Phi != getLoopPhiForCounter(IncV, L, DT);
2101 }
2102 
2103 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
2104 /// down to checking that all operands are constant and listing instructions
2105 /// that may hide undef.
2107  unsigned Depth) {
2108  if (isa<Constant>(V))
2109  return !isa<UndefValue>(V);
2110 
2111  if (Depth >= 6)
2112  return false;
2113 
2114  // Conservatively handle non-constant non-instructions. For example, Arguments
2115  // may be undef.
2116  Instruction *I = dyn_cast<Instruction>(V);
2117  if (!I)
2118  return false;
2119 
2120  // Load and return values may be undef.
2121  if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))
2122  return false;
2123 
2124  // Optimistically handle other instructions.
2125  for (Value *Op : I->operands()) {
2126  if (!Visited.insert(Op).second)
2127  continue;
2128  if (!hasConcreteDefImpl(Op, Visited, Depth+1))
2129  return false;
2130  }
2131  return true;
2132 }
2133 
2134 /// Return true if the given value is concrete. We must prove that undef can
2135 /// never reach it.
2136 ///
2137 /// TODO: If we decide that this is a good approach to checking for undef, we
2138 /// may factor it into a common location.
2139 static bool hasConcreteDef(Value *V) {
2140  SmallPtrSet<Value*, 8> Visited;
2141  Visited.insert(V);
2142  return hasConcreteDefImpl(V, Visited, 0);
2143 }
2144 
2145 /// Return true if this IV has any uses other than the (soon to be rewritten)
2146 /// loop exit test.
2147 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) {
2148  int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
2149  Value *IncV = Phi->getIncomingValue(LatchIdx);
2150 
2151  for (User *U : Phi->users())
2152  if (U != Cond && U != IncV) return false;
2153 
2154  for (User *U : IncV->users())
2155  if (U != Cond && U != Phi) return false;
2156  return true;
2157 }
2158 
2159 /// Find an affine IV in canonical form.
2160 ///
2161 /// BECount may be an i8* pointer type. The pointer difference is already
2162 /// valid count without scaling the address stride, so it remains a pointer
2163 /// expression as far as SCEV is concerned.
2164 ///
2165 /// Currently only valid for LFTR. See the comments on hasConcreteDef below.
2166 ///
2167 /// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount
2168 ///
2169 /// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride.
2170 /// This is difficult in general for SCEV because of potential overflow. But we
2171 /// could at least handle constant BECounts.
2172 static PHINode *FindLoopCounter(Loop *L, const SCEV *BECount,
2173  ScalarEvolution *SE, DominatorTree *DT) {
2174  uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());
2175 
2176  Value *Cond =
2177  cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition();
2178 
2179  // Loop over all of the PHI nodes, looking for a simple counter.
2180  PHINode *BestPhi = nullptr;
2181  const SCEV *BestInit = nullptr;
2182  BasicBlock *LatchBlock = L->getLoopLatch();
2183  assert(LatchBlock && "needsLFTR should guarantee a loop latch");
2184  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2185 
2186  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
2187  PHINode *Phi = cast<PHINode>(I);
2188  if (!SE->isSCEVable(Phi->getType()))
2189  continue;
2190 
2191  // Avoid comparing an integer IV against a pointer Limit.
2192  if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy())
2193  continue;
2194 
2195  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
2196  if (!AR || AR->getLoop() != L || !AR->isAffine())
2197  continue;
2198 
2199  // AR may be a pointer type, while BECount is an integer type.
2200  // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
2201  // AR may not be a narrower type, or we may never exit.
2202  uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
2203  if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))
2204  continue;
2205 
2206  const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
2207  if (!Step || !Step->isOne())
2208  continue;
2209 
2210  int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
2211  Value *IncV = Phi->getIncomingValue(LatchIdx);
2212  if (getLoopPhiForCounter(IncV, L, DT) != Phi)
2213  continue;
2214 
2215  // Avoid reusing a potentially undef value to compute other values that may
2216  // have originally had a concrete definition.
2217  if (!hasConcreteDef(Phi)) {
2218  // We explicitly allow unknown phis as long as they are already used by
2219  // the loop test. In this case we assume that performing LFTR could not
2220  // increase the number of undef users.
2221  if (ICmpInst *Cond = getLoopTest(L)) {
2222  if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT) &&
2223  Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) {
2224  continue;
2225  }
2226  }
2227  }
2228  const SCEV *Init = AR->getStart();
2229 
2230  if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
2231  // Don't force a live loop counter if another IV can be used.
2232  if (AlmostDeadIV(Phi, LatchBlock, Cond))
2233  continue;
2234 
2235  // Prefer to count-from-zero. This is a more "canonical" counter form. It
2236  // also prefers integer to pointer IVs.
2237  if (BestInit->isZero() != Init->isZero()) {
2238  if (BestInit->isZero())
2239  continue;
2240  }
2241  // If two IVs both count from zero or both count from nonzero then the
2242  // narrower is likely a dead phi that has been widened. Use the wider phi
2243  // to allow the other to be eliminated.
2244  else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))
2245  continue;
2246  }
2247  BestPhi = Phi;
2248  BestInit = Init;
2249  }
2250  return BestPhi;
2251 }
2252 
2253 /// Help linearFunctionTestReplace by generating a value that holds the RHS of
2254 /// the new loop test.
2255 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L,
2256  SCEVExpander &Rewriter, ScalarEvolution *SE) {
2257  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2258  assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter");
2259  const SCEV *IVInit = AR->getStart();
2260 
2261  // IVInit may be a pointer while IVCount is an integer when FindLoopCounter
2262  // finds a valid pointer IV. Sign extend BECount in order to materialize a
2263  // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing
2264  // the existing GEPs whenever possible.
2265  if (IndVar->getType()->isPointerTy() && !IVCount->getType()->isPointerTy()) {
2266  // IVOffset will be the new GEP offset that is interpreted by GEP as a
2267  // signed value. IVCount on the other hand represents the loop trip count,
2268  // which is an unsigned value. FindLoopCounter only allows induction
2269  // variables that have a positive unit stride of one. This means we don't
2270  // have to handle the case of negative offsets (yet) and just need to zero
2271  // extend IVCount.
2272  Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType());
2273  const SCEV *IVOffset = SE->getTruncateOrZeroExtend(IVCount, OfsTy);
2274 
2275  // Expand the code for the iteration count.
2276  assert(SE->isLoopInvariant(IVOffset, L) &&
2277  "Computed iteration count is not loop invariant!");
2278  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2279  Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI);
2280 
2281  Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader());
2282  assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter");
2283  // We could handle pointer IVs other than i8*, but we need to compensate for
2284  // gep index scaling. See canExpandBackedgeTakenCount comments.
2286  cast<PointerType>(GEPBase->getType())
2287  ->getElementType())->isOne() &&
2288  "unit stride pointer IV must be i8*");
2289 
2290  IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
2291  return Builder.CreateGEP(nullptr, GEPBase, GEPOffset, "lftr.limit");
2292  } else {
2293  // In any other case, convert both IVInit and IVCount to integers before
2294  // comparing. This may result in SCEV expansion of pointers, but in practice
2295  // SCEV will fold the pointer arithmetic away as such:
2296  // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc).
2297  //
2298  // Valid Cases: (1) both integers is most common; (2) both may be pointers
2299  // for simple memset-style loops.
2300  //
2301  // IVInit integer and IVCount pointer would only occur if a canonical IV
2302  // were generated on top of case #2, which is not expected.
2303 
2304  const SCEV *IVLimit = nullptr;
2305  // For unit stride, IVCount = Start + BECount with 2's complement overflow.
2306  // For non-zero Start, compute IVCount here.
2307  if (AR->getStart()->isZero())
2308  IVLimit = IVCount;
2309  else {
2310  assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");
2311  const SCEV *IVInit = AR->getStart();
2312 
2313  // For integer IVs, truncate the IV before computing IVInit + BECount.
2314  if (SE->getTypeSizeInBits(IVInit->getType())
2315  > SE->getTypeSizeInBits(IVCount->getType()))
2316  IVInit = SE->getTruncateExpr(IVInit, IVCount->getType());
2317 
2318  IVLimit = SE->getAddExpr(IVInit, IVCount);
2319  }
2320  // Expand the code for the iteration count.
2321  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2322  IRBuilder<> Builder(BI);
2323  assert(SE->isLoopInvariant(IVLimit, L) &&
2324  "Computed iteration count is not loop invariant!");
2325  // Ensure that we generate the same type as IndVar, or a smaller integer
2326  // type. In the presence of null pointer values, we have an integer type
2327  // SCEV expression (IVInit) for a pointer type IV value (IndVar).
2328  Type *LimitTy = IVCount->getType()->isPointerTy() ?
2329  IndVar->getType() : IVCount->getType();
2330  return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
2331  }
2332 }
2333 
2334 /// This method rewrites the exit condition of the loop to be a canonical !=
2335 /// comparison against the incremented loop induction variable. This pass is
2336 /// able to rewrite the exit tests of any loop where the SCEV analysis can
2337 /// determine a loop-invariant trip count of the loop, which is actually a much
2338 /// broader range than just linear tests.
2339 bool IndVarSimplify::
2340 linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
2341  PHINode *IndVar, SCEVExpander &Rewriter) {
2342  assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition");
2343 
2344  // Initialize CmpIndVar and IVCount to their preincremented values.
2345  Value *CmpIndVar = IndVar;
2346  const SCEV *IVCount = BackedgeTakenCount;
2347 
2348  assert(L->getLoopLatch() && "Loop no longer in simplified form?");
2349 
2350  // If the exiting block is the same as the backedge block, we prefer to
2351  // compare against the post-incremented value, otherwise we must compare
2352  // against the preincremented value.
2353  if (L->getExitingBlock() == L->getLoopLatch()) {
2354  // Add one to the "backedge-taken" count to get the trip count.
2355  // This addition may overflow, which is valid as long as the comparison is
2356  // truncated to BackedgeTakenCount->getType().
2357  IVCount = SE->getAddExpr(BackedgeTakenCount,
2358  SE->getOne(BackedgeTakenCount->getType()));
2359  // The BackedgeTaken expression contains the number of times that the
2360  // backedge branches to the loop header. This is one less than the
2361  // number of times the loop executes, so use the incremented indvar.
2362  CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock());
2363  }
2364 
2365  Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
2366  assert(ExitCnt->getType()->isPointerTy() ==
2367  IndVar->getType()->isPointerTy() &&
2368  "genLoopLimit missed a cast");
2369 
2370  // Insert a new icmp_ne or icmp_eq instruction before the branch.
2371  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2373  if (L->contains(BI->getSuccessor(0)))
2374  P = ICmpInst::ICMP_NE;
2375  else
2376  P = ICmpInst::ICMP_EQ;
2377 
2378  LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
2379  << " LHS:" << *CmpIndVar << '\n'
2380  << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")
2381  << "\n"
2382  << " RHS:\t" << *ExitCnt << "\n"
2383  << " IVCount:\t" << *IVCount << "\n");
2384 
2385  IRBuilder<> Builder(BI);
2386 
2387  // The new loop exit condition should reuse the debug location of the
2388  // original loop exit condition.
2389  if (auto *Cond = dyn_cast<Instruction>(BI->getCondition()))
2390  Builder.SetCurrentDebugLocation(Cond->getDebugLoc());
2391 
2392  // LFTR can ignore IV overflow and truncate to the width of
2393  // BECount. This avoids materializing the add(zext(add)) expression.
2394  unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());
2395  unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());
2396  if (CmpIndVarSize > ExitCntSize) {
2397  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2398  const SCEV *ARStart = AR->getStart();
2399  const SCEV *ARStep = AR->getStepRecurrence(*SE);
2400  // For constant IVCount, avoid truncation.
2401  if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) {
2402  const APInt &Start = cast<SCEVConstant>(ARStart)->getAPInt();
2403  APInt Count = cast<SCEVConstant>(IVCount)->getAPInt();
2404  // Note that the post-inc value of BackedgeTakenCount may have overflowed
2405  // above such that IVCount is now zero.
2406  if (IVCount != BackedgeTakenCount && Count == 0) {
2407  Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize);
2408  ++Count;
2409  }
2410  else
2411  Count = Count.zext(CmpIndVarSize);
2412  APInt NewLimit;
2413  if (cast<SCEVConstant>(ARStep)->getValue()->isNegative())
2414  NewLimit = Start - Count;
2415  else
2416  NewLimit = Start + Count;
2417  ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit);
2418 
2419  LLVM_DEBUG(dbgs() << " Widen RHS:\t" << *ExitCnt << "\n");
2420  } else {
2421  // We try to extend trip count first. If that doesn't work we truncate IV.
2422  // Zext(trunc(IV)) == IV implies equivalence of the following two:
2423  // Trunc(IV) == ExitCnt and IV == zext(ExitCnt). Similarly for sext. If
2424  // one of the two holds, extend the trip count, otherwise we truncate IV.
2425  bool Extended = false;
2426  const SCEV *IV = SE->getSCEV(CmpIndVar);
2427  const SCEV *ZExtTrunc =
2428  SE->getZeroExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2429  ExitCnt->getType()),
2430  CmpIndVar->getType());
2431 
2432  if (ZExtTrunc == IV) {
2433  Extended = true;
2434  ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),
2435  "wide.trip.count");
2436  } else {
2437  const SCEV *SExtTrunc =
2438  SE->getSignExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2439  ExitCnt->getType()),
2440  CmpIndVar->getType());
2441  if (SExtTrunc == IV) {
2442  Extended = true;
2443  ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->getType(),
2444  "wide.trip.count");
2445  }
2446  }
2447 
2448  if (!Extended)
2449  CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
2450  "lftr.wideiv");
2451  }
2452  }
2453  Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
2454  Value *OrigCond = BI->getCondition();
2455  // It's tempting to use replaceAllUsesWith here to fully replace the old
2456  // comparison, but that's not immediately safe, since users of the old
2457  // comparison may not be dominated by the new comparison. Instead, just
2458  // update the branch to use the new comparison; in the common case this
2459  // will make old comparison dead.
2460  BI->setCondition(Cond);
2461  DeadInsts.push_back(OrigCond);
2462 
2463  ++NumLFTR;
2464  return true;
2465 }
2466 
2467 //===----------------------------------------------------------------------===//
2468 // sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
2469 //===----------------------------------------------------------------------===//
2470 
2471 /// If there's a single exit block, sink any loop-invariant values that
2472 /// were defined in the preheader but not used inside the loop into the
2473 /// exit block to reduce register pressure in the loop.
2474 bool IndVarSimplify::sinkUnusedInvariants(Loop *L) {
2475  BasicBlock *ExitBlock = L->getExitBlock();
2476  if (!ExitBlock) return false;
2477 
2478  BasicBlock *Preheader = L->getLoopPreheader();
2479  if (!Preheader) return false;
2480 
2481  bool MadeAnyChanges = false;
2482  BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();
2483  BasicBlock::iterator I(Preheader->getTerminator());
2484  while (I != Preheader->begin()) {
2485  --I;
2486  // New instructions were inserted at the end of the preheader.
2487  if (isa<PHINode>(I))
2488  break;
2489 
2490  // Don't move instructions which might have side effects, since the side
2491  // effects need to complete before instructions inside the loop. Also don't
2492  // move instructions which might read memory, since the loop may modify
2493  // memory. Note that it's okay if the instruction might have undefined
2494  // behavior: LoopSimplify guarantees that the preheader dominates the exit
2495  // block.
2496  if (I->mayHaveSideEffects() || I->mayReadFromMemory())
2497  continue;
2498 
2499  // Skip debug info intrinsics.
2500  if (isa<DbgInfoIntrinsic>(I))
2501  continue;
2502 
2503  // Skip eh pad instructions.
2504  if (I->isEHPad())
2505  continue;
2506 
2507  // Don't sink alloca: we never want to sink static alloca's out of the
2508  // entry block, and correctly sinking dynamic alloca's requires
2509  // checks for stacksave/stackrestore intrinsics.
2510  // FIXME: Refactor this check somehow?
2511  if (isa<AllocaInst>(I))
2512  continue;
2513 
2514  // Determine if there is a use in or before the loop (direct or
2515  // otherwise).
2516  bool UsedInLoop = false;
2517  for (Use &U : I->uses()) {
2518  Instruction *User = cast<Instruction>(U.getUser());
2519  BasicBlock *UseBB = User->getParent();
2520  if (PHINode *P = dyn_cast<PHINode>(User)) {
2521  unsigned i =
2522  PHINode::getIncomingValueNumForOperand(U.getOperandNo());
2523  UseBB = P->getIncomingBlock(i);
2524  }
2525  if (UseBB == Preheader || L->contains(UseBB)) {
2526  UsedInLoop = true;
2527  break;
2528  }
2529  }
2530 
2531  // If there is, the def must remain in the preheader.
2532  if (UsedInLoop)
2533  continue;
2534 
2535  // Otherwise, sink it to the exit block.
2536  Instruction *ToMove = &*I;
2537  bool Done = false;
2538 
2539  if (I != Preheader->begin()) {
2540  // Skip debug info intrinsics.
2541  do {
2542  --I;
2543  } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
2544 
2545  if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
2546  Done = true;
2547  } else {
2548  Done = true;
2549  }
2550 
2551  MadeAnyChanges = true;
2552  ToMove->moveBefore(*ExitBlock, InsertPt);
2553  if (Done) break;
2554  InsertPt = ToMove->getIterator();
2555  }
2556 
2557  return MadeAnyChanges;
2558 }
2559 
2560 //===----------------------------------------------------------------------===//
2561 // IndVarSimplify driver. Manage several subpasses of IV simplification.
2562 //===----------------------------------------------------------------------===//
2563 
2564 bool IndVarSimplify::run(Loop *L) {
2565  // We need (and expect!) the incoming loop to be in LCSSA.
2566  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2567  "LCSSA required to run indvars!");
2568  bool Changed = false;
2569 
2570  // If LoopSimplify form is not available, stay out of trouble. Some notes:
2571  // - LSR currently only supports LoopSimplify-form loops. Indvars'
2572  // canonicalization can be a pessimization without LSR to "clean up"
2573  // afterwards.
2574  // - We depend on having a preheader; in particular,
2575  // Loop::getCanonicalInductionVariable only supports loops with preheaders,
2576  // and we're in trouble if we can't find the induction variable even when
2577  // we've manually inserted one.
2578  // - LFTR relies on having a single backedge.
2579  if (!L->isLoopSimplifyForm())
2580  return false;
2581 
2582  // If there are any floating-point recurrences, attempt to
2583  // transform them to use integer recurrences.
2584  Changed |= rewriteNonIntegerIVs(L);
2585 
2586  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
2587 
2588  // Create a rewriter object which we'll use to transform the code with.
2589  SCEVExpander Rewriter(*SE, DL, "indvars");
2590 #ifndef NDEBUG
2591  Rewriter.setDebugType(DEBUG_TYPE);
2592 #endif
2593 
2594  // Eliminate redundant IV users.
2595  //
2596  // Simplification works best when run before other consumers of SCEV. We
2597  // attempt to avoid evaluating SCEVs for sign/zero extend operations until
2598  // other expressions involving loop IVs have been evaluated. This helps SCEV
2599  // set no-wrap flags before normalizing sign/zero extension.
2600  Rewriter.disableCanonicalMode();
2601  Changed |= simplifyAndExtend(L, Rewriter, LI);
2602 
2603  // Check to see if this loop has a computable loop-invariant execution count.
2604  // If so, this means that we can compute the final value of any expressions
2605  // that are recurrent in the loop, and substitute the exit values from the
2606  // loop into any instructions outside of the loop that use the final values of
2607  // the current expressions.
2608  //
2609  if (ReplaceExitValue != NeverRepl &&
2610  !isa<SCEVCouldNotCompute>(BackedgeTakenCount))
2611  Changed |= rewriteLoopExitValues(L, Rewriter);
2612 
2613  // Eliminate redundant IV cycles.
2614  NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
2615 
2616  // If we have a trip count expression, rewrite the loop's exit condition
2617  // using it. We can currently only handle loops with a single exit.
2618  if (!DisableLFTR && canExpandBackedgeTakenCount(L, SE, Rewriter) &&
2619  needsLFTR(L, DT)) {
2620  PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT);
2621  if (IndVar) {
2622  // Check preconditions for proper SCEVExpander operation. SCEV does not
2623  // express SCEVExpander's dependencies, such as LoopSimplify. Instead any
2624  // pass that uses the SCEVExpander must do it. This does not work well for
2625  // loop passes because SCEVExpander makes assumptions about all loops,
2626  // while LoopPassManager only forces the current loop to be simplified.
2627  //
2628  // FIXME: SCEV expansion has no way to bail out, so the caller must
2629  // explicitly check any assumptions made by SCEV. Brittle.
2630  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount);
2631  if (!AR || AR->getLoop()->getLoopPreheader())
2632  Changed |= linearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
2633  Rewriter);
2634  }
2635  }
2636  // Clear the rewriter cache, because values that are in the rewriter's cache
2637  // can be deleted in the loop below, causing the AssertingVH in the cache to
2638  // trigger.
2639  Rewriter.clear();
2640 
2641  // Now that we're done iterating through lists, clean up any instructions
2642  // which are now dead.
2643  while (!DeadInsts.empty())
2644  if (Instruction *Inst =
2645  dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
2646  Changed |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
2647 
2648  // The Rewriter may not be used from this point on.
2649 
2650  // Loop-invariant instructions in the preheader that aren't used in the
2651  // loop may be sunk below the loop to reduce register pressure.
2652  Changed |= sinkUnusedInvariants(L);
2653 
2654  // rewriteFirstIterationLoopExitValues does not rely on the computation of
2655  // trip count and therefore can further simplify exit values in addition to
2656  // rewriteLoopExitValues.
2657  Changed |= rewriteFirstIterationLoopExitValues(L);
2658 
2659  // Clean up dead instructions.
2660  Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
2661 
2662  // Check a post-condition.
2663  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2664  "Indvars did not preserve LCSSA!");
2665 
2666  // Verify that LFTR, and any other change have not interfered with SCEV's
2667  // ability to compute trip count.
2668 #ifndef NDEBUG
2669  if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
2670  SE->forgetLoop(L);
2671  const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
2672  if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
2673  SE->getTypeSizeInBits(NewBECount->getType()))
2674  NewBECount = SE->getTruncateOrNoop(NewBECount,
2675  BackedgeTakenCount->getType());
2676  else
2677  BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
2678  NewBECount->getType());
2679  assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV");
2680  }
2681 #endif
2682 
2683  return Changed;
2684 }
2685 
2688  LPMUpdater &) {
2689  Function *F = L.getHeader()->getParent();
2690  const DataLayout &DL = F->getParent()->getDataLayout();
2691 
2692  IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI);
2693  if (!IVS.run(&L))
2694  return PreservedAnalyses::all();
2695 
2696  auto PA = getLoopPassPreservedAnalyses();
2697  PA.preserveSet<CFGAnalyses>();
2698  return PA;
2699 }
2700 
2701 namespace {
2702 
2703 struct IndVarSimplifyLegacyPass : public LoopPass {
2704  static char ID; // Pass identification, replacement for typeid
2705 
2706  IndVarSimplifyLegacyPass() : LoopPass(ID) {
2708  }
2709 
2710  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
2711  if (skipLoop(L))
2712  return false;
2713 
2714  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2715  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2716  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2717  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
2718  auto *TLI = TLIP ? &TLIP->getTLI() : nullptr;
2719  auto *TTIP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
2720  auto *TTI = TTIP ? &TTIP->getTTI(*L->getHeader()->getParent()) : nullptr;
2721  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2722 
2723  IndVarSimplify IVS(LI, SE, DT, DL, TLI, TTI);
2724  return IVS.run(L);
2725  }
2726 
2727  void getAnalysisUsage(AnalysisUsage &AU) const override {
2728  AU.setPreservesCFG();
2730  }
2731 };
2732 
2733 } // end anonymous namespace
2734 
2736 
2737 INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars",
2738  "Induction Variable Simplification", false, false)
2740 INITIALIZE_PASS_END(IndVarSimplifyLegacyPass, "indvars",
2741  "Induction Variable Simplification", false, false)
2742 
2744  return new IndVarSimplifyLegacyPass();
2745 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Induction Variable Simplification
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1948
iterator_range< use_iterator > uses()
Definition: Value.h:354
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT)
Perform a quick domtree based check for loop invariance assuming that V is used within the loop...
MutableArrayRef< T > makeMutableArrayRef(T &OneElt)
Construct a MutableArrayRef from a single element.
Definition: ArrayRef.h:502
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:183
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:176
This class represents zero extension of integer types.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
The main scalar evolution driver.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:857
bool isZero() const
Return true if the expression is a constant zero.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
bool isHighCostExpansion(const SCEV *Expr, Loop *L, const Instruction *At=nullptr)
Return true for expressions that may incur non-trivial cost to evaluate at runtime.
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:651
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:704
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:661
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
void setDebugType(const char *s)
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
BasicBlock * getSuccessor(unsigned i) const
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1662
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
STATISTIC(NumFunctions, "Total number of functions")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
static cl::opt< bool > UsePostIncrementRanges("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
This class represents a sign extension of integer types.
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:176
Hexagon Common GEP
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
This defines the Use class.
static bool hasConcreteDef(Value *V)
Return true if the given value is concrete.
ReplaceExitVal
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:63
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars", "Induction Variable Simplification", false, false) INITIALIZE_PASS_END(IndVarSimplifyLegacyPass
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
opStatus convertToInteger(MutableArrayRef< integerPart > Input, unsigned int Width, bool IsSigned, roundingMode RM, bool *IsExact) const
Definition: APFloat.h:1068
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:656
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
static Value * genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L, SCEVExpander &Rewriter, ScalarEvolution *SE)
Help linearFunctionTestReplace by generating a value that holds the RHS of the new loop test...
Interface for visiting interesting IV users that are recognized but not simplified by this utility...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool isSigned() const
Definition: InstrTypes.h:815
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:625
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:744
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:370
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:689
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:368
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:352
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal)
Convert APF to an integer, if possible.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:652
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockT * getHeader() const
Definition: LoopInfo.h:99
Key
PAL metadata keys.
void findDbgValues(SmallVectorImpl< DbgValueInst *> &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: Local.cpp:1494
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:605
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:181
This node represents a polynomial recurrence on the trip count of the specified loop.
This instruction compares its operands according to the predicate given to the constructor.
static Instruction * getInsertPointForUses(Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)
Determine the insertion point for this user.
static cl::opt< bool > VerifyIndvars("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars"))
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Examine each PHI in the given block and delete it if it is dead.
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
Return an expression for sizeof AllocTy that is type IntTy.
ConstantRange intersectWith(const ConstantRange &CR) const
Return the range that results from the intersection of this range with another range.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:150
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1658
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:126
Value * getOperand(unsigned i) const
Definition: User.h:169
void initializeIndVarSimplifyLegacyPassPass(PassRegistry &)
void clearInsertPoint()
Clear the current insertion point.
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:105
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:175
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:216
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:307
static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE, SCEVExpander &Rewriter)
Return true if this loop&#39;s backedge taken count expression can be safely and cheaply expanded into an...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl< Value *> &Visited, unsigned Depth)
Recursive helper for hasConcreteDef().
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:642
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
const Instruction & front() const
Definition: BasicBlock.h:280
#define H(x, y, z)
Definition: MD5.cpp:57
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:263
static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, const TargetTransformInfo *TTI)
Update information about the induction variable that is extended by this sign or zero extend operatio...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:561
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:501
Represent the analysis usage information of a pass.
This file declares a class to represent arbitrary precision floating point values and provide a varie...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:645
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
op_range operands()
Definition: User.h:237
self_iterator getIterator()
Definition: ilist_node.h:81
Class to represent integer types.
Definition: DerivedTypes.h:39
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:429
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:75
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1414
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static unsigned getIncomingValueNumForOperand(unsigned i)
size_t size() const
Definition: SmallVector.h:52
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
static ICmpInst * getLoopTest(Loop *L)
Return the compare guarding the loop latch, or NULL for unrecognized tests.
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:660
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1654
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:57
signed greater than
Definition: InstrTypes.h:672
#define DEBUG_TYPE
const APFloat & getValueAPF() const
Definition: Constants.h:302
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1457
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:649
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:109
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
Type * getType() const
Return the LLVM type of this SCEV expression.
constexpr bool isInt< 32 >(int64_t x)
Definition: MathExtras.h:308
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty)
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:348
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:659
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:845
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
Provides information about what library functions are available for the current target.
This class represents a range of values.
Definition: ConstantRange.h:46
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU...
Definition: DataLayout.h:242
signed less than
Definition: InstrTypes.h:674
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:379
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static PHINode * getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT)
Return the loop header phi IFF IncV adds a loop invariant value to the phi.
bool isConditional() const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:237
static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI)
This IV user cannot be widen.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:811
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
signed less or equal
Definition: InstrTypes.h:675
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:399
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property...
Definition: Operator.h:95
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
This class uses information about analyze scalars to rewrite expressions in canonical form...
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:529
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:617
LoopT * getParentLoop() const
Definition: LoopInfo.h:100
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:720
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:192
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:650
This class represents an analyzed expression in the program.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:148
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:213
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
user_iterator_impl< User > user_iterator
Definition: Value.h:368
bool mayReadFromMemory() const
Return true if this instruction may read memory.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:131
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:653
static bool needsLFTR(Loop *L, DominatorTree *DT)
linearFunctionTestReplace policy.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)
simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...
int getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info=OK_AnyValue, OperandValueKind Opd2Info=OK_AnyValue, OperandValueProperties Opd1PropInfo=OP_None, OperandValueProperties Opd2PropInfo=OP_None, ArrayRef< const Value *> Args=ArrayRef< const Value *>()) const
This is an approximation of reciprocal throughput of a math/logic op.
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:657
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
const SCEV * getBackedgeTakenCount(const Loop *L)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
This class represents a cast from signed integer to floating point.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
bool isOne() const
Return true if the expression is a constant one.
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:648
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:348
LLVM Value Representation.
Definition: Value.h:72
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:658
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:250
static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond)
Return true if this IV has any uses other than the (soon to be rewritten) loop exit test...
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:572
void getUniqueExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:99
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
A container for analyses that lazily runs them and caches their results.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
This pass exposes codegen information to IR-level passes.
This header defines various interfaces for pass management in LLVM.
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:155
static cl::opt< bool > DisableLFTR("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:650
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
bool use_empty() const
Definition: Value.h:322
Pass * createIndVarSimplifyPass()
signed greater or equal
Definition: InstrTypes.h:673
IntegerType * Int32Ty
const BasicBlock * getParent() const
Definition: Instruction.h:66
This class represents a constant integer value.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property...
Definition: Operator.h:89
static PHINode * FindLoopCounter(Loop *L, const SCEV *BECount, ScalarEvolution *SE, DominatorTree *DT)
Find an affine IV in canonical form.