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