1 //===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the TDDataStructures class, which represents the
11 // Top-down Interprocedural closure of the data structure graph over the
12 // program. This is useful (but not strictly necessary?) for applications
13 // like pointer analysis.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Analysis/DataStructure/DataStructure.h"
18 #include "llvm/Module.h"
19 #include "llvm/DerivedTypes.h"
20 #include "llvm/Analysis/DataStructure/DSGraph.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/ADT/Statistic.h"
26 RegisterAnalysis<TDDataStructures> // Register the pass
27 Y("tddatastructure", "Top-down Data Structure Analysis");
29 Statistic<> NumTDInlines("tddatastructures", "Number of graphs inlined");
32 void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N,
33 hash_set<DSNode*> &Visited) {
34 if (!N || Visited.count(N)) return;
37 for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) {
38 DSNodeHandle &NH = N->getLink(i*N->getPointerSize());
39 if (DSNode *NN = NH.getNode()) {
40 std::vector<Function*> Functions;
41 NN->addFullFunctionList(Functions);
42 ArgsRemainIncomplete.insert(Functions.begin(), Functions.end());
43 markReachableFunctionsExternallyAccessible(NN, Visited);
49 // run - Calculate the top down data structure graphs for each function in the
52 bool TDDataStructures::runOnModule(Module &M) {
53 BUDataStructures &BU = getAnalysis<BUDataStructures>();
54 GlobalECs = BU.getGlobalECs();
55 GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
56 GlobalsGraph->setPrintAuxCalls();
58 // Figure out which functions must not mark their arguments complete because
59 // they are accessible outside this compilation unit. Currently, these
60 // arguments are functions which are reachable by global variables in the
62 const DSScalarMap &GGSM = GlobalsGraph->getScalarMap();
63 hash_set<DSNode*> Visited;
64 for (DSScalarMap::global_iterator I=GGSM.global_begin(), E=GGSM.global_end();
66 markReachableFunctionsExternallyAccessible(GGSM.find(*I)->second.getNode(),
69 // Loop over unresolved call nodes. Any functions passed into (but not
70 // returned!) from unresolvable call nodes may be invoked outside of the
72 for (DSGraph::afc_iterator I = GlobalsGraph->afc_begin(),
73 E = GlobalsGraph->afc_end(); I != E; ++I)
74 for (unsigned arg = 0, e = I->getNumPtrArgs(); arg != e; ++arg)
75 markReachableFunctionsExternallyAccessible(I->getPtrArg(arg).getNode(),
79 // Functions without internal linkage also have unknown incoming arguments!
80 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
81 if (!I->isExternal() && !I->hasInternalLinkage())
82 ArgsRemainIncomplete.insert(I);
84 // We want to traverse the call graph in reverse post-order. To do this, we
85 // calculate a post-order traversal, then reverse it.
86 hash_set<DSGraph*> VisitedGraph;
87 std::vector<DSGraph*> PostOrder;
88 const BUDataStructures::ActualCalleesTy &ActualCallees =
89 getAnalysis<BUDataStructures>().getActualCallees();
91 // Calculate top-down from main...
92 if (Function *F = M.getMainFunction())
93 ComputePostOrder(*F, VisitedGraph, PostOrder, ActualCallees);
95 // Next calculate the graphs for each unreachable function...
96 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
97 ComputePostOrder(*I, VisitedGraph, PostOrder, ActualCallees);
99 VisitedGraph.clear(); // Release memory!
101 // Visit each of the graphs in reverse post-order now!
102 while (!PostOrder.empty()) {
103 inlineGraphIntoCallees(*PostOrder.back());
104 PostOrder.pop_back();
107 ArgsRemainIncomplete.clear();
108 GlobalsGraph->removeTriviallyDeadNodes();
114 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
115 DSGraph *&G = DSInfo[&F];
116 if (G == 0) { // Not created yet? Clone BU graph...
117 G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
118 G->getAuxFunctionCalls().clear();
119 G->setPrintAuxCalls();
120 G->setGlobalsGraph(GlobalsGraph);
126 void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
127 std::vector<DSGraph*> &PostOrder,
128 const BUDataStructures::ActualCalleesTy &ActualCallees) {
129 if (F.isExternal()) return;
130 DSGraph &G = getOrCreateDSGraph(F);
131 if (Visited.count(&G)) return;
134 // Recursively traverse all of the callee graphs.
135 for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E; ++CI) {
136 Instruction *CallI = CI->getCallSite().getInstruction();
137 std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
138 BUDataStructures::ActualCalleesTy::const_iterator>
139 IP = ActualCallees.equal_range(CallI);
141 for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
143 ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
146 PostOrder.push_back(&G);
153 // releaseMemory - If the pass pipeline is done with this pass, we can release
154 // our memory... here...
156 // FIXME: This should be releaseMemory and will work fine, except that LoadVN
157 // has no way to extend the lifetime of the pass, which screws up ds-aa.
159 void TDDataStructures::releaseMyMemory() {
160 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
161 E = DSInfo.end(); I != E; ++I) {
162 I->second->getReturnNodes().erase(I->first);
163 if (I->second->getReturnNodes().empty())
167 // Empty map so next time memory is released, data structures are not
174 void TDDataStructures::inlineGraphIntoCallees(DSGraph &Graph) {
175 // Recompute the Incomplete markers and eliminate unreachable nodes.
176 Graph.maskIncompleteMarkers();
178 // If any of the functions has incomplete incoming arguments, don't mark any
179 // of them as complete.
180 bool HasIncompleteArgs = false;
181 for (DSGraph::retnodes_iterator I = Graph.retnodes_begin(),
182 E = Graph.retnodes_end(); I != E; ++I)
183 if (ArgsRemainIncomplete.count(I->first)) {
184 HasIncompleteArgs = true;
188 // Recompute the Incomplete markers. Depends on whether args are complete
190 = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs;
191 Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
193 // Delete dead nodes. Treat globals that are unreachable as dead also.
194 Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
196 // We are done with computing the current TD Graph! Now move on to
197 // inlining the current graph into the graphs for its callees, if any.
199 if (Graph.fc_begin() == Graph.fc_end()) {
200 DEBUG(std::cerr << " [TD] No callees for: " << Graph.getFunctionNames()
205 // Now that we have information about all of the callees, propagate the
206 // current graph into the callees. Clone only the reachable subgraph at
207 // each call-site, not the entire graph (even though the entire graph
208 // would be cloned only once, this should still be better on average).
210 DEBUG(std::cerr << " [TD] Inlining '" << Graph.getFunctionNames() <<"' into "
211 << Graph.getFunctionCalls().size() << " call nodes.\n");
213 const BUDataStructures::ActualCalleesTy &ActualCallees =
214 getAnalysis<BUDataStructures>().getActualCallees();
216 // Loop over all the call sites and all the callees at each call site. Build
217 // a mapping from called DSGraph's to the call sites in this function that
218 // invoke them. This is useful because we can be more efficient if there are
219 // multiple call sites to the callees in the graph from this caller.
220 std::multimap<DSGraph*, std::pair<Function*, const DSCallSite*> > CallSites;
222 for (DSGraph::fc_iterator CI = Graph.fc_begin(), E = Graph.fc_end();
224 Instruction *CallI = CI->getCallSite().getInstruction();
225 // For each function in the invoked function list at this call site...
226 std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
227 BUDataStructures::ActualCalleesTy::const_iterator>
228 IP = ActualCallees.equal_range(CallI);
229 // Loop over each actual callee at this call site
230 for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
231 I != IP.second; ++I) {
232 DSGraph& CalleeGraph = getDSGraph(*I->second);
233 if (&CalleeGraph != &Graph)
234 CallSites.insert(std::make_pair(&CalleeGraph,
235 std::make_pair(I->second, &*CI)));
239 // Now that we built the mapping, actually perform the inlining a callee graph
241 std::multimap<DSGraph*,std::pair<Function*,const DSCallSite*> >::iterator CSI;
242 for (CSI = CallSites.begin(); CSI != CallSites.end(); ) {
243 DSGraph &CalleeGraph = *CSI->first;
244 // Iterate through all of the call sites of this graph, cloning and merging
245 // any nodes required by the call.
246 ReachabilityCloner RC(CalleeGraph, Graph, 0);
248 // Clone over any global nodes that appear in both graphs.
249 for (DSScalarMap::global_iterator
250 SI = CalleeGraph.getScalarMap().global_begin(),
251 SE = CalleeGraph.getScalarMap().global_end(); SI != SE; ++SI) {
252 DSScalarMap::const_iterator GI = Graph.getScalarMap().find(*SI);
253 if (GI != Graph.getScalarMap().end())
254 RC.merge(CalleeGraph.getNodeForValue(*SI), GI->second);
257 // Loop over all of the distinct call sites in the caller of the callee.
258 for (; CSI != CallSites.end() && CSI->first == &CalleeGraph; ++CSI) {
259 Function &CF = *CSI->second.first;
260 const DSCallSite &CS = *CSI->second.second;
261 DEBUG(std::cerr << " [TD] Resolving arguments for callee graph '"
262 << CalleeGraph.getFunctionNames()
263 << "': " << CF.getFunctionType()->getNumParams()
264 << " args\n at call site (DSCallSite*) 0x" << &CS << "\n");
266 // Get the formal argument and return nodes for the called function and
267 // merge them with the cloned subgraph.
268 RC.mergeCallSite(CalleeGraph.getCallSiteForArguments(CF), CS);
273 DEBUG(std::cerr << " [TD] Done inlining into callees for: "
274 << Graph.getFunctionNames() << " [" << Graph.getGraphSize() << "+"
275 << Graph.getFunctionCalls().size() << "]\n");
278 static const Function *getFnForValue(const Value *V) {
279 if (const Instruction *I = dyn_cast<Instruction>(V))
280 return I->getParent()->getParent();
281 else if (const Argument *A = dyn_cast<Argument>(V))
282 return A->getParent();
283 else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
284 return BB->getParent();
288 void TDDataStructures::deleteValue(Value *V) {
289 if (const Function *F = getFnForValue(V)) { // Function local value?
290 // If this is a function local value, just delete it from the scalar map!
291 getDSGraph(*F).getScalarMap().eraseIfExists(V);
295 if (Function *F = dyn_cast<Function>(V)) {
296 assert(getDSGraph(*F).getReturnNodes().size() == 1 &&
297 "cannot handle scc's");
303 assert(!isa<GlobalVariable>(V) && "Do not know how to delete GV's yet!");
306 void TDDataStructures::copyValue(Value *From, Value *To) {
307 if (From == To) return;
308 if (const Function *F = getFnForValue(From)) { // Function local value?
309 // If this is a function local value, just delete it from the scalar map!
310 getDSGraph(*F).getScalarMap().copyScalarIfExists(From, To);
314 if (Function *FromF = dyn_cast<Function>(From)) {
315 Function *ToF = cast<Function>(To);
316 assert(!DSInfo.count(ToF) && "New Function already exists!");
317 DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs);
319 assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!");
321 // Change the Function* is the returnnodes map to the ToF.
322 DSNodeHandle Ret = NG->retnodes_begin()->second;
323 NG->getReturnNodes().clear();
324 NG->getReturnNodes()[ToF] = Ret;
328 assert(!isa<GlobalVariable>(From) && "Do not know how to copy GV's yet!");