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"
14 class LocalDataStructures; // A collection of local graphs for a program
15 class BUDataStructures; // A collection of bu graphs for a program
16 class TDDataStructures; // A collection of td graphs for a program
19 // FIXME: move this stuff to a private header
20 namespace DataStructureAnalysis {
21 // isPointerType - Return true if this first class type is big enough to hold
24 bool isPointerType(const Type *Ty);
28 // LocalDataStructures - The analysis that computes the local data structure
29 // graphs for all of the functions in the program.
31 // FIXME: This should be a Function pass that can be USED by a Pass, and would
32 // be automatically preserved. Until we can do that, this is a Pass.
34 class LocalDataStructures : public Pass {
35 // DSInfo, one graph for each function
36 std::map<const Function*, DSGraph*> DSInfo;
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 // print - Print out the analysis results...
50 void print(std::ostream &O, const Module *M) const;
52 // If the pass pipeline is done with this pass, we can release our memory...
53 virtual void releaseMemory();
55 // getAnalysisUsage - This obviously provides a data structure graph.
56 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
61 // BUDataStructures - The analysis that computes the interprocedurally closed
62 // data structure graphs for all of the functions in the program. This pass
63 // only performs a "Bottom Up" propogation (hence the name).
65 class BUDataStructures : public Pass {
66 // DSInfo, one graph for each function
67 std::map<const Function*, DSGraph*> DSInfo;
69 ~BUDataStructures() { releaseMemory(); }
71 virtual bool run(Module &M);
73 // getDSGraph - Return the data structure graph for the specified function.
74 DSGraph &getDSGraph(const Function &F) const {
75 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
76 assert(I != DSInfo.end() && "Function not in module!");
80 // print - Print out the analysis results...
81 void print(std::ostream &O, const Module *M) const;
83 // If the pass pipeline is done with this pass, we can release our memory...
84 virtual void releaseMemory();
86 // getAnalysisUsage - This obviously provides a data structure graph.
87 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
89 AU.addRequired<LocalDataStructures>();
92 DSGraph &calculateGraph(Function &F);
97 // TDDataStructures - Analysis that computes new data structure graphs
98 // for each function using the closed graphs for the callers computed
99 // by the bottom-up pass.
101 class TDDataStructures : public Pass {
102 // DSInfo, one graph for each function
103 std::map<const Function*, DSGraph*> DSInfo;
105 ~TDDataStructures() { releaseMemory(); }
107 virtual bool run(Module &M);
109 // getDSGraph - Return the data structure graph for the specified function.
110 DSGraph &getDSGraph(const Function &F) const {
111 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
112 assert(I != DSInfo.end() && "Function not in module!");
116 // print - Print out the analysis results...
117 void print(std::ostream &O, const Module *M) const;
119 // If the pass pipeline is done with this pass, we can release our memory...
120 virtual void releaseMemory();
122 // getAnalysisUsage - This obviously provides a data structure graph.
123 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
124 AU.setPreservesAll();
125 AU.addRequired<BUDataStructures>();
128 DSGraph &calculateGraph(Function &F);
129 void pushGraphIntoCallee(DSGraph &callerGraph, DSGraph &calleeGraph,
130 std::map<Value*, DSNodeHandle> &OldValMap,
131 std::map<const DSNode*, DSNode*> &OldNodeMap);
136 // GlobalDSGraph - A common graph for all the globals and their outgoing links
137 // to externally visible nodes. This includes GlobalValues, New nodes,
138 // Cast nodes, and Calls. This graph can only be used by one of the
139 // individual function graphs, and it goes away when they all go away.
141 class GlobalDSGraph : public DSGraph {
142 hash_set<const DSGraph*> Referrers;
143 void addReference(const DSGraph* referrer);
144 void removeReference(const DSGraph* referrer);
145 friend class DSGraph; // give access to Referrers
147 GlobalDSGraph(const GlobalDSGraph &GlobalDSG); // Do not implement
149 // Helper function for cloneGlobals and cloneCalls
150 DSNode* cloneNodeInto(DSNode *OldNode,
151 std::map<const DSNode*, DSNode*> &NodeCache,
152 bool GlobalsAreFinal = false);
155 GlobalDSGraph(); // Create an empty DSGraph
156 virtual ~GlobalDSGraph();
158 void cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
159 void cloneCalls (DSGraph& Graph);