LLVM 17.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"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Dominators.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
37using 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
44using 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.
49Value *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.
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
126SCEVExpander::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()
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.
156Value *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!");
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()) ==
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.
218Value *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.
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)
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.
294static 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 append_range(Ops, Add->operands());
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 append_range(Ops, Add->operands());
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///
453Value *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,
568 Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
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))
579 return Builder.CreateGEP(Builder.getInt8Ty(), CLHS, CRHS);
580
581 // Do a quick scan to see if we have this GEP nearby. If so, reuse it.
582 unsigned ScanLimit = 6;
583 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
584 // Scanning starts from the last instruction before the insertion point.
586 if (IP != BlockBegin) {
587 --IP;
588 for (; ScanLimit; --IP, --ScanLimit) {
589 // Don't count dbg.value against the ScanLimit, to avoid perturbing the
590 // generated code.
591 if (isa<DbgInfoIntrinsic>(IP))
592 ScanLimit++;
593 if (IP->getOpcode() == Instruction::GetElementPtr &&
594 IP->getOperand(0) == V && IP->getOperand(1) == Idx &&
595 cast<GEPOperator>(&*IP)->getSourceElementType() ==
597 return &*IP;
598 if (IP == BlockBegin) break;
599 }
600 }
601
602 // Save the original insertion point so we can restore it when we're done.
603 SCEVInsertPointGuard Guard(Builder, this);
604
605 // Move the insertion point out of as many loops as we can.
606 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
607 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
608 BasicBlock *Preheader = L->getLoopPreheader();
609 if (!Preheader) break;
610
611 // Ok, move up a level.
612 Builder.SetInsertPoint(Preheader->getTerminator());
613 }
614
615 // Emit a GEP.
616 return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
617 }
618
619 {
620 SCEVInsertPointGuard Guard(Builder, this);
621
622 // Move the insertion point out of as many loops as we can.
623 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
624 if (!L->isLoopInvariant(V)) break;
625
626 bool AnyIndexNotLoopInvariant = any_of(
627 GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
628
629 if (AnyIndexNotLoopInvariant)
630 break;
631
632 BasicBlock *Preheader = L->getLoopPreheader();
633 if (!Preheader) break;
634
635 // Ok, move up a level.
636 Builder.SetInsertPoint(Preheader->getTerminator());
637 }
638
639 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
640 // because ScalarEvolution may have changed the address arithmetic to
641 // compute a value which is beyond the end of the allocated object.
642 Value *Casted = V;
643 if (V->getType() != PTy)
644 Casted = InsertNoopCastOfTo(Casted, PTy);
645 Value *GEP = Builder.CreateGEP(PTy->getNonOpaquePointerElementType(),
646 Casted, GepIndices, "scevgep");
647 Ops.push_back(SE.getUnknown(GEP));
648 }
649
650 return expand(SE.getAddExpr(Ops));
651}
652
653Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
654 Value *V) {
655 const SCEV *const Ops[1] = {Op};
656 return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
657}
658
659/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
660/// SCEV expansion. If they are nested, this is the most nested. If they are
661/// neighboring, pick the later.
662static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
663 DominatorTree &DT) {
664 if (!A) return B;
665 if (!B) return A;
666 if (A->contains(B)) return B;
667 if (B->contains(A)) return A;
668 if (DT.dominates(A->getHeader(), B->getHeader())) return B;
669 if (DT.dominates(B->getHeader(), A->getHeader())) return A;
670 return A; // Arbitrarily break the tie.
671}
672
673/// getRelevantLoop - Get the most relevant loop associated with the given
674/// expression, according to PickMostRelevantLoop.
675const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
676 // Test whether we've already computed the most relevant loop for this SCEV.
677 auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
678 if (!Pair.second)
679 return Pair.first->second;
680
681 switch (S->getSCEVType()) {
682 case scConstant:
683 return nullptr; // A constant has no relevant loops.
684 case scTruncate:
685 case scZeroExtend:
686 case scSignExtend:
687 case scPtrToInt:
688 case scAddExpr:
689 case scMulExpr:
690 case scUDivExpr:
691 case scAddRecExpr:
692 case scUMaxExpr:
693 case scSMaxExpr:
694 case scUMinExpr:
695 case scSMinExpr:
697 const Loop *L = nullptr;
698 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
699 L = AR->getLoop();
700 for (const SCEV *Op : S->operands())
701 L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
702 return RelevantLoops[S] = L;
703 }
704 case scUnknown: {
705 const SCEVUnknown *U = cast<SCEVUnknown>(S);
706 if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
707 return Pair.first->second = SE.LI.getLoopFor(I->getParent());
708 // A non-instruction has no relevant loops.
709 return nullptr;
710 }
712 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
713 }
714 llvm_unreachable("Unexpected SCEV type!");
715}
716
717namespace {
718
719/// LoopCompare - Compare loops by PickMostRelevantLoop.
720class LoopCompare {
721 DominatorTree &DT;
722public:
723 explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
724
725 bool operator()(std::pair<const Loop *, const SCEV *> LHS,
726 std::pair<const Loop *, const SCEV *> RHS) const {
727 // Keep pointer operands sorted at the end.
728 if (LHS.second->getType()->isPointerTy() !=
729 RHS.second->getType()->isPointerTy())
730 return LHS.second->getType()->isPointerTy();
731
732 // Compare loops with PickMostRelevantLoop.
733 if (LHS.first != RHS.first)
734 return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
735
736 // If one operand is a non-constant negative and the other is not,
737 // put the non-constant negative on the right so that a sub can
738 // be used instead of a negate and add.
739 if (LHS.second->isNonConstantNegative()) {
740 if (!RHS.second->isNonConstantNegative())
741 return false;
742 } else if (RHS.second->isNonConstantNegative())
743 return true;
744
745 // Otherwise they are equivalent according to this comparison.
746 return false;
747 }
748};
749
750}
751
752Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
753 Type *Ty = SE.getEffectiveSCEVType(S->getType());
754
755 // Collect all the add operands in a loop, along with their associated loops.
756 // Iterate in reverse so that constants are emitted last, all else equal, and
757 // so that pointer operands are inserted first, which the code below relies on
758 // to form more involved GEPs.
760 for (const SCEV *Op : reverse(S->operands()))
761 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));
762
763 // Sort by loop. Use a stable sort so that constants follow non-constants and
764 // pointer operands precede non-pointer operands.
765 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
766
767 // Emit instructions to add all the operands. Hoist as much as possible
768 // out of loops, and form meaningful getelementptrs where possible.
769 Value *Sum = nullptr;
770 for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
771 const Loop *CurLoop = I->first;
772 const SCEV *Op = I->second;
773 if (!Sum) {
774 // This is the first operand. Just expand it.
775 Sum = expand(Op);
776 ++I;
777 continue;
778 }
779
780 assert(!Op->getType()->isPointerTy() && "Only first op can be pointer");
781 if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
782 // The running sum expression is a pointer. Try to form a getelementptr
783 // at this level with that as the base.
785 for (; I != E && I->first == CurLoop; ++I) {
786 // If the operand is SCEVUnknown and not instructions, peek through
787 // it, to enable more of it to be folded into the GEP.
788 const SCEV *X = I->second;
789 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
790 if (!isa<Instruction>(U->getValue()))
791 X = SE.getSCEV(U->getValue());
792 NewOps.push_back(X);
793 }
794 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
795 } else if (Op->isNonConstantNegative()) {
796 // Instead of doing a negate and add, just do a subtract.
797 Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty);
798 Sum = InsertNoopCastOfTo(Sum, Ty);
799 Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
800 /*IsSafeToHoist*/ true);
801 ++I;
802 } else {
803 // A simple add.
804 Value *W = expandCodeForImpl(Op, Ty);
805 Sum = InsertNoopCastOfTo(Sum, Ty);
806 // Canonicalize a constant to the RHS.
807 if (isa<Constant>(Sum)) std::swap(Sum, W);
808 Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
809 /*IsSafeToHoist*/ true);
810 ++I;
811 }
812 }
813
814 return Sum;
815}
816
817Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
818 Type *Ty = SE.getEffectiveSCEVType(S->getType());
819
820 // Collect all the mul operands in a loop, along with their associated loops.
821 // Iterate in reverse so that constants are emitted last, all else equal.
823 for (const SCEV *Op : reverse(S->operands()))
824 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));
825
826 // Sort by loop. Use a stable sort so that constants follow non-constants.
827 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
828
829 // Emit instructions to mul all the operands. Hoist as much as possible
830 // out of loops.
831 Value *Prod = nullptr;
832 auto I = OpsAndLoops.begin();
833
834 // Expand the calculation of X pow N in the following manner:
835 // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
836 // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
837 const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
838 auto E = I;
839 // Calculate how many times the same operand from the same loop is included
840 // into this power.
841 uint64_t Exponent = 0;
842 const uint64_t MaxExponent = UINT64_MAX >> 1;
843 // No one sane will ever try to calculate such huge exponents, but if we
844 // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
845 // below when the power of 2 exceeds our Exponent, and we want it to be
846 // 1u << 31 at most to not deal with unsigned overflow.
847 while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
848 ++Exponent;
849 ++E;
850 }
851 assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
852
853 // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
854 // that are needed into the result.
855 Value *P = expandCodeForImpl(I->second, Ty);
856 Value *Result = nullptr;
857 if (Exponent & 1)
858 Result = P;
859 for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
860 P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
861 /*IsSafeToHoist*/ true);
862 if (Exponent & BinExp)
863 Result = Result ? InsertBinop(Instruction::Mul, Result, P,
865 /*IsSafeToHoist*/ true)
866 : P;
867 }
868
869 I = E;
870 assert(Result && "Nothing was expanded?");
871 return Result;
872 };
873
874 while (I != OpsAndLoops.end()) {
875 if (!Prod) {
876 // This is the first operand. Just expand it.
877 Prod = ExpandOpBinPowN();
878 } else if (I->second->isAllOnesValue()) {
879 // Instead of doing a multiply by negative one, just do a negate.
880 Prod = InsertNoopCastOfTo(Prod, Ty);
881 Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
882 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
883 ++I;
884 } else {
885 // A simple mul.
886 Value *W = ExpandOpBinPowN();
887 Prod = InsertNoopCastOfTo(Prod, Ty);
888 // Canonicalize a constant to the RHS.
889 if (isa<Constant>(Prod)) std::swap(Prod, W);
890 const APInt *RHS;
891 if (match(W, m_Power2(RHS))) {
892 // Canonicalize Prod*(1<<C) to Prod<<C.
893 assert(!Ty->isVectorTy() && "vector types are not SCEVable");
894 auto NWFlags = S->getNoWrapFlags();
895 // clear nsw flag if shl will produce poison value.
896 if (RHS->logBase2() == RHS->getBitWidth() - 1)
897 NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
898 Prod = InsertBinop(Instruction::Shl, Prod,
899 ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
900 /*IsSafeToHoist*/ true);
901 } else {
902 Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
903 /*IsSafeToHoist*/ true);
904 }
905 }
906 }
907
908 return Prod;
909}
910
911Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
912 Type *Ty = SE.getEffectiveSCEVType(S->getType());
913
914 Value *LHS = expandCodeForImpl(S->getLHS(), Ty);
915 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
916 const APInt &RHS = SC->getAPInt();
917 if (RHS.isPowerOf2())
918 return InsertBinop(Instruction::LShr, LHS,
919 ConstantInt::get(Ty, RHS.logBase2()),
920 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
921 }
922
923 Value *RHS = expandCodeForImpl(S->getRHS(), Ty);
924 return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
925 /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
926}
927
928/// Determine if this is a well-behaved chain of instructions leading back to
929/// the PHI. If so, it may be reused by expanded expressions.
930bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
931 const Loop *L) {
932 if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
933 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
934 return false;
935 // If any of the operands don't dominate the insert position, bail.
936 // Addrec operands are always loop-invariant, so this can only happen
937 // if there are instructions which haven't been hoisted.
938 if (L == IVIncInsertLoop) {
939 for (Use &Op : llvm::drop_begin(IncV->operands()))
940 if (Instruction *OInst = dyn_cast<Instruction>(Op))
941 if (!SE.DT.dominates(OInst, IVIncInsertPos))
942 return false;
943 }
944 // Advance to the next instruction.
945 IncV = dyn_cast<Instruction>(IncV->getOperand(0));
946 if (!IncV)
947 return false;
948
949 if (IncV->mayHaveSideEffects())
950 return false;
951
952 if (IncV == PN)
953 return true;
954
955 return isNormalAddRecExprPHI(PN, IncV, L);
956}
957
958/// getIVIncOperand returns an induction variable increment's induction
959/// variable operand.
960///
961/// If allowScale is set, any type of GEP is allowed as long as the nonIV
962/// operands dominate InsertPos.
963///
964/// If allowScale is not set, ensure that a GEP increment conforms to one of the
965/// simple patterns generated by getAddRecExprPHILiterally and
966/// expandAddtoGEP. If the pattern isn't recognized, return NULL.
968 Instruction *InsertPos,
969 bool allowScale) {
970 if (IncV == InsertPos)
971 return nullptr;
972
973 switch (IncV->getOpcode()) {
974 default:
975 return nullptr;
976 // Check for a simple Add/Sub or GEP of a loop invariant step.
977 case Instruction::Add:
978 case Instruction::Sub: {
979 Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
980 if (!OInst || SE.DT.dominates(OInst, InsertPos))
981 return dyn_cast<Instruction>(IncV->getOperand(0));
982 return nullptr;
983 }
984 case Instruction::BitCast:
985 return dyn_cast<Instruction>(IncV->getOperand(0));
986 case Instruction::GetElementPtr:
987 for (Use &U : llvm::drop_begin(IncV->operands())) {
988 if (isa<Constant>(U))
989 continue;
990 if (Instruction *OInst = dyn_cast<Instruction>(U)) {
991 if (!SE.DT.dominates(OInst, InsertPos))
992 return nullptr;
993 }
994 if (allowScale) {
995 // allow any kind of GEP as long as it can be hoisted.
996 continue;
997 }
998 // This must be a pointer addition of constants (pretty), which is already
999 // handled, or some number of address-size elements (ugly). Ugly geps
1000 // have 2 operands. i1* is used by the expander to represent an
1001 // address-size element.
1002 if (IncV->getNumOperands() != 2)
1003 return nullptr;
1004 unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
1005 if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
1006 && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
1007 return nullptr;
1008 break;
1009 }
1010 return dyn_cast<Instruction>(IncV->getOperand(0));
1011 }
1012}
1013
1014/// If the insert point of the current builder or any of the builders on the
1015/// stack of saved builders has 'I' as its insert point, update it to point to
1016/// the instruction after 'I'. This is intended to be used when the instruction
1017/// 'I' is being moved. If this fixup is not done and 'I' is moved to a
1018/// different block, the inconsistent insert point (with a mismatched
1019/// Instruction and Block) can lead to an instruction being inserted in a block
1020/// other than its parent.
1021void SCEVExpander::fixupInsertPoints(Instruction *I) {
1023 BasicBlock::iterator NewInsertPt = std::next(It);
1024 if (Builder.GetInsertPoint() == It)
1025 Builder.SetInsertPoint(&*NewInsertPt);
1026 for (auto *InsertPtGuard : InsertPointGuards)
1027 if (InsertPtGuard->GetInsertPoint() == It)
1028 InsertPtGuard->SetInsertPoint(NewInsertPt);
1029}
1030
1031/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1032/// it available to other uses in this loop. Recursively hoist any operands,
1033/// until we reach a value that dominates InsertPos.
1035 bool RecomputePoisonFlags) {
1036 auto FixupPoisonFlags = [this](Instruction *I) {
1037 // Drop flags that are potentially inferred from old context and infer flags
1038 // in new context.
1039 I->dropPoisonGeneratingFlags();
1040 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(I))
1041 if (auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {
1042 auto *BO = cast<BinaryOperator>(I);
1047 }
1048 };
1049
1050 if (SE.DT.dominates(IncV, InsertPos)) {
1051 if (RecomputePoisonFlags)
1052 FixupPoisonFlags(IncV);
1053 return true;
1054 }
1055
1056 // InsertPos must itself dominate IncV so that IncV's new position satisfies
1057 // its existing users.
1058 if (isa<PHINode>(InsertPos) ||
1059 !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1060 return false;
1061
1062 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1063 return false;
1064
1065 // Check that the chain of IV operands leading back to Phi can be hoisted.
1067 for(;;) {
1068 Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1069 if (!Oper)
1070 return false;
1071 // IncV is safe to hoist.
1072 IVIncs.push_back(IncV);
1073 IncV = Oper;
1074 if (SE.DT.dominates(IncV, InsertPos))
1075 break;
1076 }
1077 for (Instruction *I : llvm::reverse(IVIncs)) {
1078 fixupInsertPoints(I);
1079 I->moveBefore(InsertPos);
1080 if (RecomputePoisonFlags)
1081 FixupPoisonFlags(I);
1082 }
1083 return true;
1084}
1085
1086/// Determine if this cyclic phi is in a form that would have been generated by
1087/// LSR. We don't care if the phi was actually expanded in this pass, as long
1088/// as it is in a low-cost form, for example, no implied multiplication. This
1089/// should match any patterns generated by getAddRecExprPHILiterally and
1090/// expandAddtoGEP.
1091bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1092 const Loop *L) {
1093 for(Instruction *IVOper = IncV;
1094 (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1095 /*allowScale=*/false));) {
1096 if (IVOper == PN)
1097 return true;
1098 }
1099 return false;
1100}
1101
1102/// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1103/// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1104/// need to materialize IV increments elsewhere to handle difficult situations.
1105Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1106 Type *ExpandTy, Type *IntTy,
1107 bool useSubtract) {
1108 Value *IncV;
1109 // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1110 if (ExpandTy->isPointerTy()) {
1111 PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1112 // If the step isn't constant, don't use an implicitly scaled GEP, because
1113 // that would require a multiply inside the loop.
1114 if (!isa<ConstantInt>(StepV))
1116 GEPPtrTy->getAddressSpace());
1117 IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1118 if (IncV->getType() != PN->getType())
1119 IncV = Builder.CreateBitCast(IncV, PN->getType());
1120 } else {
1121 IncV = useSubtract ?
1122 Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1123 Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1124 }
1125 return IncV;
1126}
1127
1128/// Check whether we can cheaply express the requested SCEV in terms of
1129/// the available PHI SCEV by truncation and/or inversion of the step.
1131 const SCEVAddRecExpr *Phi,
1132 const SCEVAddRecExpr *Requested,
1133 bool &InvertStep) {
1134 // We can't transform to match a pointer PHI.
1135 if (Phi->getType()->isPointerTy())
1136 return false;
1137
1138 Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1139 Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1140
1141 if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1142 return false;
1143
1144 // Try truncate it if necessary.
1145 Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1146 if (!Phi)
1147 return false;
1148
1149 // Check whether truncation will help.
1150 if (Phi == Requested) {
1151 InvertStep = false;
1152 return true;
1153 }
1154
1155 // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1156 if (SE.getMinusSCEV(Requested->getStart(), Requested) == Phi) {
1157 InvertStep = true;
1158 return true;
1159 }
1160
1161 return false;
1162}
1163
1164static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1165 if (!isa<IntegerType>(AR->getType()))
1166 return false;
1167
1168 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1169 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1170 const SCEV *Step = AR->getStepRecurrence(SE);
1171 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1172 SE.getSignExtendExpr(AR, WideTy));
1173 const SCEV *ExtendAfterOp =
1174 SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1175 return ExtendAfterOp == OpAfterExtend;
1176}
1177
1178static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1179 if (!isa<IntegerType>(AR->getType()))
1180 return false;
1181
1182 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1183 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1184 const SCEV *Step = AR->getStepRecurrence(SE);
1185 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1186 SE.getZeroExtendExpr(AR, WideTy));
1187 const SCEV *ExtendAfterOp =
1188 SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1189 return ExtendAfterOp == OpAfterExtend;
1190}
1191
1192/// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1193/// the base addrec, which is the addrec without any non-loop-dominating
1194/// values, and return the PHI.
1195PHINode *
1196SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1197 const Loop *L,
1198 Type *ExpandTy,
1199 Type *IntTy,
1200 Type *&TruncTy,
1201 bool &InvertStep) {
1202 assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
1203
1204 // Reuse a previously-inserted PHI, if present.
1205 BasicBlock *LatchBlock = L->getLoopLatch();
1206 if (LatchBlock) {
1207 PHINode *AddRecPhiMatch = nullptr;
1208 Instruction *IncV = nullptr;
1209 TruncTy = nullptr;
1210 InvertStep = false;
1211
1212 // Only try partially matching scevs that need truncation and/or
1213 // step-inversion if we know this loop is outside the current loop.
1214 bool TryNonMatchingSCEV =
1215 IVIncInsertLoop &&
1216 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1217
1218 for (PHINode &PN : L->getHeader()->phis()) {
1219 if (!SE.isSCEVable(PN.getType()))
1220 continue;
1221
1222 // We should not look for a incomplete PHI. Getting SCEV for a incomplete
1223 // PHI has no meaning at all.
1224 if (!PN.isComplete()) {
1226 DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");
1227 continue;
1228 }
1229
1230 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1231 if (!PhiSCEV)
1232 continue;
1233
1234 bool IsMatchingSCEV = PhiSCEV == Normalized;
1235 // We only handle truncation and inversion of phi recurrences for the
1236 // expanded expression if the expanded expression's loop dominates the
1237 // loop we insert to. Check now, so we can bail out early.
1238 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1239 continue;
1240
1241 // TODO: this possibly can be reworked to avoid this cast at all.
1242 Instruction *TempIncV =
1243 dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1244 if (!TempIncV)
1245 continue;
1246
1247 // Check whether we can reuse this PHI node.
1248 if (LSRMode) {
1249 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1250 continue;
1251 } else {
1252 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1253 continue;
1254 }
1255
1256 // Stop if we have found an exact match SCEV.
1257 if (IsMatchingSCEV) {
1258 IncV = TempIncV;
1259 TruncTy = nullptr;
1260 InvertStep = false;
1261 AddRecPhiMatch = &PN;
1262 break;
1263 }
1264
1265 // Try whether the phi can be translated into the requested form
1266 // (truncated and/or offset by a constant).
1267 if ((!TruncTy || InvertStep) &&
1268 canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1269 // Record the phi node. But don't stop we might find an exact match
1270 // later.
1271 AddRecPhiMatch = &PN;
1272 IncV = TempIncV;
1273 TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1274 }
1275 }
1276
1277 if (AddRecPhiMatch) {
1278 // Ok, the add recurrence looks usable.
1279 // Remember this PHI, even in post-inc mode.
1280 InsertedValues.insert(AddRecPhiMatch);
1281 // Remember the increment.
1282 rememberInstruction(IncV);
1283 // Those values were not actually inserted but re-used.
1284 ReusedValues.insert(AddRecPhiMatch);
1285 ReusedValues.insert(IncV);
1286 return AddRecPhiMatch;
1287 }
1288 }
1289
1290 // Save the original insertion point so we can restore it when we're done.
1291 SCEVInsertPointGuard Guard(Builder, this);
1292
1293 // Another AddRec may need to be recursively expanded below. For example, if
1294 // this AddRec is quadratic, the StepV may itself be an AddRec in this
1295 // loop. Remove this loop from the PostIncLoops set before expanding such
1296 // AddRecs. Otherwise, we cannot find a valid position for the step
1297 // (i.e. StepV can never dominate its loop header). Ideally, we could do
1298 // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1299 // so it's not worth implementing SmallPtrSet::swap.
1300 PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1301 PostIncLoops.clear();
1302
1303 // Expand code for the start value into the loop preheader.
1304 assert(L->getLoopPreheader() &&
1305 "Can't expand add recurrences without a loop preheader!");
1306 Value *StartV =
1307 expandCodeForImpl(Normalized->getStart(), ExpandTy,
1309
1310 // StartV must have been be inserted into L's preheader to dominate the new
1311 // phi.
1312 assert(!isa<Instruction>(StartV) ||
1313 SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1314 L->getHeader()));
1315
1316 // Expand code for the step value. Do this before creating the PHI so that PHI
1317 // reuse code doesn't see an incomplete PHI.
1318 const SCEV *Step = Normalized->getStepRecurrence(SE);
1319 // If the stride is negative, insert a sub instead of an add for the increment
1320 // (unless it's a constant, because subtracts of constants are canonicalized
1321 // to adds).
1322 bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1323 if (useSubtract)
1324 Step = SE.getNegativeSCEV(Step);
1325 // Expand the step somewhere that dominates the loop header.
1326 Value *StepV = expandCodeForImpl(
1327 Step, IntTy, &*L->getHeader()->getFirstInsertionPt());
1328
1329 // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1330 // we actually do emit an addition. It does not apply if we emit a
1331 // subtraction.
1332 bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1333 bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1334
1335 // Create the PHI.
1336 BasicBlock *Header = L->getHeader();
1337 Builder.SetInsertPoint(Header, Header->begin());
1338 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1339 PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1340 Twine(IVName) + ".iv");
1341
1342 // Create the step instructions and populate the PHI.
1343 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1344 BasicBlock *Pred = *HPI;
1345
1346 // Add a start value.
1347 if (!L->contains(Pred)) {
1348 PN->addIncoming(StartV, Pred);
1349 continue;
1350 }
1351
1352 // Create a step value and add it to the PHI.
1353 // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1354 // instructions at IVIncInsertPos.
1355 Instruction *InsertPos = L == IVIncInsertLoop ?
1356 IVIncInsertPos : Pred->getTerminator();
1357 Builder.SetInsertPoint(InsertPos);
1358 Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1359
1360 if (isa<OverflowingBinaryOperator>(IncV)) {
1361 if (IncrementIsNUW)
1362 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1363 if (IncrementIsNSW)
1364 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1365 }
1366 PN->addIncoming(IncV, Pred);
1367 }
1368
1369 // After expanding subexpressions, restore the PostIncLoops set so the caller
1370 // can ensure that IVIncrement dominates the current uses.
1371 PostIncLoops = SavedPostIncLoops;
1372
1373 // Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most
1374 // effective when we are able to use an IV inserted here, so record it.
1375 InsertedValues.insert(PN);
1376 InsertedIVs.push_back(PN);
1377 return PN;
1378}
1379
1380Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1381 Type *STy = S->getType();
1382 Type *IntTy = SE.getEffectiveSCEVType(STy);
1383 const Loop *L = S->getLoop();
1384
1385 // Determine a normalized form of this expression, which is the expression
1386 // before any post-inc adjustment is made.
1387 const SCEVAddRecExpr *Normalized = S;
1388 if (PostIncLoops.count(L)) {
1390 Loops.insert(L);
1391 Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1392 }
1393
1394 // Strip off any non-loop-dominating component from the addrec start.
1395 const SCEV *Start = Normalized->getStart();
1396 const SCEV *PostLoopOffset = nullptr;
1397 if (!SE.properlyDominates(Start, L->getHeader())) {
1398 PostLoopOffset = Start;
1399 Start = SE.getConstant(Normalized->getType(), 0);
1400 Normalized = cast<SCEVAddRecExpr>(
1401 SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1402 Normalized->getLoop(),
1403 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1404 }
1405
1406 // Strip off any non-loop-dominating component from the addrec step.
1407 const SCEV *Step = Normalized->getStepRecurrence(SE);
1408 const SCEV *PostLoopScale = nullptr;
1409 if (!SE.dominates(Step, L->getHeader())) {
1410 PostLoopScale = Step;
1411 Step = SE.getConstant(Normalized->getType(), 1);
1412 if (!Start->isZero()) {
1413 // The normalization below assumes that Start is constant zero, so if
1414 // it isn't re-associate Start to PostLoopOffset.
1415 assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
1416 PostLoopOffset = Start;
1417 Start = SE.getConstant(Normalized->getType(), 0);
1418 }
1419 Normalized =
1420 cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1421 Start, Step, Normalized->getLoop(),
1422 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1423 }
1424
1425 // Expand the core addrec. If we need post-loop scaling, force it to
1426 // expand to an integer type to avoid the need for additional casting.
1427 Type *ExpandTy = PostLoopScale ? IntTy : STy;
1428 // We can't use a pointer type for the addrec if the pointer type is
1429 // non-integral.
1430 Type *AddRecPHIExpandTy =
1431 DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1432
1433 // In some cases, we decide to reuse an existing phi node but need to truncate
1434 // it and/or invert the step.
1435 Type *TruncTy = nullptr;
1436 bool InvertStep = false;
1437 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1438 IntTy, TruncTy, InvertStep);
1439
1440 // Accommodate post-inc mode, if necessary.
1441 Value *Result;
1442 if (!PostIncLoops.count(L))
1443 Result = PN;
1444 else {
1445 // In PostInc mode, use the post-incremented value.
1446 BasicBlock *LatchBlock = L->getLoopLatch();
1447 assert(LatchBlock && "PostInc mode requires a unique loop latch!");
1448 Result = PN->getIncomingValueForBlock(LatchBlock);
1449
1450 // We might be introducing a new use of the post-inc IV that is not poison
1451 // safe, in which case we should drop poison generating flags. Only keep
1452 // those flags for which SCEV has proven that they always hold.
1453 if (isa<OverflowingBinaryOperator>(Result)) {
1454 auto *I = cast<Instruction>(Result);
1455 if (!S->hasNoUnsignedWrap())
1456 I->setHasNoUnsignedWrap(false);
1457 if (!S->hasNoSignedWrap())
1458 I->setHasNoSignedWrap(false);
1459 }
1460
1461 // For an expansion to use the postinc form, the client must call
1462 // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1463 // or dominated by IVIncInsertPos.
1464 if (isa<Instruction>(Result) &&
1465 !SE.DT.dominates(cast<Instruction>(Result),
1466 &*Builder.GetInsertPoint())) {
1467 // The induction variable's postinc expansion does not dominate this use.
1468 // IVUsers tries to prevent this case, so it is rare. However, it can
1469 // happen when an IVUser outside the loop is not dominated by the latch
1470 // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1471 // all cases. Consider a phi outside whose operand is replaced during
1472 // expansion with the value of the postinc user. Without fundamentally
1473 // changing the way postinc users are tracked, the only remedy is
1474 // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1475 // but hopefully expandCodeFor handles that.
1476 bool useSubtract =
1477 !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1478 if (useSubtract)
1479 Step = SE.getNegativeSCEV(Step);
1480 Value *StepV;
1481 {
1482 // Expand the step somewhere that dominates the loop header.
1483 SCEVInsertPointGuard Guard(Builder, this);
1484 StepV = expandCodeForImpl(
1485 Step, IntTy, &*L->getHeader()->getFirstInsertionPt());
1486 }
1487 Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1488 }
1489 }
1490
1491 // We have decided to reuse an induction variable of a dominating loop. Apply
1492 // truncation and/or inversion of the step.
1493 if (TruncTy) {
1494 Type *ResTy = Result->getType();
1495 // Normalize the result type.
1496 if (ResTy != SE.getEffectiveSCEVType(ResTy))
1497 Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1498 // Truncate the result.
1499 if (TruncTy != Result->getType())
1500 Result = Builder.CreateTrunc(Result, TruncTy);
1501
1502 // Invert the result.
1503 if (InvertStep)
1504 Result = Builder.CreateSub(
1505 expandCodeForImpl(Normalized->getStart(), TruncTy), Result);
1506 }
1507
1508 // Re-apply any non-loop-dominating scale.
1509 if (PostLoopScale) {
1510 assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
1511 Result = InsertNoopCastOfTo(Result, IntTy);
1512 Result = Builder.CreateMul(Result,
1513 expandCodeForImpl(PostLoopScale, IntTy));
1514 }
1515
1516 // Re-apply any non-loop-dominating offset.
1517 if (PostLoopOffset) {
1518 if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1519 if (Result->getType()->isIntegerTy()) {
1520 Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy);
1521 Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1522 } else {
1523 Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1524 }
1525 } else {
1526 Result = InsertNoopCastOfTo(Result, IntTy);
1527 Result = Builder.CreateAdd(
1528 Result, expandCodeForImpl(PostLoopOffset, IntTy));
1529 }
1530 }
1531
1532 return Result;
1533}
1534
1535Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1536 // In canonical mode we compute the addrec as an expression of a canonical IV
1537 // using evaluateAtIteration and expand the resulting SCEV expression. This
1538 // way we avoid introducing new IVs to carry on the computation of the addrec
1539 // throughout the loop.
1540 //
1541 // For nested addrecs evaluateAtIteration might need a canonical IV of a
1542 // type wider than the addrec itself. Emitting a canonical IV of the
1543 // proper type might produce non-legal types, for example expanding an i64
1544 // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
1545 // back to non-canonical mode for nested addrecs.
1546 if (!CanonicalMode || (S->getNumOperands() > 2))
1547 return expandAddRecExprLiterally(S);
1548
1549 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1550 const Loop *L = S->getLoop();
1551
1552 // First check for an existing canonical IV in a suitable type.
1553 PHINode *CanonicalIV = nullptr;
1555 if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1556 CanonicalIV = PN;
1557
1558 // Rewrite an AddRec in terms of the canonical induction variable, if
1559 // its type is more narrow.
1560 if (CanonicalIV &&
1561 SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&
1562 !S->getType()->isPointerTy()) {
1564 for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1565 NewOps[i] = SE.getAnyExtendExpr(S->getOperand(i), CanonicalIV->getType());
1566 Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1568 BasicBlock::iterator NewInsertPt =
1569 findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
1570 V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1571 &*NewInsertPt);
1572 return V;
1573 }
1574
1575 // {X,+,F} --> X + {0,+,F}
1576 if (!S->getStart()->isZero()) {
1577 if (PointerType *PTy = dyn_cast<PointerType>(S->getType())) {
1578 Value *StartV = expand(SE.getPointerBase(S));
1579 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
1580 return expandAddToGEP(SE.removePointerBase(S), PTy, Ty, StartV);
1581 }
1582
1584 NewOps[0] = SE.getConstant(Ty, 0);
1585 const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1587
1588 // Just do a normal add. Pre-expand the operands to suppress folding.
1589 //
1590 // The LHS and RHS values are factored out of the expand call to make the
1591 // output independent of the argument evaluation order.
1592 const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1593 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1594 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1595 }
1596
1597 // If we don't yet have a canonical IV, create one.
1598 if (!CanonicalIV) {
1599 // Create and insert the PHI node for the induction variable in the
1600 // specified loop.
1601 BasicBlock *Header = L->getHeader();
1602 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1603 CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1604 &Header->front());
1605 rememberInstruction(CanonicalIV);
1606
1608 Constant *One = ConstantInt::get(Ty, 1);
1609 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1610 BasicBlock *HP = *HPI;
1611 if (!PredSeen.insert(HP).second) {
1612 // There must be an incoming value for each predecessor, even the
1613 // duplicates!
1614 CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1615 continue;
1616 }
1617
1618 if (L->contains(HP)) {
1619 // Insert a unit add instruction right before the terminator
1620 // corresponding to the back-edge.
1621 Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1622 "indvar.next",
1623 HP->getTerminator());
1624 Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1625 rememberInstruction(Add);
1626 CanonicalIV->addIncoming(Add, HP);
1627 } else {
1628 CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1629 }
1630 }
1631 }
1632
1633 // {0,+,1} --> Insert a canonical induction variable into the loop!
1634 if (S->isAffine() && S->getOperand(1)->isOne()) {
1635 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
1636 "IVs with types different from the canonical IV should "
1637 "already have been handled!");
1638 return CanonicalIV;
1639 }
1640
1641 // {0,+,F} --> {0,+,1} * F
1642
1643 // If this is a simple linear addrec, emit it now as a special case.
1644 if (S->isAffine()) // {0,+,F} --> i*F
1645 return
1646 expand(SE.getTruncateOrNoop(
1647 SE.getMulExpr(SE.getUnknown(CanonicalIV),
1649 CanonicalIV->getType())),
1650 Ty));
1651
1652 // If this is a chain of recurrences, turn it into a closed form, using the
1653 // folders, then expandCodeFor the closed form. This allows the folders to
1654 // simplify the expression without having to build a bunch of special code
1655 // into this folder.
1656 const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV.
1657
1658 // Promote S up to the canonical IV type, if the cast is foldable.
1659 const SCEV *NewS = S;
1660 const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1661 if (isa<SCEVAddRecExpr>(Ext))
1662 NewS = Ext;
1663
1664 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1665
1666 // Truncate the result down to the original type, if needed.
1667 const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1668 return expand(T);
1669}
1670
1671Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) {
1672 Value *V =
1673 expandCodeForImpl(S->getOperand(), S->getOperand()->getType());
1674 return ReuseOrCreateCast(V, S->getType(), CastInst::PtrToInt,
1675 GetOptimalInsertionPointForCastOf(V));
1676}
1677
1678Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1679 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1680 Value *V = expandCodeForImpl(
1682 );
1683 return Builder.CreateTrunc(V, Ty);
1684}
1685
1686Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1687 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1688 Value *V = expandCodeForImpl(
1690 );
1691 return Builder.CreateZExt(V, Ty);
1692}
1693
1694Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1695 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1696 Value *V = expandCodeForImpl(
1698 );
1699 return Builder.CreateSExt(V, Ty);
1700}
1701
1702Value *SCEVExpander::expandMinMaxExpr(const SCEVNAryExpr *S,
1703 Intrinsic::ID IntrinID, Twine Name,
1704 bool IsSequential) {
1705 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1706 Type *Ty = LHS->getType();
1707 if (IsSequential)
1708 LHS = Builder.CreateFreeze(LHS);
1709 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1710 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty);
1711 if (IsSequential && i != 0)
1712 RHS = Builder.CreateFreeze(RHS);
1713 Value *Sel;
1714 if (Ty->isIntegerTy())
1715 Sel = Builder.CreateIntrinsic(IntrinID, {Ty}, {LHS, RHS},
1716 /*FMFSource=*/nullptr, Name);
1717 else {
1718 Value *ICmp =
1719 Builder.CreateICmp(MinMaxIntrinsic::getPredicate(IntrinID), LHS, RHS);
1720 Sel = Builder.CreateSelect(ICmp, LHS, RHS, Name);
1721 }
1722 LHS = Sel;
1723 }
1724 return LHS;
1725}
1726
1727Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1728 return expandMinMaxExpr(S, Intrinsic::smax, "smax");
1729}
1730
1731Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1732 return expandMinMaxExpr(S, Intrinsic::umax, "umax");
1733}
1734
1735Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1736 return expandMinMaxExpr(S, Intrinsic::smin, "smin");
1737}
1738
1739Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1740 return expandMinMaxExpr(S, Intrinsic::umin, "umin");
1741}
1742
1743Value *SCEVExpander::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S) {
1744 return expandMinMaxExpr(S, Intrinsic::umin, "umin", /*IsSequential*/true);
1745}
1746
1747Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
1748 Instruction *IP) {
1749 setInsertPoint(IP);
1750 Value *V = expandCodeForImpl(SH, Ty);
1751 return V;
1752}
1753
1754Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty) {
1755 // Expand the code for this SCEV.
1756 Value *V = expand(SH);
1757
1758 if (Ty) {
1759 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
1760 "non-trivial casts should be done with the SCEVs directly!");
1761 V = InsertNoopCastOfTo(V, Ty);
1762 }
1763 return V;
1764}
1765
1766Value *SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1767 const Instruction *InsertPt) {
1768 // If the expansion is not in CanonicalMode, and the SCEV contains any
1769 // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1770 if (!CanonicalMode && SE.containsAddRecurrence(S))
1771 return nullptr;
1772
1773 // If S is a constant, it may be worse to reuse an existing Value.
1774 if (isa<SCEVConstant>(S))
1775 return nullptr;
1776
1777 // Choose a Value from the set which dominates the InsertPt.
1778 // InsertPt should be inside the Value's parent loop so as not to break
1779 // the LCSSA form.
1780 for (Value *V : SE.getSCEVValues(S)) {
1781 Instruction *EntInst = dyn_cast<Instruction>(V);
1782 if (!EntInst)
1783 continue;
1784
1785 assert(EntInst->getFunction() == InsertPt->getFunction());
1786 if (S->getType() == V->getType() &&
1787 SE.DT.dominates(EntInst, InsertPt) &&
1788 (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1789 SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1790 return V;
1791 }
1792 return nullptr;
1793}
1794
1795// The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1796// or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1797// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1798// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1799// the expansion will try to reuse Value from ExprValueMap, and only when it
1800// fails, expand the SCEV literally.
1801Value *SCEVExpander::expand(const SCEV *S) {
1802 // Compute an insertion point for this SCEV object. Hoist the instructions
1803 // as far out in the loop nest as possible.
1804 Instruction *InsertPt = &*Builder.GetInsertPoint();
1805
1806 // We can move insertion point only if there is no div or rem operations
1807 // otherwise we are risky to move it over the check for zero denominator.
1808 auto SafeToHoist = [](const SCEV *S) {
1809 return !SCEVExprContains(S, [](const SCEV *S) {
1810 if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1811 if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1812 // Division by non-zero constants can be hoisted.
1813 return SC->getValue()->isZero();
1814 // All other divisions should not be moved as they may be
1815 // divisions by zero and should be kept within the
1816 // conditions of the surrounding loops that guard their
1817 // execution (see PR35406).
1818 return true;
1819 }
1820 return false;
1821 });
1822 };
1823 if (SafeToHoist(S)) {
1824 for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1825 L = L->getParentLoop()) {
1826 if (SE.isLoopInvariant(S, L)) {
1827 if (!L) break;
1828 if (BasicBlock *Preheader = L->getLoopPreheader())
1829 InsertPt = Preheader->getTerminator();
1830 else
1831 // LSR sets the insertion point for AddRec start/step values to the
1832 // block start to simplify value reuse, even though it's an invalid
1833 // position. SCEVExpander must correct for this in all cases.
1834 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1835 } else {
1836 // If the SCEV is computable at this level, insert it into the header
1837 // after the PHIs (and after any other instructions that we've inserted
1838 // there) so that it is guaranteed to dominate any user inside the loop.
1839 if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1840 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1841
1842 while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1843 (isInsertedInstruction(InsertPt) ||
1844 isa<DbgInfoIntrinsic>(InsertPt))) {
1845 InsertPt = &*std::next(InsertPt->getIterator());
1846 }
1847 break;
1848 }
1849 }
1850 }
1851
1852 // Check to see if we already expanded this here.
1853 auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1854 if (I != InsertedExpressions.end())
1855 return I->second;
1856
1857 SCEVInsertPointGuard Guard(Builder, this);
1858 Builder.SetInsertPoint(InsertPt);
1859
1860 // Expand the expression into instructions.
1861 Value *V = FindValueInExprValueMap(S, InsertPt);
1862 if (!V) {
1863 V = visit(S);
1864 V = fixupLCSSAFormFor(V);
1865 } else {
1866 // If we're reusing an existing instruction, we are effectively CSEing two
1867 // copies of the instruction (with potentially different flags). As such,
1868 // we need to drop any poison generating flags unless we can prove that
1869 // said flags must be valid for all new users.
1870 if (auto *I = dyn_cast<Instruction>(V))
1871 if (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I))
1872 I->dropPoisonGeneratingFlags();
1873 }
1874 // Remember the expanded value for this SCEV at this location.
1875 //
1876 // This is independent of PostIncLoops. The mapped value simply materializes
1877 // the expression at this insertion point. If the mapped value happened to be
1878 // a postinc expansion, it could be reused by a non-postinc user, but only if
1879 // its insertion point was already at the head of the loop.
1880 InsertedExpressions[std::make_pair(S, InsertPt)] = V;
1881 return V;
1882}
1883
1884void SCEVExpander::rememberInstruction(Value *I) {
1885 auto DoInsert = [this](Value *V) {
1886 if (!PostIncLoops.empty())
1887 InsertedPostIncValues.insert(V);
1888 else
1889 InsertedValues.insert(V);
1890 };
1891 DoInsert(I);
1892}
1893
1894/// replaceCongruentIVs - Check for congruent phis in this loop header and
1895/// replace them with their most canonical representative. Return the number of
1896/// phis eliminated.
1897///
1898/// This does not depend on any SCEVExpander state but should be used in
1899/// the same context that SCEVExpander is used.
1900unsigned
1903 const TargetTransformInfo *TTI) {
1904 // Find integer phis in order of increasing width.
1906 for (PHINode &PN : L->getHeader()->phis())
1907 Phis.push_back(&PN);
1908
1909 if (TTI)
1910 // Use stable_sort to preserve order of equivalent PHIs, so the order
1911 // of the sorted Phis is the same from run to run on the same loop.
1912 llvm::stable_sort(Phis, [](Value *LHS, Value *RHS) {
1913 // Put pointers at the back and make sure pointer < pointer = false.
1914 if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
1915 return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
1918 });
1919
1920 unsigned NumElim = 0;
1922 // Process phis from wide to narrow. Map wide phis to their truncation
1923 // so narrow phis can reuse them.
1924 for (PHINode *Phi : Phis) {
1925 auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
1926 if (Value *V = simplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
1927 return V;
1928 if (!SE.isSCEVable(PN->getType()))
1929 return nullptr;
1930 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
1931 if (!Const)
1932 return nullptr;
1933 return Const->getValue();
1934 };
1935
1936 // Fold constant phis. They may be congruent to other constant phis and
1937 // would confuse the logic below that expects proper IVs.
1938 if (Value *V = SimplifyPHINode(Phi)) {
1939 if (V->getType() != Phi->getType())
1940 continue;
1941 SE.forgetValue(Phi);
1942 Phi->replaceAllUsesWith(V);
1943 DeadInsts.emplace_back(Phi);
1944 ++NumElim;
1945 SCEV_DEBUG_WITH_TYPE(DebugType,
1946 dbgs() << "INDVARS: Eliminated constant iv: " << *Phi
1947 << '\n');
1948 continue;
1949 }
1950
1951 if (!SE.isSCEVable(Phi->getType()))
1952 continue;
1953
1954 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
1955 if (!OrigPhiRef) {
1956 OrigPhiRef = Phi;
1957 if (Phi->getType()->isIntegerTy() && TTI &&
1958 TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
1959 // This phi can be freely truncated to the narrowest phi type. Map the
1960 // truncated expression to it so it will be reused for narrow types.
1961 const SCEV *TruncExpr =
1962 SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
1963 ExprToIVMap[TruncExpr] = Phi;
1964 }
1965 continue;
1966 }
1967
1968 // Replacing a pointer phi with an integer phi or vice-versa doesn't make
1969 // sense.
1970 if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
1971 continue;
1972
1973 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1974 Instruction *OrigInc = dyn_cast<Instruction>(
1975 OrigPhiRef->getIncomingValueForBlock(LatchBlock));
1976 Instruction *IsomorphicInc =
1977 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
1978
1979 if (OrigInc && IsomorphicInc) {
1980 // If this phi has the same width but is more canonical, replace the
1981 // original with it. As part of the "more canonical" determination,
1982 // respect a prior decision to use an IV chain.
1983 if (OrigPhiRef->getType() == Phi->getType() &&
1984 !(ChainedPhis.count(Phi) ||
1985 isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
1986 (ChainedPhis.count(Phi) ||
1987 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
1988 std::swap(OrigPhiRef, Phi);
1989 std::swap(OrigInc, IsomorphicInc);
1990 }
1991 // Replacing the congruent phi is sufficient because acyclic
1992 // redundancy elimination, CSE/GVN, should handle the
1993 // rest. However, once SCEV proves that a phi is congruent,
1994 // it's often the head of an IV user cycle that is isomorphic
1995 // with the original phi. It's worth eagerly cleaning up the
1996 // common case of a single IV increment so that DeleteDeadPHIs
1997 // can remove cycles that had postinc uses.
1998 // Because we may potentially introduce a new use of OrigIV that didn't
1999 // exist before at this point, its poison flags need readjustment.
2000 const SCEV *TruncExpr =
2001 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2002 if (OrigInc != IsomorphicInc &&
2003 TruncExpr == SE.getSCEV(IsomorphicInc) &&
2004 SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2005 hoistIVInc(OrigInc, IsomorphicInc, /*RecomputePoisonFlags*/ true)) {
2007 DebugType, dbgs() << "INDVARS: Eliminated congruent iv.inc: "
2008 << *IsomorphicInc << '\n');
2009 Value *NewInc = OrigInc;
2010 if (OrigInc->getType() != IsomorphicInc->getType()) {
2011 Instruction *IP = nullptr;
2012 if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2013 IP = &*PN->getParent()->getFirstInsertionPt();
2014 else
2015 IP = OrigInc->getNextNode();
2016
2017 IRBuilder<> Builder(IP);
2018 Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2019 NewInc = Builder.CreateTruncOrBitCast(
2020 OrigInc, IsomorphicInc->getType(), IVName);
2021 }
2022 IsomorphicInc->replaceAllUsesWith(NewInc);
2023 DeadInsts.emplace_back(IsomorphicInc);
2024 }
2025 }
2026 }
2027 SCEV_DEBUG_WITH_TYPE(DebugType,
2028 dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi
2029 << '\n');
2031 DebugType, dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n');
2032 ++NumElim;
2033 Value *NewIV = OrigPhiRef;
2034 if (OrigPhiRef->getType() != Phi->getType()) {
2035 IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
2036 Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2037 NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2038 }
2039 Phi->replaceAllUsesWith(NewIV);
2040 DeadInsts.emplace_back(Phi);
2041 }
2042 return NumElim;
2043}
2044
2046 const Instruction *At,
2047 Loop *L) {
2048 using namespace llvm::PatternMatch;
2049
2050 SmallVector<BasicBlock *, 4> ExitingBlocks;
2051 L->getExitingBlocks(ExitingBlocks);
2052
2053 // Look for suitable value in simple conditions at the loop exits.
2054 for (BasicBlock *BB : ExitingBlocks) {
2056 Instruction *LHS, *RHS;
2057
2058 if (!match(BB->getTerminator(),
2061 continue;
2062
2063 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2064 return LHS;
2065
2066 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2067 return RHS;
2068 }
2069
2070 // Use expand's logic which is used for reusing a previous Value in
2071 // ExprValueMap. Note that we don't currently model the cost of
2072 // needing to drop poison generating flags on the instruction if we
2073 // want to reuse it. We effectively assume that has zero cost.
2074 return FindValueInExprValueMap(S, At);
2075}
2076
2077template<typename T> static InstructionCost costAndCollectOperands(
2078 const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
2080 SmallVectorImpl<SCEVOperand> &Worklist) {
2081
2082 const T *S = cast<T>(WorkItem.S);
2084 // Object to help map SCEV operands to expanded IR instructions.
2085 struct OperationIndices {
2086 OperationIndices(unsigned Opc, size_t min, size_t max) :
2087 Opcode(Opc), MinIdx(min), MaxIdx(max) { }
2088 unsigned Opcode;
2089 size_t MinIdx;
2090 size_t MaxIdx;
2091 };
2092
2093 // Collect the operations of all the instructions that will be needed to
2094 // expand the SCEVExpr. This is so that when we come to cost the operands,
2095 // we know what the generated user(s) will be.
2097
2098 auto CastCost = [&](unsigned Opcode) -> InstructionCost {
2099 Operations.emplace_back(Opcode, 0, 0);
2100 return TTI.getCastInstrCost(Opcode, S->getType(),
2101 S->getOperand(0)->getType(),
2103 };
2104
2105 auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,
2106 unsigned MinIdx = 0,
2107 unsigned MaxIdx = 1) -> InstructionCost {
2108 Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2109 return NumRequired *
2110 TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2111 };
2112
2113 auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx,
2114 unsigned MaxIdx) -> InstructionCost {
2115 Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2116 Type *OpType = S->getType();
2117 return NumRequired * TTI.getCmpSelInstrCost(
2118 Opcode, OpType, CmpInst::makeCmpResultType(OpType),
2120 };
2121
2122 switch (S->getSCEVType()) {
2123 case scCouldNotCompute:
2124 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2125 case scUnknown:
2126 case scConstant:
2127 return 0;
2128 case scPtrToInt:
2129 Cost = CastCost(Instruction::PtrToInt);
2130 break;
2131 case scTruncate:
2132 Cost = CastCost(Instruction::Trunc);
2133 break;
2134 case scZeroExtend:
2135 Cost = CastCost(Instruction::ZExt);
2136 break;
2137 case scSignExtend:
2138 Cost = CastCost(Instruction::SExt);
2139 break;
2140 case scUDivExpr: {
2141 unsigned Opcode = Instruction::UDiv;
2142 if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
2143 if (SC->getAPInt().isPowerOf2())
2144 Opcode = Instruction::LShr;
2145 Cost = ArithCost(Opcode, 1);
2146 break;
2147 }
2148 case scAddExpr:
2149 Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2150 break;
2151 case scMulExpr:
2152 // TODO: this is a very pessimistic cost modelling for Mul,
2153 // because of Bin Pow algorithm actually used by the expander,
2154 // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
2155 Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
2156 break;
2157 case scSMaxExpr:
2158 case scUMaxExpr:
2159 case scSMinExpr:
2160 case scUMinExpr:
2161 case scSequentialUMinExpr: {
2162 // FIXME: should this ask the cost for Intrinsic's?
2163 // The reduction tree.
2164 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2165 Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2166 switch (S->getSCEVType()) {
2167 case scSequentialUMinExpr: {
2168 // The safety net against poison.
2169 // FIXME: this is broken.
2170 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);
2171 Cost += ArithCost(Instruction::Or,
2172 S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);
2173 Cost += CmpSelCost(Instruction::Select, 1, 0, 1);
2174 break;
2175 }
2176 default:
2177 assert(!isa<SCEVSequentialMinMaxExpr>(S) &&
2178 "Unhandled SCEV expression type?");
2179 break;
2180 }
2181 break;
2182 }
2183 case scAddRecExpr: {
2184 // In this polynominal, we may have some zero operands, and we shouldn't
2185 // really charge for those. So how many non-zero coefficients are there?
2186 int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
2187 return !Op->isZero();
2188 });
2189
2190 assert(NumTerms >= 1 && "Polynominal should have at least one term.");
2191 assert(!(*std::prev(S->operands().end()))->isZero() &&
2192 "Last operand should not be zero");
2193
2194 // Ignoring constant term (operand 0), how many of the coefficients are u> 1?
2195 int NumNonZeroDegreeNonOneTerms =
2196 llvm::count_if(S->operands(), [](const SCEV *Op) {
2197 auto *SConst = dyn_cast<SCEVConstant>(Op);
2198 return !SConst || SConst->getAPInt().ugt(1);
2199 });
2200
2201 // Much like with normal add expr, the polynominal will require
2202 // one less addition than the number of it's terms.
2203 InstructionCost AddCost = ArithCost(Instruction::Add, NumTerms - 1,
2204 /*MinIdx*/ 1, /*MaxIdx*/ 1);
2205 // Here, *each* one of those will require a multiplication.
2206 InstructionCost MulCost =
2207 ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
2208 Cost = AddCost + MulCost;
2209
2210 // What is the degree of this polynominal?
2211 int PolyDegree = S->getNumOperands() - 1;
2212 assert(PolyDegree >= 1 && "Should be at least affine.");
2213
2214 // The final term will be:
2215 // Op_{PolyDegree} * x ^ {PolyDegree}
2216 // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations.
2217 // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for
2218 // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free.
2219 // FIXME: this is conservatively correct, but might be overly pessimistic.
2220 Cost += MulCost * (PolyDegree - 1);
2221 break;
2222 }
2223 }
2224
2225 for (auto &CostOp : Operations) {
2226 for (auto SCEVOp : enumerate(S->operands())) {
2227 // Clamp the index to account for multiple IR operations being chained.
2228 size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2229 size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2230 Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2231 }
2232 }
2233 return Cost;
2234}
2235
2236bool SCEVExpander::isHighCostExpansionHelper(
2237 const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
2238 InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI,
2240 SmallVectorImpl<SCEVOperand> &Worklist) {
2241 if (Cost > Budget)
2242 return true; // Already run out of budget, give up.
2243
2244 const SCEV *S = WorkItem.S;
2245 // Was the cost of expansion of this expression already accounted for?
2246 if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)
2247 return false; // We have already accounted for this expression.
2248
2249 // If we can find an existing value for this scev available at the point "At"
2250 // then consider the expression cheap.
2251 if (getRelatedExistingExpansion(S, &At, L))
2252 return false; // Consider the expression to be free.
2253
2255 L->getHeader()->getParent()->hasMinSize()
2258
2259 switch (S->getSCEVType()) {
2260 case scCouldNotCompute:
2261 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2262 case scUnknown:
2263 // Assume to be zero-cost.
2264 return false;
2265 case scConstant: {
2266 // Only evalulate the costs of constants when optimizing for size.
2268 return false;
2269 const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
2270 Type *Ty = S->getType();
2272 WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
2273 return Cost > Budget;
2274 }
2275 case scTruncate:
2276 case scPtrToInt:
2277 case scZeroExtend:
2278 case scSignExtend: {
2279 Cost +=
2280 costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
2281 return false; // Will answer upon next entry into this function.
2282 }
2283 case scUDivExpr: {
2284 // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2285 // HowManyLessThans produced to compute a precise expression, rather than a
2286 // UDiv from the user's code. If we can't find a UDiv in the code with some
2287 // simple searching, we need to account for it's cost.
2288
2289 // At the beginning of this function we already tried to find existing
2290 // value for plain 'S'. Now try to lookup 'S + 1' since it is common
2291 // pattern involving division. This is just a simple search heuristic.
2293 SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
2294 return false; // Consider it to be free.
2295
2296 Cost +=
2297 costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
2298 return false; // Will answer upon next entry into this function.
2299 }
2300 case scAddExpr:
2301 case scMulExpr:
2302 case scUMaxExpr:
2303 case scSMaxExpr:
2304 case scUMinExpr:
2305 case scSMinExpr:
2306 case scSequentialUMinExpr: {
2307 assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2308 "Nary expr should have more than 1 operand.");
2309 // The simple nary expr will require one less op (or pair of ops)
2310 // than the number of it's terms.
2311 Cost +=
2312 costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
2313 return Cost > Budget;
2314 }
2315 case scAddRecExpr: {
2316 assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2317 "Polynomial should be at least linear");
2318 Cost += costAndCollectOperands<SCEVAddRecExpr>(
2319 WorkItem, TTI, CostKind, Worklist);
2320 return Cost > Budget;
2321 }
2322 }
2323 llvm_unreachable("Unknown SCEV kind!");
2324}
2325
2327 Instruction *IP) {
2328 assert(IP);
2329 switch (Pred->getKind()) {
2331 return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2333 return expandComparePredicate(cast<SCEVComparePredicate>(Pred), IP);
2334 case SCEVPredicate::P_Wrap: {
2335 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2336 return expandWrapPredicate(AddRecPred, IP);
2337 }
2338 }
2339 llvm_unreachable("Unknown SCEV predicate type");
2340}
2341
2343 Instruction *IP) {
2344 Value *Expr0 =
2345 expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP);
2346 Value *Expr1 =
2347 expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP);
2348
2349 Builder.SetInsertPoint(IP);
2350 auto InvPred = ICmpInst::getInversePredicate(Pred->getPredicate());
2351 auto *I = Builder.CreateICmp(InvPred, Expr0, Expr1, "ident.check");
2352 return I;
2353}
2354
2356 Instruction *Loc, bool Signed) {
2357 assert(AR->isAffine() && "Cannot generate RT check for "
2358 "non-affine expression");
2359
2360 // FIXME: It is highly suspicious that we're ignoring the predicates here.
2362 const SCEV *ExitCount =
2364
2365 assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count");
2366
2367 const SCEV *Step = AR->getStepRecurrence(SE);
2368 const SCEV *Start = AR->getStart();
2369
2370 Type *ARTy = AR->getType();
2371 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2372 unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2373
2374 // The expression {Start,+,Step} has nusw/nssw if
2375 // Step < 0, Start - |Step| * Backedge <= Start
2376 // Step >= 0, Start + |Step| * Backedge > Start
2377 // and |Step| * Backedge doesn't unsigned overflow.
2378
2379 IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2380 Builder.SetInsertPoint(Loc);
2381 Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc);
2382
2383 IntegerType *Ty =
2385
2386 Value *StepValue = expandCodeForImpl(Step, Ty, Loc);
2387 Value *NegStepValue =
2388 expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc);
2389 Value *StartValue = expandCodeForImpl(Start, ARTy, Loc);
2390
2391 ConstantInt *Zero =
2392 ConstantInt::get(Loc->getContext(), APInt::getZero(DstBits));
2393
2394 Builder.SetInsertPoint(Loc);
2395 // Compute |Step|
2396 Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2397 Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2398
2399 // Compute |Step| * Backedge
2400 // Compute:
2401 // 1. Start + |Step| * Backedge < Start
2402 // 2. Start - |Step| * Backedge > Start
2403 //
2404 // And select either 1. or 2. depending on whether step is positive or
2405 // negative. If Step is known to be positive or negative, only create
2406 // either 1. or 2.
2407 auto ComputeEndCheck = [&]() -> Value * {
2408 // Checking <u 0 is always false.
2409 if (!Signed && Start->isZero() && SE.isKnownPositive(Step))
2410 return ConstantInt::getFalse(Loc->getContext());
2411
2412 // Get the backedge taken count and truncate or extended to the AR type.
2413 Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2414
2415 Value *MulV, *OfMul;
2416 if (Step->isOne()) {
2417 // Special-case Step of one. Potentially-costly `umul_with_overflow` isn't
2418 // needed, there is never an overflow, so to avoid artificially inflating
2419 // the cost of the check, directly emit the optimized IR.
2420 MulV = TruncTripCount;
2421 OfMul = ConstantInt::getFalse(MulV->getContext());
2422 } else {
2423 auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2424 Intrinsic::umul_with_overflow, Ty);
2425 CallInst *Mul =
2426 Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2427 MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2428 OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2429 }
2430
2431 Value *Add = nullptr, *Sub = nullptr;
2432 bool NeedPosCheck = !SE.isKnownNegative(Step);
2433 bool NeedNegCheck = !SE.isKnownPositive(Step);
2434
2435 if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARTy)) {
2436 StartValue = InsertNoopCastOfTo(
2437 StartValue, Builder.getInt8PtrTy(ARPtrTy->getAddressSpace()));
2438 Value *NegMulV = Builder.CreateNeg(MulV);
2439 if (NeedPosCheck)
2440 Add = Builder.CreateGEP(Builder.getInt8Ty(), StartValue, MulV);
2441 if (NeedNegCheck)
2442 Sub = Builder.CreateGEP(Builder.getInt8Ty(), StartValue, NegMulV);
2443 } else {
2444 if (NeedPosCheck)
2445 Add = Builder.CreateAdd(StartValue, MulV);
2446 if (NeedNegCheck)
2447 Sub = Builder.CreateSub(StartValue, MulV);
2448 }
2449
2450 Value *EndCompareLT = nullptr;
2451 Value *EndCompareGT = nullptr;
2452 Value *EndCheck = nullptr;
2453 if (NeedPosCheck)
2454 EndCheck = EndCompareLT = Builder.CreateICmp(
2456 if (NeedNegCheck)
2457 EndCheck = EndCompareGT = Builder.CreateICmp(
2458 Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2459 if (NeedPosCheck && NeedNegCheck) {
2460 // Select the answer based on the sign of Step.
2461 EndCheck = Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2462 }
2463 return Builder.CreateOr(EndCheck, OfMul);
2464 };
2465 Value *EndCheck = ComputeEndCheck();
2466
2467 // If the backedge taken count type is larger than the AR type,
2468 // check that we don't drop any bits by truncating it. If we are
2469 // dropping bits, then we have overflow (unless the step is zero).
2470 if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2471 auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2472 auto *BackedgeCheck =
2473 Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2474 ConstantInt::get(Loc->getContext(), MaxVal));
2475 BackedgeCheck = Builder.CreateAnd(
2476 BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2477
2478 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2479 }
2480
2481 return EndCheck;
2482}
2483
2485 Instruction *IP) {
2486 const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2487 Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2488
2489 // Add a check for NUSW
2491 NUSWCheck = generateOverflowCheck(A, IP, false);
2492
2493 // Add a check for NSSW
2495 NSSWCheck = generateOverflowCheck(A, IP, true);
2496
2497 if (NUSWCheck && NSSWCheck)
2498 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2499
2500 if (NUSWCheck)
2501 return NUSWCheck;
2502
2503 if (NSSWCheck)
2504 return NSSWCheck;
2505
2506 return ConstantInt::getFalse(IP->getContext());
2507}
2508
2510 Instruction *IP) {
2511 // Loop over all checks in this set.
2512 SmallVector<Value *> Checks;
2513 for (const auto *Pred : Union->getPredicates()) {
2514 Checks.push_back(expandCodeForPredicate(Pred, IP));
2515 Builder.SetInsertPoint(IP);
2516 }
2517
2518 if (Checks.empty())
2519 return ConstantInt::getFalse(IP->getContext());
2520 return Builder.CreateOr(Checks);
2521}
2522
2523Value *SCEVExpander::fixupLCSSAFormFor(Value *V) {
2524 auto *DefI = dyn_cast<Instruction>(V);
2525 if (!PreserveLCSSA || !DefI)
2526 return V;
2527
2528 Instruction *InsertPt = &*Builder.GetInsertPoint();
2529 Loop *DefLoop = SE.LI.getLoopFor(DefI->getParent());
2530 Loop *UseLoop = SE.LI.getLoopFor(InsertPt->getParent());
2531 if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
2532 return V;
2533
2534 // Create a temporary instruction to at the current insertion point, so we
2535 // can hand it off to the helper to create LCSSA PHIs if required for the
2536 // new use.
2537 // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
2538 // would accept a insertion point and return an LCSSA phi for that
2539 // insertion point, so there is no need to insert & remove the temporary
2540 // instruction.
2541 Type *ToTy;
2542 if (DefI->getType()->isIntegerTy())
2543 ToTy = DefI->getType()->getPointerTo();
2544 else
2545 ToTy = Type::getInt32Ty(DefI->getContext());
2546 Instruction *User =
2547 CastInst::CreateBitOrPointerCast(DefI, ToTy, "tmp.lcssa.user", InsertPt);
2548 auto RemoveUserOnExit =
2549 make_scope_exit([User]() { User->eraseFromParent(); });
2550
2552 ToUpdate.push_back(DefI);
2553 SmallVector<PHINode *, 16> PHIsToRemove;
2554 formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove);
2555 for (PHINode *PN : PHIsToRemove) {
2556 if (!PN->use_empty())
2557 continue;
2558 InsertedValues.erase(PN);
2559 InsertedPostIncValues.erase(PN);
2560 PN->eraseFromParent();
2561 }
2562
2563 return User->getOperand(0);
2564}
2565
2566namespace {
2567// Search for a SCEV subexpression that is not safe to expand. Any expression
2568// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2569// UDiv expressions. We don't know if the UDiv is derived from an IR divide
2570// instruction, but the important thing is that we prove the denominator is
2571// nonzero before expansion.
2572//
2573// IVUsers already checks that IV-derived expressions are safe. So this check is
2574// only needed when the expression includes some subexpression that is not IV
2575// derived.
2576//
2577// Currently, we only allow division by a value provably non-zero here.
2578//
2579// We cannot generally expand recurrences unless the step dominates the loop
2580// header. The expander handles the special case of affine recurrences by
2581// scaling the recurrence outside the loop, but this technique isn't generally
2582// applicable. Expanding a nested recurrence outside a loop requires computing
2583// binomial coefficients. This could be done, but the recurrence has to be in a
2584// perfectly reduced form, which can't be guaranteed.
2585struct SCEVFindUnsafe {
2586 ScalarEvolution &SE;
2587 bool CanonicalMode;
2588 bool IsUnsafe = false;
2589
2590 SCEVFindUnsafe(ScalarEvolution &SE, bool CanonicalMode)
2591 : SE(SE), CanonicalMode(CanonicalMode) {}
2592
2593 bool follow(const SCEV *S) {
2594 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2595 if (!SE.isKnownNonZero(D->getRHS())) {
2596 IsUnsafe = true;
2597 return false;
2598 }
2599 }
2600 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2601 const SCEV *Step = AR->getStepRecurrence(SE);
2602 if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2603 IsUnsafe = true;
2604 return false;
2605 }
2606
2607 // For non-affine addrecs or in non-canonical mode we need a preheader
2608 // to insert into.
2609 if (!AR->getLoop()->getLoopPreheader() &&
2610 (!CanonicalMode || !AR->isAffine())) {
2611 IsUnsafe = true;
2612 return false;
2613 }
2614 }
2615 return true;
2616 }
2617 bool isDone() const { return IsUnsafe; }
2618};
2619} // namespace
2620
2622 SCEVFindUnsafe Search(SE, CanonicalMode);
2623 visitAll(S, Search);
2624 return !Search.IsUnsafe;
2625}
2626
2628 const Instruction *InsertionPoint) const {
2629 if (!isSafeToExpand(S))
2630 return false;
2631 // We have to prove that the expanded site of S dominates InsertionPoint.
2632 // This is easy when not in the same block, but hard when S is an instruction
2633 // to be expanded somewhere inside the same block as our insertion point.
2634 // What we really need here is something analogous to an OrderedBasicBlock,
2635 // but for the moment, we paper over the problem by handling two common and
2636 // cheap to check cases.
2637 if (SE.properlyDominates(S, InsertionPoint->getParent()))
2638 return true;
2639 if (SE.dominates(S, InsertionPoint->getParent())) {
2640 if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2641 return true;
2642 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2643 if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
2644 return true;
2645 }
2646 return false;
2647}
2648
2650 // Result is used, nothing to remove.
2651 if (ResultUsed)
2652 return;
2653
2654 auto InsertedInstructions = Expander.getAllInsertedInstructions();
2655#ifndef NDEBUG
2656 SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
2657 InsertedInstructions.end());
2658 (void)InsertedSet;
2659#endif
2660 // Remove sets with value handles.
2661 Expander.clear();
2662
2663 // Remove all inserted instructions.
2664 for (Instruction *I : reverse(InsertedInstructions)) {
2665#ifndef NDEBUG
2666 assert(all_of(I->users(),
2667 [&InsertedSet](Value *U) {
2668 return InsertedSet.contains(cast<Instruction>(U));
2669 }) &&
2670 "removed instruction should only be used by instructions inserted "
2671 "during expansion");
2672#endif
2673 assert(!I->getType()->isVoidTy() &&
2674 "inserted instruction should have non-void types");
2675 I->replaceAllUsesWith(PoisonValue::get(I->getType()));
2676 I->eraseFromParent();
2677 }
2678}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
@ Scaled
assume Assume Builder
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
std::string Name
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
Hexagon Hardware Loops
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
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.
static InstructionCost costAndCollectOperands(const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, SmallVectorImpl< SCEVOperand > &Worklist)
static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
static void SimplifyAddOperands(SmallVectorImpl< const SCEV * > &Ops, Type *Ty, ScalarEvolution &SE)
SimplifyAddOperands - Sort and simplify a list of add operands.
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...
#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
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.
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.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallSet class.
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:372
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:245
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
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:127
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.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
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.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:675
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1054
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:745
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:998
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1973
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
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:887
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:842
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:681
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:507
Type * getIndexType(Type *PtrTy) const
Returns the type of a GEP index.
Definition: DataLayout.cpp:876
bool isNonIntegralPointerType(PointerType *PT) const
Definition: DataLayout.h:401
A debug info location.
Definition: DebugLoc.h:33
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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
const BasicBlock & getEntryBlock() const
Definition: Function.h:735
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:641
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1912
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1631
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1926
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2397
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:965
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1126
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:175
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1920
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2416
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:174
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1916
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2278
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:145
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1259
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2008
PointerType * getInt8PtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer to an 8-bit integer value.
Definition: IRBuilder.h:560
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1390
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1242
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1412
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2045
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2293
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
Definition: IRBuilder.h:1781
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2232
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
Definition: IRBuilder.h:502
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1276
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2550
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:70
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:74
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
Class to represent integer types.
Definition: DerivedTypes.h:40
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:313
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
BlockT * getHeader() const
Definition: LoopInfo.h:105
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1140
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
Definition: LoopInfo.h:1166
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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
ICmpInst::Predicate getPredicate() const
Returns the comparison predicate underlying the intrinsic.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
bool isComplete() const
If the PHI node is complete which means all of its parent's predecessors have incoming value in this ...
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...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Class to represent pointers.
Definition: DerivedTypes.h:632
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEV * getOperand() const
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
const SCEV * getLHS() const
Returns the left hand side of the predicate.
This class represents a constant integer value.
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
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...
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...
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
Value * getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
void setInsertPoint(Instruction *IP)
Set the current insertion point.
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
ArrayRef< const SCEV * > operands() const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
This class represents a cast from a pointer to a pointer-sized integer value.
This class represents a signed maximum selection.
This class represents a signed minimum selection.
This class represents a sequential/in-order unsigned minimum selection.
This class represents a sign extension of a small integer value to a larger integer value.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned maximum selection.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
SCEVTypes getSCEVType() const
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
The main scalar evolution driver.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
Return an expression for the alloc size of AllocTy that is type IntTy.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
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...
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
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.
const SCEV * getUnknown(Value *V)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
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.
LLVMContext & getContext() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
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:177
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:625
uint64_t getSizeInBytes() const
Definition: DataLayout.h:632
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:655
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
Class to represent struct types.
Definition: DerivedTypes.h:213
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
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...
TargetCostKind
The kind of cost model.
@ TCK_RecipThroughput
Reciprocal throughput.
@ TCK_CodeSize
Instruction code size.
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.
bool isTruncateFree(Type *Ty1, Type *Ty2) const
Return true if it's free to truncate a value of type Ty1 to type Ty2.
@ None
The cast is not used with a load/store of any kind.
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:258
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:249
static IntegerType * getInt1Ty(LLVMContext &C)
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:295
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:222
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
iterator_range< value_op_iterator > operand_values()
Definition: User.h:266
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
iterator_range< user_iterator > users()
Definition: Value.h:421
bool use_empty() const
Definition: Value.h:344
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
constexpr ScalarTy getFixedValue() const
Definition: TypeSize.h:182
self_iterator getIterator()
Definition: ilist_node.h:82
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
#define UINT64_MAX
Definition: DataTypes.h:77
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1502
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:168
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:386
void stable_sort(R &&Range)
Definition: STLExtras.h:1948
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:1735
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
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:1742
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
bool programUndefinedIfPoison(const Instruction *Inst)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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
cl::opt< unsigned > SCEVCheapExpansionBudget
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
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:2264
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
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
@ Mul
Product of integers.
@ Add
Sum of integers.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
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:1903
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:1869
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
const SCEV * S
The SCEV operand to be costed.
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
int OperandIdx
The use index of an expanded instruction.