1 //===- BottomUpClosure.cpp - Compute the bottom up interprocedure closure -===//
3 // This file implements the BUDataStructures class, which represents the
4 // Bottom-Up Interprocedural closure of the data structure graph over the
5 // program. This is useful for applications like pool allocation, but **not**
6 // applications like pointer analysis.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/DataStructure.h"
11 #include "llvm/Module.h"
12 #include "llvm/DerivedTypes.h"
13 #include "Support/StatisticReporter.h"
17 static RegisterAnalysis<BUDataStructures>
18 X("budatastructure", "Bottom-up Data Structure Analysis Closure");
19 AnalysisID BUDataStructures::ID = X;
21 // releaseMemory - If the pass pipeline is done with this pass, we can release
22 // our memory... here...
24 void BUDataStructures::releaseMemory() {
25 for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
26 E = DSInfo.end(); I != E; ++I)
29 // Empty map so next time memory is released, data structures are not
34 // run - Calculate the bottom up data structure graphs for each function in the
37 bool BUDataStructures::run(Module &M) {
38 // Simply calculate the graphs for each function...
39 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
46 // ResolveArguments - Resolve the formal and actual arguments for a function
49 static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
50 map<Value*, DSNodeHandle> &ValueMap) {
51 // Resolve all of the function arguments...
52 Function::aiterator AI = F.abegin();
53 for (unsigned i = 2, e = Call.size(); i != e; ++i) {
54 // Advance the argument iterator to the first pointer argument...
55 while (!isa<PointerType>(AI->getType())) ++AI;
57 // Add the link from the argument scalar to the provided value
58 DSNode *NN = ValueMap[AI];
59 NN->addEdgeTo(Call[i]);
64 // MergeGlobalNodes - Merge all existing global nodes with globals
65 // inlined from the callee or with globals from the GlobalsGraph.
67 static void MergeGlobalNodes(DSGraph& Graph,
68 map<Value*, DSNodeHandle> &OldValMap) {
69 map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
70 for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
72 if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
73 map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
74 if (NHI != OldValMap.end()) // was it inlined from the callee?
75 I->second->mergeWith(NHI->second);
76 else // get it from the GlobalsGraph
77 I->second->mergeWith(Graph.cloneGlobalInto(GV));
80 // Add unused inlined global nodes into the value map
81 for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
82 E = OldValMap.end(); I != E; ++I)
83 if (isa<GlobalValue>(I->first)) {
84 DSNodeHandle &NH = ValMap[I->first]; // If global is not in ValMap...
86 NH = I->second; // Add the one just inlined.
91 DSGraph &BUDataStructures::calculateGraph(Function &F) {
92 // Make sure this graph has not already been calculated, or that we don't get
93 // into an infinite loop with mutually recursive functions.
95 DSGraph *&Graph = DSInfo[&F];
96 if (Graph) return *Graph;
98 // Copy the local version into DSInfo...
99 Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
101 // Populate the GlobalsGraph with globals from this one.
102 Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
104 // Save a copy of the original call nodes for the top-down pass
105 Graph->saveOrigFunctionCalls();
107 // Start resolving calls...
108 std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
110 DEBUG(std::cerr << " [BU] Inlining: " << F.getName() << "\n");
112 // Add F to the PendingCallers list of each direct callee for use in the
113 // top-down pass so we don't have to compute this again. We don't want
114 // to do it for indirect callees inlined later, so remember which calls
115 // are in the original FCs set.
116 std::set<const DSNode*> directCallees;
117 for (unsigned i = 0; i < FCs.size(); ++i)
118 directCallees.insert(FCs[i][1]); // ptr to function node
124 for (unsigned i = 0; i != FCs.size(); ++i) {
125 // Copy the call, because inlining graphs may invalidate the FCs vector.
126 std::vector<DSNodeHandle> Call = FCs[i];
128 // If the function list is not incomplete...
129 if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
130 // Start inlining all of the functions we can... some may not be
131 // inlinable if they are external...
133 std::vector<GlobalValue*> Callees(Call[1]->getGlobals());
135 // Loop over the functions, inlining whatever we can...
136 for (unsigned c = 0; c != Callees.size(); ++c) {
137 // Must be a function type, so this cast MUST succeed.
138 Function &FI = cast<Function>(*Callees[c]);
140 // Self recursion... simply link up the formal arguments with the
141 // actual arguments...
143 DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
145 if (Call[0]) // Handle the return value if present...
146 Graph->RetNode->mergeWith(Call[0]);
148 // Resolve the arguments in the call to the actual values...
149 ResolveArguments(Call, F, Graph->getValueMap());
151 // Erase the entry in the callees vector
152 Callees.erase(Callees.begin()+c--);
153 } else if (!FI.isExternal()) {
154 DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
155 << FI.getName() << "\n");
157 // Get the data structure graph for the called function, closing it
158 // if possible (which is only impossible in the case of mutual
161 DSGraph &GI = calculateGraph(FI); // Graph to inline
163 DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
164 << " in: " << F.getName() << "\n");
166 // Clone the callee's graph into the current graph, keeping
167 // track of where scalars in the old graph _used_ to point,
168 // and of the new nodes matching nodes of the old graph.
169 std::map<Value*, DSNodeHandle> OldValMap;
170 std::map<const DSNode*, DSNode*> OldNodeMap;
172 // The clone call may invalidate any of the vectors in the data
173 // structure graph. Strip locals and don't copy the list of callers
174 DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
175 /*StripScalars*/ true,
176 /*StripAllocas*/ true,
177 /*CopyCallers*/ false,
178 /*CopyOrigCalls*/ false);
180 ResolveArguments(Call, FI, OldValMap);
182 if (Call[0]) // Handle the return value if present
183 RetVal->mergeWith(Call[0]);
185 // Merge global value nodes in the inlined graph with the global
186 // value nodes in the current graph if there are duplicates.
188 MergeGlobalNodes(*Graph, OldValMap);
190 // If this was an original call, add F to the PendingCallers list
191 if (directCallees.find(Call[1]) != directCallees.end())
194 // Erase the entry in the Callees vector
195 Callees.erase(Callees.begin()+c--);
197 } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
198 FI.getName() == "fprintf" || FI.getName() == "open" ||
199 FI.getName() == "sprintf") {
201 // Erase the entry in the globals vector
202 Callees.erase(Callees.begin()+c--);
206 if (Callees.empty()) { // Inlined all of the function calls?
207 // Erase the call if it is resolvable...
208 FCs.erase(FCs.begin()+i--); // Don't skip a the next call...
210 } else if (Callees.size() != Call[1]->getGlobals().size()) {
211 // Was able to inline SOME, but not all of the functions. Construct a
212 // new global node here.
214 assert(0 && "Unimpl!");
220 // Recompute the Incomplete markers. If there are any function calls left
221 // now that are complete, we must loop!
223 Graph->maskIncompleteMarkers();
224 Graph->markIncompleteNodes();
225 Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ true);
227 } while (Inlined && !FCs.empty());
229 // Copy any unresolved call nodes into the Globals graph and
230 // filter out unresolved call nodes inlined from the callee.
232 Graph->GlobalsGraph->cloneCalls(*Graph);
234 Graph->maskIncompleteMarkers();
235 Graph->markIncompleteNodes();
236 Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
238 DEBUG(cerr << " [BU] Done inlining: " << F.getName() << "\n");