//
//===----------------------------------------------------------------------===//
-#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Constants.h"
+#include "llvm/DataLayout.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalAlias.h"
#include "llvm/LLVMContext.h"
#include "llvm/Operator.h"
#include "llvm/Pass.h"
-#include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
-#include "llvm/Analysis/InstructionSimplify.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/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) {
// This function needs to use the aligned object size because we allow
// reads a bit past the end given sufficient alignment.
/// 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;
}
/// 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) {
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // 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()) {
+ LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
+ Location(V2, V2Size, V2TBAAInfo));
+ if (PN > V2)
+ std::swap(Locs.first, Locs.second);
+
+ // Find the first incoming phi value not from its parent.
+ unsigned f = 0;
+ while (PN->getIncomingBlock(f) == PN->getParent() &&
+ f < PN->getNumIncomingValues()-1)
+ ++f;
+
AliasResult Alias =
- aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
- PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
+ aliasCheck(PN->getIncomingValue(f), PNSize, PNTBAAInfo,
+ PN2->getIncomingValueForBlock(PN->getIncomingBlock(f)),
V2Size, V2TBAAInfo);
if (Alias == MayAlias)
return MayAlias;
- for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
+
+ // If the first source of the PHI nodes NoAlias and the other inputs are
+ // the PHI node itself through some amount of recursion this does not add
+ // any new information so just return NoAlias.
+ // bb:
+ // ptr = ptr2 + 1
+ // loop:
+ // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one]
+ // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one]
+ // ...
+ // ptr_plus_one = gep ptr_phi, 1
+ // ptr2_plus_one = gep ptr2_phi, 1
+ // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do
+ // not alias each other.
+ bool ArePhisAssumedNoAlias = false;
+ AliasResult OrigAliasResult = NoAlias;
+ if (Alias == NoAlias) {
+ // Pretend the phis do not alias.
+ assert(AliasCache.count(Locs) &&
+ "There must exist an entry for the phi node");
+ OrigAliasResult = AliasCache[Locs];
+ AliasCache[Locs] = NoAlias;
+ ArePhisAssumedNoAlias = true;
+ }
+
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+ if (i == f)
+ continue;
+
AliasResult ThisAlias =
aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
if (Alias == MayAlias)
break;
}
+
+ // Reset if speculation failed.
+ if (ArePhisAssumedNoAlias && Alias != NoAlias)
+ AliasCache[Locs] = OrigAliasResult;
+
return Alias;
}
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, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
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,