LLVM  14.0.0git
Macros | Functions | Variables
BasicAliasAnalysis.cpp File Reference
#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/InstructionSimplify.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/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/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:

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 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 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 ExtendedValue &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 adjustToPointerSize (const 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 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 FunctiongetParent (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...
 
static cl::opt< bool > ForceAtLeast64Bits ("basic-aa-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 ("basic-aa-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
 
basic aa
 
basic Basic Alias true
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "basicaa"

Definition at line 63 of file BasicAliasAnalysis.cpp.

Function Documentation

◆ adjustToPointerSize()

static APInt adjustToPointerSize ( const 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 402 of file BasicAliasAnalysis.cpp.

References assert(), Offset, and llvm::jitlink::x86_64::PointerSize.

◆ Analysis()

basic Basic Alias Analysis ( stateless AA  impl)

◆ GetLinearExpression()

static LinearExpression GetLinearExpression ( const ExtendedValue &  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 304 of file BasicAliasAnalysis.cpp.

References llvm::MCID::Add, llvm::Depth, DL, E, llvm::APInt::getLimitedValue(), LLVM_FALLTHROUGH, and llvm::MaskedValueIsZero().

◆ getMaxPointerSize()

static unsigned getMaxPointerSize ( const DataLayout DL)
static

Definition at line 408 of file BasicAliasAnalysis.cpp.

References DL, DoubleCalcBits, and ForceAtLeast64Bits.

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

References DL, llvm::getObjectSize(), llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::ObjectSizeOpts::RoundToAlign, llvm::Check::Size, 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 776 of file BasicAliasAnalysis.cpp.

References llvm::GlobalValue::getParent().

Referenced by llvm::orc::IRSymbolMapper::add(), llvm::CanonicalLoopInfo::assertOK(), llvm::CloneAndPruneIntoFromInst(), llvm::JumpThreadingPass::computeValueKnownInPredecessorsImpl(), detectPopcountIdiom(), ensureValueAvailableInSuccessor(), llvm::CodeExtractor::findAllocas(), llvm::LiveVariables::VarInfo::findKill(), llvm::InstCombinerImpl::foldOpIntoPhi(), llvm::RegionBase< RegionTraits< Function > >::getDepth(), llvm::getLiveRegMap(), getLocalFunctionMetadata(), llvm::CoroIdAsyncInst::getStorage(), hasUsersIn(), isBlockValidForExtraction(), llvm::PHINode::isComplete(), llvm::CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(), isUsedOutsideOfDefiningBlock(), LLVMGetBasicBlockParent(), LLVMGetGlobalParent(), LLVMGetInstructionParent(), LLVMGetParamParent(), llvm::NVPTXTargetLowering::LowerFormalArguments(), llvm::PHITransAddr::NeedsPHITranslationFromBlock(), notDifferentParent(), 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 1013 of file BasicAliasAnalysis.cpp.

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

◆ isIntrinsicCall()

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

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

References DL, llvm::getObjectSize(), llvm::Check::Size, 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 159 of file BasicAliasAnalysis.cpp.

References DL, llvm::getObjectSize(), llvm::isIdentifiedObject(), llvm::Check::Size, 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 735 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

◆ 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

◆ aa

basic aa

Definition at line 1814 of file BasicAliasAnalysis.cpp.

◆ DoubleCalcBits

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

Referenced by getMaxPointerSize().

◆ EnableRecPhiAnalysis

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

Enable analysis of recursive PHI nodes.

◆ ForceAtLeast64Bits

cl::opt<bool> ForceAtLeast64Bits("basic-aa-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.

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

◆ true

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