MemoryDependenceAnalysis.h revision df464195fe049d5ea921e2e37f4f833c2ea4e3ec 
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
27namespace llvm {
28
29class Function;
30class FunctionPass;
31class Instruction;
32
33class MemoryDependenceAnalysis : public FunctionPass {
34  private:
35
36    typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
37    depMapType;
38
39    depMapType depGraphLocal;
40
41    typedef std::multimap<Instruction*, Instruction*> reverseDepMapType;
42    reverseDepMapType reverseDep;
43
44    Instruction* getCallSiteDependency(CallSite C, Instruction* start,
45                                       bool local = true);
46    bool nonLocalHelper(Instruction* query, BasicBlock* block,
47                        DenseMap<BasicBlock*, Value*>& resp,
48                        SmallPtrSet<BasicBlock*, 4>& visited);
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    bool 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
88