diff options
author | Dan Gohman <gohman@apple.com> | 2010-11-10 20:37:15 +0000 |
---|---|---|
committer | Dan Gohman <gohman@apple.com> | 2010-11-10 20:37:15 +0000 |
commit | 075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2a (patch) | |
tree | bd2ac0b33edd3125d8741077ff4a5c274276b35e /lib/Analysis | |
parent | af3d38f70ebba9fec0048c2540dbdf0168d280d2 (diff) | |
download | llvm-075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2a.tar.gz llvm-075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2a.tar.bz2 llvm-075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2a.tar.xz |
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
Diffstat (limited to 'lib/Analysis')
-rw-r--r-- | lib/Analysis/MemDepPrinter.cpp | 23 | ||||
-rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 47 |
2 files changed, 55 insertions, 15 deletions
diff --git a/lib/Analysis/MemDepPrinter.cpp b/lib/Analysis/MemDepPrinter.cpp index 597daff8db..90a7c576f0 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 @@ namespace { 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 @@ FunctionPass *llvm::createMemDepPrinter() { 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 @@ bool MemDepPrinter::runOnFunction(Function &F) { 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 c72cd1e83a..b4c6d09e4c 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -741,16 +741,40 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // 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 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); else { CacheInfo->Pair = BBSkipFirstBlockPair(); + CacheInfo->Size = 0; CacheInfo->TBAATag = 0; } @@ -921,6 +946,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // 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 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // 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 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // 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 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { // 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. |