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