1//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===// 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 7//===----------------------------------------------------------------------===// 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 13//===----------------------------------------------------------------------===// 31#if LLVM_ENABLE_ABI_BREAKING_CHECKS 32#define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X) 34#define SCEV_DEBUG_WITH_TYPE(TYPE, X) 41cl::desc(
"When performing SCEV expansion only if it is cheap to do, this " 42"controls the budget that is considered cheap (default = 4)"));
44using namespacePatternMatch;
54if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I)) {
55NUW = OBO->hasNoUnsignedWrap();
56NSW = OBO->hasNoSignedWrap();
58if (
auto *PEO = dyn_cast<PossiblyExactOperator>(
I))
59Exact = PEO->isExact();
60if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
62if (
auto *PNI = dyn_cast<PossiblyNonNegInst>(
I))
63NNeg = PNI->hasNonNeg();
64if (
auto *TI = dyn_cast<TruncInst>(
I)) {
65NUW = TI->hasNoUnsignedWrap();
66NSW = TI->hasNoSignedWrap();
68if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
70if (
auto *ICmp = dyn_cast<ICmpInst>(
I))
75if (isa<OverflowingBinaryOperator>(
I)) {
76I->setHasNoUnsignedWrap(
NUW);
77I->setHasNoSignedWrap(
NSW);
79if (isa<PossiblyExactOperator>(
I))
81if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
83if (
auto *PNI = dyn_cast<PossiblyNonNegInst>(
I))
85if (isa<TruncInst>(
I)) {
86I->setHasNoUnsignedWrap(
NUW);
87I->setHasNoSignedWrap(
NSW);
89if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
91if (
auto *ICmp = dyn_cast<ICmpInst>(
I))
95/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP, 96/// reusing an existing cast if a suitable one (= dominating IP) exists, or 97/// creating a new one. 101// This function must be called with the builder having a valid insertion 102// point. It doesn't need to be the actual IP where the uses of the returned 103// cast will be added, but it must dominate such IP. 104// We use this precondition to produce a cast that will dominate all its 105// uses. In particular, this is crucial for the case where the builder's 106// insertion point *is* the point where we were asked to put the cast. 107// Since we don't know the builder's insertion point is actually 108// where the uses will be added (only that it dominates it), we are 109// not allowed to move it. 114// Check to see if there is already a cast! 115for (
User *U : V->users()) {
116if (U->getType() != Ty)
118CastInst *CI = dyn_cast<CastInst>(U);
122// Found a suitable cast that is at IP or comes before IP. Use it. Note that 123// the cast must also properly dominate the Builder's insertion point. 124if (IP->getParent() == CI->
getParent() && &*BIP != CI &&
133 SCEVInsertPointGuard Guard(Builder,
this);
138// We assert at the end of the function since IP might point to an 139// instruction with different dominance properties than a cast 140// (an invoke for example) and not dominate BIP (but the cast does). 141assert(!isa<Instruction>(Ret) ||
142 SE.DT.
dominates(cast<Instruction>(Ret), &*BIP));
151if (
auto *
II = dyn_cast<InvokeInst>(
I))
152 IP =
II->getNormalDest()->begin();
154while (isa<PHINode>(IP))
157if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
159 }
elseif (isa<CatchSwitchInst>(IP)) {
160 IP = MustDominate->
getParent()->getFirstInsertionPt();
162assert(!IP->isEHPad() &&
"unexpected eh pad!");
165// Adjust insert point to be after instructions inserted by the expander, so 166// we can re-use already inserted instructions. Avoid skipping past the 167// original \p MustDominate, in case it is an inserted instruction. 175SCEVExpander::GetOptimalInsertionPointForCastOf(
Value *V)
const{
176// Cast the argument at the beginning of the entry block, after 177// any bitcasts of other arguments. 178if (
Argument *
A = dyn_cast<Argument>(V)) {
180while ((isa<BitCastInst>(IP) &&
181 isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
182 cast<BitCastInst>(IP)->getOperand(0) !=
A) ||
183 isa<DbgInfoIntrinsic>(IP))
188// Cast the instruction immediately after the instruction. 192// Otherwise, this must be some kind of a constant, 193// so let's plop this cast into the function's entry block. 195"Expected the cast argument to be a global/constant");
202/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 203/// which must be possible with a noop cast, doing what we can to share 207assert((
Op == Instruction::BitCast ||
208Op == Instruction::PtrToInt ||
209Op == Instruction::IntToPtr) &&
210"InsertNoopCastOfTo cannot perform non-noop casts!");
212"InsertNoopCastOfTo cannot change sizes!");
214// inttoptr only works for integral pointers. For non-integral pointers, we 215// can create a GEP on null with the integral value as index. Note that 216// it is safe to use GEP of null instead of inttoptr here, because only 217// expressions already based on a GEP of null should be converted to pointers 219if (
Op == Instruction::IntToPtr) {
220auto *PtrTy = cast<PointerType>(Ty);
224// Short-circuit unnecessary bitcasts. 225if (
Op == Instruction::BitCast) {
226if (
V->getType() == Ty)
228if (
CastInst *CI = dyn_cast<CastInst>(V)) {
233// Short-circuit unnecessary inttoptr<->ptrtoint casts. 234if ((
Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) &&
236if (
CastInst *CI = dyn_cast<CastInst>(V))
237if ((CI->
getOpcode() == Instruction::PtrToInt ||
238 CI->
getOpcode() == Instruction::IntToPtr) &&
243if ((
CE->getOpcode() == Instruction::PtrToInt ||
244CE->getOpcode() == Instruction::IntToPtr) &&
247returnCE->getOperand(0);
250// Fold a cast of a constant. 254// Try to reuse existing cast, or insert one. 255return ReuseOrCreateCast(V, Ty,
Op, GetOptimalInsertionPointForCastOf(V));
258/// InsertBinop - Insert the specified binary operator, doing a small amount 259/// of work to avoid inserting an obviously redundant operation, and hoisting 260/// to an outer loop when the opportunity is there and it is safe. 264// Fold a binop with constant operands. 265if (
Constant *CLHS = dyn_cast<Constant>(LHS))
266if (
Constant *CRHS = dyn_cast<Constant>(RHS))
270// Do a quick scan to see if we have this binop nearby. If so, reuse it. 271unsigned ScanLimit = 6;
273// Scanning starts from the last instruction before the insertion point. 275if (IP != BlockBegin) {
277for (; ScanLimit; --IP, --ScanLimit) {
278// Don't count dbg.value against the ScanLimit, to avoid perturbing the 280if (isa<DbgInfoIntrinsic>(IP))
284// Ensure that no-wrap flags match. 285if (isa<OverflowingBinaryOperator>(
I)) {
291// Conservatively, do not use any instruction which has any of exact 293if (isa<PossiblyExactOperator>(
I) &&
I->isExact())
297if (IP->getOpcode() == (
unsigned)Opcode && IP->getOperand(0) ==
LHS &&
298 IP->getOperand(1) ==
RHS && !canGenerateIncompatiblePoison(&*IP))
300if (IP == BlockBegin)
break;
304// Save the original insertion point so we can restore it when we're done. 306 SCEVInsertPointGuard Guard(Builder,
this);
309// Move the insertion point out of as many loops as we can. 311if (!
L->isLoopInvariant(LHS) || !
L->isLoopInvariant(RHS))
break;
315// Ok, move up a level. 320// If we haven't found this binop, insert it. 321// TODO: Use the Builder, which will make CreateBinOp below fold with 322// InstSimplifyFolder. 333/// expandAddToGEP - Expand an addition expression with a pointer type into 334/// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps 335/// BasicAliasAnalysis and other passes analyze the result. See the rules 336/// for getelementptr vs. inttoptr in 337/// http://llvm.org/docs/LangRef.html#pointeraliasing 340/// Design note: The correctness of using getelementptr here depends on 341/// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as 342/// they may introduce pointer arithmetic which may not be safely converted 343/// into getelementptr. 345/// Design note: It might seem desirable for this function to be more 346/// loop-aware. If some of the indices are loop-invariant while others 347/// aren't, it might seem desirable to emit multiple GEPs, keeping the 348/// loop-invariant portions of the overall computation outside the loop. 349/// However, there are a few reasons this is not done here. Hoisting simple 350/// arithmetic is a low-level optimization that often isn't very 351/// important until late in the optimization process. In fact, passes 352/// like InstructionCombining will combine GEPs, even if it means 353/// pushing loop-invariant computation down into loops, so even if the 354/// GEPs were split here, the work would quickly be undone. The 355/// LoopStrengthReduction pass, which is usually run quite late (and 356/// after the last InstructionCombining pass), takes care of hoisting 357/// loop-invariant portions of expressions, after considering what 358/// can be folded using target addressing modes. 362assert(!isa<Instruction>(V) ||
369// Fold a GEP with constant operands. 370if (
Constant *CLHS = dyn_cast<Constant>(V))
374// Do a quick scan to see if we have this GEP nearby. If so, reuse it. 375unsigned ScanLimit = 6;
377// Scanning starts from the last instruction before the insertion point. 379if (IP != BlockBegin) {
381for (; ScanLimit; --IP, --ScanLimit) {
382// Don't count dbg.value against the ScanLimit, to avoid perturbing the 384if (isa<DbgInfoIntrinsic>(IP))
386if (
auto *
GEP = dyn_cast<GetElementPtrInst>(IP)) {
387if (
GEP->getPointerOperand() == V &&
389GEP->getOperand(1) ==
Idx) {
391GEP->setNoWrapFlags(
GEP->getNoWrapFlags() & NW);
395if (IP == BlockBegin)
break;
399// Save the original insertion point so we can restore it when we're done. 400 SCEVInsertPointGuard Guard(Builder,
this);
402// Move the insertion point out of as many loops as we can. 404if (!
L->isLoopInvariant(V) || !
L->isLoopInvariant(
Idx))
break;
408// Ok, move up a level. 416/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for 417/// SCEV expansion. If they are nested, this is the most nested. If they are 418/// neighboring, pick the later. 423if (
A->contains(
B))
returnB;
424if (
B->contains(
A))
returnA;
427returnA;
// Arbitrarily break the tie. 430/// getRelevantLoop - Get the most relevant loop associated with the given 431/// expression, according to PickMostRelevantLoop. 432constLoop *SCEVExpander::getRelevantLoop(
constSCEV *S) {
433// Test whether we've already computed the most relevant loop for this SCEV. 434auto Pair = RelevantLoops.insert(std::make_pair(S,
nullptr));
436return Pair.first->second;
441returnnullptr;
// A constant has no relevant loops. 455constLoop *
L =
nullptr;
460return RelevantLoops[S] =
L;
464if (
constInstruction *
I = dyn_cast<Instruction>(
U->getValue()))
465return Pair.first->second = SE.LI.
getLoopFor(
I->getParent());
466// A non-instruction has no relevant loops. 477/// LoopCompare - Compare loops by PickMostRelevantLoop. 483bool operator()(std::pair<const Loop *, const SCEV *>
LHS,
484 std::pair<const Loop *, const SCEV *>
RHS)
const{
485// Keep pointer operands sorted at the end. 490// Compare loops with PickMostRelevantLoop. 494// If one operand is a non-constant negative and the other is not, 495// put the non-constant negative on the right so that a sub can 496// be used instead of a negate and add. 497if (
LHS.second->isNonConstantNegative()) {
498if (!
RHS.second->isNonConstantNegative())
500 }
elseif (
RHS.second->isNonConstantNegative())
503// Otherwise they are equivalent according to this comparison. 511// Recognize the canonical representation of an unsimplifed urem. 512constSCEV *URemLHS =
nullptr;
513constSCEV *URemRHS =
nullptr;
514if (SE.matchURem(S, URemLHS, URemRHS)) {
518/*IsSafeToHoist*/false);
521// Collect all the add operands in a loop, along with their associated loops. 522// Iterate in reverse so that constants are emitted last, all else equal, and 523// so that pointer operands are inserted first, which the code below relies on 524// to form more involved GEPs. 527 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
529// Sort by loop. Use a stable sort so that constants follow non-constants and 530// pointer operands precede non-pointer operands. 533// Emit instructions to add all the operands. Hoist as much as possible 534// out of loops, and form meaningful getelementptrs where possible. 536for (
autoI = OpsAndLoops.
begin(), E = OpsAndLoops.
end();
I != E;) {
537constLoop *CurLoop =
I->first;
540// This is the first operand. Just expand it. 546assert(!
Op->getType()->isPointerTy() &&
"Only first op can be pointer");
547if (isa<PointerType>(Sum->
getType())) {
548// The running sum expression is a pointer. Try to form a getelementptr 549// at this level with that as the base. 551for (;
I != E &&
I->first == CurLoop; ++
I) {
552// If the operand is SCEVUnknown and not instructions, peek through 553// it, to enable more of it to be folded into the GEP. 556if (!isa<Instruction>(
U->getValue()))
561 }
elseif (
Op->isNonConstantNegative()) {
562// Instead of doing a negate and add, just do a subtract. 565/*IsSafeToHoist*/true);
570// Canonicalize a constant to the RHS. 571if (isa<Constant>(Sum))
574/*IsSafeToHoist*/true);
585// Collect all the mul operands in a loop, along with their associated loops. 586// Iterate in reverse so that constants are emitted last, all else equal. 589 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
591// Sort by loop. Use a stable sort so that constants follow non-constants. 594// Emit instructions to mul all the operands. Hoist as much as possible 597autoI = OpsAndLoops.
begin();
599// Expand the calculation of X pow N in the following manner: 600// Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then: 601// X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK). 602constauto ExpandOpBinPowN = [
this, &
I, &OpsAndLoops]() {
604// Calculate how many times the same operand from the same loop is included 608// No one sane will ever try to calculate such huge exponents, but if we 609// need this, we stop on UINT64_MAX / 2 because we need to exit the loop 610// below when the power of 2 exceeds our Exponent, and we want it to be 611// 1u << 31 at most to not deal with unsigned overflow. 612while (E != OpsAndLoops.
end() && *
I == *E &&
Exponent != MaxExponent) {
616assert(
Exponent > 0 &&
"Trying to calculate a zeroth exponent of operand?");
618// Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them 619// that are needed into the result. 626/*IsSafeToHoist*/true);
630/*IsSafeToHoist*/true)
635assert(Result &&
"Nothing was expanded?");
639while (
I != OpsAndLoops.
end()) {
641// This is the first operand. Just expand it. 642 Prod = ExpandOpBinPowN();
643 }
elseif (
I->second->isAllOnesValue()) {
644// Instead of doing a multiply by negative one, just do a negate. 650Value *
W = ExpandOpBinPowN();
651// Canonicalize a constant to the RHS. 652if (isa<Constant>(Prod))
std::swap(Prod, W);
655// Canonicalize Prod*(1<<C) to Prod<<C. 658// clear nsw flag if shl will produce poison value. 659if (
RHS->logBase2() ==
RHS->getBitWidth() - 1)
661 Prod = InsertBinop(Instruction::Shl, Prod,
662 ConstantInt::get(Ty,
RHS->logBase2()), NWFlags,
663/*IsSafeToHoist*/true);
665 Prod = InsertBinop(Instruction::Mul, Prod, W, S->
getNoWrapFlags(),
666/*IsSafeToHoist*/true);
679return InsertBinop(Instruction::LShr, LHS,
680 ConstantInt::get(
SC->getType(),
RHS.logBase2()),
687bool GuaranteedNotPoison =
688 ScalarEvolution::isGuaranteedNotToBePoison(RHSExpr);
689if (!GuaranteedNotPoison)
692// We need an umax if either RHSExpr is not known to be zero, or if it is 693// not guaranteed to be non-poison. In the later case, the frozen poison may 697 {RHS, ConstantInt::get(RHS->getType(), 1)});
703/// Determine if this is a well-behaved chain of instructions leading back to 704/// the PHI. If so, it may be reused by expanded expressions. 708 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
710// If any of the operands don't dominate the insert position, bail. 711// Addrec operands are always loop-invariant, so this can only happen 712// if there are instructions which haven't been hoisted. 713if (L == IVIncInsertLoop) {
716if (!SE.DT.
dominates(OInst, IVIncInsertPos))
719// Advance to the next instruction. 720 IncV = dyn_cast<Instruction>(IncV->
getOperand(0));
730return isNormalAddRecExprPHI(PN, IncV, L);
733/// getIVIncOperand returns an induction variable increment's induction 736/// If allowScale is set, any type of GEP is allowed as long as the nonIV 737/// operands dominate InsertPos. 739/// If allowScale is not set, ensure that a GEP increment conforms to one of the 740/// simple patterns generated by getAddRecExprPHILiterally and 741/// expandAddtoGEP. If the pattern isn't recognized, return NULL. 745if (IncV == InsertPos)
751// Check for a simple Add/Sub or GEP of a loop invariant step. 752case Instruction::Add:
753case Instruction::Sub: {
755if (!OInst || SE.DT.
dominates(OInst, InsertPos))
756return dyn_cast<Instruction>(IncV->
getOperand(0));
759case Instruction::BitCast:
760return dyn_cast<Instruction>(IncV->
getOperand(0));
761case Instruction::GetElementPtr:
765if (
Instruction *OInst = dyn_cast<Instruction>(U)) {
770// allow any kind of GEP as long as it can be hoisted. 773// GEPs produced by SCEVExpander use i8 element type. 774if (!cast<GEPOperator>(IncV)->getSourceElementType()->isIntegerTy(8))
778return dyn_cast<Instruction>(IncV->
getOperand(0));
782/// If the insert point of the current builder or any of the builders on the 783/// stack of saved builders has 'I' as its insert point, update it to point to 784/// the instruction after 'I'. This is intended to be used when the instruction 785/// 'I' is being moved. If this fixup is not done and 'I' is moved to a 786/// different block, the inconsistent insert point (with a mismatched 787/// Instruction and Block) can lead to an instruction being inserted in a block 788/// other than its parent. 794for (
auto *InsertPtGuard : InsertPointGuards)
795if (InsertPtGuard->GetInsertPoint() == It)
796 InsertPtGuard->SetInsertPoint(NewInsertPt);
799/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make 800/// it available to other uses in this loop. Recursively hoist any operands, 801/// until we reach a value that dominates InsertPos. 803bool RecomputePoisonFlags) {
805// Drop flags that are potentially inferred from old context and infer flags 808I->dropPoisonGeneratingFlags();
809if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I))
811auto *BO = cast<BinaryOperator>(
I);
820if (RecomputePoisonFlags)
821 FixupPoisonFlags(IncV);
825// InsertPos must itself dominate IncV so that IncV's new position satisfies 826// its existing users. 827if (isa<PHINode>(InsertPos) ||
834// Check that the chain of IV operands leading back to Phi can be hoisted. 840// IncV is safe to hoist. 847 fixupInsertPoints(
I);
849if (RecomputePoisonFlags)
864/// Determine if this cyclic phi is in a form that would have been generated by 865/// LSR. We don't care if the phi was actually expanded in this pass, as long 866/// as it is in a low-cost form, for example, no implied multiplication. This 867/// should match any patterns generated by getAddRecExprPHILiterally and 872 (IVOper =
getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
873/*allowScale=*/false));) {
880/// expandIVInc - Expand an IV increment at Builder's current InsertPos. 881/// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may 882/// need to materialize IV increments elsewhere to handle difficult situations. 886// If the PHI is a pointer, use a GEP, otherwise use an add or sub. 888// TODO: Change name to IVName.iv.next. 898/// Check whether we can cheaply express the requested SCEV in terms of 899/// the available PHI SCEV by truncation and/or inversion of the step. 904// We can't transform to match a pointer PHI. 905Type *PhiTy = Phi->getType();
913// Try truncate it if necessary. 918// Check whether truncation will help. 919if (Phi == Requested) {
924// Check whether inverting will help: {R,+,-1} == R - {0,+,1}. 934if (!isa<IntegerType>(AR->
getType()))
942constSCEV *ExtendAfterOp =
944return ExtendAfterOp == OpAfterExtend;
948if (!isa<IntegerType>(AR->
getType()))
956constSCEV *ExtendAfterOp =
958return ExtendAfterOp == OpAfterExtend;
961/// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand 962/// the base addrec, which is the addrec without any non-loop-dominating 963/// values, and return the PHI. 965SCEVExpander::getAddRecExprPHILiterally(
constSCEVAddRecExpr *Normalized,
968assert((!IVIncInsertLoop || IVIncInsertPos) &&
969"Uninitialized insert position");
971// Reuse a previously-inserted PHI, if present. 974PHINode *AddRecPhiMatch =
nullptr;
979// Only try partially matching scevs that need truncation and/or 980// step-inversion if we know this loop is outside the current loop. 981bool TryNonMatchingSCEV =
985for (
PHINode &PN :
L->getHeader()->phis()) {
989// We should not look for a incomplete PHI. Getting SCEV for a incomplete 990// PHI has no meaning at all. 993 DebugType,
dbgs() <<
"One incomplete PHI is found: " << PN <<
"\n");
1001bool IsMatchingSCEV = PhiSCEV == Normalized;
1002// We only handle truncation and inversion of phi recurrences for the 1003// expanded expression if the expanded expression's loop dominates the 1004// loop we insert to. Check now, so we can bail out early. 1005if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1008// TODO: this possibly can be reworked to avoid this cast at all. 1014// Check whether we can reuse this PHI node. 1016if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1019if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1023// Stop if we have found an exact match SCEV. 1024if (IsMatchingSCEV) {
1028 AddRecPhiMatch = &PN;
1032// Try whether the phi can be translated into the requested form 1033// (truncated and/or offset by a constant). 1034if ((!TruncTy || InvertStep) &&
1036// Record the phi node. But don't stop we might find an exact match 1038 AddRecPhiMatch = &PN;
1040 TruncTy = Normalized->
getType();
1044if (AddRecPhiMatch) {
1045// Ok, the add recurrence looks usable. 1046// Remember this PHI, even in post-inc mode. 1047 InsertedValues.insert(AddRecPhiMatch);
1048// Remember the increment. 1049 rememberInstruction(IncV);
1050// Those values were not actually inserted but re-used. 1051 ReusedValues.
insert(AddRecPhiMatch);
1052 ReusedValues.
insert(IncV);
1053return AddRecPhiMatch;
1057// Save the original insertion point so we can restore it when we're done. 1058 SCEVInsertPointGuard Guard(Builder,
this);
1060// Another AddRec may need to be recursively expanded below. For example, if 1061// this AddRec is quadratic, the StepV may itself be an AddRec in this 1062// loop. Remove this loop from the PostIncLoops set before expanding such 1063// AddRecs. Otherwise, we cannot find a valid position for the step 1064// (i.e. StepV can never dominate its loop header). Ideally, we could do 1065// SavedIncLoops.swap(PostIncLoops), but we generally have a single element, 1066// so it's not worth implementing SmallPtrSet::swap. 1068 PostIncLoops.
clear();
1070// Expand code for the start value into the loop preheader. 1071assert(
L->getLoopPreheader() &&
1072"Can't expand add recurrences without a loop preheader!");
1074 expand(Normalized->
getStart(),
L->getLoopPreheader()->getTerminator());
1076// StartV must have been be inserted into L's preheader to dominate the new 1078assert(!isa<Instruction>(StartV) ||
1082// Expand code for the step value. Do this before creating the PHI so that PHI 1083// reuse code doesn't see an incomplete PHI. 1086// If the stride is negative, insert a sub instead of an add for the increment 1087// (unless it's a constant, because subtracts of constants are canonicalized 1092// Expand the step somewhere that dominates the loop header. 1093Value *StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1095// The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if 1096// we actually do emit an addition. It does not apply if we emit a 1098bool IncrementIsNUW = !useSubtract &&
IsIncrementNUW(SE, Normalized);
1099bool IncrementIsNSW = !useSubtract &&
IsIncrementNSW(SE, Normalized);
1107// Create the step instructions and populate the PHI. 1109// Add a start value. 1110if (!
L->contains(Pred)) {
1115// Create a step value and add it to the PHI. 1116// If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the 1117// instructions at IVIncInsertPos. 1119 IVIncInsertPos : Pred->getTerminator();
1121Value *IncV = expandIVInc(PN, StepV, L, useSubtract);
1123if (isa<OverflowingBinaryOperator>(IncV)) {
1125 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1127 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1132// After expanding subexpressions, restore the PostIncLoops set so the caller 1133// can ensure that IVIncrement dominates the current uses. 1134 PostIncLoops = SavedPostIncLoops;
1136// Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most 1137// effective when we are able to use an IV inserted here, so record it. 1138 InsertedValues.insert(PN);
1139 InsertedIVs.push_back(PN);
1146// Determine a normalized form of this expression, which is the expression 1147// before any post-inc adjustment is made. 1149if (PostIncLoops.
count(L)) {
1152 Normalized = cast<SCEVAddRecExpr>(
1156 [[maybe_unused]]
constSCEV *Start = Normalized->
getStart();
1159"Start does not properly dominate loop header");
1160assert(SE.
dominates(Step,
L->getHeader()) &&
"Step not dominate loop header");
1162// In some cases, we decide to reuse an existing phi node but need to truncate 1163// it and/or invert the step. 1164Type *TruncTy =
nullptr;
1165bool InvertStep =
false;
1166PHINode *PN = getAddRecExprPHILiterally(Normalized, L, TruncTy, InvertStep);
1168// Accommodate post-inc mode, if necessary. 1170if (!PostIncLoops.
count(L))
1173// In PostInc mode, use the post-incremented value. 1175assert(LatchBlock &&
"PostInc mode requires a unique loop latch!");
1178// We might be introducing a new use of the post-inc IV that is not poison 1179// safe, in which case we should drop poison generating flags. Only keep 1180// those flags for which SCEV has proven that they always hold. 1181if (isa<OverflowingBinaryOperator>(Result)) {
1182auto *
I = cast<Instruction>(Result);
1184I->setHasNoUnsignedWrap(
false);
1186I->setHasNoSignedWrap(
false);
1189// For an expansion to use the postinc form, the client must call 1190// expandCodeFor with an InsertPoint that is either outside the PostIncLoop 1191// or dominated by IVIncInsertPos. 1192if (isa<Instruction>(Result) &&
1193 !SE.DT.
dominates(cast<Instruction>(Result),
1195// The induction variable's postinc expansion does not dominate this use. 1196// IVUsers tries to prevent this case, so it is rare. However, it can 1197// happen when an IVUser outside the loop is not dominated by the latch 1198// block. Adjusting IVIncInsertPos before expansion begins cannot handle 1199// all cases. Consider a phi outside whose operand is replaced during 1200// expansion with the value of the postinc user. Without fundamentally 1201// changing the way postinc users are tracked, the only remedy is 1202// inserting an extra IV increment. StepV might fold into PostLoopOffset, 1203// but hopefully expandCodeFor handles that. 1210// Expand the step somewhere that dominates the loop header. 1211 SCEVInsertPointGuard Guard(Builder,
this);
1212 StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1214Result = expandIVInc(PN, StepV, L, useSubtract);
1218// We have decided to reuse an induction variable of a dominating loop. Apply 1219// truncation and/or inversion of the step. 1221// Truncate the result. 1222if (TruncTy !=
Result->getType())
1225// Invert the result. 1234// In canonical mode we compute the addrec as an expression of a canonical IV 1235// using evaluateAtIteration and expand the resulting SCEV expression. This 1236// way we avoid introducing new IVs to carry on the computation of the addrec 1237// throughout the loop. 1239// For nested addrecs evaluateAtIteration might need a canonical IV of a 1240// type wider than the addrec itself. Emitting a canonical IV of the 1241// proper type might produce non-legal types, for example expanding an i64 1242// {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall 1243// back to non-canonical mode for nested addrecs. 1245return expandAddRecExprLiterally(S);
1250// First check for an existing canonical IV in a suitable type. 1252if (
PHINode *PN =
L->getCanonicalInductionVariable())
1256// Rewrite an AddRec in terms of the canonical induction variable, if 1257// its type is more narrow. 1272// {X,+,F} --> X + {0,+,F} 1274if (isa<PointerType>(S->
getType())) {
1285// Just do a normal add. Pre-expand the operands to suppress folding. 1287// The LHS and RHS values are factored out of the expand call to make the 1288// output independent of the argument evaluation order. 1291return expand(SE.
getAddExpr(AddExprLHS, AddExprRHS));
1294// If we don't yet have a canonical IV, create one. 1296// Create and insert the PHI node for the induction variable in the 1302 rememberInstruction(CanonicalIV);
1305Constant *One = ConstantInt::get(Ty, 1);
1308if (!PredSeen.
insert(HP).second) {
1309// There must be an incoming value for each predecessor, even the 1315if (
L->contains(HP)) {
1316// Insert a unit add instruction right before the terminator 1317// corresponding to the back-edge. 1322 rememberInstruction(
Add);
1330// {0,+,1} --> Insert a canonical induction variable into the loop! 1333"IVs with types different from the canonical IV should " 1334"already have been handled!");
1338// {0,+,F} --> {0,+,1} * F 1340// If this is a simple linear addrec, emit it now as a special case. 1341if (S->
isAffine())
// {0,+,F} --> i*F 1349// If this is a chain of recurrences, turn it into a closed form, using the 1350// folders, then expandCodeFor the closed form. This allows the folders to 1351// simplify the expression without having to build a bunch of special code 1353constSCEV *IH = SE.
getUnknown(CanonicalIV);
// Get I as a "symbolic" SCEV. 1355// Promote S up to the canonical IV type, if the cast is foldable. 1358if (isa<SCEVAddRecExpr>(Ext))
1361constSCEV *
V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1363// Truncate the result down to the original type, if needed. 1370return ReuseOrCreateCast(V, S->
getType(), CastInst::PtrToInt,
1371 GetOptimalInsertionPointForCastOf(V));
1393bool PrevSafeMode = SafeUDivMode;
1394 SafeUDivMode |= IsSequential;
1400 SafeUDivMode = (IsSequential && i != 0) || PrevSafeMode;
1402if (IsSequential && i != 0)
1407/*FMFSource=*/nullptr,
Name);
1415 SafeUDivMode = PrevSafeMode;
1420return expandMinMaxExpr(S, Intrinsic::smax,
"smax");
1424return expandMinMaxExpr(S, Intrinsic::umax,
"umax");
1428return expandMinMaxExpr(S, Intrinsic::smin,
"smin");
1432return expandMinMaxExpr(S, Intrinsic::umin,
"umin");
1436return expandMinMaxExpr(S, Intrinsic::umin,
"umin",
/*IsSequential*/true);
1451// Expand the code for this SCEV. 1452Value *V = expand(SH);
1456"non-trivial casts should be done with the SCEVs directly!");
1457 V = InsertNoopCastOfTo(V, Ty);
1462Value *SCEVExpander::FindValueInExprValueMap(
1465// If the expansion is not in CanonicalMode, and the SCEV contains any 1466// sub scAddRecExpr type SCEV, it is required to expand the SCEV literally. 1470// If S is a constant or unknown, it may be worse to reuse an existing Value. 1471if (isa<SCEVConstant>(S) || isa<SCEVUnknown>(S))
1474for (
Value *V : SE.getSCEVValues(S)) {
1479// Choose a Value from the set which dominates the InsertPt. 1480// InsertPt should be inside the Value's parent loop so as not to break 1488// Make sure reusing the instruction is poison-safe. 1491 DropPoisonGeneratingInsts.
clear();
1496// The expansion of SCEV will either reuse a previous Value in ExprValueMap, 1497// or expand the SCEV literally. Specifically, if the expansion is in LSRMode, 1498// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded 1499// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise, 1500// the expansion will try to reuse Value from ExprValueMap, and only when it 1501// fails, expand the SCEV literally. 1502Value *SCEVExpander::expand(
constSCEV *S) {
1503// Compute an insertion point for this SCEV object. Hoist the instructions 1504// as far out in the loop nest as possible. 1507// We can move insertion point only if there is no div or rem operations 1508// otherwise we are risky to move it over the check for zero denominator. 1509auto SafeToHoist = [](
constSCEV *S) {
1511if (
constauto *
D = dyn_cast<SCEVUDivExpr>(S)) {
1512if (
constauto *SC = dyn_cast<SCEVConstant>(
D->getRHS()))
1513// Division by non-zero constants can be hoisted. 1514returnSC->getValue()->isZero();
1515// All other divisions should not be moved as they may be 1516// divisions by zero and should be kept within the 1517// conditions of the surrounding loops that guard their 1518// execution (see PR35406). 1524if (SafeToHoist(S)) {
1526 L =
L->getParentLoop()) {
1529if (
BasicBlock *Preheader =
L->getLoopPreheader()) {
1532// LSR sets the insertion point for AddRec start/step values to the 1533// block start to simplify value reuse, even though it's an invalid 1534// position. SCEVExpander must correct for this in all cases. 1535 InsertPt =
L->getHeader()->getFirstInsertionPt();
1538// If the SCEV is computable at this level, insert it into the header 1539// after the PHIs (and after any other instructions that we've inserted 1540// there) so that it is guaranteed to dominate any user inside the loop. 1542 InsertPt =
L->getHeader()->getFirstInsertionPt();
1546 isa<DbgInfoIntrinsic>(&*InsertPt))) {
1547 InsertPt = std::next(InsertPt);
1554// Check to see if we already expanded this here. 1555autoI = InsertedExpressions.find(std::make_pair(S, &*InsertPt));
1556if (
I != InsertedExpressions.end())
1559 SCEVInsertPointGuard Guard(Builder,
this);
1562// Expand the expression into instructions. 1564Value *
V = FindValueInExprValueMap(S, &*InsertPt, DropPoisonGeneratingInsts);
1567V = fixupLCSSAFormFor(V);
1571I->dropPoisonGeneratingAnnotations();
1572// See if we can re-infer from first principles any of the flags we just 1574if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I))
1576auto *BO = cast<BinaryOperator>(
I);
1582if (
auto *NNI = dyn_cast<PossiblyNonNegInst>(
I)) {
1583auto *Src = NNI->getOperand(0);
1586 DL).value_or(
false))
1587 NNI->setNonNeg(
true);
1591// Remember the expanded value for this SCEV at this location. 1593// This is independent of PostIncLoops. The mapped value simply materializes 1594// the expression at this insertion point. If the mapped value happened to be 1595// a postinc expansion, it could be reused by a non-postinc user, but only if 1596// its insertion point was already at the head of the loop. 1597 InsertedExpressions[std::make_pair(S, &*InsertPt)] =
V;
1601void SCEVExpander::rememberInstruction(
Value *
I) {
1602auto DoInsert = [
this](
Value *
V) {
1603if (!PostIncLoops.
empty())
1604 InsertedPostIncValues.insert(V);
1606 InsertedValues.insert(V);
1612// If we already have flags for the instruction, keep the existing ones. 1616void SCEVExpander::replaceCongruentIVInc(
1626 dyn_cast<Instruction>(
Phi->getIncomingValueForBlock(LatchBlock));
1627if (!OrigInc || !IsomorphicInc)
1630// If this phi has the same width but is more canonical, replace the 1631// original with it. As part of the "more canonical" determination, 1632// respect a prior decision to use an IV chain. 1634 !(ChainedPhis.count(Phi) ||
1635 isExpandedAddRecExprPHI(OrigPhi, OrigInc, L)) &&
1636 (ChainedPhis.count(Phi) ||
1637 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
1642// Replacing the congruent phi is sufficient because acyclic 1643// redundancy elimination, CSE/GVN, should handle the 1644// rest. However, once SCEV proves that a phi is congruent, 1645// it's often the head of an IV user cycle that is isomorphic 1646// with the original phi. It's worth eagerly cleaning up the 1647// common case of a single IV increment so that DeleteDeadPHIs 1648// can remove cycles that had postinc uses. 1649// Because we may potentially introduce a new use of OrigIV that didn't 1650// exist before at this point, its poison flags need readjustment. 1651constSCEV *TruncExpr =
1653if (OrigInc == IsomorphicInc || TruncExpr != SE.
getSCEV(IsomorphicInc) ||
1657bool BothHaveNUW =
false;
1658bool BothHaveNSW =
false;
1659auto *OBOIncV = dyn_cast<OverflowingBinaryOperator>(OrigInc);
1660auto *OBOIsomorphic = dyn_cast<OverflowingBinaryOperator>(IsomorphicInc);
1661if (OBOIncV && OBOIsomorphic) {
1663 OBOIncV->hasNoUnsignedWrap() && OBOIsomorphic->hasNoUnsignedWrap();
1665 OBOIncV->hasNoSignedWrap() && OBOIsomorphic->hasNoSignedWrap();
1669/*RecomputePoisonFlags*/true))
1672// We are replacing with a wider increment. If both OrigInc and IsomorphicInc 1673// are NUW/NSW, then we can preserve them on the wider increment; the narrower 1674// IsomorphicInc would wrap before the wider OrigInc, so the replacement won't 1675// make IsomorphicInc's uses more poisonous. 1678"Should only replace an increment with a wider one.");
1679if (BothHaveNUW || BothHaveNSW) {
1685dbgs() <<
"INDVARS: Eliminated congruent iv.inc: " 1686 << *IsomorphicInc <<
'\n');
1687Value *NewInc = OrigInc;
1690if (
PHINode *PN = dyn_cast<PHINode>(OrigInc))
1691 IP = PN->
getParent()->getFirstInsertionPt();
1704/// replaceCongruentIVs - Check for congruent phis in this loop header and 1705/// replace them with their most canonical representative. Return the number of 1708/// This does not depend on any SCEVExpander state but should be used in 1709/// the same context that SCEVExpander is used. 1714// Find integer phis in order of increasing width. 1716for (
PHINode &PN : L->getHeader()->phis())
1720// Use stable_sort to preserve order of equivalent PHIs, so the order 1721// of the sorted Phis is the same from run to run on the same loop. 1723// Put pointers at the back and make sure pointer < pointer = false. 1730unsigned NumElim = 0;
1732// Process phis from wide to narrow. Map wide phis to their truncation 1733// so narrow phis can reuse them. 1740auto *Const = dyn_cast<SCEVConstant>(SE.
getSCEV(PN));
1743return Const->getValue();
1746// Fold constant phis. They may be congruent to other constant phis and 1747// would confuse the logic below that expects proper IVs. 1748if (
Value *V = SimplifyPHINode(Phi)) {
1749if (V->getType() != Phi->getType())
1752 Phi->replaceAllUsesWith(V);
1756dbgs() <<
"INDVARS: Eliminated constant iv: " << *Phi
1767if (Phi->getType()->isIntegerTy() &&
TTI &&
1769// Make sure we only rewrite using simple induction variables; 1770// otherwise, we can make the trip count of a loop unanalyzable 1773if (isa<SCEVAddRecExpr>(PhiExpr)) {
1774// This phi can be freely truncated to the narrowest phi type. Map the 1775// truncated expression to it so it will be reused for narrow types. 1776constSCEV *TruncExpr =
1778 ExprToIVMap[TruncExpr] = Phi;
1784// Replacing a pointer phi with an integer phi or vice-versa doesn't make 1789 replaceCongruentIVInc(Phi, OrigPhiRef, L, DT, DeadInsts);
1791dbgs() <<
"INDVARS: Eliminated congruent iv: " << *Phi
1794 DebugType,
dbgs() <<
"INDVARS: Original iv: " << *OrigPhiRef <<
'\n');
1796Value *NewIV = OrigPhiRef;
1797if (OrigPhiRef->
getType() != Phi->getType()) {
1799 L->getHeader()->getFirstInsertionPt());
1803 Phi->replaceAllUsesWith(NewIV);
1815 L->getExitingBlocks(ExitingBlocks);
1817// Look for suitable value in simple conditions at the loop exits. 1822if (!
match(BB->getTerminator(),
1834// Use expand's logic which is used for reusing a previous Value in 1835// ExprValueMap. Note that we don't currently model the cost of 1836// needing to drop poison generating flags on the instruction if we 1837// want to reuse it. We effectively assume that has zero cost. 1839return FindValueInExprValueMap(S, At, DropPoisonGeneratingInsts) !=
nullptr;
1849// Object to help map SCEV operands to expanded IR instructions. 1850structOperationIndices {
1851 OperationIndices(
unsigned Opc,
size_t min,
size_tmax) :
1852 Opcode(Opc), MinIdx(min), MaxIdx(
max) { }
1858// Collect the operations of all the instructions that will be needed to 1859// expand the SCEVExpr. This is so that when we come to cost the operands, 1860// we know what the generated user(s) will be. 1866 S->getOperand(0)->getType(),
1870auto ArithCost = [&](
unsigned Opcode,
unsigned NumRequired,
1878auto CmpSelCost = [&](
unsigned Opcode,
unsigned NumRequired,
unsigned MinIdx,
1881Type *OpType = S->getType();
1887switch (S->getSCEVType()) {
1895Cost = CastCost(Instruction::PtrToInt);
1898Cost = CastCost(Instruction::Trunc);
1901Cost = CastCost(Instruction::ZExt);
1904Cost = CastCost(Instruction::SExt);
1907unsigned Opcode = Instruction::UDiv;
1908if (
auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
1909if (SC->getAPInt().isPowerOf2())
1910 Opcode = Instruction::LShr;
1911Cost = ArithCost(Opcode, 1);
1915Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
1918// TODO: this is a very pessimistic cost modelling for Mul, 1919// because of Bin Pow algorithm actually used by the expander, 1920// see SCEVExpander::visitMulExpr(), ExpandOpBinPowN(). 1921Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
1928// FIXME: should this ask the cost for Intrinsic's? 1929// The reduction tree. 1930Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
1931Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
1932switch (S->getSCEVType()) {
1934// The safety net against poison. 1935// FIXME: this is broken. 1936Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);
1937Cost += ArithCost(Instruction::Or,
1938 S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);
1939Cost += CmpSelCost(Instruction::Select, 1, 0, 1);
1943assert(!isa<SCEVSequentialMinMaxExpr>(S) &&
1944"Unhandled SCEV expression type?");
1950// Addrec expands to a phi and add per recurrence. 1951unsigned NumRecurrences = S->getNumOperands() - 1;
1956// AR start is used in phi. 1957 Worklist.
emplace_back(Instruction::PHI, 0, S->getOperand(0));
1958// Other operands are used in add. 1959for (
constSCEV *
Op : S->operands().drop_front())
1965for (
auto &CostOp : Operations) {
1966for (
auto SCEVOp :
enumerate(S->operands())) {
1967// Clamp the index to account for multiple IR operations being chained. 1968size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
1969size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
1970 Worklist.
emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
1976bool SCEVExpander::isHighCostExpansionHelper(
1982returntrue;
// Already run out of budget, give up. 1985// Was the cost of expansion of this expression already accounted for? 1986if (!isa<SCEVConstant>(S) && !Processed.
insert(S).second)
1987returnfalse;
// We have already accounted for this expression. 1989// If we can find an existing value for this scev available at the point "At" 1990// then consider the expression cheap. 1992returnfalse;
// Consider the expression to be free. 1995L->getHeader()->getParent()->hasMinSize()
2004// Assume to be zero-cost. 2007// Only evalulate the costs of constants when optimizing for size. 2010constAPInt &
Imm = cast<SCEVConstant>(S)->getAPInt();
2022returnfalse;
// Will answer upon next entry into this function. 2025// UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or 2026// HowManyLessThans produced to compute a precise expression, rather than a 2027// UDiv from the user's code. If we can't find a UDiv in the code with some 2028// simple searching, we need to account for it's cost. 2030// At the beginning of this function we already tried to find existing 2031// value for plain 'S'. Now try to lookup 'S + 1' since it is common 2032// pattern involving division. This is just a simple search heuristic. 2035returnfalse;
// Consider it to be free. 2039returnfalse;
// Will answer upon next entry into this function. 2048assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2049"Nary expr should have more than 1 operand.");
2050// The simple nary expr will require one less op (or pair of ops) 2051// than the number of it's terms. 2057assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2058"Polynomial should be at least linear");
2059Cost += costAndCollectOperands<SCEVAddRecExpr>(
2076auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2090auto *
I = Builder.
CreateICmp(InvPred, Expr0, Expr1,
"ident.check");
2097"non-affine expression");
2099// FIXME: It is highly suspicious that we're ignoring the predicates here. 2101constSCEV *ExitCount =
2104assert(!isa<SCEVCouldNotCompute>(ExitCount) &&
"Invalid loop count");
2113// The expression {Start,+,Step} has nusw/nssw if 2114// Step < 0, Start - |Step| * Backedge <= Start 2115// Step >= 0, Start + |Step| * Backedge > Start 2116// and |Step| * Backedge doesn't unsigned overflow. 2119Value *TripCountVal = expand(ExitCount, Loc);
2124Value *StepValue = expand(Step, Loc);
2126Value *StartValue = expand(Start, Loc);
2136// Compute |Step| * Backedge 2138// 1. Start + |Step| * Backedge < Start 2139// 2. Start - |Step| * Backedge > Start 2141// And select either 1. or 2. depending on whether step is positive or 2142// negative. If Step is known to be positive or negative, only create 2144auto ComputeEndCheck = [&]() ->
Value * {
2145// Checking <u 0 is always false. 2149// Get the backedge taken count and truncate or extended to the AR type. 2154// Special-case Step of one. Potentially-costly `umul_with_overflow` isn't 2155// needed, there is never an overflow, so to avoid artificially inflating 2156// the cost of the check, directly emit the optimized IR. 2157 MulV = TruncTripCount;
2161 {AbsStep, TruncTripCount},
2162/*FMFSource=*/nullptr,
"mul");
2171if (isa<PointerType>(ARTy)) {
2181 Sub = Builder.
CreateSub(StartValue, MulV);
2184Value *EndCompareLT =
nullptr;
2185Value *EndCompareGT =
nullptr;
2186Value *EndCheck =
nullptr;
2188 EndCheck = EndCompareLT = Builder.
CreateICmp(
2191 EndCheck = EndCompareGT = Builder.
CreateICmp(
2193if (NeedPosCheck && NeedNegCheck) {
2194// Select the answer based on the sign of Step. 2195 EndCheck = Builder.
CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2197return Builder.
CreateOr(EndCheck, OfMul);
2199Value *EndCheck = ComputeEndCheck();
2201// If the backedge taken count type is larger than the AR type, 2202// check that we don't drop any bits by truncating it. If we are 2203// dropping bits, then we have overflow (unless the step is zero). 2204if (SrcBits > DstBits) {
2206auto *BackedgeCheck =
2208 ConstantInt::get(Loc->
getContext(), MaxVal));
2212 EndCheck = Builder.
CreateOr(EndCheck, BackedgeCheck);
2220constauto *
A = cast<SCEVAddRecExpr>(Pred->
getExpr());
2221Value *NSSWCheck =
nullptr, *NUSWCheck =
nullptr;
2223// Add a check for NUSW 2227// Add a check for NSSW 2231if (NUSWCheck && NSSWCheck)
2232return Builder.
CreateOr(NUSWCheck, NSSWCheck);
2245// Loop over all checks in this set. 2247for (
constauto *Pred : Union->getPredicates()) {
2257Value *SCEVExpander::fixupLCSSAFormFor(
Value *V) {
2258auto *DefI = dyn_cast<Instruction>(V);
2259if (!PreserveLCSSA || !DefI)
2265if (!DefLoop || UseLoop == DefLoop || DefLoop->
contains(UseLoop))
2268// Create a temporary instruction to at the current insertion point, so we 2269// can hand it off to the helper to create LCSSA PHIs if required for the 2271// FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor) 2272// would accept a insertion point and return an LCSSA phi for that 2273// insertion point, so there is no need to insert & remove the temporary 2276if (DefI->getType()->isIntegerTy())
2282auto RemoveUserOnExit =
2291for (
PHINode *PN : InsertedPHIs)
2292 rememberInstruction(PN);
2293for (
PHINode *PN : PHIsToRemove) {
2296 InsertedValues.erase(PN);
2297 InsertedPostIncValues.erase(PN);
2305// Search for a SCEV subexpression that is not safe to expand. Any expression 2306// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely 2307// UDiv expressions. We don't know if the UDiv is derived from an IR divide 2308// instruction, but the important thing is that we prove the denominator is 2309// nonzero before expansion. 2311// IVUsers already checks that IV-derived expressions are safe. So this check is 2312// only needed when the expression includes some subexpression that is not IV 2315// Currently, we only allow division by a value provably non-zero here. 2317// We cannot generally expand recurrences unless the step dominates the loop 2318// header. The expander handles the special case of affine recurrences by 2319// scaling the recurrence outside the loop, but this technique isn't generally 2320// applicable. Expanding a nested recurrence outside a loop requires computing 2321// binomial coefficients. This could be done, but the recurrence has to be in a 2322// perfectly reduced form, which can't be guaranteed. 2323structSCEVFindUnsafe {
2326bool IsUnsafe =
false;
2329 : SE(SE), CanonicalMode(CanonicalMode) {}
2331bool follow(
constSCEV *S) {
2339// For non-affine addrecs or in non-canonical mode we need a preheader 2341if (!AR->getLoop()->getLoopPreheader() &&
2342 (!CanonicalMode || !AR->isAffine())) {
2349bool isDone()
const{
return IsUnsafe; }
2354 SCEVFindUnsafe Search(SE, CanonicalMode);
2356return !Search.IsUnsafe;
2363// We have to prove that the expanded site of S dominates InsertionPoint. 2364// This is easy when not in the same block, but hard when S is an instruction 2365// to be expanded somewhere inside the same block as our insertion point. 2366// What we really need here is something analogous to an OrderedBasicBlock, 2367// but for the moment, we paper over the problem by handling two common and 2368// cheap to check cases. 2374if (
constSCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2382// Result is used, nothing to remove. 2386// Restore original poison flags. 2387for (
auto [
I, Flags] : Expander.OrigFlags)
2393 InsertedInstructions.end());
2396// Remove sets with value handles. 2399// Remove all inserted instructions. 2403 [&InsertedSet](
Value *U) {
2404 return InsertedSet.contains(cast<Instruction>(U));
2406"removed instruction should only be used by instructions inserted " 2409assert(!
I->getType()->isVoidTy() &&
2410"inserted instruction should have non-void types");
2412I->eraseFromParent();
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 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
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
uint64_t IntrinsicInst * II
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 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)
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.
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
This class represents an incoming formal argument to a Function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
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...
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition 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.
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.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
A constant value that is initialized with an expression using other constant values.
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
This is the shared class of boolean and integer constants.
static ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This class represents an Operation in the Expression.
bool isNonIntegralPointerType(PointerType *PT) const
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.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
const BasicBlock & getEntryBlock() const
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags noUnsignedWrap()
static GEPNoWrapFlags none()
Value * CreateVScale(Constant *Scaling, const Twine &Name="")
Create a call to llvm.vscale, multiplied by Scaling.
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
BasicBlock * GetInsertBlock() const
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNSW=false)
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateTruncOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
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.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const Function * getFunction() const
Return the function this instruction belongs to.
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...
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
Represents a single loop in the control flow graph.
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 ...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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.
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 * getStart() const
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 Loop * getLoop() const
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.
bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Determine whether there is an existing expansion of S that can be reused.
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 * 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.
static bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)
Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
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.
bool hasNoUnsignedWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
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.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
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...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getUnknown(Value *V)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueInfo Op1Info={OK_AnyValue, OP_None}, OperandValueInfo Op2Info={OK_AnyValue, OP_None}, const Instruction *I=nullptr) const
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={}, const Instruction *CxtI=nullptr, const TargetLibraryInfo *TLibInfo=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.
InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
@ None
The cast is not used with a load/store of any kind.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
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.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
constexpr ScalarTy getFixedValue() const
const ParentTy * getParent() const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
auto pred_end(const MachineBasicBlock *BB)
auto pred_size(const MachineBasicBlock *BB)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)
Normalize S to be post-increment for all loops present in Loops.
@ Mul
Product of integers.
constexpr unsigned BitWidth
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
auto pred_begin(const MachineBasicBlock *BB)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
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.
void apply(Instruction *I)
PoisonFlags(const Instruction *I)
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Value * visit(const SCEV *S)
