LLVM  9.0.0svn
Macros | Functions | Variables
BasicAliasAnalysis.cpp File Reference
#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:

Go to the source code of this file.

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, SmallDenseMap< const Value *, bool, 8 > *IsCapturedCache=nullptr)
 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 FunctiongetParent (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< boolEnableRecPhiAnalysis ("basicaa-recphi", cl::Hidden, cl::init(false))
 Enable analysis of recursive PHI nodes. More...
 
static cl::opt< boolForceAtLeast64Bits ("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< boolDoubleCalcBits ("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 62 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 415 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

◆ Analysis()

Basic Alias Analysis ( stateless AA  impl)

◆ getMaxPointerSize()

static unsigned getMaxPointerSize ( const DataLayout DL)
static

◆ 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 180 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:
/opt/doxygen-docs/src/llvm/include/llvm/ADT/ilist_node.h.

Definition at line 797 of file BasicAliasAnalysis.cpp.

References llvm::GlobalValue::getParent().

Referenced by appendEndToFunction(), llvm::FastISel::canFoldAddIntoGEP(), llvm::DIE::children(), llvm::colorEHFunclets(), computeBranchTargetAndInversion(), llvm::JumpThreadingPass::ComputeValueKnownInPredecessorsImpl(), createBBSelectReg(), createCallInst(), llvm::createX86OptimizeLEAs(), llvm::DWARFDie::dump(), ensureValueAvailableInSuccessor(), llvm::NamedMDNode::eraseFromParent(), llvm::CodeExtractor::findAllocas(), findBasePointers(), llvm::LiveVariables::VarInfo::findKill(), foldOperationIntoPhiValue(), 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(), INITIALIZE_PASS(), insertLifetimeMarkersSurroundingCall(), 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(), propagateMetadata(), redirectValuesFromPredecessorsToPhi(), llvm::AssumptionCache::registerAssumption(), llvm::replaceDominatedUsesWith(), llvm::VLIWMachineScheduler::schedule(), llvm::ScheduleDAGMI::schedule(), llvm::SIScheduleDAGMI::schedule(), llvm::ScheduleDAGMILive::schedule(), shouldRotateLoopExitingLatch(), sinkAndCmp0Expression(), splitCallSite(), 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   
)

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

Referenced by MergeAliasResults().

◆ isIntrinsicCall()

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

◆ isNonEscapingLocalObject()

static bool isNonEscapingLocalObject ( const Value V,
SmallDenseMap< const Value *, bool, 8 > *  IsCapturedCache = nullptr 
)
static

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

Definition at line 119 of file BasicAliasAnalysis.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isNoAliasCall(), llvm::PointerMayBeCaptured(), and llvm::MipsISD::Ret.

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

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

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

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

◆ MergeAliasResults()

static AliasResult MergeAliasResults ( AliasResult  A,
AliasResult  B 
)
static

Definition at line 1513 of file BasicAliasAnalysis.cpp.

References llvm::APInt::abs(), llvm::AAResultBase< DerivedT >::AAResultsProxy::alias(), llvm::AAQueryInfo::AliasCache, assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), EnableRecPhiAnalysis, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), 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(), llvm::AAQueryInfo::IsCapturedCache, 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, bool >::push_back(), llvm::SmallVectorTemplateBase< T >::push_back(), SI, llvm::SmallVectorBase::size(), llvm::SmallPtrSetImplBase::size(), llvm::Value::stripPointerCastsAndInvariantGroups(), std::swap(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), llvm::APInt::uge(), llvm::APIntOps::umin(), llvm::LocationSize::unknown(), and llvm::APInt::zextOrTrunc().

◆ notDifferentParent()

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

◆ 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 2042 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 2043 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 95 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 90 of file BasicAliasAnalysis.cpp.

Referenced by MergeAliasResults().