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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
//===- BottomUpClosure.cpp - Compute the bottom up interprocedure closure -===//
//
// This file implements the BUDataStructures class, which represents the
// Bottom-Up Interprocedural closure of the data structure graph over the
// program. This is useful for applications like pool allocation, but **not**
// applications like pointer analysis.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Module.h"
#include "llvm/DerivedTypes.h"
#include "Support/Statistic.h"
#include <set>
using std::map;
#if 0
static RegisterAnalysis<BUDataStructures>
X("budatastructure", "Bottom-up Data Structure Analysis Closure");
// releaseMemory - If the pass pipeline is done with this pass, we can release
// our memory... here...
//
void BUDataStructures::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 bottom up data structure graphs for each function in the
// program.
//
bool BUDataStructures::run(Module &M) {
// Simply calculate the graphs for each function...
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal())
calculateGraph(*I);
return false;
}
// ResolveArguments - Resolve the formal and actual arguments for a function
// call.
//
static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
map<Value*, DSNodeHandle> &ValueMap) {
// Resolve all of the function arguments...
Function::aiterator AI = F.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;
// Add the link from the argument scalar to the provided value
DSNode *NN = ValueMap[AI];
NN->addEdgeTo(Call[i]);
++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.
}
}
DSGraph &BUDataStructures::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...
Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
// Populate the GlobalsGraph with globals from this one.
Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
// Save a copy of the original call nodes for the top-down pass
Graph->saveOrigFunctionCalls();
// Start resolving calls...
std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
DEBUG(std::cerr << " [BU] Inlining: " << F.getName() << "\n");
// Add F to the PendingCallers list of each direct callee for use in the
// top-down pass so we don't have to compute this again. We don't want
// to do it for indirect callees inlined later, so remember which calls
// are in the original FCs set.
std::set<const DSNode*> directCallees;
for (unsigned i = 0; i < FCs.size(); ++i)
directCallees.insert(FCs[i][1]); // ptr to function node
bool Inlined;
do {
Inlined = false;
for (unsigned i = 0; i != FCs.size(); ++i) {
// Copy the call, because inlining graphs may invalidate the FCs vector.
std::vector<DSNodeHandle> Call = FCs[i];
// If the function list is not incomplete...
if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
// Start inlining all of the functions we can... some may not be
// inlinable if they are external...
//
std::vector<GlobalValue*> Callees(Call[1]->getGlobals());
// Loop over the functions, inlining whatever we can...
for (unsigned c = 0; c != Callees.size(); ++c) {
// Must be a function type, so this cast MUST succeed.
Function &FI = cast<Function>(*Callees[c]);
if (&FI == &F) {
// Self recursion... simply link up the formal arguments with the
// actual arguments...
DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
if (Call[0]) // Handle the return value if present...
Graph->RetNode->mergeWith(Call[0]);
// Resolve the arguments in the call to the actual values...
ResolveArguments(Call, F, Graph->getValueMap());
// Erase the entry in the callees vector
Callees.erase(Callees.begin()+c--);
} else if (!FI.isExternal()) {
DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
<< FI.getName() << "\n");
// Get the data structure graph for the called function, closing it
// if possible (which is only impossible in the case of mutual
// recursion...
//
DSGraph &GI = calculateGraph(FI); // Graph to inline
DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
<< " in: " << F.getName() << "\n");
// Clone the callee's graph into the current graph, keeping
// track of where scalars in the old graph _used_ to point,
// and of the new nodes matching nodes of the old graph.
std::map<Value*, DSNodeHandle> OldValMap;
std::map<const DSNode*, DSNode*> OldNodeMap;
// The clone call may invalidate any of the vectors in the data
// structure graph. Strip locals and don't copy the list of callers
DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
/*StripScalars*/ true,
/*StripAllocas*/ true,
/*CopyCallers*/ false,
/*CopyOrigCalls*/ false);
ResolveArguments(Call, FI, OldValMap);
if (Call[0]) // Handle the return value if present
RetVal->mergeWith(Call[0]);
// Merge global value nodes in the inlined graph with the global
// value nodes in the current graph if there are duplicates.
//
MergeGlobalNodes(*Graph, OldValMap);
// If this was an original call, add F to the PendingCallers list
if (directCallees.find(Call[1]) != directCallees.end())
GI.addCaller(F);
// Erase the entry in the Callees vector
Callees.erase(Callees.begin()+c--);
} else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
FI.getName() == "fprintf" || FI.getName() == "open" ||
FI.getName() == "sprintf") {
// Erase the entry in the globals vector
Callees.erase(Callees.begin()+c--);
}
}
if (Callees.empty()) { // Inlined all of the function calls?
// Erase the call if it is resolvable...
FCs.erase(FCs.begin()+i--); // Don't skip a the next call...
Inlined = true;
} else if (Callees.size() != Call[1]->getGlobals().size()) {
// Was able to inline SOME, but not all of the functions. Construct a
// new global node here.
//
assert(0 && "Unimpl!");
Inlined = true;
}
}
}
// Recompute the Incomplete markers. If there are any function calls left
// now that are complete, we must loop!
if (Inlined) {
Graph->maskIncompleteMarkers();
Graph->markIncompleteNodes();
Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ true);
}
} while (Inlined && !FCs.empty());
// Copy any unresolved call nodes into the Globals graph and
// filter out unresolved call nodes inlined from the callee.
if (!FCs.empty())
Graph->GlobalsGraph->cloneCalls(*Graph);
Graph->maskIncompleteMarkers();
Graph->markIncompleteNodes();
Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
DEBUG(std::cerr << " [BU] Done inlining: " << F.getName() << " ["
<< Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
<< "]\n");
return *Graph;
}
#endif
|
