Teach BasicAA::getModRefInfo(CallSite, CallSite) some

tricks based on readnone/readonly functions.

Teach memdep to look past readonly calls when analyzing
deps for a readonly call.  This allows elimination of a
few more calls from 403.gcc:

before:
     63 gvn    - Number of instructions PRE'd
 153986 gvn    - Number of instructions deleted
  50069 gvn    - Number of loads deleted

after:
     63 gvn    - Number of instructions PRE'd
 153991 gvn    - Number of instructions deleted
  50069 gvn    - Number of loads deleted

5 calls isn't much, but this adds plumbing for the next change.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60794 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 82 insertions, 22 deletions

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index d7b1fbf..ceed0ab 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/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/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index bc30c09..944d0e0 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/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/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 9fcbd8d..4211493 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/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/test/Transforms/GVN/readonly-calls.ll b/test/Transforms/GVN/readonly-calls.ll
new file mode 100644
index 0000000..723ef77
--- /dev/null
+++ b/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