Add a new experimental generalized dependence query interface to

AliasAnalysis, and some code for implementing the new query on top of
existing implementations by making standard alias and getModRefInfo
queries.


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

2 files changed, 212 insertions, 0 deletions

diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp
index 1f2528f..536b759 100644
--- a/lib/Analysis/AliasAnalysis.cpp
+++ b/lib/Analysis/AliasAnalysis.cpp
@@ -188,6 +188,14 @@ AliasAnalysis::getModRefBehavior(const Function *F) {
   return AA->getModRefBehavior(F);
 }
 
+AliasAnalysis::DependenceResult
+AliasAnalysis::getDependence(const Instruction *First,
+                             DependenceQueryFlags FirstFlags,
+                             const Instruction *Second,
+                             DependenceQueryFlags SecondFlags) {
+  assert(AA && "AA didn't call InitializeAliasAnalyais in its run method!");
+  return AA->getDependence(First, FirstFlags, Second, SecondFlags);
+}
 
 //===----------------------------------------------------------------------===//
 // AliasAnalysis non-virtual helper method implementation
@@ -245,6 +253,190 @@ AliasAnalysis::getModRefInfo(const VAArgInst *V, const Value *P, unsigned Size)
   return ModRef;
 }
 
+AliasAnalysis::DependenceResult
+AliasAnalysis::getDependenceViaModRefInfo(const Instruction *First,
+                                          DependenceQueryFlags FirstFlags,
+                                          const Instruction *Second,
+                                          DependenceQueryFlags SecondFlags) {
+  if (const LoadInst *L = dyn_cast<LoadInst>(First)) {
+    // Be over-conservative with volatile for now.
+    if (L->isVolatile())
+      return Unknown;
+
+    // Forward this query to getModRefInfo.
+    switch (getModRefInfo(Second,
+                          L->getPointerOperand(),
+                          getTypeStoreSize(L->getType()))) {
+    case NoModRef:
+      // Second doesn't reference First's memory, so they're independent.
+      return Independent;
+
+    case Ref:
+      // Second only reads from the memory read from by First. If it
+      // also writes to any other memory, be conservative.
+      if (Second->mayWriteToMemory())
+        return Unknown;
+
+      // If it's loading the same size from the same address, we can
+      // give a more precise result.
+      if (const LoadInst *SecondL = dyn_cast<LoadInst>(Second)) {
+        unsigned LSize = getTypeStoreSize(L->getType());
+        unsigned SecondLSize = getTypeStoreSize(SecondL->getType());
+        if (alias(L->getPointerOperand(), LSize,
+                  SecondL->getPointerOperand(), SecondLSize) ==
+            MustAlias) {
+          // If the loads are the same size, it's ReadThenRead.
+          if (LSize == SecondLSize)
+            return ReadThenRead;
+
+          // If the second load is smaller, it's only ReadThenReadSome.
+          if (LSize > SecondLSize)
+            return ReadThenReadSome;
+        }
+      }
+
+      // Otherwise it's just two loads.
+      return Independent;
+
+    case Mod:
+      // Second only writes to the memory read from by First. If it
+      // also reads from any other memory, be conservative.
+      if (Second->mayReadFromMemory())
+        return Unknown;
+
+      // If it's storing the same size to the same address, we can
+      // give a more precise result.
+      if (const StoreInst *SecondS = dyn_cast<StoreInst>(Second)) {
+        unsigned LSize = getTypeStoreSize(L->getType());
+        unsigned SecondSSize = getTypeStoreSize(SecondS->getType());
+        if (alias(L->getPointerOperand(), LSize,
+                  SecondS->getPointerOperand(), SecondSSize) ==
+            MustAlias) {
+          // If the load and the store are the same size, it's ReadThenWrite.
+          if (LSize == SecondSSize)
+            return ReadThenWrite;
+        }
+      }
+
+      // Otherwise we don't know if it could be writing to other memory.
+      return Unknown;
+
+    case ModRef:
+      // Second reads and writes to the memory read from by First.
+      // We don't have a way to express that.
+      return Unknown;
+    }
+
+  } else if (const StoreInst *S = dyn_cast<StoreInst>(First)) {
+    // Be over-conservative with volatile for now.
+    if (S->isVolatile())
+      return Unknown;
+
+    // Forward this query to getModRefInfo.
+    switch (getModRefInfo(Second,
+                          S->getPointerOperand(),
+                          getTypeStoreSize(S->getValueOperand()->getType()))) {
+    case NoModRef:
+      // Second doesn't reference First's memory, so they're independent.
+      return Independent;
+
+    case Ref:
+      // Second only reads from the memory written to by First. If it
+      // also writes to any other memory, be conservative.
+      if (Second->mayWriteToMemory())
+        return Unknown;
+
+      // If it's loading the same size from the same address, we can
+      // give a more precise result.
+      if (const LoadInst *SecondL = dyn_cast<LoadInst>(Second)) {
+        unsigned SSize = getTypeStoreSize(S->getValueOperand()->getType());
+        unsigned SecondLSize = getTypeStoreSize(SecondL->getType());
+        if (alias(S->getPointerOperand(), SSize,
+                  SecondL->getPointerOperand(), SecondLSize) ==
+            MustAlias) {
+          // If the store and the load are the same size, it's WriteThenRead.
+          if (SSize == SecondLSize)
+            return WriteThenRead;
+
+          // If the load is smaller, it's only WriteThenReadSome.
+          if (SSize > SecondLSize)
+            return WriteThenReadSome;
+        }
+      }
+
+      // Otherwise we don't know if it could be reading from other memory.
+      return Unknown;
+
+    case Mod:
+      // Second only writes to the memory written to by First. If it
+      // also reads from any other memory, be conservative.
+      if (Second->mayReadFromMemory())
+        return Unknown;
+
+      // If it's storing the same size to the same address, we can
+      // give a more precise result.
+      if (const StoreInst *SecondS = dyn_cast<StoreInst>(Second)) {
+        unsigned SSize = getTypeStoreSize(S->getValueOperand()->getType());
+        unsigned SecondSSize = getTypeStoreSize(SecondS->getType());
+        if (alias(S->getPointerOperand(), SSize,
+                  SecondS->getPointerOperand(), SecondSSize) ==
+            MustAlias) {
+          // If the stores are the same size, it's WriteThenWrite.
+          if (SSize == SecondSSize)
+            return WriteThenWrite;
+
+          // If the second store is larger, it's only WriteSomeThenWrite.
+          if (SSize < SecondSSize)
+            return WriteSomeThenWrite;
+        }
+      }
+
+      // Otherwise we don't know if it could be writing to other memory.
+      return Unknown;
+
+    case ModRef:
+      // Second reads and writes to the memory written to by First.
+      // We don't have a way to express that.
+      return Unknown;
+    }
+
+  } else if (const VAArgInst *V = dyn_cast<VAArgInst>(First)) {
+    // Forward this query to getModRefInfo.
+    if (getModRefInfo(Second, V->getOperand(0), UnknownSize) == NoModRef)
+      // Second doesn't reference First's memory, so they're independent.
+      return Independent;
+
+  } else if (ImmutableCallSite FirstCS = cast<Value>(First)) {
+    // If both instructions are calls/invokes we can use the two-callsite
+    // form of getModRefInfo.
+    if (ImmutableCallSite SecondCS = cast<Value>(Second))
+      // getModRefInfo's arguments are backwards from intuition.
+      switch (getModRefInfo(SecondCS, FirstCS)) {
+      case NoModRef:
+        // Second doesn't reference First's memory, so they're independent.
+        return Independent;
+
+      case Ref:
+        // If they're both read-only, there's no dependence.
+        if (FirstCS.onlyReadsMemory() && SecondCS.onlyReadsMemory())
+          return Independent;
+
+        // Otherwise it's not obvious what we can do here.
+        return Unknown;
+
+      case Mod:
+        // It's not obvious what we can do here.
+        return Unknown;
+
+      case ModRef:
+        // I know, right?
+        return Unknown;
+      }
+  }
+
+  // For anything else, be conservative.
+  return Unknown;
+}
 
 AliasAnalysis::ModRefBehavior
 AliasAnalysis::getIntrinsicModRefBehavior(unsigned iid) {
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 113c72b..597e34b 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -171,6 +171,13 @@ namespace {
       return ModRef;
     }
 
+    virtual DependenceResult getDependence(const Instruction *First,
+                                           DependenceQueryFlags FirstFlags,
+                                           const Instruction *Second,
+                                           DependenceQueryFlags SecondFlags) {
+      return Unknown;
+    }
+
     virtual void deleteValue(Value *V) {}
     virtual void copyValue(Value *From, Value *To) {}
     
@@ -523,6 +530,11 @@ namespace {
     /// For use when the call site is not known.
     virtual ModRefBehavior getModRefBehavior(const Function *F);
 
+    virtual DependenceResult getDependence(const Instruction *First,
+                                           DependenceQueryFlags FirstFlags,
+                                           const Instruction *Second,
+                                           DependenceQueryFlags SecondFlags);
+
     /// getAdjustedAnalysisPointer - This method is used when a pass implements
     /// an analysis interface through multiple inheritance.  If needed, it
     /// should override this to adjust the this pointer as needed for the
@@ -734,6 +746,14 @@ BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
   return AliasAnalysis::getModRefInfo(CS, P, Size);
 }
 
+AliasAnalysis::DependenceResult
+BasicAliasAnalysis::getDependence(const Instruction *First,
+                                  DependenceQueryFlags FirstFlags,
+                                  const Instruction *Second,
+                                  DependenceQueryFlags SecondFlags) {
+  // We don't have anything special to say yet.
+  return getDependenceViaModRefInfo(First, FirstFlags, Second, SecondFlags);
+}
 
 /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
 /// against another pointer.  We know that V1 is a GEP, but we don't know