Enhance GVN to do more precise alias queries for non-local memory
references. For example, this allows gvn to eliminate the load in
this example:
void foo(int n, int* p, int *q) {
p[0] = 0;
p[1] = 1;
if (n) {
*q = p[0];
}
}
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118714 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/MemDepPrinter.cpp b/lib/Analysis/MemDepPrinter.cpp
index 597daff..90a7c57 100644
--- a/lib/Analysis/MemDepPrinter.cpp
+++ b/lib/Analysis/MemDepPrinter.cpp
@@ -11,6 +11,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CallSite.h"
@@ -40,7 +41,8 @@
void print(raw_ostream &OS, const Module * = 0) const;
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<MemoryDependenceAnalysis>();
+ AU.addRequiredTransitive<AliasAnalysis>();
+ AU.addRequiredTransitive<MemoryDependenceAnalysis>();
AU.setPreservesAll();
}
@@ -64,6 +66,7 @@
bool MemDepPrinter::runOnFunction(Function &F) {
this->F = &F;
+ AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
// All this code uses non-const interfaces because MemDep is not
@@ -99,15 +102,23 @@
SmallVector<NonLocalDepResult, 4> NLDI;
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
// FIXME: Volatile is not handled properly here.
- MDA.getNonLocalPointerDependency(LI->getPointerOperand(), !LI->isVolatile(),
+ AliasAnalysis::Location Loc(LI->getPointerOperand(),
+ AA.getTypeStoreSize(LI->getType()),
+ LI->getMetadata(LLVMContext::MD_tbaa));
+ MDA.getNonLocalPointerDependency(Loc, !LI->isVolatile(),
LI->getParent(), NLDI);
} else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
// FIXME: Volatile is not handled properly here.
- MDA.getNonLocalPointerDependency(SI->getPointerOperand(), false,
- SI->getParent(), NLDI);
+ AliasAnalysis::Location Loc(SI->getPointerOperand(),
+ AA.getTypeStoreSize(SI->getValueOperand()
+ ->getType()),
+ SI->getMetadata(LLVMContext::MD_tbaa));
+ MDA.getNonLocalPointerDependency(Loc, false, SI->getParent(), NLDI);
} else if (VAArgInst *VI = dyn_cast<VAArgInst>(Inst)) {
- MDA.getNonLocalPointerDependency(VI->getPointerOperand(), false,
- VI->getParent(), NLDI);
+ AliasAnalysis::Location Loc(SI->getPointerOperand(),
+ AliasAnalysis::UnknownSize,
+ SI->getMetadata(LLVMContext::MD_tbaa));
+ MDA.getNonLocalPointerDependency(Loc, false, VI->getParent(), NLDI);
} else {
llvm_unreachable("Unknown memory instruction!");
}
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index c72cd1e..b4c6d09 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -741,16 +741,40 @@
// Look up the cached info for Pointer.
ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
- NonLocalPointerInfo *CacheInfo = &NonLocalPointerDeps[CacheKey];
- // If this query's TBAATag is inconsistent with the cached one, discard the
- // tag and restart the query.
- if (CacheInfo->TBAATag != Loc.TBAATag) {
- CacheInfo->TBAATag = 0;
- NonLocalPointerDeps.erase(CacheKey);
- return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
- isLoad, StartBB, Result, Visited,
- SkipFirstBlock);
+ // Set up a temporary NLPI value. If the map doesn't yet have an entry for
+ // CacheKey, this value will be inserted as the associated value. Otherwise,
+ // it'll be ignored, and we'll have to check to see if the cached size and
+ // tbaa tag are consistent with the current query.
+ NonLocalPointerInfo InitialNLPI;
+ InitialNLPI.Size = Loc.Size;
+ InitialNLPI.TBAATag = Loc.TBAATag;
+
+ // Get the NLPI for CacheKey, inserting one into the map if it doesn't
+ // already have one.
+ std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
+ NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
+ NonLocalPointerInfo *CacheInfo = &Pair.first->second;
+
+ if (!Pair.second) {
+ // If this query's Size is inconsistent with the cached one, take the
+ // maximum size and restart the query.
+ if (CacheInfo->Size != Loc.Size) {
+ CacheInfo->Size = std::max(CacheInfo->Size, Loc.Size);
+ return getNonLocalPointerDepFromBB(Pointer,
+ Loc.getWithNewSize(CacheInfo->Size),
+ isLoad, StartBB, Result, Visited,
+ SkipFirstBlock);
+ }
+
+ // If this query's TBAATag is inconsistent with the cached one, discard the
+ // tag and restart the query.
+ if (CacheInfo->TBAATag != Loc.TBAATag) {
+ CacheInfo->TBAATag = 0;
+ return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
+ isLoad, StartBB, Result, Visited,
+ SkipFirstBlock);
+ }
}
NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
@@ -796,6 +820,7 @@
CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
else {
CacheInfo->Pair = BBSkipFirstBlockPair();
+ CacheInfo->Size = 0;
CacheInfo->TBAATag = 0;
}
@@ -921,6 +946,7 @@
// cached value to do more work but not miss the phi trans failure.
NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
NLPI.Pair = BBSkipFirstBlockPair();
+ NLPI.Size = 0;
NLPI.TBAATag = 0;
continue;
}
@@ -949,6 +975,7 @@
// specific block queries) but we can't do the fastpath "return all
// results from the set" Clear out the indicator for this.
CacheInfo->Pair = BBSkipFirstBlockPair();
+ CacheInfo->Size = 0;
CacheInfo->TBAATag = 0;
SkipFirstBlock = false;
continue;
@@ -967,6 +994,7 @@
// specific block queries) but we can't do the fastpath "return all
// results from the set". Clear out the indicator for this.
CacheInfo->Pair = BBSkipFirstBlockPair();
+ CacheInfo->Size = 0;
CacheInfo->TBAATag = 0;
// If *nothing* works, mark the pointer as being clobbered by the first
@@ -1184,6 +1212,7 @@
// The cache is not valid for any specific block anymore.
NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
+ NonLocalPointerDeps[P].Size = 0;
NonLocalPointerDeps[P].TBAATag = 0;
// Update any entries for RemInst to use the instruction after it.