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/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20
  21 namespace llvm {
  22   class Function;
  23   class FunctionPass;
  24   class Instruction;
  25   class CallSite;
  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> > depMapType;
  36     depMapType depGraphLocal;
  37
  38     // A map from instructions to their non-local dependencies.
  39     typedef DenseMap<Instruction*,
  40                      DenseMap<BasicBlock*, Value*> > nonLocalDepMapType;
  41     nonLocalDepMapType depGraphNonLocal;
  42
  43     // A reverse mapping from dependencies to the dependees.  This is
  44     // used when removing instructions to keep the cache coherent.
  45     typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > reverseDepMapType;
  46     reverseDepMapType reverseDep;
  47
  48     // A reverse mapping form dependencies to the non-local dependees.
  49     reverseDepMapType reverseDepNonLocal;
  50
  51   public:
  52     // Special marker indicating that the query has no dependency
  53     // in the specified block.
  54     static Instruction* const NonLocal;
  55
  56     // Special marker indicating that the query has no dependency at all
  57     static Instruction* const None;
  58
  59     // Special marker indicating a dirty cache entry
  60     static Instruction* const Dirty;
  61
  62     static char ID; // Class identification, replacement for typeinfo
  63     MemoryDependenceAnalysis() : FunctionPass(&ID) {}
  64
  65     /// Pass Implementation stuff.  This doesn't do any analysis.
  66     ///
  67     bool runOnFunction(Function &) {return false; }
  68
  69     /// Clean up memory in between runs
  70     void releaseMemory() {
  71       depGraphLocal.clear();
  72       depGraphNonLocal.clear();
  73       reverseDep.clear();
  74       reverseDepNonLocal.clear();
  75     }
  76
  77     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  78     /// and Alias Analysis.
  79     ///
  80     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  81
  82     /// getDependency - Return the instruction on which a memory operation
  83     /// depends, starting with start.
  84     Instruction* getDependency(Instruction* query, Instruction* start = 0,
  85                                BasicBlock* block = 0);
  86
  87     /// getNonLocalDependency - Fills the passed-in map with the non-local
  88     /// dependencies of the queries.  The map will contain NonLocal for
  89     /// blocks between the query and its dependencies.
  90     void getNonLocalDependency(Instruction* query,
  91                                DenseMap<BasicBlock*, Value*>& resp);
  92
  93     /// removeInstruction - Remove an instruction from the dependence analysis,
  94     /// updating the dependence of instructions that previously depended on it.
  95     void removeInstruction(Instruction* rem);
  96
  97     /// dropInstruction - Remove an instruction from the analysis, making
  98     /// absolutely conservative assumptions when updating the cache.  This is
  99     /// useful, for example when an instruction is changed rather than removed.
 100     void dropInstruction(Instruction* drop);
 101
 102   private:
 103     /// verifyRemoved - Verify that the specified instruction does not occur
 104     /// in our internal data structures.
 105     void verifyRemoved(Instruction *Inst) const;
 106
 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