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

3 files changed, 296 insertions, 0 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index 0183b19..c1844be 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -278,6 +278,81 @@ public:
                                      ImmutableCallSite CS2);
 
   //===--------------------------------------------------------------------===//
+  /// Dependence queries.
+  ///
+
+  /// DependenceResult - These are the return values for getDependence queries.
+  /// They are defined in terms of "memory", but they are also used to model
+  /// other side effects, such as I/O and volatility.
+  enum DependenceResult {
+    /// ReadThenRead - The instructions are ReadThenReadSome and the second
+    /// instruction reads from exactly the same memory read from by the first.
+    ReadThenRead,
+    
+    /// ReadThenReadSome - The instructions are Independent, both are read-only,
+    /// and the second instruction reads from a subset of the memory read from
+    /// by the first.
+    ReadThenReadSome,
+
+    /// Independent - Neither instruction reads from or writes to memory written
+    /// to by the other.  All enum values lower than this one are special cases
+    /// of Indepenent.
+    Independent,
+
+    /// WriteThenRead - The instructions are WriteThenReadSome and the second
+    /// instruction reads from exactly the same memory written by the first.
+    WriteThenRead,
+
+    /// WriteThenReadSome - The first instruction is write-only, the second
+    /// instruction is read-only, and the second only reads from memory
+    /// written to by the first.
+    WriteThenReadSome,
+
+    /// ReadThenWrite - The instructions are ReadThenWriteSome and the second
+    /// instruction writes to exactly the same memory read from by the first.
+    ReadThenWrite,
+
+    /// WriteThenWrite - The instructions are WriteThenWriteSome, and the
+    /// second instruction writes to exactly the same memory written to by
+    /// the first.
+    WriteThenWrite,
+
+    /// WriteSomeThenWrite - Both instructions are write-only, and the second
+    /// instruction writes to a superset of the memory written to by the first.
+    WriteSomeThenWrite,
+
+    /// Unknown - The relationship between the instructions cannot be
+    /// determined or does not fit into any of the cases defined here.
+    Unknown
+  };
+
+  /// DependenceQueryFlags - Flags for refining dependence queries.
+  enum DependenceQueryFlags {
+    Default      = 0,
+    IgnoreLoads  = 1,
+    IgnoreStores = 2
+  };
+
+  /// getDependence - Determine the dependence relationship between the
+  /// instructions. This does not include "register" dependencies; it just
+  /// considers memory references and other side effects.
+  /// WARNING: This is an experimental interface.
+  DependenceResult getDependence(const Instruction *First,
+                                 const Instruction *Second) {
+    return getDependence(First, Default, Second, Default);
+  }
+
+  /// getDependence - Determine the dependence relationship between the
+  /// instructions. This does not include "register" dependencies; it just
+  /// considers memory references and other side effects.  This overload
+  /// accepts additional flags to refine the query.
+  /// WARNING: This is an experimental interface.
+  virtual DependenceResult getDependence(const Instruction *First,
+                                         DependenceQueryFlags FirstFlags,
+                                         const Instruction *Second,
+                                         DependenceQueryFlags SecondFlags);
+
+  //===--------------------------------------------------------------------===//
   /// Higher level methods for querying mod/ref information.
   ///
 
@@ -322,6 +397,15 @@ public:
     copyValue(Old, New);
     deleteValue(Old);
   }
+
+protected:
+  /// getDependenceViaModRefInfo - Helper function for implementing getDependence
+  /// in implementations which already have getModRefInfo implementations.
+  DependenceResult getDependenceViaModRefInfo(const Instruction *First,
+                                              DependenceQueryFlags FirstFlags,
+                                              const Instruction *Second,
+                                              DependenceQueryFlags SecondFlags);
+
 };
 
 /// isNoAliasCall - Return true if this pointer is returned by a noalias
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