#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PhiValues.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.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/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.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/Operator.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.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/KnownBits.h"
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <utility>

Include dependency graph for BasicAliasAnalysis.cpp:

Classes
struct	llvm::BasicAAResult::DecomposedGEP

Macros
#define	DEBUG_TYPE "basicaa"

Functions
	STATISTIC (SearchLimitReached, "Number of times the limit to " "decompose GEPs is reached")
	SearchLimitReached / SearchTimes shows how often the limit of to decompose GEPs is reached. More...

	STATISTIC (SearchTimes, "Number of times a GEP is decomposed")

static uint64_t	getObjectSize (const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, bool NullIsValidLoc, bool RoundToAlign=false)
	Returns the size of the object specified by V or UnknownSize if unknown. More...

static bool	isObjectSmallerThan (const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI, bool NullIsValidLoc)
	Returns true if we can prove that the object specified by V is smaller than Size. More...

static uint64_t	getMinimalExtentFrom (const Value &V, const LocationSize &LocSize, const DataLayout &DL, bool NullIsValidLoc)
	Return the minimal extent from `V` to the end of the underlying object, assuming the result is used in an aliasing query. More...

static bool	isObjectSize (const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI, bool NullIsValidLoc)
	Returns true if we can prove that the object specified by V has size Size. More...

static LinearExpression	GetLinearExpression (const CastedValue &Val, const DataLayout &DL, unsigned Depth, AssumptionCache AC, DominatorTree DT)
	Analyzes the specified value as a linear expression: "A*V + B", where A and B are constant integers. More...

static APInt	adjustToIndexSize (const APInt &Offset, unsigned IndexSize)
	To ensure a pointer offset fits in an integer of size IndexSize (in bits) when that size is smaller than the maximum index size. More...

static bool	isIntrinsicCall (const CallBase *Call, Intrinsic::ID IID)

static bool	isWriteOnlyParam (const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
	Returns true if this is a writeonly (i.e Mod only) parameter. More...

static const Function *	getParent (const Value *V)

static bool	notDifferentParent (const Value O1, const Value O2)

static bool	isBaseOfObject (const Value *V)
	Return true if we know V to the base address of the corresponding memory object. More...

static AliasResult	MergeAliasResults (AliasResult A, AliasResult B)

	INITIALIZE_PASS_BEGIN (BasicAAWrapperPass, "basic-aa", "Basic Alias Analysis (stateless AA impl)", true, true) INITIALIZE_PASS_END(BasicAAWrapperPass

basic Basic Alias	Analysis (stateless AA impl)"

Variables
static cl::opt< bool >	EnableRecPhiAnalysis ("basic-aa-recphi", cl::Hidden, cl::init(true))
	Enable analysis of recursive PHI nodes. More...

const unsigned	MaxNumPhiBBsValueReachabilityCheck = 20
	Cutoff after which to stop analysing a set of phi nodes potentially involved in a cycle. More...

static const unsigned	MaxLookupSearchDepth = 6

basic	aa

basic Basic Alias	true

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "basicaa"

Definition at line 62 of file BasicAliasAnalysis.cpp.

Function Documentation

◆ adjustToIndexSize()

static APInt adjustToIndexSize	(	const APInt &	Offset,
		unsigned	IndexSize
	)

static

To ensure a pointer offset fits in an integer of size IndexSize (in bits) when that size is smaller than the maximum index size.

This is an issue, for example, in particular for 32b pointers with negative indices that rely on two's complement wrap-arounds for precise alias information where the maximum index size is 64b.

Definition at line 448 of file BasicAliasAnalysis.cpp.

References assert().

◆ Analysis()

basic Basic Alias Analysis ( stateless AA impl )

◆ GetLinearExpression()

static LinearExpression GetLinearExpression	(	const CastedValue &	Val,
		const DataLayout &	DL,
		unsigned	Depth,
		AssumptionCache *	AC,
		DominatorTree *	DT
	)

static

Analyzes the specified value as a linear expression: "A*V + B", where A and B are constant integers.

Definition at line 348 of file BasicAliasAnalysis.cpp.

References llvm::MCID::Add, llvm::Depth, DL, E, llvm::MaskedValueIsZero(), Mul, and RHS.

◆ getMinimalExtentFrom()

static uint64_t getMinimalExtentFrom	(	const Value &	V,
		const LocationSize &	LocSize,
		const DataLayout &	DL,
		bool	NullIsValidLoc
	)

static

Return the minimal extent from V to the end of the underlying object, assuming the result is used in an aliasing query.

E.g., we do use the query location size and the fact that null pointers cannot alias here.

Definition at line 166 of file BasicAliasAnalysis.cpp.

References DL, llvm::Value::getPointerDereferenceableBytes(), llvm::LocationSize::getValue(), llvm::LocationSize::isPrecise(), and llvm::max().

◆ getObjectSize()

static uint64_t getObjectSize	(	const Value *	V,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI,
		bool	NullIsValidLoc,
		bool	RoundToAlign = `false`
	)

static

Returns the size of the object specified by V or UnknownSize if unknown.

Definition at line 107 of file BasicAliasAnalysis.cpp.

References DL, llvm::getObjectSize(), llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::ObjectSizeOpts::RoundToAlign, and llvm::MemoryLocation::UnknownSize.

◆ getParent()

static const Function* getParent ( const Value * V )

static

Examples: /home/buildbot/as-worker-4/publish-doxygen-docs/llvm-project/llvm/include/llvm/ADT/ilist_node.h.

Definition at line 847 of file BasicAliasAnalysis.cpp.

References llvm::GlobalValue::getParent().

Referenced by llvm::orc::IRSymbolMapper::add(), llvm::CanonicalLoopInfo::assertOK(), canVectorizeLoads(), llvm::CloneAndPruneIntoFromInst(), llvm::JumpThreadingPass::computeValueKnownInPredecessorsImpl(), detectPopcountIdiom(), llvm::DWARFDie::dump(), ensureValueAvailableInSuccessor(), llvm::VPWidenPointerInductionRecipe::execute(), llvm::VPScalarIVStepsRecipe::execute(), llvm::CodeExtractor::findAllocas(), llvm::InstCombinerImpl::foldOpIntoPhi(), llvm::RegionBase< RegionTraits< Function > >::getDepth(), llvm::VPBasicBlock::getEnclosingLoopRegion(), llvm::getLiveRegMap(), getLocalFunctionMetadata(), llvm::CoroIdAsyncInst::getStorage(), hasUsersIn(), isBlockValidForExtraction(), llvm::PHINode::isComplete(), llvm::VPBasicBlock::isExiting(), llvm::CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(), isUsedOutsideOfDefiningBlock(), LLVMGetBasicBlockParent(), LLVMGetGlobalParent(), LLVMGetInstructionParent(), LLVMGetParamParent(), llvm::PHITransAddr::NeedsPHITranslationFromBlock(), notDifferentParent(), llvm::GenericSSAContext< Function >::print(), llvm::MachineFunction::print(), redirectValuesFromPredecessorsToPhi(), llvm::AssumptionCache::registerAssumption(), llvm::VerifyInstrumentation::registerCallbacks(), llvm::VLIWMachineScheduler::schedule(), llvm::ScheduleDAGMI::schedule(), llvm::SIScheduleDAGMI::schedule(), llvm::ScheduleDAGMILive::schedule(), splitCallSite(), llvm::slpvectorizer::BoUpSLP::vectorizeTree(), and llvm::LoopBase< BasicBlock, Loop >::verifyLoop().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	BasicAAWrapperPass	,
		"basic-aa"	,
		"Basic Alias Analysis (stateless AA impl)"	,
		true	,
		true
	)

◆ isBaseOfObject()

static bool isBaseOfObject ( const Value * V )

static

Return true if we know V to the base address of the corresponding memory object.

This implies that any address less than V must be out of bounds for the underlying object. Note that just being isIdentifiedObject() is not enough - For example, a negative offset from a noalias argument or call can be inbounds w.r.t the actual underlying object.

Definition at line 1075 of file BasicAliasAnalysis.cpp.

◆ isIntrinsicCall()

static bool isIntrinsicCall	(	const CallBase *	Call,
		Intrinsic::ID	IID
	)

static

Definition at line 745 of file BasicAliasAnalysis.cpp.

References llvm::IntrinsicInst::getIntrinsicID().

Referenced by llvm::BasicAAResult::getModRefInfo().

◆ isObjectSize()

static bool isObjectSize	(	const Value *	V,
		uint64_t	Size,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI,
		bool	NullIsValidLoc
	)

static

Returns true if we can prove that the object specified by V has size Size.

Definition at line 186 of file BasicAliasAnalysis.cpp.

References DL, llvm::getObjectSize(), and llvm::MemoryLocation::UnknownSize.

◆ isObjectSmallerThan()

static bool isObjectSmallerThan	(	const Value *	V,
		uint64_t	Size,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI,
		bool	NullIsValidLoc
	)

static

Returns true if we can prove that the object specified by V is smaller than Size.

Definition at line 122 of file BasicAliasAnalysis.cpp.

References DL, llvm::getObjectSize(), llvm::isIdentifiedObject(), and llvm::MemoryLocation::UnknownSize.

◆ isWriteOnlyParam()

static bool isWriteOnlyParam	(	const CallBase *	Call,
		unsigned	ArgIdx,
		const TargetLibraryInfo &	TLI
	)

static

Returns true if this is a writeonly (i.e Mod only) parameter.

Definition at line 806 of file BasicAliasAnalysis.cpp.

References F, llvm::TargetLibraryInfo::getLibFunc(), and llvm::TargetLibraryInfo::has().

Referenced by llvm::BasicAAResult::getArgModRefInfo().

◆ MergeAliasResults()

static AliasResult MergeAliasResults	(	AliasResult	A,
		AliasResult	B
	)

static

Definition at line 1327 of file BasicAliasAnalysis.cpp.

References B, llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, and llvm::AliasResult::PartialAlias.

◆ notDifferentParent()

static bool notDifferentParent	(	const Value *	O1,
		const Value *	O2
	)

static

Definition at line 860 of file BasicAliasAnalysis.cpp.

References getParent().

Referenced by llvm::BasicAAResult::alias(), and llvm::BasicAAResult::getModRefInfo().

◆ STATISTIC() [1/2]

STATISTIC	(	SearchLimitReached	,
		"Number of times the limit to " "decompose GEPs is reached"
	)

SearchLimitReached / SearchTimes shows how often the limit of to decompose GEPs is reached.

It will affect the precision of basic alias analysis.

◆ STATISTIC() [2/2]

STATISTIC	(	SearchTimes	,
		"Number of times a GEP is decomposed"
	)

Variable Documentation

◆ aa

basic aa

Definition at line 1876 of file BasicAliasAnalysis.cpp.

◆ EnableRecPhiAnalysis

cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, cl::init(true))

static

Enable analysis of recursive PHI nodes.

◆ MaxLookupSearchDepth

const unsigned MaxLookupSearchDepth = 6

static

Definition at line 85 of file BasicAliasAnalysis.cpp.

◆ MaxNumPhiBBsValueReachabilityCheck

const unsigned MaxNumPhiBBsValueReachabilityCheck = 20

Cutoff after which to stop analysing a set of phi nodes potentially involved in a cycle.

Because we are analysing 'through' phi nodes, we need to be careful with value equivalence. We use reachability to make sure a value cannot be involved in a cycle.

Definition at line 81 of file BasicAliasAnalysis.cpp.

◆ true

print machine Print Machine Cycle Info true

Examples: /home/buildbot/as-worker-4/publish-doxygen-docs/llvm-project/llvm/include/llvm/ADT/ilist_node.h.

Definition at line 1877 of file BasicAliasAnalysis.cpp.

Referenced by llvm::PotentialValuesState< MemberTy >::contains(), llvm::PPCInstrInfo::getFMAPatterns(), hasBZHI(), llvm::X86CallLowering::lowerCall(), llvm::MIPatternMatch::GCstAndRegMatch::match(), llvm::MIPatternMatch::GFCstAndRegMatch::match(), matchIntrinsicType(), llvm::ScopedHandle< HandleTraits >::operator bool(), llvm::orc::BlockFreqQuery::operator()(), and llvm::TargetLowering::SimplifyDemandedVectorElts().

Classes

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ adjustToIndexSize()

◆ Analysis()

◆ GetLinearExpression()

◆ getMinimalExtentFrom()

◆ getObjectSize()

◆ getParent()

◆ INITIALIZE_PASS_BEGIN()

◆ isBaseOfObject()

◆ isIntrinsicCall()

◆ isObjectSize()

◆ isObjectSmallerThan()

◆ isWriteOnlyParam()

◆ MergeAliasResults()

◆ notDifferentParent()

◆ STATISTIC() [1/2]

◆ STATISTIC() [2/2]

Variable Documentation

◆ aa

◆ EnableRecPhiAnalysis

◆ MaxLookupSearchDepth

◆ MaxNumPhiBBsValueReachabilityCheck

◆ true