LLVM  mainline
Defines | Enumerations | Functions | Variables
BasicAliasAnalysis.cpp File Reference
#include "llvm/Analysis/Passes.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.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/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.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/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/Pass.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include "llvm/IR/Intrinsics.gen"
Include dependency graph for BasicAliasAnalysis.cpp:

Go to the source code of this file.




enum  ExtensionKind


static bool isNonEscapingLocalObject (const Value *V)
static bool isEscapeSource (const Value *V)
static uint64_t getObjectSize (const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, bool RoundToAlign=false)
static bool isObjectSmallerThan (const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI)
static bool isObjectSize (const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI)
static ValueGetLinearExpression (Value *V, APInt &Scale, APInt &Offset, ExtensionKind &Extension, const DataLayout &DL, unsigned Depth, AssumptionCache *AC, DominatorTree *DT)
static const ValueDecomposeGEPExpression (const Value *V, int64_t &BaseOffs, SmallVectorImpl< VariableGEPIndex > &VarIndices, bool &MaxLookupReached, const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT)
static const FunctiongetParent (const Value *V)
static bool notDifferentParent (const Value *O1, const Value *O2)
 INITIALIZE_AG_PASS_BEGIN (BasicAliasAnalysis, AliasAnalysis,"basicaa","Basic Alias Analysis (stateless AA impl)", false, true, false) INITIALIZE_AG_PASS_END(BasicAliasAnalysis
Basic Alias Analysis (stateless AA impl)"
static bool isMemsetPattern16 (const Function *MS, const TargetLibraryInfo &TLI)
static bool isAssumeIntrinsic (ImmutableCallSite CS)
static AliasAnalysis::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.
static AliasAnalysis::AliasResult MergeAliasResults (AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B)


const unsigned MaxNumPhiBBsValueReachabilityCheck = 20
static const unsigned MaxLookupSearchDepth = 6
Basic Alias false
Basic Alias true

Define Documentation

Enumeration Type Documentation

Definition at line 165 of file BasicAliasAnalysis.cpp.

Function Documentation

static AliasAnalysis::AliasResult aliasSameBasePointerGEPs ( const GEPOperator GEP1,
uint64_t  V1Size,
const GEPOperator GEP2,
uint64_t  V2Size,
const DataLayout DL 
) [static]
Basic Alias Analysis ( stateless AA  impl)
static const Value* DecomposeGEPExpression ( const Value V,
int64_t &  BaseOffs,
SmallVectorImpl< VariableGEPIndex > &  VarIndices,
bool MaxLookupReached,
const DataLayout DL,
AssumptionCache AC,
DominatorTree DT 
) [static]

DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it into a base pointer with a constant offset and a number of scaled symbolic offsets.

The scaled symbolic offsets (represented by pairs of a Value* and a scale in the VarIndices vector) are Value*'s that are known to be scaled by the specified amount, but which may have other unrepresented high bits. As such, the gep cannot necessarily be reconstructed from its decomposed form.

When DataLayout is around, this function is capable of analyzing everything that GetUnderlyingObject can look through. To be able to do that GetUnderlyingObject and DecomposeGEPExpression must use the same search depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks through pointer casts.

Definition at line 293 of file BasicAliasAnalysis.cpp.

References llvm::AddrSpaceCast, llvm::SmallVectorTemplateCommon< T >::begin(), llvm::dyn_cast(), llvm::SmallVectorImpl< T >::erase(), llvm::gep_type_begin(), llvm::StructLayout::getElementOffset(), llvm::Type::getIntegerBitWidth(), GetLinearExpression(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::GEPOperator::getPointerAddressSpace(), llvm::Type::getPointerElementType(), llvm::DataLayout::getPointerSizeInBits(), llvm::APInt::getSExtValue(), llvm::DataLayout::getStructLayout(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), I, llvm::Type::isSized(), MaxLookupSearchDepth, llvm::User::op_begin(), llvm::User::op_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::JumpTable::Simplified, llvm::SimplifyInstruction(), and llvm::SmallVectorTemplateCommon< T >::size().

static Value* GetLinearExpression ( Value V,
APInt Scale,
APInt Offset,
ExtensionKind Extension,
const DataLayout DL,
unsigned  Depth,
AssumptionCache AC,
DominatorTree DT 
) [static]

GetLinearExpression - Analyze the specified value as a linear expression: "A*V + B", where A and B are constant integers. Return the scale and offset values as APInts and return V as a Value*, and return whether we looked through any sign or zero extends. The incoming Value is known to have IntegerType and it may already be sign or zero extended.

Note that this looks through extends, so the high bits may not be represented in the result.

Definition at line 196 of file BasicAliasAnalysis.cpp.

References llvm::DL, llvm::APInt::getBitWidth(), llvm::APInt::getLimitedValue(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::MaskedValueIsZero(), llvm::APIntOps::Or(), llvm::APInt::sext(), llvm::APInt::trunc(), and llvm::APInt::zext().

Referenced by DecomposeGEPExpression().

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

getObjectSize - Return the size of the object specified by V, or UnknownSize if unknown.

Definition at line 102 of file BasicAliasAnalysis.cpp.

References llvm::getObjectSize(), and llvm::AliasAnalysis::UnknownSize.

static const Function* getParent ( const Value V) [static]
INITIALIZE_AG_PASS_BEGIN ( BasicAliasAnalysis  ,
AliasAnalysis  ,
"basicaa"  ,
"Basic Alias Analysis (stateless AA impl)"  ,
false  ,
true  ,
static bool isAssumeIntrinsic ( ImmutableCallSite  CS) [static]
static bool isEscapeSource ( const Value V) [static]

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

Definition at line 87 of file BasicAliasAnalysis.cpp.

static bool isMemsetPattern16 ( const Function MS,
const TargetLibraryInfo TLI 
) [static]
static bool isNonEscapingLocalObject ( const Value V) [static]

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

Definition at line 62 of file BasicAliasAnalysis.cpp.

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

static bool isObjectSize ( const Value V,
uint64_t  Size,
const DataLayout DL,
const TargetLibraryInfo TLI 
) [static]

isObjectSize - Return true if we can prove that the object specified by V has size Size.

Definition at line 154 of file BasicAliasAnalysis.cpp.

References llvm::getObjectSize(), and llvm::AliasAnalysis::UnknownSize.

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

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

Definition at line 113 of file BasicAliasAnalysis.cpp.

References llvm::getObjectSize(), llvm::isIdentifiedObject(), and llvm::AliasAnalysis::UnknownSize.

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

Definition at line 437 of file BasicAliasAnalysis.cpp.

References getParent().

Variable Documentation

Definition at line 583 of file BasicAliasAnalysis.cpp.

Definition at line 583 of file BasicAliasAnalysis.cpp.

Basic Alias false

Definition at line 585 of file BasicAliasAnalysis.cpp.

Definition at line 54 of file BasicAliasAnalysis.cpp.

Referenced by DecomposeGEPExpression().

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

Basic Alias true

Definition at line 585 of file BasicAliasAnalysis.cpp.