diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h | 2 | ||||
| -rw-r--r-- | llvm/lib/Analysis/BasicAliasAnalysis.cpp | 24 | ||||
| -rw-r--r-- | llvm/lib/Analysis/MemoryDependenceAnalysis.cpp | 49 | ||||
| -rw-r--r-- | llvm/test/Transforms/GVN/readonly-calls.ll | 29 |
4 files changed, 82 insertions, 22 deletions
diff --git a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h index d7b1fbf8b60..ceed0ab5446 100644 --- a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -248,7 +248,7 @@ namespace llvm { bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB); - MemDepResult getCallSiteDependencyFrom(CallSite C, + MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB); void getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size, diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index bc30c09217c..944d0e0d375 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -264,10 +264,8 @@ namespace { const Value *V2, unsigned V2Size); ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); - ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { - return NoAA::getModRefInfo(CS1,CS2); - } - + ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); + /// hasNoModRefInfoForCalls - We can provide mod/ref information against /// non-escaping allocations. virtual bool hasNoModRefInfoForCalls() const { return false; } @@ -352,6 +350,24 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { } +AliasAnalysis::ModRefResult +BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { + // If CS1 or CS2 are readnone, they don't interact. + ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); + if (CS1B == DoesNotAccessMemory) return NoModRef; + + ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); + if (CS2B == DoesNotAccessMemory) return NoModRef; + + // If they both only read from memory, just return ref. + if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) + return Ref; + + // Otherwise, fall back to NoAA (mod+ref). + return NoAA::getModRefInfo(CS1, CS2); +} + + // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such // as array references. Note that this function is heavily tail recursive. // Hopefully we have a smart C++ compiler. :) diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index 9fcbd8dbf05..42114938edf 100644 --- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -99,8 +99,8 @@ static void RemoveFromReverseMap(DenseMap<Instruction*, /// getCallSiteDependencyFrom - Private helper for finding the local /// dependencies of a call site. MemDepResult MemoryDependenceAnalysis:: -getCallSiteDependencyFrom(CallSite CS, BasicBlock::iterator ScanIt, - BasicBlock *BB) { +getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, + BasicBlock::iterator ScanIt, BasicBlock *BB) { // Walk backwards through the block, looking for dependencies while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; @@ -122,20 +122,31 @@ getCallSiteDependencyFrom(CallSite CS, BasicBlock::iterator ScanIt, } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { CallSite InstCS = CallSite::get(Inst); // If these two calls do not interfere, look past it. - if (AA->getModRefInfo(CS, InstCS) == AliasAnalysis::NoModRef) + switch (AA->getModRefInfo(CS, InstCS)) { + case AliasAnalysis::NoModRef: + // If the two calls don't interact (e.g. InstCS is readnone) keep + // scanning. continue; - - // FIXME: If this is a ref/ref result, we should ignore it! - // X = strlen(P); - // Y = strlen(Q); - // Z = strlen(P); // Z = X - - // If they interfere, we generally return clobber. However, if they are - // calls to the same read-only functions we return Def. - if (!AA->onlyReadsMemory(CS) || CS.getCalledFunction() == 0 || - CS.getCalledFunction() != InstCS.getCalledFunction()) + case AliasAnalysis::Ref: + // If the two calls read the same memory locations and CS is a readonly + // function, then we have two cases: 1) the calls may not interfere with + // each other at all. 2) the calls may produce the same value. In case + // #1 we want to ignore the values, in case #2, we want to return Inst + // as a Def dependence. This allows us to CSE in cases like: + // X = strlen(P); + // memchr(...); + // Y = strlen(P); // Y = X + if (isReadOnlyCall) { + if (CS.getCalledFunction() != 0 && + CS.getCalledFunction() == InstCS.getCalledFunction()) + return MemDepResult::getDef(Inst); + // Ignore unrelated read/read call dependences. + continue; + } + // FALL THROUGH + default: return MemDepResult::getClobber(Inst); - return MemDepResult::getDef(Inst); + } } else { // Non-memory instruction. continue; @@ -212,7 +223,6 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, } // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. - // FIXME: If this is a load, we should ignore readonly calls! switch (AA->getModRefInfo(Inst, MemPtr, MemSize)) { case AliasAnalysis::NoModRef: // If the call has no effect on the queried pointer, just ignore it. @@ -289,7 +299,9 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { MemSize = TD->getTypeStoreSize(LI->getType()); } } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) { - LocalCache = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos, + CallSite QueryCS = CallSite::get(QueryInst); + bool isReadOnly = AA->onlyReadsMemory(QueryCS); + LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, QueryParent); } else if (FreeInst *FI = dyn_cast<FreeInst>(QueryInst)) { MemPtr = FI->getPointerOperand(); @@ -367,6 +379,9 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { NumUncacheNonLocal++; } + // isReadonlyCall - If this is a read-only call, we can be more aggressive. + bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); + // Visited checked first, vector in sorted order. SmallPtrSet<BasicBlock*, 64> Visited; @@ -417,7 +432,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { MemDepResult Dep; if (ScanPos != DirtyBB->begin()) { - Dep = getCallSiteDependencyFrom(QueryCS, ScanPos, DirtyBB); + Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { // No dependence found. If this is the entry block of the function, it is // a clobber, otherwise it is non-local. diff --git a/llvm/test/Transforms/GVN/readonly-calls.ll b/llvm/test/Transforms/GVN/readonly-calls.ll new file mode 100644 index 00000000000..723ef774929 --- /dev/null +++ b/llvm/test/Transforms/GVN/readonly-calls.ll @@ -0,0 +1,29 @@ +; RUN: llvm-as < %s | opt -basicaa -gvn | llvm-dis | grep {call.*strlen} | count 1 +; Should delete the second call to strlen even though the intervening strchr call exists. + +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" +target triple = "i386-apple-darwin7" + +define i8* @test(i8* %P, i8* %Q, i32 %x, i32 %y) nounwind readonly { +entry: + %0 = tail call i32 @strlen(i8* %P) nounwind readonly ; <i32> [#uses=2] + %1 = icmp eq i32 %0, 0 ; <i1> [#uses=1] + br i1 %1, label %bb, label %bb1 + +bb: ; preds = %entry + %2 = sdiv i32 %x, %y ; <i32> [#uses=1] + br label %bb1 + +bb1: ; preds = %bb, %entry + %x_addr.0 = phi i32 [ %2, %bb ], [ %x, %entry ] ; <i32> [#uses=1] + %3 = tail call i8* @strchr(i8* %Q, i32 97) nounwind readonly ; <i8*> [#uses=1] + %4 = tail call i32 @strlen(i8* %P) nounwind readonly ; <i32> [#uses=1] + %5 = add i32 %x_addr.0, %0 ; <i32> [#uses=1] + %.sum = sub i32 %5, %4 ; <i32> [#uses=1] + %6 = getelementptr i8* %3, i32 %.sum ; <i8*> [#uses=1] + ret i8* %6 +} + +declare i32 @strlen(i8*) nounwind readonly + +declare i8* @strchr(i8*, i32) nounwind readonly |
