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

1 files changed, 69 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