include/llvm/Analysis/MemoryDependenceAnalysis.h

   1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the MemoryDependenceAnalysis analysis pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
  15 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
  16
  17 #include "llvm/Pass.h"
  18 #include "llvm/Support/CallSite.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21
  22 namespace llvm {
  23   class Function;
  24   class FunctionPass;
  25   class Instruction;
  26
  27   /// MemoryDependenceAnalysis - This is an analysis that determines, for a
  28   /// given memory operation, what preceding memory operations it depends on.
  29   /// It builds on alias analysis information, and tries to provide a lazy,
  30   /// caching interface to a common kind of alias information query.
  31   class MemoryDependenceAnalysis : public FunctionPass {
  32   private:
  33     // A map from instructions to their dependency, with a boolean
  34     // flags for whether this mapping is confirmed or not
  35     typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
  36             depMapType;
  37     depMapType depGraphLocal;
  38
  39     // A map from instructions to their non-local dependencies.
  40     typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
  41             nonLocalDepMapType;
  42     nonLocalDepMapType depGraphNonLocal;
  43
  44     // A reverse mapping form dependencies to the dependees.  This is
  45     // used when removing instructions to keep the cache coherent.
  46     typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
  47             reverseDepMapType;
  48     reverseDepMapType reverseDep;
  49
  50     // A reverse mapping form dependencies to the non-local dependees.
  51     reverseDepMapType reverseDepNonLocal;
  52
  53   public:
  54     void ping(Instruction* D);
  55
  56     // Special marker indicating that the query has no dependency
  57     // in the specified block.
  58     static Instruction* const NonLocal;
  59
  60     // Special marker indicating that the query has no dependency at all
  61     static Instruction* const None;
  62
  63     // Special marker indicating a dirty cache entry
  64     static Instruction* const Dirty;
  65
  66     static char ID; // Class identification, replacement for typeinfo
  67     MemoryDependenceAnalysis() : FunctionPass(&ID) {}
  68
  69     /// Pass Implementation stuff.  This doesn't do any analysis.
  70     ///
  71     bool runOnFunction(Function &) {return false; }
  72
  73     /// Clean up memory in between runs
  74     void releaseMemory() {
  75       depGraphLocal.clear();
  76       depGraphNonLocal.clear();
  77       reverseDep.clear();
  78       reverseDepNonLocal.clear();
  79     }
  80
  81     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  82     /// and Alias Analysis.
  83     ///
  84     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  85
  86     /// getDependency - Return the instruction on which a memory operation
  87     /// depends, starting with start.
  88     Instruction* getDependency(Instruction* query, Instruction* start = 0,
  89                                BasicBlock* block = 0);
  90
  91     /// getNonLocalDependency - Fills the passed-in map with the non-local
  92     /// dependencies of the queries.  The map will contain NonLocal for
  93     /// blocks between the query and its dependencies.
  94     void getNonLocalDependency(Instruction* query,
  95                                DenseMap<BasicBlock*, Value*>& resp);
  96
  97     /// removeInstruction - Remove an instruction from the dependence analysis,
  98     /// updating the dependence of instructions that previously depended on it.
  99     void removeInstruction(Instruction* rem);
 100
 101     /// dropInstruction - Remove an instruction from the analysis, making
 102     /// absolutely conservative assumptions when updating the cache.  This is
 103     /// useful, for example when an instruction is changed rather than removed.
 104     void dropInstruction(Instruction* drop);
 105
 106   private:
 107     Instruction* getCallSiteDependency(CallSite C, Instruction* start,
 108                                        BasicBlock* block);
 109     void nonLocalHelper(Instruction* query, BasicBlock* block,
 110                         DenseMap<BasicBlock*, Value*>& resp);
 111   };
 112
 113 } // End llvm namespace
 114
 115 #endif