ScalarEvolution.cpp File Reference

#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/SaveAndRestore.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE   "scalar-evolution"

Functions
	STATISTIC (NumExitCountsComputed, "Number of loop exits with predictable exit counts")
	STATISTIC (NumExitCountsNotComputed, "Number of loop exits without predictable exit counts")
	STATISTIC (NumBruteForceTripCountsComputed, "Number of loops with trip counts computed by force")
static int	CompareValueComplexity (const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
	Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and somewhat ad-hoc) relation used to order operands in SCEV expressions.
static std::optional< int >	CompareSCEVComplexity (EquivalenceClasses< const SCEV * > &EqCacheSCEV, const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static void	GroupByComplexity (SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI, DominatorTree &DT)
	Given a list of SCEV objects, order them by their complexity, and group objects of the same complexity together by value.
static bool	hasHugeExpression (ArrayRef< const SCEV * > Ops)
	Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes).
template<typename FoldT , typename IsIdentityT , typename IsAbsorberT >
static const SCEV *	constantFoldAndGroupOps (ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< const SCEV * > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
	Performs a number of common optimizations on the passed Ops.
static const SCEV *	BinomialCoefficient (const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
	Compute BC(It, K). The result has width W. Assume, K > 0.
static const SCEV *	getSignedOverflowLimitForStep (const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static const SCEV *	getUnsignedOverflowLimitForStep (const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
template<typename ExtendOpTy >
static const SCEV *	getPreStartForExtend (const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
template<typename ExtendOpTy >
static const SCEV *	getExtendAddRecStart (const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static APInt	extractConstantWithoutWrapping (ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static APInt	extractConstantWithoutWrapping (ScalarEvolution &SE, const APInt &ConstantStart, const SCEV *Step)
static void	insertFoldCacheEntry (const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static bool	CollectAddOperandsWithScales (SmallDenseMap< const SCEV *, APInt, 16 > &M, SmallVectorImpl< const SCEV * > &NewOps, APInt &AccumulatedConstant, ArrayRef< const SCEV * > Ops, const APInt &Scale, ScalarEvolution &SE)
	Process the given Ops list, which is a list of operands to be added under the given scale, update the given map.
static SCEV::NoWrapFlags	StrengthenNoWrapFlags (ScalarEvolution *SE, SCEVTypes Type, const ArrayRef< const SCEV * > Ops, SCEV::NoWrapFlags Flags)
static uint64_t	umul_ov (uint64_t i, uint64_t j, bool &Overflow)
static uint64_t	Choose (uint64_t n, uint64_t k, bool &Overflow)
	Compute the result of "n choose k", the binomial coefficient.
static bool	containsConstantInAddMulChain (const SCEV *StartExpr)
	Determine if any of the operands in this SCEV are a constant or if any of the add or multiply expressions in this SCEV contain a constant.
APInt	gcd (const SCEVConstant *C1, const SCEVConstant *C2)
static bool	scevUnconditionallyPropagatesPoisonFromOperands (SCEVTypes Kind)
static bool	impliesPoison (const SCEV *AssumedPoison, const SCEV *S)
	Return true if V is poison given that AssumedPoison is already poison.
static const SCEV *	MatchNotExpr (const SCEV *Expr)
	If Expr computes ~A, return A else return nullptr.
static void	PushDefUseChildren (Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
	Push users of the given Instruction onto the given Worklist.
static std::optional< BinaryOp >	MatchBinaryOp (Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
	Try to map V into a BinaryOp, and return std::nullopt on failure.
static Type *	isSimpleCastedPHI (const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
	Helper function to createAddRecFromPHIWithCasts.
static const Loop *	isIntegerLoopHeaderPHI (const PHINode *PN, LoopInfo &LI)
static bool	BrPHIToSelect (DominatorTree &DT, BranchInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
bool	SCEVMinMaxExprContains (const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static std::optional< const SCEV * >	createNodeForSelectViaUMinSeq (ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static std::optional< const SCEV * >	createNodeForSelectViaUMinSeq (ScalarEvolution *SE, Value *Cond, Value *TrueVal, Value *FalseVal)
static std::optional< ConstantRange >	GetRangeFromMetadata (Value *V)
	Helper method to assign a range to V from metadata present in the IR.
static ConstantRange	getRangeForAffineARHelper (APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static unsigned	getConstantTripCount (const SCEVConstant *ExitCount)
static void	PushLoopPHIs (const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
	Push PHI nodes in the header of the given loop onto the given Worklist.
static ConstantInt *	EvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static bool	CanConstantFold (const Instruction *I)
	Return true if we can constant fold an instruction of the specified type, assuming that all operands were constants.
static bool	canConstantEvolve (Instruction *I, const Loop *L)
	Determine whether this instruction can constant evolve within this loop assuming its operands can all constant evolve.
static PHINode *	getConstantEvolvingPHIOperands (Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
	getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instruction operand until reaching a loop header phi.
static PHINode *	getConstantEvolvingPHI (Value *V, const Loop *L)
	getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is derived from.
static Constant *	EvaluateExpression (Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
	EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node in the loop has the value PHIVal.
static Constant *	getOtherIncomingValue (PHINode *PN, BasicBlock *BB)
static Constant *	BuildConstantFromSCEV (const SCEV *V)
	This builds up a Constant using the ConstantExpr interface.
static const SCEV *	SolveLinEquationWithOverflow (const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE)
	Finds the minimum unsigned root of the following equation:
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > >	GetQuadraticEquation (const SCEVAddRecExpr *AddRec)
	For a given quadratic addrec, generate coefficients of the corresponding quadratic equation, multiplied by a common value to ensure that they are integers.
static std::optional< APInt >	MinOptional (std::optional< APInt > X, std::optional< APInt > Y)
	Helper function to compare optional APInts: (a) if X and Y both exist, return min(X, Y), (b) if neither X nor Y exist, return std::nullopt, (c) if exactly one of X and Y exists, return that value.
static std::optional< APInt >	TruncIfPossible (std::optional< APInt > X, unsigned BitWidth)
	Helper function to truncate an optional APInt to a given BitWidth.
static std::optional< APInt >	SolveQuadraticAddRecExact (const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
	Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt >	SolveQuadraticAddRecRange (const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
	Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static bool	HasSameValue (const SCEV *A, const SCEV *B)
	SCEV structural equivalence is usually sufficient for testing whether two expressions are equal, however for the purposes of looking for a condition guarding a loop, it can be useful to be a little more general, since a front-end may have replicated the controlling expression.
static bool	MatchBinarySub (const SCEV *S, const SCEV *&LHS, const SCEV *&RHS)
template<typename MinMaxExprType >
static bool	IsMinMaxConsistingOf (const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
	Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static bool	IsKnownPredicateViaAddRecStart (ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
static bool	IsKnownPredicateViaMinOrMax (ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
	Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool	isKnownPredicateExtendIdiom (ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
static void	PrintSCEVWithTypeHint (raw_ostream &OS, const SCEV *S)
	When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which are otherwise hard to disambiguate.
static void	PrintLoopInfo (raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
raw_ostream &	llvm::operator<< (raw_ostream &OS, ScalarEvolution::LoopDisposition LD)
raw_ostream &	llvm::operator<< (raw_ostream &OS, ScalarEvolution::BlockDisposition BD)
	INITIALIZE_PASS_BEGIN (ScalarEvolutionWrapperPass, "scalar-evolution", "Scalar Evolution Analysis", false, true) INITIALIZE_PASS_END(ScalarEvolutionWrapperPass

Variables
static cl::opt< unsigned >	MaxBruteForceIterations ("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static cl::opt< bool, true >	VerifySCEVOpt ("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static cl::opt< bool >	VerifySCEVStrict ("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static cl::opt< bool >	VerifyIR ("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static cl::opt< unsigned >	MulOpsInlineThreshold ("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static cl::opt< unsigned >	AddOpsInlineThreshold ("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned >	MaxSCEVCompareDepth ("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static cl::opt< unsigned >	MaxSCEVOperationsImplicationDepth ("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static cl::opt< unsigned >	MaxValueCompareDepth ("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static cl::opt< unsigned >	MaxArithDepth ("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static cl::opt< unsigned >	MaxConstantEvolvingDepth ("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static cl::opt< unsigned >	MaxCastDepth ("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static cl::opt< unsigned >	MaxAddRecSize ("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned >	HugeExprThreshold ("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static cl::opt< unsigned >	RangeIterThreshold ("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static cl::opt< unsigned >	MaxLoopGuardCollectionDepth ("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recrusive loop guard collection"), cl::init(1))
static cl::opt< bool >	ClassifyExpressions ("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static cl::opt< bool >	UseExpensiveRangeSharpening ("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static cl::opt< unsigned >	MaxPhiSCCAnalysisSize ("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8))
static cl::opt< bool >	EnableFiniteLoopControl ("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static cl::opt< bool >	UseContextForNoWrapFlagInference ("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
scalar	evolution
scalar Scalar Evolution	Analysis
scalar Scalar Evolution	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "scalar-evolution"

Definition at line 139 of file ScalarEvolution.cpp.

Function Documentation

BinomialCoefficient()

static const SCEV * BinomialCoefficient ( const SCEV *  It, unsigned  K, ScalarEvolution &  SE, Type *  ResultTy  )

static

Compute BC(It, K). The result has width W. Assume, K > 0.

Definition at line 876 of file ScalarEvolution.cpp.

References llvm::countr_zero(), llvm::IntegerType::get(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getOneBitSet(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUDivExpr(), and llvm::APInt::multiplicativeInverse().

Referenced by llvm::SCEVAddRecExpr::evaluateAtIteration().

BrPHIToSelect()

static bool BrPHIToSelect ( DominatorTree &  DT, BranchInst *  BI, PHINode *  Merge, Value *&  C, Value *&  LHS, Value *&  RHS  )

static

Definition at line 5950 of file ScalarEvolution.cpp.

References assert(), llvm::CallingConv::C, llvm::DominatorTree::dominates(), llvm::BranchInst::getCondition(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlockEdge::isSingleEdge(), LHS, Merge, and RHS.

BuildConstantFromSCEV()

static Constant * BuildConstantFromSCEV ( const SCEV *  V )

static

This builds up a Constant using the ConstantExpr interface.

That way, we will return Constants for objects which aren't represented by a SCEVConstant, because SCEVConstant is restricted to ConstantInt. Returns NULL if the SCEV isn't representable as a Constant.

Definition at line 9882 of file ScalarEvolution.cpp.

References assert(), BuildConstantFromSCEV(), llvm::CallingConv::C, llvm::ConstantExpr::getAdd(), llvm::ConstantExpr::getGetElementPtr(), llvm::Type::getInt8Ty(), llvm::SCEVCastExpr::getOperand(), llvm::ConstantExpr::getPtrToInt(), llvm::ConstantExpr::getTrunc(), llvm::SCEVCastExpr::getType(), llvm::Value::getType(), llvm::Type::isPointerTy(), llvm_unreachable, llvm::SCEVNAryExpr::operands(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

Referenced by BuildConstantFromSCEV().

canConstantEvolve()

static bool canConstantEvolve ( Instruction *  I, const Loop *  L  )

static

Determine whether this instruction can constant evolve within this loop assuming its operands can all constant evolve.

Definition at line 9563 of file ScalarEvolution.cpp.

References CanConstantFold(), and I.

Referenced by EvaluateExpression(), getConstantEvolvingPHI(), and getConstantEvolvingPHIOperands().

CanConstantFold()

static bool CanConstantFold ( const Instruction *  I )

static

Return true if we can constant fold an instruction of the specified type, assuming that all operands were constants.

Definition at line 9549 of file ScalarEvolution.cpp.

References llvm::canConstantFoldCallTo(), and I.

Referenced by canConstantEvolve().

Choose()

static uint64_t Choose ( uint64_t  n, uint64_t  k, bool &  Overflow  )

static

Compute the result of "n choose k", the binomial coefficient.

If an intermediate computation overflows, Overflow will be set and the return will be garbage. Overflow is not cleared on absence of overflow.

Definition at line 3060 of file ScalarEvolution.cpp.

References umul_ov().

Referenced by llvm::ScalarEvolution::getMulExpr().

CollectAddOperandsWithScales()

static bool CollectAddOperandsWithScales ( SmallDenseMap< const SCEV *, APInt, 16 > &  M, SmallVectorImpl< const SCEV * > &  NewOps, APInt &  AccumulatedConstant, ArrayRef< const SCEV * >  Ops, const APInt &  Scale, ScalarEvolution &  SE  )

static

Process the given Ops list, which is a list of operands to be added under the given scale, update the given map.

This is a helper function for getAddRecExpr. As an example of what it does, given a sequence of operands that would form an add expression like this:

m + n + 13 + (A * (o + p + (B * (q + m + 29)))) + r + (-1 * r)

where A and B are constants, update the map with these values:

(m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)

and add 13 + A*B*29 to AccumulatedConstant. This will allow getAddRecExpr to produce this:

13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)

This form often exposes folding opportunities that are hidden in the original operand list.

Return true iff it appears that any interesting folding opportunities may be exposed. This helps getAddRecExpr short-circuit extra work in the common case where no interesting opportunities are present, and is also used as a check to avoid infinite recursion.

Definition at line 2251 of file ScalarEvolution.cpp.

References llvm::Add, llvm::CallingConv::C, CollectAddOperandsWithScales(), llvm::drop_begin(), llvm::ScalarEvolution::getMulExpr(), llvm::Mul, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::ArrayRef< T >::size().

Referenced by CollectAddOperandsWithScales(), and llvm::ScalarEvolution::getAddExpr().

CompareSCEVComplexity()

static std::optional< int > CompareSCEVComplexity ( EquivalenceClasses< const SCEV * > &  EqCacheSCEV, const LoopInfo *const  LI, const SCEV *  LHS, const SCEV *  RHS, DominatorTree &  DT, unsigned  Depth = 0  )

static

Definition at line 656 of file ScalarEvolution.cpp.

References assert(), CompareSCEVComplexity(), CompareValueComplexity(), llvm::Depth, llvm::DominatorTree::dominates(), llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), getType(), llvm::SCEVUnknown::getValue(), llvm::EquivalenceClasses< ElemTy, Compare >::isEquivalent(), LHS, llvm_unreachable, MaxSCEVCompareDepth, RA, RHS, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, llvm::scZeroExtend, llvm::ArrayRef< T >::size(), llvm::APInt::ult(), llvm::EquivalenceClasses< ElemTy, Compare >::unionSets(), and X.

Referenced by CompareSCEVComplexity(), and GroupByComplexity().

CompareValueComplexity()

static int CompareValueComplexity ( const LoopInfo *const  LI, Value *  LV, Value *  RV, unsigned  Depth  )

static

Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and somewhat ad-hoc) relation used to order operands in SCEV expressions.

Definition at line 579 of file ScalarEvolution.cpp.

References CompareValueComplexity(), llvm::Depth, llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth(), llvm::GlobalValue::getParent(), llvm::BasicBlock::getParent(), llvm::Value::getType(), llvm::Value::getValueID(), Idx, llvm::GlobalValue::isInternalLinkage(), llvm::Type::isPointerTy(), llvm::GlobalValue::isPrivateLinkage(), MaxValueCompareDepth, RA, and llvm::seq().

Referenced by CompareSCEVComplexity(), and CompareValueComplexity().

constantFoldAndGroupOps()

template<typename FoldT , typename IsIdentityT , typename IsAbsorberT >

static const SCEV * constantFoldAndGroupOps ( ScalarEvolution &  SE, LoopInfo &  LI, DominatorTree &  DT, SmallVectorImpl< const SCEV * > &  Ops, FoldT  Fold, IsIdentityT  IsIdentity, IsAbsorberT  IsAbsorber  )

static

Performs a number of common optimizations on the passed Ops.

If the whole expression reduces down to a single operand, it will be returned.

The following optimizations are performed:

• Fold constants using the Fold function.
• Remove identity constants satisfying IsIdentity.
• If a constant satisfies IsAbsorber, return it.
• Sort operands by complexity.

Definition at line 838 of file ScalarEvolution.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::erase(), llvm::SCEVConstant::getAPInt(), llvm::ScalarEvolution::getConstant(), GroupByComplexity(), Idx, llvm::SmallVectorImpl< T >::insert(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMinMaxExpr(), and llvm::ScalarEvolution::getMulExpr().

containsConstantInAddMulChain()

static bool containsConstantInAddMulChain ( const SCEV *  StartExpr )

static

Determine if any of the operands in this SCEV are a constant or if any of the add or multiply expressions in this SCEV contain a constant.

Definition at line 3085 of file ScalarEvolution.cpp.

References F.

Referenced by llvm::ScalarEvolution::getMulExpr().

createNodeForSelectViaUMinSeq() [1/2]

static std::optional< const SCEV * > createNodeForSelectViaUMinSeq ( ScalarEvolution *  SE, const SCEV *  CondExpr, const SCEV *  TrueExpr, const SCEV *  FalseExpr  )

static

Definition at line 6213 of file ScalarEvolution.cpp.

References assert(), llvm::CallingConv::C, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getNotSCEV(), llvm::SCEV::getType(), llvm::ScalarEvolution::getUMinExpr(), llvm::Type::isIntegerTy(), and X.

Referenced by createNodeForSelectViaUMinSeq().

createNodeForSelectViaUMinSeq() [2/2]

static std::optional< const SCEV * > createNodeForSelectViaUMinSeq ( ScalarEvolution *  SE, Value *  Cond, Value *  TrueVal, Value *  FalseVal  )

static

Definition at line 6246 of file ScalarEvolution.cpp.

References Cond, createNodeForSelectViaUMinSeq(), and llvm::ScalarEvolution::getSCEV().

EvaluateConstantChrecAtConstant()

static ConstantInt * EvaluateConstantChrecAtConstant ( const SCEVAddRecExpr *  AddRec, ConstantInt *  C, ScalarEvolution &  SE  )

static

Definition at line 9395 of file ScalarEvolution.cpp.

References assert(), llvm::CallingConv::C, llvm::SCEVAddRecExpr::evaluateAtIteration(), and llvm::ScalarEvolution::getConstant().

Referenced by llvm::SCEVAddRecExpr::getNumIterationsInRange(), SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

EvaluateExpression()

static Constant * EvaluateExpression ( Value *  V, const Loop *  L, DenseMap< Instruction *, Constant * > &  Vals, const DataLayout &  DL, const TargetLibraryInfo *  TLI  )

static

EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node in the loop has the value PHIVal.

If we can't fold this expression for some reason, return null.

Definition at line 9639 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, canConstantEvolve(), llvm::ConstantFoldInstOperands(), DL, EvaluateExpression(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), and Operands.

Referenced by EvaluateExpression().

extractConstantWithoutWrapping() [1/2]

static APInt extractConstantWithoutWrapping ( ScalarEvolution &  SE, const APInt &  ConstantStart, const SCEV *  Step  )

static

Definition at line 1531 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::APInt::getBitWidth(), llvm::ScalarEvolution::getMinTrailingZeros(), llvm::APInt::trunc(), and llvm::APInt::zext().

extractConstantWithoutWrapping() [2/2]

static APInt extractConstantWithoutWrapping ( ScalarEvolution &  SE, const SCEVConstant *  ConstantTerm, const SCEVAddExpr *  WholeAddExpr  )

static

Definition at line 1510 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::CallingConv::C, llvm::SCEVConstant::getAPInt(), llvm::ScalarEvolution::getMinTrailingZeros(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), and I.

Referenced by llvm::ScalarEvolution::getSignExtendExprImpl(), and llvm::ScalarEvolution::getZeroExtendExprImpl().

gcd()

APInt gcd	(	const SCEVConstant *	C1,
		const SCEVConstant *	C2
	)

Definition at line 3569 of file ScalarEvolution.cpp.

References A, llvm::APInt::abs(), B, llvm::SCEVConstant::getAPInt(), and llvm::APIntOps::GreatestCommonDivisor().

getConstantEvolvingPHI()

static PHINode * getConstantEvolvingPHI ( Value *  V, const Loop *  L  )

static

getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is derived from.

We allow arbitrary operations along the way, but the operands of an operation must either be constants or a value derived from a constant PHI. If this expression does not fit with these constraints, return null.

Definition at line 9623 of file ScalarEvolution.cpp.

References canConstantEvolve(), getConstantEvolvingPHIOperands(), and I.

getConstantEvolvingPHIOperands()

static PHINode * getConstantEvolvingPHIOperands ( Instruction *  UseInst, const Loop *  L, DenseMap< Instruction *, PHINode * > &  PHIMap, unsigned  Depth  )

static

getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instruction operand until reaching a loop header phi.

Definition at line 9581 of file ScalarEvolution.cpp.

References canConstantEvolve(), llvm::Depth, getConstantEvolvingPHIOperands(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), MaxConstantEvolvingDepth, llvm::User::operands(), P, and PHI.

Referenced by getConstantEvolvingPHI(), and getConstantEvolvingPHIOperands().

getConstantTripCount()

static unsigned getConstantTripCount ( const SCEVConstant *  ExitCount )

static

Definition at line 8223 of file ScalarEvolution.cpp.

References llvm::APInt::getActiveBits(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::ConstantInt::getZExtValue().

Referenced by llvm::ScalarEvolution::getSmallConstantMaxTripCount(), and llvm::ScalarEvolution::getSmallConstantTripCount().

getExtendAddRecStart()

template<typename ExtendOpTy >

static const SCEV * getExtendAddRecStart ( const SCEVAddRecExpr *  AR, Type *  Ty, ScalarEvolution *  SE, unsigned  Depth  )

static

Definition at line 1416 of file ScalarEvolution.cpp.

References llvm::Depth, llvm::ScalarEvolution::getAddExpr(), llvm::SCEVAddRecExpr::getStart(), and llvm::SCEVAddRecExpr::getStepRecurrence().

getOtherIncomingValue()

static Constant * getOtherIncomingValue ( PHINode *  PN, BasicBlock *  BB  )

static

Definition at line 9681 of file ScalarEvolution.cpp.

References llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), and llvm::PHINode::getNumIncomingValues().

getPreStartForExtend()

template<typename ExtendOpTy >

static const SCEV * getPreStartForExtend ( const SCEVAddRecExpr *  AR, Type *  Ty, ScalarEvolution *  SE, unsigned  Depth  )

static

Definition at line 1339 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::BitWidth, llvm::Depth, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNUW, llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getContext(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::isKnownPositive(), llvm::ScalarEvolution::isLoopEntryGuardedByCond(), llvm::ScalarEvolution::maskFlags(), llvm::SCEVNAryExpr::operands(), llvm::ScalarEvolution::setNoWrapFlags(), and llvm::SmallVectorBase< Size_T >::size().

GetQuadraticEquation()

static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation ( const SCEVAddRecExpr *  AddRec )

static

For a given quadratic addrec, generate coefficients of the corresponding quadratic equation, multiplied by a common value to ensure that they are integers.

The returned value is a tuple { A, B, C, M, BitWidth }, where Ax^2 + Bx + C is the quadratic function, M is the value that A, B and C were multiplied by, and BitWidth is the bit width of the original addrec coefficients. This function returns std::nullopt if the addrec coefficients are not compile- time constants.

Definition at line 10262 of file ScalarEvolution.cpp.

References A, assert(), B, llvm::BitWidth, llvm::CallingConv::C, llvm::dbgs(), llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), LLVM_DEBUG, N, and NC.

Referenced by SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

getRangeForAffineARHelper()

static ConstantRange getRangeForAffineARHelper ( APInt  Step, const ConstantRange &  StartRange, const APInt &  MaxBECount, bool  Signed  )

static

Definition at line 6982 of file ScalarEvolution.cpp.

References llvm::APInt::abs(), assert(), llvm::BitWidth, llvm::ConstantRange::contains(), llvm::APInt::getBitWidth(), llvm::ConstantRange::getBitWidth(), llvm::ConstantRange::getLower(), llvm::APInt::getMaxValue(), llvm::ConstantRange::getNonEmpty(), llvm::ConstantRange::getUpper(), llvm::ConstantRange::isFullSet(), llvm::APInt::isNegative(), llvm::Offset, Signed, llvm::APInt::udiv(), and llvm::APInt::ult().

GetRangeFromMetadata()

static std::optional< ConstantRange > GetRangeFromMetadata ( Value *  V )

static

Helper method to assign a range to V from metadata present in the IR.

Definition at line 6417 of file ScalarEvolution.cpp.

References A, llvm::getConstantRangeFromMetadata(), I, and Range.

getSignedOverflowLimitForStep()

static const SCEV * getSignedOverflowLimitForStep ( const SCEV *  Step, ICmpInst::Predicate *  Pred, ScalarEvolution *  SE  )

static

Definition at line 1247 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::ScalarEvolution::getConstant(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getSignedRangeMax(), llvm::ScalarEvolution::getSignedRangeMin(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::ScalarEvolution::isKnownNegative(), and llvm::ScalarEvolution::isKnownPositive().

getUnsignedOverflowLimitForStep()

static const SCEV * getUnsignedOverflowLimitForStep ( const SCEV *  Step, ICmpInst::Predicate *  Pred, ScalarEvolution *  SE  )

static

Definition at line 1267 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::ScalarEvolution::getConstant(), llvm::APInt::getMinValue(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUnsignedRangeMax(), and llvm::CmpInst::ICMP_ULT.

GroupByComplexity()

static void GroupByComplexity ( SmallVectorImpl< const SCEV * > &  Ops, LoopInfo *  LI, DominatorTree &  DT  )

static

Given a list of SCEV objects, order them by their complexity, and group objects of the same complexity together by value.

When this routine is finished, we know that any duplicates in the vector are consecutive and that complexity is monotonically increasing.

Note that we go take special precautions to ensure that we get deterministic results from this routine. In other words, we don't want the results of this to depend on where the addresses of various SCEV objects happened to land in memory.

Definition at line 774 of file ScalarEvolution.cpp.

References CompareSCEVComplexity(), llvm::SCEV::getSCEVType(), LHS, RHS, llvm::SmallVectorBase< Size_T >::size(), llvm::stable_sort(), and std::swap().

Referenced by constantFoldAndGroupOps().

hasHugeExpression()

static bool hasHugeExpression ( ArrayRef< const SCEV * >  Ops )

static

Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes).

Definition at line 822 of file ScalarEvolution.cpp.

References llvm::any_of(), llvm::SCEV::getExpressionSize(), and HugeExprThreshold.

Referenced by llvm::ScalarEvolution::getAddExpr(), and llvm::ScalarEvolution::getMulExpr().

HasSameValue()

static bool HasSameValue ( const SCEV *  A, const SCEV *  B  )

static

SCEV structural equivalence is usually sufficient for testing whether two expressions are equal, however for the purposes of looking for a condition guarding a loop, it can be useful to be a little more general, since a front-end may have replicated the controlling expression.

Definition at line 10717 of file ScalarEvolution.cpp.

References A, and B.

Referenced by llvm::ScalarEvolution::SimplifyICmpOperands().

impliesPoison()

static bool impliesPoison ( const SCEV *  AssumedPoison, const SCEV *  S  )

static

Return true if V is poison given that AssumedPoison is already poison.

Definition at line 4136 of file ScalarEvolution.cpp.

References llvm::set_is_subset(), and llvm::visitAll().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	ScalarEvolutionWrapperPass	,
		"scalar-evolution"	,
		"Scalar Evolution Analysis"	,
		false	,
		true
	)

insertFoldCacheEntry()

static void insertFoldCacheEntry ( const ScalarEvolution::FoldID &  ID, const SCEV *  S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &  FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &  FoldCacheUser  )

static

Definition at line 1542 of file ScalarEvolution.cpp.

References assert(), llvm::count(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and std::swap().

Referenced by llvm::ScalarEvolution::getSignExtendExpr(), and llvm::ScalarEvolution::getZeroExtendExpr().

isIntegerLoopHeaderPHI()

static const Loop * isIntegerLoopHeaderPHI ( const PHINode *  PN, LoopInfo &  LI  )

static

Definition at line 5389 of file ScalarEvolution.cpp.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::Value::getType(), and llvm::Type::isIntegerTy().

Referenced by llvm::ScalarEvolution::createAddRecFromPHIWithCasts().

isKnownPredicateExtendIdiom()

static bool isKnownPredicateExtendIdiom ( ICmpInst::Predicate  Pred, const SCEV *  LHS, const SCEV *  RHS  )

static

Definition at line 12725 of file ScalarEvolution.cpp.

References llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, LHS, llvm_unreachable, llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_SExt(), llvm::SCEVPatternMatch::m_scev_ZExt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), RHS, and std::swap().

IsKnownPredicateViaAddRecStart()

static bool IsKnownPredicateViaAddRecStart ( ScalarEvolution &  SE, ICmpInst::Predicate  Pred, const SCEV *  LHS, const SCEV *  RHS  )

static

Definition at line 12491 of file ScalarEvolution.cpp.

References llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownPredicate(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isSigned(), LHS, and RHS.

IsKnownPredicateViaMinOrMax()

static bool IsKnownPredicateViaMinOrMax ( ScalarEvolution &  SE, ICmpInst::Predicate  Pred, const SCEV *  LHS, const SCEV *  RHS  )

static

Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?

Definition at line 12525 of file ScalarEvolution.cpp.

References llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, LHS, llvm_unreachable, RHS, and std::swap().

IsMinMaxConsistingOf()

template<typename MinMaxExprType >

static bool IsMinMaxConsistingOf ( const SCEV *  MaybeMinMaxExpr, const SCEV *  Candidate  )

static

Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?

Definition at line 12482 of file ScalarEvolution.cpp.

References llvm::is_contained().

isSimpleCastedPHI()

static Type * isSimpleCastedPHI ( const SCEV *  Op, const SCEVUnknown *  SymbolicPHI, bool &  Signed, ScalarEvolution &  SE  )

static

Helper function to createAddRecFromPHIWithCasts.

We have a phi node whose symbolic (unknown) SCEV is SymbolicPHI, which is updated via the loop backedge by a SCEVAddExpr, possibly also with a few casts on the way. This function checks if Op, an operand of this SCEVAddExpr, follows one of the following patterns: Op == (SExt ix (Trunc iy (SymbolicPHI) to ix) to iy) Op == (ZExt ix (Trunc iy (SymbolicPHI) to ix) to iy) If the SCEV expression of Op conforms with one of the expected patterns we return the type of the truncation operation, and indicate whether the truncated type should be treated as signed/unsigned by setting Signed to true/false, respectively.

Definition at line 5353 of file ScalarEvolution.cpp.

References llvm::SCEVCastExpr::getOperand(), llvm::SCEVCastExpr::getType(), llvm::SCEVUnknown::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), Signed, and X.

MatchBinaryOp()

static std::optional< BinaryOp > MatchBinaryOp ( Value *  V, const DataLayout &  DL, AssumptionCache &  AC, const DominatorTree &  DT, const Instruction *  CxtI  )

static

Try to map V into a BinaryOp, and return std::nullopt on failure.

Definition at line 5247 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::APInt::getOneBitSet(), II, llvm::isOverflowIntrinsicNoWrap(), Signed, and X.

MatchBinarySub()

static bool MatchBinarySub ( const SCEV *  S, const SCEV *&  LHS, const SCEV *&  RHS  )

static

Definition at line 10741 of file ScalarEvolution.cpp.

References llvm::Add, LHS, and RHS.

Referenced by llvm::ScalarEvolution::SimplifyICmpOperands().

MatchNotExpr()

static const SCEV * MatchNotExpr ( const SCEV *  Expr )

static

If Expr computes ~A, return A else return nullptr.

Definition at line 4581 of file ScalarEvolution.cpp.

References llvm::Add, llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), and llvm::SCEV::isAllOnesValue().

Referenced by llvm::ScalarEvolution::getNotSCEV().

MinOptional()

static std::optional< APInt > MinOptional ( std::optional< APInt >  X, std::optional< APInt >  Y  )

static

Helper function to compare optional APInts: (a) if X and Y both exist, return min(X, Y), (b) if neither X nor Y exist, return std::nullopt, (c) if exactly one of X and Y exists, return that value.

Definition at line 10315 of file ScalarEvolution.cpp.

References llvm::APInt::slt(), X, and Y.

Referenced by SolveQuadraticAddRecRange().

PrintLoopInfo()

static void PrintLoopInfo ( raw_ostream &  OS, ScalarEvolution *  SE, const Loop *  L  )

static

Definition at line 13729 of file ScalarEvolution.cpp.

References assert(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase< Size_T >::empty(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::ScalarEvolution::getExitCount(), llvm::Value::getName(), llvm::ScalarEvolution::getPredicatedBackedgeTakenCount(), llvm::ScalarEvolution::getPredicatedConstantMaxBackedgeTakenCount(), llvm::ScalarEvolution::getPredicatedExitCount(), llvm::ScalarEvolution::getPredicatedSymbolicMaxBackedgeTakenCount(), llvm::ScalarEvolution::getSmallConstantTripMultiple(), llvm::ScalarEvolution::getSymbolicMaxBackedgeTakenCount(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), I, llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero(), OS, P, PrintLoopInfo(), PrintSCEVWithTypeHint(), llvm::SmallVectorBase< Size_T >::size(), and llvm::ScalarEvolution::SymbolicMaximum.

Referenced by llvm::ScalarEvolution::print(), and PrintLoopInfo().

PrintSCEVWithTypeHint()

static void PrintSCEVWithTypeHint ( raw_ostream &  OS, const SCEV *  S  )

static

When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which are otherwise hard to disambiguate.

Definition at line 13723 of file ScalarEvolution.cpp.

References llvm::SCEV::getType(), and OS.

Referenced by PrintLoopInfo().

PushDefUseChildren()

static void PushDefUseChildren ( Instruction *  I, SmallVectorImpl< Instruction * > &  Worklist, SmallPtrSetImpl< Instruction * > &  Visited  )

static

Push users of the given Instruction onto the given Worklist.

Definition at line 4847 of file ScalarEvolution.cpp.

References I, llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

PushLoopPHIs()

static void PushLoopPHIs ( const Loop *  L, SmallVectorImpl< Instruction * > &  Worklist, SmallPtrSetImpl< Instruction * > &  Visited  )

static

Push PHI nodes in the header of the given loop onto the given Worklist.

Definition at line 8378 of file ScalarEvolution.cpp.

References llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::ScalarEvolution::forgetLoop().

SCEVMinMaxExprContains()

bool SCEVMinMaxExprContains	(	const SCEV *	Root,
		const SCEV *	OperandToFind,
		SCEVTypes	RootKind
	)

Definition at line 6069 of file ScalarEvolution.cpp.

References llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(), llvm::SCEV::getSCEVType(), llvm::scZeroExtend, and llvm::visitAll().

scevUnconditionallyPropagatesPoisonFromOperands()

static bool scevUnconditionallyPropagatesPoisonFromOperands ( SCEVTypes  Kind )

static

Definition at line 4077 of file ScalarEvolution.cpp.

References llvm_unreachable, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

SolveLinEquationWithOverflow()

static const SCEV * SolveLinEquationWithOverflow ( const APInt &  A, const SCEV *  B, SmallVectorImpl< const SCEVPredicate * > *  Predicates, ScalarEvolution &  SE  )

static

Finds the minimum unsigned root of the following equation:

A * X = B (mod N)

where N = 2^BW and BW is the common bit width of A and B. The signedness of A and B isn't important.

If the equation does not have a solution, SCEVCouldNotCompute is returned.

Definition at line 10199 of file ScalarEvolution.cpp.

References A, assert(), B, D, llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ScalarEvolution::getEqualPredicate(), llvm::ScalarEvolution::getMinTrailingZeros(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getOneBitSet(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUDivExactExpr(), llvm::ScalarEvolution::getURemExpr(), llvm::ScalarEvolution::getZero(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::ScalarEvolution::isKnownPredicate(), llvm::APInt::multiplicativeInverse(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::APInt::zext().

SolveQuadraticAddRecExact()

static std::optional< APInt > SolveQuadraticAddRecExact ( const SCEVAddRecExpr *  AddRec, ScalarEvolution &  SE  )

static

Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.

The values L, M, N are assumed to be signed, and they should all have the same bit widths. Find the least n >= 0 such that c(n) = 0 in the arithmetic modulo 2^BW, where BW is the bit width of the addrec's coefficients. If the calculated value is a BW-bit integer (for BW > 1), it will be returned as such, otherwise the bit width of the returned value may be greater than BW.

This function returns std::nullopt if (a) the addrec coefficients are not constant, or (b) SolveQuadraticEquationWrap was unable to find a solution. For cases like x^2 = 5, no integer solutions exist, in other cases an integer solution may exist, but SolveQuadraticEquationWrap may fail to find it.

Definition at line 10364 of file ScalarEvolution.cpp.

References A, B, llvm::BitWidth, llvm::CallingConv::C, llvm::dbgs(), EvaluateConstantChrecAtConstant(), llvm::ScalarEvolution::getContext(), GetQuadraticEquation(), LLVM_DEBUG, llvm::APIntOps::SolveQuadraticEquationWrap(), TruncIfPossible(), and X.

SolveQuadraticAddRecRange()

static std::optional< APInt > SolveQuadraticAddRecRange ( const SCEVAddRecExpr *  AddRec, const ConstantRange &  Range, ScalarEvolution &  SE  )

static

Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.

The values M, N are assumed to be signed, and they should all have the same bit widths. Find the least n such that c(n) does not belong to the given range, while c(n-1) does.

This function returns std::nullopt if (a) the addrec coefficients are not constant, or (b) SolveQuadraticEquationWrap was unable to find a solution for the bounds of the range.

Definition at line 10397 of file ScalarEvolution.cpp.

References A, assert(), B, llvm::BitWidth, llvm::CallingConv::C, llvm::ConstantRange::contains(), llvm::dbgs(), EvaluateConstantChrecAtConstant(), llvm::ScalarEvolution::getContext(), llvm::ConstantRange::getLower(), llvm::SCEVNAryExpr::getOperand(), GetQuadraticEquation(), llvm::SCEVAddRecExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ConstantRange::getUpper(), llvm::ConstantInt::getValue(), llvm::SCEV::isZero(), LLVM_DEBUG, llvm::Lower, MinOptional(), Range, llvm::APInt::sext(), llvm::APIntOps::SolveQuadraticEquationWrap(), TruncIfPossible(), llvm::Upper, and X.

Referenced by llvm::SCEVAddRecExpr::getNumIterationsInRange().

STATISTIC() [1/3]

STATISTIC	(	NumBruteForceTripCountsComputed	,
		"Number of loops with trip counts computed by force"
	)

STATISTIC() [2/3]

STATISTIC	(	NumExitCountsComputed	,
		"Number of loop exits with predictable exit counts"
	)

STATISTIC() [3/3]

STATISTIC	(	NumExitCountsNotComputed	,
		"Number of loop exits without predictable exit counts"
	)

StrengthenNoWrapFlags()

static SCEV::NoWrapFlags StrengthenNoWrapFlags ( ScalarEvolution *  SE, SCEVTypes  Type, const ArrayRef< const SCEV * >  Ops, SCEV::NoWrapFlags  Flags  )

static

Definition at line 2439 of file ScalarEvolution.cpp.

References llvm::all_of(), assert(), llvm::CallingConv::C, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::ScalarEvolution::getSignedRange(), llvm::ScalarEvolution::getUnsignedRange(), llvm::ScalarEvolution::hasFlags(), llvm::ScalarEvolution::isKnownNonNegative(), llvm_unreachable, llvm::ConstantRange::makeGuaranteedNoWrapRegion(), llvm::ScalarEvolution::maskFlags(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, llvm::ScalarEvolution::setFlags(), and llvm::ArrayRef< T >::size().

Referenced by llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getMulExpr().

TruncIfPossible()

static std::optional< APInt > TruncIfPossible ( std::optional< APInt >  X, unsigned  BitWidth  )

static

Helper function to truncate an optional APInt to a given BitWidth.

When solving addrec-related equations, it is preferable to return a value that has the same bit width as the original addrec's coefficients. If the solution fits in the original bit width, truncate it (except for i1). Returning a value of a different bit width may inhibit some optimizations.

In general, a solution to a quadratic equation generated from an addrec may require BW+1 bits, where BW is the bit width of the addrec's coefficients. The reason is that the coefficients of the quadratic equation are BW+1 bits wide (to avoid truncation when converting from the addrec to the equation).

Definition at line 10339 of file ScalarEvolution.cpp.

References llvm::BitWidth, llvm::isIntN(), and X.

Referenced by SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

umul_ov()

static uint64_t umul_ov ( uint64_t  i, uint64_t  j, bool &  Overflow  )

static

Definition at line 3051 of file ScalarEvolution.cpp.

Referenced by Choose(), llvm::SelectionDAG::computeKnownBits(), and llvm::ScalarEvolution::getMulExpr().

Variable Documentation

AddOpsInlineThreshold

cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500)) ( "scev-addops-inline-threshold"  , cl::Hidden  , cl::desc("Threshold for inlining addition operands into a SCEV")  , cl::init(500)    )

static

Referenced by llvm::ScalarEvolution::getAddExpr().

Analysis

scalar Scalar Evolution Analysis

Definition at line 14697 of file ScalarEvolution.cpp.

ClassifyExpressions

cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction")) ( "scalar-evolution-classify-expressions"  , cl::Hidden  , cl::init(true)  , cl::desc("When printing analysis, include information on every instruction")    )

static

Referenced by llvm::ScalarEvolution::print().

EnableFiniteLoopControl

cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true)) ( "scalar-evolution-finite-loop"  , cl::Hidden  , cl::desc("Handle <= and >= in finite loops")  , cl::init(true)    )

static

evolution

scalar evolution

Definition at line 14696 of file ScalarEvolution.cpp.

false

scalar Scalar Evolution false

Definition at line 14697 of file ScalarEvolution.cpp.

HugeExprThreshold

cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096)) ( "scalar-evolution-huge-expr-threshold"  , cl::Hidden  , cl::desc("Size of the expression which is considered huge")  , cl::init(4096)    )

static

Referenced by hasHugeExpression().

MaxAddRecSize

cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8)) ( "scalar-evolution-max-add-rec-size"  , cl::Hidden  , cl::desc("Max coefficients in AddRec during evolving")  , cl::init(8)    )

static

Referenced by llvm::ScalarEvolution::getMulExpr().

MaxArithDepth

cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32)) ( "scalar-evolution-max-arith-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive arithmetics")  , cl::init(32)    )

static

Referenced by llvm::ScalarEvolution::getAddExpr(), and llvm::ScalarEvolution::getMulExpr().

MaxBruteForceIterations

cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100)) ( "scalar-evolution-max-iterations"  , cl::ReallyHidden  , cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop")  , cl::init(100)    )

static

MaxCastDepth

cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8)) ( "scalar-evolution-max-cast-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive SExt/ZExt/Trunc")  , cl::init(8)    )

static

Referenced by llvm::ScalarEvolution::getSignExtendExprImpl(), llvm::ScalarEvolution::getTruncateExpr(), and llvm::ScalarEvolution::getZeroExtendExprImpl().

MaxConstantEvolvingDepth

cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32)) ( "scalar-evolution-max-constant-evolving-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive constant evolving")  , cl::init(32)    )

static

Referenced by getConstantEvolvingPHIOperands().

MaxLoopGuardCollectionDepth

cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recrusive loop guard collection"), cl::init(1)) ( "scalar-evolution-max-loop-guard-collection-depth"  , cl::Hidden  , cl::desc("Maximum depth for recrusive loop guard collection")  , cl::init(1)    )

static

MaxPhiSCCAnalysisSize

cl::opt< unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8)) ( "scalar-evolution-max-scc-analysis-depth"  , cl::Hidden  , cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components")  , cl::init(8)    )

static

MaxSCEVCompareDepth

cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32)) ( "scalar-evolution-max-scev-compare-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive SCEV complexity comparisons")  , cl::init(32)    )

static

Referenced by CompareSCEVComplexity().

MaxSCEVOperationsImplicationDepth

cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2)) ( "scalar-evolution-max-scev-operations-implication-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive SCEV operations implication analysis")  , cl::init(2)    )

static

MaxValueCompareDepth

cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2)) ( "scalar-evolution-max-value-compare-depth"  , cl::Hidden  , cl::desc("Maximum depth of recursive value complexity comparisons")  , cl::init(2)    )

static

Referenced by CompareValueComplexity().

MulOpsInlineThreshold

cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32)) ( "scev-mulops-inline-threshold"  , cl::Hidden  , cl::desc("Threshold for inlining multiplication operands into a SCEV")  , cl::init(32)    )

static

Referenced by llvm::ScalarEvolution::getMulExpr().

RangeIterThreshold

cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32)) ( "scev-range-iter-threshold"  , cl::Hidden  , cl::desc("Threshold for switching to iteratively computing SCEV ranges")  , cl::init(32)    )

static

UseContextForNoWrapFlagInference

cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true)) ( "scalar-evolution-use-context-for-no-wrap-flag-strenghening"  , cl::Hidden  , cl::desc("Infer nuw/nsw flags using context where suitable")  , cl::init(true)    )

static

Referenced by llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp().

UseExpensiveRangeSharpening

cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time")) ( "scalar-evolution-use-expensive-range-sharpening"  , cl::Hidden  , cl::init(false)  , cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time")    )

static

VerifyIR

cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false)) ( "scev-verify-ir"  , cl::Hidden  , cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)")  , cl::init(false)    )

static

Referenced by llvm::ScalarEvolution::isBasicBlockEntryGuardedByCond(), and llvm::ScalarEvolution::isLoopBackedgeGuardedByCond().

VerifySCEVOpt

cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)")) ( "verify-scev"  , cl::Hidden  , cl::location(VerifySCEV)  , cl::desc("Verify ScalarEvolution's backedge taken counts (slow)")    )

static

VerifySCEVStrict

cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed")) ( "verify-scev-strict"  , cl::Hidden  , cl::desc("Enable stricter verification with -verify-scev is passed")    )

static

Referenced by llvm::ScalarEvolution::verify().