1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
//===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===//
//
// This file implements the TDDataStructures class, which represents the
// Top-down Interprocedural closure of the data structure graph over the
// program. This is useful (but not strictly necessary?) for applications
// like pointer analysis.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Module.h"
#include "llvm/DerivedTypes.h"
#include "Support/StatisticReporter.h"
using std::map;
static RegisterAnalysis<TDDataStructures>
Y("tddatastructure", "Top-down Data Structure Analysis Closure");
AnalysisID TDDataStructures::ID = Y;
// releaseMemory - If the pass pipeline is done with this pass, we can release
// our memory... here...
//
void TDDataStructures::releaseMemory() {
for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
E = DSInfo.end(); I != E; ++I)
delete I->second;
// Empty map so next time memory is released, data structures are not
// re-deleted.
DSInfo.clear();
}
// run - Calculate the top down data structure graphs for each function in the
// program.
//
bool TDDataStructures::run(Module &M) {
// Simply calculate the graphs for each function...
for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
if (!I->isExternal())
calculateGraph(*I);
return false;
}
// ResolveArguments - Resolve the formal and actual arguments for a function
// call by merging the nodes for the actual arguments at the call site Call[]
// (these were copied over from the caller's graph into the callee's graph
// by cloneInto, and the nodes can be found from OldNodeMap) with the
// corresponding nodes for the formal arguments in the callee.
//
static void ResolveArguments(std::vector<DSNodeHandle> &Call,
Function &callee,
std::map<Value*, DSNodeHandle> &CalleeValueMap,
std::map<const DSNode*, DSNode*> OldNodeMap,
bool ignoreNodeMap) {
// Resolve all of the function formal arguments...
Function::aiterator AI = callee.abegin();
for (unsigned i = 2, e = Call.size(); i != e; ++i) {
// Advance the argument iterator to the first pointer argument...
while (!isa<PointerType>(AI->getType())) ++AI;
// TD ...Merge the formal arg scalar with the actual arg node
DSNode* actualArg = Call[i];
DSNode *nodeForActual = ignoreNodeMap? actualArg : OldNodeMap[actualArg];
assert(nodeForActual && "No node found for actual arg in callee graph!");
DSNode *nodeForFormal = CalleeValueMap[AI]->getLink(0);
if (nodeForFormal)
nodeForFormal->mergeWith(nodeForActual);
++AI;
}
}
// MergeGlobalNodes - Merge all existing global nodes with globals
// inlined from the callee or with globals from the GlobalsGraph.
//
static void MergeGlobalNodes(DSGraph& Graph,
map<Value*, DSNodeHandle> &OldValMap) {
map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
I != E; ++I)
if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
if (NHI != OldValMap.end()) // was it inlined from the callee?
I->second->mergeWith(NHI->second);
else // get it from the GlobalsGraph
I->second->mergeWith(Graph.cloneGlobalInto(GV));
}
// Add unused inlined global nodes into the value map
for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
E = OldValMap.end(); I != E; ++I)
if (isa<GlobalValue>(I->first)) {
DSNodeHandle &NH = ValMap[I->first]; // If global is not in ValMap...
if (NH == 0)
NH = I->second; // Add the one just inlined.
}
}
// Helper function to push a caller's graph into the calleeGraph,
// once per call between the caller and the callee.
// Remove each such resolved call from the OrigFunctionCalls vector.
// NOTE: This may produce O(N^2) behavior because it uses linear search
// through the vector OrigFunctionCalls to find all calls to this callee.
//
void TDDataStructures::pushGraphIntoCallee(DSGraph &callerGraph,
DSGraph &calleeGraph,
std::map<Value*, DSNodeHandle> &OldValMap,
std::map<const DSNode*, DSNode*> &OldNodeMap) {
Function& caller = callerGraph.getFunction();
// Loop over all function calls in the caller to find those to this callee
std::vector<std::vector<DSNodeHandle> >& FunctionCalls =
callerGraph.getOrigFunctionCalls();
for (unsigned i = 0, ei = FunctionCalls.size(); i != ei; ++i) {
std::vector<DSNodeHandle>& Call = FunctionCalls[i];
assert(Call.size() >= 2 && "No function pointer in Call?");
DSNodeHandle& callee = Call[1];
std::vector<GlobalValue*> funcPtrs(callee->getGlobals());
// Loop over the function pointers in the call, looking for the callee
for (unsigned f = 0; f != funcPtrs.size(); ++f) {
// Must be a function type, so this cast MUST succeed.
Function &callee = cast<Function>(*funcPtrs[f]);
if (&callee != &calleeGraph.getFunction())
continue;
// Found a call to the callee. Inline its graph
// copy caller pointer because inlining may modify the callers vector
// Merge actual arguments from the caller with formals in the callee.
// Don't use the old->new node map if this is a self-recursive call.
ResolveArguments(Call, callee, calleeGraph.getValueMap(), OldNodeMap,
/*ignoreNodeMap*/ &caller == &callee);
// If its not a self-recursive call, merge global nodes in the inlined
// graph with the corresponding global nodes in the current graph
if (&caller != &callee)
MergeGlobalNodes(calleeGraph, OldValMap);
// Merge returned node in the caller with the "return" node in callee
if (Call[0])
calleeGraph.getRetNode()->mergeWith(OldNodeMap[Call[0]]);
// Erase the entry in the globals vector
funcPtrs.erase(funcPtrs.begin()+f--);
} // for each function pointer in the call node
} // for each original call node
}
DSGraph &TDDataStructures::calculateGraph(Function &F) {
// Make sure this graph has not already been calculated, or that we don't get
// into an infinite loop with mutually recursive functions.
//
DSGraph *&Graph = DSInfo[&F];
if (Graph) return *Graph;
// Copy the local version into DSInfo...
DSGraph& BUGraph = getAnalysis<BUDataStructures>().getDSGraph(F);
Graph = new DSGraph(BUGraph);
// Find the callers of this function recorded during the BU pass
std::set<Function*> &PendingCallers = BUGraph.getPendingCallers();
DEBUG(std::cerr << " [TD] Inlining callers for: " << F.getName() << "\n");
for (std::set<Function*>::iterator I=PendingCallers.begin(),
E=PendingCallers.end(); I != E; ++I) {
Function& caller = **I;
assert(! caller.isExternal() && "Externals unexpected in callers list");
DEBUG(std::cerr << "\t [TD] Inlining " << caller.getName()
<< " into callee: " << F.getName() << "\n");
// These two maps keep track of where scalars in the old graph _used_
// to point to, and of new nodes matching nodes of the old graph.
// These remain empty if no other graph is inlined (i.e., self-recursive).
std::map<const DSNode*, DSNode*> OldNodeMap;
std::map<Value*, DSNodeHandle> OldValMap;
if (&caller == &F) {
// Self-recursive call: this can happen after a cycle of calls is inlined.
pushGraphIntoCallee(*Graph, *Graph, OldValMap, OldNodeMap);
}
else {
// Recursively compute the graph for the caller. That should
// be fully resolved except if there is mutual recursion...
//
DSGraph &callerGraph = calculateGraph(caller); // Graph to inline
DEBUG(std::cerr << "\t\t[TD] Got graph for " << caller.getName()
<< " in: " << F.getName() << "\n");
// Clone the caller's graph into the current graph, keeping
// track of where scalars in the old graph _used_ to point...
// Do this here because it only needs to happens once for each caller!
// Strip scalars but not allocas since they are visible in callee.
//
DSNode *RetVal = Graph->cloneInto(callerGraph, OldValMap, OldNodeMap,
/*StripScalars*/ true,
/*StripAllocas*/ false,
/*CopyCallers*/ true,
/*CopyOrigCalls*/ false);
pushGraphIntoCallee(callerGraph, *Graph, OldValMap, OldNodeMap);
}
}
// Recompute the Incomplete markers and eliminate unreachable nodes.
Graph->maskIncompleteMarkers();
Graph->markIncompleteNodes(/*markFormals*/ ! F.hasInternalLinkage()
/*&& FIXME: NEED TO CHECK IF ALL CALLERS FOUND!*/);
Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
DEBUG(std::cerr << " [TD] Done inlining callers for: "
<< F.getName() << "\n");
return *Graph;
}
|
