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
|
//===- BottomUpClosure.cpp - Compute bottom-up interprocedural 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 alias analysis.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Module.h"
#include "Support/Statistic.h"
using std::map;
static RegisterAnalysis<BUDataStructures>
X("budatastructure", "Bottom-up Data Structure Analysis Closure");
using namespace DS;
// 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;
}
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));
#if 0
// Populate the GlobalsGraph with globals from this one.
Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
#endif
// Start resolving calls...
std::vector<DSCallSite> &FCs = Graph->getAuxFunctionCalls();
// Start with a copy of the original call sites...
FCs = Graph->getFunctionCalls();
DEBUG(std::cerr << " [BU] Inlining: " << F.getName() << "\n");
bool Inlined;
do {
Inlined = false;
for (unsigned i = 0; i != FCs.size(); ++i) {
// Copy the call, because inlining graphs may invalidate the FCs vector.
DSCallSite Call = FCs[i];
// If the function list is complete...
if ((Call.getCallee().getNode()->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.getCallee().getNode()->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");
// Handle self recursion by resolving the arguments and return value
Graph->mergeInGraph(Call, *Graph, DSGraph::StripAllocaBit);
// 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");
// Handle self recursion by resolving the arguments and return value
Graph->mergeInGraph(Call, GI, DSGraph::StripAllocaBit);
// 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") {
// FIXME: These special cases (eg printf) should go away when we can
// define functions that take a variable number of arguments.
// FIXME: at the very least, this should update mod/ref info
// 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.getCallee().getNode()->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*/ true, /*KeepCalls*/ true);
}
} while (Inlined && !FCs.empty());
Graph->maskIncompleteMarkers();
Graph->markIncompleteNodes();
Graph->removeTriviallyDeadNodes(false);
Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
DEBUG(std::cerr << " [BU] Done inlining: " << F.getName() << " ["
<< Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
<< "]\n");
return *Graph;
}
|
