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 (const SCEV *Op : reverse(S->operands()))
751  OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));
752 
753  // Sort by loop. Use a stable sort so that constants follow non-constants and
754  // pointer operands precede non-pointer operands.
755  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
756 
757  // Emit instructions to add all the operands. Hoist as much as possible
758  // out of loops, and form meaningful getelementptrs where possible.
759  Value *Sum = nullptr;
760  for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
761  const Loop *CurLoop = I->first;
762  const SCEV *Op = I->second;
763  if (!Sum) {
764  // This is the first operand. Just expand it.
765  Sum = expand(Op);
766  ++I;
767  continue;
768  }
769 
770  assert(!Op->getType()->isPointerTy() && "Only first op can be pointer");
771  if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
772  // The running sum expression is a pointer. Try to form a getelementptr
773  // at this level with that as the base.
775  for (; I != E && I->first == CurLoop; ++I) {
776  // If the operand is SCEVUnknown and not instructions, peek through
777  // it, to enable more of it to be folded into the GEP.
778  const SCEV *X = I->second;
779  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
780  if (!isa<Instruction>(U->getValue()))
781  X = SE.getSCEV(U->getValue());
782  NewOps.push_back(X);
783  }
784  Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
785  } else if (Op->isNonConstantNegative()) {
786  // Instead of doing a negate and add, just do a subtract.
787  Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false);
788  Sum = InsertNoopCastOfTo(Sum, Ty);
789  Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
790  /*IsSafeToHoist*/ true);
791  ++I;
792  } else {
793  // A simple add.
794  Value *W = expandCodeForImpl(Op, Ty, false);
795  Sum = InsertNoopCastOfTo(Sum, Ty);
796  // Canonicalize a constant to the RHS.
797  if (isa<Constant>(Sum)) std::swap(Sum, W);
798  Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
799  /*IsSafeToHoist*/ true);
800  ++I;
801  }
802  }
803 
804  return Sum;
805 }
806 
807 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
808  Type *Ty = SE.getEffectiveSCEVType(S->getType());
809 
810  // Collect all the mul operands in a loop, along with their associated loops.
811  // Iterate in reverse so that constants are emitted last, all else equal.
813  for (const SCEV *Op : reverse(S->operands()))
814  OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));
815 
816  // Sort by loop. Use a stable sort so that constants follow non-constants.
817  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
818 
819  // Emit instructions to mul all the operands. Hoist as much as possible
820  // out of loops.
821  Value *Prod = nullptr;
822  auto I = OpsAndLoops.begin();
823 
824  // Expand the calculation of X pow N in the following manner:
825  // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
826  // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
827  const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
828  auto E = I;
829  // Calculate how many times the same operand from the same loop is included
830  // into this power.
831  uint64_t Exponent = 0;
832  const uint64_t MaxExponent = UINT64_MAX >> 1;
833  // No one sane will ever try to calculate such huge exponents, but if we
834  // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
835  // below when the power of 2 exceeds our Exponent, and we want it to be
836  // 1u << 31 at most to not deal with unsigned overflow.
837  while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
838  ++Exponent;
839  ++E;
840  }
841  assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
842 
843  // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
844  // that are needed into the result.
845  Value *P = expandCodeForImpl(I->second, Ty, false);
846  Value *Result = nullptr;
847  if (Exponent & 1)
848  Result = P;
849  for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
850  P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
851  /*IsSafeToHoist*/ true);
852  if (Exponent & BinExp)
853  Result = Result ? InsertBinop(Instruction::Mul, Result, P,
855  /*IsSafeToHoist*/ true)
856  : P;
857  }
858 
859  I = E;
860  assert(Result && "Nothing was expanded?");
861  return Result;
862  };
863 
864  while (I != OpsAndLoops.end()) {
865  if (!Prod) {
866  // This is the first operand. Just expand it.
867  Prod = ExpandOpBinPowN();
868  } else if (I->second->isAllOnesValue()) {
869  // Instead of doing a multiply by negative one, just do a negate.
870  Prod = InsertNoopCastOfTo(Prod, Ty);
871  Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
872  SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
873  ++I;
874  } else {
875  // A simple mul.
876  Value *W = ExpandOpBinPowN();
877  Prod = InsertNoopCastOfTo(Prod, Ty);
878  // Canonicalize a constant to the RHS.
879  if (isa<Constant>(Prod)) std::swap(Prod, W);
880  const APInt *RHS;
881  if (match(W, m_Power2(RHS))) {
882  // Canonicalize Prod*(1<<C) to Prod<<C.
883  assert(!Ty->isVectorTy() && "vector types are not SCEVable");
884  auto NWFlags = S->getNoWrapFlags();
885  // clear nsw flag if shl will produce poison value.
886  if (RHS->logBase2() == RHS->getBitWidth() - 1)
887  NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
888  Prod = InsertBinop(Instruction::Shl, Prod,
889  ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
890  /*IsSafeToHoist*/ true);
891  } else {
892  Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
893  /*IsSafeToHoist*/ true);
894  }
895  }
896  }
897 
898  return Prod;
899 }
900 
901 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
902  Type *Ty = SE.getEffectiveSCEVType(S->getType());
903 
904  Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false);
905  if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
906  const APInt &RHS = SC->getAPInt();
907  if (RHS.isPowerOf2())
908  return InsertBinop(Instruction::LShr, LHS,
909  ConstantInt::get(Ty, RHS.logBase2()),
910  SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
911  }
912 
913  Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false);
914  return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
915  /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
916 }
917 
918 /// Determine if this is a well-behaved chain of instructions leading back to
919 /// the PHI. If so, it may be reused by expanded expressions.
920 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
921  const Loop *L) {
922  if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
923  (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
924  return false;
925  // If any of the operands don't dominate the insert position, bail.
926  // Addrec operands are always loop-invariant, so this can only happen
927  // if there are instructions which haven't been hoisted.
928  if (L == IVIncInsertLoop) {
929  for (Use &Op : llvm::drop_begin(IncV->operands()))
930  if (Instruction *OInst = dyn_cast<Instruction>(Op))
931  if (!SE.DT.dominates(OInst, IVIncInsertPos))
932  return false;
933  }
934  // Advance to the next instruction.
935  IncV = dyn_cast<Instruction>(IncV->getOperand(0));
936  if (!IncV)
937  return false;
938 
939  if (IncV->mayHaveSideEffects())
940  return false;
941 
942  if (IncV == PN)
943  return true;
944 
945  return isNormalAddRecExprPHI(PN, IncV, L);
946 }
947 
948 /// getIVIncOperand returns an induction variable increment's induction
949 /// variable operand.
950 ///
951 /// If allowScale is set, any type of GEP is allowed as long as the nonIV
952 /// operands dominate InsertPos.
953 ///
954 /// If allowScale is not set, ensure that a GEP increment conforms to one of the
955 /// simple patterns generated by getAddRecExprPHILiterally and
956 /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
958  Instruction *InsertPos,
959  bool allowScale) {
960  if (IncV == InsertPos)
961  return nullptr;
962 
963  switch (IncV->getOpcode()) {
964  default:
965  return nullptr;
966  // Check for a simple Add/Sub or GEP of a loop invariant step.
967  case Instruction::Add:
968  case Instruction::Sub: {
969  Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
970  if (!OInst || SE.DT.dominates(OInst, InsertPos))
971  return dyn_cast<Instruction>(IncV->getOperand(0));
972  return nullptr;
973  }
974  case Instruction::BitCast:
975  return dyn_cast<Instruction>(IncV->getOperand(0));
976  case Instruction::GetElementPtr:
977  for (Use &U : llvm::drop_begin(IncV->operands())) {
978  if (isa<Constant>(U))
979  continue;
980  if (Instruction *OInst = dyn_cast<Instruction>(U)) {
981  if (!SE.DT.dominates(OInst, InsertPos))
982  return nullptr;
983  }
984  if (allowScale) {
985  // allow any kind of GEP as long as it can be hoisted.
986  continue;
987  }
988  // This must be a pointer addition of constants (pretty), which is already
989  // handled, or some number of address-size elements (ugly). Ugly geps
990  // have 2 operands. i1* is used by the expander to represent an
991  // address-size element.
992  if (IncV->getNumOperands() != 2)
993  return nullptr;
994  unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
995  if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
996  && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
997  return nullptr;
998  break;
999  }
1000  return dyn_cast<Instruction>(IncV->getOperand(0));
1001  }
1002 }
1003 
1004 /// If the insert point of the current builder or any of the builders on the
1005 /// stack of saved builders has 'I' as its insert point, update it to point to
1006 /// the instruction after 'I'. This is intended to be used when the instruction
1007 /// 'I' is being moved. If this fixup is not done and 'I' is moved to a
1008 /// different block, the inconsistent insert point (with a mismatched
1009 /// Instruction and Block) can lead to an instruction being inserted in a block
1010 /// other than its parent.
1011 void SCEVExpander::fixupInsertPoints(Instruction *I) {
1012  BasicBlock::iterator It(*I);
1013  BasicBlock::iterator NewInsertPt = std::next(It);
1014  if (Builder.GetInsertPoint() == It)
1015  Builder.SetInsertPoint(&*NewInsertPt);
1016  for (auto *InsertPtGuard : InsertPointGuards)
1017  if (InsertPtGuard->GetInsertPoint() == It)
1018  InsertPtGuard->SetInsertPoint(NewInsertPt);
1019 }
1020 
1021 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1022 /// it available to other uses in this loop. Recursively hoist any operands,
1023 /// until we reach a value that dominates InsertPos.
1025  if (SE.DT.dominates(IncV, InsertPos))
1026  return true;
1027 
1028  // InsertPos must itself dominate IncV so that IncV's new position satisfies
1029  // its existing users.
1030  if (isa<PHINode>(InsertPos) ||
1031  !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1032  return false;
1033 
1034  if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1035  return false;
1036 
1037  // Check that the chain of IV operands leading back to Phi can be hoisted.
1039  for(;;) {
1040  Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1041  if (!Oper)
1042  return false;
1043  // IncV is safe to hoist.
1044  IVIncs.push_back(IncV);
1045  IncV = Oper;
1046  if (SE.DT.dominates(IncV, InsertPos))
1047  break;
1048  }
1049  for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
1050  fixupInsertPoints(*I);
1051  (*I)->moveBefore(InsertPos);
1052  }
1053  return true;
1054 }
1055 
1056 /// Determine if this cyclic phi is in a form that would have been generated by
1057 /// LSR. We don't care if the phi was actually expanded in this pass, as long
1058 /// as it is in a low-cost form, for example, no implied multiplication. This
1059 /// should match any patterns generated by getAddRecExprPHILiterally and
1060 /// expandAddtoGEP.
1061 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1062  const Loop *L) {
1063  for(Instruction *IVOper = IncV;
1064  (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1065  /*allowScale=*/false));) {
1066  if (IVOper == PN)
1067  return true;
1068  }
1069  return false;
1070 }
1071 
1072 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1073 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1074 /// need to materialize IV increments elsewhere to handle difficult situations.
1075 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1076  Type *ExpandTy, Type *IntTy,
1077  bool useSubtract) {
1078  Value *IncV;
1079  // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1080  if (ExpandTy->isPointerTy()) {
1081  PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1082  // If the step isn't constant, don't use an implicitly scaled GEP, because
1083  // that would require a multiply inside the loop.
1084  if (!isa<ConstantInt>(StepV))
1085  GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
1086  GEPPtrTy->getAddressSpace());
1087  IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1088  if (IncV->getType() != PN->getType())
1089  IncV = Builder.CreateBitCast(IncV, PN->getType());
1090  } else {
1091  IncV = useSubtract ?
1092  Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1093  Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1094  }
1095  return IncV;
1096 }
1097 
1098 /// Check whether we can cheaply express the requested SCEV in terms of
1099 /// the available PHI SCEV by truncation and/or inversion of the step.
1101  const SCEVAddRecExpr *Phi,
1102  const SCEVAddRecExpr *Requested,
1103  bool &InvertStep) {
1104  // We can't transform to match a pointer PHI.
1105  if (Phi->getType()->isPointerTy())
1106  return false;
1107 
1108  Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1109  Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1110 
1111  if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1112  return false;
1113 
1114  // Try truncate it if necessary.
1115  Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1116  if (!Phi)
1117  return false;
1118 
1119  // Check whether truncation will help.
1120  if (Phi == Requested) {
1121  InvertStep = false;
1122  return true;
1123  }
1124 
1125  // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1126  if (SE.getMinusSCEV(Requested->getStart(), Requested) == Phi) {
1127  InvertStep = true;
1128  return true;
1129  }
1130 
1131  return false;
1132 }
1133 
1134 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1135  if (!isa<IntegerType>(AR->getType()))
1136  return false;
1137 
1138  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1139  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1140  const SCEV *Step = AR->getStepRecurrence(SE);
1141  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1142  SE.getSignExtendExpr(AR, WideTy));
1143  const SCEV *ExtendAfterOp =
1144  SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1145  return ExtendAfterOp == OpAfterExtend;
1146 }
1147 
1148 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1149  if (!isa<IntegerType>(AR->getType()))
1150  return false;
1151 
1152  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1153  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1154  const SCEV *Step = AR->getStepRecurrence(SE);
1155  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1156  SE.getZeroExtendExpr(AR, WideTy));
1157  const SCEV *ExtendAfterOp =
1158  SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1159  return ExtendAfterOp == OpAfterExtend;
1160 }
1161 
1162 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1163 /// the base addrec, which is the addrec without any non-loop-dominating
1164 /// values, and return the PHI.
1165 PHINode *
1166 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1167  const Loop *L,
1168  Type *ExpandTy,
1169  Type *IntTy,
1170  Type *&TruncTy,
1171  bool &InvertStep) {
1172  assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
1173 
1174  // Reuse a previously-inserted PHI, if present.
1175  BasicBlock *LatchBlock = L->getLoopLatch();
1176  if (LatchBlock) {
1177  PHINode *AddRecPhiMatch = nullptr;
1178  Instruction *IncV = nullptr;
1179  TruncTy = nullptr;
1180  InvertStep = false;
1181 
1182  // Only try partially matching scevs that need truncation and/or
1183  // step-inversion if we know this loop is outside the current loop.
1184  bool TryNonMatchingSCEV =
1185  IVIncInsertLoop &&
1186  SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1187 
1188  for (PHINode &PN : L->getHeader()->phis()) {
1189  if (!SE.isSCEVable(PN.getType()))
1190  continue;
1191 
1192  // We should not look for a incomplete PHI. Getting SCEV for a incomplete
1193  // PHI has no meaning at all.
1194  if (!PN.isComplete()) {
1196  DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");
1197  continue;
1198  }
1199 
1200  const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1201  if (!PhiSCEV)
1202  continue;
1203 
1204  bool IsMatchingSCEV = PhiSCEV == Normalized;
1205  // We only handle truncation and inversion of phi recurrences for the
1206  // expanded expression if the expanded expression's loop dominates the
1207  // loop we insert to. Check now, so we can bail out early.
1208  if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1209  continue;
1210 
1211  // TODO: this possibly can be reworked to avoid this cast at all.
1212  Instruction *TempIncV =
1213  dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1214  if (!TempIncV)
1215  continue;
1216 
1217  // Check whether we can reuse this PHI node.
1218  if (LSRMode) {
1219  if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1220  continue;
1221  } else {
1222  if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1223  continue;
1224  }
1225 
1226  // Stop if we have found an exact match SCEV.
1227  if (IsMatchingSCEV) {
1228  IncV = TempIncV;
1229  TruncTy = nullptr;
1230  InvertStep = false;
1231  AddRecPhiMatch = &PN;
1232  break;
1233  }
1234 
1235  // Try whether the phi can be translated into the requested form
1236  // (truncated and/or offset by a constant).
1237  if ((!TruncTy || InvertStep) &&
1238  canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1239  // Record the phi node. But don't stop we might find an exact match
1240  // later.
1241  AddRecPhiMatch = &PN;
1242  IncV = TempIncV;
1243  TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1244  }
1245  }
1246 
1247  if (AddRecPhiMatch) {
1248  // Ok, the add recurrence looks usable.
1249  // Remember this PHI, even in post-inc mode.
1250  InsertedValues.insert(AddRecPhiMatch);
1251  // Remember the increment.
1252  rememberInstruction(IncV);
1253  // Those values were not actually inserted but re-used.
1254  ReusedValues.insert(AddRecPhiMatch);
1255  ReusedValues.insert(IncV);
1256  return AddRecPhiMatch;
1257  }
1258  }
1259 
1260  // Save the original insertion point so we can restore it when we're done.
1261  SCEVInsertPointGuard Guard(Builder, this);
1262 
1263  // Another AddRec may need to be recursively expanded below. For example, if
1264  // this AddRec is quadratic, the StepV may itself be an AddRec in this
1265  // loop. Remove this loop from the PostIncLoops set before expanding such
1266  // AddRecs. Otherwise, we cannot find a valid position for the step
1267  // (i.e. StepV can never dominate its loop header). Ideally, we could do
1268  // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1269  // so it's not worth implementing SmallPtrSet::swap.
1270  PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1271  PostIncLoops.clear();
1272 
1273  // Expand code for the start value into the loop preheader.
1274  assert(L->getLoopPreheader() &&
1275  "Can't expand add recurrences without a loop preheader!");
1276  Value *StartV =
1277  expandCodeForImpl(Normalized->getStart(), ExpandTy,
1278  L->getLoopPreheader()->getTerminator(), false);
1279 
1280  // StartV must have been be inserted into L's preheader to dominate the new
1281  // phi.
1282  assert(!isa<Instruction>(StartV) ||
1283  SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1284  L->getHeader()));
1285 
1286  // Expand code for the step value. Do this before creating the PHI so that PHI
1287  // reuse code doesn't see an incomplete PHI.
1288  const SCEV *Step = Normalized->getStepRecurrence(SE);
1289  // If the stride is negative, insert a sub instead of an add for the increment
1290  // (unless it's a constant, because subtracts of constants are canonicalized
1291  // to adds).
1292  bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1293  if (useSubtract)
1294  Step = SE.getNegativeSCEV(Step);
1295  // Expand the step somewhere that dominates the loop header.
1296  Value *StepV = expandCodeForImpl(
1297  Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1298 
1299  // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1300  // we actually do emit an addition. It does not apply if we emit a
1301  // subtraction.
1302  bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1303  bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1304 
1305  // Create the PHI.
1306  BasicBlock *Header = L->getHeader();
1307  Builder.SetInsertPoint(Header, Header->begin());
1308  pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1309  PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1310  Twine(IVName) + ".iv");
1311 
1312  // Create the step instructions and populate the PHI.
1313  for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1314  BasicBlock *Pred = *HPI;
1315 
1316  // Add a start value.
1317  if (!L->contains(Pred)) {
1318  PN->addIncoming(StartV, Pred);
1319  continue;
1320  }
1321 
1322  // Create a step value and add it to the PHI.
1323  // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1324  // instructions at IVIncInsertPos.
1325  Instruction *InsertPos = L == IVIncInsertLoop ?
1326  IVIncInsertPos : Pred->getTerminator();
1327  Builder.SetInsertPoint(InsertPos);
1328  Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1329 
1330  if (isa<OverflowingBinaryOperator>(IncV)) {
1331  if (IncrementIsNUW)
1332  cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1333  if (IncrementIsNSW)
1334  cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1335  }
1336  PN->addIncoming(IncV, Pred);
1337  }
1338 
1339  // After expanding subexpressions, restore the PostIncLoops set so the caller
1340  // can ensure that IVIncrement dominates the current uses.
1341  PostIncLoops = SavedPostIncLoops;
1342 
1343  // Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most
1344  // effective when we are able to use an IV inserted here, so record it.
1345  InsertedValues.insert(PN);
1346  InsertedIVs.push_back(PN);
1347  return PN;
1348 }
1349 
1350 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1351  Type *STy = S->getType();
1352  Type *IntTy = SE.getEffectiveSCEVType(STy);
1353  const Loop *L = S->getLoop();
1354 
1355  // Determine a normalized form of this expression, which is the expression
1356  // before any post-inc adjustment is made.
1357  const SCEVAddRecExpr *Normalized = S;
1358  if (PostIncLoops.count(L)) {
1360  Loops.insert(L);
1361  Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1362  }
1363 
1364  // Strip off any non-loop-dominating component from the addrec start.
1365  const SCEV *Start = Normalized->getStart();
1366  const SCEV *PostLoopOffset = nullptr;
1367  if (!SE.properlyDominates(Start, L->getHeader())) {
1368  PostLoopOffset = Start;
1369  Start = SE.getConstant(Normalized->getType(), 0);
1370  Normalized = cast<SCEVAddRecExpr>(
1371  SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1372  Normalized->getLoop(),
1373  Normalized->getNoWrapFlags(SCEV::FlagNW)));
1374  }
1375 
1376  // Strip off any non-loop-dominating component from the addrec step.
1377  const SCEV *Step = Normalized->getStepRecurrence(SE);
1378  const SCEV *PostLoopScale = nullptr;
1379  if (!SE.dominates(Step, L->getHeader())) {
1380  PostLoopScale = Step;
1381  Step = SE.getConstant(Normalized->getType(), 1);
1382  if (!Start->isZero()) {
1383  // The normalization below assumes that Start is constant zero, so if
1384  // it isn't re-associate Start to PostLoopOffset.
1385  assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
1386  PostLoopOffset = Start;
1387  Start = SE.getConstant(Normalized->getType(), 0);
1388  }
1389  Normalized =
1390  cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1391  Start, Step, Normalized->getLoop(),
1392  Normalized->getNoWrapFlags(SCEV::FlagNW)));
1393  }
1394 
1395  // Expand the core addrec. If we need post-loop scaling, force it to
1396  // expand to an integer type to avoid the need for additional casting.
1397  Type *ExpandTy = PostLoopScale ? IntTy : STy;
1398  // We can't use a pointer type for the addrec if the pointer type is
1399  // non-integral.
1400  Type *AddRecPHIExpandTy =
1401  DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1402 
1403  // In some cases, we decide to reuse an existing phi node but need to truncate
1404  // it and/or invert the step.
1405  Type *TruncTy = nullptr;
1406  bool InvertStep = false;
1407  PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1408  IntTy, TruncTy, InvertStep);
1409 
1410  // Accommodate post-inc mode, if necessary.
1411  Value *Result;
1412  if (!PostIncLoops.count(L))
1413  Result = PN;
1414  else {
1415  // In PostInc mode, use the post-incremented value.
1416  BasicBlock *LatchBlock = L->getLoopLatch();
1417  assert(LatchBlock && "PostInc mode requires a unique loop latch!");
1418  Result = PN->getIncomingValueForBlock(LatchBlock);
1419 
1420  // We might be introducing a new use of the post-inc IV that is not poison
1421  // safe, in which case we should drop poison generating flags. Only keep
1422  // those flags for which SCEV has proven that they always hold.
1423  if (isa<OverflowingBinaryOperator>(Result)) {
1424  auto *I = cast<Instruction>(Result);
1425  if (!S->hasNoUnsignedWrap())
1426  I->setHasNoUnsignedWrap(false);
1427  if (!S->hasNoSignedWrap())
1428  I->setHasNoSignedWrap(false);
1429  }
1430 
1431  // For an expansion to use the postinc form, the client must call
1432  // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1433  // or dominated by IVIncInsertPos.
1434  if (isa<Instruction>(Result) &&
1435  !SE.DT.dominates(cast<Instruction>(Result),
1436  &*Builder.GetInsertPoint())) {
1437  // The induction variable's postinc expansion does not dominate this use.
1438  // IVUsers tries to prevent this case, so it is rare. However, it can
1439  // happen when an IVUser outside the loop is not dominated by the latch
1440  // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1441  // all cases. Consider a phi outside whose operand is replaced during
1442  // expansion with the value of the postinc user. Without fundamentally
1443  // changing the way postinc users are tracked, the only remedy is
1444  // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1445  // but hopefully expandCodeFor handles that.
1446  bool useSubtract =
1447  !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1448  if (useSubtract)
1449  Step = SE.getNegativeSCEV(Step);
1450  Value *StepV;
1451  {
1452  // Expand the step somewhere that dominates the loop header.
1453  SCEVInsertPointGuard Guard(Builder, this);
1454  StepV = expandCodeForImpl(
1455  Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1456  }
1457  Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1458  }
1459  }
1460 
1461  // We have decided to reuse an induction variable of a dominating loop. Apply
1462  // truncation and/or inversion of the step.
1463  if (TruncTy) {
1464  Type *ResTy = Result->getType();
1465  // Normalize the result type.
1466  if (ResTy != SE.getEffectiveSCEVType(ResTy))
1467  Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1468  // Truncate the result.
1469  if (TruncTy != Result->getType())
1470  Result = Builder.CreateTrunc(Result, TruncTy);
1471 
1472  // Invert the result.
1473  if (InvertStep)
1474  Result = Builder.CreateSub(
1475  expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result);
1476  }
1477 
1478  // Re-apply any non-loop-dominating scale.
1479  if (PostLoopScale) {
1480  assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
1481  Result = InsertNoopCastOfTo(Result, IntTy);
1482  Result = Builder.CreateMul(Result,
1483  expandCodeForImpl(PostLoopScale, IntTy, false));
1484  }
1485 
1486  // Re-apply any non-loop-dominating offset.
1487  if (PostLoopOffset) {
1488  if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1489  if (Result->getType()->isIntegerTy()) {
1490  Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false);
1491  Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1492  } else {
1493  Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1494  }
1495  } else {
1496  Result = InsertNoopCastOfTo(Result, IntTy);
1497  Result = Builder.CreateAdd(
1498  Result, expandCodeForImpl(PostLoopOffset, IntTy, false));
1499  }
1500  }
1501 
1502  return Result;
1503 }
1504 
1505 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1506  // In canonical mode we compute the addrec as an expression of a canonical IV
1507  // using evaluateAtIteration and expand the resulting SCEV expression. This
1508  // way we avoid introducing new IVs to carry on the comutation of the addrec
1509  // throughout the loop.
1510  //
1511  // For nested addrecs evaluateAtIteration might need a canonical IV of a
1512  // type wider than the addrec itself. Emitting a canonical IV of the
1513  // proper type might produce non-legal types, for example expanding an i64
1514  // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
1515  // back to non-canonical mode for nested addrecs.
1516  if (!CanonicalMode || (S->getNumOperands() > 2))
1517  return expandAddRecExprLiterally(S);
1518 
1519  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1520  const Loop *L = S->getLoop();
1521 
1522  // First check for an existing canonical IV in a suitable type.
1523  PHINode *CanonicalIV = nullptr;
1524  if (PHINode *PN = L->getCanonicalInductionVariable())
1525  if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1526  CanonicalIV = PN;
1527 
1528  // Rewrite an AddRec in terms of the canonical induction variable, if
1529  // its type is more narrow.
1530  if (CanonicalIV &&
1531  SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&
1532  !S->getType()->isPointerTy()) {
1533  SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
1534  for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1535  NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
1536  Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1537  S->getNoWrapFlags(SCEV::FlagNW)));
1538  BasicBlock::iterator NewInsertPt =
1539  findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
1540  V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1541  &*NewInsertPt, false);
1542  return V;
1543  }
1544 
1545  // {X,+,F} --> X + {0,+,F}
1546  if (!S->getStart()->isZero()) {
1547  if (PointerType *PTy = dyn_cast<PointerType>(S->getType())) {
1548  Value *StartV = expand(SE.getPointerBase(S));
1549  assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
1550  return expandAddToGEP(SE.removePointerBase(S), PTy, Ty, StartV);
1551  }
1552 
1553  SmallVector<const SCEV *, 4> NewOps(S->operands());
1554  NewOps[0] = SE.getConstant(Ty, 0);
1555  const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1556  S->getNoWrapFlags(SCEV::FlagNW));
1557 
1558  // Just do a normal add. Pre-expand the operands to suppress folding.
1559  //
1560  // The LHS and RHS values are factored out of the expand call to make the
1561  // output independent of the argument evaluation order.
1562  const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1563  const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1564  return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1565  }
1566 
1567  // If we don't yet have a canonical IV, create one.
1568  if (!CanonicalIV) {
1569  // Create and insert the PHI node for the induction variable in the
1570  // specified loop.
1571  BasicBlock *Header = L->getHeader();
1572  pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1573  CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1574  &Header->front());
1575  rememberInstruction(CanonicalIV);
1576 
1577  SmallSet<BasicBlock *, 4> PredSeen;
1578  Constant *One = ConstantInt::get(Ty, 1);
1579  for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1580  BasicBlock *HP = *HPI;
1581  if (!PredSeen.insert(HP).second) {
1582  // There must be an incoming value for each predecessor, even the
1583  // duplicates!
1584  CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1585  continue;
1586  }
1587 
1588  if (L->contains(HP)) {
1589  // Insert a unit add instruction right before the terminator
1590  // corresponding to the back-edge.
1591  Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1592  "indvar.next",
1593  HP->getTerminator());
1594  Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1595  rememberInstruction(Add);
1596  CanonicalIV->addIncoming(Add, HP);
1597  } else {
1598  CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1599  }
1600  }
1601  }
1602 
1603  // {0,+,1} --> Insert a canonical induction variable into the loop!
1604  if (S->isAffine() && S->getOperand(1)->isOne()) {
1605  assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
1606  "IVs with types different from the canonical IV should "
1607  "already have been handled!");
1608  return CanonicalIV;
1609  }
1610 
1611  // {0,+,F} --> {0,+,1} * F
1612 
1613  // If this is a simple linear addrec, emit it now as a special case.
1614  if (S->isAffine()) // {0,+,F} --> i*F
1615  return
1616  expand(SE.getTruncateOrNoop(
1617  SE.getMulExpr(SE.getUnknown(CanonicalIV),
1618  SE.getNoopOrAnyExtend(S->getOperand(1),
1619  CanonicalIV->getType())),
1620  Ty));
1621 
1622  // If this is a chain of recurrences, turn it into a closed form, using the
1623  // folders, then expandCodeFor the closed form. This allows the folders to
1624  // simplify the expression without having to build a bunch of special code
1625  // into this folder.
1626  const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV.
1627 
1628  // Promote S up to the canonical IV type, if the cast is foldable.
1629  const SCEV *NewS = S;
1630  const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1631  if (isa<SCEVAddRecExpr>(Ext))
1632  NewS = Ext;
1633 
1634  const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1635  //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
1636 
1637  // Truncate the result down to the original type, if needed.
1638  const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1639  return expand(T);
1640 }
1641 
1642 Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) {
1643  Value *V =
1644  expandCodeForImpl(S->getOperand(), S->getOperand()->getType(), false);
1645  return ReuseOrCreateCast(V, S->getType(), CastInst::PtrToInt,
1646  GetOptimalInsertionPointForCastOf(V));
1647 }
1648 
1649 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1650  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1651  Value *V = expandCodeForImpl(
1652  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1653  false);
1654  return Builder.CreateTrunc(V, Ty);
1655 }
1656 
1657 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1658  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1659  Value *V = expandCodeForImpl(
1660  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1661  false);
1662  return Builder.CreateZExt(V, Ty);
1663 }
1664 
1665 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1666  Type *Ty = SE.getEffectiveSCEVType(S->getType());
1667  Value *V = expandCodeForImpl(
1668  S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1669  false);
1670  return Builder.CreateSExt(V, Ty);
1671 }
1672 
1673 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1674  Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1675  Type *Ty = LHS->getType();
1676  for (int i = S->getNumOperands()-2; i >= 0; --i) {
1677  // In the case of mixed integer and pointer types, do the
1678  // rest of the comparisons as integer.
1679  Type *OpTy = S->getOperand(i)->getType();
1680  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1681  Ty = SE.getEffectiveSCEVType(Ty);
1682  LHS = InsertNoopCastOfTo(LHS, Ty);
1683  }
1684  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1685  Value *Sel;
1686  if (Ty->isIntegerTy())
1687  Sel = Builder.CreateIntrinsic(Intrinsic::smax, {Ty}, {LHS, RHS},
1688  /*FMFSource=*/nullptr, "smax");
1689  else {
1690  Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
1691  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
1692  }
1693  LHS = Sel;
1694  }
1695  // In the case of mixed integer and pointer types, cast the
1696  // final result back to the pointer type.
1697  if (LHS->getType() != S->getType())
1698  LHS = InsertNoopCastOfTo(LHS, S->getType());
1699  return LHS;
1700 }
1701 
1702 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1703  Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1704  Type *Ty = LHS->getType();
1705  for (int i = S->getNumOperands()-2; i >= 0; --i) {
1706  // In the case of mixed integer and pointer types, do the
1707  // rest of the comparisons as integer.
1708  Type *OpTy = S->getOperand(i)->getType();
1709  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1710  Ty = SE.getEffectiveSCEVType(Ty);
1711  LHS = InsertNoopCastOfTo(LHS, Ty);
1712  }
1713  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1714  Value *Sel;
1715  if (Ty->isIntegerTy())
1716  Sel = Builder.CreateIntrinsic(Intrinsic::umax, {Ty}, {LHS, RHS},
1717  /*FMFSource=*/nullptr, "umax");
1718  else {
1719  Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
1720  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
1721  }
1722  LHS = Sel;
1723  }
1724  // In the case of mixed integer and pointer types, cast the
1725  // final result back to the pointer type.
1726  if (LHS->getType() != S->getType())
1727  LHS = InsertNoopCastOfTo(LHS, S->getType());
1728  return LHS;
1729 }
1730 
1731 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1732  Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1733  Type *Ty = LHS->getType();
1734  for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1735  // In the case of mixed integer and pointer types, do the
1736  // rest of the comparisons as integer.
1737  Type *OpTy = S->getOperand(i)->getType();
1738  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1739  Ty = SE.getEffectiveSCEVType(Ty);
1740  LHS = InsertNoopCastOfTo(LHS, Ty);
1741  }
1742  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1743  Value *Sel;
1744  if (Ty->isIntegerTy())
1745  Sel = Builder.CreateIntrinsic(Intrinsic::smin, {Ty}, {LHS, RHS},
1746  /*FMFSource=*/nullptr, "smin");
1747  else {
1748  Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
1749  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
1750  }
1751  LHS = Sel;
1752  }
1753  // In the case of mixed integer and pointer types, cast the
1754  // final result back to the pointer type.
1755  if (LHS->getType() != S->getType())
1756  LHS = InsertNoopCastOfTo(LHS, S->getType());
1757  return LHS;
1758 }
1759 
1760 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1761  Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1762  Type *Ty = LHS->getType();
1763  for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1764  // In the case of mixed integer and pointer types, do the
1765  // rest of the comparisons as integer.
1766  Type *OpTy = S->getOperand(i)->getType();
1767  if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1768  Ty = SE.getEffectiveSCEVType(Ty);
1769  LHS = InsertNoopCastOfTo(LHS, Ty);
1770  }
1771  Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1772  Value *Sel;
1773  if (Ty->isIntegerTy())
1774  Sel = Builder.CreateIntrinsic(Intrinsic::umin, {Ty}, {LHS, RHS},
1775  /*FMFSource=*/nullptr, "umin");
1776  else {
1777  Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
1778  Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
1779  }
1780  LHS = Sel;
1781  }
1782  // In the case of mixed integer and pointer types, cast the
1783  // final result back to the pointer type.
1784  if (LHS->getType() != S->getType())
1785  LHS = InsertNoopCastOfTo(LHS, S->getType());
1786  return LHS;
1787 }
1788 
1789 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
1790  Instruction *IP, bool Root) {
1791  setInsertPoint(IP);
1792  Value *V = expandCodeForImpl(SH, Ty, Root);
1793  return V;
1794 }
1795 
1796 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
1797  // Expand the code for this SCEV.
1798  Value *V = expand(SH);
1799 
1800  if (PreserveLCSSA) {
1801  if (auto *Inst = dyn_cast<Instruction>(V)) {
1802  // Create a temporary instruction to at the current insertion point, so we
1803  // can hand it off to the helper to create LCSSA PHIs if required for the
1804  // new use.
1805  // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
1806  // would accept a insertion point and return an LCSSA phi for that
1807  // insertion point, so there is no need to insert & remove the temporary
1808  // instruction.
1809  Instruction *Tmp;
1810  if (Inst->getType()->isIntegerTy())
1811  Tmp =
1812  cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user"));
1813  else {
1814  assert(Inst->getType()->isPointerTy());
1815  Tmp = cast<Instruction>(Builder.CreatePtrToInt(
1816  Inst, Type::getInt32Ty(Inst->getContext()), "tmp.lcssa.user"));
1817  }
1818  V = fixupLCSSAFormFor(Tmp, 0);
1819 
1820  // Clean up temporary instruction.
1821  InsertedValues.erase(Tmp);
1822  InsertedPostIncValues.erase(Tmp);
1823  Tmp->eraseFromParent();
1824  }
1825  }
1826 
1827  InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V;
1828  if (Ty) {
1829  assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
1830  "non-trivial casts should be done with the SCEVs directly!");
1831  V = InsertNoopCastOfTo(V, Ty);
1832  }
1833  return V;
1834 }
1835 
1836 /// Check whether value has nuw/nsw/exact set but SCEV does not.
1837 /// TODO: In reality it is better to check the poison recursively
1838 /// but this is better than nothing.
1839 static bool SCEVLostPoisonFlags(const SCEV *S, const Instruction *I) {
1840  if (isa<OverflowingBinaryOperator>(I)) {
1841  if (auto *NS = dyn_cast<SCEVNAryExpr>(S)) {
1842  if (I->hasNoSignedWrap() && !NS->hasNoSignedWrap())
1843  return true;
1844  if (I->hasNoUnsignedWrap() && !NS->hasNoUnsignedWrap())
1845  return true;
1846  }
1847  } else if (isa<PossiblyExactOperator>(I) && I->isExact())
1848  return true;
1849  return false;
1850 }
1851 
1852 ScalarEvolution::ValueOffsetPair
1853 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1854  const Instruction *InsertPt) {
1855  auto *Set = SE.getSCEVValues(S);
1856  // If the expansion is not in CanonicalMode, and the SCEV contains any
1857  // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1858  if (CanonicalMode || !SE.containsAddRecurrence(S)) {
1859  // If S is scConstant, it may be worse to reuse an existing Value.
1860  if (S->getSCEVType() != scConstant && Set) {
1861  // Choose a Value from the set which dominates the InsertPt.
1862  // InsertPt should be inside the Value's parent loop so as not to break
1863  // the LCSSA form.
1864  for (auto const &VOPair : *Set) {
1865  Value *V = VOPair.first;
1866  ConstantInt *Offset = VOPair.second;
1867  Instruction *EntInst = dyn_cast_or_null<Instruction>(V);
1868  if (!EntInst)
1869  continue;
1870 
1871  assert(EntInst->getFunction() == InsertPt->getFunction());
1872  if (S->getType() == V->getType() &&
1873  SE.DT.dominates(EntInst, InsertPt) &&
1874  (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1875  SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)) &&
1876  !SCEVLostPoisonFlags(S, EntInst))
1877  return {V, Offset};
1878  }
1879  }
1880  }
1881  return {nullptr, nullptr};
1882 }
1883 
1884 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1885 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1886 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1887 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1888 // the expansion will try to reuse Value from ExprValueMap, and only when it
1889 // fails, expand the SCEV literally.
1890 Value *SCEVExpander::expand(const SCEV *S) {
1891  // Compute an insertion point for this SCEV object. Hoist the instructions
1892  // as far out in the loop nest as possible.
1893  Instruction *InsertPt = &*Builder.GetInsertPoint();
1894 
1895  // We can move insertion point only if there is no div or rem operations
1896  // otherwise we are risky to move it over the check for zero denominator.
1897  auto SafeToHoist = [](const SCEV *S) {
1898  return !SCEVExprContains(S, [](const SCEV *S) {
1899  if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1900  if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1901  // Division by non-zero constants can be hoisted.
1902  return SC->getValue()->isZero();
1903  // All other divisions should not be moved as they may be
1904  // divisions by zero and should be kept within the
1905  // conditions of the surrounding loops that guard their
1906  // execution (see PR35406).
1907  return true;
1908  }
1909  return false;
1910  });
1911  };
1912  if (SafeToHoist(S)) {
1913  for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1914  L = L->getParentLoop()) {
1915  if (SE.isLoopInvariant(S, L)) {
1916  if (!L) break;
1917  if (BasicBlock *Preheader = L->getLoopPreheader())
1918  InsertPt = Preheader->getTerminator();
1919  else
1920  // LSR sets the insertion point for AddRec start/step values to the
1921  // block start to simplify value reuse, even though it's an invalid
1922  // position. SCEVExpander must correct for this in all cases.
1923  InsertPt = &*L->getHeader()->getFirstInsertionPt();
1924  } else {
1925  // If the SCEV is computable at this level, insert it into the header
1926  // after the PHIs (and after any other instructions that we've inserted
1927  // there) so that it is guaranteed to dominate any user inside the loop.
1928  if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1929  InsertPt = &*L->getHeader()->getFirstInsertionPt();
1930 
1931  while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1932  (isInsertedInstruction(InsertPt) ||
1933  isa<DbgInfoIntrinsic>(InsertPt))) {
1934  InsertPt = &*std::next(InsertPt->getIterator());
1935  }
1936  break;
1937  }
1938  }
1939  }
1940 
1941  // Check to see if we already expanded this here.
1942  auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1943  if (I != InsertedExpressions.end())
1944  return I->second;
1945 
1946  SCEVInsertPointGuard Guard(Builder, this);
1947  Builder.SetInsertPoint(InsertPt);
1948 
1949  // Expand the expression into instructions.
1950  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
1951  Value *V = VO.first;
1952 
1953  if (!V)
1954  V = visit(S);
1955  else if (VO.second) {
1956  if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
1957  Type *Ety = Vty->getPointerElementType();
1958  int64_t Offset = VO.second->getSExtValue();
1959  int64_t ESize = SE.getTypeSizeInBits(Ety);
1960  if ((Offset * 8) % ESize == 0) {
1961  ConstantInt *Idx =
1962  ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
1963  V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
1964  } else {
1965  ConstantInt *Idx =
1966  ConstantInt::getSigned(VO.second->getType(), -Offset);
1967  unsigned AS = Vty->getAddressSpace();
1968  V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
1969  V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
1970  "uglygep");
1971  V = Builder.CreateBitCast(V, Vty);
1972  }
1973  } else {
1974  V = Builder.CreateSub(V, VO.second);
1975  }
1976  }
1977  // Remember the expanded value for this SCEV at this location.
1978  //
1979  // This is independent of PostIncLoops. The mapped value simply materializes
1980  // the expression at this insertion point. If the mapped value happened to be
1981  // a postinc expansion, it could be reused by a non-postinc user, but only if
1982  // its insertion point was already at the head of the loop.
1983  InsertedExpressions[std::make_pair(S, InsertPt)] = V;
1984  return V;
1985 }
1986 
1987 void SCEVExpander::rememberInstruction(Value *I) {
1988  auto DoInsert = [this](Value *V) {
1989  if (!PostIncLoops.empty())
1990  InsertedPostIncValues.insert(V);
1991  else
1992  InsertedValues.insert(V);
1993  };
1994  DoInsert(I);
1995 
1996  if (!PreserveLCSSA)
1997  return;
1998 
1999  if (auto *Inst = dyn_cast<Instruction>(I)) {
2000  // A new instruction has been added, which might introduce new uses outside
2001  // a defining loop. Fix LCSSA from for each operand of the new instruction,
2002  // if required.
2003  for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
2004  OpIdx++)
2005  fixupLCSSAFormFor(Inst, OpIdx);
2006  }
2007 }
2008 
2009 /// replaceCongruentIVs - Check for congruent phis in this loop header and
2010 /// replace them with their most canonical representative. Return the number of
2011 /// phis eliminated.
2012 ///
2013 /// This does not depend on any SCEVExpander state but should be used in
2014 /// the same context that SCEVExpander is used.
2015 unsigned
2018  const TargetTransformInfo *TTI) {
2019  // Find integer phis in order of increasing width.
2021  for (PHINode &PN : L->getHeader()->phis())
2022  Phis.push_back(&PN);
2023 
2024  if (TTI)
2025  llvm::sort(Phis, [](Value *LHS, Value *RHS) {
2026  // Put pointers at the back and make sure pointer < pointer = false.
2027  if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
2028  return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
2029  return RHS->getType()->getPrimitiveSizeInBits().getFixedSize() <
2031  });
2032 
2033  unsigned NumElim = 0;
2035  // Process phis from wide to narrow. Map wide phis to their truncation
2036  // so narrow phis can reuse them.
2037  for (PHINode *Phi : Phis) {
2038  auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
2039  if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
2040  return V;
2041  if (!SE.isSCEVable(PN->getType()))
2042  return nullptr;
2043  auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
2044  if (!Const)
2045  return nullptr;
2046  return Const->getValue();
2047  };
2048 
2049  // Fold constant phis. They may be congruent to other constant phis and
2050  // would confuse the logic below that expects proper IVs.
2051  if (Value *V = SimplifyPHINode(Phi)) {
2052  if (V->getType() != Phi->getType())
2053  continue;
2054  Phi->replaceAllUsesWith(V);
2055  DeadInsts.emplace_back(Phi);
2056  ++NumElim;
2058  dbgs() << "INDVARS: Eliminated constant iv: " << *Phi
2059  << '\n');
2060  continue;
2061  }
2062 
2063  if (!SE.isSCEVable(Phi->getType()))
2064  continue;
2065 
2066  PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
2067  if (!OrigPhiRef) {
2068  OrigPhiRef = Phi;
2069  if (Phi->getType()->isIntegerTy() && TTI &&
2070  TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
2071  // This phi can be freely truncated to the narrowest phi type. Map the
2072  // truncated expression to it so it will be reused for narrow types.
2073  const SCEV *TruncExpr =
2074  SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
2075  ExprToIVMap[TruncExpr] = Phi;
2076  }
2077  continue;
2078  }
2079 
2080  // Replacing a pointer phi with an integer phi or vice-versa doesn't make
2081  // sense.
2082  if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
2083  continue;
2084 
2085  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2086  Instruction *OrigInc = dyn_cast<Instruction>(
2087  OrigPhiRef->getIncomingValueForBlock(LatchBlock));
2088  Instruction *IsomorphicInc =
2089  dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
2090 
2091  if (OrigInc && IsomorphicInc) {
2092  // If this phi has the same width but is more canonical, replace the
2093  // original with it. As part of the "more canonical" determination,
2094  // respect a prior decision to use an IV chain.
2095  if (OrigPhiRef->getType() == Phi->getType() &&
2096  !(ChainedPhis.count(Phi) ||
2097  isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
2098  (ChainedPhis.count(Phi) ||
2099  isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2100  std::swap(OrigPhiRef, Phi);
2101  std::swap(OrigInc, IsomorphicInc);
2102  }
2103  // Replacing the congruent phi is sufficient because acyclic
2104  // redundancy elimination, CSE/GVN, should handle the
2105  // rest. However, once SCEV proves that a phi is congruent,
2106  // it's often the head of an IV user cycle that is isomorphic
2107  // with the original phi. It's worth eagerly cleaning up the
2108  // common case of a single IV increment so that DeleteDeadPHIs
2109  // can remove cycles that had postinc uses.
2110  const SCEV *TruncExpr =
2111  SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2112  if (OrigInc != IsomorphicInc &&
2113  TruncExpr == SE.getSCEV(IsomorphicInc) &&
2114  SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2115  hoistIVInc(OrigInc, IsomorphicInc)) {
2117  DebugType, dbgs() << "INDVARS: Eliminated congruent iv.inc: "
2118  << *IsomorphicInc << '\n');
2119  Value *NewInc = OrigInc;
2120  if (OrigInc->getType() != IsomorphicInc->getType()) {
2121  Instruction *IP = nullptr;
2122  if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2123  IP = &*PN->getParent()->getFirstInsertionPt();
2124  else
2125  IP = OrigInc->getNextNode();
2126 
2128  Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2129  NewInc = Builder.CreateTruncOrBitCast(
2130  OrigInc, IsomorphicInc->getType(), IVName);
2131  }
2132  IsomorphicInc->replaceAllUsesWith(NewInc);
2133  DeadInsts.emplace_back(IsomorphicInc);
2134  }
2135  }
2136  }
2138  dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi
2139  << '\n');
2141  DebugType, dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n');
2142  ++NumElim;
2143  Value *NewIV = OrigPhiRef;
2144  if (OrigPhiRef->getType() != Phi->getType()) {
2146  Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2147  NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2148  }
2149  Phi->replaceAllUsesWith(NewIV);
2150  DeadInsts.emplace_back(Phi);
2151  }
2152  return NumElim;
2153 }
2154 
2157  Loop *L) {
2158  using namespace llvm::PatternMatch;
2159 
2160  SmallVector<BasicBlock *, 4> ExitingBlocks;
2161  L->getExitingBlocks(ExitingBlocks);
2162 
2163  // Look for suitable value in simple conditions at the loop exits.
2164  for (BasicBlock *BB : ExitingBlocks) {
2165  ICmpInst::Predicate Pred;
2166  Instruction *LHS, *RHS;
2167 
2168  if (!match(BB->getTerminator(),
2169  m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
2170  m_BasicBlock(), m_BasicBlock())))
2171  continue;
2172 
2173  if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2174  return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
2175 
2176  if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2177  return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
2178  }
2179 
2180  // Use expand's logic which is used for reusing a previous Value in
2181  // ExprValueMap.
2182  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
2183  if (VO.first)
2184  return VO;
2185 
2186  // There is potential to make this significantly smarter, but this simple
2187  // heuristic already gets some interesting cases.
2188 
2189  // Can not find suitable value.
2190  return None;
2191 }
2192 
2193 template<typename T> static InstructionCost costAndCollectOperands(
2194  const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
2196  SmallVectorImpl<SCEVOperand> &Worklist) {
2197 
2198  const T *S = cast<T>(WorkItem.S);
2199  InstructionCost Cost = 0;
2200  // Object to help map SCEV operands to expanded IR instructions.
2201  struct OperationIndices {
2202  OperationIndices(unsigned Opc, size_t min, size_t max) :
2203  Opcode(Opc), MinIdx(min), MaxIdx(max) { }
2204  unsigned Opcode;
2205  size_t MinIdx;
2206  size_t MaxIdx;
2207  };
2208 
2209  // Collect the operations of all the instructions that will be needed to
2210  // expand the SCEVExpr. This is so that when we come to cost the operands,
2211  // we know what the generated user(s) will be.
2213 
2214  auto CastCost = [&](unsigned Opcode) -> InstructionCost {
2215  Operations.emplace_back(Opcode, 0, 0);
2216  return TTI.getCastInstrCost(Opcode, S->getType(),
2217  S->getOperand(0)->getType(),
2219  };
2220 
2221  auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,
2222  unsigned MinIdx = 0,
2223  unsigned MaxIdx = 1) -> InstructionCost {
2224  Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2225  return NumRequired *
2226  TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2227  };
2228 
2229  auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx,
2230  unsigned MaxIdx) -> InstructionCost {
2231  Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2232  Type *OpType = S->getOperand(0)->getType();
2233  return NumRequired * TTI.getCmpSelInstrCost(
2234  Opcode, OpType, CmpInst::makeCmpResultType(OpType),
2236  };
2237 
2238  switch (S->getSCEVType()) {
2239  case scCouldNotCompute:
2240  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2241  case scUnknown:
2242  case scConstant:
2243  return 0;
2244  case scPtrToInt:
2245  Cost = CastCost(Instruction::PtrToInt);
2246  break;
2247  case scTruncate:
2248  Cost = CastCost(Instruction::Trunc);
2249  break;
2250  case scZeroExtend:
2251  Cost = CastCost(Instruction::ZExt);
2252  break;
2253  case scSignExtend:
2254  Cost = CastCost(Instruction::SExt);
2255  break;
2256  case scUDivExpr: {
2257  unsigned Opcode = Instruction::UDiv;
2258  if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
2259  if (SC->getAPInt().isPowerOf2())
2260  Opcode = Instruction::LShr;
2261  Cost = ArithCost(Opcode, 1);
2262  break;
2263  }
2264  case scAddExpr:
2265  Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2266  break;
2267  case scMulExpr:
2268  // TODO: this is a very pessimistic cost modelling for Mul,
2269  // because of Bin Pow algorithm actually used by the expander,
2270  // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
2271  Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
2272  break;
2273  case scSMaxExpr:
2274  case scUMaxExpr:
2275  case scSMinExpr:
2276  case scUMinExpr: {
2277  // FIXME: should this ask the cost for Intrinsic's?
2278  Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2279  Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2280  break;
2281  }
2282  case scAddRecExpr: {
2283  // In this polynominal, we may have some zero operands, and we shouldn't
2284  // really charge for those. So how many non-zero coeffients are there?
2285  int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
2286  return !Op->isZero();
2287  });
2288 
2289  assert(NumTerms >= 1 && "Polynominal should have at least one term.");
2290  assert(!(*std::prev(S->operands().end()))->isZero() &&
2291  "Last operand should not be zero");
2292 
2293  // Ignoring constant term (operand 0), how many of the coeffients are u> 1?
2294  int NumNonZeroDegreeNonOneTerms =
2295  llvm::count_if(S->operands(), [](const SCEV *Op) {
2296  auto *SConst = dyn_cast<SCEVConstant>(Op);
2297  return !SConst || SConst->getAPInt().ugt(1);
2298  });
2299 
2300  // Much like with normal add expr, the polynominal will require
2301  // one less addition than the number of it's terms.
2302  InstructionCost AddCost = ArithCost(Instruction::Add, NumTerms - 1,
2303  /*MinIdx*/ 1, /*MaxIdx*/ 1);
2304  // Here, *each* one of those will require a multiplication.
2305  InstructionCost MulCost =
2306  ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
2307  Cost = AddCost + MulCost;
2308 
2309  // What is the degree of this polynominal?
2310  int PolyDegree = S->getNumOperands() - 1;
2311  assert(PolyDegree >= 1 && "Should be at least affine.");
2312 
2313  // The final term will be:
2314  // Op_{PolyDegree} * x ^ {PolyDegree}
2315  // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations.
2316  // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for
2317  // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free.
2318  // FIXME: this is conservatively correct, but might be overly pessimistic.
2319  Cost += MulCost * (PolyDegree - 1);
2320  break;
2321  }
2322  }
2323 
2324  for (auto &CostOp : Operations) {
2325  for (auto SCEVOp : enumerate(S->operands())) {
2326  // Clamp the index to account for multiple IR operations being chained.
2327  size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2328  size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2329  Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2330  }
2331  }
2332  return Cost;
2333 }
2334 
2335 bool SCEVExpander::isHighCostExpansionHelper(
2336  const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
2337  InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI,
2338  SmallPtrSetImpl<const SCEV *> &Processed,
2339  SmallVectorImpl<SCEVOperand> &Worklist) {
2340  if (Cost > Budget)
2341  return true; // Already run out of budget, give up.
2342 
2343  const SCEV *S = WorkItem.S;
2344  // Was the cost of expansion of this expression already accounted for?
2345  if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)
2346  return false; // We have already accounted for this expression.
2347 
2348  // If we can find an existing value for this scev available at the point "At"
2349  // then consider the expression cheap.
2350  if (getRelatedExistingExpansion(S, &At, L))
2351  return false; // Consider the expression to be free.
2352 
2354  L->getHeader()->getParent()->hasMinSize()
2357 
2358  switch (S->getSCEVType()) {
2359  case scCouldNotCompute:
2360  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2361  case scUnknown:
2362  // Assume to be zero-cost.
2363  return false;
2364  case scConstant: {
2365  // Only evalulate the costs of constants when optimizing for size.
2367  return 0;
2368  const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
2369  Type *Ty = S->getType();
2370  Cost += TTI.getIntImmCostInst(
2371  WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
2372  return Cost > Budget;
2373  }
2374  case scTruncate:
2375  case scPtrToInt:
2376  case scZeroExtend:
2377  case scSignExtend: {
2378  Cost +=
2379  costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
2380  return false; // Will answer upon next entry into this function.
2381  }
2382  case scUDivExpr: {
2383  // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2384  // HowManyLessThans produced to compute a precise expression, rather than a
2385  // UDiv from the user's code. If we can't find a UDiv in the code with some
2386  // simple searching, we need to account for it's cost.
2387 
2388  // At the beginning of this function we already tried to find existing
2389  // value for plain 'S'. Now try to lookup 'S + 1' since it is common
2390  // pattern involving division. This is just a simple search heuristic.
2391  if (getRelatedExistingExpansion(
2392  SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
2393  return false; // Consider it to be free.
2394 
2395  Cost +=
2396  costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
2397  return false; // Will answer upon next entry into this function.
2398  }
2399  case scAddExpr:
2400  case scMulExpr:
2401  case scUMaxExpr:
2402  case scSMaxExpr:
2403  case scUMinExpr:
2404  case scSMinExpr: {
2405  assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2406  "Nary expr should have more than 1 operand.");
2407  // The simple nary expr will require one less op (or pair of ops)
2408  // than the number of it's terms.
2409  Cost +=
2410  costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
2411  return Cost > Budget;
2412  }
2413  case scAddRecExpr: {
2414  assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2415  "Polynomial should be at least linear");
2416  Cost += costAndCollectOperands<SCEVAddRecExpr>(
2417  WorkItem, TTI, CostKind, Worklist);
2418  return Cost > Budget;
2419  }
2420  }
2421  llvm_unreachable("Unknown SCEV kind!");
2422 }
2423 
2425  Instruction *IP) {
2426  assert(IP);
2427  switch (Pred->getKind()) {
2429  return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2431  return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
2432  case SCEVPredicate::P_Wrap: {
2433  auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2434  return expandWrapPredicate(AddRecPred, IP);
2435  }
2436  }
2437  llvm_unreachable("Unknown SCEV predicate type");
2438 }
2439 
2441  Instruction *IP) {
2442  Value *Expr0 =
2443  expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
2444  Value *Expr1 =
2445  expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
2446 
2447  Builder.SetInsertPoint(IP);
2448  auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
2449  return I;
2450 }
2451 
2453  Instruction *Loc, bool Signed) {
2454  assert(AR->isAffine() && "Cannot generate RT check for "
2455  "non-affine expression");
2456 
2457  SCEVUnionPredicate Pred;
2458  const SCEV *ExitCount =
2459  SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
2460 
2461  assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count");
2462 
2463  const SCEV *Step = AR->getStepRecurrence(SE);
2464  const SCEV *Start = AR->getStart();
2465 
2466  Type *ARTy = AR->getType();
2467  unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2468  unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2469 
2470  // The expression {Start,+,Step} has nusw/nssw if
2471  // Step < 0, Start - |Step| * Backedge <= Start
2472  // Step >= 0, Start + |Step| * Backedge > Start
2473  // and |Step| * Backedge doesn't unsigned overflow.
2474 
2475  IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2476  Builder.SetInsertPoint(Loc);
2477  Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false);
2478 
2479  IntegerType *Ty =
2480  IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2481 
2482  Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false);
2483  Value *NegStepValue =
2484  expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false);
2485  Value *StartValue = expandCodeForImpl(Start, ARTy, Loc, false);
2486 
2487  ConstantInt *Zero =
2488  ConstantInt::get(Loc->getContext(), APInt::getZero(DstBits));
2489 
2490  Builder.SetInsertPoint(Loc);
2491  // Compute |Step|
2492  Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2493  Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2494 
2495  // Get the backedge taken count and truncate or extended to the AR type.
2496  Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2497 
2498  // Compute |Step| * Backedge
2499  Value *MulV, *OfMul;
2500  if (Step->isOne()) {
2501  // Special-case Step of one. Potentially-costly `umul_with_overflow` isn't
2502  // needed, there is never an overflow, so to avoid artificially inflating
2503  // the cost of the check, directly emit the optimized IR.
2504  MulV = TruncTripCount;
2505  OfMul = ConstantInt::getFalse(MulV->getContext());
2506  } else {
2507  auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2508  Intrinsic::umul_with_overflow, Ty);
2509  CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2510  MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2511  OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2512  }
2513 
2514  // Compute:
2515  // Start + |Step| * Backedge < Start
2516  // Start - |Step| * Backedge > Start
2517  Value *Add = nullptr, *Sub = nullptr;
2518  if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARTy)) {
2519  StartValue = InsertNoopCastOfTo(
2520  StartValue, Builder.getInt8PtrTy(ARPtrTy->getAddressSpace()));
2521  Value *NegMulV = Builder.CreateNeg(MulV);
2522  Add = Builder.CreateGEP(Builder.getInt8Ty(), StartValue, MulV);
2523  Sub = Builder.CreateGEP(Builder.getInt8Ty(), StartValue, NegMulV);
2524  } else {
2525  Add = Builder.CreateAdd(StartValue, MulV);
2526  Sub = Builder.CreateSub(StartValue, MulV);
2527  }
2528 
2529  Value *EndCompareGT = Builder.CreateICmp(
2530  Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2531 
2532  Value *EndCompareLT = Builder.CreateICmp(
2533  Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
2534 
2535  // Select the answer based on the sign of Step.
2536  Value *EndCheck =
2537  Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2538 
2539  // If the backedge taken count type is larger than the AR type,
2540  // check that we don't drop any bits by truncating it. If we are
2541  // dropping bits, then we have overflow (unless the step is zero).
2542  if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2543  auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2544  auto *BackedgeCheck =
2545  Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2546  ConstantInt::get(Loc->getContext(), MaxVal));
2547  BackedgeCheck = Builder.CreateAnd(
2548  BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2549 
2550  EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2551  }
2552 
2553  return Builder.CreateOr(EndCheck, OfMul);
2554 }
2555 
2557  Instruction *IP) {
2558  const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2559  Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2560 
2561  // Add a check for NUSW
2563  NUSWCheck = generateOverflowCheck(A, IP, false);
2564 
2565  // Add a check for NSSW
2567  NSSWCheck = generateOverflowCheck(A, IP, true);
2568 
2569  if (NUSWCheck && NSSWCheck)
2570  return Builder.CreateOr(NUSWCheck, NSSWCheck);
2571 
2572  if (NUSWCheck)
2573  return NUSWCheck;
2574 
2575  if (NSSWCheck)
2576  return NSSWCheck;
2577 
2578  return ConstantInt::getFalse(IP->getContext());
2579 }
2580 
2582  Instruction *IP) {
2583  auto *BoolType = IntegerType::get(IP->getContext(), 1);
2584  Value *Check = ConstantInt::getNullValue(BoolType);
2585 
2586  // Loop over all checks in this set.
2587  for (auto Pred : Union->getPredicates()) {
2588  auto *NextCheck = expandCodeForPredicate(Pred, IP);
2589  Builder.SetInsertPoint(IP);
2590  Check = Builder.CreateOr(Check, NextCheck);
2591  }
2592 
2593  return Check;
2594 }
2595 
2596 Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) {
2597  assert(PreserveLCSSA);
2599 
2600  auto *OpV = User->getOperand(OpIdx);
2601  auto *OpI = dyn_cast<Instruction>(OpV);
2602  if (!OpI)
2603  return OpV;
2604 
2605  Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
2606  Loop *UseLoop = SE.LI.getLoopFor(User->getParent());
2607  if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
2608  return OpV;
2609 
2610  ToUpdate.push_back(OpI);
2611  SmallVector<PHINode *, 16> PHIsToRemove;
2612  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove);
2613  for (PHINode *PN : PHIsToRemove) {
2614  if (!PN->use_empty())
2615  continue;
2616  InsertedValues.erase(PN);
2617  InsertedPostIncValues.erase(PN);
2618  PN->eraseFromParent();
2619  }
2620 
2621  return User->getOperand(OpIdx);
2622 }
2623 
2624 namespace {
2625 // Search for a SCEV subexpression that is not safe to expand. Any expression
2626 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2627 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
2628 // instruction, but the important thing is that we prove the denominator is
2629 // nonzero before expansion.
2630 //
2631 // IVUsers already checks that IV-derived expressions are safe. So this check is
2632 // only needed when the expression includes some subexpression that is not IV
2633 // derived.
2634 //
2635 // Currently, we only allow division by a nonzero constant here. If this is
2636 // inadequate, we could easily allow division by SCEVUnknown by using
2637 // ValueTracking to check isKnownNonZero().
2638 //
2639 // We cannot generally expand recurrences unless the step dominates the loop
2640 // header. The expander handles the special case of affine recurrences by
2641 // scaling the recurrence outside the loop, but this technique isn't generally
2642 // applicable. Expanding a nested recurrence outside a loop requires computing
2643 // binomial coefficients. This could be done, but the recurrence has to be in a
2644 // perfectly reduced form, which can't be guaranteed.
2645 struct SCEVFindUnsafe {
2646  ScalarEvolution &SE;
2647  bool CanonicalMode;
2648  bool IsUnsafe;
2649 
2650  SCEVFindUnsafe(ScalarEvolution &SE, bool CanonicalMode)
2651  : SE(SE), CanonicalMode(CanonicalMode), IsUnsafe(false) {}
2652 
2653  bool follow(const SCEV *S) {
2654  if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2655  const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
2656  if (!SC || SC->getValue()->isZero()) {
2657  IsUnsafe = true;
2658  return false;
2659  }
2660  }
2661  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2662  const SCEV *Step = AR->getStepRecurrence(SE);
2663  if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2664  IsUnsafe = true;
2665  return false;
2666  }
2667 
2668  // For non-affine addrecs or in non-canonical mode we need a preheader
2669  // to insert into.
2670  if (!AR->getLoop()->getLoopPreheader() &&
2671  (!CanonicalMode || !AR->isAffine())) {
2672  IsUnsafe = true;
2673  return false;
2674  }
2675  }
2676  return true;
2677  }
2678  bool isDone() const { return IsUnsafe; }
2679 };
2680 }
2681 
2682 namespace llvm {
2683 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode) {
2684  SCEVFindUnsafe Search(SE, CanonicalMode);
2685  visitAll(S, Search);
2686  return !Search.IsUnsafe;
2687 }
2688 
2689 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
2690  ScalarEvolution &SE) {
2691  if (!isSafeToExpand(S, SE))
2692  return false;
2693  // We have to prove that the expanded site of S dominates InsertionPoint.
2694  // This is easy when not in the same block, but hard when S is an instruction
2695  // to be expanded somewhere inside the same block as our insertion point.
2696  // What we really need here is something analogous to an OrderedBasicBlock,
2697  // but for the moment, we paper over the problem by handling two common and
2698  // cheap to check cases.
2699  if (SE.properlyDominates(S, InsertionPoint->getParent()))
2700  return true;
2701  if (SE.dominates(S, InsertionPoint->getParent())) {
2702  if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2703  return true;
2704  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2705  if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
2706  return true;
2707  }
2708  return false;
2709 }
2710 
2712  // Result is used, nothing to remove.
2713  if (ResultUsed)
2714  return;
2715 
2716  auto InsertedInstructions = Expander.getAllInsertedInstructions();
2717 #ifndef NDEBUG
2718  SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
2719  InsertedInstructions.end());
2720  (void)InsertedSet;
2721 #endif
2722  // Remove sets with value handles.
2723  Expander.clear();
2724 
2725  // Sort so that earlier instructions do not dominate later instructions.
2726  stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
2727  return DT.dominates(B, A);
2728  });
2729  // Remove all inserted instructions.
2730  for (Instruction *I : InsertedInstructions) {
2731 
2732 #ifndef NDEBUG
2733  assert(all_of(I->users(),
2734  [&InsertedSet](Value *U) {
2735  return InsertedSet.contains(cast<Instruction>(U));
2736  }) &&
2737  "removed instruction should only be used by instructions inserted "
2738  "during expansion");
2739 #endif
2740  assert(!I->getType()->isVoidTy() &&
2741  "inserted instruction should have non-void types");
2742  I->replaceAllUsesWith(UndefValue::get(I->getType()));
2743  I->eraseFromParent();
2744  }
2745 }
2746 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:502
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:4326
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:263
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:4636
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2711
llvm
This file implements support for optimizing divisions by a constant.
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:238
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:3983
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::isSafeToExpand
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode=true)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
Definition: ScalarEvolutionExpander.cpp:2683
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:1379
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:293
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:217
ScalarEvolutionExpander.h
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:363
llvm::TargetTransformInfo::getCmpSelInstrCost
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:808
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:426
T
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:673
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:425
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:729
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:199
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:1981
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:3535
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
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:687
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
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:134
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:1410
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
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:489
llvm::SCEVEqualPredicate::getRHS
const SCEV * getRHS() const
Returns the right hand side of the equality.
Definition: ScalarEvolution.h:303
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
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:3358
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:2193
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:1024
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:4627
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
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:562
llvm::SCEVPredicate::P_Wrap
@ P_Wrap
Definition: ScalarEvolution.h:225
llvm::SCEVOperand
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Definition: ScalarEvolutionExpander.h:48
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:239
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:1641
llvm::APInt::getZero
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:241
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:2156
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:2128
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:217
llvm::SCEVOperand::OperandIdx
int OperandIdx
The use index of an expanded instruction.
Definition: ScalarEvolutionExpander.h:54
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:3010
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:12731
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:1551
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:226
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:253
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:2818
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:799
llvm::SCEVWrapPredicate::IncrementNSSW
@ IncrementNSSW
Definition: ScalarEvolution.h:348
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:300
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:6281
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:1796
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:925
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:289
llvm::PointerType::isOpaque
bool isOpaque() const
Definition: DerivedTypes.h:678
llvm::None
const NoneType None
Definition: None.h:23
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
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:56
LoopInfo.h
llvm::SCEV::isNonConstantNegative
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
Definition: ScalarEvolution.cpp:425
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:190
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:12727
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:2452
Check
static bool Check(DecodeStatus &Out, DecodeStatus In)
Definition: AArch64Disassembler.cpp:242
llvm::cl::opt
Definition: CommandLine.h:1432
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:2848
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
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
uint64_t
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:613
llvm::SCEVPredicate::getKind
SCEVPredicateKind getKind() const
Definition: ScalarEvolution.h:236
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:284
llvm::SCEVPredicate::P_Equal
@ P_Equal
Definition: ScalarEvolution.h:225
llvm::scZeroExtend
@ scZeroExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVWrapPredicate::getExpr
const SCEV * getExpr() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:13215
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:2581
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1643
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
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:136
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:133
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:2267
IsIncrementNSW
static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
Definition: ScalarEvolutionExpander.cpp:1134
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
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:632
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:1616
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::SCEVWrapPredicate::IncrementNUSW
@ IncrementNUSW
Definition: ScalarEvolution.h:347
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:1988
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
SCEVLostPoisonFlags
static bool SCEVLostPoisonFlags(const SCEV *S, const Instruction *I)
Check whether value has nuw/nsw/exact set but SCEV does not.
Definition: ScalarEvolutionExpander.cpp:1839
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:780
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:650
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
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:444
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:2118
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:1883
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:1558
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::scTruncate
@ scTruncate
Definition: ScalarEvolutionExpressions.h:41
llvm::StructLayout::getSizeInBytes
uint64_t getSizeInBytes() const
Definition: DataLayout.h:620
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:444
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:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:532
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:993
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:135
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:309
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:152
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:880
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:952
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:132
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:2133
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:1686
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:348
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:4215
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:396
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:2016
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::SCEVUnionPredicate
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Definition: ScalarEvolution.h:416
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:2675
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:643
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:939
llvm::SCEVWrapPredicate
This class represents an assumption made on an AddRec expression.
Definition: ScalarEvolution.h:321
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:1492
llvm::SCEV::isOne
bool isOne() const
Return true if the expression is a constant one.
Definition: ScalarEvolution.cpp:413
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:1148
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:52
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:2440
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
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:1578
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:2689
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:2424
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
llvm::SCEVPredicate::P_Union
@ P_Union
Definition: ScalarEvolution.h:225
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:369
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:2633
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:957
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:669
llvm::SmallPtrSetImpl< const SCEV * >
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:377
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:2556
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:2424
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:313
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:714
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:412
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:1100
raw_ostream.h
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:407
llvm::SCEVAddRecExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:362
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
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:421
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:2123
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::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:166
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