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