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 
720  bool MadeAnyChanges = false;
721  for (auto *ExitBB : ExitBlocks) {
722  // If there are no more PHI nodes in this exit block, then no more
723  // values defined inside the loop are used on this path.
724  for (PHINode &PN : ExitBB->phis()) {
725  for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();
726  IncomingValIdx != E; ++IncomingValIdx) {
727  auto *IncomingBB = PN.getIncomingBlock(IncomingValIdx);
728 
729  // Can we prove that the exit must run on the first iteration if it
730  // runs at all? (i.e. early exits are fine for our purposes, but
731  // traces which lead to this exit being taken on the 2nd iteration
732  // aren't.) Note that this is about whether the exit branch is
733  // executed, not about whether it is taken.
734  if (!L->getLoopLatch() ||
735  !DT->dominates(IncomingBB, L->getLoopLatch()))
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 in the loop header.
757  if (!ExitVal || ExitVal->getParent() != L->getHeader())
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() == L->getHeader() &&
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 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1035  bool IsSigned, Instruction *Use) {
1036  // Set the debug location and conservative insertion point.
1037  IRBuilder<> Builder(Use);
1038  // Hoist the insertion point into loop preheaders as far as possible.
1039  for (const Loop *L = LI->getLoopFor(Use->getParent());
1040  L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
1041  L = L->getParentLoop())
1043 
1044  return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1045  Builder.CreateZExt(NarrowOper, WideType);
1046 }
1047 
1048 /// Instantiate a wide operation to replace a narrow operation. This only needs
1049 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1050 /// 0 for any operation we decide not to clone.
1051 Instruction *WidenIV::cloneIVUser(NarrowIVDefUse DU,
1052  const SCEVAddRecExpr *WideAR) {
1053  unsigned Opcode = DU.NarrowUse->getOpcode();
1054  switch (Opcode) {
1055  default:
1056  return nullptr;
1057  case Instruction::Add:
1058  case Instruction::Mul:
1059  case Instruction::UDiv:
1060  case Instruction::Sub:
1061  return cloneArithmeticIVUser(DU, WideAR);
1062 
1063  case Instruction::And:
1064  case Instruction::Or:
1065  case Instruction::Xor:
1066  case Instruction::Shl:
1067  case Instruction::LShr:
1068  case Instruction::AShr:
1069  return cloneBitwiseIVUser(DU);
1070  }
1071 }
1072 
1073 Instruction *WidenIV::cloneBitwiseIVUser(NarrowIVDefUse DU) {
1074  Instruction *NarrowUse = DU.NarrowUse;
1075  Instruction *NarrowDef = DU.NarrowDef;
1076  Instruction *WideDef = DU.WideDef;
1077 
1078  LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1079 
1080  // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1081  // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1082  // invariant and will be folded or hoisted. If it actually comes from a
1083  // widened IV, it should be removed during a future call to widenIVUse.
1084  bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1085  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1086  ? WideDef
1087  : createExtendInst(NarrowUse->getOperand(0), WideType,
1088  IsSigned, NarrowUse);
1089  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1090  ? WideDef
1091  : createExtendInst(NarrowUse->getOperand(1), WideType,
1092  IsSigned, NarrowUse);
1093 
1094  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1095  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1096  NarrowBO->getName());
1097  IRBuilder<> Builder(NarrowUse);
1098  Builder.Insert(WideBO);
1099  WideBO->copyIRFlags(NarrowBO);
1100  return WideBO;
1101 }
1102 
1103 Instruction *WidenIV::cloneArithmeticIVUser(NarrowIVDefUse DU,
1104  const SCEVAddRecExpr *WideAR) {
1105  Instruction *NarrowUse = DU.NarrowUse;
1106  Instruction *NarrowDef = DU.NarrowDef;
1107  Instruction *WideDef = DU.WideDef;
1108 
1109  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1110 
1111  unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1112 
1113  // We're trying to find X such that
1114  //
1115  // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1116  //
1117  // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1118  // and check using SCEV if any of them are correct.
1119 
1120  // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1121  // correct solution to X.
1122  auto GuessNonIVOperand = [&](bool SignExt) {
1123  const SCEV *WideLHS;
1124  const SCEV *WideRHS;
1125 
1126  auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1127  if (SignExt)
1128  return SE->getSignExtendExpr(S, Ty);
1129  return SE->getZeroExtendExpr(S, Ty);
1130  };
1131 
1132  if (IVOpIdx == 0) {
1133  WideLHS = SE->getSCEV(WideDef);
1134  const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1135  WideRHS = GetExtend(NarrowRHS, WideType);
1136  } else {
1137  const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1138  WideLHS = GetExtend(NarrowLHS, WideType);
1139  WideRHS = SE->getSCEV(WideDef);
1140  }
1141 
1142  // WideUse is "WideDef `op.wide` X" as described in the comment.
1143  const SCEV *WideUse = nullptr;
1144 
1145  switch (NarrowUse->getOpcode()) {
1146  default:
1147  llvm_unreachable("No other possibility!");
1148 
1149  case Instruction::Add:
1150  WideUse = SE->getAddExpr(WideLHS, WideRHS);
1151  break;
1152 
1153  case Instruction::Mul:
1154  WideUse = SE->getMulExpr(WideLHS, WideRHS);
1155  break;
1156 
1157  case Instruction::UDiv:
1158  WideUse = SE->getUDivExpr(WideLHS, WideRHS);
1159  break;
1160 
1161  case Instruction::Sub:
1162  WideUse = SE->getMinusSCEV(WideLHS, WideRHS);
1163  break;
1164  }
1165 
1166  return WideUse == WideAR;
1167  };
1168 
1169  bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1170  if (!GuessNonIVOperand(SignExtend)) {
1171  SignExtend = !SignExtend;
1172  if (!GuessNonIVOperand(SignExtend))
1173  return nullptr;
1174  }
1175 
1176  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1177  ? WideDef
1178  : createExtendInst(NarrowUse->getOperand(0), WideType,
1179  SignExtend, NarrowUse);
1180  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1181  ? WideDef
1182  : createExtendInst(NarrowUse->getOperand(1), WideType,
1183  SignExtend, NarrowUse);
1184 
1185  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1186  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1187  NarrowBO->getName());
1188 
1189  IRBuilder<> Builder(NarrowUse);
1190  Builder.Insert(WideBO);
1191  WideBO->copyIRFlags(NarrowBO);
1192  return WideBO;
1193 }
1194 
1195 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1196  auto It = ExtendKindMap.find(I);
1197  assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1198  return It->second;
1199 }
1200 
1201 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1202  unsigned OpCode) const {
1203  if (OpCode == Instruction::Add)
1204  return SE->getAddExpr(LHS, RHS);
1205  if (OpCode == Instruction::Sub)
1206  return SE->getMinusSCEV(LHS, RHS);
1207  if (OpCode == Instruction::Mul)
1208  return SE->getMulExpr(LHS, RHS);
1209 
1210  llvm_unreachable("Unsupported opcode.");
1211 }
1212 
1213 /// No-wrap operations can transfer sign extension of their result to their
1214 /// operands. Generate the SCEV value for the widened operation without
1215 /// actually modifying the IR yet. If the expression after extending the
1216 /// operands is an AddRec for this loop, return the AddRec and the kind of
1217 /// extension used.
1218 WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
1219  // Handle the common case of add<nsw/nuw>
1220  const unsigned OpCode = DU.NarrowUse->getOpcode();
1221  // Only Add/Sub/Mul instructions supported yet.
1222  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1223  OpCode != Instruction::Mul)
1224  return {nullptr, Unknown};
1225 
1226  // One operand (NarrowDef) has already been extended to WideDef. Now determine
1227  // if extending the other will lead to a recurrence.
1228  const unsigned ExtendOperIdx =
1229  DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1230  assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1231 
1232  const SCEV *ExtendOperExpr = nullptr;
1233  const OverflowingBinaryOperator *OBO =
1234  cast<OverflowingBinaryOperator>(DU.NarrowUse);
1235  ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1236  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1237  ExtendOperExpr = SE->getSignExtendExpr(
1238  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1239  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1240  ExtendOperExpr = SE->getZeroExtendExpr(
1241  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1242  else
1243  return {nullptr, Unknown};
1244 
1245  // When creating this SCEV expr, don't apply the current operations NSW or NUW
1246  // flags. This instruction may be guarded by control flow that the no-wrap
1247  // behavior depends on. Non-control-equivalent instructions can be mapped to
1248  // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1249  // semantics to those operations.
1250  const SCEV *lhs = SE->getSCEV(DU.WideDef);
1251  const SCEV *rhs = ExtendOperExpr;
1252 
1253  // Let's swap operands to the initial order for the case of non-commutative
1254  // operations, like SUB. See PR21014.
1255  if (ExtendOperIdx == 0)
1256  std::swap(lhs, rhs);
1257  const SCEVAddRecExpr *AddRec =
1258  dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1259 
1260  if (!AddRec || AddRec->getLoop() != L)
1261  return {nullptr, Unknown};
1262 
1263  return {AddRec, ExtKind};
1264 }
1265 
1266 /// Is this instruction potentially interesting for further simplification after
1267 /// widening it's type? In other words, can the extend be safely hoisted out of
1268 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1269 /// so, return the extended recurrence and the kind of extension used. Otherwise
1270 /// return {nullptr, Unknown}.
1271 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(NarrowIVDefUse DU) {
1272  if (!SE->isSCEVable(DU.NarrowUse->getType()))
1273  return {nullptr, Unknown};
1274 
1275  const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1276  if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1277  SE->getTypeSizeInBits(WideType)) {
1278  // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1279  // index. So don't follow this use.
1280  return {nullptr, Unknown};
1281  }
1282 
1283  const SCEV *WideExpr;
1284  ExtendKind ExtKind;
1285  if (DU.NeverNegative) {
1286  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1287  if (isa<SCEVAddRecExpr>(WideExpr))
1288  ExtKind = SignExtended;
1289  else {
1290  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1291  ExtKind = ZeroExtended;
1292  }
1293  } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1294  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1295  ExtKind = SignExtended;
1296  } else {
1297  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1298  ExtKind = ZeroExtended;
1299  }
1300  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1301  if (!AddRec || AddRec->getLoop() != L)
1302  return {nullptr, Unknown};
1303  return {AddRec, ExtKind};
1304 }
1305 
1306 /// This IV user cannot be widen. Replace this use of the original narrow IV
1307 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1308 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
1309  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1310  if (!InsertPt)
1311  return;
1312  LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1313  << *DU.NarrowUse << "\n");
1314  IRBuilder<> Builder(InsertPt);
1315  Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1316  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1317 }
1318 
1319 /// If the narrow use is a compare instruction, then widen the compare
1320 // (and possibly the other operand). The extend operation is hoisted into the
1321 // loop preheader as far as possible.
1322 bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
1323  ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1324  if (!Cmp)
1325  return false;
1326 
1327  // We can legally widen the comparison in the following two cases:
1328  //
1329  // - The signedness of the IV extension and comparison match
1330  //
1331  // - The narrow IV is always positive (and thus its sign extension is equal
1332  // to its zero extension). For instance, let's say we're zero extending
1333  // %narrow for the following use
1334  //
1335  // icmp slt i32 %narrow, %val ... (A)
1336  //
1337  // and %narrow is always positive. Then
1338  //
1339  // (A) == icmp slt i32 sext(%narrow), sext(%val)
1340  // == icmp slt i32 zext(%narrow), sext(%val)
1341  bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1342  if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1343  return false;
1344 
1345  Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1346  unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1347  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1348  assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1349 
1350  // Widen the compare instruction.
1351  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1352  if (!InsertPt)
1353  return false;
1354  IRBuilder<> Builder(InsertPt);
1355  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1356 
1357  // Widen the other operand of the compare, if necessary.
1358  if (CastWidth < IVWidth) {
1359  Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1360  DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1361  }
1362  return true;
1363 }
1364 
1365 /// If the narrow use is an instruction whose two operands are the defining
1366 /// instruction of DU and a load instruction, then we have the following:
1367 /// if the load is hoisted outside the loop, then we do not reach this function
1368 /// as scalar evolution analysis works fine in widenIVUse with variables
1369 /// hoisted outside the loop and efficient code is subsequently generated by
1370 /// not emitting truncate instructions. But when the load is not hoisted
1371 /// (whether due to limitation in alias analysis or due to a true legality),
1372 /// then scalar evolution can not proceed with loop variant values and
1373 /// inefficient code is generated. This function handles the non-hoisted load
1374 /// special case by making the optimization generate the same type of code for
1375 /// hoisted and non-hoisted load (widen use and eliminate sign extend
1376 /// instruction). This special case is important especially when the induction
1377 /// variables are affecting addressing mode in code generation.
1378 bool WidenIV::widenWithVariantLoadUse(NarrowIVDefUse DU) {
1379  Instruction *NarrowUse = DU.NarrowUse;
1380  Instruction *NarrowDef = DU.NarrowDef;
1381  Instruction *WideDef = DU.WideDef;
1382 
1383  // Handle the common case of add<nsw/nuw>
1384  const unsigned OpCode = NarrowUse->getOpcode();
1385  // Only Add/Sub/Mul instructions are supported.
1386  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1387  OpCode != Instruction::Mul)
1388  return false;
1389 
1390  // The operand that is not defined by NarrowDef of DU. Let's call it the
1391  // other operand.
1392  unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == NarrowDef ? 1 : 0;
1393  assert(DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef &&
1394  "bad DU");
1395 
1396  const SCEV *ExtendOperExpr = nullptr;
1397  const OverflowingBinaryOperator *OBO =
1398  cast<OverflowingBinaryOperator>(NarrowUse);
1399  ExtendKind ExtKind = getExtendKind(NarrowDef);
1400  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1401  ExtendOperExpr = SE->getSignExtendExpr(
1402  SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
1403  else if (ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1404  ExtendOperExpr = SE->getZeroExtendExpr(
1405  SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
1406  else
1407  return false;
1408 
1409  // We are interested in the other operand being a load instruction.
1410  // But, we should look into relaxing this restriction later on.
1411  auto *I = dyn_cast<Instruction>(NarrowUse->getOperand(ExtendOperIdx));
1412  if (I && I->getOpcode() != Instruction::Load)
1413  return false;
1414 
1415  // Verifying that Defining operand is an AddRec
1416  const SCEV *Op1 = SE->getSCEV(WideDef);
1417  const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
1418  if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1419  return false;
1420  // Verifying that other operand is an Extend.
1421  if (ExtKind == SignExtended) {
1422  if (!isa<SCEVSignExtendExpr>(ExtendOperExpr))
1423  return false;
1424  } else {
1425  if (!isa<SCEVZeroExtendExpr>(ExtendOperExpr))
1426  return false;
1427  }
1428 
1429  if (ExtKind == SignExtended) {
1430  for (Use &U : NarrowUse->uses()) {
1431  SExtInst *User = dyn_cast<SExtInst>(U.getUser());
1432  if (!User || User->getType() != WideType)
1433  return false;
1434  }
1435  } else { // ExtKind == ZeroExtended
1436  for (Use &U : NarrowUse->uses()) {
1437  ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
1438  if (!User || User->getType() != WideType)
1439  return false;
1440  }
1441  }
1442 
1443  return true;
1444 }
1445 
1446 /// Special Case for widening with variant Loads (see
1447 /// WidenIV::widenWithVariantLoadUse). This is the code generation part.
1448 void WidenIV::widenWithVariantLoadUseCodegen(NarrowIVDefUse DU) {
1449  Instruction *NarrowUse = DU.NarrowUse;
1450  Instruction *NarrowDef = DU.NarrowDef;
1451  Instruction *WideDef = DU.WideDef;
1452 
1453  ExtendKind ExtKind = getExtendKind(NarrowDef);
1454 
1455  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1456 
1457  // Generating a widening use instruction.
1458  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1459  ? WideDef
1460  : createExtendInst(NarrowUse->getOperand(0), WideType,
1461  ExtKind, NarrowUse);
1462  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1463  ? WideDef
1464  : createExtendInst(NarrowUse->getOperand(1), WideType,
1465  ExtKind, NarrowUse);
1466 
1467  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1468  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1469  NarrowBO->getName());
1470  IRBuilder<> Builder(NarrowUse);
1471  Builder.Insert(WideBO);
1472  WideBO->copyIRFlags(NarrowBO);
1473 
1474  if (ExtKind == SignExtended)
1475  ExtendKindMap[NarrowUse] = SignExtended;
1476  else
1477  ExtendKindMap[NarrowUse] = ZeroExtended;
1478 
1479  // Update the Use.
1480  if (ExtKind == SignExtended) {
1481  for (Use &U : NarrowUse->uses()) {
1482  SExtInst *User = dyn_cast<SExtInst>(U.getUser());
1483  if (User && User->getType() == WideType) {
1484  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1485  << *WideBO << "\n");
1486  ++NumElimExt;
1487  User->replaceAllUsesWith(WideBO);
1488  DeadInsts.emplace_back(User);
1489  }
1490  }
1491  } else { // ExtKind == ZeroExtended
1492  for (Use &U : NarrowUse->uses()) {
1493  ZExtInst *User = dyn_cast<ZExtInst>(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  }
1503 }
1504 
1505 /// Determine whether an individual user of the narrow IV can be widened. If so,
1506 /// return the wide clone of the user.
1507 Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
1508  assert(ExtendKindMap.count(DU.NarrowDef) &&
1509  "Should already know the kind of extension used to widen NarrowDef");
1510 
1511  // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1512  if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1513  if (LI->getLoopFor(UsePhi->getParent()) != L) {
1514  // For LCSSA phis, sink the truncate outside the loop.
1515  // After SimplifyCFG most loop exit targets have a single predecessor.
1516  // Otherwise fall back to a truncate within the loop.
1517  if (UsePhi->getNumOperands() != 1)
1518  truncateIVUse(DU, DT, LI);
1519  else {
1520  // Widening the PHI requires us to insert a trunc. The logical place
1521  // for this trunc is in the same BB as the PHI. This is not possible if
1522  // the BB is terminated by a catchswitch.
1523  if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1524  return nullptr;
1525 
1526  PHINode *WidePhi =
1527  PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1528  UsePhi);
1529  WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1530  IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
1531  Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1532  UsePhi->replaceAllUsesWith(Trunc);
1533  DeadInsts.emplace_back(UsePhi);
1534  LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1535  << *WidePhi << "\n");
1536  }
1537  return nullptr;
1538  }
1539  }
1540 
1541  // This narrow use can be widened by a sext if it's non-negative or its narrow
1542  // def was widended by a sext. Same for zext.
1543  auto canWidenBySExt = [&]() {
1544  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1545  };
1546  auto canWidenByZExt = [&]() {
1547  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1548  };
1549 
1550  // Our raison d'etre! Eliminate sign and zero extension.
1551  if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1552  (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1553  Value *NewDef = DU.WideDef;
1554  if (DU.NarrowUse->getType() != WideType) {
1555  unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1556  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1557  if (CastWidth < IVWidth) {
1558  // The cast isn't as wide as the IV, so insert a Trunc.
1559  IRBuilder<> Builder(DU.NarrowUse);
1560  NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1561  }
1562  else {
1563  // A wider extend was hidden behind a narrower one. This may induce
1564  // another round of IV widening in which the intermediate IV becomes
1565  // dead. It should be very rare.
1566  LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1567  << " not wide enough to subsume " << *DU.NarrowUse
1568  << "\n");
1569  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1570  NewDef = DU.NarrowUse;
1571  }
1572  }
1573  if (NewDef != DU.NarrowUse) {
1574  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1575  << " replaced by " << *DU.WideDef << "\n");
1576  ++NumElimExt;
1577  DU.NarrowUse->replaceAllUsesWith(NewDef);
1578  DeadInsts.emplace_back(DU.NarrowUse);
1579  }
1580  // Now that the extend is gone, we want to expose it's uses for potential
1581  // further simplification. We don't need to directly inform SimplifyIVUsers
1582  // of the new users, because their parent IV will be processed later as a
1583  // new loop phi. If we preserved IVUsers analysis, we would also want to
1584  // push the uses of WideDef here.
1585 
1586  // No further widening is needed. The deceased [sz]ext had done it for us.
1587  return nullptr;
1588  }
1589 
1590  // Does this user itself evaluate to a recurrence after widening?
1591  WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1592  if (!WideAddRec.first)
1593  WideAddRec = getWideRecurrence(DU);
1594 
1595  assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
1596  if (!WideAddRec.first) {
1597  // If use is a loop condition, try to promote the condition instead of
1598  // truncating the IV first.
1599  if (widenLoopCompare(DU))
1600  return nullptr;
1601 
1602  // We are here about to generate a truncate instruction that may hurt
1603  // performance because the scalar evolution expression computed earlier
1604  // in WideAddRec.first does not indicate a polynomial induction expression.
1605  // In that case, look at the operands of the use instruction to determine
1606  // if we can still widen the use instead of truncating its operand.
1607  if (widenWithVariantLoadUse(DU)) {
1608  widenWithVariantLoadUseCodegen(DU);
1609  return nullptr;
1610  }
1611 
1612  // This user does not evaluate to a recurrence after widening, so don't
1613  // follow it. Instead insert a Trunc to kill off the original use,
1614  // eventually isolating the original narrow IV so it can be removed.
1615  truncateIVUse(DU, DT, LI);
1616  return nullptr;
1617  }
1618  // Assume block terminators cannot evaluate to a recurrence. We can't to
1619  // insert a Trunc after a terminator if there happens to be a critical edge.
1620  assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
1621  "SCEV is not expected to evaluate a block terminator");
1622 
1623  // Reuse the IV increment that SCEVExpander created as long as it dominates
1624  // NarrowUse.
1625  Instruction *WideUse = nullptr;
1626  if (WideAddRec.first == WideIncExpr &&
1627  Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1628  WideUse = WideInc;
1629  else {
1630  WideUse = cloneIVUser(DU, WideAddRec.first);
1631  if (!WideUse)
1632  return nullptr;
1633  }
1634  // Evaluation of WideAddRec ensured that the narrow expression could be
1635  // extended outside the loop without overflow. This suggests that the wide use
1636  // evaluates to the same expression as the extended narrow use, but doesn't
1637  // absolutely guarantee it. Hence the following failsafe check. In rare cases
1638  // where it fails, we simply throw away the newly created wide use.
1639  if (WideAddRec.first != SE->getSCEV(WideUse)) {
1640  LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1641  << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1642  << "\n");
1643  DeadInsts.emplace_back(WideUse);
1644  return nullptr;
1645  }
1646 
1647  ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1648  // Returning WideUse pushes it on the worklist.
1649  return WideUse;
1650 }
1651 
1652 /// Add eligible users of NarrowDef to NarrowIVUsers.
1653 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
1654  const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1655  bool NonNegativeDef =
1656  SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1657  SE->getConstant(NarrowSCEV->getType(), 0));
1658  for (User *U : NarrowDef->users()) {
1659  Instruction *NarrowUser = cast<Instruction>(U);
1660 
1661  // Handle data flow merges and bizarre phi cycles.
1662  if (!Widened.insert(NarrowUser).second)
1663  continue;
1664 
1665  bool NonNegativeUse = false;
1666  if (!NonNegativeDef) {
1667  // We might have a control-dependent range information for this context.
1668  if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1669  NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1670  }
1671 
1672  NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1673  NonNegativeDef || NonNegativeUse);
1674  }
1675 }
1676 
1677 /// Process a single induction variable. First use the SCEVExpander to create a
1678 /// wide induction variable that evaluates to the same recurrence as the
1679 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1680 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1681 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1682 ///
1683 /// It would be simpler to delete uses as they are processed, but we must avoid
1684 /// invalidating SCEV expressions.
1685 PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
1686  // Is this phi an induction variable?
1687  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1688  if (!AddRec)
1689  return nullptr;
1690 
1691  // Widen the induction variable expression.
1692  const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1693  ? SE->getSignExtendExpr(AddRec, WideType)
1694  : SE->getZeroExtendExpr(AddRec, WideType);
1695 
1696  assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1697  "Expect the new IV expression to preserve its type");
1698 
1699  // Can the IV be extended outside the loop without overflow?
1700  AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1701  if (!AddRec || AddRec->getLoop() != L)
1702  return nullptr;
1703 
1704  // An AddRec must have loop-invariant operands. Since this AddRec is
1705  // materialized by a loop header phi, the expression cannot have any post-loop
1706  // operands, so they must dominate the loop header.
1707  assert(
1708  SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1709  SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1710  "Loop header phi recurrence inputs do not dominate the loop");
1711 
1712  // Iterate over IV uses (including transitive ones) looking for IV increments
1713  // of the form 'add nsw %iv, <const>'. For each increment and each use of
1714  // the increment calculate control-dependent range information basing on
1715  // dominating conditions inside of the loop (e.g. a range check inside of the
1716  // loop). Calculated ranges are stored in PostIncRangeInfos map.
1717  //
1718  // Control-dependent range information is later used to prove that a narrow
1719  // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1720  // this on demand because when pushNarrowIVUsers needs this information some
1721  // of the dominating conditions might be already widened.
1722  if (UsePostIncrementRanges)
1723  calculatePostIncRanges(OrigPhi);
1724 
1725  // The rewriter provides a value for the desired IV expression. This may
1726  // either find an existing phi or materialize a new one. Either way, we
1727  // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1728  // of the phi-SCC dominates the loop entry.
1729  Instruction *InsertPt = &L->getHeader()->front();
1730  WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));
1731 
1732  // Remembering the WideIV increment generated by SCEVExpander allows
1733  // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1734  // employ a general reuse mechanism because the call above is the only call to
1735  // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1736  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1737  WideInc =
1738  cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1739  WideIncExpr = SE->getSCEV(WideInc);
1740  // Propagate the debug location associated with the original loop increment
1741  // to the new (widened) increment.
1742  auto *OrigInc =
1743  cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1744  WideInc->setDebugLoc(OrigInc->getDebugLoc());
1745  }
1746 
1747  LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1748  ++NumWidened;
1749 
1750  // Traverse the def-use chain using a worklist starting at the original IV.
1751  assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1752 
1753  Widened.insert(OrigPhi);
1754  pushNarrowIVUsers(OrigPhi, WidePhi);
1755 
1756  while (!NarrowIVUsers.empty()) {
1757  NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1758 
1759  // Process a def-use edge. This may replace the use, so don't hold a
1760  // use_iterator across it.
1761  Instruction *WideUse = widenIVUse(DU, Rewriter);
1762 
1763  // Follow all def-use edges from the previous narrow use.
1764  if (WideUse)
1765  pushNarrowIVUsers(DU.NarrowUse, WideUse);
1766 
1767  // widenIVUse may have removed the def-use edge.
1768  if (DU.NarrowDef->use_empty())
1769  DeadInsts.emplace_back(DU.NarrowDef);
1770  }
1771 
1772  // Attach any debug information to the new PHI. Since OrigPhi and WidePHI
1773  // evaluate the same recurrence, we can just copy the debug info over.
1775  llvm::findDbgValues(DbgValues, OrigPhi);
1776  auto *MDPhi = MetadataAsValue::get(WidePhi->getContext(),
1777  ValueAsMetadata::get(WidePhi));
1778  for (auto &DbgValue : DbgValues)
1779  DbgValue->setOperand(0, MDPhi);
1780  return WidePhi;
1781 }
1782 
1783 /// Calculates control-dependent range for the given def at the given context
1784 /// by looking at dominating conditions inside of the loop
1785 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1786  Instruction *NarrowUser) {
1787  using namespace llvm::PatternMatch;
1788 
1789  Value *NarrowDefLHS;
1790  const APInt *NarrowDefRHS;
1791  if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1792  m_APInt(NarrowDefRHS))) ||
1793  !NarrowDefRHS->isNonNegative())
1794  return;
1795 
1796  auto UpdateRangeFromCondition = [&] (Value *Condition,
1797  bool TrueDest) {
1798  CmpInst::Predicate Pred;
1799  Value *CmpRHS;
1800  if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
1801  m_Value(CmpRHS))))
1802  return;
1803 
1805  TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
1806 
1807  auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
1808  auto CmpConstrainedLHSRange =
1809  ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
1810  auto NarrowDefRange =
1811  CmpConstrainedLHSRange.addWithNoSignedWrap(*NarrowDefRHS);
1812 
1813  updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
1814  };
1815 
1816  auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
1817  if (!HasGuards)
1818  return;
1819 
1820  for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
1821  Ctx->getParent()->rend())) {
1822  Value *C = nullptr;
1823  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
1824  UpdateRangeFromCondition(C, /*TrueDest=*/true);
1825  }
1826  };
1827 
1828  UpdateRangeFromGuards(NarrowUser);
1829 
1830  BasicBlock *NarrowUserBB = NarrowUser->getParent();
1831  // If NarrowUserBB is statically unreachable asking dominator queries may
1832  // yield surprising results. (e.g. the block may not have a dom tree node)
1833  if (!DT->isReachableFromEntry(NarrowUserBB))
1834  return;
1835 
1836  for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
1837  L->contains(DTB->getBlock());
1838  DTB = DTB->getIDom()) {
1839  auto *BB = DTB->getBlock();
1840  auto *TI = BB->getTerminator();
1841  UpdateRangeFromGuards(TI);
1842 
1843  auto *BI = dyn_cast<BranchInst>(TI);
1844  if (!BI || !BI->isConditional())
1845  continue;
1846 
1847  auto *TrueSuccessor = BI->getSuccessor(0);
1848  auto *FalseSuccessor = BI->getSuccessor(1);
1849 
1850  auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
1851  return BBE.isSingleEdge() &&
1852  DT->dominates(BBE, NarrowUser->getParent());
1853  };
1854 
1855  if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
1856  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
1857 
1858  if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
1859  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
1860  }
1861 }
1862 
1863 /// Calculates PostIncRangeInfos map for the given IV
1864 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
1867  Worklist.push_back(OrigPhi);
1868  Visited.insert(OrigPhi);
1869 
1870  while (!Worklist.empty()) {
1871  Instruction *NarrowDef = Worklist.pop_back_val();
1872 
1873  for (Use &U : NarrowDef->uses()) {
1874  auto *NarrowUser = cast<Instruction>(U.getUser());
1875 
1876  // Don't go looking outside the current loop.
1877  auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
1878  if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
1879  continue;
1880 
1881  if (!Visited.insert(NarrowUser).second)
1882  continue;
1883 
1884  Worklist.push_back(NarrowUser);
1885 
1886  calculatePostIncRange(NarrowDef, NarrowUser);
1887  }
1888  }
1889 }
1890 
1891 //===----------------------------------------------------------------------===//
1892 // Live IV Reduction - Minimize IVs live across the loop.
1893 //===----------------------------------------------------------------------===//
1894 
1895 //===----------------------------------------------------------------------===//
1896 // Simplification of IV users based on SCEV evaluation.
1897 //===----------------------------------------------------------------------===//
1898 
1899 namespace {
1900 
1901 class IndVarSimplifyVisitor : public IVVisitor {
1902  ScalarEvolution *SE;
1903  const TargetTransformInfo *TTI;
1904  PHINode *IVPhi;
1905 
1906 public:
1907  WideIVInfo WI;
1908 
1909  IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,
1910  const TargetTransformInfo *TTI,
1911  const DominatorTree *DTree)
1912  : SE(SCEV), TTI(TTI), IVPhi(IV) {
1913  DT = DTree;
1914  WI.NarrowIV = IVPhi;
1915  }
1916 
1917  // Implement the interface used by simplifyUsersOfIV.
1918  void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
1919 };
1920 
1921 } // end anonymous namespace
1922 
1923 /// Iteratively perform simplification on a worklist of IV users. Each
1924 /// successive simplification may push more users which may themselves be
1925 /// candidates for simplification.
1926 ///
1927 /// Sign/Zero extend elimination is interleaved with IV simplification.
1928 bool IndVarSimplify::simplifyAndExtend(Loop *L,
1929  SCEVExpander &Rewriter,
1930  LoopInfo *LI) {
1932 
1933  auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction(
1934  Intrinsic::getName(Intrinsic::experimental_guard));
1935  bool HasGuards = GuardDecl && !GuardDecl->use_empty();
1936 
1937  SmallVector<PHINode*, 8> LoopPhis;
1938  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1939  LoopPhis.push_back(cast<PHINode>(I));
1940  }
1941  // Each round of simplification iterates through the SimplifyIVUsers worklist
1942  // for all current phis, then determines whether any IVs can be
1943  // widened. Widening adds new phis to LoopPhis, inducing another round of
1944  // simplification on the wide IVs.
1945  bool Changed = false;
1946  while (!LoopPhis.empty()) {
1947  // Evaluate as many IV expressions as possible before widening any IVs. This
1948  // forces SCEV to set no-wrap flags before evaluating sign/zero
1949  // extension. The first time SCEV attempts to normalize sign/zero extension,
1950  // the result becomes final. So for the most predictable results, we delay
1951  // evaluation of sign/zero extend evaluation until needed, and avoid running
1952  // other SCEV based analysis prior to simplifyAndExtend.
1953  do {
1954  PHINode *CurrIV = LoopPhis.pop_back_val();
1955 
1956  // Information about sign/zero extensions of CurrIV.
1957  IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
1958 
1959  Changed |=
1960  simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, Rewriter, &Visitor);
1961 
1962  if (Visitor.WI.WidestNativeType) {
1963  WideIVs.push_back(Visitor.WI);
1964  }
1965  } while(!LoopPhis.empty());
1966 
1967  for (; !WideIVs.empty(); WideIVs.pop_back()) {
1968  WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts, HasGuards);
1969  if (PHINode *WidePhi = Widener.createWideIV(Rewriter)) {
1970  Changed = true;
1971  LoopPhis.push_back(WidePhi);
1972  }
1973  }
1974  }
1975  return Changed;
1976 }
1977 
1978 //===----------------------------------------------------------------------===//
1979 // linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
1980 //===----------------------------------------------------------------------===//
1981 
1982 /// Return true if this loop's backedge taken count expression can be safely and
1983 /// cheaply expanded into an instruction sequence that can be used by
1984 /// linearFunctionTestReplace.
1986  SCEVExpander &Rewriter) {
1987  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1988  if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1989  return false;
1990 
1991  // Better to break the backedge
1992  if (BackedgeTakenCount->isZero())
1993  return false;
1994 
1995  // Loops with multiple exits are not currently suported by lftr
1996  if (!L->getExitingBlock())
1997  return false;
1998 
1999  // Can't rewrite non-branch yet.
2000  if (!isa<BranchInst>(L->getExitingBlock()->getTerminator()))
2001  return false;
2002 
2003  if (Rewriter.isHighCostExpansion(BackedgeTakenCount, L))
2004  return false;
2005 
2006  return true;
2007 }
2008 
2009 /// Given an Value which is hoped to be part of an add recurance in the given
2010 /// loop, return the associated Phi node if so. Otherwise, return null. Note
2011 /// that this is less general than SCEVs AddRec checking.
2013  Instruction *IncI = dyn_cast<Instruction>(IncV);
2014  if (!IncI)
2015  return nullptr;
2016 
2017  switch (IncI->getOpcode()) {
2018  case Instruction::Add:
2019  case Instruction::Sub:
2020  break;
2021  case Instruction::GetElementPtr:
2022  // An IV counter must preserve its type.
2023  if (IncI->getNumOperands() == 2)
2024  break;
2026  default:
2027  return nullptr;
2028  }
2029 
2030  PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));
2031  if (Phi && Phi->getParent() == L->getHeader()) {
2032  if (L->isLoopInvariant(IncI->getOperand(1)))
2033  return Phi;
2034  return nullptr;
2035  }
2036  if (IncI->getOpcode() == Instruction::GetElementPtr)
2037  return nullptr;
2038 
2039  // Allow add/sub to be commuted.
2040  Phi = dyn_cast<PHINode>(IncI->getOperand(1));
2041  if (Phi && Phi->getParent() == L->getHeader()) {
2042  if (L->isLoopInvariant(IncI->getOperand(0)))
2043  return Phi;
2044  }
2045  return nullptr;
2046 }
2047 
2048 /// Given a loop with one backedge and one exit, return the ICmpInst
2049 /// controlling the sole loop exit. There is no guarantee that the exiting
2050 /// block is also the latch.
2052  assert(L->getExitingBlock() && "expected loop exit");
2053 
2054  BasicBlock *LatchBlock = L->getLoopLatch();
2055  // Don't bother with LFTR if the loop is not properly simplified.
2056  if (!LatchBlock)
2057  return nullptr;
2058 
2060  assert(BI && "expected exit branch");
2061 
2062  return dyn_cast<ICmpInst>(BI->getCondition());
2063 }
2064 
2065 /// linearFunctionTestReplace policy. Return true unless we can show that the
2066 /// current exit test is already sufficiently canonical.
2067 static bool needsLFTR(Loop *L) {
2068  // Do LFTR to simplify the exit condition to an ICMP.
2069  ICmpInst *Cond = getLoopTest(L);
2070  if (!Cond)
2071  return true;
2072 
2073  // Do LFTR to simplify the exit ICMP to EQ/NE
2074  ICmpInst::Predicate Pred = Cond->getPredicate();
2075  if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
2076  return true;
2077 
2078  // Look for a loop invariant RHS
2079  Value *LHS = Cond->getOperand(0);
2080  Value *RHS = Cond->getOperand(1);
2081  if (!L->isLoopInvariant(RHS)) {
2082  if (!L->isLoopInvariant(LHS))
2083  return true;
2084  std::swap(LHS, RHS);
2085  }
2086  // Look for a simple IV counter LHS
2087  PHINode *Phi = dyn_cast<PHINode>(LHS);
2088  if (!Phi)
2089  Phi = getLoopPhiForCounter(LHS, L);
2090 
2091  if (!Phi)
2092  return true;
2093 
2094  // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
2095  int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
2096  if (Idx < 0)
2097  return true;
2098 
2099  // Do LFTR if the exit condition's IV is *not* a simple counter.
2100  Value *IncV = Phi->getIncomingValue(Idx);
2101  return Phi != getLoopPhiForCounter(IncV, L);
2102 }
2103 
2104 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
2105 /// down to checking that all operands are constant and listing instructions
2106 /// that may hide undef.
2108  unsigned Depth) {
2109  if (isa<Constant>(V))
2110  return !isa<UndefValue>(V);
2111 
2112  if (Depth >= 6)
2113  return false;
2114 
2115  // Conservatively handle non-constant non-instructions. For example, Arguments
2116  // may be undef.
2117  Instruction *I = dyn_cast<Instruction>(V);
2118  if (!I)
2119  return false;
2120 
2121  // Load and return values may be undef.
2122  if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))
2123  return false;
2124 
2125  // Optimistically handle other instructions.
2126  for (Value *Op : I->operands()) {
2127  if (!Visited.insert(Op).second)
2128  continue;
2129  if (!hasConcreteDefImpl(Op, Visited, Depth+1))
2130  return false;
2131  }
2132  return true;
2133 }
2134 
2135 /// Return true if the given value is concrete. We must prove that undef can
2136 /// never reach it.
2137 ///
2138 /// TODO: If we decide that this is a good approach to checking for undef, we
2139 /// may factor it into a common location.
2140 static bool hasConcreteDef(Value *V) {
2141  SmallPtrSet<Value*, 8> Visited;
2142  Visited.insert(V);
2143  return hasConcreteDefImpl(V, Visited, 0);
2144 }
2145 
2146 /// Return true if this IV has any uses other than the (soon to be rewritten)
2147 /// loop exit test.
2148 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) {
2149  int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
2150  Value *IncV = Phi->getIncomingValue(LatchIdx);
2151 
2152  for (User *U : Phi->users())
2153  if (U != Cond && U != IncV) return false;
2154 
2155  for (User *U : IncV->users())
2156  if (U != Cond && U != Phi) return false;
2157  return true;
2158 }
2159 
2160 /// Return true if the given phi is a "counter" in L. A counter is an
2161 /// add recurance (of integer or pointer type) with an arbitrary start, and a
2162 /// step of 1. Note that L must have exactly one latch.
2163 static bool isLoopCounter(PHINode* Phi, Loop *L,
2164  ScalarEvolution *SE) {
2165  assert(Phi->getParent() == L->getHeader());
2166  assert(L->getLoopLatch());
2167 
2168  if (!SE->isSCEVable(Phi->getType()))
2169  return false;
2170 
2171  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
2172  if (!AR || AR->getLoop() != L || !AR->isAffine())
2173  return false;
2174 
2175  const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
2176  if (!Step || !Step->isOne())
2177  return false;
2178 
2179  int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());
2180  Value *IncV = Phi->getIncomingValue(LatchIdx);
2181  return (getLoopPhiForCounter(IncV, L) == Phi);
2182 }
2183 
2184 /// Search the loop header for a loop counter (anadd rec w/step of one)
2185 /// suitable for use by LFTR. If multiple counters are available, select the
2186 /// "best" one based profitable heuristics.
2187 ///
2188 /// BECount may be an i8* pointer type. The pointer difference is already
2189 /// valid count without scaling the address stride, so it remains a pointer
2190 /// expression as far as SCEV is concerned.
2191 static PHINode *FindLoopCounter(Loop *L, const SCEV *BECount,
2192  ScalarEvolution *SE) {
2193  uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());
2194 
2195  Value *Cond =
2196  cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition();
2197 
2198  // Loop over all of the PHI nodes, looking for a simple counter.
2199  PHINode *BestPhi = nullptr;
2200  const SCEV *BestInit = nullptr;
2201  BasicBlock *LatchBlock = L->getLoopLatch();
2202  assert(LatchBlock && "needsLFTR should guarantee a loop latch");
2203  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2204 
2205  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
2206  PHINode *Phi = cast<PHINode>(I);
2207  if (!isLoopCounter(Phi, L, SE))
2208  continue;
2209 
2210  // Avoid comparing an integer IV against a pointer Limit.
2211  if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy())
2212  continue;
2213 
2214  const auto *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
2215 
2216  // AR may be a pointer type, while BECount is an integer type.
2217  // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
2218  // AR may not be a narrower type, or we may never exit.
2219  uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
2220  if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))
2221  continue;
2222 
2223  // Avoid reusing a potentially undef value to compute other values that may
2224  // have originally had a concrete definition.
2225  if (!hasConcreteDef(Phi)) {
2226  // We explicitly allow unknown phis as long as they are already used by
2227  // the loop test. In this case we assume that performing LFTR could not
2228  // increase the number of undef users.
2229  if (ICmpInst *Cond = getLoopTest(L)) {
2230  if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L) &&
2231  Phi != getLoopPhiForCounter(Cond->getOperand(1), L)) {
2232  continue;
2233  }
2234  }
2235  }
2236  const SCEV *Init = AR->getStart();
2237 
2238  if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
2239  // Don't force a live loop counter if another IV can be used.
2240  if (AlmostDeadIV(Phi, LatchBlock, Cond))
2241  continue;
2242 
2243  // Prefer to count-from-zero. This is a more "canonical" counter form. It
2244  // also prefers integer to pointer IVs.
2245  if (BestInit->isZero() != Init->isZero()) {
2246  if (BestInit->isZero())
2247  continue;
2248  }
2249  // If two IVs both count from zero or both count from nonzero then the
2250  // narrower is likely a dead phi that has been widened. Use the wider phi
2251  // to allow the other to be eliminated.
2252  else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))
2253  continue;
2254  }
2255  BestPhi = Phi;
2256  BestInit = Init;
2257  }
2258  return BestPhi;
2259 }
2260 
2261 /// Insert an IR expression which computes the value held by the IV IndVar
2262 /// (which must be an loop counter w/unit stride) after the backedge of loop L
2263 /// is taken IVCount times.
2264 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L,
2265  SCEVExpander &Rewriter, ScalarEvolution *SE) {
2266  assert(isLoopCounter(IndVar, L, SE));
2267  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2268  const SCEV *IVInit = AR->getStart();
2269 
2270  // IVInit may be a pointer while IVCount is an integer when FindLoopCounter
2271  // finds a valid pointer IV. Sign extend BECount in order to materialize a
2272  // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing
2273  // the existing GEPs whenever possible.
2274  if (IndVar->getType()->isPointerTy() && !IVCount->getType()->isPointerTy()) {
2275  // IVOffset will be the new GEP offset that is interpreted by GEP as a
2276  // signed value. IVCount on the other hand represents the loop trip count,
2277  // which is an unsigned value. FindLoopCounter only allows induction
2278  // variables that have a positive unit stride of one. This means we don't
2279  // have to handle the case of negative offsets (yet) and just need to zero
2280  // extend IVCount.
2281  Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType());
2282  const SCEV *IVOffset = SE->getTruncateOrZeroExtend(IVCount, OfsTy);
2283 
2284  // Expand the code for the iteration count.
2285  assert(SE->isLoopInvariant(IVOffset, L) &&
2286  "Computed iteration count is not loop invariant!");
2287  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2288  Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI);
2289 
2290  Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader());
2291  assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter");
2292  // We could handle pointer IVs other than i8*, but we need to compensate for
2293  // gep index scaling. See canExpandBackedgeTakenCount comments.
2295  cast<PointerType>(GEPBase->getType())
2296  ->getElementType())->isOne() &&
2297  "unit stride pointer IV must be i8*");
2298 
2299  IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
2300  return Builder.CreateGEP(GEPBase->getType()->getPointerElementType(),
2301  GEPBase, GEPOffset, "lftr.limit");
2302  } else {
2303  // In any other case, convert both IVInit and IVCount to integers before
2304  // comparing. This may result in SCEV expansion of pointers, but in practice
2305  // SCEV will fold the pointer arithmetic away as such:
2306  // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc).
2307  //
2308  // Valid Cases: (1) both integers is most common; (2) both may be pointers
2309  // for simple memset-style loops.
2310  //
2311  // IVInit integer and IVCount pointer would only occur if a canonical IV
2312  // were generated on top of case #2, which is not expected.
2313 
2314  assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");
2315  const SCEV *IVLimit = nullptr;
2316  // For unit stride, IVCount = Start + BECount with 2's complement overflow.
2317  // For non-zero Start, compute IVCount here.
2318  if (AR->getStart()->isZero())
2319  IVLimit = IVCount;
2320  else {
2321  const SCEV *IVInit = AR->getStart();
2322 
2323  // For integer IVs, truncate the IV before computing IVInit + BECount.
2324  if (SE->getTypeSizeInBits(IVInit->getType())
2325  > SE->getTypeSizeInBits(IVCount->getType()))
2326  IVInit = SE->getTruncateExpr(IVInit, IVCount->getType());
2327 
2328  IVLimit = SE->getAddExpr(IVInit, IVCount);
2329  }
2330  // Expand the code for the iteration count.
2331  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2332  IRBuilder<> Builder(BI);
2333  assert(SE->isLoopInvariant(IVLimit, L) &&
2334  "Computed iteration count is not loop invariant!");
2335  // Ensure that we generate the same type as IndVar, or a smaller integer
2336  // type. In the presence of null pointer values, we have an integer type
2337  // SCEV expression (IVInit) for a pointer type IV value (IndVar).
2338  Type *LimitTy = IVCount->getType()->isPointerTy() ?
2339  IndVar->getType() : IVCount->getType();
2340  return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
2341  }
2342 }
2343 
2344 /// This method rewrites the exit condition of the loop to be a canonical !=
2345 /// comparison against the incremented loop induction variable. This pass is
2346 /// able to rewrite the exit tests of any loop where the SCEV analysis can
2347 /// determine a loop-invariant trip count of the loop, which is actually a much
2348 /// broader range than just linear tests.
2349 bool IndVarSimplify::
2350 linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
2351  PHINode *IndVar, SCEVExpander &Rewriter) {
2352  assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition");
2353 
2354  // Initialize CmpIndVar and IVCount to their preincremented values.
2355  Value *CmpIndVar = IndVar;
2356  const SCEV *IVCount = BackedgeTakenCount;
2357 
2358  assert(L->getLoopLatch() && "Loop no longer in simplified form?");
2359 
2360  // If the exiting block is the same as the backedge block, we prefer to
2361  // compare against the post-incremented value, otherwise we must compare
2362  // against the preincremented value.
2363  if (L->getExitingBlock() == L->getLoopLatch()) {
2364  // Add one to the "backedge-taken" count to get the trip count.
2365  // This addition may overflow, which is valid as long as the comparison is
2366  // truncated to BackedgeTakenCount->getType().
2367  IVCount = SE->getAddExpr(BackedgeTakenCount,
2368  SE->getOne(BackedgeTakenCount->getType()));
2369  // The BackedgeTaken expression contains the number of times that the
2370  // backedge branches to the loop header. This is one less than the
2371  // number of times the loop executes, so use the incremented indvar.
2372  CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock());
2373  }
2374 
2375  Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
2376  assert(ExitCnt->getType()->isPointerTy() ==
2377  IndVar->getType()->isPointerTy() &&
2378  "genLoopLimit missed a cast");
2379 
2380  // Insert a new icmp_ne or icmp_eq instruction before the branch.
2381  BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2383  if (L->contains(BI->getSuccessor(0)))
2384  P = ICmpInst::ICMP_NE;
2385  else
2386  P = ICmpInst::ICMP_EQ;
2387 
2388  LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
2389  << " LHS:" << *CmpIndVar << '\n'
2390  << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")
2391  << "\n"
2392  << " RHS:\t" << *ExitCnt << "\n"
2393  << " IVCount:\t" << *IVCount << "\n");
2394 
2395  IRBuilder<> Builder(BI);
2396 
2397  // The new loop exit condition should reuse the debug location of the
2398  // original loop exit condition.
2399  if (auto *Cond = dyn_cast<Instruction>(BI->getCondition()))
2400  Builder.SetCurrentDebugLocation(Cond->getDebugLoc());
2401 
2402  // LFTR can ignore IV overflow and truncate to the width of
2403  // BECount. This avoids materializing the add(zext(add)) expression.
2404  unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());
2405  unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());
2406  if (CmpIndVarSize > ExitCntSize) {
2407  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2408  const SCEV *ARStart = AR->getStart();
2409  const SCEV *ARStep = AR->getStepRecurrence(*SE);
2410  // For constant IVCount, avoid truncation.
2411  if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) {
2412  const APInt &Start = cast<SCEVConstant>(ARStart)->getAPInt();
2413  APInt Count = cast<SCEVConstant>(IVCount)->getAPInt();
2414  // Note that the post-inc value of BackedgeTakenCount may have overflowed
2415  // above such that IVCount is now zero.
2416  if (IVCount != BackedgeTakenCount && Count == 0) {
2417  Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize);
2418  ++Count;
2419  }
2420  else
2421  Count = Count.zext(CmpIndVarSize);
2422  APInt NewLimit;
2423  if (cast<SCEVConstant>(ARStep)->getValue()->isNegative())
2424  NewLimit = Start - Count;
2425  else
2426  NewLimit = Start + Count;
2427  ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit);
2428 
2429  LLVM_DEBUG(dbgs() << " Widen RHS:\t" << *ExitCnt << "\n");
2430  } else {
2431  // We try to extend trip count first. If that doesn't work we truncate IV.
2432  // Zext(trunc(IV)) == IV implies equivalence of the following two:
2433  // Trunc(IV) == ExitCnt and IV == zext(ExitCnt). Similarly for sext. If
2434  // one of the two holds, extend the trip count, otherwise we truncate IV.
2435  bool Extended = false;
2436  const SCEV *IV = SE->getSCEV(CmpIndVar);
2437  const SCEV *ZExtTrunc =
2438  SE->getZeroExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2439  ExitCnt->getType()),
2440  CmpIndVar->getType());
2441 
2442  if (ZExtTrunc == IV) {
2443  Extended = true;
2444  ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),
2445  "wide.trip.count");
2446  } else {
2447  const SCEV *SExtTrunc =
2448  SE->getSignExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2449  ExitCnt->getType()),
2450  CmpIndVar->getType());
2451  if (SExtTrunc == IV) {
2452  Extended = true;
2453  ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->getType(),
2454  "wide.trip.count");
2455  }
2456  }
2457 
2458  if (!Extended)
2459  CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
2460  "lftr.wideiv");
2461  }
2462  }
2463  Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
2464  Value *OrigCond = BI->getCondition();
2465  // It's tempting to use replaceAllUsesWith here to fully replace the old
2466  // comparison, but that's not immediately safe, since users of the old
2467  // comparison may not be dominated by the new comparison. Instead, just
2468  // update the branch to use the new comparison; in the common case this
2469  // will make old comparison dead.
2470  BI->setCondition(Cond);
2471  DeadInsts.push_back(OrigCond);
2472 
2473  ++NumLFTR;
2474  return true;
2475 }
2476 
2477 //===----------------------------------------------------------------------===//
2478 // sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
2479 //===----------------------------------------------------------------------===//
2480 
2481 /// If there's a single exit block, sink any loop-invariant values that
2482 /// were defined in the preheader but not used inside the loop into the
2483 /// exit block to reduce register pressure in the loop.
2484 bool IndVarSimplify::sinkUnusedInvariants(Loop *L) {
2485  BasicBlock *ExitBlock = L->getExitBlock();
2486  if (!ExitBlock) return false;
2487 
2488  BasicBlock *Preheader = L->getLoopPreheader();
2489  if (!Preheader) return false;
2490 
2491  bool MadeAnyChanges = false;
2492  BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();
2493  BasicBlock::iterator I(Preheader->getTerminator());
2494  while (I != Preheader->begin()) {
2495  --I;
2496  // New instructions were inserted at the end of the preheader.
2497  if (isa<PHINode>(I))
2498  break;
2499 
2500  // Don't move instructions which might have side effects, since the side
2501  // effects need to complete before instructions inside the loop. Also don't
2502  // move instructions which might read memory, since the loop may modify
2503  // memory. Note that it's okay if the instruction might have undefined
2504  // behavior: LoopSimplify guarantees that the preheader dominates the exit
2505  // block.
2506  if (I->mayHaveSideEffects() || I->mayReadFromMemory())
2507  continue;
2508 
2509  // Skip debug info intrinsics.
2510  if (isa<DbgInfoIntrinsic>(I))
2511  continue;
2512 
2513  // Skip eh pad instructions.
2514  if (I->isEHPad())
2515  continue;
2516 
2517  // Don't sink alloca: we never want to sink static alloca's out of the
2518  // entry block, and correctly sinking dynamic alloca's requires
2519  // checks for stacksave/stackrestore intrinsics.
2520  // FIXME: Refactor this check somehow?
2521  if (isa<AllocaInst>(I))
2522  continue;
2523 
2524  // Determine if there is a use in or before the loop (direct or
2525  // otherwise).
2526  bool UsedInLoop = false;
2527  for (Use &U : I->uses()) {
2528  Instruction *User = cast<Instruction>(U.getUser());
2529  BasicBlock *UseBB = User->getParent();
2530  if (PHINode *P = dyn_cast<PHINode>(User)) {
2531  unsigned i =
2532  PHINode::getIncomingValueNumForOperand(U.getOperandNo());
2533  UseBB = P->getIncomingBlock(i);
2534  }
2535  if (UseBB == Preheader || L->contains(UseBB)) {
2536  UsedInLoop = true;
2537  break;
2538  }
2539  }
2540 
2541  // If there is, the def must remain in the preheader.
2542  if (UsedInLoop)
2543  continue;
2544 
2545  // Otherwise, sink it to the exit block.
2546  Instruction *ToMove = &*I;
2547  bool Done = false;
2548 
2549  if (I != Preheader->begin()) {
2550  // Skip debug info intrinsics.
2551  do {
2552  --I;
2553  } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
2554 
2555  if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
2556  Done = true;
2557  } else {
2558  Done = true;
2559  }
2560 
2561  MadeAnyChanges = true;
2562  ToMove->moveBefore(*ExitBlock, InsertPt);
2563  if (Done) break;
2564  InsertPt = ToMove->getIterator();
2565  }
2566 
2567  return MadeAnyChanges;
2568 }
2569 
2570 //===----------------------------------------------------------------------===//
2571 // IndVarSimplify driver. Manage several subpasses of IV simplification.
2572 //===----------------------------------------------------------------------===//
2573 
2574 bool IndVarSimplify::run(Loop *L) {
2575  // We need (and expect!) the incoming loop to be in LCSSA.
2576  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2577  "LCSSA required to run indvars!");
2578  bool Changed = false;
2579 
2580  // If LoopSimplify form is not available, stay out of trouble. Some notes:
2581  // - LSR currently only supports LoopSimplify-form loops. Indvars'
2582  // canonicalization can be a pessimization without LSR to "clean up"
2583  // afterwards.
2584  // - We depend on having a preheader; in particular,
2585  // Loop::getCanonicalInductionVariable only supports loops with preheaders,
2586  // and we're in trouble if we can't find the induction variable even when
2587  // we've manually inserted one.
2588  // - LFTR relies on having a single backedge.
2589  if (!L->isLoopSimplifyForm())
2590  return false;
2591 
2592  // If there are any floating-point recurrences, attempt to
2593  // transform them to use integer recurrences.
2594  Changed |= rewriteNonIntegerIVs(L);
2595 
2596  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
2597 
2598  // Create a rewriter object which we'll use to transform the code with.
2599  SCEVExpander Rewriter(*SE, DL, "indvars");
2600 #ifndef NDEBUG
2601  Rewriter.setDebugType(DEBUG_TYPE);
2602 #endif
2603 
2604  // Eliminate redundant IV users.
2605  //
2606  // Simplification works best when run before other consumers of SCEV. We
2607  // attempt to avoid evaluating SCEVs for sign/zero extend operations until
2608  // other expressions involving loop IVs have been evaluated. This helps SCEV
2609  // set no-wrap flags before normalizing sign/zero extension.
2610  Rewriter.disableCanonicalMode();
2611  Changed |= simplifyAndExtend(L, Rewriter, LI);
2612 
2613  // Check to see if this loop has a computable loop-invariant execution count.
2614  // If so, this means that we can compute the final value of any expressions
2615  // that are recurrent in the loop, and substitute the exit values from the
2616  // loop into any instructions outside of the loop that use the final values of
2617  // the current expressions.
2618  //
2619  if (ReplaceExitValue != NeverRepl &&
2620  !isa<SCEVCouldNotCompute>(BackedgeTakenCount))
2621  Changed |= rewriteLoopExitValues(L, Rewriter);
2622 
2623  // Eliminate redundant IV cycles.
2624  NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
2625 
2626  // If we have a trip count expression, rewrite the loop's exit condition
2627  // using it. We can currently only handle loops with a single exit.
2628  if (!DisableLFTR && canExpandBackedgeTakenCount(L, SE, Rewriter) &&
2629  needsLFTR(L)) {
2630  PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE);
2631  if (IndVar) {
2632  // Check preconditions for proper SCEVExpander operation. SCEV does not
2633  // express SCEVExpander's dependencies, such as LoopSimplify. Instead any
2634  // pass that uses the SCEVExpander must do it. This does not work well for
2635  // loop passes because SCEVExpander makes assumptions about all loops,
2636  // while LoopPassManager only forces the current loop to be simplified.
2637  //
2638  // FIXME: SCEV expansion has no way to bail out, so the caller must
2639  // explicitly check any assumptions made by SCEV. Brittle.
2640  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount);
2641  if (!AR || AR->getLoop()->getLoopPreheader())
2642  Changed |= linearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
2643  Rewriter);
2644  }
2645  }
2646  // Clear the rewriter cache, because values that are in the rewriter's cache
2647  // can be deleted in the loop below, causing the AssertingVH in the cache to
2648  // trigger.
2649  Rewriter.clear();
2650 
2651  // Now that we're done iterating through lists, clean up any instructions
2652  // which are now dead.
2653  while (!DeadInsts.empty())
2654  if (Instruction *Inst =
2655  dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
2656  Changed |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
2657 
2658  // The Rewriter may not be used from this point on.
2659 
2660  // Loop-invariant instructions in the preheader that aren't used in the
2661  // loop may be sunk below the loop to reduce register pressure.
2662  Changed |= sinkUnusedInvariants(L);
2663 
2664  // rewriteFirstIterationLoopExitValues does not rely on the computation of
2665  // trip count and therefore can further simplify exit values in addition to
2666  // rewriteLoopExitValues.
2667  Changed |= rewriteFirstIterationLoopExitValues(L);
2668 
2669  // Clean up dead instructions.
2670  Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
2671 
2672  // Check a post-condition.
2673  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2674  "Indvars did not preserve LCSSA!");
2675 
2676  // Verify that LFTR, and any other change have not interfered with SCEV's
2677  // ability to compute trip count.
2678 #ifndef NDEBUG
2679  if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
2680  SE->forgetLoop(L);
2681  const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
2682  if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
2683  SE->getTypeSizeInBits(NewBECount->getType()))
2684  NewBECount = SE->getTruncateOrNoop(NewBECount,
2685  BackedgeTakenCount->getType());
2686  else
2687  BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
2688  NewBECount->getType());
2689  assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV");
2690  }
2691 #endif
2692 
2693  return Changed;
2694 }
2695 
2698  LPMUpdater &) {
2699  Function *F = L.getHeader()->getParent();
2700  const DataLayout &DL = F->getParent()->getDataLayout();
2701 
2702  IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI);
2703  if (!IVS.run(&L))
2704  return PreservedAnalyses::all();
2705 
2706  auto PA = getLoopPassPreservedAnalyses();
2707  PA.preserveSet<CFGAnalyses>();
2708  return PA;
2709 }
2710 
2711 namespace {
2712 
2713 struct IndVarSimplifyLegacyPass : public LoopPass {
2714  static char ID; // Pass identification, replacement for typeid
2715 
2716  IndVarSimplifyLegacyPass() : LoopPass(ID) {
2718  }
2719 
2720  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
2721  if (skipLoop(L))
2722  return false;
2723 
2724  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2725  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2726  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2727  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
2728  auto *TLI = TLIP ? &TLIP->getTLI() : nullptr;
2729  auto *TTIP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
2730  auto *TTI = TTIP ? &TTIP->getTTI(*L->getHeader()->getParent()) : nullptr;
2731  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2732 
2733  IndVarSimplify IVS(LI, SE, DT, DL, TLI, TTI);
2734  return IVS.run(L);
2735  }
2736 
2737  void getAnalysisUsage(AnalysisUsage &AU) const override {
2738  AU.setPreservesCFG();
2740  }
2741 };
2742 
2743 } // end anonymous namespace
2744 
2746 
2747 INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars",
2748  "Induction Variable Simplification", false, false)
2750 INITIALIZE_PASS_END(IndVarSimplifyLegacyPass, "indvars",
2751  "Induction Variable Simplification", false, false)
2752 
2754  return new IndVarSimplifyLegacyPass();
2755 }
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
static PHINode * getLoopPhiForCounter(Value *IncV, Loop *L)
Given an Value which is hoped to be part of an add recurance in the given loop, return the associated...
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.
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:202
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:195
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
static PHINode * FindLoopCounter(Loop *L, const SCEV *BECount, ScalarEvolution *SE)
Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR...
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:715
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:725
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
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:65
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:720
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)
Insert an IR expression which computes the value held by the IV IndVar (which must be an loop counter...
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:879
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:629
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:808
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:697
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:416
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
static bool needsLFTR(Loop *L)
linearFunctionTestReplace policy.
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:716
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockT * getHeader() const
Definition: LoopInfo.h:100
Key
PAL metadata keys.
void findDbgValues(SmallVectorImpl< DbgValueInst *> &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: Local.cpp:1528
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:669
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.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
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.
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:432
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:318
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:652
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:572
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:709
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:434
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)
Given a loop with one backedge and one exit, return the ICmpInst controlling the sole loop exit...
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:724
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:59
signed greater than
Definition: InstrTypes.h:736
#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:713
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:110
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:723
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:738
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
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:819
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:739
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:627
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:784
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:211
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:465
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
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:717
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:332
static bool isLoopCounter(PHINode *Phi, Loop *L, ScalarEvolution *SE)
Return true if the given phi is a "counter" in L.
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:721
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:712
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:353
LLVM Value Representation.
Definition: Value.h:72
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:722
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:583
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:156
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:714
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:737
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