1 //===- BottomUpClosure.cpp - Compute bottom-up interprocedural 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 alias analysis.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/DataStructure.h"
11 #include "llvm/Analysis/DSGraph.h"
12 #include "llvm/Module.h"
13 #include "Support/Statistic.h"
16 static RegisterAnalysis<BUDataStructures>
17 X("budatastructure", "Bottom-up Data Structure Analysis Closure");
19 namespace DataStructureAnalysis { // TODO: FIXME: Eliminate
20 // isPointerType - Return true if this first class type is big enough to hold
23 bool isPointerType(const Type *Ty);
25 using namespace DataStructureAnalysis;
28 // releaseMemory - If the pass pipeline is done with this pass, we can release
29 // our memory... here...
31 void BUDataStructures::releaseMemory() {
32 // Delete all call site information
35 for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
36 E = DSInfo.end(); I != E; ++I)
39 // Empty map so next time memory is released, data structures are not
44 // run - Calculate the bottom up data structure graphs for each function in the
47 bool BUDataStructures::run(Module &M) {
48 // Simply calculate the graphs for each function...
49 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
55 // ResolveArguments - Resolve the formal and actual arguments for a function
58 static void ResolveArguments(DSCallSite &Call, Function &F,
59 map<Value*, DSNodeHandle> &ScalarMap) {
60 // Resolve all of the function arguments...
61 Function::aiterator AI = F.abegin();
62 for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i, ++AI) {
63 // Advance the argument iterator to the first pointer argument...
64 while (!isPointerType(AI->getType())) {
68 std::cerr << "Bad call to Function: " << F.getName() << "\n";
70 assert(AI != F.aend() && "# Args provided is not # Args required!");
73 // Add the link from the argument scalar to the provided value
74 ScalarMap[AI].mergeWith(Call.getPtrArg(i));
78 DSGraph &BUDataStructures::calculateGraph(Function &F) {
79 // Make sure this graph has not already been calculated, or that we don't get
80 // into an infinite loop with mutually recursive functions.
82 DSGraph *&Graph = DSInfo[&F];
83 if (Graph) return *Graph;
85 // Copy the local version into DSInfo...
86 Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
89 // Populate the GlobalsGraph with globals from this one.
90 Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
93 // Start resolving calls...
94 std::vector<DSCallSite> &FCs = Graph->getFunctionCalls();
96 DEBUG(std::cerr << " [BU] Inlining: " << F.getName() << "\n");
102 for (unsigned i = 0; i != FCs.size(); ++i) {
103 // Copy the call, because inlining graphs may invalidate the FCs vector.
104 DSCallSite Call = FCs[i];
106 // If the function list is complete...
107 if ((Call.getCallee().getNode()->NodeType & DSNode::Incomplete)==0) {
108 // Start inlining all of the functions we can... some may not be
109 // inlinable if they are external...
111 std::vector<GlobalValue*> Callees =
112 Call.getCallee().getNode()->getGlobals();
114 // Loop over the functions, inlining whatever we can...
115 for (unsigned c = 0; c != Callees.size(); ++c) {
116 // Must be a function type, so this cast MUST succeed.
117 Function &FI = cast<Function>(*Callees[c]);
120 // Self recursion... simply link up the formal arguments with the
121 // actual arguments...
122 DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
124 // Handle the return value if present...
125 Graph->getRetNode().mergeWith(Call.getRetVal());
127 // Resolve the arguments in the call to the actual values...
128 ResolveArguments(Call, F, Graph->getScalarMap());
130 // Erase the entry in the callees vector
131 Callees.erase(Callees.begin()+c--);
133 } else if (!FI.isExternal()) {
134 DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
135 << FI.getName() << "\n");
137 // Get the data structure graph for the called function, closing it
138 // if possible (which is only impossible in the case of mutual
141 DSGraph &GI = calculateGraph(FI); // Graph to inline
143 DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
144 << " in: " << F.getName() << "\n");
146 // Record that the original DSCallSite was a call site of FI.
147 // This may or may not have been known when the DSCallSite was
148 // originally created.
149 std::vector<DSCallSite> &CallSitesForFunc = CallSites[&FI];
150 CallSitesForFunc.push_back(Call);
151 CallSitesForFunc.back().setResolvingCaller(&F);
152 CallSitesForFunc.back().setCallee(0);
154 // Clone the callee's graph into the current graph, keeping
155 // track of where scalars in the old graph _used_ to point,
156 // and of the new nodes matching nodes of the old graph.
157 map<Value*, DSNodeHandle> OldValMap;
158 map<const DSNode*, DSNode*> OldNodeMap;
160 // The clone call may invalidate any of the vectors in the data
161 // structure graph. Strip locals and don't copy the list of callers
162 DSNodeHandle RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
163 /*StripScalars*/ true,
164 /*StripAllocas*/ true);
166 // Resolve the arguments in the call to the actual values...
167 ResolveArguments(Call, FI, OldValMap);
169 // Handle the return value if present...
170 RetVal.mergeWith(Call.getRetVal());
172 // Erase the entry in the Callees vector
173 Callees.erase(Callees.begin()+c--);
175 } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
176 FI.getName() == "fprintf" || FI.getName() == "open" ||
177 FI.getName() == "sprintf") {
178 // FIXME: These special cases (eg printf) should go away when we can
179 // define functions that take a variable number of arguments.
181 // FIXME: at the very least, this should update mod/ref info
182 // Erase the entry in the globals vector
183 Callees.erase(Callees.begin()+c--);
187 if (Callees.empty()) { // Inlined all of the function calls?
188 // Erase the call if it is resolvable...
189 FCs.erase(FCs.begin()+i--); // Don't skip a the next call...
191 } else if (Callees.size() !=
192 Call.getCallee().getNode()->getGlobals().size()) {
193 // Was able to inline SOME, but not all of the functions. Construct a
194 // new global node here.
196 assert(0 && "Unimpl!");
202 // Recompute the Incomplete markers. If there are any function calls left
203 // now that are complete, we must loop!
205 Graph->maskIncompleteMarkers();
206 Graph->markIncompleteNodes();
207 Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
209 } while (Inlined && !FCs.empty());
211 Graph->maskIncompleteMarkers();
212 Graph->markIncompleteNodes();
213 Graph->removeTriviallyDeadNodes(false);
214 Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
216 DEBUG(std::cerr << " [BU] Done inlining: " << F.getName() << " ["
217 << Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()