34 return BA >= Alignment && !(
Offset & (APAlign - 1));
51 if (!Visited.
insert(V).second)
77 CtxI, AC, DT, TLI, Visited,
MaxDepth);
82 if (BC->getSrcTy()->isPointerTy())
84 BC->getOperand(0), Alignment,
Size,
DL, CtxI, AC, DT, TLI,
89 if (
const SelectInst *Sel = dyn_cast<SelectInst>(V)) {
91 Size,
DL, CtxI, AC, DT, TLI,
94 Size,
DL, CtxI, AC, DT, TLI,
98 bool CheckForNonNull, CheckForFreed;
116 if (
const auto *Call = dyn_cast<CallBase>(V)) {
136 APInt KnownDerefBytes(
Size.getBitWidth(), ObjSize);
150 if (
const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
152 Alignment,
Size,
DL, CtxI, AC, DT,
157 Size,
DL, CtxI, AC, DT, TLI,
166 V, {Attribute::Dereferenceable, Attribute::Alignment}, AC,
170 if (RK.AttrKind == Attribute::Alignment)
171 AlignRK = std::max(AlignRK, RK);
172 if (RK.AttrKind == Attribute::Dereferenceable)
173 DerefRK = std::max(DerefRK, RK);
197 return ::isDereferenceableAndAlignedPointer(V, Alignment,
Size,
DL, CtxI, AC,
198 DT, TLI, Visited, 16);
207 if (!Ty->
isSized() || isa<ScalableVectorType>(Ty))
216 DL.getTypeStoreSize(Ty));
252 if (isa<BinaryOperator>(
A) || isa<CastInst>(
A) || isa<PHINode>(
A) ||
253 isa<GetElementPtrInst>(
A))
255 if (cast<Instruction>(
A)->isIdenticalToWhenDefined(BI))
269 APInt EltSize(
DL.getIndexTypeSizeInBits(
Ptr->getType()),
270 DL.getTypeStoreSize(LI->
getType()).getFixedValue());
279 HeaderFirstNonPHI, AC, &DT);
283 auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(
Ptr));
284 if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())
286 auto* Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE));
290 if (Step->getAPInt() != EltSize)
297 const APInt AccessSize = TC * EltSize;
299 auto *StartS = dyn_cast<SCEVUnknown>(AddRec->getStart());
308 if (EltSize.
urem(Alignment.
value()) != 0)
311 HeaderFirstNonPHI, AC, &DT);
340 if (
Size.getBitWidth() > 64)
361 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
362 !isa<LifetimeIntrinsic>(BBI) && !isa<DbgInfoIntrinsic>(BBI))
368 if (
LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
372 if (LI->isVolatile())
374 AccessedPtr = LI->getPointerOperand();
375 AccessedTy = LI->getType();
376 AccessedAlign = LI->getAlign();
377 }
else if (
StoreInst *
SI = dyn_cast<StoreInst>(BBI)) {
379 if (
SI->isVolatile())
381 AccessedPtr =
SI->getPointerOperand();
382 AccessedTy =
SI->getValueOperand()->getType();
383 AccessedAlign =
SI->getAlign();
387 if (AccessedAlign < Alignment)
391 if (AccessedPtr == V &&
392 LoadSize <=
DL.getTypeStoreSize(AccessedTy))
396 LoadSize <=
DL.getTypeStoreSize(AccessedTy))
424 cl::desc(
"Use this to specify the default maximum number of instructions "
425 "to scan backward from a given instruction, when searching for "
426 "available loaded value"));
431 unsigned MaxInstsToScan,
433 unsigned *NumScanedInst) {
435 if (!Load->isUnordered())
440 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,
448 const Value *StorePtr,
451 APInt LoadOffset(
DL.getIndexTypeSizeInBits(LoadPtr->
getType()), 0);
452 APInt StoreOffset(
DL.getIndexTypeSizeInBits(StorePtr->
getType()), 0);
454 DL, LoadOffset,
false);
456 DL, StoreOffset,
false);
457 if (LoadBase != StoreBase)
462 LoadOffset + LoadAccessSize.toRaw());
464 StoreOffset + StoreAccessSize.toRaw());
469 Type *AccessTy,
bool AtLeastAtomic,
474 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
477 if (LI->isAtomic() < AtLeastAtomic)
497 if (
SI->isAtomic() < AtLeastAtomic)
500 Value *StorePtr =
SI->getPointerOperand()->stripPointerCasts();
507 Value *Val =
SI->getValueOperand();
512 TypeSize LoadSize =
DL.getTypeSizeInBits(AccessTy);
513 if (TypeSize::isKnownLE(LoadSize, StoreSize))
514 if (
auto *
C = dyn_cast<Constant>(Val))
518 if (
auto *MSI = dyn_cast<MemSetInst>(Inst)) {
524 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());
525 auto *Len = dyn_cast<ConstantInt>(MSI->getLength());
530 Value *Dst = MSI->getDest();
537 TypeSize LoadTypeSize =
DL.getTypeSizeInBits(AccessTy);
543 if ((Len->getValue() * 8).ult(LoadSize))
547 : Val->getValue().trunc(LoadSize);
561 AAResults *AA,
bool *IsLoadCSE,
unsigned *NumScanedInst) {
562 if (MaxInstsToScan == 0)
563 MaxInstsToScan = ~0U;
568 while (ScanFrom != ScanBB->
begin()) {
582 if (MaxInstsToScan-- == 0)
588 AtLeastAtomic,
DL, IsLoadCSE))
593 Value *StorePtr =
SI->getPointerOperand()->stripPointerCasts();
598 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
599 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
600 StrippedPtr != StorePtr)
609 Loc.
Ptr, AccessTy,
SI->getPointerOperand(),
610 SI->getValueOperand()->getType(),
DL))
644 unsigned MaxInstsToScan) {
645 const DataLayout &
DL = Load->getModule()->getDataLayout();
646 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
648 Type *AccessTy = Load->getType();
649 bool AtLeastAtomic = Load->isAtomic();
651 if (!Load->isUnordered())
660 if (Inst.isDebugOrPseudoInst())
663 if (MaxInstsToScan-- == 0)
667 AtLeastAtomic,
DL, IsLoadCSE);
671 if (Inst.mayWriteToMemory())
689 Type *Ty =
A->getType();
691 "values must have matching pointer types");
696 if (
auto *
C = dyn_cast<Constant>(
B)) {
699 APInt OneByte(
DL.getPointerTypeSizeInBits(Ty), 1);
700 return C->isNullValue() ||
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
@ Available
We know the block is fully available. This is a fixpoint.
static const unsigned MaxDepth
static bool AreEquivalentAddressValues(const Value *A, const Value *B)
Test if A and B will obviously have the same value.
static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment, const DataLayout &DL)
static bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited, unsigned MaxDepth)
Test if V is always a pointer to allocated and suitably aligned memory for a simple load or store.
static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr, Type *LoadTy, const Value *StorePtr, Type *StoreTy, const DataLayout &DL)
static Value * getAvailableLoadStore(Instruction *Inst, const Value *Ptr, Type *AccessTy, bool AtLeastAtomic, const DataLayout &DL, bool *IsLoadCSE)
This file provides utility analysis objects describing memory locations.
Module.h This file contains the declarations for the Module class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
bool getBoolValue() const
Convert APInt to a boolean value.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
InstListType::iterator iterator
Instruction iterators...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
This is the shared class of boolean and integer constants.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
This class represents a range of values.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Represents calls to the gc.relocate intrinsic.
bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
An instruction for reading from memory.
Value * getPointerOperand()
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
BlockT * getHeader() const
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
const Value * Ptr
The address of the start of the location.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
self_iterator getIterator()
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache *AC=nullptr, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
bool isModSet(const ModRefInfo MRI)
bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL, Instruction *CtxI)
Returns true if a pointer value A can be replace with another pointer value \B if they are deemed equ...
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, const DataLayout &DL, Instruction *ScanFrom=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if we know that executing a load from this value cannot trap.
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Represent one information held inside an operand bundle of an llvm.assume.