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