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/Analysis/DSGraph.h"
11 #include "llvm/Pass.h"
13 #include "llvm/GlobalValue.h"
14 #include "Support/HashExtras.h"
15 #include "Support/hash_set"
22 class GlobalDSGraph; // A common graph for globals in a program
24 class LocalDataStructures; // A collection of local graphs for a program
25 class BUDataStructures; // A collection of bu graphs for a program
26 class TDDataStructures; // A collection of td graphs for a program
29 // FIXME: move this stuff to a private header
30 namespace DataStructureAnalysis {
31 // isPointerType - Return true if this first class type is big enough to hold
34 bool isPointerType(const Type *Ty);
38 // LocalDataStructures - The analysis that computes the local data structure
39 // graphs for all of the functions in the program.
41 // FIXME: This should be a Function pass that can be USED by a Pass, and would
42 // be automatically preserved. Until we can do that, this is a Pass.
44 class LocalDataStructures : public Pass {
45 // DSInfo, one graph for each function
46 std::map<const Function*, DSGraph*> DSInfo;
48 ~LocalDataStructures() { releaseMemory(); }
50 virtual bool run(Module &M);
52 // getDSGraph - Return the data structure graph for the specified function.
53 DSGraph &getDSGraph(const Function &F) const {
54 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
55 assert(I != DSInfo.end() && "Function not in module!");
59 // print - Print out the analysis results...
60 void print(std::ostream &O, const Module *M) const;
62 // If the pass pipeline is done with this pass, we can release our memory...
63 virtual void releaseMemory();
65 // getAnalysisUsage - This obviously provides a data structure graph.
66 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
72 // BUDataStructures - The analysis that computes the interprocedurally closed
73 // data structure graphs for all of the functions in the program. This pass
74 // only performs a "Bottom Up" propogation (hence the name).
76 class BUDataStructures : public Pass {
77 // DSInfo, one graph for each function
78 std::map<const Function*, DSGraph*> DSInfo;
80 ~BUDataStructures() { releaseMemory(); }
82 virtual bool run(Module &M);
84 // getDSGraph - Return the data structure graph for the specified function.
85 DSGraph &getDSGraph(const Function &F) const {
86 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
87 assert(I != DSInfo.end() && "Function not in module!");
91 // print - Print out the analysis results...
92 void print(std::ostream &O, const Module *M) const;
94 // If the pass pipeline is done with this pass, we can release our memory...
95 virtual void releaseMemory();
97 // getAnalysisUsage - This obviously provides a data structure graph.
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
100 AU.addRequired<LocalDataStructures>();
103 DSGraph &calculateGraph(Function &F);
107 // TDDataStructures - Analysis that computes new data structure graphs
108 // for each function using the closed graphs for the callers computed
109 // by the bottom-up pass.
111 class TDDataStructures : public Pass {
112 // DSInfo, one graph for each function
113 std::map<const Function*, DSGraph*> DSInfo;
115 ~TDDataStructures() { releaseMemory(); }
117 virtual bool run(Module &M);
119 // getDSGraph - Return the data structure graph for the specified function.
120 DSGraph &getDSGraph(const Function &F) const {
121 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
122 assert(I != DSInfo.end() && "Function not in module!");
126 // print - Print out the analysis results...
127 void print(std::ostream &O, const Module *M) const;
129 // If the pass pipeline is done with this pass, we can release our memory...
130 virtual void releaseMemory();
132 // getAnalysisUsage - This obviously provides a data structure graph.
133 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
134 AU.setPreservesAll();
135 AU.addRequired<BUDataStructures>();
138 DSGraph &calculateGraph(Function &F);
139 void pushGraphIntoCallee(DSGraph &callerGraph, DSGraph &calleeGraph,
140 std::map<Value*, DSNodeHandle> &OldValMap,
141 std::map<const DSNode*, DSNode*> &OldNodeMap);
146 // GlobalDSGraph - A common graph for all the globals and their outgoing links
147 // to externally visible nodes. This includes GlobalValues, New nodes,
148 // Cast nodes, and Calls. This graph can only be used by one of the
149 // individual function graphs, and it goes away when they all go away.
151 class GlobalDSGraph : public DSGraph {
152 hash_set<const DSGraph*> Referrers;
153 void addReference(const DSGraph* referrer);
154 void removeReference(const DSGraph* referrer);
155 friend class DSGraph; // give access to Referrers
157 GlobalDSGraph(const GlobalDSGraph &GlobalDSG); // Do not implement
159 // Helper function for cloneGlobals and cloneCalls
160 DSNode* cloneNodeInto(DSNode *OldNode,
161 std::map<const DSNode*, DSNode*> &NodeCache,
162 bool GlobalsAreFinal = false);
165 GlobalDSGraph(); // Create an empty DSGraph
166 virtual ~GlobalDSGraph();
168 void cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
169 void cloneCalls (DSGraph& Graph);