LLVM  14.0.0git
ScalarEvolutionExpander.cpp
Go to the documentation of this file.
1 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===//
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 file contains the implementation of the scalar evolution expander,
10 // which is used to generate the code corresponding to a given scalar evolution
11 // expression.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/IntrinsicInst.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/PatternMatch.h"
28 #include "llvm/Support/Debug.h"
31 
32 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
33 #define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)
34 #else
35 #define SCEV_DEBUG_WITH_TYPE(TYPE, X)
36 #endif
37 
38 using namespace llvm;
39 
41  "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
42  cl::desc("When performing SCEV expansion only if it is cheap to do, this "
43  "controls the budget that is considered cheap (default = 4)"));
44 
45 using namespace PatternMatch;
46 
47 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
48 /// reusing an existing cast if a suitable one (= dominating IP) exists, or
49 /// creating a new one.
50 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
53  // This function must be called with the builder having a valid insertion
54  // point. It doesn't need to be the actual IP where the uses of the returned
55  // cast will be added, but it must dominate such IP.
56  // We use this precondition to produce a cast that will dominate all its
57  // uses. In particular, this is crucial for the case where the builder's
58  // insertion point *is* the point where we were asked to put the cast.
59  // Since we don't know the builder's insertion point is actually
60  // where the uses will be added (only that it dominates it), we are
61  // not allowed to move it.
62  BasicBlock::iterator BIP = Builder.GetInsertPoint();
63 
64  Value *Ret = nullptr;
65 
66  // Check to see if there is already a cast!
67  for (User *U : V->users()) {
68  if (U->getType() != Ty)
69  continue;
70  CastInst *CI = dyn_cast<CastInst>(U);
71  if (!CI || CI->getOpcode() != Op)
72  continue;
73 
74  // Found a suitable cast that is at IP or comes before IP. Use it. Note that
75  // the cast must also properly dominate the Builder's insertion point.
76  if (IP->getParent() == CI->getParent() && &*BIP != CI &&
77  (&*IP == CI || CI->comesBefore(&*IP))) {
78  Ret = CI;
79  break;
80  }
81  }
82 
83  // Create a new cast.
84  if (!Ret) {
85  SCEVInsertPointGuard Guard(Builder, this);
86  Builder.SetInsertPoint(&*IP);
87  Ret = Builder.CreateCast(Op, V, Ty, V->getName());
88  }
89 
90  // We assert at the end of the function since IP might point to an
91  // instruction with different dominance properties than a cast
92  // (an invoke for example) and not dominate BIP (but the cast does).
93  assert(!isa<Instruction>(Ret) ||
94  SE.DT.dominates(cast<Instruction>(Ret), &*BIP));
95 
96  return Ret;
97 }
98 
101  Instruction *MustDominate) const {
102  BasicBlock::iterator IP = ++I->getIterator();
103  if (auto *II = dyn_cast<InvokeInst>(I))
104  IP = II->getNormalDest()->begin();
105 
106  while (isa<PHINode>(IP))
107  ++IP;
108 
109  if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
110  ++IP;
111  } else if (isa<CatchSwitchInst>(IP)) {
112  IP = MustDominate->getParent()->getFirstInsertionPt();
113  } else {
114  assert(!IP->isEHPad() && "unexpected eh pad!");
115  }
116 
117  // Adjust insert point to be after instructions inserted by the expander, so
118  // we can re-use already inserted instructions. Avoid skipping past the
119  // original \p MustDominate, in case it is an inserted instruction.
120  while (isInsertedInstruction(&*IP) && &*IP != MustDominate)
121  ++IP;
122 
123  return IP;
124 }
125 
127 SCEVExpander::GetOptimalInsertionPointForCastOf(Value *V) const {
128  // Cast the argument at the beginning of the entry block, after
129  // any bitcasts of other arguments.
130  if (Argument *A = dyn_cast<Argument>(V)) {
131  BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
132  while ((isa<BitCastInst>(IP) &&
133  isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
134  cast<BitCastInst>(IP)->getOperand(0) != A) ||
135  isa<DbgInfoIntrinsic>(IP))
136  ++IP;
137  return IP;
138  }
139 
140  // Cast the instruction immediately after the instruction.
141  if (Instruction *I = dyn_cast<Instruction>(V))
142  return findInsertPointAfter(I, &*Builder.GetInsertPoint());
143 
144  // Otherwise, this must be some kind of a constant,
145  // so let's plop this cast into the function's entry block.
146  assert(isa<Constant>(V) &&
147  "Expected the cast argument to be a global/constant");
148  return Builder.GetInsertBlock()
149  ->getParent()
150  ->getEntryBlock()
151  .getFirstInsertionPt();
152 }
153 
154 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
155 /// which must be possible with a noop cast, doing what we can to share
156 /// the casts.
157 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
158  Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
159  assert((Op == Instruction::BitCast ||
160  Op == Instruction::PtrToInt ||
161  Op == Instruction::IntToPtr) &&
162  "InsertNoopCastOfTo cannot perform non-noop casts!");
163  assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
164  "InsertNoopCastOfTo cannot change sizes!");
165 
166  // inttoptr only works for integral pointers. For non-integral pointers, we
167  // can create a GEP on i8* null with the integral value as index. Note that
168  // it is safe to use GEP of null instead of inttoptr here, because only
169  // expressions already based on a GEP of null should be converted to pointers
170  // during expansion.
171  if (Op == Instruction::IntToPtr) {
172  auto *PtrTy = cast<PointerType>(Ty);
173  if (DL.isNonIntegralPointerType(PtrTy)) {
174  auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace());
175  assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&
176  "alloc size of i8 must by 1 byte for the GEP to be correct");
177  auto *GEP = Builder.CreateGEP(
178  Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep");
179  return Builder.CreateBitCast(GEP, Ty);
180  }
181  }
182  // Short-circuit unnecessary bitcasts.
183  if (Op == Instruction::BitCast) {
184  if (V->getType() == Ty)
185  return V;
186  if (CastInst *CI = dyn_cast<CastInst>(V)) {
187  if (CI->getOperand(0)->getType() == Ty)
188  return CI->getOperand(0);
189  }
190  }
191  // Short-circuit unnecessary inttoptr<->ptrtoint casts.
192  if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
193  SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
194  if (CastInst *CI = dyn_cast<CastInst>(V))
195  if ((CI->getOpcode() == Instruction::PtrToInt ||
196  CI->getOpcode() == Instruction::IntToPtr) &&
197  SE.getTypeSizeInBits(CI->getType()) ==
198  SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
199  return CI->getOperand(0);
200  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
201  if ((CE->getOpcode() == Instruction::PtrToInt ||
202  CE->getOpcode() == Instruction::IntToPtr) &&
203  SE.getTypeSizeInBits(CE->getType()) ==
204  SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
205  return CE->getOperand(0);
206  }
207 
208  // Fold a cast of a constant.
209  if (Constant *C = dyn_cast<Constant>(V))
210  return ConstantExpr::getCast(Op, C, Ty);
211 
212  // Try to reuse existing cast, or insert one.
213  return ReuseOrCreateCast(V, Ty, Op, GetOptimalInsertionPointForCastOf(V));
214 }
215 
216 /// InsertBinop - Insert the specified binary operator, doing a small amount
217 /// of work to avoid inserting an obviously redundant operation, and hoisting
218 /// to an outer loop when the opportunity is there and it is safe.
219 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
220  Value *LHS, Value *RHS,
221  SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {
222  // Fold a binop with constant operands.
223  if (Constant *CLHS = dyn_cast<Constant>(LHS))
224  if (Constant *CRHS = dyn_cast<Constant>(RHS))
225  return ConstantExpr::get(Opcode, CLHS, CRHS);
226 
227  // Do a quick scan to see if we have this binop nearby. If so, reuse it.
228  unsigned ScanLimit = 6;
229  BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
230  // Scanning starts from the last instruction before the insertion point.
231  BasicBlock::iterator IP = Builder.GetInsertPoint();
232  if (IP != BlockBegin) {
233  --IP;
234  for (; ScanLimit; --IP, --ScanLimit) {
235  // Don't count dbg.value against the ScanLimit, to avoid perturbing the
236  // generated code.
237  if (isa<DbgInfoIntrinsic>(IP))
238  ScanLimit++;
239 
240  auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {
241  // Ensure that no-wrap flags match.
242  if (isa<OverflowingBinaryOperator>(I)) {
243  if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))
244  return true;
245  if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))
246  return true;
247  }
248  // Conservatively, do not use any instruction which has any of exact
249  // flags installed.
250  if (isa<PossiblyExactOperator>(I) && I->isExact())
251  return true;
252  return false;
253  };
254  if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
255  IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))
256  return &*IP;
257  if (IP == BlockBegin) break;
258  }
259  }
260 
261  // Save the original insertion point so we can restore it when we're done.
262  DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
263  SCEVInsertPointGuard Guard(Builder, this);
264 
265  if (IsSafeToHoist) {
266  // Move the insertion point out of as many loops as we can.
267  while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
268  if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
269  BasicBlock *Preheader = L->getLoopPreheader();
270  if (!Preheader) break;
271 
272  // Ok, move up a level.
273  Builder.SetInsertPoint(Preheader->getTerminator());
274  }
275  }
276 
277  // If we haven't found this binop, insert it.
278  Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
279  BO->setDebugLoc(Loc);
280  if (Flags & SCEV::FlagNUW)
281  BO->setHasNoUnsignedWrap();
282  if (Flags & SCEV::FlagNSW)
283  BO->setHasNoSignedWrap();
284 
285  return BO;
286 }
287 
288 /// FactorOutConstant - Test if S is divisible by Factor, using signed
289 /// division. If so, update S with Factor divided out and return true.
290 /// S need not be evenly divisible if a reasonable remainder can be
291 /// computed.
292 static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
293  const SCEV *Factor, ScalarEvolution &SE,
294  const DataLayout &DL) {
295  // Everything is divisible by one.
296  if (Factor->isOne())
297  return true;
298 
299  // x/x == 1.
300  if (S == Factor) {
301  S = SE.getConstant(S->getType(), 1);
302  return true;
303  }
304 
305  // For a Constant, check for a multiple of the given factor.
306  if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
307  // 0/x == 0.
308  if (C->isZero())
309  return true;
310  // Check for divisibility.
311  if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
312  ConstantInt *CI =
313  ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
314  // If the quotient is zero and the remainder is non-zero, reject
315  // the value at this scale. It will be considered for subsequent
316  // smaller scales.
317  if (!CI->isZero()) {
318  const SCEV *Div = SE.getConstant(CI);
319  S = Div;
320  Remainder = SE.getAddExpr(
321  Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
322  return true;
323  }
324  }
325  }
326 
327  // In a Mul, check if there is a constant operand which is a multiple
328  // of the given factor.
329  if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
330  // Size is known, check if there is a constant operand which is a multiple
331  // of the given factor. If so, we can factor it.
332  if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor))
333  if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
334  if (!C->getAPInt().srem(FC->getAPInt())) {
335  SmallVector<const SCEV *, 4> NewMulOps(M->operands());
336  NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
337  S = SE.getMulExpr(NewMulOps);
338  return true;
339  }
340  }
341 
342  // In an AddRec, check if both start and step are divisible.
343  if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
344  const SCEV *Step = A->getStepRecurrence(SE);
345  const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
346  if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
347  return false;
348  if (!StepRem->isZero())
349  return false;
350  const SCEV *Start = A->getStart();
351  if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
352  return false;
353  S = SE.getAddRecExpr(Start, Step, A->getLoop(),
354  A->getNoWrapFlags(SCEV::FlagNW));
355  return true;
356  }
357 
358  return false;
359 }
360 
361 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
362 /// is the number of SCEVAddRecExprs present, which are kept at the end of
363 /// the list.
364 ///
366  Type *Ty,
367  ScalarEvolution &SE) {
368  unsigned NumAddRecs = 0;
369  for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
370  ++NumAddRecs;
371  // Group Ops into non-addrecs and addrecs.
372  SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
373  SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
374  // Let ScalarEvolution sort and simplify the non-addrecs list.
375  const SCEV *Sum = NoAddRecs.empty() ?
376  SE.getConstant(Ty, 0) :
377  SE.getAddExpr(NoAddRecs);
378  // If it returned an add, use the operands. Otherwise it simplified
379  // the sum into a single value, so just use that.
380  Ops.clear();
381  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
382  Ops.append(Add->op_begin(), Add->op_end());
383  else if (!Sum->isZero())
384  Ops.push_back(Sum);
385  // Then append the addrecs.
386  Ops.append(AddRecs.begin(), AddRecs.end());
387 }
388 
389 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values
390 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
391 /// This helps expose more opportunities for folding parts of the expressions
392 /// into GEP indices.
393 ///
395  Type *Ty,
396  ScalarEvolution &SE) {
397  // Find the addrecs.
399  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
400  while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
401  const SCEV *Start = A->getStart();
402  if (Start->isZero()) break;
403  const SCEV *Zero = SE.getConstant(Ty, 0);
404  AddRecs.push_back(SE.getAddRecExpr(Zero,
405  A->getStepRecurrence(SE),
406  A->getLoop(),
407  A->getNoWrapFlags(SCEV::FlagNW)));
408  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
409  Ops[i] = Zero;
410  Ops.append(Add->op_begin(), Add->op_end());
411  e += Add->getNumOperands();
412  } else {
413  Ops[i] = Start;
414  }
415  }
416  if (!AddRecs.empty()) {
417  // Add the addrecs onto the end of the list.
418  Ops.append(AddRecs.begin(), AddRecs.end());
419  // Resort the operand list, moving any constants to the front.
420  SimplifyAddOperands(Ops, Ty, SE);
421  }
422 }
423 
424 /// expandAddToGEP - Expand an addition expression with a pointer type into
425 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
426 /// BasicAliasAnalysis and other passes analyze the result. See the rules
427 /// for getelementptr vs. inttoptr in
428 /// http://llvm.org/docs/LangRef.html#pointeraliasing
429 /// for details.
430 ///
431 /// Design note: The correctness of using getelementptr here depends on
432 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
433 /// they may introduce pointer arithmetic which may not be safely converted
434 /// into getelementptr.
435 ///
436 /// Design note: It might seem desirable for this function to be more
437 /// loop-aware. If some of the indices are loop-invariant while others
438 /// aren't, it might seem desirable to emit multiple GEPs, keeping the
439 /// loop-invariant portions of the overall computation outside the loop.
440 /// However, there are a few reasons this is not done here. Hoisting simple
441 /// arithmetic is a low-level optimization that often isn't very
442 /// important until late in the optimization process. In fact, passes
443 /// like InstructionCombining will combine GEPs, even if it means
444 /// pushing loop-invariant computation down into loops, so even if the
445 /// GEPs were split here, the work would quickly be undone. The
446 /// LoopStrengthReduction pass, which is usually run quite late (and
447 /// after the last InstructionCombining pass), takes care of hoisting
448 /// loop-invariant portions of expressions, after considering what
449 /// can be folded using target addressing modes.
450 ///
451 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
452  const SCEV *const *op_end,
453  PointerType *PTy,
454  Type *Ty,
455  Value *V) {
456  SmallVector<Value *, 4> GepIndices;
457  SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
458  bool AnyNonZeroIndices = false;
459 
460  // Split AddRecs up into parts as either of the parts may be usable
461  // without the other.
462  SplitAddRecs(Ops, Ty, SE);
463 
464  Type *IntIdxTy = DL.getIndexType(PTy);
465 
466  // For opaque pointers, always generate i8 GEP.
467  if (!PTy->isOpaque()) {
468  // Descend down the pointer's type and attempt to convert the other
469  // operands into GEP indices, at each level. The first index in a GEP
470  // indexes into the array implied by the pointer operand; the rest of
471  // the indices index into the element or field type selected by the
472  // preceding index.
473  Type *ElTy = PTy->getElementType();
474  for (;;) {
475  // If the scale size is not 0, attempt to factor out a scale for
476  // array indexing.
478  if (ElTy->isSized()) {
479  const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy);
480  if (!ElSize->isZero()) {
482  for (const SCEV *Op : Ops) {
483  const SCEV *Remainder = SE.getConstant(Ty, 0);
484  if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
485  // Op now has ElSize factored out.
486  ScaledOps.push_back(Op);
487  if (!Remainder->isZero())
488  NewOps.push_back(Remainder);
489  AnyNonZeroIndices = true;
490  } else {
491  // The operand was not divisible, so add it to the list of
492  // operands we'll scan next iteration.
493  NewOps.push_back(Op);
494  }
495  }
496  // If we made any changes, update Ops.
497  if (!ScaledOps.empty()) {
498  Ops = NewOps;
499  SimplifyAddOperands(Ops, Ty, SE);
500  }
501  }
502  }
503 
504  // Record the scaled array index for this level of the type. If
505  // we didn't find any operands that could be factored, tentatively
506  // assume that element zero was selected (since the zero offset
507  // would obviously be folded away).
508  Value *Scaled =
509  ScaledOps.empty()
511  : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false);
512  GepIndices.push_back(Scaled);
513 
514  // Collect struct field index operands.
515  while (StructType *STy = dyn_cast<StructType>(ElTy)) {
516  bool FoundFieldNo = false;
517  // An empty struct has no fields.
518  if (STy->getNumElements() == 0) break;
519  // Field offsets are known. See if a constant offset falls within any of
520  // the struct fields.
521  if (Ops.empty())
522  break;
523  if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
524  if (SE.getTypeSizeInBits(C->getType()) <= 64) {
525  const StructLayout &SL = *DL.getStructLayout(STy);
526  uint64_t FullOffset = C->getValue()->getZExtValue();
527  if (FullOffset < SL.getSizeInBytes()) {
528  unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
529  GepIndices.push_back(
531  ElTy = STy->getTypeAtIndex(ElIdx);
532  Ops[0] =
533  SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
534  AnyNonZeroIndices = true;
535  FoundFieldNo = true;
536  }
537  }
538  // If no struct field offsets were found, tentatively assume that
539  // field zero was selected (since the zero offset would obviously
540  // be folded away).
541  if (!FoundFieldNo) {
542  ElTy = STy->getTypeAtIndex(0u);
543  GepIndices.push_back(
545  }
546  }
547 
548  if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
549  ElTy = ATy->getElementType();
550  else
551  // FIXME: Handle VectorType.
552  // E.g., If ElTy is scalable vector, then ElSize is not a compile-time
553  // constant, therefore can not be factored out. The generated IR is less
554  // ideal with base 'V' cast to i8* and do ugly getelementptr over that.
555  break;
556  }
557  }
558 
559  // If none of the operands were convertible to proper GEP indices, cast
560  // the base to i8* and do an ugly getelementptr with that. It's still
561  // better than ptrtoint+arithmetic+inttoptr at least.
562  if (!AnyNonZeroIndices) {
563  // Cast the base to i8*.
564  if (!PTy->isOpaque())
565  V = InsertNoopCastOfTo(V,
567 
568  assert(!isa<Instruction>(V) ||
569  SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
570 
571  // Expand the operands for a plain byte offset.
572  Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false);
573 
574  // Fold a GEP with constant operands.
575  if (Constant *CLHS = dyn_cast<Constant>(V))
576  if (Constant *CRHS = dyn_cast<Constant>(Idx))
578  CLHS, CRHS);
579 
580  // Do a quick scan to see if we have this GEP nearby. If so, reuse it.
581  unsigned ScanLimit = 6;
582  BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
583  // Scanning starts from the last instruction before the insertion point.
584  BasicBlock::iterator IP = Builder.GetInsertPoint();
585  if (IP != BlockBegin) {
586  --IP;
587  for (; ScanLimit; --IP, --ScanLimit) {
588  // Don't count dbg.value against the ScanLimit, to avoid perturbing the
589  // generated code.
590  if (isa<DbgInfoIntrinsic>(IP))
591  ScanLimit++;
592  if (IP->getOpcode() == Instruction::GetElementPtr &&
593  IP->getOperand(0) == V && IP->getOperand(1) == Idx)
594  return &*IP;
595  if (IP == BlockBegin) break;
596  }
597  }
598 
599  // Save the original insertion point so we can restore it when we're done.
600  SCEVInsertPointGuard Guard(Builder, this);
601 
602  // Move the insertion point out of as many loops as we can.
603  while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
604  if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
605  BasicBlock *Preheader = L->getLoopPreheader();
606  if (!Preheader) break;
607 
608  // Ok, move up a level.
609  Builder.SetInsertPoint(Preheader->getTerminator());
610  }
611 
612  // Emit a GEP.
613  return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
614  }
615 
616  {
617  SCEVInsertPointGuard Guard(Builder, this);
618 
619  // Move the insertion point out of as many loops as we can.
620  while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
621  if (!L->isLoopInvariant(V)) break;
622 
623  bool AnyIndexNotLoopInvariant = any_of(
624  GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
625 
626  if (AnyIndexNotLoopInvariant)
627  break;
628 
629  BasicBlock *Preheader = L->getLoopPreheader();
630  if (!Preheader) break;
631 
632  // Ok, move up a level.
633  Builder.SetInsertPoint(Preheader->getTerminator());
634  }
635 
636  // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
637  // because ScalarEvolution may have changed the address arithmetic to
638  // compute a value which is beyond the end of the allocated object.
639  Value *Casted = V;
640  if (V->getType() != PTy)
641  Casted = InsertNoopCastOfTo(Casted, PTy);
642  Value *GEP = Builder.CreateGEP(PTy->getElementType(), Casted, GepIndices,
643  "scevgep");
644  Ops.push_back(SE.getUnknown(GEP));
645  }
646 
647  return expand(SE.getAddExpr(Ops));
648 }
649 
650 Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
651  Value *V) {
652  const SCEV *const Ops[1] = {Op};
653  return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
654 }
655 
656 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
657 /// SCEV expansion. If they are nested, this is the most nested. If they are
658 /// neighboring, pick the later.
659 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
660  DominatorTree &DT) {
661  if (!A) return B;
662  if (!B) return A;
663  if (A->contains(B)) return B;
664  if (B->contains(A)) return A;
665  if (DT.dominates(A->getHeader(), B->getHeader())) return B;
666  if (DT.dominates(B->getHeader(), A->getHeader())) return A;
667  return A; // Arbitrarily break the tie.
668 }
669 
670 /// getRelevantLoop - Get the most relevant loop associated with the given
671 /// expression, according to PickMostRelevantLoop.
672 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
673  // Test whether we've already computed the most relevant loop for this SCEV.
674  auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
675  if (!Pair.second)
676  return Pair.first->second;
677 
678  if (isa<SCEVConstant>(S))
679  // A constant has no relevant loops.
680  return nullptr;
681  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
682  if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
683  return Pair.first->second = SE.LI.getLoopFor(I->getParent());
684  // A non-instruction has no relevant loops.
685  return nullptr;
686  }
687  if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
688  const Loop *L = nullptr;
689  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
690  L = AR->getLoop();
691  for (const SCEV *Op : N->operands())
692  L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
693  return RelevantLoops[N] = L;
694  }
695  if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
696  const Loop *Result = getRelevantLoop(C->getOperand());
697  return RelevantLoops[C] = Result;
698  }
699  if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
701  getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
702  return RelevantLoops[D] = Result;
703  }
704  llvm_unreachable("Unexpected SCEV type!");
705 }
706 
707 namespace {
708 
709 /// LoopCompare - Compare loops by PickMostRelevantLoop.
710 class LoopCompare {
711  DominatorTree &DT;
712 public:
713  explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
714 
715  bool operator()(std::pair<const Loop *, const SCEV *> LHS,
716  std::pair<const Loop *, const SCEV *> RHS) const {
717  // Keep pointer operands sorted at the end.
718  if (LHS.second->getType()->isPointerTy() !=
719  RHS.second->getType()->isPointerTy())
720  return LHS.second->getType()->isPointerTy();
721 
722  // Compare loops with PickMostRelevantLoop.
723  if (LHS.first != RHS.first)
724  return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
725 
726  // If one operand is a non-constant negative and the other is not,
727  // put the non-constant negative on the right so that a sub can
728  // be used instead of a negate and add.
729  if (LHS.second->isNonConstantNegative()) {
730  if (!RHS.second->isNonConstantNegative())
731  return false;
732  } else if (RHS.second->isNonConstantNegative())
733  return true;
734 
735  // Otherwise they are equivalent according to this comparison.
736  return false;
737  }
738 };
739 
740 }
741 
742 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
743  Type *Ty = SE.getEffectiveSCEVType(S->getType());
744 
745  // Collect all the add operands in a loop, along with their associated loops.
746  // Iterate in reverse so that constants are emitted last, all else equal, and
747  // so that pointer operands are inserted first, which the code below relies on
748  // to form more involved GEPs.
750  for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
751  E(S->op_begin()); I != E; ++I)
752  OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
753 
754  // Sort by loop. Use a stable sort so that constants follow non-constants and
755  // pointer operands precede non-pointer operands.
756  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
757 
758  // Emit instructions to add all the operands. Hoist as much as possible
759  // out of loops, and form meaningful getelementptrs where possible.
760  Value *Sum = nullptr;
761  for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
762  const Loop *CurLoop = I->first;
763  const SCEV *Op = I->second;
764  if (!Sum) {
765  // This is the first operand. Just expand it.
766  Sum = expand(Op);
767  ++I;
768  } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
769  // The running sum expression is a pointer. Try to form a getelementptr
770  // at this level with that as the base.
772  for (; I != E && I->first == CurLoop; ++I) {
773  // If the operand is SCEVUnknown and not instructions, peek through
774  // it, to enable more of it to be folded into the GEP.
775  const SCEV *X = I->second;
776  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
777  if (!isa<Instruction>(U->getValue()))
778  X = SE.getSCEV(U->getValue());
779  NewOps.push_back(X);
780  }
781  Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
782  } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
783  // The running sum is an integer, and there's a pointer at this level.
784  // Try to form a getelementptr. If the running sum is instructions,
785  // use a SCEVUnknown to avoid re-analyzing them.
787  NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
788  SE.getSCEV(Sum));
789  for (++I; I != E && I->first == CurLoop; ++I)
790  NewOps.push_back(I->second);
791  Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
792  } else if (Op->isNonConstantNegative()) {
793  // Instead of doing a negate and add, just do a subtract.
794  Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false);
795  Sum = InsertNoopCastOfTo(Sum, Ty);
796  Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
797  /*IsSafeToHoist*/ true);
798  ++I;
799  } else {
800  // A simple add.
801  Value *W = expandCodeForImpl(Op, Ty, false);
802  Sum = InsertNoopCastOfTo(Sum, Ty);
803  // Canonicalize a constant to the RHS.
804  if (isa<Constant>(Sum)) std::swap(Sum, W);
805  Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
806  /*IsSafeToHoist*/ true);
807  ++I;
808  }
809  }
810 
811  return Sum;
812 }
813 
814 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
815  Type *Ty = SE.getEffectiveSCEVType(S->getType());
816 
817  // Collect all the mul operands in a loop, along with their associated loops.
818  // Iterate in reverse so that constants are emitted last, all else equal.
820  for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
821  E(S->op_begin()); I != E; ++I)
822  OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
823 
824  // Sort by loop. Use a stable sort so that constants follow non-constants.
825  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
826 
827  // Emit instructions to mul all the operands. Hoist as much as possible
828  // out of loops.
829  Value *Prod = nullptr;
830  auto I = OpsAndLoops.begin();
831 
832  // Expand the calculation of X pow N in the following manner:
833  // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
834  // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
835  const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
836  auto E = I;
837  // Calculate how many times the same operand from the same loop is included
838  // into this power.
839  uint64_t Exponent = 0;
840  const uint64_t MaxExponent = UINT64_MAX >> 1;
841  // No one sane will ever try to calculate such huge exponents, but if we
842  // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
843  // below when the power of 2 exceeds our Exponent, and we want it to be
844  // 1u << 31 at most to not deal with unsigned overflow.
845  while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
846  ++Exponent;
847  ++E;
848  }
849  assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
850 
851  // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
852  // that are needed into the result.
853  Value *P = expandCodeForImpl(I->second, Ty, false);
854  Value *Result = nullptr;
855  if (Exponent & 1)
856  Result = P;
857  for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
858  P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
859  /*IsSafeToHoist*/ true);
860  if (Exponent & BinExp)
861  Result = Result ? InsertBinop(Instruction::Mul, Result, P,
863  /*IsSafeToHoist*/ true)
864  : P;
865  }
866 
867  I = E;
868  assert(Result && "Nothing was expanded?");
869  return Result;
870  };
871 
872  while (I != OpsAndLoops.end()) {
873  if (!Prod) {
874  // This is the first operand. Just expand it.
875  Prod = ExpandOpBinPowN();
876  } else if (I->second->isAllOnesValue()) {
877  // Instead of doing a multiply by negative one, just do a negate.
878  Prod = InsertNoopCastOfTo(Prod, Ty);
879  Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
880  SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
881  ++I;
882  } else {
883  // A simple mul.
884  Value *W = ExpandOpBinPowN();
885  Prod = InsertNoopCastOfTo(Prod, Ty);
886  // Canonicalize a constant to the RHS.
887  if (isa<Constant>(Prod)) std::swap(Prod, W);
888  const APInt *RHS;
889  if (match(W, m_Power2(RHS))) {
890  // Canonicalize Prod*(1<<C) to Prod<<C.
891  assert(!Ty->isVectorTy() && "vector types are not SCEVable");
892  auto NWFlags = S->getNoWrapFlags();
893  // clear nsw flag if shl will produce poison value.
894  if (RHS->logBase2() == RHS->getBitWidth() - 1)
895  NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
896  Prod = InsertBinop(Instruction::Shl, Prod,
897  ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
898  /*IsSafeToHoist*/ true);
899  } else {
900  Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
901  /*IsSafeToHoist*/ true);
902  }
903  }
904  }
905 
906  return Prod;
907 }
908 
909 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
910  Type *Ty = SE.getEffectiveSCEVType(S->getType());
911 
912  Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false);
913  if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
914  const APInt &RHS = SC->getAPInt();
915  if (RHS.isPowerOf2())
916  return InsertBinop(Instruction::LShr, LHS,
917  ConstantInt::get(Ty, RHS.logBase2()),
918  SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
919  }
920 
921  Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false);
922  return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
923  /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
924 }
925 
926 /// Move parts of Base into Rest to leave Base with the minimal
927 /// expression that provides a pointer operand suitable for a
928 /// GEP expansion.
929 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
930  ScalarEvolution &SE) {
931  while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
932  Base = A->getStart();
933  Rest = SE.getAddExpr(Rest,
934  SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
935  A->getStepRecurrence(SE),
936  A->getLoop(),
937  A->getNoWrapFlags(SCEV::FlagNW)));
938  }
939  if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
940  Base = A->getOperand(A->getNumOperands()-1);
941  SmallVector<const SCEV *, 8> NewAddOps(A->operands());
942  NewAddOps.back() = Rest;
943  Rest = SE.getAddExpr(NewAddOps);
944  ExposePointerBase(Base, Rest, SE);
945  }
946 }
947 
948 /// Determine if this is a well-behaved chain of instructions leading back to
949 /// the PHI. If so, it may be reused by expanded expressions.
950 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
951  const Loop *L) {
952  if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
953  (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
954  return false;
955  // If any of the operands don't dominate the insert position, bail.
956  // Addrec operands are always loop-invariant, so this can only happen
957  // if there are instructions which haven't been hoisted.
958  if (L == IVIncInsertLoop) {
959  for (Use &Op : llvm::drop_begin(IncV->operands()))
960  if (Instruction *OInst = dyn_cast<Instruction>(Op))
961  if (!SE.DT.dominates(OInst, IVIncInsertPos))
962  return false;
963  }
964  // Advance to the next instruction.
965  IncV = dyn_cast<Instruction>(IncV->getOperand(0));
966  if (!IncV)
967  return false;
968 
969  if (IncV->mayHaveSideEffects())
970  return false;
971 
972  if (IncV == PN)
973  return true;
974 
975  return isNormalAddRecExprPHI(PN, IncV, L);
976 }
977 
978 /// getIVIncOperand returns an induction variable increment's induction
979 /// variable operand.
980 ///
981 /// If allowScale is set, any type of GEP is allowed as long as the nonIV
982 /// operands dominate InsertPos.
983 ///
984 /// If allowScale is not set, ensure that a GEP increment conforms to one of the
985 /// simple patterns generated by getAddRecExprPHILiterally and
986 /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
988  Instruction *InsertPos,
989  bool allowScale) {
990  if (IncV == InsertPos)
991  return nullptr;
992 
993  switch (IncV->getOpcode()) {
994  default:
995  return nullptr;
996  // Check for a simple Add/Sub or GEP of a loop invariant step.
997  case Instruction::Add:
998  case Instruction::Sub: {
999  Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
1000  if (!OInst || SE.DT.dominates(OInst, InsertPos))
1001  return dyn_cast<Instruction>(IncV->getOperand(0));
1002  return nullptr;
1003  }
1004  case Instruction::BitCast:
1005  return dyn_cast<Instruction>(IncV->getOperand(0));
1006  case Instruction::GetElementPtr:
1007  for (Use &U : llvm::drop_begin(IncV->operands())) {
1008  if (isa<Constant>(U))
1009  continue;
1010  if (Instruction *OInst = dyn_cast<Instruction>(U)) {
1011  if (!SE.DT.dominates(OInst, InsertPos))
1012  return nullptr;
1013  }
1014  if (allowScale) {
1015  // allow any kind of GEP as long as it can be hoisted.
1016  continue;
1017  }
1018  // This must be a pointer addition of constants (pretty), which is already
1019  // handled, or some number of address-size elements (ugly). Ugly geps
1020  // have 2 operands. i1* is used by the expander to represent an
1021  // address-size element.
1022  if (IncV->getNumOperands() != 2)
1023  return nullptr;
1024  unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
1025  if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
1026  && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
1027  return nullptr;
1028  break;
1029  }
1030  return dyn_cast<Instruction>(IncV->getOperand(0));
1031  }
1032 }
1033 
1034 /// If the insert point of the current builder or any of the builders on the
1035 /// stack of saved builders has 'I' as its insert point, update it to point to
1036 /// the instruction after 'I'. This is intended to be used when the instruction
1037 /// 'I' is being moved. If this fixup is not done and 'I' is moved to a
1038 /// different block, the inconsistent insert point (with a mismatched
1039 /// Instruction and Block) can lead to an instruction being inserted in a block
1040 /// other than its parent.
1041 void SCEVExpander::fixupInsertPoints(Instruction *I) {
1042  BasicBlock::iterator It(*I);
1043  BasicBlock::iterator NewInsertPt = std::next(It);
1044  if (Builder.GetInsertPoint() == It)
1045  Builder.SetInsertPoint(&*NewInsertPt);
1046  for (auto *InsertPtGuard : InsertPointGuards)
1047  if (InsertPtGuard->GetInsertPoint() == It)
1048  InsertPtGuard->SetInsertPoint(NewInsertPt);
1049 }
1050 
1051 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1052 /// it available to other uses in this loop. Recursively hoist any operands,
1053 /// until we reach a value that dominates InsertPos.
1055  if (SE.DT.dominates(IncV, InsertPos))
1056  return true;
1057 
1058  // InsertPos must itself dominate IncV so that IncV's new position satisfies
1059  // its existing users.
1060  if (isa<PHINode>(InsertPos) ||
1061  !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1062  return false;
1063 
1064  if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1065  return false;
1066 
1067  // Check that the chain of IV operands leading back to Phi can be hoisted.
1069  for(;;) {
1070  Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1071  if (!Oper)
1072  return false;
1073  // IncV is safe to hoist.
1074  IVIncs.push_back(IncV);
1075  IncV = Oper;
1076  if (SE.DT.dominates(IncV, InsertPos))
1077  break;
1078  }
1079  for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
1080  fixupInsertPoints(*I);
1081  (*I)->moveBefore(InsertPos);
1082  }
1083  return true;
1084 }
1085 
1086 /// Determine if this cyclic phi is in a form that would have been generated by
1087 /// LSR. We don't care if the phi was actually expanded in this pass, as long
1088 /// as it is in a low-cost form, for example, no implied multiplication. This
1089 /// should match any patterns generated by getAddRecExprPHILiterally and
1090 /// expandAddtoGEP.
1091 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1092  const Loop *L) {
1093  for(Instruction *IVOper = IncV;
1094  (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1095  /*allowScale=*/false));) {
1096  if (IVOper == PN)
1097  return true;
1098  }
1099  return false;
1100 }
1101 
1102 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1103 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1104 /// need to materialize IV increments elsewhere to handle difficult situations.
1105 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1106  Type *ExpandTy, Type *IntTy,
1107  bool useSubtract) {
1108  Value *IncV;
1109  // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1110  if (ExpandTy->isPointerTy()) {
1111  PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1112  // If the step isn't constant, don't use an implicitly scaled GEP, because
1113  // that would require a multiply inside the loop.
1114  if (!isa<ConstantInt>(StepV))
1115  GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
1116  GEPPtrTy->getAddressSpace());
1117  IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1118  if (IncV->getType() != PN->getType())
1119  IncV = Builder.CreateBitCast(IncV, PN->getType());
1120  } else {
1121  IncV = useSubtract ?
1122  Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1123  Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1124  }
1125  return IncV;
1126 }
1127 
1128 /// Hoist the addrec instruction chain rooted in the loop phi above the
1129 /// position. This routine assumes that this is possible (has been checked).
1130 void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
1131  Instruction *Pos, PHINode *LoopPhi) {
1132  do {
1133  if (DT->dominates(InstToHoist, Pos))
1134  break;
1135  // Make sure the increment is where we want it. But don't move it
1136  // down past a potential existing post-inc user.
1137  fixupInsertPoints(InstToHoist);
1138  InstToHoist->moveBefore(Pos);
1139  Pos = InstToHoist;
1140  InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
1141  } while (InstToHoist != LoopPhi);
1142 }
1143 
1144 /// Check whether we can cheaply express the requested SCEV in terms of
1145 /// the available PHI SCEV by truncation and/or inversion of the step.
1147  const SCEVAddRecExpr *Phi,
1148  const SCEVAddRecExpr *Requested,
1149  bool &InvertStep) {
1150  // We can't transform to match a pointer PHI.
1151  if (Phi->getType()->isPointerTy())
1152  return false;
1153 
1154  Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1155  Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1156 
1157  if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1158  return false;
1159 
1160  // Try truncate it if necessary.
1161  Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1162  if (!Phi)
1163  return false;
1164 
1165  // Check whether truncation will help.
1166  if (Phi == Requested) {
1167  InvertStep = false;
1168  return true;
1169  }
1170 
1171  // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1172  if (SE.getMinusSCEV(Requested->getStart(), Requested) == Phi) {
1173  InvertStep = true;
1174  return true;
1175  }
1176 
1177  return false;
1178 }
1179 
1180 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1181  if (!isa<IntegerType>(AR->getType()))
1182  return false;
1183 
1184  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1185  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1186  const SCEV *Step = AR->getStepRecurrence(SE);
1187  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1188  SE.getSignExtendExpr(AR, WideTy));
1189  const SCEV *ExtendAfterOp =
1190  SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1191  return ExtendAfterOp == OpAfterExtend;
1192 }
1193 
1194 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1195  if (!isa<IntegerType>(AR->getType()))
1196  return false;
1197 
1198  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1199  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1200  const SCEV *Step = AR->getStepRecurrence(SE);
1201  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1202  SE.getZeroExtendExpr(AR, WideTy));
1203  const SCEV *ExtendAfterOp =
1204  SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1205  return ExtendAfterOp == OpAfterExtend;
1206 }
1207 
1208 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1209 /// the base addrec, which is the addrec without any non-loop-dominating
1210 /// values, and return the PHI.
1211 PHINode *
1212 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1213  const Loop *L,
1214  Type *ExpandTy,
1215  Type *IntTy,
1216  Type *&TruncTy,
1217  bool &InvertStep) {
1218  assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
1219 
1220  // Reuse a previously-inserted PHI, if present.
1221  BasicBlock *LatchBlock = L->getLoopLatch();
1222  if (LatchBlock) {
1223  PHINode *AddRecPhiMatch = nullptr;
1224  Instruction *IncV = nullptr;
1225  TruncTy = nullptr;
1226  InvertStep = false;
1227 
1228  // Only try partially matching scevs that need truncation and/or
1229  // step-inversion if we know this loop is outside the current loop.
1230  bool TryNonMatchingSCEV =
1231  IVIncInsertLoop &&
1232  SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1233 
1234  for (PHINode &PN : L->getHeader()->phis()) {
1235  if (!SE.isSCEVable(PN.getType()))
1236  continue;
1237 
1238  // We should not look for a incomplete PHI. Getting SCEV for a incomplete
1239  // PHI has no meaning at all.
1240  if (!PN.isComplete()) {
1242  DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");
1243  continue;
1244  }
1245 
1246  const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1247  if (!PhiSCEV)
1248  continue;
1249 
1250  bool IsMatchingSCEV = PhiSCEV == Normalized;
1251  // We only handle truncation and inversion of phi recurrences for the
1252  // expanded expression if the expanded expression's loop dominates the
1253  // loop we insert to. Check now, so we can bail out early.
1254  if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1255  continue;
1256 
1257  // TODO: this possibly can be reworked to avoid this cast at all.
1258  Instruction *TempIncV =
1259  dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1260  if (!TempIncV)
1261  continue;
1262 
1263  // Check whether we can reuse this PHI node.
1264  if (LSRMode) {
1265  if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1266  continue;
1267  if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
1268  continue;
1269  } else {
1270  if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1271  continue;
1272  }
1273 
1274  // Stop if we have found an exact match SCEV.
1275  if (IsMatchingSCEV) {
1276  IncV = TempIncV;
1277  TruncTy = nullptr;
1278  InvertStep = false;
1279  AddRecPhiMatch = &PN;
1280  break;
1281  }
1282 
1283  // Try whether the phi can be translated into the requested form
1284  // (truncated and/or offset by a constant).
1285  if ((!TruncTy || InvertStep) &&
1286  canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1287  // Record the phi node. But don't stop we might find an exact match
1288  // later.
1289  AddRecPhiMatch = &PN;
1290  IncV = TempIncV;
1291  TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1292  }
1293  }
1294 
1295  if (AddRecPhiMatch) {
1296  // Potentially, move the increment. We have made sure in
1297  // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
1298  if (L == IVIncInsertLoop)
1299  hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
1300 
1301  // Ok, the add recurrence looks usable.
1302  // Remember this PHI, even in post-inc mode.
1303  InsertedValues.insert(AddRecPhiMatch);
1304  // Remember the increment.
1305  rememberInstruction(IncV);
1306  // Those values were not actually inserted but re-used.
1307  ReusedValues.insert(AddRecPhiMatch);
1308  ReusedValues.insert(IncV);
1309  return AddRecPhiMatch;
1310  }
1311  }
1312 
1313  // Save the original insertion point so we can restore it when we're done.
1314  SCEVInsertPointGuard Guard(Builder, this);
1315 
1316  // Another AddRec may need to be recursively expanded below. For example, if
1317  // this AddRec is quadratic, the StepV may itself be an AddRec in this
1318  // loop. Remove this loop from the PostIncLoops set before expanding such
1319  // AddRecs. Otherwise, we cannot find a valid position for the step
1320  // (i.e. StepV can never dominate its loop header). Ideally, we could do
1321  // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1322  // so it's not worth implementing SmallPtrSet::swap.
1323  PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1324  PostIncLoops.clear();
1325 
1326  // Expand code for the start value into the loop preheader.
1327  assert(L->getLoopPreheader() &&
1328  "Can't expand add recurrences without a loop preheader!");
1329  Value *StartV =
1330  expandCodeForImpl(Normalized->getStart(), ExpandTy,
1331  L->getLoopPreheader()->getTerminator(), false);
1332 
1333  // StartV must have been be inserted into L's preheader to dominate the new
1334  // phi.
1335  assert(!isa<Instruction>(StartV) ||
1336  SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1337  L->getHeader()));
1338 
1339  // Expand code for the step value. Do this before creating the PHI so that PHI
1340  // reuse code doesn't see an incomplete PHI.
1341  const SCEV *Step = Normalized->getStepRecurrence(SE);
1342  // If the stride is negative, insert a sub instead of an add for the increment
1343  // (unless it's a constant, because subtracts of constants are canonicalized
1344  // to adds).
1345  bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1346  if (useSubtract)
1347  Step = SE.getNegativeSCEV(Step);
1348  // Expand the step somewhere that dominates the loop header.
1349  Value *StepV = expandCodeForImpl(
1350  Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1351 
1352  // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1353  // we actually do emit an addition. It does not apply if we emit a
1354  // subtraction.
1355  bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1356  bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1357 
1358  // Create the PHI.
1359  BasicBlock *Header = L->getHeader();
1360  Builder.SetInsertPoint(Header, Header->begin());
1361  pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1362  PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1363  Twine(IVName) + ".iv");
1364 
1365  // Create the step instructions and populate the PHI.
1366  for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1367  BasicBlock *Pred = *HPI;
1368 
1369  // Add a start value.
1370  if (!L->contains(Pred)) {
1371  PN->addIncoming(StartV, Pred);
1372  continue;
1373  }
1374 
1375  // Create a step value and add it to the PHI.
1376  // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1377  // instructions at IVIncInsertPos.
1378  Instruction *InsertPos = L == IVIncInsertLoop ?
1379  IVIncInsertPos : Pred->getTerminator();
1380  Builder.SetInsertPoint(InsertPos);
1381  Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1382 
1383  if (isa<OverflowingBinaryOperator>(IncV)) {
1384  if (IncrementIsNUW)
1385  cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1386  if (IncrementIsNSW)
1387  cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1388  }
1389  PN->addIncoming(IncV, Pred);
1390  }
1391 
1392  // After expanding subexpressions, restore the PostIncLoops set so the caller
1393  // can ensure that IVIncrement dominates the current uses.
1394  PostIncLoops = SavedPostIncLoops;
1395 
1396  // Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most
1397  // effective when we are able to use an IV inserted here, so record it.
1398  InsertedValues.insert(PN);
1399  InsertedIVs.push_back(PN);
1400  return PN;
1401 }
1402 
1403 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1404  Type *STy = S->getType();
1405  Type *IntTy = SE.getEffectiveSCEVType(STy);
1406  const Loop *L = S->getLoop();
1407 
1408  // Determine a normalized form of this expression, which is the expression
1409  // before any post-inc adjustment is made.
1410  const SCEVAddRecExpr *Normalized = S;
1411  if (PostIncLoops.count(L)) {
1413  Loops.insert(L);
1414  Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1415  }
1416 
1417  // Strip off any non-loop-dominating component from the addrec start.
1418  const SCEV *Start = Normalized->getStart();
1419  const SCEV *PostLoopOffset = nullptr;
1420  if (!SE.properlyDominates(Start, L->getHeader())) {
1421  PostLoopOffset = Start;
1422  Start = SE.getConstant(Normalized->getType(), 0);
1423  Normalized = cast<SCEVAddRecExpr>(
1424  SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1425  Normalized->getLoop(),
1426  Normalized->getNoWrapFlags(SCEV::FlagNW)));
1427  }
1428 
1429  // Strip off any non-loop-dominating component from the addrec step.
1430  const SCEV *Step = Normalized->getStepRecurrence(SE);
1431  const SCEV *PostLoopScale = nullptr;
1432  if (!SE.dominates(Step, L->getHeader())) {
1433  PostLoopScale = Step;
1434  Step = SE.getConstant(Normalized->getType(), 1);
1435  if (!Start->isZero()) {
1436  // The normalization below assumes that Start is constant zero, so if
1437  // it isn't re-associate Start to PostLoopOffset.
1438  assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
1439  PostLoopOffset = Start;
1440  Start = SE.getConstant(Normalized->getType(), 0);
1441  }
1442  Normalized =
1443  cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1444  Start, Step, Normalized->getLoop(),
1445  Normalized->getNoWrapFlags(SCEV::FlagNW)));
1446  }
1447 
1448  // Expand the core addrec. If we need post-loop scaling, force it to
1449  // expand to an integer type to avoid the need for additional casting.
1450  Type *ExpandTy = PostLoopScale ? IntTy : STy;
1451  // We can't use a pointer type for the addrec if the pointer type is
1452  // non-integral.
1453  Type *AddRecPHIExpandTy =
1454  DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1455 
1456  // In some cases, we decide to reuse an existing phi node but need to truncate
1457  // it and/or invert the step.
1458  Type *TruncTy = nullptr;
1459  bool InvertStep = false;
1460  PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1461  IntTy, TruncTy, InvertStep);
1462 
1463  // Accommodate post-inc mode, if necessary.
1464  Value *Result;
1465  if (!PostIncLoops.count(L))
1466  Result = PN;
1467  else {
1468  // In PostInc mode, use the post-incremented value.
1469  BasicBlock *LatchBlock = L->getLoopLatch();
1470  assert(LatchBlock && "PostInc mode requires a unique loop latch!");
1471  Result = PN->getIncomingValueForBlock(LatchBlock);
1472 
1473  // We might be introducing a new use of the post-inc IV that is not poison
1474  // safe, in which case we should drop poison generating flags. Only keep
1475  // those flags for which SCEV has proven that they always hold.
1476  if (isa<OverflowingBinaryOperator>(Result)) {
1477  auto *I = cast<Instruction>(Result);
1478  if (!S->hasNoUnsignedWrap())
1479  I->setHasNoUnsignedWrap(false);
1480  if (!S->hasNoSignedWrap())
1481  I->setHasNoSignedWrap(false);
1482  }
1483 
1484  // For an expansion to use the postinc form, the client must call
1485  // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1486  // or dominated by IVIncInsertPos.
1487  if (isa<Instruction>(Result) &&
1488  !SE.DT.dominates(cast<Instruction>(Result),
1489  &*Builder.GetInsertPoint())) {
1490  // The induction variable's postinc expansion does not dominate this use.
1491  // IVUsers tries to prevent this case, so it is rare. However, it can
1492  // happen when an IVUser outside the loop is not dominated by the latch
1493  // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1494  // all cases. Consider a phi outside whose operand is replaced during
1495  // expansion with the value of the postinc user. Without fundamentally
1496  // changing the way postinc users are tracked, the only remedy is
1497  // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1498  // but hopefully expandCodeFor handles that.
1499  bool useSubtract =
1500  !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1501  if (useSubtract)
1502  Step = SE.getNegativeSCEV(Step);
1503  Value *StepV;
1504  {
1505  // Expand the step somewhere that dominates the loop header.
1506  SCEVInsertPointGuard Guard(Builder, this);
1507  StepV = expandCodeForImpl(
1508  Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1509  }
1510  Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1511  }
1512  }
1513 
1514  // We have decided to reuse an induction variable of a dominating loop. Apply
1515  // truncation and/or inversion of the step.
1516  if (TruncTy) {
1517  Type *ResTy = Result->getType();
1518  // Normalize the result type.
1519  if (ResTy != SE.getEffectiveSCEVType(ResTy))
1520  Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1521  // Truncate the result.
1522  if (TruncTy != Result->getType())
1523  Result = Builder.CreateTrunc(Result, TruncTy);
1524 
1525  // Invert the result.
1526  if (InvertStep)
1527  Result = Builder.CreateSub(
1528  expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result);
1529  }
1530 
1531  // Re-apply any non-loop-dominating scale.
1532  if (PostLoopScale) {
1533  assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
1534  Result = InsertNoopCastOfTo(Result, IntTy);
1535  Result = Builder.CreateMul(Result,
1536  expandCodeForImpl(PostLoopScale, IntTy, false));
1537  }
1538 
1539  // Re-apply any non-loop-dominating offset.
1540  if (PostLoopOffset) {
1541  if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1542  if (Result->getType()->isIntegerTy()) {
1543  Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false);
1544  Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1545  } else {
1546  Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1547  }
1548  } else {
1549  Result = InsertNoopCastOfTo(Result, IntTy);
1550  Result = Builder.CreateAdd(
1551  Result, expandCodeForImpl(PostLoopOffset, IntTy, false));
1552  }
1553  }
1554 
1555  return Result;
1556 }
1557 
1558 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1559  // In canonical mode we compute the addrec as an expression of a canonical IV
1560  // using evaluateAtIteration and expand the resulting SCEV expression. This
1561  // way we avoid introducing new IVs to carry on the comutation of the addrec
1562  // throughout the loop.
1563  //
1564  // For nested addrecs evaluateAtIteration might need a canonical IV of a
1565  // type wider than the addrec itself. Emitting a canonical IV of the
1566  // proper type might produce non-legal types, for example expanding an i64
1567  // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
1568  // back to non-canonical mode for nested addrecs.
1569  if (!CanonicalMode || (S->getNumOperands() > 2))
1570  return expandAddRecExprLiterally(S);
1571 
1572  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1573  const Loop *L = S->getLoop();
1574 
1575  // First check for an existing canonical IV in a suitable type.
1576  PHINode *CanonicalIV = nullptr;
1577  if (PHINode *PN = L->getCanonicalInductionVariable())
1578  if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1579  CanonicalIV = PN;
1580 
1581  // Rewrite an AddRec in terms of the canonical induction variable, if
1582  // its type is more narrow.
1583  if (CanonicalIV &&
1584  SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&
1585  !S->getType()->isPointerTy()) {
1586  SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
1587  for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1588  NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
1589  Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1590  S->getNoWrapFlags(SCEV::FlagNW)));
1591  BasicBlock::iterator NewInsertPt =
1592  findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
1593  V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1594  &*NewInsertPt, false);
1595  return V;
1596  }
1597 
1598  // {X,+,F} --> X + {0,+,F}
1599  if (!S->getStart()->isZero()) {
1600  SmallVector<const SCEV *, 4> NewOps(S->operands());
1601  NewOps[0] = SE.getConstant(Ty, 0);
1602  const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1603  S->getNoWrapFlags(SCEV::FlagNW));
1604 
1605  // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
1606  // comments on expandAddToGEP for details.
1607  const SCEV *Base = S->getStart();
1608  // Dig into the expression to find the pointer base for a GEP.
1609  const SCEV *ExposedRest = Rest;
1610  ExposePointerBase(Base, ExposedRest, SE);
1611  // If we found a pointer, expand the AddRec with a GEP.
1612  if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
1613  // Make sure the Base isn't something exotic, such as a multiplied
1614  // or divided pointer value. In those cases, the result type isn't
1615  // actually a pointer type.
1616  if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
1617  Value *StartV = expand(Base);
1618  assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
1619  return expandAddToGEP(ExposedRest, PTy, Ty, StartV);
1620  }
1621  }
1622 
1623  // Just do a normal add. Pre-expand the operands to suppress folding.
1624  //
1625  // The LHS and RHS values are factored out of the expand call to make the
1626  // output independent of the argument evaluation order.
1627  const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1628  const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1629  return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1630  }
1631 
1632  // If we don't yet have a canonical IV, create one.
1633  if (!CanonicalIV) {
1634  // Create and insert the PHI node for the induction variable in the
1635  // specified loop.
1636  BasicBlock *Header = L->getHeader();
1637  pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1638  CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1639  &Header->front());
1640  rememberInstruction(CanonicalIV);
1641 
1642  SmallSet<BasicBlock *, 4> PredSeen;
1643  Constant *One = ConstantInt::get(Ty, 1);
1644  for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1645  BasicBlock *HP = *HPI;
1646  if (!PredSeen.insert(HP).second) {
1647  // There must be an incoming value for each predecessor, even the
1648  // duplicates!
1649  CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1650  continue;
1651  }
1652 
1653  if (L->contains(HP)) {
1654  // Insert a unit add instruction right before the terminator
1655  // corresponding to the back-edge.
1656  Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1657  "indvar.next",
1658  HP->getTerminator());
1659  Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1660  rememberInstruction(Add);
1661  CanonicalIV->addIncoming(Add, HP);
1662  } else {
1663  CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1664  }
1665  }
1666  }
1667 
1668  // {0,+,1} --> Insert a canonical induction variable into the loop!
1669  if (S->isAffine() && S->getOperand(1)->isOne()) {
1670  assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
1671  "IVs with types different from the canonical IV should "
1672  "already have been handled!");
1673  return CanonicalIV;
1674  }
1675 
1676  // {0,+,F} --> {0,+,1} * F
1677 
1678  // If this is a simple linear addrec, emit it now as a special case.
1679  if (S->isAffine()) // {0,+,F} --> i*F
1680  return
1681  expand(SE.getTruncateOrNoop(
1682  SE.getMulExpr(SE.getUnknown(CanonicalIV),
1683  SE.getNoopOrAnyExtend(S->getOperand(1),
1684  CanonicalIV->getType())),
1685  Ty));
1686 
1687  // If this is a chain of recurrences, turn it into a closed form, using the
1688  // folders, then expandCodeFor the closed form. This allows the folders to
1689  // simplify the expression without having to build a bunch of special code
1690  // into this folder.
1691  const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV.
1692 
1693  // Promote S up to the canonical IV type, if the cast is foldable.
1694  const SCEV *NewS = S;
1695  const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1696  if (isa<SCEVAddRecExpr>(Ext))
1697  NewS = Ext;
1698 
1699  const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1700  //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
1701 
1702  // Truncate the result down to the original type, if needed.
1703  const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1704  return expand(T);
1705 }
1706 
1707 Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) {
1708  Value *V =
1709  expandCodeForImpl(S->getOperand(), S->getOperand()->getType(), false);
1710  return ReuseOrCreateCast(V, S->getType(), CastInst::PtrToInt,
1711  GetOptimalInsertionPointForCastOf(V));
1712 }
1713 
1714 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1715  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1716  Value *V = expandCodeForImpl(
1717  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1718  false);
1719  return Builder.CreateTrunc(V, Ty);
1720 }
1721 
1722 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1723  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1724  Value *V = expandCodeForImpl(
1725  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1726  false);
1727  return Builder.CreateZExt(V, Ty);
1728 }
1729 
1730 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1731  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1732  Value *V = expandCodeForImpl(
1733  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1734  false);
1735  return Builder.CreateSExt(V, Ty);
1736 }
1737 
1738 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1739  Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1740  Type *Ty = LHS->getType();
1741  for (int i = S->getNumOperands()-2; i >= 0; --i) {
1742  // In the case of mixed integer and pointer types, do the
1743  // rest of the comparisons as integer.
1744  Type *OpTy = S->getOperand(i)->getType();
1745  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1746  Ty = SE.getEffectiveSCEVType(Ty);
1747  LHS = InsertNoopCastOfTo(LHS, Ty);
1748  }
1749  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1750  Value *Sel;
1751  if (Ty->isIntegerTy())
1752  Sel = Builder.CreateIntrinsic(Intrinsic::smax, {Ty}, {LHS, RHS},
1753  /*FMFSource=*/nullptr, "smax");
1754  else {
1755  Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
1756  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
1757  }
1758  LHS = Sel;
1759  }
1760  // In the case of mixed integer and pointer types, cast the
1761  // final result back to the pointer type.
1762  if (LHS->getType() != S->getType())
1763  LHS = InsertNoopCastOfTo(LHS, S->getType());
1764  return LHS;
1765 }
1766 
1767 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1768  Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1769  Type *Ty = LHS->getType();
1770  for (int i = S->getNumOperands()-2; i >= 0; --i) {
1771  // In the case of mixed integer and pointer types, do the
1772  // rest of the comparisons as integer.
1773  Type *OpTy = S->getOperand(i)->getType();
1774  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1775  Ty = SE.getEffectiveSCEVType(Ty);
1776  LHS = InsertNoopCastOfTo(LHS, Ty);
1777  }
1778  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1779  Value *Sel;
1780  if (Ty->isIntegerTy())
1781  Sel = Builder.CreateIntrinsic(Intrinsic::umax, {Ty}, {LHS, RHS},
1782  /*FMFSource=*/nullptr, "umax");
1783  else {
1784  Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
1785  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
1786  }
1787  LHS = Sel;
1788  }
1789  // In the case of mixed integer and pointer types, cast the
1790  // final result back to the pointer type.
1791  if (LHS->getType() != S->getType())
1792  LHS = InsertNoopCastOfTo(LHS, S->getType());
1793  return LHS;
1794 }
1795 
1796 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1797  Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1798  Type *Ty = LHS->getType();
1799  for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1800  // In the case of mixed integer and pointer types, do the
1801  // rest of the comparisons as integer.
1802  Type *OpTy = S->getOperand(i)->getType();
1803  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1804  Ty = SE.getEffectiveSCEVType(Ty);
1805  LHS = InsertNoopCastOfTo(LHS, Ty);
1806  }
1807  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1808  Value *Sel;
1809  if (Ty->isIntegerTy())
1810  Sel = Builder.CreateIntrinsic(Intrinsic::smin, {Ty}, {LHS, RHS},
1811  /*FMFSource=*/nullptr, "smin");
1812  else {
1813  Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
1814  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
1815  }
1816  LHS = Sel;
1817  }
1818  // In the case of mixed integer and pointer types, cast the
1819  // final result back to the pointer type.
1820  if (LHS->getType() != S->getType())
1821  LHS = InsertNoopCastOfTo(LHS, S->getType());
1822  return LHS;
1823 }
1824 
1825 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1826  Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1827  Type *Ty = LHS->getType();
1828  for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1829  // In the case of mixed integer and pointer types, do the
1830  // rest of the comparisons as integer.
1831  Type *OpTy = S->getOperand(i)->getType();
1832  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1833  Ty = SE.getEffectiveSCEVType(Ty);
1834  LHS = InsertNoopCastOfTo(LHS, Ty);
1835  }
1836  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1837  Value *Sel;
1838  if (Ty->isIntegerTy())
1839  Sel = Builder.CreateIntrinsic(Intrinsic::umin, {Ty}, {LHS, RHS},
1840  /*FMFSource=*/nullptr, "umin");
1841  else {
1842  Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
1843  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
1844  }
1845  LHS = Sel;
1846  }
1847  // In the case of mixed integer and pointer types, cast the
1848  // final result back to the pointer type.
1849  if (LHS->getType() != S->getType())
1850  LHS = InsertNoopCastOfTo(LHS, S->getType());
1851  return LHS;
1852 }
1853 
1854 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
1855  Instruction *IP, bool Root) {
1856  setInsertPoint(IP);
1857  Value *V = expandCodeForImpl(SH, Ty, Root);
1858  return V;
1859 }
1860 
1861 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
1862  // Expand the code for this SCEV.
1863  Value *V = expand(SH);
1864 
1865  if (PreserveLCSSA) {
1866  if (auto *Inst = dyn_cast<Instruction>(V)) {
1867  // Create a temporary instruction to at the current insertion point, so we
1868  // can hand it off to the helper to create LCSSA PHIs if required for the
1869  // new use.
1870  // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
1871  // would accept a insertion point and return an LCSSA phi for that
1872  // insertion point, so there is no need to insert & remove the temporary
1873  // instruction.
1874  Instruction *Tmp;
1875  if (Inst->getType()->isIntegerTy())
1876  Tmp =
1877  cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user"));
1878  else {
1879  assert(Inst->getType()->isPointerTy());
1880  Tmp = cast<Instruction>(Builder.CreatePtrToInt(
1881  Inst, Type::getInt32Ty(Inst->getContext()), "tmp.lcssa.user"));
1882  }
1883  V = fixupLCSSAFormFor(Tmp, 0);
1884 
1885  // Clean up temporary instruction.
1886  InsertedValues.erase(Tmp);
1887  InsertedPostIncValues.erase(Tmp);
1888  Tmp->eraseFromParent();
1889  }
1890  }
1891 
1892  InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V;
1893  if (Ty) {
1894  assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
1895  "non-trivial casts should be done with the SCEVs directly!");
1896  V = InsertNoopCastOfTo(V, Ty);
1897  }
1898  return V;
1899 }
1900 
1901 ScalarEvolution::ValueOffsetPair
1902 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1903  const Instruction *InsertPt) {
1904  auto *Set = SE.getSCEVValues(S);
1905  // If the expansion is not in CanonicalMode, and the SCEV contains any
1906  // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1907  if (CanonicalMode || !SE.containsAddRecurrence(S)) {
1908  // If S is scConstant, it may be worse to reuse an existing Value.
1909  if (S->getSCEVType() != scConstant && Set) {
1910  // Choose a Value from the set which dominates the insertPt.
1911  // insertPt should be inside the Value's parent loop so as not to break
1912  // the LCSSA form.
1913  for (auto const &VOPair : *Set) {
1914  Value *V = VOPair.first;
1915  ConstantInt *Offset = VOPair.second;
1916  Instruction *EntInst = nullptr;
1917  if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
1918  S->getType() == V->getType() &&
1919  EntInst->getFunction() == InsertPt->getFunction() &&
1920  SE.DT.dominates(EntInst, InsertPt) &&
1921  (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1922  SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1923  return {V, Offset};
1924  }
1925  }
1926  }
1927  return {nullptr, nullptr};
1928 }
1929 
1930 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1931 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1932 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1933 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1934 // the expansion will try to reuse Value from ExprValueMap, and only when it
1935 // fails, expand the SCEV literally.
1936 Value *SCEVExpander::expand(const SCEV *S) {
1937  // Compute an insertion point for this SCEV object. Hoist the instructions
1938  // as far out in the loop nest as possible.
1939  Instruction *InsertPt = &*Builder.GetInsertPoint();
1940 
1941  // We can move insertion point only if there is no div or rem operations
1942  // otherwise we are risky to move it over the check for zero denominator.
1943  auto SafeToHoist = [](const SCEV *S) {
1944  return !SCEVExprContains(S, [](const SCEV *S) {
1945  if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1946  if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1947  // Division by non-zero constants can be hoisted.
1948  return SC->getValue()->isZero();
1949  // All other divisions should not be moved as they may be
1950  // divisions by zero and should be kept within the
1951  // conditions of the surrounding loops that guard their
1952  // execution (see PR35406).
1953  return true;
1954  }
1955  return false;
1956  });
1957  };
1958  if (SafeToHoist(S)) {
1959  for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1960  L = L->getParentLoop()) {
1961  if (SE.isLoopInvariant(S, L)) {
1962  if (!L) break;
1963  if (BasicBlock *Preheader = L->getLoopPreheader())
1964  InsertPt = Preheader->getTerminator();
1965  else
1966  // LSR sets the insertion point for AddRec start/step values to the
1967  // block start to simplify value reuse, even though it's an invalid
1968  // position. SCEVExpander must correct for this in all cases.
1969  InsertPt = &*L->getHeader()->getFirstInsertionPt();
1970  } else {
1971  // If the SCEV is computable at this level, insert it into the header
1972  // after the PHIs (and after any other instructions that we've inserted
1973  // there) so that it is guaranteed to dominate any user inside the loop.
1974  if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1975  InsertPt = &*L->getHeader()->getFirstInsertionPt();
1976 
1977  while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1978  (isInsertedInstruction(InsertPt) ||
1979  isa<DbgInfoIntrinsic>(InsertPt))) {
1980  InsertPt = &*std::next(InsertPt->getIterator());
1981  }
1982  break;
1983  }
1984  }
1985  }
1986 
1987  // Check to see if we already expanded this here.
1988  auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1989  if (I != InsertedExpressions.end())
1990  return I->second;
1991 
1992  SCEVInsertPointGuard Guard(Builder, this);
1993  Builder.SetInsertPoint(InsertPt);
1994 
1995  // Expand the expression into instructions.
1996  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
1997  Value *V = VO.first;
1998 
1999  if (!V)
2000  V = visit(S);
2001  else if (VO.second) {
2002  if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
2003  Type *Ety = Vty->getPointerElementType();
2004  int64_t Offset = VO.second->getSExtValue();
2005  int64_t ESize = SE.getTypeSizeInBits(Ety);
2006  if ((Offset * 8) % ESize == 0) {
2007  ConstantInt *Idx =
2008  ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
2009  V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
2010  } else {
2011  ConstantInt *Idx =
2012  ConstantInt::getSigned(VO.second->getType(), -Offset);
2013  unsigned AS = Vty->getAddressSpace();
2014  V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
2015  V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
2016  "uglygep");
2017  V = Builder.CreateBitCast(V, Vty);
2018  }
2019  } else {
2020  V = Builder.CreateSub(V, VO.second);
2021  }
2022  }
2023  // Remember the expanded value for this SCEV at this location.
2024  //
2025  // This is independent of PostIncLoops. The mapped value simply materializes
2026  // the expression at this insertion point. If the mapped value happened to be
2027  // a postinc expansion, it could be reused by a non-postinc user, but only if
2028  // its insertion point was already at the head of the loop.
2029  InsertedExpressions[std::make_pair(S, InsertPt)] = V;
2030  return V;
2031 }
2032 
2033 void SCEVExpander::rememberInstruction(Value *I) {
2034  auto DoInsert = [this](Value *V) {
2035  if (!PostIncLoops.empty())
2036  InsertedPostIncValues.insert(V);
2037  else
2038  InsertedValues.insert(V);
2039  };
2040  DoInsert(I);
2041 
2042  if (!PreserveLCSSA)
2043  return;
2044 
2045  if (auto *Inst = dyn_cast<Instruction>(I)) {
2046  // A new instruction has been added, which might introduce new uses outside
2047  // a defining loop. Fix LCSSA from for each operand of the new instruction,
2048  // if required.
2049  for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
2050  OpIdx++)
2051  fixupLCSSAFormFor(Inst, OpIdx);
2052  }
2053 }
2054 
2055 /// replaceCongruentIVs - Check for congruent phis in this loop header and
2056 /// replace them with their most canonical representative. Return the number of
2057 /// phis eliminated.
2058 ///
2059 /// This does not depend on any SCEVExpander state but should be used in
2060 /// the same context that SCEVExpander is used.
2061 unsigned
2064  const TargetTransformInfo *TTI) {
2065  // Find integer phis in order of increasing width.
2067  for (PHINode &PN : L->getHeader()->phis())
2068  Phis.push_back(&PN);
2069 
2070  if (TTI)
2071  llvm::sort(Phis, [](Value *LHS, Value *RHS) {
2072  // Put pointers at the back and make sure pointer < pointer = false.
2073  if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
2074  return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
2075  return RHS->getType()->getPrimitiveSizeInBits().getFixedSize() <
2077  });
2078 
2079  unsigned NumElim = 0;
2081  // Process phis from wide to narrow. Map wide phis to their truncation
2082  // so narrow phis can reuse them.
2083  for (PHINode *Phi : Phis) {
2084  auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
2085  if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
2086  return V;
2087  if (!SE.isSCEVable(PN->getType()))
2088  return nullptr;
2089  auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
2090  if (!Const)
2091  return nullptr;
2092  return Const->getValue();
2093  };
2094 
2095  // Fold constant phis. They may be congruent to other constant phis and
2096  // would confuse the logic below that expects proper IVs.
2097  if (Value *V = SimplifyPHINode(Phi)) {
2098  if (V->getType() != Phi->getType())
2099  continue;
2100  Phi->replaceAllUsesWith(V);
2101  DeadInsts.emplace_back(Phi);
2102  ++NumElim;
2104  dbgs() << "INDVARS: Eliminated constant iv: " << *Phi
2105  << '\n');
2106  continue;
2107  }
2108 
2109  if (!SE.isSCEVable(Phi->getType()))
2110  continue;
2111 
2112  PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
2113  if (!OrigPhiRef) {
2114  OrigPhiRef = Phi;
2115  if (Phi->getType()->isIntegerTy() && TTI &&
2116  TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
2117  // This phi can be freely truncated to the narrowest phi type. Map the
2118  // truncated expression to it so it will be reused for narrow types.
2119  const SCEV *TruncExpr =
2120  SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
2121  ExprToIVMap[TruncExpr] = Phi;
2122  }
2123  continue;
2124  }
2125 
2126  // Replacing a pointer phi with an integer phi or vice-versa doesn't make
2127  // sense.
2128  if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
2129  continue;
2130 
2131  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2132  Instruction *OrigInc = dyn_cast<Instruction>(
2133  OrigPhiRef->getIncomingValueForBlock(LatchBlock));
2134  Instruction *IsomorphicInc =
2135  dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
2136 
2137  if (OrigInc && IsomorphicInc) {
2138  // If this phi has the same width but is more canonical, replace the
2139  // original with it. As part of the "more canonical" determination,
2140  // respect a prior decision to use an IV chain.
2141  if (OrigPhiRef->getType() == Phi->getType() &&
2142  !(ChainedPhis.count(Phi) ||
2143  isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
2144  (ChainedPhis.count(Phi) ||
2145  isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2146  std::swap(OrigPhiRef, Phi);
2147  std::swap(OrigInc, IsomorphicInc);
2148  }
2149  // Replacing the congruent phi is sufficient because acyclic
2150  // redundancy elimination, CSE/GVN, should handle the
2151  // rest. However, once SCEV proves that a phi is congruent,
2152  // it's often the head of an IV user cycle that is isomorphic
2153  // with the original phi. It's worth eagerly cleaning up the
2154  // common case of a single IV increment so that DeleteDeadPHIs
2155  // can remove cycles that had postinc uses.
2156  const SCEV *TruncExpr =
2157  SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2158  if (OrigInc != IsomorphicInc &&
2159  TruncExpr == SE.getSCEV(IsomorphicInc) &&
2160  SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2161  hoistIVInc(OrigInc, IsomorphicInc)) {
2163  DebugType, dbgs() << "INDVARS: Eliminated congruent iv.inc: "
2164  << *IsomorphicInc << '\n');
2165  Value *NewInc = OrigInc;
2166  if (OrigInc->getType() != IsomorphicInc->getType()) {
2167  Instruction *IP = nullptr;
2168  if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2169  IP = &*PN->getParent()->getFirstInsertionPt();
2170  else
2171  IP = OrigInc->getNextNode();
2172 
2174  Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2175  NewInc = Builder.CreateTruncOrBitCast(
2176  OrigInc, IsomorphicInc->getType(), IVName);
2177  }
2178  IsomorphicInc->replaceAllUsesWith(NewInc);
2179  DeadInsts.emplace_back(IsomorphicInc);
2180  }
2181  }
2182  }
2184  dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi
2185  << '\n');
2187  DebugType, dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n');
2188  ++NumElim;
2189  Value *NewIV = OrigPhiRef;
2190  if (OrigPhiRef->getType() != Phi->getType()) {
2192  Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2193  NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2194  }
2195  Phi->replaceAllUsesWith(NewIV);
2196  DeadInsts.emplace_back(Phi);
2197  }
2198  return NumElim;
2199 }
2200 
2203  Loop *L) {
2204  using namespace llvm::PatternMatch;
2205 
2206  SmallVector<BasicBlock *, 4> ExitingBlocks;
2207  L->getExitingBlocks(ExitingBlocks);
2208 
2209  // Look for suitable value in simple conditions at the loop exits.
2210  for (BasicBlock *BB : ExitingBlocks) {
2211  ICmpInst::Predicate Pred;
2212  Instruction *LHS, *RHS;
2213 
2214  if (!match(BB->getTerminator(),
2215  m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
2216  m_BasicBlock(), m_BasicBlock())))
2217  continue;
2218 
2219  if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2220  return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
2221 
2222  if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2223  return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
2224  }
2225 
2226  // Use expand's logic which is used for reusing a previous Value in
2227  // ExprValueMap.
2228  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
2229  if (VO.first)
2230  return VO;
2231 
2232  // There is potential to make this significantly smarter, but this simple
2233  // heuristic already gets some interesting cases.
2234 
2235  // Can not find suitable value.
2236  return None;
2237 }
2238 
2239 template<typename T> static InstructionCost costAndCollectOperands(
2240  const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
2242  SmallVectorImpl<SCEVOperand> &Worklist) {
2243 
2244  const T *S = cast<T>(WorkItem.S);
2245  InstructionCost Cost = 0;
2246  // Object to help map SCEV operands to expanded IR instructions.
2247  struct OperationIndices {
2248  OperationIndices(unsigned Opc, size_t min, size_t max) :
2249  Opcode(Opc), MinIdx(min), MaxIdx(max) { }
2250  unsigned Opcode;
2251  size_t MinIdx;
2252  size_t MaxIdx;
2253  };
2254 
2255  // Collect the operations of all the instructions that will be needed to
2256  // expand the SCEVExpr. This is so that when we come to cost the operands,
2257  // we know what the generated user(s) will be.
2259 
2260  auto CastCost = [&](unsigned Opcode) -> InstructionCost {
2261  Operations.emplace_back(Opcode, 0, 0);
2262  return TTI.getCastInstrCost(Opcode, S->getType(),
2263  S->getOperand(0)->getType(),
2265  };
2266 
2267  auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,
2268  unsigned MinIdx = 0,
2269  unsigned MaxIdx = 1) -> InstructionCost {
2270  Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2271  return NumRequired *
2272  TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2273  };
2274 
2275  auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx,
2276  unsigned MaxIdx) -> InstructionCost {
2277  Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2278  Type *OpType = S->getOperand(0)->getType();
2279  return NumRequired * TTI.getCmpSelInstrCost(
2280  Opcode, OpType, CmpInst::makeCmpResultType(OpType),
2282  };
2283 
2284  switch (S->getSCEVType()) {
2285  case scCouldNotCompute:
2286  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2287  case scUnknown:
2288  case scConstant:
2289  return 0;
2290  case scPtrToInt:
2291  Cost = CastCost(Instruction::PtrToInt);
2292  break;
2293  case scTruncate:
2294  Cost = CastCost(Instruction::Trunc);
2295  break;
2296  case scZeroExtend:
2297  Cost = CastCost(Instruction::ZExt);
2298  break;
2299  case scSignExtend:
2300  Cost = CastCost(Instruction::SExt);
2301  break;
2302  case scUDivExpr: {
2303  unsigned Opcode = Instruction::UDiv;
2304  if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
2305  if (SC->getAPInt().isPowerOf2())
2306  Opcode = Instruction::LShr;
2307  Cost = ArithCost(Opcode, 1);
2308  break;
2309  }
2310  case scAddExpr:
2311  Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2312  break;
2313  case scMulExpr:
2314  // TODO: this is a very pessimistic cost modelling for Mul,
2315  // because of Bin Pow algorithm actually used by the expander,
2316  // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
2317  Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
2318  break;
2319  case scSMaxExpr:
2320  case scUMaxExpr:
2321  case scSMinExpr:
2322  case scUMinExpr: {
2323  // FIXME: should this ask the cost for Intrinsic's?
2324  Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2325  Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2326  break;
2327  }
2328  case scAddRecExpr: {
2329  // In this polynominal, we may have some zero operands, and we shouldn't
2330  // really charge for those. So how many non-zero coeffients are there?
2331  int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
2332  return !Op->isZero();
2333  });
2334 
2335  assert(NumTerms >= 1 && "Polynominal should have at least one term.");
2336  assert(!(*std::prev(S->operands().end()))->isZero() &&
2337  "Last operand should not be zero");
2338 
2339  // Ignoring constant term (operand 0), how many of the coeffients are u> 1?
2340  int NumNonZeroDegreeNonOneTerms =
2341  llvm::count_if(S->operands(), [](const SCEV *Op) {
2342  auto *SConst = dyn_cast<SCEVConstant>(Op);
2343  return !SConst || SConst->getAPInt().ugt(1);
2344  });
2345 
2346  // Much like with normal add expr, the polynominal will require
2347  // one less addition than the number of it's terms.
2348  InstructionCost AddCost = ArithCost(Instruction::Add, NumTerms - 1,
2349  /*MinIdx*/ 1, /*MaxIdx*/ 1);
2350  // Here, *each* one of those will require a multiplication.
2351  InstructionCost MulCost =
2352  ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
2353  Cost = AddCost + MulCost;
2354 
2355  // What is the degree of this polynominal?
2356  int PolyDegree = S->getNumOperands() - 1;
2357  assert(PolyDegree >= 1 && "Should be at least affine.");
2358 
2359  // The final term will be:
2360  // Op_{PolyDegree} * x ^ {PolyDegree}
2361  // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations.
2362  // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for
2363  // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free.
2364  // FIXME: this is conservatively correct, but might be overly pessimistic.
2365  Cost += MulCost * (PolyDegree - 1);
2366  break;
2367  }
2368  }
2369 
2370  for (auto &CostOp : Operations) {
2371  for (auto SCEVOp : enumerate(S->operands())) {
2372  // Clamp the index to account for multiple IR operations being chained.
2373  size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2374  size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2375  Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2376  }
2377  }
2378  return Cost;
2379 }
2380 
2381 bool SCEVExpander::isHighCostExpansionHelper(
2382  const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
2383  InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI,
2384  SmallPtrSetImpl<const SCEV *> &Processed,
2385  SmallVectorImpl<SCEVOperand> &Worklist) {
2386  if (Cost > Budget)
2387  return true; // Already run out of budget, give up.
2388 
2389  const SCEV *S = WorkItem.S;
2390  // Was the cost of expansion of this expression already accounted for?
2391  if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)
2392  return false; // We have already accounted for this expression.
2393 
2394  // If we can find an existing value for this scev available at the point "At"
2395  // then consider the expression cheap.
2396  if (getRelatedExistingExpansion(S, &At, L))
2397  return false; // Consider the expression to be free.
2398 
2400  L->getHeader()->getParent()->hasMinSize()
2403 
2404  switch (S->getSCEVType()) {
2405  case scCouldNotCompute:
2406  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2407  case scUnknown:
2408  // Assume to be zero-cost.
2409  return false;
2410  case scConstant: {
2411  // Only evalulate the costs of constants when optimizing for size.
2413  return 0;
2414  const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
2415  Type *Ty = S->getType();
2416  Cost += TTI.getIntImmCostInst(
2417  WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
2418  return Cost > Budget;
2419  }
2420  case scTruncate:
2421  case scPtrToInt:
2422  case scZeroExtend:
2423  case scSignExtend: {
2424  Cost +=
2425  costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
2426  return false; // Will answer upon next entry into this function.
2427  }
2428  case scUDivExpr: {
2429  // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2430  // HowManyLessThans produced to compute a precise expression, rather than a
2431  // UDiv from the user's code. If we can't find a UDiv in the code with some
2432  // simple searching, we need to account for it's cost.
2433 
2434  // At the beginning of this function we already tried to find existing
2435  // value for plain 'S'. Now try to lookup 'S + 1' since it is common
2436  // pattern involving division. This is just a simple search heuristic.
2437  if (getRelatedExistingExpansion(
2438  SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
2439  return false; // Consider it to be free.
2440 
2441  Cost +=
2442  costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
2443  return false; // Will answer upon next entry into this function.
2444  }
2445  case scAddExpr:
2446  case scMulExpr:
2447  case scUMaxExpr:
2448  case scSMaxExpr:
2449  case scUMinExpr:
2450  case scSMinExpr: {
2451  assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2452  "Nary expr should have more than 1 operand.");
2453  // The simple nary expr will require one less op (or pair of ops)
2454  // than the number of it's terms.
2455  Cost +=
2456  costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
2457  return Cost > Budget;
2458  }
2459  case scAddRecExpr: {
2460  assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2461  "Polynomial should be at least linear");
2462  Cost += costAndCollectOperands<SCEVAddRecExpr>(
2463  WorkItem, TTI, CostKind, Worklist);
2464  return Cost > Budget;
2465  }
2466  }
2467  llvm_unreachable("Unknown SCEV kind!");
2468 }
2469 
2471  Instruction *IP) {
2472  assert(IP);
2473  switch (Pred->getKind()) {
2475  return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2477  return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
2478  case SCEVPredicate::P_Wrap: {
2479  auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2480  return expandWrapPredicate(AddRecPred, IP);
2481  }
2482  }
2483  llvm_unreachable("Unknown SCEV predicate type");
2484 }
2485 
2487  Instruction *IP) {
2488  Value *Expr0 =
2489  expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
2490  Value *Expr1 =
2491  expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
2492 
2493  Builder.SetInsertPoint(IP);
2494  auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
2495  return I;
2496 }
2497 
2499  Instruction *Loc, bool Signed) {
2500  assert(AR->isAffine() && "Cannot generate RT check for "
2501  "non-affine expression");
2502 
2503  SCEVUnionPredicate Pred;
2504  const SCEV *ExitCount =
2505  SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
2506 
2507  assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count");
2508 
2509  const SCEV *Step = AR->getStepRecurrence(SE);
2510  const SCEV *Start = AR->getStart();
2511 
2512  Type *ARTy = AR->getType();
2513  unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2514  unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2515 
2516  // The expression {Start,+,Step} has nusw/nssw if
2517  // Step < 0, Start - |Step| * Backedge <= Start
2518  // Step >= 0, Start + |Step| * Backedge > Start
2519  // and |Step| * Backedge doesn't unsigned overflow.
2520 
2521  IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2522  Builder.SetInsertPoint(Loc);
2523  Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false);
2524 
2525  IntegerType *Ty =
2526  IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2527  Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
2528 
2529  Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false);
2530  Value *NegStepValue =
2531  expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false);
2532  Value *StartValue = expandCodeForImpl(
2533  isa<PointerType>(ARExpandTy) ? Start
2534  : SE.getPtrToIntExpr(Start, ARExpandTy),
2535  ARExpandTy, Loc, false);
2536 
2537  ConstantInt *Zero =
2539 
2540  Builder.SetInsertPoint(Loc);
2541  // Compute |Step|
2542  Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2543  Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2544 
2545  // Get the backedge taken count and truncate or extended to the AR type.
2546  Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2547  auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2548  Intrinsic::umul_with_overflow, Ty);
2549 
2550  // Compute |Step| * Backedge
2551  CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2552  Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2553  Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2554 
2555  // Compute:
2556  // Start + |Step| * Backedge < Start
2557  // Start - |Step| * Backedge > Start
2558  Value *Add = nullptr, *Sub = nullptr;
2559  if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) {
2560  const SCEV *MulS = SE.getSCEV(MulV);
2561  const SCEV *NegMulS = SE.getNegativeSCEV(MulS);
2562  Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue),
2563  ARPtrTy);
2564  Sub = Builder.CreateBitCast(
2565  expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy);
2566  } else {
2567  Add = Builder.CreateAdd(StartValue, MulV);
2568  Sub = Builder.CreateSub(StartValue, MulV);
2569  }
2570 
2571  Value *EndCompareGT = Builder.CreateICmp(
2572  Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2573 
2574  Value *EndCompareLT = Builder.CreateICmp(
2575  Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
2576 
2577  // Select the answer based on the sign of Step.
2578  Value *EndCheck =
2579  Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2580 
2581  // If the backedge taken count type is larger than the AR type,
2582  // check that we don't drop any bits by truncating it. If we are
2583  // dropping bits, then we have overflow (unless the step is zero).
2584  if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2585  auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2586  auto *BackedgeCheck =
2587  Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2588  ConstantInt::get(Loc->getContext(), MaxVal));
2589  BackedgeCheck = Builder.CreateAnd(
2590  BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2591 
2592  EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2593  }
2594 
2595  return Builder.CreateOr(EndCheck, OfMul);
2596 }
2597 
2599  Instruction *IP) {
2600  const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2601  Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2602 
2603  // Add a check for NUSW
2605  NUSWCheck = generateOverflowCheck(A, IP, false);
2606 
2607  // Add a check for NSSW
2609  NSSWCheck = generateOverflowCheck(A, IP, true);
2610 
2611  if (NUSWCheck && NSSWCheck)
2612  return Builder.CreateOr(NUSWCheck, NSSWCheck);
2613 
2614  if (NUSWCheck)
2615  return NUSWCheck;
2616 
2617  if (NSSWCheck)
2618  return NSSWCheck;
2619 
2620  return ConstantInt::getFalse(IP->getContext());
2621 }
2622 
2624  Instruction *IP) {
2625  auto *BoolType = IntegerType::get(IP->getContext(), 1);
2626  Value *Check = ConstantInt::getNullValue(BoolType);
2627 
2628  // Loop over all checks in this set.
2629  for (auto Pred : Union->getPredicates()) {
2630  auto *NextCheck = expandCodeForPredicate(Pred, IP);
2631  Builder.SetInsertPoint(IP);
2632  Check = Builder.CreateOr(Check, NextCheck);
2633  }
2634 
2635  return Check;
2636 }
2637 
2638 Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) {
2639  assert(PreserveLCSSA);
2641 
2642  auto *OpV = User->getOperand(OpIdx);
2643  auto *OpI = dyn_cast<Instruction>(OpV);
2644  if (!OpI)
2645  return OpV;
2646 
2647  Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
2648  Loop *UseLoop = SE.LI.getLoopFor(User->getParent());
2649  if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
2650  return OpV;
2651 
2652  ToUpdate.push_back(OpI);
2653  SmallVector<PHINode *, 16> PHIsToRemove;
2654  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove);
2655  for (PHINode *PN : PHIsToRemove) {
2656  if (!PN->use_empty())
2657  continue;
2658  InsertedValues.erase(PN);
2659  InsertedPostIncValues.erase(PN);
2660  PN->eraseFromParent();
2661  }
2662 
2663  return User->getOperand(OpIdx);
2664 }
2665 
2666 namespace {
2667 // Search for a SCEV subexpression that is not safe to expand. Any expression
2668 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2669 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
2670 // instruction, but the important thing is that we prove the denominator is
2671 // nonzero before expansion.
2672 //
2673 // IVUsers already checks that IV-derived expressions are safe. So this check is
2674 // only needed when the expression includes some subexpression that is not IV
2675 // derived.
2676 //
2677 // Currently, we only allow division by a nonzero constant here. If this is
2678 // inadequate, we could easily allow division by SCEVUnknown by using
2679 // ValueTracking to check isKnownNonZero().
2680 //
2681 // We cannot generally expand recurrences unless the step dominates the loop
2682 // header. The expander handles the special case of affine recurrences by
2683 // scaling the recurrence outside the loop, but this technique isn't generally
2684 // applicable. Expanding a nested recurrence outside a loop requires computing
2685 // binomial coefficients. This could be done, but the recurrence has to be in a
2686 // perfectly reduced form, which can't be guaranteed.
2687 struct SCEVFindUnsafe {
2688  ScalarEvolution &SE;
2689  bool IsUnsafe;
2690 
2691  SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
2692 
2693  bool follow(const SCEV *S) {
2694  if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2695  const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
2696  if (!SC || SC->getValue()->isZero()) {
2697  IsUnsafe = true;
2698  return false;
2699  }
2700  }
2701  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2702  const SCEV *Step = AR->getStepRecurrence(SE);
2703  if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2704  IsUnsafe = true;
2705  return false;
2706  }
2707  }
2708  return true;
2709  }
2710  bool isDone() const { return IsUnsafe; }
2711 };
2712 }
2713 
2714 namespace llvm {
2716  SCEVFindUnsafe Search(SE);
2717  visitAll(S, Search);
2718  return !Search.IsUnsafe;
2719 }
2720 
2721 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
2722  ScalarEvolution &SE) {
2723  if (!isSafeToExpand(S, SE))
2724  return false;
2725  // We have to prove that the expanded site of S dominates InsertionPoint.
2726  // This is easy when not in the same block, but hard when S is an instruction
2727  // to be expanded somewhere inside the same block as our insertion point.
2728  // What we really need here is something analogous to an OrderedBasicBlock,
2729  // but for the moment, we paper over the problem by handling two common and
2730  // cheap to check cases.
2731  if (SE.properlyDominates(S, InsertionPoint->getParent()))
2732  return true;
2733  if (SE.dominates(S, InsertionPoint->getParent())) {
2734  if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2735  return true;
2736  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2737  if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
2738  return true;
2739  }
2740  return false;
2741 }
2742 
2744  // Result is used, nothing to remove.
2745  if (ResultUsed)
2746  return;
2747 
2748  auto InsertedInstructions = Expander.getAllInsertedInstructions();
2749 #ifndef NDEBUG
2750  SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
2751  InsertedInstructions.end());
2752  (void)InsertedSet;
2753 #endif
2754  // Remove sets with value handles.
2755  Expander.clear();
2756 
2757  // Sort so that earlier instructions do not dominate later instructions.
2758  stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
2759  return DT.dominates(B, A);
2760  });
2761  // Remove all inserted instructions.
2762  for (Instruction *I : InsertedInstructions) {
2763 
2764 #ifndef NDEBUG
2765  assert(all_of(I->users(),
2766  [&InsertedSet](Value *U) {
2767  return InsertedSet.contains(cast<Instruction>(U));
2768  }) &&
2769  "removed instruction should only be used by instructions inserted "
2770  "during expansion");
2771 #endif
2772  assert(!I->getType()->isVoidTy() &&
2773  "inserted instruction should have non-void types");
2774  I->replaceAllUsesWith(UndefValue::get(I->getType()));
2775  I->eraseFromParent();
2776  }
2777 }
2778 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:481
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::ScalarEvolution::getTruncateOrNoop
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4295
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:274
llvm::SCEVUDivExpr
This class represents a binary unsigned division operation.
Definition: ScalarEvolutionExpressions.h:303
llvm::TargetTransformInfo::TargetCostKind
TargetCostKind
The kind of cost model.
Definition: TargetTransformInfo.h:211
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4630
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2743
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SCEVUMinExpr
This class represents an unsigned minimum selection.
Definition: ScalarEvolutionExpressions.h:514
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:200
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
llvm::ScalarEvolution::getEffectiveSCEVType
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...
Definition: ScalarEvolution.cpp:3931
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::scSMinExpr
@ scSMinExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1336
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:255
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:379
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:228
ScalarEvolutionExpander.h
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:363
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:426
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:672
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SCEVSMaxExpr
This class represents a signed maximum selection.
Definition: ScalarEvolutionExpressions.h:472
llvm::scConstant
@ scConstant
Definition: ScalarEvolutionExpressions.h:41
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:469
llvm::PointerType::get
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
Definition: Type.cpp:693
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:181
llvm::SCEVPtrToIntExpr
This class represents a cast from a pointer to a pointer-sized integer value.
Definition: ScalarEvolutionExpressions.h:108
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1977
llvm::scCouldNotCompute
@ scCouldNotCompute
Definition: ScalarEvolutionExpressions.h:43
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
Definition: ScalarEvolution.cpp:3495
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:535
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1031
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder<>
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:686
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:214
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1741
llvm::SCEV::FlagNW
@ FlagNW
Definition: ScalarEvolution.h:117
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1581
Module.h
llvm::scSMaxExpr
@ scSMaxExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::ScalarEvolution::clearFlags
static LLVM_NODISCARD SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
Definition: ScalarEvolution.h:472
llvm::SCEVEqualPredicate::getRHS
const SCEV * getRHS() const
Returns the right hand side of the equality.
Definition: ScalarEvolution.h:286
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:111
llvm::Instruction::setHasNoUnsignedWrap
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:124
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::CastInst::getCastOpcode
static Instruction::CastOps getCastOpcode(const Value *Val, bool SrcIsSigned, Type *Ty, bool DstIsSigned)
Returns the opcode necessary to cast Val into Ty using usual casting rules.
Definition: Instructions.cpp:3322
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet< const Loop *, 2 >
costAndCollectOperands
static InstructionCost costAndCollectOperands(const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, SmallVectorImpl< SCEVOperand > &Worklist)
Definition: ScalarEvolutionExpander.cpp:2239
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::SCEVSignExtendExpr
This class represents a sign extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:167
llvm::SCEVExpander::hoistIVInc
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Definition: ScalarEvolutionExpander.cpp:1054
STLExtras.h
llvm::scUnknown
@ scUnknown
Definition: ScalarEvolutionExpressions.h:43
SimplifyPHINode
static Value * SimplifyPHINode(PHINode *PN, ArrayRef< Value * > IncomingValues, const SimplifyQuery &Q)
See if we can fold the given phi. If not, returns null.
Definition: InstructionSimplify.cpp:4572
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:356
llvm::TargetTransformInfo::getIntImmCostInst
InstructionCost getIntImmCostInst(unsigned Opc, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind, Instruction *Inst=nullptr) const
Return the expected cost of materialization for the given integer immediate of the specified type for...
Definition: TargetTransformInfo.cpp:557
llvm::SCEVPredicate::P_Wrap
@ P_Wrap
Definition: ScalarEvolution.h:208
llvm::SCEVOperand
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Definition: ScalarEvolutionExpander.h:46
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:201
llvm::count_if
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1637
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
llvm::SCEVExpander::getRelatedExistingExpansion
Optional< ScalarEvolution::ValueOffsetPair > getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
Definition: ScalarEvolutionExpander.cpp:2202
llvm::SCEVZeroExtendExpr
This class represents a zero extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:152
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2178
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.cpp:683
llvm::SCEVPredicate
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition: ScalarEvolution.h:200
llvm::SCEVOperand::OperandIdx
int OperandIdx
The use index of an expanded instruction.
Definition: ScalarEvolutionExpander.h:52
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:2971
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::ScalarEvolution::properlyDominates
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
Definition: ScalarEvolution.cpp:13125
llvm::isSafeToExpand
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...
Definition: ScalarEvolutionExpander.cpp:2715
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1547
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:680
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::COFF::DebugType
DebugType
Definition: COFF.h:652
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:128
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::scAddRecExpr
@ scAddRecExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVTruncateExpr
This class represents a truncation of an integer value to a smaller integer value.
Definition: ScalarEvolutionExpressions.h:137
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::scUMaxExpr
@ scUMaxExpr
Definition: ScalarEvolutionExpressions.h:42
UINT64_MAX
#define UINT64_MAX
Definition: DataTypes.h:77
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:237
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:748
llvm::BasicBlock::getFirstInsertionPt
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:249
false
Definition: StackSlotColoring.cpp:142
FactorOutConstant
static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder, const SCEV *Factor, ScalarEvolution &SE, const DataLayout &DL)
FactorOutConstant - Test if S is divisible by Factor, using signed division.
Definition: ScalarEvolutionExpander.cpp:292
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCEVMulExpr
This node represents multiplication of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:286
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2812
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:801
llvm::SCEVWrapPredicate::IncrementNSSW
@ IncrementNSSW
Definition: ScalarEvolution.h:331
llvm::SCEVUMaxExpr
This class represents an unsigned maximum selection.
Definition: ScalarEvolutionExpressions.h:486
llvm::SCEVEqualPredicate::getLHS
const SCEV * getLHS() const
Returns the left hand side of the equality.
Definition: ScalarEvolution.h:283
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6246
llvm::SCEVExprContains
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Definition: ScalarEvolutionExpressions.h:687
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
llvm::ConstantInt::get
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:899
LoopUtils.h
PickMostRelevantLoop
static const Loop * PickMostRelevantLoop(const Loop *A, const Loop *B, DominatorTree &DT)
PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion.
Definition: ScalarEvolutionExpander.cpp:659
llvm::SCEVNAryExpr
This node is a base class providing common functionality for n'ary operators.
Definition: ScalarEvolutionExpressions.h:182
PatternMatch.h
llvm::Type::getInt1PtrTy
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:251
llvm::PointerType::isOpaque
bool isOpaque() const
Definition: DerivedTypes.h:677
llvm::None
const NoneType None
Definition: None.h:23
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::SCEVOperand::S
const SCEV * S
The SCEV operand to be costed.
Definition: ScalarEvolutionExpander.h:54
ExposePointerBase
static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, ScalarEvolution &SE)
Move parts of Base into Rest to leave Base with the minimal expression that provides a pointer operan...
Definition: ScalarEvolutionExpander.cpp:929
LoopInfo.h
llvm::SCEV::isNonConstantNegative
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
Definition: ScalarEvolution.cpp:427
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:201
llvm::ScalarEvolution::dominates
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
Definition: ScalarEvolution.cpp:13121
llvm::SCEVExpander::generateOverflowCheck
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
Definition: ScalarEvolutionExpander.cpp:2498
Check
static bool Check(DecodeStatus &Out, DecodeStatus In)
Definition: AArch64Disassembler.cpp:243
llvm::cl::opt
Definition: CommandLine.h:1422
llvm::PHINode::isComplete
bool isComplete() const
If the PHI node is complete which means all of its parent's predecessors have incoming value in this ...
Definition: Instructions.h:2842
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:156
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::SCEVExpander::findInsertPointAfter
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
Definition: ScalarEvolutionExpander.cpp:100
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:604
llvm::SCEVPredicate::getKind
SCEVPredicateKind getKind() const
Definition: ScalarEvolution.h:219
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Scaled
@ Scaled
Definition: ARCInstrInfo.cpp:35
llvm::SCEVEqualPredicate
This class represents an assumption that two SCEV expressions are equal, and this can be checked at r...
Definition: ScalarEvolution.h:267
llvm::SCEVPredicate::P_Equal
@ P_Equal
Definition: ScalarEvolution.h:208
llvm::scZeroExtend
@ scZeroExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVWrapPredicate::getExpr
const SCEV * getExpr() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:13580
llvm::SCEVExpander::expandUnionPredicate
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2623
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1811
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2777
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::scAddExpr
@ scAddExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:119
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:116
llvm::ConstantExpr::get
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
Definition: Constants.cpp:2255
IsIncrementNSW
static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
Definition: ScalarEvolutionExpander.cpp:1180
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::StructLayout::getElementContainingOffset
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it.
Definition: DataLayout.cpp:82
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:631
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1612
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:369
llvm::SCEVWrapPredicate::IncrementNUSW
@ IncrementNUSW
Definition: ScalarEvolution.h:330
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:47
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::scUDivExpr
@ scUDivExpr
Definition: ScalarEvolutionExpressions.h:42
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::ConstantExpr::getCast
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1976
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:753
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::scSignExtend
@ scSignExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::TargetTransformInfo::getCastInstrCost
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:775
SimplifyAddOperands
static void SimplifyAddOperands(SmallVectorImpl< const SCEV * > &Ops, Type *Ty, ScalarEvolution &SE)
SimplifyAddOperands - Sort and simplify a list of add operands.
Definition: ScalarEvolutionExpander.cpp:365
SplitAddRecs
static void SplitAddRecs(SmallVectorImpl< const SCEV * > &Ops, Type *Ty, ScalarEvolution &SE)
SplitAddRecs - Flatten a list of add operands, moving addrec start values out to the top level.
Definition: ScalarEvolutionExpander.cpp:394
llvm::FloatStyle::Exponent
@ Exponent
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::TargetTransformInfo::isTruncateFree
bool isTruncateFree(Type *Ty1, Type *Ty2) const
Return true if it's free to truncate a value of type Ty1 to type Ty2.
Definition: TargetTransformInfo.cpp:439
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2168
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:213
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::ScalarEvolution::getSignExtendExpr
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1880
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::any_of
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:1554
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
llvm::scTruncate
@ scTruncate
Definition: ScalarEvolutionExpressions.h:41
llvm::StructLayout::getSizeInBytes
uint64_t getSizeInBytes() const
Definition: DataLayout.h:611
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:446
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
llvm::Loop::getCanonicalInductionVariable
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
Definition: LoopInfo.cpp:150
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
CostKind
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:979
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::SCEV::FlagNUW
@ FlagNUW
Definition: ScalarEvolution.h:118
llvm::TargetTransformInfo::getCmpSelInstrCost
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy=nullptr, CmpInst::Predicate VecPred=CmpInst::BAD_ICMP_PREDICATE, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:803
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::PredIterator
Definition: CFG.h:43
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
llvm::BasicBlock::getTerminator
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:148
llvm::TargetTransformInfo::CastContextHint::None
@ None
The cast is not used with a load/store of any kind.
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:854
llvm::scPtrToInt
@ scPtrToInt
Definition: ScalarEvolutionExpressions.h:43
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:934
SCEV_DEBUG_WITH_TYPE
#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
Definition: ScalarEvolutionExpander.cpp:35
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:115
llvm::APInt::getNullValue
static APInt getNullValue(unsigned numBits)
Get the '0' value.
Definition: APInt.h:574
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::APIntOps::umax
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2183
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1682
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:936
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:346
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4184
llvm::SCEVSMinExpr
This class represents a signed minimum selection.
Definition: ScalarEvolutionExpressions.h:500
llvm::normalizeForPostIncUse
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
Definition: ScalarEvolutionNormalization.cpp:96
llvm::SCEVWrapPredicate::getFlags
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
Definition: ScalarEvolution.h:379
llvm::SCEVExpander::replaceCongruentIVs
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
Definition: ScalarEvolutionExpander.cpp:2062
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::SCEVUnionPredicate
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Definition: ScalarEvolution.h:399
llvm::PHINode::Create
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...
Definition: Instructions.h:2669
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:634
llvm::SCEVCastExpr
This is the base class for unary cast operator classes.
Definition: ScalarEvolutionExpressions.h:75
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::ConstantInt::getSigned
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:913
llvm::SCEVWrapPredicate
This class represents an assumption made on an AddRec expression.
Definition: ScalarEvolution.h:304
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:530
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
llvm::SCEV::isOne
bool isOne() const
Return true if the expression is a constant one.
Definition: ScalarEvolution.cpp:415
llvm::User::operand_values
iterator_range< value_op_iterator > operand_values()
Definition: User.h:266
IsIncrementNUW
static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
Definition: ScalarEvolutionExpander.cpp:1194
llvm::ConstantExpr::getGetElementPtr
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, Optional< unsigned > InRangeIndex=None, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1210
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::SCEVOperand::ParentOpcode
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Definition: ScalarEvolutionExpander.h:50
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::SCEVExpander::expandEqualPredicate
Value * expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2486
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:787
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::formLCSSAForInstructions
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Definition: LCSSA.cpp:79
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1577
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:260
llvm::isSafeToExpandAt
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are d...
Definition: ScalarEvolutionExpander.cpp:2721
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::scMulExpr
@ scMulExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2470
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:372
llvm::SCEVPredicate::P_Union
@ P_Union
Definition: ScalarEvolution.h:208
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1404
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
Dominators.h
llvm::Type::getPointerElementType
Type * getPointerElementType() const
Definition: Type.h:380
N
#define N
llvm::CastInst::getOpcode
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:677
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2627
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:987
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:713
llvm::SmallPtrSetImpl< const SCEV * >
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:379
llvm::SCEVExpander::expandWrapPredicate
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2598
llvm::ScalarEvolution::getAddExpr
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.
Definition: ScalarEvolution.cpp:2401
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:275
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
LLVMContext.h
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:234
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:160
llvm::TargetTransformInfo::getArithmeticInstrCost
InstructionCost getArithmeticInstrCost(unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueKind Opd1Info=OK_AnyValue, OperandValueKind Opd2Info=OK_AnyValue, OperandValueProperties Opd1PropInfo=OP_None, OperandValueProperties Opd2PropInfo=OP_None, ArrayRef< const Value * > Args=ArrayRef< const Value * >(), const Instruction *CxtI=nullptr) const
This is an approximation of reciprocal throughput of a math/logic op.
Definition: TargetTransformInfo.cpp:709
llvm::scUMinExpr
@ scUMinExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:414
canBeCheaplyTransformed
static bool canBeCheaplyTransformed(ScalarEvolution &SE, const SCEVAddRecExpr *Phi, const SCEVAddRecExpr *Requested, bool &InvertStep)
Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncat...
Definition: ScalarEvolutionExpander.cpp:1146
raw_ostream.h
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:409
llvm::SCEVAddRecExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:362
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetTransformInfo::TCK_RecipThroughput
@ TCK_RecipThroughput
Reciprocal throughput.
Definition: TargetTransformInfo.h:212
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2173
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:128
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
SmallSet.h
llvm::SmallPtrSetImpl::insert
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:364