LLVM  6.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/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/CallSite.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)
 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 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)
 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)
 Returns true if we can prove that the object specified by V has size Size. More...
 
static int64_t adjustToPointerSize (int64_t Offset, unsigned PointerSize)
 To ensure a pointer offset fits in an integer of size PointerSize (in bits) when that size is smaller than 64. More...
 
static bool isWriteOnlyParam (ImmutableCallSite CS, unsigned ArgIdx, const TargetLibraryInfo &TLI)
 Returns true if this is a writeonly (i.e Mod only) parameter. More...
 
static bool isIntrinsicCall (ImmutableCallSite CS, Intrinsic::ID IID)
 
static const FunctiongetParent (const Value *V)
 
static bool notDifferentParent (const Value *O1, const Value *O2)
 
static AliasResult aliasSameBasePointerGEPs (const GEPOperator *GEP1, uint64_t V1Size, const GEPOperator *GEP2, uint64_t V2Size, 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)", true, 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...
 
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 true
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "basicaa"

Definition at line 63 of file BasicAliasAnalysis.cpp.

Function Documentation

◆ adjustToPointerSize()

static int64_t adjustToPointerSize ( int64_t  Offset,
unsigned  PointerSize 
)
static

◆ aliasSameBasePointerGEPs()

static AliasResult aliasSameBasePointerGEPs ( const GEPOperator GEP1,
uint64_t  V1Size,
const GEPOperator GEP2,
uint64_t  V2Size,
const DataLayout DL 
)
static

◆ Analysis()

Basic Alias Analysis ( stateless AA  impl)

◆ getObjectSize()

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

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

Definition at line 148 of file BasicAliasAnalysis.cpp.

References llvm::getObjectSize(), llvm::ObjectSizeOpts::RoundToAlign, llvm::AMDGPU::CodeObject::Kernel::Arg::Key::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 703 of file BasicAliasAnalysis.cpp.

References llvm::GlobalValue::getParent().

Referenced by llvm::FastISel::canFoldAddIntoGEP(), llvm::DIE::children(), llvm::colorEHFunclets(), llvm::JumpThreadingPass::ComputeValueKnownInPredecessors(), createBBSelectReg(), llvm::createX86OptimizeLEAs(), llvm::DWARFDie::dump(), ensureValueAvailableInSuccessor(), llvm::NamedMDNode::eraseFromParent(), llvm::CodeExtractor::findAllocas(), findBasePointers(), llvm::LiveVariables::VarInfo::findKill(), FindPhiPredForUseInBlock(), llvm::RegionBase< RegionTraits< Function > >::getDepth(), llvm::DWARFUnit::getDIEAtIndex(), getLocalFunction(), getPHIDestReg(), GetPointerOperand(), llvm::LazyValueInfo::getPredicateAt(), getReductionValue(), llvm::GCProjectionInst::getStatepoint(), llvm::SelectionDAGBuilder::getValueImpl(), hasSameExtUse(), llvm::FastISel::hasTrivialKill(), INITIALIZE_PASS(), insertSpills(), is_empty(), llvm::CodeExtractor::isBlockValidForExtraction(), llvm::CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(), isTargetConstant(), LLVMGetBasicBlockParent(), LLVMGetGlobalParent(), LLVMGetInstructionParent(), LLVMGetParamParent(), llvm::NVPTXTargetLowering::LowerFormalArguments(), MarkBlocksLiveIn(), llvm::PHITransAddr::NeedsPHITranslationFromBlock(), notDifferentParent(), PlaceMarkers(), preheader(), llvm::MachineFunction::print(), llvm::Function::print(), llvm::NamedMDNode::print(), processSwitch(), propagateMetadata(), redirectValuesFromPredecessorsToPhi(), llvm::AssumptionCache::registerAssumption(), removeExternalCFGEdges(), replaceAllUsesOfWithIn(), llvm::replaceDominatedUsesWith(), shouldReorderOperands(), sinkAndCmp0Expression(), 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)"  ,
true  ,
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 134 of file BasicAliasAnalysis.cpp.

Referenced by MergeAliasResults().

◆ isIntrinsicCall()

static bool isIntrinsicCall ( ImmutableCallSite  CS,
Intrinsic::ID  IID 
)
static

◆ 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 109 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 
)
static

◆ isObjectSmallerThan()

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

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

Definition at line 161 of file BasicAliasAnalysis.cpp.

References llvm::getObjectSize(), llvm::isIdentifiedObject(), llvm::AMDGPU::CodeObject::Kernel::Arg::Key::Size, and llvm::MemoryLocation::UnknownSize.

Referenced by MergeAliasResults().

◆ isWriteOnlyParam()

static bool isWriteOnlyParam ( ImmutableCallSite  CS,
unsigned  ArgIdx,
const TargetLibraryInfo TLI 
)
static

◆ MergeAliasResults()

static AliasResult MergeAliasResults ( AliasResult  A,
AliasResult  B 
)
static

Definition at line 1375 of file BasicAliasAnalysis.cpp.

References llvm::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::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::GetUnderlyingObject(), llvm::APInt::getZExtValue(), 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(), MaxNumPhiBBsValueReachabilityCheck, llvm::MayAlias, llvm::MustAlias, llvm::NoAlias, P, llvm::PartialAlias, llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), SI, llvm::SmallPtrSetImplBase::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::Value::stripPointerCastsAndBarriers(), std::swap(), llvm::APIntOps::umin(), and llvm::MemoryLocation::UnknownSize.

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

◆ EnableRecPhiAnalysis

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

Enable analysis of recursive PHI nodes.

Referenced by MergeAliasResults().

◆ MaxLookupSearchDepth

const unsigned MaxLookupSearchDepth = 6
static

Definition at line 86 of file BasicAliasAnalysis.cpp.

Referenced by adjustToPointerSize().

◆ 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.

Referenced by MergeAliasResults().

◆ true

dot regions Print regions of function to dot true view regions View regions of true