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