A first stab at memory dependence analysis. This is an interface on top of

alias analysis, adding caching and lazy computation of queries.  This will
be used in planned improvements to memory access optimizations.


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

2 files changed, 240 insertions, 0 deletions

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
new file mode 100644
index 0000000..99d9130
--- /dev/null
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -0,0 +1,69 @@
+//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the Owen Anderson and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an analysis that determines, for a given memory operation,
+// what preceding memory operations it depends on.  It builds on alias analysis
+// information, and tries to provide a lazy, caching interface to a common kind
+// of alias information query.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+
+#include "llvm/Pass.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Compiler.h"
+#include <map>
+
+namespace llvm {
+
+class Function;
+class FunctionPass;
+class Instruction;
+
+class VISIBILITY_HIDDEN MemoryDependenceAnalysis : public FunctionPass {
+  private:
+    
+    DenseMap<Instruction*, std::pair<Instruction*, bool> > depGraphLocal;
+    std::multimap<Instruction*, Instruction*> reverseDep;
+  
+  public:
+    
+    static Instruction* NonLocal;
+    static Instruction* None;
+    
+    static char ID; // Class identification, replacement for typeinfo
+    MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
+
+    /// Pass Implementation stuff.  This doesn't do any analysis.
+    ///
+    bool runOnFunction(Function &) { 
+      depGraphLocal.clear();
+      reverseDep.clear();
+      return false;
+    }
+
+    /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
+    /// and Alias Analysis.
+    ///
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+    
+    /// getDependency - Return the instruction on which a memory operation
+    /// depends.
+    Instruction* getDependency(Instruction* query, bool local = true);
+    
+    /// removeInstruction - Remove an instruction from the dependence analysis,
+    /// updating the dependence of instructions that previously depended on it.
+    void removeInstruction(Instruction* rem);
+  };
+
+} // End llvm namespace
+
+#endif
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
new file mode 100644
index 0000000..ed1e4e1
--- /dev/null
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -0,0 +1,171 @@
+//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the Owen Anderson and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements an analysis that determines, for a given memory
+// operation, what preceding memory operations it depends on.  It builds on 
+// alias analysis information, and tries to provide a lazy, caching interface to 
+// a common kind of alias information query.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Instructions.h"
+#include "llvm/Function.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Target/TargetData.h"
+
+using namespace llvm;
+
+char MemoryDependenceAnalysis::ID = 0;
+  
+Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
+Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
+  
+// Register this pass...
+RegisterPass<MemoryDependenceAnalysis> X("memdep",
+                                           "Memory Dependence Analysis");
+
+/// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
+///
+void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequiredTransitive<AliasAnalysis>();
+  AU.addRequiredTransitive<TargetData>();
+}
+
+/// getDependency - Return the instruction on which a memory operation
+/// depends.  NOTE: A return value of NULL indicates that no dependency
+/// was found in the parent block.
+Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
+                                                     bool local) {
+  if (!local)
+    assert(0 && "Non-local memory dependence is not yet supported.");
+  
+  // Start looking for dependencies with the queried inst
+  BasicBlock::iterator QI = query;
+  
+  // Check for a cached result
+  std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
+  // If we have a _confirmed_ cached entry, return it
+  if (cachedResult.second)
+    return cachedResult.first;
+  else if (cachedResult.first != NonLocal)
+  // If we have an unconfirmed cached entry, we can start our search from there
+    QI = cachedResult.first;
+  
+  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
+  
+  BasicBlock::iterator blockBegin = query->getParent()->begin();
+  
+  // Get the pointer value for which dependence will be determined
+  Value* dependee = 0;
+  if (StoreInst* S = dyn_cast<StoreInst>(QI))
+    dependee = S->getPointerOperand();
+  else if (LoadInst* L = dyn_cast<LoadInst>(QI))
+    dependee = L->getPointerOperand();
+  else if (FreeInst* F = dyn_cast<FreeInst>(QI))
+    dependee = F->getPointerOperand();
+  else if (isa<AllocationInst>(query)) {
+    // Allocations don't depend on anything
+    depGraphLocal.insert(std::make_pair(query, std::make_pair(None,
+                                                              true)));
+    reverseDep.insert(std::make_pair(None, query));
+    return None;
+  } else {
+    // Non-memory operations depend on their immediate predecessor
+    --QI;
+    depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+    reverseDep.insert(std::make_pair(QI, query));
+    return QI;
+  }
+  
+  // Start with the predecessor of the queried inst
+  --QI;
+  
+  TargetData& TD = getAnalysis<TargetData>();
+  
+  while (QI != blockBegin) {
+    // If this inst is a memory op, get the pointer it accessed
+    Value* pointer = 0;
+    if (StoreInst* S = dyn_cast<StoreInst>(QI))
+      pointer = S->getPointerOperand();
+    else if (LoadInst* L = dyn_cast<LoadInst>(QI))
+      pointer = L->getPointerOperand();
+    else if (isa<AllocationInst>(QI))
+      pointer = QI;
+    else if (FreeInst* F = dyn_cast<FreeInst>(QI))
+      pointer = F->getPointerOperand();
+    else if (CallInst* C = dyn_cast<CallInst>(QI)) {
+      // Call insts need special handling.  Check is they can modify our pointer
+      if (AA.getModRefInfo(C, dependee, TD.getTypeSize(dependee->getType())) !=
+          AliasAnalysis::NoModRef) {
+        depGraphLocal.insert(std::make_pair(query, std::make_pair(C, true)));
+        reverseDep.insert(std::make_pair(C, query));
+        return C;
+      } else {
+        continue;
+      }
+    }
+    
+    // If we found a pointer, check if it could be the same as our pointer
+    if (pointer) {
+      AliasAnalysis::AliasResult R = AA.alias(
+                                 pointer, TD.getTypeSize(pointer->getType()),
+                                 dependee, TD.getTypeSize(dependee->getType()));
+      
+      if (R != AliasAnalysis::NoAlias) {
+        depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+        reverseDep.insert(std::make_pair(QI, query));
+        return QI;
+      }
+    }
+    
+    QI--;
+  }
+  
+  // If we found nothing, return the non-local flag
+  depGraphLocal.insert(std::make_pair(query,
+                                      std::make_pair(NonLocal, true)));
+  reverseDep.insert(std::make_pair(NonLocal, query));
+  
+  return NonLocal;
+}
+
+/// removeInstruction - Remove an instruction from the dependence analysis,
+/// updating the dependence of instructions that previously depended on it.
+void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
+  // Figure out the new dep for things that currently depend on rem
+  Instruction* newDep = NonLocal;
+  if (depGraphLocal[rem].first != NonLocal) {
+    // If we have dep info for rem, set them to it
+    BasicBlock::iterator RI = depGraphLocal[rem].first;
+    RI++;
+    newDep = RI;
+  } else if (depGraphLocal[rem].first == NonLocal &&
+             depGraphLocal[rem].second ) {
+    // If we have a confirmed non-local flag, use it
+    newDep = NonLocal;
+  } else {
+    // Otherwise, use the immediate successor of rem
+    // NOTE: This is because, when getDependence is called, it will first check
+    // the immediate predecessor of what is in the cache.
+    BasicBlock::iterator RI = rem;
+    RI++;
+    newDep = RI;
+  }
+
+  std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
+  while (I->first == rem) {
+    // Insert the new dependencies
+    // Mark it as unconfirmed as long as it is not the non-local flag
+    depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
+    reverseDep.erase(I);
+    I = reverseDep.find(rem);
+  }
+}