LLVM 19.0.0git
Macros | Functions | Variables
LoopAccessAnalysis.cpp File Reference
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.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/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/TargetLibraryInfo.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/GetElementPtrTypeIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.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/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>
#include <variant>
#include <vector>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-accesses"
 

Functions

static const SCEVgetMinFromExprs (const SCEV *I, const SCEV *J, ScalarEvolution *SE)
 Compare I and J and return the minimum.
 
static bool hasComputableBounds (PredicatedScalarEvolution &PSE, Value *Ptr, const SCEV *PtrScev, Loop *L, bool Assume)
 Check whether a pointer can participate in a runtime bounds check.
 
static bool isNoWrap (PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &Strides, Value *Ptr, Type *AccessTy, Loop *L)
 Check whether a pointer address cannot wrap.
 
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 SmallVector< PointerIntPair< const SCEV *, 1, bool > > findForkedPointer (PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &StridesMap, Value *Ptr, const Loop *L)
 
static bool isNoWrapAddRec (Value *Ptr, const SCEVAddRecExpr *AR, PredicatedScalarEvolution &PSE, const Loop *L)
 Return true if an AddRec pointer Ptr is unsigned non-wrapping, i.e.
 
static bool isSafeDependenceDistance (const DataLayout &DL, ScalarEvolution &SE, const SCEV &BackedgeTakenCount, const SCEV &Dist, uint64_t Stride, uint64_t TypeByteSize)
 Given a dependence-distance Dist between two memory accesses, that have the same stride whose absolute value is given in Stride, and that have the same type size TypeByteSize, in a loop whose takenCount is BackedgeTakenCount, 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 bool isLoopVariantIndirectAddress (ArrayRef< const Value * > UnderlyingObjects, ScalarEvolution &SE, const Loop *L)
 Returns true if any of the underlying objects has a loop varying address, i.e.
 
static std::variant< MemoryDepChecker::Dependence::DepType, std::tuple< const SCEV *, uint64_t, uint64_t, bool, bool > > getDependenceDistanceStrideAndSize (const AccessAnalysis::MemAccessInfo &A, Instruction *AInst, const AccessAnalysis::MemAccessInfo &B, Instruction *BInst, const DenseMap< Value *, const SCEV * > &Strides, const DenseMap< Value *, SmallVector< const Value *, 16 > > &UnderlyingObjects, PredicatedScalarEvolution &PSE, const Loop *InnermostLoop)
 
static unsigned getGEPInductionOperand (const GetElementPtrInst *Gep)
 Find the operand of the GEP that should be checked for consecutive stores.
 
static ValuestripGetElementPtr (Value *Ptr, ScalarEvolution *SE, Loop *Lp)
 If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.
 
static ValuegetUniqueCastUse (Value *Ptr, Loop *Lp, Type *Ty)
 If a value has only one user that is a CastInst, return it.
 
static const SCEVgetStrideFromPointer (Value *Ptr, ScalarEvolution *SE, Loop *Lp)
 Get the stride of a pointer access in a loop.
 

Variables

static cl::opt< unsigned, trueVectorizationFactor ("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor))
 
static cl::opt< unsigned, trueVectorizationInterleave ("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location(VectorizerParams::VectorizationInterleave))
 
static cl::opt< unsigned, trueRuntimeMemoryCheckThreshold ("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< unsignedMemoryCheckMergeThreshold ("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< unsignedMaxDependences ("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< boolEnableMemAccessVersioning ("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< boolEnableForwardingConflictDetection ("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< unsignedMaxForkedSCEVDepth ("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5))
 
static cl::opt< boolSpeculateUnitStride ("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true))
 
static cl::opt< bool, trueHoistRuntimeChecks ("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))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-accesses"

Definition at line 70 of file LoopAccessAnalysis.cpp.

Function Documentation

◆ areStridedAccessesIndependent()

static 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 and TypeByteSize is type size in bytes.

Returns
true if they are independent.

Definition at line 1879 of file LoopAccessAnalysis.cpp.

References assert().

◆ findForkedPointer()

static SmallVector< PointerIntPair< const SCEV *, 1, bool > > findForkedPointer ( PredicatedScalarEvolution PSE,
const DenseMap< Value *, const SCEV * > &  StridesMap,
Value Ptr,
const Loop L 
)
static

◆ findForkedSCEVs()

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

◆ getDependenceDistanceStrideAndSize()

static std::variant< MemoryDepChecker::Dependence::DepType, std::tuple< const SCEV *, uint64_t, uint64_t, bool, bool > > getDependenceDistanceStrideAndSize ( const AccessAnalysis::MemAccessInfo A,
Instruction AInst,
const AccessAnalysis::MemAccessInfo B,
Instruction BInst,
const DenseMap< Value *, const SCEV * > &  Strides,
const DenseMap< Value *, SmallVector< const Value *, 16 > > &  UnderlyingObjects,
PredicatedScalarEvolution PSE,
const Loop InnermostLoop 
)
static

◆ getGEPInductionOperand()

static unsigned getGEPInductionOperand ( const GetElementPtrInst Gep)
static

◆ getMinFromExprs()

static 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 405 of file LoopAccessAnalysis.cpp.

References llvm::CallingConv::C, llvm::ScalarEvolution::getMinusSCEV(), and I.

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

◆ getStrideFromPointer()

static 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 2795 of file LoopAccessAnalysis.cpp.

References llvm::CallingConv::C, llvm::APInt::getBitWidth(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), llvm::APInt::getSExtValue(), llvm::SCEVAddRecExpr::getStepRecurrence(), getUniqueCastUse(), llvm::ScalarEvolution::isLoopInvariant(), Ptr, llvm::scConstant, and stripGetElementPtr().

◆ getUniqueCastUse()

static Value * getUniqueCastUse ( Value Ptr,
Loop Lp,
Type Ty 
)
static

If a value has only one user that is a CastInst, return it.

Definition at line 2779 of file LoopAccessAnalysis.cpp.

References llvm::Value::getType(), and Ptr.

Referenced by getStrideFromPointer().

◆ hasComputableBounds()

static bool hasComputableBounds ( PredicatedScalarEvolution PSE,
Value Ptr,
const SCEV PtrScev,
Loop L,
bool  Assume 
)
static

Check whether a pointer can participate in a runtime bounds check.

If Assume, try harder to prove that we can compute the bounds of Ptr by adding run-time checks (overflow checks) if necessary.

Definition at line 817 of file LoopAccessAnalysis.cpp.

References llvm::PredicatedScalarEvolution::getAsAddRec(), llvm::PredicatedScalarEvolution::getSE(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isLoopInvariant(), and Ptr.

◆ isLoopVariantIndirectAddress()

static bool isLoopVariantIndirectAddress ( ArrayRef< const Value * >  UnderlyingObjects,
ScalarEvolution SE,
const Loop L 
)
static

Returns true if any of the underlying objects has a loop varying address, i.e.

may change in L.

Definition at line 1913 of file LoopAccessAnalysis.cpp.

References llvm::any_of(), llvm::ScalarEvolution::getSCEV(), and llvm::ScalarEvolution::isLoopInvariant().

Referenced by getDependenceDistanceStrideAndSize().

◆ isNoWrap()

static bool isNoWrap ( PredicatedScalarEvolution PSE,
const DenseMap< Value *, const SCEV * > &  Strides,
Value Ptr,
Type AccessTy,
Loop L 
)
static

◆ isNoWrapAddRec()

static bool isNoWrapAddRec ( Value Ptr,
const SCEVAddRecExpr AR,
PredicatedScalarEvolution PSE,
const Loop L 
)
static

Return true if an AddRec pointer Ptr is unsigned non-wrapping, i.e.

monotonically increasing/decreasing.

Definition at line 1411 of file LoopAccessAnalysis.cpp.

References llvm::SCEV::FlagNSW, GEP, llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::hasNoOverflow(), llvm::SCEVWrapPredicate::IncrementNUSW, llvm::SCEV::NoWrapMask, and Ptr.

Referenced by llvm::getPtrStride().

◆ isSafeDependenceDistance()

static bool isSafeDependenceDistance ( const DataLayout DL,
ScalarEvolution SE,
const SCEV BackedgeTakenCount,
const SCEV Dist,
uint64_t  Stride,
uint64_t  TypeByteSize 
)
static

Given a dependence-distance Dist between two memory accesses, that have the same stride whose absolute value is given in Stride, and that have the same type size TypeByteSize, in a loop whose takenCount is BackedgeTakenCount, 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 1819 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(), and llvm::Minus.

◆ stripGetElementPtr()

static Value * stripGetElementPtr ( Value Ptr,
ScalarEvolution SE,
Loop Lp 
)
static

If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.

However, if there is some other non-loop-invariant operand, it returns that instead.

Definition at line 2762 of file LoopAccessAnalysis.cpp.

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

Referenced by getStrideFromPointer().

◆ visitPointers()

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

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

◆ 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

Referenced by findForkedPointer().

◆ 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

◆ VectorizationFactor

cl::opt< unsigned, 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

◆ 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