1 //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===//
3 // Implement the LLVM data structure analysis library.
5 //===----------------------------------------------------------------------===//
7 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
8 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
10 #include "llvm/Pass.h"
18 // FIXME: move this stuff to a private header
19 namespace DataStructureAnalysis {
20 // isPointerType - Return true if this first class type is big enough to hold
23 bool isPointerType(const Type *Ty);
27 // LocalDataStructures - The analysis that computes the local data structure
28 // graphs for all of the functions in the program.
30 // FIXME: This should be a Function pass that can be USED by a Pass, and would
31 // be automatically preserved. Until we can do that, this is a Pass.
33 class LocalDataStructures : public Pass {
34 // DSInfo, one graph for each function
35 std::map<const Function*, DSGraph*> DSInfo;
36 DSGraph *GlobalsGraph;
38 ~LocalDataStructures() { releaseMemory(); }
40 virtual bool run(Module &M);
42 // getDSGraph - Return the data structure graph for the specified function.
43 DSGraph &getDSGraph(const Function &F) const {
44 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
45 assert(I != DSInfo.end() && "Function not in module!");
49 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
51 // print - Print out the analysis results...
52 void print(std::ostream &O, const Module *M) const;
54 // If the pass pipeline is done with this pass, we can release our memory...
55 virtual void releaseMemory();
57 // getAnalysisUsage - This obviously provides a data structure graph.
58 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
64 // BUDataStructures - The analysis that computes the interprocedurally closed
65 // data structure graphs for all of the functions in the program. This pass
66 // only performs a "Bottom Up" propagation (hence the name).
68 class BUDataStructures : public Pass {
69 // DSInfo, one graph for each function
70 std::map<const Function*, DSGraph*> DSInfo;
71 DSGraph *GlobalsGraph;
73 ~BUDataStructures() { releaseMemory(); }
75 virtual bool run(Module &M);
77 // getDSGraph - Return the data structure graph for the specified function.
78 DSGraph &getDSGraph(const Function &F) const {
79 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
80 assert(I != DSInfo.end() && "Function not in module!");
84 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
86 // print - Print out the analysis results...
87 void print(std::ostream &O, const Module *M) const;
89 // If the pass pipeline is done with this pass, we can release our memory...
90 virtual void releaseMemory();
92 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
94 AU.addRequired<LocalDataStructures>();
97 DSGraph &calculateGraph(Function &F);
101 // TDDataStructures - Analysis that computes new data structure graphs
102 // for each function using the closed graphs for the callers computed
103 // by the bottom-up pass.
105 class TDDataStructures : public Pass {
106 // DSInfo, one graph for each function
107 std::map<const Function*, DSGraph*> DSInfo;
108 std::set<const Function*> GraphDone;
109 DSGraph *GlobalsGraph;
111 ~TDDataStructures() { releaseMemory(); }
113 virtual bool run(Module &M);
115 // getDSGraph - Return the data structure graph for the specified function.
116 DSGraph &getDSGraph(const Function &F) const {
117 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
118 assert(I != DSInfo.end() && "Function not in module!");
122 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
124 // print - Print out the analysis results...
125 void print(std::ostream &O, const Module *M) const;
127 // If the pass pipeline is done with this pass, we can release our memory...
128 virtual void releaseMemory();
130 // getAnalysisUsage - This obviously provides a data structure graph.
131 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
132 AU.setPreservesAll();
133 AU.addRequired<BUDataStructures>();
136 void calculateGraph(Function &F);
137 DSGraph &getOrCreateDSGraph(Function &F);
139 void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);