#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>
#include <variant>
#include <vector>

Classes
struct	StencilDecomposition
	Result of decomposing a SCEV expression into stencil offset form: Offset = Constant + sum(Coefficients[stride] * stride) where each stride is a loop-invariant SCEV expression. More...

Macros
#define	DEBUG_TYPE "loop-accesses"

Enumerations
enum class	StencilMergePolicy { Off , Auto , Force }

Functions
static const SCEV *	addSCEVNoOverflow (const SCEV A, const SCEV B, ScalarEvolution &SE)
	Returns `A` + `B`, if it is guaranteed not to unsigned wrap.
static const SCEV *	mulSCEVNoOverflow (const SCEV A, const SCEV B, ScalarEvolution &SE)
	Returns `A` * `B`, if it is guaranteed not to unsigned wrap.
static bool	evaluatePtrAddRecAtMaxBTCWillNotWrap (const SCEVAddRecExpr AR, const SCEV MaxBTC, const SCEV EltSize, ScalarEvolution &SE, const DataLayout &DL, DominatorTree DT, AssumptionCache *AC, std::optional< ScalarEvolution::LoopGuards > &LoopGuards)
	Return true, if evaluating `AR` at `MaxBTC` cannot wrap, because `AR` at `MaxBTC` is guaranteed inbounds of the accessed object.
static bool	isKnownNonDecreasingInLoop (const SCEV S, const Loop L, ScalarEvolution &SE)
	Return true if `S` is known to be monotonically non-decreasing (in the unsigned sense, without unsigned wrap) across iterations of `L`.
static std::pair< const SCEV , const SCEV >	getNonAffineMonotonicBounds (const Loop Lp, const SCEV PtrExpr, const SCEV EltSizeSCEV, ScalarEvolution SE)
	Try to bound a loop-variant pointer that is not an affine AddRec.
static const SCEV *	getMinFromExprs (const SCEV I, const SCEV J, ScalarEvolution *SE)
	Compare `I` and `J` and return the minimum.
static bool	addScaledStencilTerm (const SCEV *Term, int64_t Mult, unsigned Depth, StencilDecomposition &D)
	Add one term of a stencil offset to `D`.
static std::optional< StencilDecomposition >	decomposeStencilOffset (const SCEV *Expr, ScalarEvolution &SE, const Loop &L)
	Try to decompose `Expr` into a stencil offset function of loop-invariant strides: C + a1s1 + a2s2 + ... `Expr` is the difference of two access "Start" SCEVs (Start_member - Start_base).
static std::optional< APInt >	getStencilStrideUpperLimit (const StencilDecomposition &D, unsigned BitWidth)
	Find a common upper limit M for the positive strides in D.
static bool	collectStrideLimits (const StencilDecomposition &D, unsigned BitWidth, ScalarEvolution &SE, StrideLimits &Limits)
	Add to `Limits` the checks each stride s of `D` needs: 1 <= s isNeverAbove assumes every stride is 1 or more.
static bool	isNeverAbove (const StencilDecomposition &A, const StencilDecomposition &B)
	Return true if offset A is never higher than offset B.
static SmallVector< unsigned, 4 >	collectCandidateMembers (ArrayRef< StencilDecomposition > Offsets, bool ForMin)
	Find the members that can define the merged bound on one side.
static std::pair< unsigned, unsigned >	computeStencilMergeCost (const RuntimePointerChecking &RtCheck, ArrayRef< unsigned > GroupIndices, const StrideLimits &Local, const StrideLimits &Committed, unsigned NumBoundOperands)
	Local cost model: count the runtime checks required before and after replacing one DepSet's groups (`GroupIndices`) with the single merged group.
static RuntimeCheckingPtrGroup	buildMergedStencilGroup (const RuntimePointerChecking &RtCheck, ArrayRef< unsigned > AllMembers, const SCEV MergedLow, const SCEV MergedHigh, ArrayRef< unsigned > GroupIndices)
	Build the merged stencil group for one DepSet, after the cost model has decided the merge is profitable.
static DenseMap< const RuntimeCheckingPtrGroup *, unsigned >	getPtrToIdxMap (ArrayRef< RuntimeCheckingPtrGroup > CheckingGroups)
	Assign each RuntimeCheckingPtrGroup pointer an index for stable UTC output.
static bool	isNoWrap (PredicatedScalarEvolution &PSE, const SCEVAddRecExpr AR, Value Ptr, Type AccessTy, const Loop L, const DominatorTree &DT, std::optional< int64_t > Stride=std::nullopt, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
	Check whether `AR` is a non-wrapping AddRec.
static void	visitPointers (Value StartPtr, const Loop &InnermostLoop, function_ref< void(Value )> AddPointer)
static void	findForkedSCEVs (ScalarEvolution SE, const Loop L, Value Ptr, SmallVectorImpl< PointerIntPair< const SCEV , 1, bool > > &ScevList, unsigned Depth)
static bool	isSafeDependenceDistance (const DataLayout &DL, ScalarEvolution &SE, const SCEV &MaxBTC, const SCEV &Dist, uint64_t MaxStride)
	Given a dependence-distance `Dist` between two memory accesses, that have strides in the same direction whose absolute value of the maximum stride is given in `MaxStride`, in a loop whose maximum backedge taken count is `MaxBTC`, check if it is possible to prove statically that the dependence distance is larger than the range that the accesses will travel through the execution of the loop.
static bool	areStridedAccessesIndependent (uint64_t Distance, uint64_t Stride, uint64_t TypeByteSize)
	Check the dependence for two accesses with the same stride `Stride`.
static Value *	getLoopVariantGEPOperand (Value Ptr, ScalarEvolution SE, Loop *Lp)
	If `Ptr` is a GEP, which has a loop-variant operand, return that operand.
static const SCEV *	getStrideFromPointer (Value Ptr, ScalarEvolution SE, Loop *Lp)
	Get the stride of a pointer access in a loop.

Variables
static cl::opt< ElementCount, true >	VectorizationFactor ("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor))
static cl::opt< unsigned, true >	VectorizationInterleave ("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location(VectorizerParams::VectorizationInterleave))
static cl::opt< unsigned, true >	RuntimeMemoryCheckThreshold ("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8))
static cl::opt< unsigned, true >	VectorizeMemoryCheckThreshold ("vectorize-memory-check-threshold", cl::Hidden, cl::desc("The maximum allowed number of runtime memory checks"), cl::location(VectorizerParams::VectorizeMemoryCheckThreshold), cl::init(128))
static cl::opt< unsigned >	MemoryCheckMergeThreshold ("memory-check-merge-threshold", cl::Hidden, cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)"), cl::init(100))
	The maximum iterations used to merge memory checks.
static cl::opt< StencilMergePolicy >	StencilMerge ("stencil-runtime-check-merge", cl::Hidden, cl::desc("Control stencil-pattern merging of runtime memory checks"), cl::init(StencilMergePolicy::Off), cl::values(clEnumValN(StencilMergePolicy::Off, "off", "Disable stencil merge (default)"), clEnumValN(StencilMergePolicy::Auto, "auto", "Enable stencil merge when runtime check count exceeds " "-vectorize-memory-check-threshold"), clEnumValN(StencilMergePolicy::Force, "force", "Always attempt stencil merge regardless of check " "count")))
static cl::opt< unsigned >	StencilMergeMaxGroups ("stencil-merge-max-groups", cl::Hidden, cl::desc("Skip stencil group merging when the number of runtime checking groups " "exceeds this limit, to bound compile time (default =4096)."), cl::init(4096))
static cl::opt< unsigned >	MaxDependences ("max-dependences", cl::Hidden, cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)"), cl::init(100))
	We collect dependences up to this threshold.
static cl::opt< bool >	EnableMemAccessVersioning ("enable-mem-access-versioning", cl::init(true), cl::Hidden, cl::desc("Enable symbolic stride memory access versioning"))
	This enables versioning on the strides of symbolically striding memory accesses in code like the following.
static cl::opt< bool >	EnableForwardingConflictDetection ("store-to-load-forwarding-conflict-detection", cl::Hidden, cl::desc("Enable conflict detection in loop-access analysis"), cl::init(true))
	Enable store-to-load forwarding conflict detection.
static cl::opt< unsigned >	MaxForkedSCEVDepth ("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5))
static cl::opt< bool >	SpeculateUnitStride ("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true))
static cl::opt< bool, true >	HoistRuntimeChecks ("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))
constexpr unsigned	MaxStencilDecomposeDepth = 3
	Recursion cap for addScaledStencilTerm.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-accesses"

Definition at line 75 of file LoopAccessAnalysis.cpp.

Enumeration Type Documentation

◆ StencilMergePolicy

enum class StencilMergePolicy

strong

Enumerator
Off
Auto
Force

Definition at line 112 of file LoopAccessAnalysis.cpp.

Function Documentation

◆ addScaledStencilTerm()

bool addScaledStencilTerm	(	const SCEV *	Term,
		int64_t	Mult,
		unsigned	Depth,
		StencilDecomposition &	D )

static

Add one term of a stencil offset to D.

Mult is the factor in front of the term; the top-level call passes 1. Example: the offset 8 + (-64 * (s1 + s2)) + (-32 * s1), Mult = 1. It is an add, so each operand is visited in turn with the same Mult = 1: 8 a constant: D.Constant += 1 * 8 (-64 * (s1 + s2)) a constant times X: visit X = (s1 + s2) with Mult = 1 * -64. X is an add, so each operand is visited with Mult = -64: s1 a stride: D.Coefficients[s1] += -64 s2 a stride: D.Coefficients[s2] += -64 (-32 * s1) a constant times X: visit X = s1 with Mult = -32: s1 a stride: D.Coefficients[s1] += -32 Result: Constant = 8, Coefficients {s1: -96, s2: -64}. The -64 and the -32 for s1 come from two different terms and add up in the map. So, by the kind of term: constant K D.Constant += Mult * K (K * X) visit X with Mult * K (a + b + ...) visit a, b, ... each with this same Mult anything else a stride key: D.Coefficients[Term] += Mult The two recursive cases only fire while Depth is below MaxStencilDecomposeDepth. At the cap, (K * X) and (a + b + ...) are stride keys like anything else; that is not a bailout. Returns false when a constant does not fit in int64_t or an update overflows. The caller then drops the whole decomposition.

Definition at line 904 of file LoopAccessAnalysis.cpp.

References llvm::Add, llvm::AddOverflow(), addScaledStencilTerm(), llvm::all_of(), C(), D(), llvm::Depth, llvm::dyn_cast(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_SCEVConstant(), llvm::PatternMatch::match(), MaxStencilDecomposeDepth, llvm::MulOverflow(), and Scaled.

Referenced by addScaledStencilTerm(), and decomposeStencilOffset().

◆ addSCEVNoOverflow()

const SCEV * addSCEVNoOverflow	(	const SCEV *	A,
		const SCEV *	B,
		ScalarEvolution &	SE )

static

Returns A + B, if it is guaranteed not to unsigned wrap.

Otherwise return nullptr. A and B must have the same type.

Definition at line 223 of file LoopAccessAnalysis.cpp.

References A(), B(), llvm::ScalarEvolution::getAddExpr(), and llvm::ScalarEvolution::willNotOverflow().

Referenced by evaluatePtrAddRecAtMaxBTCWillNotWrap().

◆ areStridedAccessesIndependent()

bool areStridedAccessesIndependent	(	uint64_t	Distance,
		uint64_t	Stride,
		uint64_t	TypeByteSize )

static

Check the dependence for two accesses with the same stride Stride.

Distance is the positive distance in bytes, and TypeByteSize is type size in bytes.

Returns: true if they are independent.

Definition at line 2927 of file LoopAccessAnalysis.cpp.

References assert(), and uint64_t.

◆ buildMergedStencilGroup()

RuntimeCheckingPtrGroup buildMergedStencilGroup	(	const RuntimePointerChecking &	RtCheck,
		ArrayRef< unsigned >	AllMembers,
		const SCEV *	MergedLow,
		const SCEV *	MergedHigh,
		ArrayRef< unsigned >	GroupIndices )

static

Build the merged stencil group for one DepSet, after the cost model has decided the merge is profitable.

Constructs the bounding group over AllMembers with bounds [MergedLow, MergedHigh]. Returns the new group.

Definition at line 1229 of file LoopAccessAnalysis.cpp.

References llvm::any_of(), llvm::append_range(), llvm::RuntimePointerChecking::CheckingGroups, llvm::drop_begin(), llvm::RuntimeCheckingPtrGroup::High, llvm::RuntimeCheckingPtrGroup::Low, llvm::RuntimeCheckingPtrGroup::Members, and llvm::RuntimeCheckingPtrGroup::NeedsFreeze.

◆ collectCandidateMembers()

SmallVector< unsigned, 4 > collectCandidateMembers	(	ArrayRef< StencilDecomposition >	Offsets,
		bool	ForMin )

static

Find the members that can define the merged bound on one side.

Example for the minimum side (ForMin == true), two members: A: 0 - 80*s1 B: -40 - 40*s1 For every s1 >= 1, A sits at or below B, so B can never be the lowest member: A beats B. The members nobody beats are the candidates. The maximum side works the same way with the comparison flipped. When two members have equal offsets, only the first one is kept. In other words: "beats" is a partial order on the offsets, and the candidates are its minimal elements. Returns indices into Offsets. TODO: Worst case compares every pair of members: O(N^2). Fine for real stencils.

Definition at line 1139 of file LoopAccessAnalysis.cpp.

References A(), B(), isNeverAbove(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BitVector::set(), and llvm::BitVector::test().

◆ collectStrideLimits()

bool collectStrideLimits	(	const StencilDecomposition &	D,
		unsigned	BitWidth,
		ScalarEvolution &	SE,
		StrideLimits &	Limits )

static

Add to Limits the checks each stride s of D needs: 1 <= s isNeverAbove assumes every stride is 1 or more.

s <= Max Max is from getStencilStrideUpperLimit. A check is skipped when SCEV already proves it. Returns false if getStencilStrideUpperLimit finds no Max, or if SCEV proves that a check always fails. Example: s = smin(x, -1) can never pass 1 <= s, so a merge would send every run to the scalar loop.

Definition at line 1063 of file LoopAccessAnalysis.cpp.

References llvm::BitWidth, D(), llvm::ScalarEvolution::getConstant(), getStencilStrideUpperLimit(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::ScalarEvolution::isKnownNonPositive(), llvm::ScalarEvolution::isKnownPositive(), and llvm::ScalarEvolution::isKnownPredicate().

◆ computeStencilMergeCost()

std::pair< unsigned, unsigned > computeStencilMergeCost	(	const RuntimePointerChecking &	RtCheck,
		ArrayRef< unsigned >	GroupIndices,
		const StrideLimits &	Local,
		const StrideLimits &	Committed,
		unsigned	NumBoundOperands )

static

Local cost model: count the runtime checks required before and after replacing one DepSet's groups (GroupIndices) with the single merged group.

Everything is counted in the same unit, one check, even though a stride predicate or an extra umin/umax operand is cheaper at runtime than a full group-pair check. The cheaper items only appear on the After side, and we merge only when After < Before, so the rounding always errs toward not merging.

Before = NumGroups * NumExternalChecks, where NumExternalChecks is the number of groups outside this DepSet that need a check against it. The product is exact: needsChecking() looks only at (DependencySetId, AliasSetId) and at whether a group writes, and all groups in this DepSet agree on those, so an external group is checked against all of them or against none.

After = NumExternalChecks + NewPredicates + NumBoundOperands:

the merged group keeps the same IDs, so it is checked against exactly the same external groups;
one check per stride needing a lower or upper limit, unless an earlier DepSet already paid for either limit;
a umin over k members costs k-1 compare+selects, same for the umax. NumBoundOperands is the sum of the two. A single candidate costs nothing: the bound is that member's own address.

Returns {ChecksBefore, ChecksAfter}.

Definition at line 1198 of file LoopAccessAnalysis.cpp.

References llvm::RuntimePointerChecking::CheckingGroups, llvm::count_if(), G, Local, and llvm::ArrayRef< T >::size().

◆ decomposeStencilOffset()

std::optional< StencilDecomposition > decomposeStencilOffset	(	const SCEV *	Expr,
		ScalarEvolution &	SE,
		const Loop &	L )

static

Try to decompose Expr into a stencil offset function of loop-invariant strides: C + a1*s1 + a2*s2 + ... Expr is the difference of two access "Start" SCEVs (Start_member - Start_base).

A "Start" is the low bound of a memory access range as computed by getStartAndEndForAccess: the address of the first byte the access can touch. The result describes where one member's range sits relative to the base member's range. Constant factors are distributed over sums. SCEV can keep a factored form: -64*s1 + -64*s2 is stored as (-64 * (s1 + s2)). Distributing the -64 gives the coefficients {s1: -64, s2: -64}, so every member of a group is keyed on the same base strides. Relies on SCEV's canonical form: AddExpr operands are flattened (N-ary), MulExpr has the constant operand first when present. Returns std::nullopt if a constant, multiplier, or coefficient update does not fit in int64_t.

Definition at line 950 of file LoopAccessAnalysis.cpp.

References addScaledStencilTerm(), assert(), D(), and llvm::ScalarEvolution::isLoopInvariant().

◆ evaluatePtrAddRecAtMaxBTCWillNotWrap()

bool evaluatePtrAddRecAtMaxBTCWillNotWrap	(	const SCEVAddRecExpr *	AR,
		const SCEV *	MaxBTC,
		const SCEV *	EltSize,
		ScalarEvolution &	SE,
		const DataLayout &	DL,
		DominatorTree *	DT,
		AssumptionCache *	AC,
		std::optional< ScalarEvolution::LoopGuards > &	LoopGuards )

static

Return true, if evaluating AR at MaxBTC cannot wrap, because AR at MaxBTC is guaranteed inbounds of the accessed object.

Definition at line 241 of file LoopAccessAnalysis.cpp.

Referenced by llvm::getStartAndEndForAccess().

◆ findForkedSCEVs()

void findForkedSCEVs	(	ScalarEvolution *	SE,
		const Loop *	L,
		Value *	Ptr,
		SmallVectorImpl< PointerIntPair< const SCEV *, 1, bool > > &	ScevList,
		unsigned	Depth )

static

◆ getLoopVariantGEPOperand()

Value * getLoopVariantGEPOperand	(	Value *	Ptr,
		ScalarEvolution *	SE,
		Loop *	Lp )

static

If Ptr is a GEP, which has a loop-variant operand, return that operand.

Otherwise, return Ptr.

Definition at line 3936 of file LoopAccessAnalysis.cpp.

References llvm::dyn_cast(), GEP, llvm::ScalarEvolution::getSCEV(), and llvm::ScalarEvolution::isLoopInvariant().

Referenced by getStrideFromPointer().

◆ getMinFromExprs()

const SCEV * getMinFromExprs	(	const SCEV *	I,
		const SCEV *	J,
		ScalarEvolution *	SE )

static

Compare I and J and return the minimum.

Return nullptr in case we couldn't find an answer.

Definition at line 681 of file LoopAccessAnalysis.cpp.

References llvm::ScalarEvolution::computeConstantDifference(), and I.

Referenced by llvm::RuntimeCheckingPtrGroup::addPointer().

◆ getNonAffineMonotonicBounds()

std::pair< const SCEV , const SCEV > getNonAffineMonotonicBounds	(	const Loop *	Lp,
		const SCEV *	PtrExpr,
		const SCEV *	EltSizeSCEV,
		ScalarEvolution *	SE )

static

Try to bound a loop-variant pointer that is not an affine AddRec.

If the offset is provably monotonically non-decreasing the accessed range is bounded by the offset's value at the first iteration (via SplitIntoInitAndPostInc) and last iteration (via getSCEVAtScope). The returned range is half-open: EltSizeSCEV is added to the address of the last accessed element to form the end.

Returns {nullptr, nullptr} if no such bound can be formed.

Definition at line 396 of file LoopAccessAnalysis.cpp.

References llvm::sampleprof::Base, llvm::dyn_cast(), llvm::find_if(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMinusSCEV(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::ScalarEvolution::getSCEVAtScope(), llvm::isa(), isKnownNonDecreasingInLoop(), llvm::ScalarEvolution::isLoopInvariant(), llvm::Offset, and llvm::ScalarEvolution::SplitIntoInitAndPostInc().

Referenced by llvm::getStartAndEndForAccess().

◆ getPtrToIdxMap()

DenseMap< const RuntimeCheckingPtrGroup *, unsigned > getPtrToIdxMap ( ArrayRef< RuntimeCheckingPtrGroup > CheckingGroups )

static

Assign each RuntimeCheckingPtrGroup pointer an index for stable UTC output.

Definition at line 1628 of file LoopAccessAnalysis.cpp.

References llvm::enumerate().

Referenced by llvm::RuntimePointerChecking::print(), and llvm::RuntimePointerChecking::printChecks().

◆ getStencilStrideUpperLimit()

std::optional< APInt > getStencilStrideUpperLimit	(	const StencilDecomposition &	D,
		unsigned	BitWidth )

static

Find a common upper limit M for the positive strides in D.

If every stride is between 1 and M, the decomposed offset fits in the signed index type. This lets isNeverAbove compare offsets as ordinary signed integers.

Subtract abs(Constant) from SignedMax, then divide the remaining budget by the sum of absolute coefficients: M = (SignedMax - abs(Constant)) / sum(abs(Coefficient)). For example, both 8 + 4*s and 8 - 4*s get M = (SignedMax - 8) / 4.

Return nullopt if abs(Constant) exceeds SignedMax or no positive stride fits. Otherwise, if all coefficients are zero, no stride limit is needed; return SignedMax.

Definition at line 975 of file LoopAccessAnalysis.cpp.

References llvm::AbsoluteValue(), llvm::BitWidth, D(), llvm::maxIntN(), and uint64_t.

Referenced by collectStrideLimits().

◆ getStrideFromPointer()

const SCEV * getStrideFromPointer	(	Value *	Ptr,
		ScalarEvolution *	SE,
		Loop *	Lp )

static

Get the stride of a pointer access in a loop.

Looks for symbolic strides "a[i*stride]". Returns the symbolic stride, or null otherwise.

Definition at line 3957 of file LoopAccessAnalysis.cpp.

References C(), llvm::dyn_cast(), getLoopVariantGEPOperand(), llvm::ScalarEvolution::getSCEV(), llvm::Value::getType(), llvm::isa(), llvm::ScalarEvolution::isLoopInvariant(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_AffineAddRec(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_SCEVConstant(), llvm::SCEVPatternMatch::m_SpecificLoop(), and llvm::PatternMatch::match().

◆ isKnownNonDecreasingInLoop()

bool isKnownNonDecreasingInLoop	(	const SCEV *	S,
		const Loop *	L,
		ScalarEvolution &	SE )

static

Return true if S is known to be monotonically non-decreasing (in the unsigned sense, without unsigned wrap) across iterations of L.

Definition at line 362 of file LoopAccessAnalysis.cpp.

References assert(), llvm::cast(), llvm::ScalarEvolution::getMonotonicPredicateType(), llvm::SCEV::getSCEVType(), llvm::CmpInst::ICMP_UGE, isKnownNonDecreasingInLoop(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ScalarEvolution::MonotonicallyIncreasing, llvm::scAddRecExpr, and llvm::scUDivExpr.

Referenced by getNonAffineMonotonicBounds(), and isKnownNonDecreasingInLoop().

◆ isNeverAbove()

bool isNeverAbove	(	const StencilDecomposition &	A,
		const StencilDecomposition &	B )

static

Return true if offset A is never higher than offset B.

A and B are these sums: A = A.Constant + CoefA_1 * stride_1 + CoefA_2 * stride_2 + ... B = B.Constant + CoefB_1 * stride_1 + CoefB_2 * stride_2 + ... A stride missing from a member's map has coefficient 0. Every stride is 1 or more: the caller proves or predicates each stride to be positive and that the whole expression does not overflow. Example: A: 0 - 80*s1 B: -40 - 40*s1 At s1 = 1 both are -80. For bigger s1, A goes down faster. So A is never above B. The rule checks two things:

CoefA_i <= CoefB_i for every stride. So when a stride grows, B - A grows too, or stays the same.
B - A >= 0 when every stride is 1. That is ACorner <= BCorner, with ACorner = A.Constant + the sum of all CoefA_i, same for BCorner. B - A starts at or above zero and never goes down, so B - A >= 0 for all stride values. Offsets are signed and addresses are unsigned, but both members read one object, and an object does not wrap around the address space, so the smaller offset is the smaller address. Returns false when ACorner or BCorner overflows int64_t. The caller then keeps the member, which is the safe side.

Definition at line 1107 of file LoopAccessAnalysis.cpp.

References A(), llvm::AddOverflow(), and B().

Referenced by collectCandidateMembers().

◆ isNoWrap()

bool isNoWrap	(	PredicatedScalarEvolution &	PSE,
		const SCEVAddRecExpr *	AR,
		Value *	Ptr,
		Type *	AccessTy,
		const Loop *	L,
		const DominatorTree &	DT,
		std::optional< int64_t >	Stride = std::nullopt,
		SmallVectorImpl< const SCEVPredicate * > *	Predicates = nullptr )

static

Check whether AR is a non-wrapping AddRec.

If Ptr is not nullptr, use information from the IR pointer value to determine no-wrap. If Predicates is not nullptr add no-wrap assumptions if needed.

Definition at line 1890 of file LoopAccessAnalysis.cpp.

References llvm::any_of(), llvm::dbgs(), llvm::dyn_cast_if_present(), GEP, llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::Type::getPointerAddressSpace(), llvm::PredicatedScalarEvolution::getPredicate(), llvm::PredicatedScalarEvolution::getSE(), llvm::getStrideFromAddRec(), llvm::SCEV::getType(), llvm::ScalarEvolution::getWrapPredicate(), llvm::SCEVPredicate::implies(), llvm::SCEVWrapPredicate::IncrementNUSW, LLVM_DEBUG, and llvm::NullPointerIsDefined().

Referenced by llvm::getPtrStride().

◆ isSafeDependenceDistance()

bool isSafeDependenceDistance	(	const DataLayout &	DL,
		ScalarEvolution &	SE,
		const SCEV &	MaxBTC,
		const SCEV &	Dist,
		uint64_t	MaxStride )

static

Given a dependence-distance Dist between two memory accesses, that have strides in the same direction whose absolute value of the maximum stride is given in MaxStride, in a loop whose maximum backedge taken count is MaxBTC, check if it is possible to prove statically that the dependence distance is larger than the range that the accesses will travel through the execution of the loop.

If so, return true; false otherwise. This is useful for example in loops such as the following (PR31098):

for (i = 0; i < D; ++i) {
           = out[i];
  out[i+D] =
}

Definition at line 2872 of file LoopAccessAnalysis.cpp.

References DL, llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::ScalarEvolution::getNoopOrSignExtend(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::ScalarEvolution::isKnownPositive(), llvm::Minus, and uint64_t.

◆ mulSCEVNoOverflow()

const SCEV * mulSCEVNoOverflow	(	const SCEV *	A,
		const SCEV *	B,
		ScalarEvolution &	SE )

static

Returns A * B, if it is guaranteed not to unsigned wrap.

Otherwise return nullptr. A and B must have the same type.

Definition at line 232 of file LoopAccessAnalysis.cpp.

References A(), B(), llvm::ScalarEvolution::getMulExpr(), and llvm::ScalarEvolution::willNotOverflow().

Referenced by evaluatePtrAddRecAtMaxBTCWillNotWrap().

◆ visitPointers()

void visitPointers	(	Value *	StartPtr,
		const Loop &	InnermostLoop,
		function_ref< void(Value *)>	AddPointer )

static

Definition at line 1949 of file LoopAccessAnalysis.cpp.

References llvm::append_range(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::MemoryDepChecker::addAccess(), and llvm::MemoryDepChecker::addAccess().

Variable Documentation

◆ EnableForwardingConflictDetection

cl::opt< bool > EnableForwardingConflictDetection("store-to-load-forwarding-conflict-detection", cl::Hidden, cl::desc("Enable conflict detection in loop-access analysis"), cl::init(true))	(	"store-to-load-forwarding-conflict-detection"	,
		cl::Hidden	,
		cl::desc("Enable conflict detection in loop-access analysis")	,
		cl::init(true)	)

static

Enable store-to-load forwarding conflict detection.

This option can be disabled for correctness testing.

◆ EnableMemAccessVersioning

cl::opt< bool > EnableMemAccessVersioning("enable-mem-access-versioning", cl::init(true), cl::Hidden, cl::desc("Enable symbolic stride memory access versioning"))	(	"enable-mem-access-versioning"	,
		cl::init(true)	,
		cl::Hidden	,
		cl::desc("Enable symbolic stride memory access versioning")	)

static

This enables versioning on the strides of symbolically striding memory accesses in code like the following.

for (i = 0; i < N; ++i) A[i * Stride1] += B[i * Stride2] ...

Will be roughly translated to if (Stride1 == 1 && Stride2 == 1) { for (i = 0; i < N; i+=4) A[i:i+3] += ... } else ...

◆ HoistRuntimeChecks

cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc( "Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))	(	"hoist-runtime-checks"	,
		cl::Hidden	,
		cl::desc( "Hoist inner loop runtime memory checks to outer loop if possible")	,
		cl::location(VectorizerParams::HoistRuntimeChecks)	,
		cl::init(true)	)

static

Referenced by llvm::addRuntimeChecks(), llvm::appendLoopsToWorklist< Loop & >(), expandBounds(), and expandBounds().

◆ MaxDependences

cl::opt< unsigned > MaxDependences("max-dependences", cl::Hidden, cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)"), cl::init(100))	(	"max-dependences"	,
		cl::Hidden	,
		cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)")	,
		cl::init(100)	)

static

We collect dependences up to this threshold.

Referenced by llvm::MemoryDepChecker::areDepsSafe().

◆ MaxForkedSCEVDepth

cl::opt< unsigned > MaxForkedSCEVDepth("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5))	(	"max-forked-scev-depth"	,
		cl::Hidden	,
		cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)")	,
		cl::init(5)	)

static

◆ MaxStencilDecomposeDepth

unsigned MaxStencilDecomposeDepth = 3

constexpr

Recursion cap for addScaledStencilTerm.

Depth counts how deep a term sits inside the offset expression. For example, the offset 8 + (64 * (s1 + s2 + (4 * s3))) is visited like this: depth 0: the whole add depth 1: its operands 8 and (64 * (s1 + s2 + (4 * s3))) depth 2: (s1 + s2 + (4 * s3)), the operand of the multiply depth 3: s1, s2 and (4 * s3), the operands of that add At depth 3 addScaledStencilTerm stops going deeper. s1 and s2 are plain strides anyway. (4 * s3) is not split into 4 times s3: it becomes one stride key as it is, with coefficient 64. The result is Constant = 8 and coefficients {s1: 64, s2: 64, (4 * s3): 64}. Three levels cover the stencil offsets we care about: a top-level add, a constant times a sum inside it, and the strides in that sum. A deeper term is kept whole as one stride key. The merge does not care what is inside a key. It only needs a loop-invariant value with a positive-stride predicate, and a whole term has both. The only cost is precision, when another member uses a part of that term, here s3 alone, as a key of its own. isNeverAbove sees two unrelated keys, so a member that is in fact always lower or higher may stay a candidate.

Definition at line 878 of file LoopAccessAnalysis.cpp.

Referenced by addScaledStencilTerm().

◆ MemoryCheckMergeThreshold

cl::opt< unsigned > MemoryCheckMergeThreshold("memory-check-merge-threshold", cl::Hidden, cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)"), cl::init(100))	(	"memory-check-merge-threshold"	,
		cl::Hidden	,
		cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)")	,
		cl::init(100)	)

static

The maximum iterations used to merge memory checks.

◆ RuntimeMemoryCheckThreshold

cl::opt< unsigned, true > RuntimeMemoryCheckThreshold("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8))	(	"runtime-memory-check-threshold"	,
		cl::Hidden	,
		cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8).")	,
		cl::location(VectorizerParams::RuntimeMemoryCheckThreshold)	,
		cl::init(8)	)

static

◆ SpeculateUnitStride

cl::opt< bool > SpeculateUnitStride("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true))	(	"laa-speculate-unit-stride"	,
		cl::Hidden	,
		cl::desc("Speculate that non-constant strides are unit in LAA")	,
		cl::init(true)	)

static

◆ StencilMerge

cl::opt< StencilMergePolicy > StencilMerge("stencil-runtime-check-merge", cl::Hidden, cl::desc("Control stencil-pattern merging of runtime memory checks"), cl::init(StencilMergePolicy::Off), cl::values( clEnumValN(StencilMergePolicy::Off, "off", "Disable stencil merge (default)"), clEnumValN(StencilMergePolicy::Auto, "auto", "Enable stencil merge when runtime check count exceeds " "-vectorize-memory-check-threshold"), clEnumValN(StencilMergePolicy::Force, "force", "Always attempt stencil merge regardless of check " "count")))	(	"stencil-runtime-check-merge"	,
		cl::Hidden	,
		cl::desc("Control stencil-pattern merging of runtime memory checks")	,
		cl::init(StencilMergePolicy::Off)	,
		cl::values( clEnumValN(StencilMergePolicy::Off, "off", "Disable stencil merge (default)"), clEnumValN(StencilMergePolicy::Auto, "auto", "Enable stencil merge when runtime check count exceeds " "-vectorize-memory-check-threshold"), clEnumValN(StencilMergePolicy::Force, "force", "Always attempt stencil merge regardless of check " "count"))	)

static

◆ StencilMergeMaxGroups

cl::opt< unsigned > StencilMergeMaxGroups("stencil-merge-max-groups", cl::Hidden, cl::desc( "Skip stencil group merging when the number of runtime checking groups " "exceeds this limit, to bound compile time (default =4096)."), cl::init(4096))	(	"stencil-merge-max-groups"	,
		cl::Hidden	,
		cl::desc( "Skip stencil group merging when the number of runtime checking groups " "exceeds this limit, to bound compile time (default =4096).")	,
		cl::init(4096)	)

static

◆ VectorizationFactor

cl::opt< ElementCount, true > VectorizationFactor("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor))	(	"force-vector-width"	,
		cl::Hidden	,
		cl::desc("Sets the SIMD width. Zero is autoselect.")	,
		cl::location(VectorizerParams::VectorizationFactor)	)

static

Referenced by llvm::LoopVectorizationPlanner::computeBestVF().

◆ VectorizationInterleave

cl::opt< unsigned, true > VectorizationInterleave("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location( VectorizerParams::VectorizationInterleave))	(	"force-vector-interleave"	,
		cl::Hidden	,
		cl::desc("Sets the vectorization interleave count. " "Zero is autoselect.")	,
		cl::location( VectorizerParams::VectorizationInterleave)	)

static

◆ VectorizeMemoryCheckThreshold

cl::opt< unsigned, true > VectorizeMemoryCheckThreshold("vectorize-memory-check-threshold", cl::Hidden, cl::desc("The maximum allowed number of runtime memory checks"), cl::location(VectorizerParams::VectorizeMemoryCheckThreshold), cl::init(128))	(	"vectorize-memory-check-threshold"	,
		cl::Hidden	,
		cl::desc("The maximum allowed number of runtime memory checks")	,
		cl::location(VectorizerParams::VectorizeMemoryCheckThreshold)	,
		cl::init(128)	)

static

Classes

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ StencilMergePolicy

Function Documentation

◆ addScaledStencilTerm()

◆ addSCEVNoOverflow()

◆ areStridedAccessesIndependent()

◆ buildMergedStencilGroup()

◆ collectCandidateMembers()

◆ collectStrideLimits()

◆ computeStencilMergeCost()

◆ decomposeStencilOffset()

◆ evaluatePtrAddRecAtMaxBTCWillNotWrap()

◆ findForkedSCEVs()

◆ getLoopVariantGEPOperand()

◆ getMinFromExprs()

◆ getNonAffineMonotonicBounds()

◆ getPtrToIdxMap()

◆ getStencilStrideUpperLimit()

◆ getStrideFromPointer()

◆ isKnownNonDecreasingInLoop()

◆ isNeverAbove()

◆ isNoWrap()

◆ isSafeDependenceDistance()

◆ mulSCEVNoOverflow()

◆ visitPointers()

Variable Documentation

◆ EnableForwardingConflictDetection

◆ EnableMemAccessVersioning

◆ HoistRuntimeChecks

◆ MaxDependences

◆ MaxForkedSCEVDepth

◆ MaxStencilDecomposeDepth

◆ MemoryCheckMergeThreshold

◆ RuntimeMemoryCheckThreshold

◆ SpeculateUnitStride

◆ StencilMerge

◆ StencilMergeMaxGroups

◆ VectorizationFactor

◆ VectorizationInterleave

◆ VectorizeMemoryCheckThreshold