#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/GlobalVariable.h"
-#include "llvm/Instructions.h"
-#include "llvm/IntrinsicInst.h"
-#include "llvm/LLVMContext.h"
-#include "llvm/Operator.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"
static bool isObjectSmallerThan(const Value *V, uint64_t Size,
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);
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
//===----------------------------------------------------------------------===//
// 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
}
// 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 (V1Size == V2Size) {
+ if ((BaseAlias == MayAlias) && V1Size == V2Size) {
// Do the base pointers alias assuming type and size.
AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
V1TBAAInfo, UnderlyingV2,
GEP1VariableIndices.clear();
}
}
-
- // Do the base pointers alias?
- AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
- UnderlyingV2, UnknownSize, 0);
// If we get a No or May, then return it immediately, no amount of analysis
// will improve this situation.
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(f), PNSize, PNTBAAInfo,
- PN2->getIncomingValueForBlock(PN->getIncomingBlock(f)),
- V2Size, V2TBAAInfo);
- if (Alias == MayAlias)
- return MayAlias;
-
- // 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;
- }
+ // 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) {
- if (i == f)
- continue;
-
AliasResult ThisAlias =
aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
}
// Reset if speculation failed.
- if (ArePhisAssumedNoAlias && Alias != NoAlias)
+ 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.
projects / oota-llvm.git / blobdiff