LLVM
17.0.0git
|
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.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/ADT/iterator_range.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/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/InitializePasses.h"
#include "llvm/Pass.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 <vector>
Go to the source code of this file.
Namespaces | |
llvm | |
This is an optimization pass for GlobalISel generic memory operations. | |
Macros | |
#define | DEBUG_TYPE "loop-accesses" |
#define | LAA_NAME "loop-accesses" |
Functions | |
static const SCEV * | getMinFromExprs (const SCEV *I, const SCEV *J, ScalarEvolution *SE) |
Compare I and J and return the minimum. More... | |
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. More... | |
static bool | isNoWrap (PredicatedScalarEvolution &PSE, const ValueToValueMap &Strides, Value *Ptr, Type *AccessTy, Loop *L) |
Check whether a pointer address cannot wrap. More... | |
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 ValueToValueMap &StridesMap, Value *Ptr, const Loop *L) |
static bool | isInBoundsGep (Value *Ptr) |
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. More... | |
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. More... | |
static bool | areStridedAccessesIndependent (uint64_t Distance, uint64_t Stride, uint64_t TypeByteSize) |
Check the dependence for two accesses with the same stride Stride . More... | |
Pass * | llvm::createLAAPass () |
Variables | |
static cl::opt< unsigned, 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 > | 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. More... | |
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. More... | |
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. More... | |
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. More... | |
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 const char | laa_name [] = "Loop Access Analysis" |
#define DEBUG_TYPE "loop-accesses" |
Definition at line 72 of file LoopAccessAnalysis.cpp.
#define LAA_NAME "loop-accesses" |
Definition at line 2717 of file LoopAccessAnalysis.cpp.
|
static |
Check the dependence for two accesses with the same stride Stride
.
Distance
is the positive distance and TypeByteSize
is type size in bytes.
Definition at line 1799 of file LoopAccessAnalysis.cpp.
References assert().
|
static |
Definition at line 953 of file LoopAccessAnalysis.cpp.
References assert(), llvm::dbgs(), findForkedSCEVs(), llvm::PredicatedScalarEvolution::getSE(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ScalarEvolution::isSCEVable(), LLVM_DEBUG, MaxForkedSCEVDepth, Ptr, and llvm::replaceSymbolicStrideSCEV().
|
static |
Definition at line 814 of file LoopAccessAnalysis.cpp.
References llvm::MCID::Add, llvm::any_of(), llvm::dbgs(), llvm::Depth, llvm::SmallVectorImpl< T >::emplace_back(), GEP, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSizeOfExpr(), llvm::ScalarEvolution::getTruncateOrSignExtend(), llvm::SCEV::getType(), I, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::Loop::isLoopInvariant(), llvm::Type::isVectorTy(), LLVM_DEBUG, llvm_unreachable, Ptr, S, and llvm::MCID::Select.
Referenced by findForkedPointer().
Compare I
and J
and return the minimum.
Return nullptr in case we couldn't find an answer.
Definition at line 369 of file LoopAccessAnalysis.cpp.
References llvm::ScalarEvolution::getMinusSCEV(), and I.
|
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 742 of file LoopAccessAnalysis.cpp.
References llvm::PredicatedScalarEvolution::getAsAddRec(), llvm::PredicatedScalarEvolution::getSE(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isLoopInvariant(), and Ptr.
|
static |
Definition at line 1314 of file LoopAccessAnalysis.cpp.
Referenced by llvm::getPtrStride().
|
static |
Check whether a pointer address cannot wrap.
Definition at line 760 of file LoopAccessAnalysis.cpp.
References llvm::getPtrStride(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::getSE(), llvm::PredicatedScalarEvolution::hasNoOverflow(), llvm::SCEVWrapPredicate::IncrementNUSW, llvm::ScalarEvolution::isLoopInvariant(), and Ptr.
|
static |
Return true if an AddRec pointer Ptr
is unsigned non-wrapping, i.e.
monotonically increasing/decreasing.
Definition at line 1322 of file LoopAccessAnalysis.cpp.
References llvm::SCEV::FlagNSW, GEP, llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::PredicatedScalarEvolution::getSCEV(), Index, llvm::SCEV::NoWrapMask, and Ptr.
Referenced by llvm::getPtrStride().
|
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 1739 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(), and llvm::ScalarEvolution::isKnownPositive().
|
static |
Definition at line 774 of file LoopAccessAnalysis.cpp.
References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), and Ptr.
Referenced by llvm::MemoryDepChecker::addAccess().
|
static |
Enable store-to-load forwarding conflict detection.
This option can be disabled for correctness testing.
|
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 ...
Definition at line 2716 of file LoopAccessAnalysis.cpp.
|
static |
We collect dependences up to this threshold.
Referenced by llvm::MemoryDepChecker::areDepsSafe().
|
static |
Referenced by findForkedPointer().
|
static |
The maximum iterations used to merge memory checks.
|
static |
|
static |
|
static |
Referenced by llvm::VectorizerParams::isInterleaveForced().