#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/ADT/APInt.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/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/PhiValues.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constant.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/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.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:

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 bool	isNonEscapingLocalObject (const Value *V)
	Returns true if the pointer is to a function-local object that never escapes from the function. More...

static bool	isEscapeSource (const Value *V)
	Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalObject. More...

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 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 APInt	adjustToPointerSize (APInt Offset, unsigned PointerSize)
	To ensure a pointer offset fits in an integer of size PointerSize (in bits) when that size is smaller than the maximum pointer size. More...

static unsigned	getMaxPointerSize (const DataLayout &DL)

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 bool	isIntrinsicCall (const CallBase *Call, Intrinsic::ID IID)

static const Function *	getParent (const Value *V)

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

static AliasResult	aliasSameBasePointerGEPs (const GEPOperator GEP1, LocationSize MaybeV1Size, const GEPOperator GEP2, LocationSize MaybeV2Size, const DataLayout &DL)
	Provide ad-hoc rules to disambiguate accesses through two GEP operators, both having the exact same pointer operand. More...

static AliasResult	MergeAliasResults (AliasResult A, AliasResult B)

	INITIALIZE_PASS_BEGIN (BasicAAWrapperPass, "basicaa", "Basic Alias Analysis (stateless AA impl)", false, true) INITIALIZE_PASS_END(BasicAAWrapperPass

Basic Alias	Analysis (stateless AA impl)"

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

static cl::opt< bool >	ForceAtLeast64Bits ("basicaa-force-at-least-64b", cl::Hidden, cl::init(true))
	By default, even on 32-bit architectures we use 64-bit integers for calculations. More...

static cl::opt< bool >	DoubleCalcBits ("basicaa-double-calc-bits", cl::Hidden, cl::init(false))

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

	basicaa

Basic Alias	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "basicaa"

Definition at line 63 of file BasicAliasAnalysis.cpp.

Function Documentation

◆ adjustToPointerSize()

static APInt adjustToPointerSize	(	APInt	Offset,
		unsigned	PointerSize
	)

static

To ensure a pointer offset fits in an integer of size PointerSize (in bits) when that size is smaller than the maximum pointer 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 pointer size is 64b.

Definition at line 397 of file BasicAliasAnalysis.cpp.

References assert(), and llvm::APInt::getBitWidth().

Referenced by getMaxPointerSize().

◆ aliasSameBasePointerGEPs()

static AliasResult aliasSameBasePointerGEPs	(	const GEPOperator *	GEP1,
		LocationSize	MaybeV1Size,
		const GEPOperator *	GEP2,
		LocationSize	MaybeV2Size,
		const DataLayout &	DL
	)

static

Provide ad-hoc rules to disambiguate accesses through two GEP operators, both having the exact same pointer operand.

Definition at line 1042 of file BasicAliasAnalysis.cpp.

References assert(), llvm::computeKnownBits(), llvm::dyn_cast(), llvm::APInt::getActiveBits(), llvm::ConstantInt::getBitWidth(), llvm::StructLayout::getElementOffset(), llvm::GetElementPtrInst::getIndexedType(), getMaxPointerSize(), llvm::GEPOperator::getNumIndices(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::GEPOperator::getPointerOperand(), llvm::GEPOperator::getPointerOperandType(), llvm::StructLayout::getSizeInBytes(), llvm::GEPOperator::getSourceElementType(), llvm::DataLayout::getStructLayout(), llvm::Value::getType(), llvm::DataLayout::getTypeStoreSize(), llvm::LocationSize::getValue(), llvm::ConstantInt::getValue(), llvm::ConstantInt::getZExtValue(), llvm::APInt::intersects(), llvm::GEPOperator::isInBounds(), llvm::isKnownNonEqual(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::max(), llvm::MayAlias, llvm::MustAlias, llvm::NoAlias, llvm::KnownBits::One, llvm::PartialAlias, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::APInt::sextOrSelf(), llvm::APInt::sge(), llvm::APInt::sgt(), llvm::APInt::slt(), llvm::Value::stripPointerCastsAndInvariantGroups(), llvm::APInt::uge(), llvm::APInt::ult(), llvm::LocationSize::unknown(), llvm::NVPTX::PTXLdStInstCode::V2, and llvm::KnownBits::Zero.

◆ Analysis()

Basic Alias Analysis ( stateless AA impl )

◆ getMaxPointerSize()

static unsigned getMaxPointerSize ( const DataLayout & DL )

static

Definition at line 403 of file BasicAliasAnalysis.cpp.

References adjustToPointerSize(), DoubleCalcBits, llvm::dyn_cast(), E, ForceAtLeast64Bits, llvm::gep_type_begin(), llvm::getArgumentAliasingToReturnedPointer(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::Type::getIntegerBitWidth(), llvm::DataLayout::getMaxPointerSizeInBits(), llvm::APInt::getMinSignedBits(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::GEPOperator::getPointerAddressSpace(), llvm::DataLayout::getPointerSizeInBits(), llvm::GEPOperator::getSourceElementType(), llvm::DataLayout::getStructLayout(), llvm::generic_gep_type_iterator< ItTy >::getStructTypeOrNull(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), I, llvm::Type::isSized(), MaxLookupSearchDepth, llvm::User::op_begin(), llvm::User::op_end(), llvm::NVPTX::PTXCvtMode::RP, llvm::APInt::sext(), llvm::APInt::sextOrTrunc(), llvm::JumpTable::Simplified, and llvm::SimplifyInstruction().

Referenced by aliasSameBasePointerGEPs(), llvm::DataLayout::fitsInLegalInteger(), and llvm::DataLayout::getMaxPointerSizeInBits().

◆ 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 162 of file BasicAliasAnalysis.cpp.

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

◆ getParent()

static const Function* getParent ( const Value * V )

static

Examples:: /home/cs6340/llvm-8.0.1.src/include/llvm/ADT/ilist_node.h.

Definition at line 779 of file BasicAliasAnalysis.cpp.

References llvm::GlobalValue::getParent().

Referenced by AppendEndToFunction(), llvm::FastISel::canFoldAddIntoGEP(), llvm::DIE::children(), llvm::colorEHFunclets(), computeBranchTargetAndInversion(), llvm::JumpThreadingPass::ComputeValueKnownInPredecessorsImpl(), createBBSelectReg(), llvm::createSIFixWWMLivenessPass(), llvm::createX86OptimizeLEAs(), llvm::DWARFDie::dump(), ensureValueAvailableInSuccessor(), llvm::NamedMDNode::eraseFromParent(), llvm::CodeExtractor::findAllocas(), findBasePointers(), llvm::CodeExtractor::findInputsOutputs(), llvm::LiveVariables::VarInfo::findKill(), llvm::RegionBase< RegionTraits< Function > >::getDepth(), llvm::DWARFUnit::getDIEAtIndex(), getLocalFunctionMetadata(), getPHIDestReg(), GetPointerOperand(), llvm::LazyValueInfo::getPredicateAt(), getReductionValue(), llvm::GCProjectionInst::getStatepoint(), llvm::SelectionDAGBuilder::getValueImpl(), hasSameExtUse(), llvm::FastISel::hasTrivialKill(), insertSpills(), isBlockValidForExtraction(), llvm::CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(), isTargetConstant(), LLVMGetBasicBlockParent(), LLVMGetGlobalParent(), LLVMGetInstructionParent(), LLVMGetParamParent(), llvm::NVPTXTargetLowering::LowerFormalArguments(), MarkBlocksLiveIn(), llvm::MergeBlockIntoPredecessor(), llvm::PHITransAddr::NeedsPHITranslationFromBlock(), notDifferentParent(), llvm::MachineFunction::print(), llvm::Function::print(), llvm::NamedMDNode::print(), processSwitch(), propagateMetadata(), redirectValuesFromPredecessorsToPhi(), llvm::AssumptionCache::registerAssumption(), removeExternalCFGEdges(), llvm::replaceDominatedUsesWith(), llvm::VLIWMachineScheduler::schedule(), llvm::ScheduleDAGMI::schedule(), llvm::SIScheduleDAGMI::schedule(), llvm::ScheduleDAGMILive::schedule(), shouldRotateLoopExitingLatch(), sinkAndCmp0Expression(), splitCallSite(), StackMallocSizeClass(), tryUnmergingGEPsAcrossIndirectBr(), llvm::slpvectorizer::BoUpSLP::vectorizeTree(), and llvm::LoopBase< BasicBlock, Loop >::verifyLoop().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	BasicAAWrapperPass	,
		"basicaa"	,
		"Basic Alias Analysis (stateless AA impl)"	,
		false	,
		true
	)

Referenced by llvm::BasicAAWrapperPass::BasicAAWrapperPass().

◆ isEscapeSource()

static bool isEscapeSource ( const Value * V )

static

Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalObject.

Definition at line 145 of file BasicAliasAnalysis.cpp.

Referenced by MergeAliasResults().

◆ isIntrinsicCall()

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

static

Definition at line 773 of file BasicAliasAnalysis.cpp.

References llvm::dyn_cast(), and llvm::IntrinsicInst::getIntrinsicID().

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

◆ isNonEscapingLocalObject()

static bool isNonEscapingLocalObject ( const Value * V )

static

Returns true if the pointer is to a function-local object that never escapes from the function.

Definition at line 120 of file BasicAliasAnalysis.cpp.

References llvm::isNoAliasCall(), and llvm::PointerMayBeCaptured().

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

◆ 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 219 of file BasicAliasAnalysis.cpp.

References llvm::MCID::Add, assert(), llvm::Depth, llvm::APInt::getBitWidth(), llvm::APInt::getLimitedValue(), llvm::getObjectSize(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isIntegerTy(), LLVM_FALLTHROUGH, llvm::MaskedValueIsZero(), llvm::APInt::sext(), Size, llvm::APInt::trunc(), llvm::MemoryLocation::UnknownSize, and llvm::APInt::zextOrSelf().

Referenced by MergeAliasResults().

◆ 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 177 of file BasicAliasAnalysis.cpp.

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

Referenced by MergeAliasResults().

◆ 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 733 of file BasicAliasAnalysis.cpp.

References llvm::CallBase::getCalledFunction(), llvm::TargetLibraryInfo::getLibFunc(), llvm::TargetLibraryInfo::has(), llvm::CallBase::paramHasAttr(), and llvm::Attribute::WriteOnly.

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

◆ MergeAliasResults()

static AliasResult MergeAliasResults	(	AliasResult	A,
		AliasResult	B
	)

static

Definition at line 1493 of file BasicAliasAnalysis.cpp.

References llvm::APInt::abs(), llvm::AAResultBase< DerivedT >::AAResultsProxy::alias(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), EnableRecPhiAnalysis, llvm::SmallVectorImpl< T >::erase(), llvm::PointerType::getAddressSpace(), llvm::AAResultBase< DerivedT >::getBestAAResults(), llvm::SelectInst::getCondition(), llvm::SelectInst::getFalseValue(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::GlobalValue::getType(), llvm::GetUnderlyingObject(), llvm::LocationSize::getValue(), llvm::PhiValues::getValuesForPhi(), llvm::PHINode::incoming_values(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), isEscapeSource(), llvm::isIdentifiedFunctionLocal(), llvm::isIdentifiedObject(), isNonEscapingLocalObject(), isObjectSize(), isObjectSmallerThan(), llvm::Type::isPointerTy(), llvm::isPotentiallyReachable(), llvm::LocationSize::isPrecise(), llvm::LocationSize::isZero(), MaxLookupSearchDepth, MaxNumPhiBBsValueReachabilityCheck, llvm::MayAlias, llvm::MustAlias, llvm::NoAlias, llvm::NullPointerIsDefined(), P, llvm::PartialAlias, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), SI, llvm::SmallVectorBase::size(), llvm::SmallPtrSetImplBase::size(), llvm::Value::stripPointerCastsAndInvariantGroups(), std::swap(), llvm::APInt::uge(), llvm::APIntOps::umin(), llvm::LocationSize::unknown(), and llvm::APInt::zextOrTrunc().

◆ notDifferentParent()

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

static

Definition at line 792 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

◆ basicaa

basicaa

Definition at line 1999 of file BasicAliasAnalysis.cpp.

◆ DoubleCalcBits

cl::opt<bool> DoubleCalcBits("basicaa-double-calc-bits", cl::Hidden, cl::init(false))

static

Referenced by getMaxPointerSize().

◆ EnableRecPhiAnalysis

cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, cl::init(false))

static

Enable analysis of recursive PHI nodes.

Referenced by MergeAliasResults().

◆ false

Basic Alias false

Definition at line 2000 of file BasicAliasAnalysis.cpp.

◆ ForceAtLeast64Bits

cl::opt<bool> ForceAtLeast64Bits("basicaa-force-at-least-64b", cl::Hidden, cl::init(true))

static

By default, even on 32-bit architectures we use 64-bit integers for calculations.

This will allow us to more-aggressively decompose indexing expressions calculated using i64 values (e.g., long long in C) which is common enough to worry about.

Referenced by getMaxPointerSize().

◆ MaxLookupSearchDepth

const unsigned MaxLookupSearchDepth = 6

static

Definition at line 96 of file BasicAliasAnalysis.cpp.

Referenced by getMaxPointerSize(), and MergeAliasResults().

◆ 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 91 of file BasicAliasAnalysis.cpp.

Referenced by MergeAliasResults().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ adjustToPointerSize()

◆ aliasSameBasePointerGEPs()

◆ Analysis()

◆ getMaxPointerSize()

◆ getObjectSize()

◆ getParent()

◆ INITIALIZE_PASS_BEGIN()

◆ isEscapeSource()

◆ isIntrinsicCall()

◆ isNonEscapingLocalObject()

◆ isObjectSize()

◆ isObjectSmallerThan()

◆ isWriteOnlyParam()

◆ MergeAliasResults()

◆ notDifferentParent()

◆ STATISTIC() [1/2]

◆ STATISTIC() [2/2]

Variable Documentation

◆ basicaa

◆ DoubleCalcBits

◆ EnableRecPhiAnalysis

◆ false

◆ ForceAtLeast64Bits

◆ MaxLookupSearchDepth

◆ MaxNumPhiBBsValueReachabilityCheck