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     // Special marker indicating that the query has no dependency
  55     // in the specified block.
  56     static Instruction* const NonLocal;
  57
  58     // Special marker indicating that the query has no dependency at all
  59     static Instruction* const None;
  60
  61     // Special marker indicating a dirty cache entry
  62     static Instruction* const Dirty;
  63
  64     static char ID; // Class identification, replacement for typeinfo
  65     MemoryDependenceAnalysis() : FunctionPass(&ID) {}
  66
  67     /// Pass Implementation stuff.  This doesn't do any analysis.
  68     ///
  69     bool runOnFunction(Function &) {return false; }
  70
  71     /// Clean up memory in between runs
  72     void releaseMemory() {
  73       depGraphLocal.clear();
  74       depGraphNonLocal.clear();
  75       reverseDep.clear();
  76       reverseDepNonLocal.clear();
  77     }
  78
  79     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  80     /// and Alias Analysis.
  81     ///
  82     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  83
  84     /// getDependency - Return the instruction on which a memory operation
  85     /// depends, starting with start.
  86     Instruction* getDependency(Instruction* query, Instruction* start = 0,
  87                                BasicBlock* block = 0);
  88
  89     /// getNonLocalDependency - Fills the passed-in map with the non-local
  90     /// dependencies of the queries.  The map will contain NonLocal for
  91     /// blocks between the query and its dependencies.
  92     void getNonLocalDependency(Instruction* query,
  93                                DenseMap<BasicBlock*, Value*>& resp);
  94
  95     /// removeInstruction - Remove an instruction from the dependence analysis,
  96     /// updating the dependence of instructions that previously depended on it.
  97     void removeInstruction(Instruction* rem);
  98
  99     /// dropInstruction - Remove an instruction from the analysis, making
 100     /// absolutely conservative assumptions when updating the cache.  This is
 101     /// useful, for example when an instruction is changed rather than removed.
 102     void dropInstruction(Instruction* drop);
 103
 104   private:
 105     /// verifyRemoved - Verify that the specified instruction does not occur
 106     /// in our internal data structures.
 107     void verifyRemoved(Instruction *Inst) const;
 108
 109     Instruction* getCallSiteDependency(CallSite C, Instruction* start,
 110                                        BasicBlock* block);
 111     void nonLocalHelper(Instruction* query, BasicBlock* block,
 112                         DenseMap<BasicBlock*, Value*>& resp);
 113   };
 114
 115 } // End llvm namespace
 116
 117 #endif