include/llvm/Analysis/MemoryDependenceAnalysis.h

   1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Owen Anderson and is distributed under
   6 // the University of Illinois Open Source 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 #include <map>
  26
  27 namespace llvm {
  28
  29 class Function;
  30 class FunctionPass;
  31 class Instruction;
  32
  33 class MemoryDependenceAnalysis : public FunctionPass {
  34   private:
  35
  36     typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
  37     depMapType;
  38
  39     depMapType depGraphLocal;
  40
  41     typedef DenseMap<Instruction*,
  42                      SmallPtrSet<Instruction*, 4> > reverseDepMapType;
  43     reverseDepMapType reverseDep;
  44
  45     Instruction* getCallSiteDependency(CallSite C, Instruction* start,
  46                                        BasicBlock* block);
  47     void nonLocalHelper(Instruction* query, BasicBlock* block,
  48                         DenseMap<BasicBlock*, Value*>& resp);
  49   public:
  50
  51     static Instruction* NonLocal;
  52     static Instruction* None;
  53
  54     static char ID; // Class identification, replacement for typeinfo
  55     MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
  56
  57     /// Pass Implementation stuff.  This doesn't do any analysis.
  58     ///
  59     bool runOnFunction(Function &) {return false; }
  60
  61     /// Clean up memory in between runs
  62     void releaseMemory() {
  63       depGraphLocal.clear();
  64       reverseDep.clear();
  65     }
  66
  67     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  68     /// and Alias Analysis.
  69     ///
  70     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  71
  72     /// getDependency - Return the instruction on which a memory operation
  73     /// depends, starting with start.
  74     Instruction* getDependency(Instruction* query, Instruction* start = 0,
  75                                BasicBlock* block = 0);
  76
  77     void getNonLocalDependency(Instruction* query,
  78                                DenseMap<BasicBlock*, Value*>& resp);
  79
  80     /// removeInstruction - Remove an instruction from the dependence analysis,
  81     /// updating the dependence of instructions that previously depended on it.
  82     void removeInstruction(Instruction* rem);
  83   };
  84
  85 } // End llvm namespace
  86
  87 #endif