Movatterモバイル変換

#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 loopexits with predictable exit counts")

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

	STATISTIC (NumBruteForceTripCountsComputed, "Number ofloops 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.

staticbool	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 >
staticconst 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`.

staticconst SCEV *	BinomialCoefficient (const SCEV It,unsigned K,ScalarEvolution &SE,Type ResultTy)
	Compute BC(It, K). The result has width W. Assume, K > 0.

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

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

template<typename ExtendOpTy >
staticconst SCEV *	getPreStartForExtend (const SCEVAddRecExpr AR,Type Ty,ScalarEvolution *SE,unsigned Depth)

template<typename ExtendOpTy >
staticconst SCEV *	getExtendAddRecStart (const SCEVAddRecExpr AR,Type Ty,ScalarEvolution *SE,unsigned Depth)

staticAPInt	extractConstantWithoutWrapping (ScalarEvolution &SE,const SCEVConstant ConstantTerm,const SCEVAddExpr WholeAddExpr)

staticAPInt	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)

staticbool	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.

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

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

staticuint64_t	Choose (uint64_t n,uint64_t k,bool &Overflow)
	Compute the result of "n choose k", the binomial coefficient.

staticbool	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)

staticbool	scevUnconditionallyPropagatesPoisonFromOperands (SCEVTypes Kind)

staticbool	impliesPoison (const SCEV AssumedPoison,const SCEV S)
	Return true if V is poison given that AssumedPoison is already poison.

staticconst 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.

staticType *	isSimpleCastedPHI (const SCEV Op,const SCEVUnknown SymbolicPHI,bool &Signed,ScalarEvolution &SE)
	Helper function to createAddRecFromPHIWithCasts.

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

staticbool	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.

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

staticunsigned	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.

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

staticbool	CanConstantFold (const Instruction *I)
	Return true if we can constant fold an instruction of the specified type, assuming that all operands were constants.

staticbool	canConstantEvolve (Instruction I,const Loop L)
	Determine whether this instruction can constant evolve within this loop assuming its operands can all constant evolve.

staticPHINode *	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.

staticPHINode *	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.

staticConstant *	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.

staticConstant *	getOtherIncomingValue (PHINode PN,BasicBlock BB)

staticConstant *	BuildConstantFromSCEV (const SCEV *V)
	This builds up a Constant using the ConstantExpr interface.

staticconst 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.

staticbool	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.

staticbool	MatchBinarySub (const SCEV S,const SCEV &LHS,const SCEV *&RHS)

template<typename MinMaxExprType >
staticbool	IsMinMaxConsistingOf (const SCEV MaybeMinMaxExpr,const SCEV Candidate)
	Is MaybeMinMaxExpr an (U\|S)(Min\|Max) of Candidate and some other values?

staticbool	IsKnownPredicateViaAddRecStart (ScalarEvolution &SE,CmpPredicate Pred,const SCEV LHS,const SCEV RHS)

staticbool	IsKnownPredicateViaMinOrMax (ScalarEvolution &SE,CmpPredicate 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?

staticbool	isKnownPredicateExtendIdiom (CmpPredicate 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
staticcl::opt<unsigned >	MaxBruteForceIterations ("scalar-evolution-max-iterations", cl::ReallyHidden,cl::desc("Maximum number of iterationsSCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))

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

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

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

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

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

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

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

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

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

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

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

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

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

staticcl::opt<unsigned >	RangeIterThreshold ("scev-range-iter-threshold", cl::Hidden,cl::desc("Thresholdfor switching to iteratively computingSCEV ranges"), cl::init(32))

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

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

staticcl::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"))

staticcl::opt<unsigned >	MaxPhiSCCAnalysisSize ("scalar-evolution-max-scc-analysis-depth", cl::Hidden,cl::desc("Maximum amount ofnodes to processwhile searchingSCEVUnknown " "Phi strongly connected components"), cl::init(8))

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

staticcl::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 line139 of fileScalarEvolution.cpp.

Function Documentation

◆ BinomialCoefficient()

staticconst 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 line876 of fileScalarEvolution.cpp.

Referencesllvm::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(), andllvm::APInt::multiplicativeInverse().

Referenced byllvm::SCEVAddRecExpr::evaluateAtIteration().

◆ BrPHIToSelect()

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

static

Definition at line5950 of fileScalarEvolution.cpp.

Referencesassert(),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, andRHS.

◆ BuildConstantFromSCEV()

staticConstant * BuildConstantFromSCEV

(

const SCEV *

)

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 line9882 of fileScalarEvolution.cpp.

Referencesassert(),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, andllvm::scZeroExtend.

Referenced byBuildConstantFromSCEV().

◆ canConstantEvolve()

staticbool 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 line9563 of fileScalarEvolution.cpp.

ReferencesCanConstantFold(), andI.

Referenced byEvaluateExpression(),getConstantEvolvingPHI(), andgetConstantEvolvingPHIOperands().

◆ CanConstantFold()

staticbool CanConstantFold

(

const Instruction *

)

static

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

Definition at line9549 of fileScalarEvolution.cpp.

Referencesllvm::canConstantFoldCallTo(), andI.

Referenced bycanConstantEvolve().

◆ Choose()

staticuint64_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 line3060 of fileScalarEvolution.cpp.

Referencesumul_ov().

Referenced byllvm::ScalarEvolution::getMulExpr().

◆ CollectAddOperandsWithScales()

staticbool 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 line2251 of fileScalarEvolution.cpp.

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

Referenced byCollectAddOperandsWithScales(), andllvm::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 line656 of fileScalarEvolution.cpp.

Referencesassert(),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(), andX.

Referenced byCompareSCEVComplexity(), andGroupByComplexity().

◆ CompareValueComplexity()

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

static

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

Definition at line579 of fileScalarEvolution.cpp.

ReferencesCompareValueComplexity(),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, andllvm::seq().

Referenced byCompareSCEVComplexity(), andCompareValueComplexity().

◆ constantFoldAndGroupOps()

template<typename FoldT , typename IsIdentityT , typename IsAbsorberT >

staticconst 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 passedOps.

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

The following optimizations are performed:

Fold constants using theFold function.
Remove identity constants satisfyingIsIdentity.
If a constant satisfiesIsAbsorber, return it.
Sort operands by complexity.

Definition at line838 of fileScalarEvolution.cpp.

Referencesassert(),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(), andllvm::SmallVectorBase< Size_T >::size().

Referenced byllvm::ScalarEvolution::getAddExpr(),llvm::ScalarEvolution::getMinMaxExpr(), andllvm::ScalarEvolution::getMulExpr().

◆ containsConstantInAddMulChain()

staticbool 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 line3085 of fileScalarEvolution.cpp.

ReferencesF.

Referenced byllvm::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 line6213 of fileScalarEvolution.cpp.

Referencesassert(),llvm::CallingConv::C,llvm::ScalarEvolution::getAddExpr(),llvm::ScalarEvolution::getMinusSCEV(),llvm::ScalarEvolution::getNotSCEV(),llvm::SCEV::getType(),llvm::ScalarEvolution::getUMinExpr(),llvm::Type::isIntegerTy(), andX.

Referenced bycreateNodeForSelectViaUMinSeq().

◆ createNodeForSelectViaUMinSeq()[2/2]

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

static

Definition at line6246 of fileScalarEvolution.cpp.

ReferencesCond,createNodeForSelectViaUMinSeq(), andllvm::ScalarEvolution::getSCEV().

◆ EvaluateConstantChrecAtConstant()

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

static

Definition at line9395 of fileScalarEvolution.cpp.

Referencesassert(),llvm::CallingConv::C,llvm::SCEVAddRecExpr::evaluateAtIteration(), andllvm::ScalarEvolution::getConstant().

Referenced byllvm::SCEVAddRecExpr::getNumIterationsInRange(),SolveQuadraticAddRecExact(), andSolveQuadraticAddRecRange().

◆ EvaluateExpression()

staticConstant * 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 line9639 of fileScalarEvolution.cpp.

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

Referenced byEvaluateExpression().

◆ extractConstantWithoutWrapping()[1/2]

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

static

Definition at line1531 of fileScalarEvolution.cpp.

Referencesllvm::BitWidth,llvm::APInt::getBitWidth(),llvm::ScalarEvolution::getMinTrailingZeros(),llvm::APInt::trunc(), andllvm::APInt::zext().

◆ extractConstantWithoutWrapping()[2/2]

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

static

Definition at line1510 of fileScalarEvolution.cpp.

Referencesllvm::BitWidth,llvm::CallingConv::C,llvm::SCEVConstant::getAPInt(),llvm::ScalarEvolution::getMinTrailingZeros(),llvm::SCEVNAryExpr::getNumOperands(),llvm::SCEVNAryExpr::getOperand(), andI.

Referenced byllvm::ScalarEvolution::getSignExtendExprImpl(), andllvm::ScalarEvolution::getZeroExtendExprImpl().

◆ gcd()

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

Definition at line3569 of fileScalarEvolution.cpp.

ReferencesA,llvm::APInt::abs(),B,llvm::SCEVConstant::getAPInt(), andllvm::APIntOps::GreatestCommonDivisor().

◆ getConstantEvolvingPHI()

staticPHINode * 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 line9623 of fileScalarEvolution.cpp.

ReferencescanConstantEvolve(),getConstantEvolvingPHIOperands(), andI.

◆ getConstantEvolvingPHIOperands()

staticPHINode * 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 line9581 of fileScalarEvolution.cpp.

ReferencescanConstantEvolve(),llvm::Depth,getConstantEvolvingPHIOperands(),llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(),MaxConstantEvolvingDepth,llvm::User::operands(),P, andPHI.

Referenced bygetConstantEvolvingPHI(), andgetConstantEvolvingPHIOperands().

◆ getConstantTripCount()

staticunsigned getConstantTripCount

(

const SCEVConstant *

ExitCount

)

static

Definition at line8223 of fileScalarEvolution.cpp.

Referencesllvm::APInt::getActiveBits(),llvm::SCEVConstant::getValue(),llvm::ConstantInt::getValue(), andllvm::ConstantInt::getZExtValue().

Referenced byllvm::ScalarEvolution::getSmallConstantMaxTripCount(), andllvm::ScalarEvolution::getSmallConstantTripCount().

◆ getExtendAddRecStart()

template<typename ExtendOpTy >

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

static

Definition at line1416 of fileScalarEvolution.cpp.

Referencesllvm::Depth,llvm::ScalarEvolution::getAddExpr(),llvm::SCEVAddRecExpr::getStart(), andllvm::SCEVAddRecExpr::getStepRecurrence().

◆ getOtherIncomingValue()

staticConstant * getOtherIncomingValue	(	PHINode *	PN,
		BasicBlock *	BB
	)

static

Definition at line9681 of fileScalarEvolution.cpp.

Referencesllvm::PHINode::getIncomingBlock(),llvm::PHINode::getIncomingValue(), andllvm::PHINode::getNumIncomingValues().

◆ getPreStartForExtend()

template<typename ExtendOpTy >

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

static

Definition at line1339 of fileScalarEvolution.cpp.

◆ 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 line10262 of fileScalarEvolution.cpp.

ReferencesA,assert(),B,llvm::BitWidth,llvm::CallingConv::C,llvm::dbgs(),llvm::SCEVConstant::getAPInt(),llvm::APInt::getBitWidth(),llvm::SCEVNAryExpr::getNumOperands(),llvm::SCEVNAryExpr::getOperand(),LLVM_DEBUG,N, andNC.

Referenced bySolveQuadraticAddRecExact(), andSolveQuadraticAddRecRange().

◆ getRangeForAffineARHelper()

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

static

Definition at line6982 of fileScalarEvolution.cpp.

Referencesllvm::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(), andllvm::APInt::ult().

◆ GetRangeFromMetadata()

static std::optional<ConstantRange > GetRangeFromMetadata

(

Value *

)

static

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

Definition at line6417 of fileScalarEvolution.cpp.

ReferencesA,llvm::getConstantRangeFromMetadata(),I, andRange.

◆ getSignedOverflowLimitForStep()

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

static

Definition at line1247 of fileScalarEvolution.cpp.

Referencesllvm::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(), andllvm::ScalarEvolution::isKnownPositive().

◆ getUnsignedOverflowLimitForStep()

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

static

Definition at line1267 of fileScalarEvolution.cpp.

Referencesllvm::BitWidth,llvm::ScalarEvolution::getConstant(),llvm::APInt::getMinValue(),llvm::SCEV::getType(),llvm::ScalarEvolution::getTypeSizeInBits(),llvm::ScalarEvolution::getUnsignedRangeMax(), andllvm::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 line774 of fileScalarEvolution.cpp.

ReferencesCompareSCEVComplexity(),llvm::SCEV::getSCEVType(),LHS,RHS,llvm::SmallVectorBase< Size_T >::size(),llvm::stable_sort(), andstd::swap().

Referenced byconstantFoldAndGroupOps().

◆ hasHugeExpression()

staticbool hasHugeExpression

(

ArrayRef<const SCEV * >

Ops

)

static

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

Definition at line822 of fileScalarEvolution.cpp.

Referencesllvm::any_of(),llvm::SCEV::getExpressionSize(), andHugeExprThreshold.

Referenced byllvm::ScalarEvolution::getAddExpr(), andllvm::ScalarEvolution::getMulExpr().

◆ HasSameValue()

staticbool 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 line10717 of fileScalarEvolution.cpp.

ReferencesA, andB.

Referenced byllvm::ScalarEvolution::SimplifyICmpOperands().

◆ impliesPoison()

staticbool impliesPoison	(	const SCEV *	AssumedPoison,
		const SCEV *	S
	)

static

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

Definition at line4136 of fileScalarEvolution.cpp.

Referencesllvm::set_is_subset(), andllvm::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 line1542 of fileScalarEvolution.cpp.

Referencesassert(),llvm::count(),I,llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), andstd::swap().

Referenced byllvm::ScalarEvolution::getSignExtendExpr(), andllvm::ScalarEvolution::getZeroExtendExpr().

◆ isIntegerLoopHeaderPHI()

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

static

Definition at line5389 of fileScalarEvolution.cpp.

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

Referenced byllvm::ScalarEvolution::createAddRecFromPHIWithCasts().

◆ isKnownPredicateExtendIdiom()

staticbool isKnownPredicateExtendIdiom	(	CmpPredicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

static

Definition at line12722 of fileScalarEvolution.cpp.

Referencesllvm::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, andstd::swap().

◆ IsKnownPredicateViaAddRecStart()

staticbool IsKnownPredicateViaAddRecStart	(	ScalarEvolution &	SE,
		CmpPredicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

static

Definition at line12489 of fileScalarEvolution.cpp.

Referencesllvm::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, andRHS.

◆ IsKnownPredicateViaMinOrMax()

staticbool IsKnownPredicateViaMinOrMax	(	ScalarEvolution &	SE,
		CmpPredicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

static

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

Definition at line12523 of fileScalarEvolution.cpp.

Referencesllvm::CmpInst::ICMP_SGE,llvm::CmpInst::ICMP_SLE,llvm::CmpInst::ICMP_UGE,llvm::CmpInst::ICMP_ULE,LHS,llvm_unreachable,RHS, andstd::swap().

◆ IsMinMaxConsistingOf()

template<typename MinMaxExprType >

staticbool IsMinMaxConsistingOf	(	const SCEV *	MaybeMinMaxExpr,
		const SCEV *	Candidate
	)

static

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

Definition at line12480 of fileScalarEvolution.cpp.

Referencesllvm::is_contained().

◆ isSimpleCastedPHI()

staticType * 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 isSymbolicPHI, which is updated via the loop backedge by a SCEVAddExpr, possibly also with a few casts on the way. This function checks ifOp, 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 ofOp 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 settingSigned to true/false, respectively.

Definition at line5353 of fileScalarEvolution.cpp.

Referencesllvm::SCEVCastExpr::getOperand(),llvm::SCEVCastExpr::getType(),llvm::SCEVUnknown::getType(),llvm::ScalarEvolution::getTypeSizeInBits(),Signed, andX.

◆ MatchBinaryOp()

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

static

Try to mapV into a BinaryOp, and returnstd::nullopt on failure.

Definition at line5247 of fileScalarEvolution.cpp.

Referencesllvm::BitWidth,llvm::APInt::getOneBitSet(),II,llvm::isOverflowIntrinsicNoWrap(),Signed, andX.

◆ MatchBinarySub()

staticbool MatchBinarySub	(	const SCEV *	S,
		const SCEV *&	LHS,
		const SCEV *&	RHS
	)

static

Definition at line10741 of fileScalarEvolution.cpp.

Referencesllvm::Add,LHS, andRHS.

Referenced byllvm::ScalarEvolution::SimplifyICmpOperands().

◆ MatchNotExpr()

staticconst SCEV * MatchNotExpr

(

const SCEV *

Expr

)

static

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

Definition at line4581 of fileScalarEvolution.cpp.

Referencesllvm::Add,llvm::SCEVNAryExpr::getNumOperands(),llvm::SCEVNAryExpr::getOperand(), andllvm::SCEV::isAllOnesValue().

Referenced byllvm::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 line10315 of fileScalarEvolution.cpp.

Referencesllvm::APInt::slt(),X, andY.

Referenced bySolveQuadraticAddRecRange().

◆ PrintLoopInfo()

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

static

Definition at line13724 of fileScalarEvolution.cpp.

Referenced byllvm::ScalarEvolution::print(), andPrintLoopInfo().

◆ 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 line13718 of fileScalarEvolution.cpp.

Referencesllvm::SCEV::getType(), andOS.

Referenced byPrintLoopInfo().

◆ 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 line4847 of fileScalarEvolution.cpp.

ReferencesI,llvm::SmallPtrSetImpl< PtrType >::insert(), andllvm::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 line8378 of fileScalarEvolution.cpp.

Referencesllvm::SmallPtrSetImpl< PtrType >::insert(), andllvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced byllvm::ScalarEvolution::forgetLoop().

◆ SCEVMinMaxExprContains()

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

Definition at line6069 of fileScalarEvolution.cpp.

Referencesllvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(),llvm::SCEV::getSCEVType(),llvm::scZeroExtend, andllvm::visitAll().

◆ scevUnconditionallyPropagatesPoisonFromOperands()

staticbool scevUnconditionallyPropagatesPoisonFromOperands

(

SCEVTypes

Kind

)

static

Definition at line4077 of fileScalarEvolution.cpp.

Referencesllvm_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, andllvm::scZeroExtend.

◆ SolveLinEquationWithOverflow()

staticconst 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 line10199 of fileScalarEvolution.cpp.

◆ 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 line10364 of fileScalarEvolution.cpp.

ReferencesA,B,llvm::BitWidth,llvm::CallingConv::C,llvm::dbgs(),EvaluateConstantChrecAtConstant(),llvm::ScalarEvolution::getContext(),GetQuadraticEquation(),LLVM_DEBUG,llvm::APIntOps::SolveQuadraticEquationWrap(),TruncIfPossible(), andX.

◆ 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 line10397 of fileScalarEvolution.cpp.

ReferencesA,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, andX.

Referenced byllvm::SCEVAddRecExpr::getNumIterationsInRange().

◆ STATISTIC()[1/3]

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

◆ STATISTIC()[2/3]

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

◆ STATISTIC()[3/3]

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

◆ StrengthenNoWrapFlags()

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

static

Definition at line2439 of fileScalarEvolution.cpp.

Referencesllvm::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(), andllvm::ArrayRef< T >::size().

Referenced byllvm::ScalarEvolution::getAddExpr(),llvm::ScalarEvolution::getAddRecExpr(), andllvm::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 line10339 of fileScalarEvolution.cpp.

Referencesllvm::BitWidth,llvm::isIntN(), andX.

Referenced bySolveQuadraticAddRecExact(), andSolveQuadraticAddRecRange().

◆ umul_ov()

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

static

Definition at line3051 of fileScalarEvolution.cpp.

Referenced byChoose(),llvm::SelectionDAG::computeKnownBits(), andllvm::ScalarEvolution::getMulExpr().

Variable Documentation

◆ AddOpsInlineThreshold

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

static

Referenced byllvm::ScalarEvolution::getAddExpr().

◆ Analysis

scalar Scalar Evolution Analysis

Definition at line14692 of fileScalarEvolution.cpp.

◆ ClassifyExpressions

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

static

Referenced byllvm::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 line14691 of fileScalarEvolution.cpp.

◆ false

scalar Scalar Evolution false

Definition at line14692 of fileScalarEvolution.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 byhasHugeExpression().

◆ 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 byllvm::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 byllvm::ScalarEvolution::getAddExpr(), andllvm::ScalarEvolution::getMulExpr().

◆ MaxBruteForceIterations

cl::opt<unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,cl::desc("Maximum number of iterationsSCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))	(	"scalar-evolution-max-iterations"	,
		cl::ReallyHidden	,
		cl::desc("Maximum number of iterationsSCEV 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 byllvm::ScalarEvolution::getSignExtendExprImpl(),llvm::ScalarEvolution::getTruncateExpr(), andllvm::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 bygetConstantEvolvingPHIOperands().

◆ MaxLoopGuardCollectionDepth

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

static

◆ MaxPhiSCCAnalysisSize

cl::opt<unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden,cl::desc("Maximum amount ofnodes to processwhile searchingSCEVUnknown " "Phi strongly connected components"), cl::init(8))	(	"scalar-evolution-max-scc-analysis-depth"	,
		cl::Hidden	,
		cl::desc("Maximum amount ofnodes to processwhile searchingSCEVUnknown " "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 recursiveSCEV complexity comparisons"), cl::init(32))	(	"scalar-evolution-max-scev-compare-depth"	,
		cl::Hidden	,
		cl::desc("Maximum depth of recursiveSCEV complexity comparisons")	,
		cl::init(32)
	)

static

Referenced byCompareSCEVComplexity().

◆ MaxSCEVOperationsImplicationDepth

cl::opt<unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden,cl::desc("Maximum depth of recursiveSCEV operations implication analysis"), cl::init(2))	(	"scalar-evolution-max-scev-operations-implication-depth"	,
		cl::Hidden	,
		cl::desc("Maximum depth of recursiveSCEV 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 recursivevalue complexity comparisons"), cl::init(2))	(	"scalar-evolution-max-value-compare-depth"	,
		cl::Hidden	,
		cl::desc("Maximum depth of recursivevalue complexity comparisons")	,
		cl::init(2)
	)

static

Referenced byCompareValueComplexity().

◆ MulOpsInlineThreshold

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

static

Referenced byllvm::ScalarEvolution::getMulExpr().

◆ RangeIterThreshold

cl::opt<unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden,cl::desc("Thresholdfor switching to iteratively computingSCEV ranges"), cl::init(32))	(	"scev-range-iter-threshold"	,
		cl::Hidden	,
		cl::desc("Thresholdfor switching to iteratively computingSCEV 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 byllvm::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("VerifyIR correctness when making sensitiveSCEV queries (slow)"), cl::init(false))	(	"scev-verify-ir"	,
		cl::Hidden	,
		cl::desc("VerifyIR correctness when making sensitiveSCEV queries (slow)")	,
		cl::init(false)
	)

static

Referenced byllvm::ScalarEvolution::isBasicBlockEntryGuardedByCond(), andllvm::ScalarEvolution::isLoopBackedgeGuardedByCond().

◆ VerifySCEVOpt

cl::opt<bool,true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV),cl::desc("VerifyScalarEvolution's backedge taken counts (slow)"))	(	"verify-scev"	,
		cl::Hidden	,
		cl::location(VerifySCEV)	,
		cl::desc("VerifyScalarEvolution'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 byllvm::ScalarEvolution::verify().

Movatterモバイル変換

Namespaces

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ BinomialCoefficient()

◆ BrPHIToSelect()

◆ BuildConstantFromSCEV()

◆ canConstantEvolve()

◆ CanConstantFold()

◆ Choose()

◆ CollectAddOperandsWithScales()

◆ CompareSCEVComplexity()

◆ CompareValueComplexity()

◆ constantFoldAndGroupOps()

◆ containsConstantInAddMulChain()

◆ createNodeForSelectViaUMinSeq()[1/2]

◆ createNodeForSelectViaUMinSeq()[2/2]

◆ EvaluateConstantChrecAtConstant()

◆ EvaluateExpression()

◆ extractConstantWithoutWrapping()[1/2]

◆ extractConstantWithoutWrapping()[2/2]

◆ gcd()

◆ getConstantEvolvingPHI()

◆ getConstantEvolvingPHIOperands()

◆ getConstantTripCount()

◆ getExtendAddRecStart()

◆ getOtherIncomingValue()

◆ getPreStartForExtend()

◆ GetQuadraticEquation()

◆ getRangeForAffineARHelper()

◆ GetRangeFromMetadata()

◆ getSignedOverflowLimitForStep()

◆ getUnsignedOverflowLimitForStep()

◆ GroupByComplexity()

◆ hasHugeExpression()

◆ HasSameValue()

◆ impliesPoison()

◆ INITIALIZE_PASS_BEGIN()

◆ insertFoldCacheEntry()

◆ isIntegerLoopHeaderPHI()

◆ isKnownPredicateExtendIdiom()

◆ IsKnownPredicateViaAddRecStart()

◆ IsKnownPredicateViaMinOrMax()

◆ IsMinMaxConsistingOf()

◆ isSimpleCastedPHI()

◆ MatchBinaryOp()

◆ MatchBinarySub()

◆ MatchNotExpr()

◆ MinOptional()

◆ PrintLoopInfo()

◆ PrintSCEVWithTypeHint()

◆ PushDefUseChildren()

◆ PushLoopPHIs()

◆ SCEVMinMaxExprContains()

◆ scevUnconditionallyPropagatesPoisonFromOperands()

◆ SolveLinEquationWithOverflow()

◆ SolveQuadraticAddRecExact()

◆ SolveQuadraticAddRecRange()

◆ STATISTIC()[1/3]

◆ STATISTIC()[2/3]

◆ STATISTIC()[3/3]

◆ StrengthenNoWrapFlags()

◆ TruncIfPossible()

◆ umul_ov()

Variable Documentation

◆ AddOpsInlineThreshold

◆ Analysis

◆ ClassifyExpressions

◆ EnableFiniteLoopControl

◆ evolution

◆ false

◆ HugeExprThreshold

◆ MaxAddRecSize

◆ MaxArithDepth

◆ MaxBruteForceIterations

◆ MaxCastDepth