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