//
//===----------------------------------------------------------------------===//
-#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/GlobalAlias.h"
-#include "llvm/GlobalVariable.h"
-#include "llvm/Instructions.h"
-#include "llvm/IntrinsicInst.h"
-#include "llvm/LLVMContext.h"
-#include "llvm/Operator.h"
-#include "llvm/Pass.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Target/TargetLibraryInfo.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Function.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 "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>
using namespace llvm;
// then it has not escaped before entering the function. Check if it escapes
// inside the function.
if (const Argument *A = dyn_cast<Argument>(V))
- if (A->hasByValAttr() || A->hasNoAliasAttr()) {
- // Don't bother analyzing arguments already known not to escape.
- if (A->hasNoCaptureAttr())
- return true;
+ if (A->hasByValAttr() || A->hasNoAliasAttr())
+ // Note even if the argument is marked nocapture we still need to check
+ // for copies made inside the function. The nocapture attribute only
+ // specifies that there are no copies made that outlive the function.
return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
- }
+
return false;
}
/// getObjectSize - Return the size of the object specified by V, or
/// UnknownSize if unknown.
-static uint64_t getObjectSize(const Value *V, const TargetData &TD,
+static uint64_t getObjectSize(const Value *V, const DataLayout &TD,
const TargetLibraryInfo &TLI,
bool RoundToAlign = false) {
uint64_t Size;
/// isObjectSmallerThan - Return true if we can prove that the object specified
/// by V is smaller than Size.
static bool isObjectSmallerThan(const Value *V, uint64_t Size,
- const TargetData &TD,
+ const DataLayout &TD,
const TargetLibraryInfo &TLI) {
+ // Note that the meanings of the "object" are slightly different in the
+ // following contexts:
+ // c1: llvm::getObjectSize()
+ // c2: llvm.objectsize() intrinsic
+ // c3: isObjectSmallerThan()
+ // c1 and c2 share the same meaning; however, the meaning of "object" in c3
+ // refers to the "entire object".
+ //
+ // Consider this example:
+ // char *p = (char*)malloc(100)
+ // char *q = p+80;
+ //
+ // In the context of c1 and c2, the "object" pointed by q refers to the
+ // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
+ //
+ // However, in the context of c3, the "object" refers to the chunk of memory
+ // being allocated. So, the "object" has 100 bytes, and q points to the middle
+ // the "object". In case q is passed to isObjectSmallerThan() as the 1st
+ // parameter, before the llvm::getObjectSize() is called to get the size of
+ // entire object, we should:
+ // - either rewind the pointer q to the base-address of the object in
+ // question (in this case rewind to p), or
+ // - just give up. It is up to caller to make sure the pointer is pointing
+ // to the base address the object.
+ //
+ // We go for 2nd option for simplicity.
+ if (!isIdentifiedObject(V))
+ return false;
+
// This function needs to use the aligned object size because we allow
// reads a bit past the end given sufficient alignment.
uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true);
/// isObjectSize - Return true if we can prove that the object specified
/// by V has size Size.
static bool isObjectSize(const Value *V, uint64_t Size,
- const TargetData &TD, const TargetLibraryInfo &TLI) {
+ const DataLayout &TD, const TargetLibraryInfo &TLI) {
uint64_t ObjectSize = getObjectSize(V, TD, TLI);
return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size;
}
+/// isIdentifiedFunctionLocal - Return true if V is umabigously identified
+/// at the function-level. Different IdentifiedFunctionLocals can't alias.
+/// Further, an IdentifiedFunctionLocal can not alias with any function
+/// arguments other than itself, which is not neccessarily true for
+/// IdentifiedObjects.
+static bool isIdentifiedFunctionLocal(const Value *V)
+{
+ return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
+}
+
+
//===----------------------------------------------------------------------===//
// GetElementPtr Instruction Decomposition and Analysis
//===----------------------------------------------------------------------===//
const Value *V;
ExtensionKind Extension;
int64_t Scale;
+
+ bool operator==(const VariableGEPIndex &Other) const {
+ return V == Other.V && Extension == Other.Extension &&
+ Scale == Other.Scale;
+ }
+
+ bool operator!=(const VariableGEPIndex &Other) const {
+ return !operator==(Other);
+ }
};
}
/// represented in the result.
static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
ExtensionKind &Extension,
- const TargetData &TD, unsigned Depth) {
+ const DataLayout &TD, unsigned Depth) {
assert(V->getType()->isIntegerTy() && "Not an integer value");
// Limit our recursion depth.
/// specified amount, but which may have other unrepresented high bits. As such,
/// the gep cannot necessarily be reconstructed from its decomposed form.
///
-/// When TargetData is around, this function is capable of analyzing everything
+/// When DataLayout is around, this function is capable of analyzing everything
/// that GetUnderlyingObject can look through. When not, it just looks
/// through pointer casts.
///
static const Value *
DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
SmallVectorImpl<VariableGEPIndex> &VarIndices,
- const TargetData *TD) {
+ const DataLayout *TD) {
// Limit recursion depth to limit compile time in crazy cases.
unsigned MaxLookup = 6;
->getElementType()->isSized())
return V;
- // If we are lacking TargetData information, we can't compute the offets of
+ // If we are lacking DataLayout information, we can't compute the offets of
// elements computed by GEPs. However, we can handle bitcast equivalent
// GEPs.
if (TD == 0) {
/// BasicAliasAnalysis - This is the primary alias analysis implementation.
struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
static char ID; // Class identification, replacement for typeinfo
- BasicAliasAnalysis() : ImmutablePass(ID),
- // AliasCache rarely has more than 1 or 2 elements,
- // so start it off fairly small so that clear()
- // doesn't have to tromp through 64 (the default)
- // elements on each alias query. This really wants
- // something like a SmallDenseMap.
- AliasCache(8) {
+ BasicAliasAnalysis() : ImmutablePass(ID) {
initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry());
}
"BasicAliasAnalysis doesn't support interprocedural queries.");
AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag,
LocB.Ptr, LocB.Size, LocB.TBAATag);
- AliasCache.clear();
+ // AliasCache rarely has more than 1 or 2 elements, always use
+ // shrink_and_clear so it quickly returns to the inline capacity of the
+ // SmallDenseMap if it ever grows larger.
+ // FIXME: This should really be shrink_to_inline_capacity_and_clear().
+ AliasCache.shrink_and_clear();
return Alias;
}
private:
// AliasCache - Track alias queries to guard against recursion.
typedef std::pair<Location, Location> LocPair;
- typedef DenseMap<LocPair, AliasResult> AliasCacheTy;
+ typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
AliasCacheTy AliasCache;
// Visited - Track instructions visited by pointsToConstantMemory.
// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
// instruction against another.
AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
+ const MDNode *V1TBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo,
const Value *UnderlyingV1, const Value *UnderlyingV2);
// For intrinsics, we can check the table.
if (unsigned iid = F->getIntrinsicID()) {
#define GET_INTRINSIC_MODREF_BEHAVIOR
-#include "llvm/Intrinsics.gen"
+#include "llvm/IR/Intrinsics.gen"
#undef GET_INTRINSIC_MODREF_BEHAVIOR
}
return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min);
}
+static bool areVarIndicesEqual(SmallVector<VariableGEPIndex, 4> &Indices1,
+ SmallVector<VariableGEPIndex, 4> &Indices2) {
+ unsigned Size1 = Indices1.size();
+ unsigned Size2 = Indices2.size();
+
+ if (Size1 != Size2)
+ return false;
+
+ for (unsigned I = 0; I != Size1; ++I)
+ if (Indices1[I] != Indices2[I])
+ return false;
+
+ return true;
+}
+
/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
/// against another pointer. We know that V1 is a GEP, but we don't know
/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD),
///
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
+ const MDNode *V1TBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo,
const Value *UnderlyingV1,
int64_t GEP1BaseOffset;
SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
- // If we have two gep instructions with must-alias'ing base pointers, figure
- // out if the indexes to the GEP tell us anything about the derived pointer.
+ // If we have two gep instructions with must-alias or not-alias'ing base
+ // pointers, figure out if the indexes to the GEP tell us anything about the
+ // derived pointer.
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
// Do the base pointers alias?
AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
UnderlyingV2, UnknownSize, 0);
+
+ // Check for geps of non-aliasing underlying pointers where the offsets are
+ // identical.
+ if ((BaseAlias == MayAlias) && V1Size == V2Size) {
+ // Do the base pointers alias assuming type and size.
+ AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
+ V1TBAAInfo, UnderlyingV2,
+ V2Size, V2TBAAInfo);
+ if (PreciseBaseAlias == NoAlias) {
+ // See if the computed offset from the common pointer tells us about the
+ // relation of the resulting pointer.
+ int64_t GEP2BaseOffset;
+ SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
+ const Value *GEP2BasePtr =
+ DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
+ const Value *GEP1BasePtr =
+ DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
+ // DecomposeGEPExpression and GetUnderlyingObject should return the
+ // same result except when DecomposeGEPExpression has no DataLayout.
+ if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
+ assert(TD == 0 &&
+ "DecomposeGEPExpression and GetUnderlyingObject disagree!");
+ return MayAlias;
+ }
+ // Same offsets.
+ if (GEP1BaseOffset == GEP2BaseOffset &&
+ areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices))
+ return NoAlias;
+ GEP1VariableIndices.clear();
+ }
+ }
// If we get a No or May, then return it immediately, no amount of analysis
// will improve this situation.
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
- // If DecomposeGEPExpression isn't able to look all the way through the
- // addressing operation, we must not have TD and this is too complex for us
- // to handle without it.
+ // DecomposeGEPExpression and GetUnderlyingObject should return the
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
- // If DecomposeGEPExpression isn't able to look all the way through the
- // addressing operation, we must not have TD and this is too complex for us
- // to handle without it.
+ // DecomposeGEPExpression and GetUnderlyingObject should return the
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
// on corresponding edges.
if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
if (PN2->getParent() == PN->getParent()) {
- AliasResult Alias =
- aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
- PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
- V2Size, V2TBAAInfo);
- if (Alias == MayAlias)
- return MayAlias;
- for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
+ LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
+ Location(V2, V2Size, V2TBAAInfo));
+ if (PN > V2)
+ std::swap(Locs.first, Locs.second);
+ // Analyse the PHIs' inputs under the assumption that the PHIs are
+ // NoAlias.
+ // If the PHIs are May/MustAlias there must be (recursively) an input
+ // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
+ // there must be an operation on the PHIs within the PHIs' value cycle
+ // that causes a MayAlias.
+ // Pretend the phis do not alias.
+ AliasResult Alias = NoAlias;
+ assert(AliasCache.count(Locs) &&
+ "There must exist an entry for the phi node");
+ AliasResult OrigAliasResult = AliasCache[Locs];
+ AliasCache[Locs] = NoAlias;
+
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
AliasResult ThisAlias =
aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
if (Alias == MayAlias)
break;
}
+
+ // Reset if speculation failed.
+ if (Alias != NoAlias)
+ AliasCache[Locs] = OrigAliasResult;
+
return Alias;
}
(isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
return NoAlias;
- // Arguments can't alias with local allocations or noalias calls
- // in the same function.
- if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) ||
- (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1)))))
+ // Function arguments can't alias with things that are known to be
+ // unambigously identified at the function level.
+ if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
+ (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
return NoAlias;
// Most objects can't alias null.
std::swap(V1, V2);
std::swap(V1Size, V2Size);
std::swap(O1, O2);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
- AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, V2TBAAInfo, O1, O2);
+ AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
if (Result != MayAlias) return AliasCache[Locs] = Result;
}
if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo,
if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo,
projects / oota-llvm.git / blobdiff