LLVM: llvm::ScalarEvolution Class Reference (original) (raw)

The main scalar evolution driver. More...

#include "[llvm/Analysis/ScalarEvolution.h](ScalarEvolution%5F8h%5Fsource.html)"

The main scalar evolution driver.

Because client code (intentionally) can't do much with the SCEV objects directly, they must ask this class for services.

Definition at line 457 of file ScalarEvolution.h.

◆ BlockDisposition

An enum describing the relationship between a SCEV and a basic block.

Definition at line 469 of file ScalarEvolution.h.

◆ ExitCountKind

The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of times the backedge of a loop has executed before the loop is exited.

Definition at line 887 of file ScalarEvolution.h.

◆ LoopDisposition

An enum describing the relationship between a SCEV and a loop.

Definition at line 462 of file ScalarEvolution.h.

◆ MonotonicPredicateType

A predicate is said to be monotonically increasing if may go from being false to being true as the loop iterates, but never the other way around.

A predicate is said to be monotonically decreasing if may go from being true to being false as the loop iterates, but never the other way around.

Definition at line 1228 of file ScalarEvolution.h.

◆ ScalarEvolution() [2/2]

◆ ~ScalarEvolution()

◆ applyLoopGuards() [1/2]

Try to apply information from loop guards for L to Expr.

Definition at line 16104 of file ScalarEvolution.cpp.

References applyLoopGuards(), and llvm::ScalarEvolution::LoopGuards::collect().

Referenced by llvm::VPlanTransforms::addMinimumIterationCheck(), applyLoopGuards(), llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::EpilogueVectorizerMainLoop::createIterationCountCheck(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), expandBounds(), getSmallConstantTripMultiple(), llvm::isDereferenceableAndAlignedInLoop(), isSafeDecreasingBound(), isSafeIncreasingBound(), and shouldPeelLastIteration().

◆ applyLoopGuards() [2/2]

◆ canReuseInstruction()

Check whether it is poison-safe to represent the expression S using the instruction I.

If such a replacement is performed, the poison flags of instructions in DropPoisonGeneratingInsts must be dropped.

Definition at line 4220 of file ScalarEvolution.cpp.

References llvm::append_range(), llvm::canCreatePoison(), llvm::cast(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), getPoisonGeneratingValues(), I, II, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::programUndefinedIfPoison(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallPtrSetImplBase::size().

◆ clearFlags()

◆ computeConstantDifference()

Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn't.

This is intended to be a cheaper version of getMinusSCEV. We can be frugal here since we just bail out of actually constructing and canonicalizing an expression in the cases where the result isn't going to be a constant.

Definition at line 12184 of file ScalarEvolution.cpp.

References llvm::Add, assert(), llvm::CallingConv::C, llvm::cast(), llvm::dyn_cast(), llvm::SCEV::getType(), getTypeSizeInBits(), I, llvm::isa(), llvm::Less, llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::PatternMatch::match(), llvm::Mul, and llvm::SCEV::operands().

Referenced by getMinFromExprs(), llvm::getPointersDiff(), IsSimplerBaseSCEVForTarget(), and SalvageDVI().

◆ computeExitLimitFromCond()

Compute the number of times the backedge of the specified loop will execute if its exit condition were a conditional branch of ExitCond.

ControlsOnlyExit is true if ExitCond directly controls the only exit branch. In this case, we can assume that the loop exits only if the condition is true and can infer that failing to meet the condition prior to integer wraparound results in undefined behavior.

If AllowPredicates is set, this call will try to use a minimal set of SCEV predicates in order to return an exact answer.

Definition at line 9027 of file ScalarEvolution.cpp.

Referenced by optimizeLoopExitWithUnknownExitCount().

◆ containsAddRecurrence()

◆ containsErasedValue()

◆ containsUndefs()

◆ convertSCEVToAddRecWithPredicates()

Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as required.

Definition at line 15026 of file ScalarEvolution.cpp.

References llvm::Add, llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::end(), getAddExpr(), getBackedgeTakenCount(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), getTruncateOrSignExtend(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_SLT, llvm::SCEVWrapPredicate::IncrementNSSW, llvm::isa(), isKnownPredicate(), and llvm::SCEV::isOne().

◆ createAddRecFromPHIWithCasts()

◆ dominates()

◆ evaluatePredicate()

◆ evaluatePredicateAt()

◆ forgetAllLoops()

◆ forgetBlockAndLoopDispositions()

Called when the client has changed the disposition of values in a loop or block.

We don't have a way to invalidate per-loop/per-block dispositions. Clear and recompute is simpler.

Definition at line 8651 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::empty(), getExistingSCEV(), llvm::SmallPtrSetImpl< PtrType >::insert(), isSCEVable(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and Users.

Referenced by llvm::breakLoopBackedge(), deleteDeadBlocksFromLoop(), llvm::deleteDeadLoop(), DoFlattenLoopPair(), llvm::LoopVectorizationPlanner::executePlan(), llvm::Loop::makeLoopInvariant(), mergeBlocksIntoPredecessors(), moveInstructionBefore(), llvm::peelLoop(), rebuildLoopAfterUnswitch(), sinkLoopInvariantInstructions(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().

◆ forgetLcssaPhiWithNewPredecessor()

Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be trivial.

Definition at line 8611 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::dyn_cast(), forgetValue(), getExistingSCEV(), llvm::SCEVAddRecExpr::getLoop(), I, isSCEVable(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::visitAll().

Referenced by buildClonedLoopBlocks(), cloneLoopBlocks(), ConnectProlog(), llvm::LoopVectorizationPlanner::executePlan(), and llvm::UnrollLoop().

◆ forgetLoop()

This method should be called by the client when it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count, or if the loop is deleted.

This call is potentially expensive for large loop bodies.

Definition at line 8552 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::append_range(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, llvm::SmallVectorImpl< T >::pop_back_val(), and PushLoopPHIs().

Referenced by llvm::breakLoopBackedge(), llvm::deleteDeadLoop(), deleteLoopIfDead(), DoFlattenLoopPair(), llvm::LoopVectorizationPlanner::executePlan(), forgetTopmostLoop(), separateNestedLoop(), splitLoopBound(), llvm::UnrollAndJamLoop(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ forgetLoopDispositions()

Called when the client has changed the disposition of values in this loop.

We don't have a way to invalidate per-loop dispositions. Clear and recompute is simpler.

Definition at line 8649 of file ScalarEvolution.cpp.

◆ forgetTopmostLoop()

◆ forgetValue()

◆ getAbsExpr()

◆ getAddExpr() [1/3]

◆ getAddExpr() [2/3]

◆ getAddExpr() [3/3]

Get a canonical add expression, or something simpler if possible.

Definition at line 2515 of file ScalarEvolution.cpp.

References A(), llvm::APInt::abs(), AbstractManglingParser< Derived, Alloc >::Ops, llvm::Add, AddOpsInlineThreshold, llvm::append_range(), assert(), B(), llvm::BasicBlock::begin(), llvm::BitWidth, llvm::CallingConv::C, llvm::cast(), CollectAddOperandsWithScales(), constantFoldAndGroupOps(), llvm::Count, llvm::count_if(), llvm::Depth, llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getConstant(), getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), getMulExpr(), getNegativeSCEV(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), getOne(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getStart(), getTruncateExpr(), getType(), llvm::SCEVAddExpr::getType(), getTypeSizeInBits(), getUDivExpr(), getZero(), getZeroExtendExpr(), hasFlags(), hasHugeExpression(), llvm::isa(), isAvailableAtLoopEntry(), llvm::APInt::isSignBitSet(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_Add(), llvm::SCEVPatternMatch::m_scev_AllOnes(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_scev_Specific(), llvm::SCEVPatternMatch::m_scev_URem(), llvm::SCEVPatternMatch::m_scev_ZExt(), maskFlags(), llvm::PatternMatch::match(), MaxArithDepth, llvm::Mul, llvm::SCEVNAryExpr::operands(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SmallVectorTemplateCommon< T, typename >::size(), StrengthenNoWrapFlags(), T, llvm::APInt::ule(), and Y.

Referenced by addSCEVNoOverflow(), calculateRtStride(), calculateSubRanges(), calculateUpperBound(), llvm::LoopVectorizationCostModel::computeMaxVF(), convertSCEVToAddRecWithPredicates(), countToEliminateCompares(), createNodeForSelectViaUMinSeq(), llvm::SCEVAddRecExpr::evaluateAtIteration(), ExtractImmediate(), ExtractSymbol(), findForkedSCEVs(), getAddExpr(), getAddExpr(), getAddExpr(), getExactSDiv(), getExtendAddRecStart(), getGEPExpr(), getLosslessPtrToIntExpr(), getMinusSCEV(), getMulExpr(), getNewAlignment(), llvm::SCEVAddRecExpr::getPostIncExpr(), getPreStartForExtend(), llvm::vputils::getSCEVExprForVPValue(), getSignExtendExprImpl(), llvm::getStartAndEndForAccess(), getTripCountFromExitCount(), getTruncateExpr(), getUDivCeilSCEV(), getUDivExpr(), getZeroExtendExprImpl(), llvm::isDereferenceableAndAlignedInLoop(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), IsIncrementNSW(), IsIncrementNUW(), isSafeDecreasingBound(), isSafeIncreasingBound(), llvm::LoopStructure::parseLoopStructure(), removePointerBase(), SimplifyICmpOperands(), llvm::UnrollRuntimeLoopRemainder(), llvm::validateDelinearizationResult(), and willNotOverflow().

◆ getAddRecExpr() [1/3]

Get an add recurrence expression for the specified loop.

Simplify the expression as much as possible.

Definition at line 3688 of file ScalarEvolution.cpp.

References llvm::append_range(), llvm::dyn_cast(), llvm::SCEV::FlagNW, getAddRecExpr(), maskFlags(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by CollectSubexprs(), DoInitialMatch(), ExtractImmediate(), ExtractSymbol(), getAddExpr(), getAddRecExpr(), getAddRecExpr(), getAddRecExpr(), getAnyExtendExpr(), getExactSDiv(), getMulExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::SCEVAddRecExpr::getPostIncExpr(), getPreStartForExtend(), llvm::vputils::getSCEVExprForVPValue(), getSignExtendExprImpl(), llvm::SCEVAddRecExpr::getStepRecurrence(), getTruncateExpr(), getUDivExpr(), getZeroExtendExprImpl(), isLoopBackedgeGuardedByCond(), and removePointerBase().

◆ getAddRecExpr() [2/3]

◆ getAddRecExpr() [3/3]

Get an add recurrence expression for the specified loop.

Simplify the expression as much as possible.

Definition at line 3706 of file ScalarEvolution.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::drop_begin(), llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), getType(), isAvailableAtLoopEntry(), isLoopInvariant(), maskFlags(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::scAddRecExpr, llvm::SmallVectorTemplateCommon< T, typename >::size(), and StrengthenNoWrapFlags().

◆ getAnyExtendExpr()

getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the given type.

Definition at line 2169 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::dyn_cast(), llvm::SCEV::FlagNW, getAddRecExpr(), getAnyExtendExpr(), getEffectiveSCEVType(), getSignExtendExpr(), getTruncateOrNoop(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), llvm::isa(), isSCEVable(), and T.

Referenced by getAddExpr(), getAnyExtendConsideringPostIncUses(), getAnyExtendExpr(), and getNoopOrAnyExtend().

◆ getBackedgeTakenCount()

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCouldNotCompute object.

The backedge-taken count is the number of times the loop header will be branched to from within the loop, assuming there are no abnormal exists like exception throws. This is one less than the trip count of the loop, since it doesn't count the first iteration, when the header is branched to from outside the loop.

Note that it is not valid to call this method on a loop without a loop-invariant backedge-taken count (see hasLoopInvariantBackedgeTakenCount).

Definition at line 8406 of file ScalarEvolution.cpp.

References ConstantMaximum, Exact, llvm_unreachable, and SymbolicMaximum.

Referenced by breakBackedgeIfNotTaken(), canFoldTermCondOfLoop(), llvm::canPeelLastIteration(), llvm::LoopVectorizationCostModel::computeMaxVF(), computeTripCount(), convertSCEVToAddRecWithPredicates(), getAppleRuntimeUnrollPreferences(), getConstantMaxBackedgeTakenCount(), getPreStartForExtend(), getSmallConstantTripCount(), getSmallConstantTripCount(), getSymbolicMaxBackedgeTakenCount(), llvm::ARMTTIImpl::getUnrollingPreferences(), hasLoopInvariantBackedgeTakenCount(), isComputableLoopNest(), llvm::isDereferenceableAndAlignedInLoop(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), isKnownLessThan(), llvm::peelLoop(), PrintLoopInfo(), shouldPeelLastIteration(), verify(), and verifyTripCount().

◆ getBlockDisposition()

◆ getCastExpr()

◆ getComparePredicate()

◆ getConstant() [1/3]

◆ getConstant() [2/3]

Definition at line 470 of file ScalarEvolution.cpp.

References llvm::scConstant.

Referenced by absSCEVNoSignedOverflow(), BinomialCoefficient(), calculateRtStride(), calculateUpperBound(), llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), CollectSubexprs(), llvm::LoopVectorizationCostModel::computeMaxVF(), computeTripCount(), constantFoldAndGroupOps(), countToEliminateCompares(), llvm::delinearizeFixedSizeArray(), DoInitialMatch(), EvaluateConstantChrecAtConstant(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), ExtractImmediate(), ExtractSymbol(), getAddExpr(), getConstant(), getConstant(), getElementCount(), getExactSDiv(), llvm::getIndexExpressionsFromGEP(), getMinusOne(), getMulExpr(), getNegativeSCEV(), getNextSCEVDivisibleByDivisor(), getNotSCEV(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getOffsetOfExpr(), getOne(), getPowerOfTwo(), getPreviousSCEVDivisibleByDivisor(), getSignedOverflowLimitForStep(), getSignExtendExprImpl(), getSizeOfExpr(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getUnsignedOverflowLimitForStep(), getZero(), getZeroExtendExprImpl(), isKnownMultipleOf(), isSafeDecreasingBound(), isSafeDependenceDistance(), isSafeIncreasingBound(), llvm::LoopVectorizationPlanner::selectEpilogueVectorizationFactor(), SimplifyICmpOperands(), SolveLinEquationWithOverflow(), llvm::UnrollRuntimeLoopRemainder(), verify(), and willNotOverflow().

◆ getConstant() [3/3]

◆ getConstantMaxBackedgeTakenCount()

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

a "conservative over-approximation") of the value returend by getBackedgeTakenCount. If such a value cannot be computed, it returns the SCEVCouldNotCompute object.

Definition at line 938 of file ScalarEvolution.h.

References ConstantMaximum, and getBackedgeTakenCount().

Referenced by breakBackedgeIfNotTaken(), countToEliminateCompares(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), getSignExtendExprImpl(), getSmallConstantMaxTripCount(), getZeroExtendExprImpl(), isLoopDead(), mustBeFiniteCountedLoop(), and PrintLoopInfo().

◆ getConstantMultiple()

◆ getContext()

Definition at line 500 of file ScalarEvolution.h.

Referenced by BinomialCoefficient(), getConstant(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::sandboxir::Utils::getPointerDiffInBytes(), getPreStartForExtend(), getSignExtendExprImpl(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), SimplifyICmpOperands(), SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

◆ getCouldNotCompute()

Definition at line 4538 of file ScalarEvolution.cpp.

Referenced by BinomialCoefficient(), getLosslessPtrToIntExpr(), getMinAnalyzeableBackedgeTakenCount(), getMinusSCEV(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::vputils::getSCEVExprForVPValue(), llvm::getStartAndEndForAccess(), getTripCountFromExitCount(), getTripCountFromExitCount(), isKnownViaInduction(), isLoopBackedgeGuardedByCond(), SolveLinEquationWithOverflow(), SplitIntoInitAndPostInc(), and verify().

◆ getDataLayout()

◆ getEffectiveSCEVType()

Return a type with the same bitwidth as the given type and which represents how SCEV will treat the given type, for which isSCEVable must return true.

For pointer types, this is the pointer-sized integer type.

For pointer types, this is the pointer index sized integer type.

Definition at line 4509 of file ScalarEvolution.cpp.

References assert(), getDataLayout(), llvm::DataLayout::getIndexType(), and isSCEVable().

Referenced by canComputePointerDiff(), DoInitialMatch(), findForkedSCEVs(), getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getConstant(), getElementSize(), getGEPExpr(), llvm::getIndexExpressionsFromGEP(), getLosslessPtrToIntExpr(), getMinMaxExpr(), getNegativeSCEV(), getNotSCEV(), getSequentialMinMaxExpr(), getSignExtendExpr(), getSignExtendExprImpl(), getTruncateExpr(), getURemExpr(), getZeroExtendExpr(), isExistingPhi(), and visitIVCast().

◆ getElementCount()

◆ getElementSize()

◆ getEqualPredicate()

◆ getExistingSCEV()

◆ getExitCount()

Return the number of times the backedge executes before the given exit would be taken; if not exactly computable, return SCEVCouldNotCompute.

For a single exit loop, this value is equivelent to the result of getBackedgeTakenCount. The loop is guaranteed to exit (via some exit) before the backedge is executed (ExitCount + 1) times. Note that there is no guarantee about which exit is taken on the exiting iteration.

Definition at line 8370 of file ScalarEvolution.cpp.

References ConstantMaximum, Exact, llvm_unreachable, and SymbolicMaximum.

Referenced by calculateUpperBound(), expandBounds(), getMinAnalyzeableBackedgeTakenCount(), getNarrowestLatchMaxTakenCountEstimate(), getSmallConstantTripCount(), getSmallConstantTripMultiple(), llvm::hasIterationCountInvariantInParent(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), mustBeFiniteCountedLoop(), optimizeLoopExitWithUnknownExitCount(), PrintLoopInfo(), llvm::rewriteLoopExitValues(), and llvm::UnrollRuntimeLoopRemainder().

◆ getGEPExpr() [1/2]

Definition at line 3802 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, getAddExpr(), getEffectiveSCEVType(), getMulExpr(), getOffsetOfExpr(), getSizeOfExpr(), getTruncateOrSignExtend(), llvm::SCEV::getType(), llvm::GetElementPtrInst::getTypeAtIndex(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), llvm::GEPNoWrapFlags::hasNoUnsignedSignedWrap(), llvm::GEPNoWrapFlags::hasNoUnsignedWrap(), llvm::isa(), isKnownNonNegative(), llvm::Offset, and setFlags().

◆ getGEPExpr() [2/2]

◆ getLoopDisposition()

◆ getLoopInvariantExitCondDuringFirstIterations()

◆ getLoopInvariantExitCondDuringFirstIterationsImpl()

Definition at line 11413 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::SCEVAddRecExpr::getLoop(), getNegativeSCEV(), getOne(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::ICmpInst::getSwappedCmpPredicate(), llvm::SCEV::getType(), llvm::SCEVAddRecExpr::getType(), llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_ULE, isKnownPredicateAt(), isLoopBackedgeGuardedByCond(), isLoopInvariant(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isSigned(), llvm::Last, and std::swap().

Referenced by getLoopInvariantExitCondDuringFirstIterations().

◆ getLoopInvariantPredicate()

If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvariantPredicate with LHS and RHS being invariants, available at L's entry.

Otherwise, return std::nullopt.

Definition at line 11308 of file ScalarEvolution.cpp.

References assert(), llvm::dyn_cast(), llvm::ICmpInst::getFlippedSignednessPredicate(), llvm::ICmpInst::getInverseCmpPredicate(), llvm::SCEVAddRecExpr::getLoop(), getMonotonicPredicateType(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::ICmpInst::getSwappedCmpPredicate(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::SCEVAddRecExpr::isAffine(), isKnownNonNegative(), isKnownPositive(), isKnownPredicateAt(), isLoopBackedgeGuardedByCond(), isLoopInvariant(), MonotonicallyIncreasing, P, and std::swap().

◆ getLosslessPtrToIntExpr()

The SCEVPtrToIntSinkingRewriter takes a scalar evolution expression, which computes a pointer-typed value, and rewrites the whole expression tree so that all the computations are done on integers, and the only pointer-typed operands in the expression are SCEVUnknown.

Definition at line 1007 of file ScalarEvolution.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::sampleprof::Base, Changed, llvm::Depth, llvm::dyn_cast(), getAddExpr(), getCouldNotCompute(), getDataLayout(), getEffectiveSCEVType(), llvm::DataLayout::getIntPtrType(), getLosslessPtrToIntExpr(), getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEV::getType(), llvm::SCEVUnknown::getType(), getTypeSizeInBits(), getZero(), llvm::isa(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm::SCEVNAryExpr::operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), Rewriter, ScalarEvolution(), SCEVUnknown, llvm::scPtrToInt, and visit().

Referenced by getLosslessPtrToIntExpr(), and getPtrToIntExpr().

◆ getMinMaxExpr()

Definition at line 3880 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::append_range(), assert(), llvm::CallingConv::C, llvm::cast(), constantFoldAndGroupOps(), getEffectiveSCEVType(), getMinMaxExpr(), getType(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, llvm::isPointerTy(), llvm_unreachable, llvm::SCEVNAryExpr::operands(), registerUser(), llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::APIntOps::smax(), llvm::APIntOps::smin(), llvm::APIntOps::umax(), llvm::APIntOps::umin(), and llvm::uninitialized_copy().

Referenced by applyDivisibilityOnMinMaxExpr(), getMinMaxExpr(), getNotSCEV(), getSequentialMinMaxExpr(), getSMaxExpr(), getSMinExpr(), getUMaxExpr(), and getUMinExpr().

◆ getMinTrailingZeros()

Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).

It is, at the same time, the minimum number of times S is divisible by 2. For example, given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. If CtxI is not nullptr, return a constant multiple valid at CtxI.

Definition at line 6466 of file ScalarEvolution.cpp.

References getConstantMultiple(), llvm::SCEV::getType(), and getTypeSizeInBits().

Referenced by extractConstantWithoutWrapping(), extractConstantWithoutWrapping(), getMulExpr(), getTruncateExpr(), and SolveLinEquationWithOverflow().

◆ getMinusOne()

◆ getMinusSCEV()

Return LHS-RHS.

Minus is represented in SCEV as A+B*-1.

If the LHS and RHS are pointers which don't share a common base (according to getPointerBase()), this returns a SCEVCouldNotCompute. To compute the difference between two unrelated pointers, you can explicitly convert the arguments using getPtrToIntExpr(), for pointer types that support it.

Definition at line 4700 of file ScalarEvolution.cpp.

References llvm::Depth, llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, getAddExpr(), getCouldNotCompute(), getNegativeSCEV(), getPointerBase(), getSignedRangeMin(), getZero(), hasFlags(), isKnownNonNegative(), llvm::APInt::isMinSignedValue(), and removePointerBase().

Referenced by BinomialCoefficient(), calculateRtStride(), calculateSubRanges(), canBeCheaplyTransformed(), createNodeForSelectViaUMinSeq(), createReplacement(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), findForkedSCEVs(), getNewAlignment(), getNotSCEV(), getStartForNegStride(), getUDivCeilSCEV(), getUDivExpr(), getURemExpr(), llvm::isDereferenceableAndAlignedInLoop(), isKnownLessThan(), isSafeDecreasingBound(), isSafeDependenceDistance(), isSafeIncreasingBound(), minusSCEVNoSignedOverflow(), llvm::LoopStructure::parseLoopStructure(), shouldPeelLastIteration(), verify(), and willNotOverflow().

◆ getMonotonicPredicateType()

◆ getMulExpr() [1/3]

◆ getMulExpr() [2/3]

◆ getMulExpr() [3/3]

Get a canonical multiply expression, or something simpler if possible.

Definition at line 3104 of file ScalarEvolution.cpp.

References llvm::APInt::abs(), AbstractManglingParser< Derived, Alloc >::Ops, llvm::Add, llvm::append_range(), assert(), llvm::CallingConv::C, llvm::cast(), Choose(), clearFlags(), constantFoldAndGroupOps(), llvm::ConstantRange::contains(), containsConstantInAddMulChain(), D(), llvm::Depth, llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddExpr(), getAddRecExpr(), llvm::SCEVConstant::getAPInt(), getConstant(), llvm::SCEVAddRecExpr::getLoop(), getMinTrailingZeros(), getMulExpr(), getNegativeSCEV(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::APInt::getSignedMinValue(), getSignedRange(), getSignedRangeMin(), getTruncateExpr(), getType(), llvm::SCEVAddExpr::getType(), llvm::SCEVAddRecExpr::getType(), getTypeSizeInBits(), getUDivExpr(), getZero(), getZeroExtendExpr(), hasFlags(), hasHugeExpression(), llvm::isa(), llvm::APInt::isAllOnes(), isAvailableAtLoopEntry(), llvm::APInt::isMinSignedValue(), llvm::APInt::isNegative(), llvm::Type::isPointerTy(), llvm::APInt::isPowerOf2(), llvm::APInt::logBase2(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_Add(), llvm::SCEVPatternMatch::m_scev_UDiv(), llvm::SCEVPatternMatch::m_scev_ZExt(), llvm::SCEVPatternMatch::m_SCEVConstant(), llvm::ConstantRange::makeGuaranteedNoWrapRegion(), maskFlags(), llvm::PatternMatch::match(), MaxAddRecSize, MaxArithDepth, llvm::Mul, MulOpsInlineThreshold, llvm::OverflowingBinaryOperator::NoSignedWrap, llvm::SCEV::operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SmallVector, StrengthenNoWrapFlags(), llvm::APInt::uge(), llvm::APInt::ugt(), and umul_ov().

Referenced by BinomialCoefficient(), calculateRtStride(), CollectAddOperandsWithScales(), collectDivisibilityInformation(), CollectSubexprs(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), findArrayDimensionsRec(), findForkedSCEVs(), getAddExpr(), getElementCount(), getExactSDiv(), getGEPExpr(), getLosslessPtrToIntExpr(), getMulExpr(), getMulExpr(), getMulExpr(), getNegativeSCEV(), getNumBytes(), llvm::vputils::getSCEVExprForVPValue(), getSignExtendExprImpl(), getSizeOfExpr(), getStartForNegStride(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), isSafeDependenceDistance(), llvm::VPlanTransforms::materializeConstantVectorTripCount(), mulSCEVNoSignedOverflow(), mulSCEVOverflow(), removeConstantFactors(), llvm::LoopVectorizationPlanner::selectEpilogueVectorizationFactor(), SolveLinEquationWithOverflow(), llvm::validateDelinearizationResult(), and willNotOverflow().

◆ getNegativeSCEV()

Return the SCEV object corresponding to -V.

Return a SCEV corresponding to -V = -1*V.

Definition at line 4620 of file ScalarEvolution.cpp.

References llvm::cast(), llvm::dyn_cast(), getConstant(), getEffectiveSCEVType(), getMinusOne(), getMulExpr(), and llvm::ConstantExpr::getNeg().

Referenced by detectShiftUntilZeroIdiom(), getAbsExpr(), getAddExpr(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getMinusSCEV(), getMulExpr(), getOptimizableIVOf(), llvm::getStartAndEndForAccess(), isOneDimensionalArray(), isSafeDependenceDistance(), llvm::FullDependence::normalize(), and llvm::LoopStructure::parseLoopStructure().

◆ getNonZeroConstantMultiple()

◆ getNoopOrAnyExtend()

◆ getNoopOrSignExtend()

◆ getNoopOrZeroExtend()

◆ getNotSCEV()

Return the SCEV object corresponding to ~V.

Return a SCEV corresponding to ~V = -1-V.

Definition at line 4641 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), llvm::dyn_cast(), getConstant(), getEffectiveSCEVType(), getMinMaxExpr(), getMinusOne(), getMinusSCEV(), llvm::ConstantExpr::getNot(), MatchNotExpr(), llvm::SCEVMinMaxExpr::negate(), llvm::SCEV::operands(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by createNodeForSelectViaUMinSeq().

◆ getOffsetOfExpr()

◆ getOne()

Return a SCEV for the constant 1 of a specific type.

Definition at line 679 of file ScalarEvolution.h.

References getConstant().

Referenced by calculateSubRanges(), calculateUpperBound(), llvm::LoopVectorizationCostModel::computeMaxVF(), createReplacement(), getAddExpr(), getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::vputils::getSCEVExprForVPValue(), getTripCountFromExitCount(), getUDivCeilSCEV(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), isLoopBackedgeGuardedByCond(), isSafeDecreasingBound(), isSafeIncreasingBound(), llvm::LoopStructure::parseLoopStructure(), llvm::replaceSymbolicStrideSCEV(), shouldPeelLastIteration(), and llvm::validateDelinearizationResult().

◆ getPointerBase()

◆ getPoisonGeneratingValues()

◆ getPowerOfTwo()

◆ getPredicatedBackedgeTakenCount()

◆ getPredicatedConstantMaxBackedgeTakenCount()

Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are required to be true in order for the answer to be correct.

Predicates can be checked with run-time checks and can be used to perform loop versioning.

Definition at line 8424 of file ScalarEvolution.cpp.

Referenced by getSmallConstantMaxTripCount(), and PrintLoopInfo().

◆ getPredicatedExitCount()

◆ getPredicatedSymbolicMaxBackedgeTakenCount()

◆ getPtrToIntExpr()

◆ getSCEV()

Return a SCEV expression for the full generality of the specified expression.

Return an existing SCEV if it exists, otherwise analyze the expression and create a new one.

Definition at line 4598 of file ScalarEvolution.cpp.

References assert(), getExistingSCEV(), and isSCEVable().

Referenced by llvm::RecurrenceDescriptor::AddReductionVar(), analyzeICmp(), calculateRtStride(), calculateSubRanges(), canFoldTermCondOfLoop(), canOverlap(), llvm::canPeelLastIteration(), canTailPredicateLoop(), countToEliminateCompares(), llvm::EpilogueVectorizerMainLoop::createIterationCountCheck(), createNodeForSelectViaUMinSeq(), createWidenInductionRecipes(), DbgGatherSalvagableDVI(), DbgRewriteSalvageableDVIs(), detectShiftUntilZeroIdiom(), DoInitialMatch(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), findForkedSCEVs(), llvm::findHistogram(), findIVOperand(), FindLoopCounter(), formLCSSAForInstructionsImpl(), genLoopLimit(), getAddressAccessSCEV(), getAppleRuntimeUnrollPreferences(), getBoundsCheckCond(), getFalkorUnrollingPreferences(), getGEPExpr(), llvm::getIndexExpressionsFromGEP(), GetInductionVariable(), llvm::LoopVectorizationCostModel::getInstructionCost(), getLoopVariantGEPOperand(), getNewAlignment(), llvm::getPointersDiff(), getSCEVAtScope(), llvm::vputils::getSCEVExprForVPValue(), llvm::getStartAndEndForAccess(), getStrengthenedNoWrapFlagsFromBinOp(), getStrideFromPointer(), isBigEndianBitShift(), llvm::isDereferenceableAndAlignedInLoop(), isExistingPhi(), llvm::RecurrenceDescriptor::isFindIVPattern(), isHighCostExpansion(), llvm::InductionDescriptor::isInductionPHI(), llvm::LoopAccessInfo::isInvariant(), llvm::LoopVectorizationLegality::isInvariantAddressOfReduction(), isLoopCounter(), isProfitableChain(), isSimpleIVUser(), llvm::LoopVectorizationLegality::isUniform(), loadCSE(), llvm::VPlanTransforms::materializeConstantVectorTripCount(), llvm::LoopStructure::parseLoopStructure(), print(), llvm::rewriteLoopExitValues(), llvm::LoopVectorizationCostModel::setVectorizedCallDecision(), splitLoopBound(), llvm::storeToSameAddress(), verify(), and verifyTripCount().

◆ getSCEVAtScope() [1/2]

Return a SCEV expression for the specified value at the specified scope in the program.

The L value specifies a loop nest to evaluate the expression at, where null is the top-level or a specified loop is immediately inside of the loop.

This method can be used to compute the exit value for a variable defined in a loop by querying what the value will hold in the parent loop.

In the case that a relevant loop exit value cannot be computed, the original value V is returned.

Definition at line 9910 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::SmallVectorImpl< T >::emplace_back(), llvm::isa(), and llvm::reverse().

Referenced by computeUnrollAndJamCount(), createReplacement(), dumpExampleDependence(), getSCEVAtScope(), isInteresting(), print(), and llvm::rewriteLoopExitValues().

◆ getSCEVAtScope() [2/2]

◆ getSequentialMinMaxExpr()

Definition at line 4282 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::cast(), Changed, getEffectiveSCEVType(), llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(), getMinMaxExpr(), getSequentialMinMaxExpr(), getType(), getZero(), llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULE, llvm::impliesPoison(), llvm::isPointerTy(), llvm_unreachable, registerUser(), llvm::scSequentialUMinExpr, and llvm::uninitialized_copy().

Referenced by getSequentialMinMaxExpr(), and getUMinExpr().

◆ getSignedRange()

◆ getSignedRangeMax()

◆ getSignedRangeMin()

◆ getSignExtendExpr()

Definition at line 1890 of file ScalarEvolution.cpp.

References assert(), llvm::Depth, getEffectiveSCEVType(), getSignExtendExprImpl(), getTypeSizeInBits(), insertFoldCacheEntry(), llvm::isa(), isSCEVable(), and llvm::scSignExtend.

Referenced by getAnyExtendExpr(), getCastExpr(), getNoopOrSignExtend(), getSignExtendExprImpl(), getTruncateOrSignExtend(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), IsIncrementNSW(), isMulSExtable(), llvm::LoopStructure::parseLoopStructure(), and willNotOverflow().

◆ getSignExtendExprImpl()

Definition at line 1908 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::BitWidth, llvm::CallingConv::C, llvm::cast(), llvm::ConstantRange::contains(), D(), llvm::Depth, llvm::dyn_cast(), extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getConstantMaxBackedgeTakenCount(), getContext(), getEffectiveSCEVType(), getExtendAddRecStart(), getMulExpr(), getSignedRange(), getSignExtendExpr(), getSMaxExpr(), getSMinExpr(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), llvm::isa(), isKnownNonNegative(), isSCEVable(), MaxCastDepth, llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), llvm::scSignExtend, setNoWrapFlags(), llvm::ConstantRange::sextOrTrunc(), llvm::ConstantRange::signExtend(), llvm::ConstantRange::truncate(), and X.

Referenced by getSignExtendExpr().

◆ getSizeOfExpr() [1/2]

◆ getSizeOfExpr() [2/2]

◆ getSmallConstantMaxTripCount()

◆ getSmallConstantTripCount() [1/2]

◆ getSmallConstantTripCount() [2/2]

Return the exact trip count for this loop if we exit through ExitingBlock.

'0' is used to represent an unknown or non-constant trip count. Note that a trip count is simply one more than the backedge taken count for the same exit. This "trip count" assumes that control exits via ExitingBlock. More precisely, it is the number of times that control will reach ExitingBlock before taking the branch. For loops with multiple exits, it may not be the number times that the loop header executes if the loop exits prematurely via another branch.

Definition at line 8299 of file ScalarEvolution.cpp.

References assert(), llvm::dyn_cast(), getConstantTripCount(), and getExitCount().

◆ getSmallConstantTripMultiple() [1/3]

◆ getSmallConstantTripMultiple() [2/3]

Returns the largest constant divisor of the trip count of this loop as a normal unsigned value, if possible.

This means that the actual trip count is always a multiple of the returned value (don't forget the trip count could very well be zero as well!). As explained in the comments for getSmallConstantTripCount, this assumes that control exits the loop via ExitingBlock.

This means that the actual trip count is always a multiple of the returned value (don't forget the trip count could very well be zero as well!).

Returns 1 if the trip count is unknown or not guaranteed to be the multiple of a constant (which is also the case if the trip count is simply constant, use getSmallConstantTripCount for that case), Will also return 1 if the trip count is very large (>= 2^32).

As explained in the comments for getSmallConstantTripCount, this assumes that control exits the loop via ExitingBlock.

Definition at line 8361 of file ScalarEvolution.cpp.

References assert(), getExitCount(), and getSmallConstantTripMultiple().

◆ getSmallConstantTripMultiple() [3/3]

Returns the largest constant divisor of the trip count as a normal unsigned value, if possible.

This means that the actual trip count is always a multiple of the returned value. Returns 1 if the trip count is unknown or not guaranteed to be the multiple of a constant., Will also return 1 if the trip count is very large (>= 2^32). Note that the argument is an exit count for loop L, NOT a trip count.

Definition at line 8332 of file ScalarEvolution.cpp.

References applyLoopGuards(), llvm::APInt::countTrailingZeros(), llvm::APInt::getActiveBits(), getNonZeroConstantMultiple(), getTripCountFromExitCount(), llvm::APInt::getZExtValue(), and llvm::isa().

Referenced by getAppleRuntimeUnrollPreferences(), getSmallConstantTripMultiple(), getSmallConstantTripMultiple(), PrintLoopInfo(), tryToUnrollAndJamLoop(), tryToUnrollLoop(), and llvm::UnrollLoop().

◆ getSMaxExpr() [1/2]

◆ getSMaxExpr() [2/2]

◆ getSMinExpr() [1/2]

◆ getSMinExpr() [2/2]

◆ getStoreSizeOfExpr()

◆ getStrengthenedNoWrapFlagsFromBinOp()

Parse NSW/NUW flags from add/sub/mul IR binary operation [Op](namespacellvm.html#ab471937b9a227e70c7fe8bd9604014d6) into SCEV no-wrap flags, and deduce flag[s] that aren't known yet.

Does not mutate the original instruction. Returns std::nullopt if it could not deduce more precise flags than the instruction already has, otherwise returns proven flags.

Definition at line 2380 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::Operator::getOpcode(), llvm::User::getOperand(), getSCEV(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), setFlags(), UseContextForNoWrapFlagInference, and willNotOverflow().

◆ getSymbolicMaxBackedgeTakenCount()

◆ getTripCountFromExitCount() [1/2]

A version of getTripCountFromExitCount below which always picks an evaluation type which can not result in overflow.

Definition at line 8238 of file ScalarEvolution.cpp.

References assert(), getCouldNotCompute(), llvm::Type::getIntNTy(), getTripCountFromExitCount(), llvm::SCEV::getType(), and llvm::isa().

Referenced by addInitialSkeleton(), computeTripCount(), getNumBytes(), getSmallConstantTripCount(), getSmallConstantTripMultiple(), getTripCountFromExitCount(), and verifyTripCount().

◆ getTripCountFromExitCount() [2/2]

Convert from an "exit count" (i.e.

"backedge taken count") to a "trip count". A "trip count" is the number of times the header of the loop will execute if an exit is taken after the specified number of backedges have been taken. (e.g. TripCount = ExitCount + 1). Note that the expression can overflow if ExitCount = UINT_MAX. If EvalTy is not wide enough to hold the result without overflow, result unsigned wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)

Definition at line 8249 of file ScalarEvolution.cpp.

References llvm::ConstantRange::contains(), getAddExpr(), getCouldNotCompute(), llvm::APInt::getMaxValue(), getMinusOne(), getOne(), llvm::Type::getPrimitiveSizeInBits(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), llvm::CmpInst::ICMP_NE, llvm::isa(), and isLoopEntryGuardedByCond().

◆ getTruncateExpr()

Definition at line 1141 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), llvm::Depth, llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, getAddExpr(), getAddRecExpr(), getConstant(), getEffectiveSCEVType(), getMinTrailingZeros(), getMulExpr(), llvm::ConstantExpr::getTrunc(), getTruncateExpr(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getTypeSizeInBits(), getZero(), llvm::isa(), isSCEVable(), llvm_unreachable, MaxCastDepth, llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), and llvm::scTruncate.

Referenced by createReplacement(), generateLoopLatchCheck(), genLoopLimit(), getAddExpr(), getCastExpr(), getMulExpr(), getTruncateExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getURemExpr(), and getZeroExtendExprImpl().

◆ getTruncateOrNoop()

◆ getTruncateOrSignExtend()

Return a SCEV corresponding to a conversion of the input value to the specified type.

If the type must be extended, it is sign extended.

Definition at line 4762 of file ScalarEvolution.cpp.

References assert(), llvm::Depth, getSignExtendExpr(), getTruncateExpr(), and getTypeSizeInBits().

Referenced by convertSCEVToAddRecWithPredicates(), findForkedSCEVs(), getGEPExpr(), llvm::vputils::getSCEVExprForVPValue(), getSignExtendExprImpl(), and getTruncateExpr().

◆ getTruncateOrZeroExtend()

Return a SCEV corresponding to a conversion of the input value to the specified type.

If the type must be extended, it is zero extended.

Definition at line 4750 of file ScalarEvolution.cpp.

References assert(), llvm::Depth, getTruncateExpr(), getTypeSizeInBits(), and getZeroExtendExpr().

Referenced by BinomialCoefficient(), getNumBytes(), getPtrToIntExpr(), getSignExtendExprImpl(), getStartForNegStride(), getTripCountFromExitCount(), getTruncateExpr(), getZeroExtendExprImpl(), and isKnownLessThan().

◆ getTypeSizeInBits()

Return the size in bits of the specified type, for which isSCEVable must return true.

Definition at line 4499 of file ScalarEvolution.cpp.

References assert(), getDataLayout(), llvm::DataLayout::getIndexTypeSizeInBits(), llvm::DataLayout::getTypeSizeInBits(), and isSCEVable().

Referenced by BinomialCoefficient(), computeConstantDifference(), createReplacement(), FindLoopCounter(), genLoopLimit(), getAddExpr(), getAnyExtendExpr(), getLosslessPtrToIntExpr(), getMinTrailingZeros(), getMulExpr(), getNoopOrAnyExtend(), getNoopOrSignExtend(), getNoopOrZeroExtend(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getPowerOfTwo(), getPreStartForExtend(), getSignedOverflowLimitForStep(), getSignExtendExpr(), getSignExtendExprImpl(), getTripCountFromExitCount(), getTruncateExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getUnsignedOverflowLimitForStep(), getWiderType(), getZeroExtendExpr(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isMulSExtable(), isSimpleCastedPHI(), SolveLinEquationWithOverflow(), SolveQuadraticAddRecRange(), verify(), and visitIVCast().

◆ getUDivCeilSCEV()

◆ getUDivExactExpr()

Get a canonical unsigned division expression, or something simpler if possible.

There is no representation for an exact udiv in SCEV IR, but we can attempt to remove factors from the LHS and RHS. We can't do this when it's not exact because the udiv may be clearing bits.

Definition at line 3634 of file ScalarEvolution.cpp.

References llvm::append_range(), llvm::cast(), llvm::drop_begin(), llvm::dyn_cast(), llvm::gcd(), getConstant(), getMulExpr(), getUDivExactExpr(), getUDivExpr(), llvm::APInt::isIntN(), llvm::Mul, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by calculateRtStride(), getUDivExactExpr(), and SolveLinEquationWithOverflow().

◆ getUDivExpr()

Get a canonical unsigned division expression, or something simpler if possible.

Get a canonical UDivExpr for a recurrence. {X,+,N}/C => {Y,+,N}/C where Y=X-(XN). Safe when CN=0.

Definition at line 3437 of file ScalarEvolution.cpp.

References A(), assert(), llvm::CallingConv::C, llvm::SmallVectorImpl< T >::clear(), llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getContext(), getMinusSCEV(), getMulExpr(), getTypeSizeInBits(), getUDivExpr(), getURemExpr(), getZero(), getZeroExtendExpr(), llvm::isa(), llvm::APInt::isMinSignedValue(), llvm::APInt::isNegative(), llvm::APInt::isPowerOf2(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_Add(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::SCEVPatternMatch::m_scev_c_NUWMul(), llvm::SCEVPatternMatch::m_scev_SMax(), llvm::SCEVPatternMatch::m_scev_Specific(), llvm::SCEVPatternMatch::m_scev_Zero(), llvm::SCEVPatternMatch::m_SCEVVScale(), llvm::PatternMatch::match(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), llvm::scUDivExpr, llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SmallVector, llvm::APInt::ule(), llvm::APInt::umul_ov(), and llvm::APInt::urem().

Referenced by BinomialCoefficient(), collectDivisibilityInformation(), getAddExpr(), getMulExpr(), getUDivCeilSCEV(), getUDivExactExpr(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), and llvm::VPlanTransforms::materializeConstantVectorTripCount().

◆ getUMaxExpr() [1/2]

◆ getUMaxExpr() [2/2]

◆ getUMaxFromMismatchedTypes()

◆ getUMinExpr() [1/2]

Definition at line 4422 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, and getUMinExpr().

Referenced by calculateSubRanges(), createNodeForSelectViaUMinSeq(), llvm::getStartAndEndForAccess(), getUDivCeilSCEV(), getUMinExpr(), getUMinFromMismatchedTypes(), getZeroExtendExprImpl(), IntersectUnsignedRange(), and splitLoopBound().

◆ getUMinExpr() [2/2]

◆ getUMinFromMismatchedTypes() [1/2]

◆ getUMinFromMismatchedTypes() [2/2]

◆ getUnknown()

◆ getUnsignedRange()

◆ getUnsignedRangeMax()

◆ getUnsignedRangeMin()

◆ getURemExpr()

Represents an unsigned remainder expression based on unsigned division.

Definition at line 3408 of file ScalarEvolution.cpp.

References assert(), llvm::dyn_cast(), llvm::SCEV::FlagNUW, llvm::IntegerType::get(), getContext(), getEffectiveSCEVType(), getMinusSCEV(), getMulExpr(), getTruncateExpr(), getUDivExpr(), getZero(), and getZeroExtendExpr().

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), getNewAlignmentDiff(), getUDivExpr(), getZeroExtendExprImpl(), isKnownMultipleOf(), llvm::LoopVectorizationPlanner::selectEpilogueVectorizationFactor(), and SolveLinEquationWithOverflow().

◆ getVScale()

◆ getWiderType()

◆ getWrapPredicate()

◆ getZero()

Return a SCEV for the constant 0 of a specific type.

Definition at line 676 of file ScalarEvolution.h.

References getConstant().

Referenced by detectShiftUntilZeroIdiom(), getAddExpr(), getLosslessPtrToIntExpr(), getMinusSCEV(), getMulExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getSequentialMinMaxExpr(), getTruncateExpr(), getUDivExpr(), getURemExpr(), isKnownMultipleOf(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), llvm::isKnownNonPositiveInLoop(), llvm::isKnownPositiveInLoop(), isLoopBackedgeGuardedByCond(), removePointerBase(), and SolveLinEquationWithOverflow().

◆ getZeroExtendExpr()

Definition at line 1556 of file ScalarEvolution.cpp.

References assert(), llvm::Depth, getEffectiveSCEVType(), getTypeSizeInBits(), getZeroExtendExprImpl(), insertFoldCacheEntry(), llvm::isa(), isSCEVable(), and llvm::scZeroExtend.

Referenced by createReplacement(), getAddExpr(), getAnyExtendExpr(), getCastExpr(), getMulExpr(), getNoopOrZeroExtend(), getSignExtendExprImpl(), getTripCountFromExitCount(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getURemExpr(), getZeroExtendExprImpl(), IsIncrementNUW(), isSafeDependenceDistance(), verify(), verifyTripCount(), and willNotOverflow().

◆ getZeroExtendExprImpl()

Definition at line 1574 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::BitWidth, llvm::CallingConv::C, llvm::cast(), llvm::ConstantRange::contains(), D(), llvm::Depth, llvm::dyn_cast(), extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getConstantMaxBackedgeTakenCount(), getContext(), getExtendAddRecStart(), llvm::APInt::getMaxValue(), getMulExpr(), getSignedRangeMin(), getSignExtendExpr(), getTruncateExpr(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getUDivExpr(), getUMaxExpr(), getUMinExpr(), getUnsignedRange(), getURemExpr(), getZeroExtendExpr(), llvm::CmpInst::ICMP_UGT, llvm::isa(), isKnownNegative(), isKnownOnEveryIteration(), isLoopBackedgeGuardedByCond(), isSCEVable(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_scev_Trunc(), llvm::SCEVPatternMatch::m_scev_URem(), llvm::PatternMatch::match(), MaxCastDepth, N, llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), llvm::scZeroExtend, setNoWrapFlags(), llvm::ConstantRange::truncate(), X, llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().

Referenced by getZeroExtendExpr().

◆ hasComputableLoopEvolution()

Return true if the given SCEV changes value in a known way in the specified loop.

This property being true implies that the value is variant in the loop AND that we can emit an expression to compute the value of the expression at any particular loop iteration.

Definition at line 14230 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopComputable.

◆ hasFlags()

◆ hasLoopInvariantBackedgeTakenCount()

◆ hasOperand()

◆ haveSameSign()

◆ instructionCouldExistWithOperands()

Return true if there exists a point in the program at which both A and B could be operands to the same instruction.

SCEV expressions are generally assumed to correspond to instructions which could exists in IR. In general, this requires that there exists a use point in the program where all operands dominate the use.

Example: loop { if loop { v1 = load @global1; } else loop { v2 = load @global2; } } No SCEV with operand V1, and v2 can exist in this program.

For a valid use point to exist, the defining scope of one operand must dominate the other.

Definition at line 4524 of file ScalarEvolution.cpp.

References A(), and B().

Referenced by canComputePointerDiff().

◆ invalidate()

◆ isAvailableAtLoopEntry()

Determine if the SCEV can be evaluated at loop's entry.

It is true if it doesn't depend on a SCEVUnknown of an instruction which is dominated by the header of loop L.

Definition at line 2510 of file ScalarEvolution.cpp.

References isLoopInvariant(), and properlyDominates().

Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), getAddExpr(), getAddRecExpr(), getMulExpr(), hasProcessableCondition(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), llvm::isKnownNonPositiveInLoop(), llvm::isKnownPositiveInLoop(), isKnownViaInduction(), isLoopEntryGuardedByCond(), isSafeDecreasingBound(), and isSafeIncreasingBound().

◆ isBackedgeTakenCountMaxOrZero()

◆ isBasicBlockEntryGuardedByCond()

Test whether entry to the basic block is protected by a conditional between LHS and RHS.

Definition at line 11750 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), llvm::dbgs(), llvm::CmpPredicate::dropSameSign(), llvm::dyn_cast(), llvm::BasicBlock::front(), llvm::BranchInst::getCondition(), llvm::Intrinsic::getDeclarationIfExists(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::ICmpInst::getNonStrictCmpPredicate(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::ICMP_NE, llvm::BranchInst::isUnconditional(), P, llvm::verifyFunction(), and VerifyIR.

Referenced by evaluatePredicateAt(), isKnownPredicateAt(), and isLoopEntryGuardedByCond().

◆ isKnownMultipleOf()

Check that S is a multiple of M.

When S is an AddRecExpr, S is a multiple of M if S starts with a multiple of M and at every iteration step S only adds multiples of M. Assumptions records the runtime predicates under which S is a multiple of M.

Definition at line 11071 of file ScalarEvolution.cpp.

References A(), llvm::CallingConv::C, llvm::dyn_cast(), getComparePredicate(), getConstant(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), getURemExpr(), getZero(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, isKnownMultipleOf(), isKnownPredicate(), P, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by isKnownMultipleOf().

◆ isKnownNegative()

◆ isKnownNonNegative()

Test if the given expression is known to be non-negative.

Definition at line 11035 of file ScalarEvolution.cpp.

References getSignedRangeMin(), and llvm::APInt::isNegative().

Referenced by applyDivisibilityOnMinMaxExpr(), detectShiftUntilZeroIdiom(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), expandBounds(), getGEPExpr(), getLoopInvariantPredicate(), getMinusSCEV(), getSignExtendExprImpl(), haveSameSign(), isKnownLessThan(), isKnownNonNegative(), and StrengthenNoWrapFlags().

◆ isKnownNonPositive()

◆ isKnownNonZero()

◆ isKnownOnEveryIteration()

◆ isKnownPositive()

◆ isKnownPredicate()

Test if the given expression is known to satisfy the condition described by Pred, LHS, and RHS.

Definition at line 11188 of file ScalarEvolution.cpp.

References isKnownViaInduction(), and SimplifyICmpOperands().

Referenced by absSCEVNoSignedOverflow(), llvm::VPlanTransforms::addMinimumIterationCheck(), calculateSubRanges(), calculateUpperBound(), llvm::LoopVectorizationCostModel::computeMaxVF(), convertSCEVToAddRecWithPredicates(), countToEliminateCompares(), llvm::EpilogueVectorizerMainLoop::createIterationCountCheck(), evaluatePredicate(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), llvm::SCEVWrapPredicate::implies(), isConditionTrueViaVFAndUF(), llvm::isDereferenceableAndAlignedInLoop(), isKnownMultipleOf(), isKnownPredicateAt(), IsKnownPredicateViaAddRecStart(), normalizePredicate(), llvm::LoopVectorizationPlanner::selectEpilogueVectorizationFactor(), shouldPeelLastIteration(), simplifyBranchConditionForVFAndUF(), simplifyKnownEVL(), and SolveLinEquationWithOverflow().

◆ isKnownPredicateAt()

◆ isKnownToBeAPowerOfTwo()

◆ isKnownViaInduction()

We'd like to check the predicate on every iteration of the most dominated loop between loops used in LHS and RHS.

To do this we use the following list of steps:

1. Collect set S all loops on which either LHS or RHS depend.
2. If S is non-empty a. Let PD be the element of S which is dominated by all other elements. b. Let E(LHS) be value of LHS on entry of PD. To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values. Define E(RHS) in the same way. c. Let B(LHS) be value of L on backedge of PD. To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values. Define B(RHS) in the same way. d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that. e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))

Definition at line 11138 of file ScalarEvolution.cpp.

References assert(), llvm::SmallPtrSetImplBase::empty(), getCouldNotCompute(), llvm::LoopBase< BlockT, LoopT >::getHeader(), isAvailableAtLoopEntry(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), llvm::max_element(), and SplitIntoInitAndPostInc().

Referenced by isKnownPredicate().

◆ isLoopBackedgeGuardedByCond()

Test whether the backedge of the loop is protected by a conditional between LHS and RHS.

isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is protected by a conditional between LHS and RHS.

This is used to eliminate casts.

This is used to to eliminate casts.

Definition at line 11644 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), llvm::dbgs(), llvm::dyn_cast(), llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddRecExpr(), llvm::BranchInst::getCondition(), getCouldNotCompute(), getOne(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), getZero(), llvm::CmpInst::ICMP_ULT, llvm::BranchInst::isConditional(), llvm::BasicBlockEdge::isSingleEdge(), llvm::verifyFunction(), and VerifyIR.

Referenced by getLoopInvariantExitCondDuringFirstIterationsImpl(), getLoopInvariantPredicate(), getZeroExtendExprImpl(), isKnownOnEveryIteration(), and isKnownViaInduction().

◆ isLoopEntryGuardedByCond()

Test whether entry to the loop is protected by a conditional between LHS and RHS.

This is used to help avoid max expressions in loop trip counts, and to eliminate casts.

Definition at line 11850 of file ScalarEvolution.cpp.

References assert(), isAvailableAtLoopEntry(), and isBasicBlockEntryGuardedByCond().

Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), findSplitCandidate(), getPreStartForExtend(), getTripCountFromExitCount(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), llvm::isKnownNonPositiveInLoop(), isKnownOnEveryIteration(), llvm::isKnownPositiveInLoop(), isKnownViaInduction(), isSafeDecreasingBound(), and isSafeIncreasingBound().

◆ isLoopInvariant()

Return true if the value of the given SCEV is unchanging in the specified loop.

Definition at line 14226 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopInvariant.

Referenced by llvm::RecurrenceDescriptor::AddReductionVar(), llvm::canPeelLastIteration(), canTailPredicateLoop(), computeUnrollAndJamCount(), createWidenInductionRecipes(), genLoopLimit(), getAddRecExpr(), getAddressAccessSCEV(), getAppleRuntimeUnrollPreferences(), llvm::LoopVectorizationCostModel::getInstructionCost(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getLoopInvariantPredicate(), getLoopVariantGEPOperand(), llvm::getPtrStride(), llvm::getStartAndEndForAccess(), getStrideFromPointer(), llvm::ARMTTIImpl::getUnrollingPreferences(), llvm::Loop::isAuxiliaryInductionVariable(), isAvailableAtLoopEntry(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), llvm::LoopAccessInfo::isInvariant(), isOneDimensionalArray(), mayUsePostIncMode(), print(), llvm::rewriteLoopExitValues(), and SimplifyICmpOperands().

◆ isSCEVable()

Test if values of the given type are analyzable within the SCEV framework.

This primarily includes integer types, and it can optionally include pointer types if the ScalarEvolution class has access to target-specific information.

Definition at line 4492 of file ScalarEvolution.cpp.

Referenced by canFoldTermCondOfLoop(), createWidenInductionRecipes(), DbgGatherSalvagableDVI(), findIVOperand(), forgetBlockAndLoopDispositions(), forgetLcssaPhiWithNewPredecessor(), formLCSSAForInstructionsImpl(), getAnyExtendExpr(), getEffectiveSCEVType(), getExistingSCEV(), GetInductionVariable(), getSCEV(), getSignExtendExpr(), getSignExtendExprImpl(), getTruncateExpr(), getTypeSizeInBits(), getZeroExtendExpr(), getZeroExtendExprImpl(), isExistingPhi(), llvm::RecurrenceDescriptor::isFindIVPattern(), isHighCostExpansion(), llvm::InductionDescriptor::isInductionPHI(), llvm::LoopAccessInfo::isInvariant(), isLoopCounter(), isProcessableCondBI(), isSimpleIVUser(), llvm::LoopVectorizationLegality::isUniform(), print(), llvm::rewriteLoopExitValues(), and splitLoopBound().

◆ loopHasNoAbnormalExits()

Return true if the loop has no abnormal exits.

That is, if the loop is not infinite, it must exit through an explicit edge in the CFG. (As opposed to either a) throwing out of the function or b) entering a well defined infinite loop in some callee.)

Definition at line 1408 of file ScalarEvolution.h.

Referenced by llvm::UnrollRuntimeLoopRemainder().

◆ loopIsFiniteByAssumption()

◆ maskFlags()

◆ print()

Definition at line 14045 of file ScalarEvolution.cpp.

References ClassifyExpressions, llvm::depth_first(), llvm::First, getLoopDisposition(), getSCEV(), getSCEVAtScope(), getSignedRange(), getUnsignedRange(), I, instructions, llvm::isa(), isLoopInvariant(), isSCEVable(), llvm::ConstantRange::print(), llvm::SCEV::print(), PrintLoopInfo(), and ScalarEvolution().

◆ properlyDominates()

◆ registerUser()

◆ removePointerBase()

Compute an expression equivalent to S - getPointerBase(S).

Definition at line 4670 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::Add, assert(), llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, getAddExpr(), getAddRecExpr(), getZero(), P, and removePointerBase().

Referenced by dumpExampleDependence(), getMinusSCEV(), and removePointerBase().

◆ rewriteUsingPredicate()

◆ setFlags()

◆ setNoWrapFlags()

◆ SimplifyICmpOperands()

Simplify LHS and RHS in a comparison with predicate Pred.

Return true iff any changes were made. If the operands are provably equal or unequal, LHS and RHS are set to the same value and Pred is set to either ICMP_EQ or ICMP_NE.

Definition at line 10815 of file ScalarEvolution.cpp.

References assert(), llvm::cast(), Changed, llvm::ICmpInst::compare(), llvm::Depth, llvm::dyn_cast(), llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, getAddExpr(), getConstant(), getContext(), llvm::ConstantRange::getEquivalentICmp(), llvm::ConstantInt::getFalse(), llvm::SCEVAddRecExpr::getLoop(), getSignedRangeMax(), getSignedRangeMin(), llvm::ICmpInst::getSwappedCmpPredicate(), getUnsignedRangeMax(), getUnsignedRangeMin(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), HasSameValue(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::isa(), llvm::ConstantRange::isEmptySet(), llvm::ICmpInst::isEquality(), llvm::CmpInst::isFalseWhenEqual(), llvm::ConstantRange::isFullSet(), isLoopInvariant(), llvm::CmpInst::isSigned(), llvm::CmpInst::isTrueWhenEqual(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_c_Mul(), llvm::SCEVPatternMatch::m_SCEVVScale(), llvm::ConstantRange::makeExactICmpRegion(), llvm::PatternMatch::match(), MatchBinarySub(), properlyDominates(), RA, SimplifyICmpOperands(), and std::swap().

Referenced by isKnownPredicate(), and SimplifyICmpOperands().

◆ SplitIntoInitAndPostInc()

Splits SCEV expression S into two SCEVs.

One of them is obtained from S by substitution of all AddRec sub-expression related to loop L with initial value of that SCEV. The second is obtained from S by substitution of all AddRec sub-expressions related to loop L with post increment of this AddRec in the loop L. In both cases all other AddRec sub-expressions (not related to L) remain the same. If the S contains non-invariant unknown SCEV the function returns CouldNotCompute SCEV in both values of std::pair. For example, for SCEV S={0, +, 1} + {0, +, 1} and loop L=L1 the function returns pair: first = {0, +, 1} second = {1, +, 1} + {0, +, 1} We can see that for the first AddRec sub-expression it was replaced with 0 (initial value) for the first element and to {1, +, 1} (post increment value) for the second one. In both cases AddRec expression related to L2 remains the same.

Definition at line 11127 of file ScalarEvolution.cpp.

References assert(), getCouldNotCompute(), and PostInc.

Referenced by isKnownViaInduction().

◆ verify()

Definition at line 14478 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::append_range(), assert(), llvm::SmallPtrSetImpl< PtrType >::contains(), containsUndefs(), llvm::dbgs(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), getBackedgeTakenCount(), getBlockDisposition(), getConstant(), getConstantMultiple(), getCouldNotCompute(), llvm::SCEVAddRecExpr::getLoop(), getLoopDisposition(), getMinusSCEV(), llvm::Value::getName(), getSCEV(), getTypeSizeInBits(), getUnknown(), llvm::SCEVUnknown::getValue(), getZeroExtendExpr(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::is_contained(), llvm::isa(), llvm::SCEV::isZero(), llvm::SCEV::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::Predicated, ScalarEvolution(), SCEVUnknown, llvm::APInt::urem(), and VerifySCEVStrict.

Referenced by llvm::FunctionToLoopPassAdaptor::run(), and llvm::UnrollAndJamLoop().

◆ willNotOverflow()

Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?

If CtxI is specified, the no-overflow fact should be true in the context of this instruction.

Definition at line 2303 of file ScalarEvolution.cpp.

References A(), B(), llvm::CallingConv::C, llvm::cast(), llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::IntegerType::get(), getAddExpr(), getConstant(), llvm::APInt::getMaxValue(), getMinusSCEV(), llvm::APInt::getMinValue(), getMulExpr(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), getSignExtendExpr(), getZeroExtendExpr(), llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_ULE, isKnownPredicateAt(), llvm_unreachable, Operation, ScalarEvolution(), and llvm::Signed.

Referenced by addSCEVNoOverflow(), getStrengthenedNoWrapFlagsFromBinOp(), minusSCEVNoSignedOverflow(), mulSCEVNoSignedOverflow(), mulSCEVOverflow(), and llvm::validateDelinearizationResult().

◆ ScalarEvolutionsTest

◆ SCEVCallbackVH

◆ SCEVExpander

◆ SCEVUnknown

The documentation for this class was generated from the following files:

• include/llvm/Analysis/ScalarEvolution.h
• lib/Analysis/ScalarEvolution.cpp