LLVM API Documentation
00001 //===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the TDDataStructures class, which represents the 00011 // Top-down Interprocedural closure of the data structure graph over the 00012 // program. This is useful (but not strictly necessary?) for applications 00013 // like pointer analysis. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/DataStructure/DataStructure.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Analysis/DataStructure/DSGraph.h" 00021 #include "llvm/Support/Debug.h" 00022 #include "llvm/ADT/Statistic.h" 00023 using namespace llvm; 00024 00025 namespace { 00026 RegisterAnalysis<TDDataStructures> // Register the pass 00027 Y("tddatastructure", "Top-down Data Structure Analysis"); 00028 00029 Statistic<> NumTDInlines("tddatastructures", "Number of graphs inlined"); 00030 } 00031 00032 void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N, 00033 hash_set<DSNode*> &Visited) { 00034 if (!N || Visited.count(N)) return; 00035 Visited.insert(N); 00036 00037 for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) { 00038 DSNodeHandle &NH = N->getLink(i*N->getPointerSize()); 00039 if (DSNode *NN = NH.getNode()) { 00040 const std::vector<GlobalValue*> &Globals = NN->getGlobals(); 00041 for (unsigned G = 0, e = Globals.size(); G != e; ++G) 00042 if (Function *F = dyn_cast<Function>(Globals[G])) 00043 ArgsRemainIncomplete.insert(F); 00044 00045 markReachableFunctionsExternallyAccessible(NN, Visited); 00046 } 00047 } 00048 } 00049 00050 00051 // run - Calculate the top down data structure graphs for each function in the 00052 // program. 00053 // 00054 bool TDDataStructures::runOnModule(Module &M) { 00055 BUDataStructures &BU = getAnalysis<BUDataStructures>(); 00056 GlobalsGraph = new DSGraph(BU.getGlobalsGraph()); 00057 GlobalsGraph->setPrintAuxCalls(); 00058 00059 // Figure out which functions must not mark their arguments complete because 00060 // they are accessible outside this compilation unit. Currently, these 00061 // arguments are functions which are reachable by global variables in the 00062 // globals graph. 00063 const DSScalarMap &GGSM = GlobalsGraph->getScalarMap(); 00064 hash_set<DSNode*> Visited; 00065 for (DSScalarMap::global_iterator I=GGSM.global_begin(), E=GGSM.global_end(); 00066 I != E; ++I) 00067 markReachableFunctionsExternallyAccessible(GGSM.find(*I)->second.getNode(), 00068 Visited); 00069 00070 // Loop over unresolved call nodes. Any functions passed into (but not 00071 // returned!) from unresolvable call nodes may be invoked outside of the 00072 // current module. 00073 const std::vector<DSCallSite> &Calls = GlobalsGraph->getAuxFunctionCalls(); 00074 for (unsigned i = 0, e = Calls.size(); i != e; ++i) { 00075 const DSCallSite &CS = Calls[i]; 00076 for (unsigned arg = 0, e = CS.getNumPtrArgs(); arg != e; ++arg) 00077 markReachableFunctionsExternallyAccessible(CS.getPtrArg(arg).getNode(), 00078 Visited); 00079 } 00080 Visited.clear(); 00081 00082 // Functions without internal linkage also have unknown incoming arguments! 00083 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00084 if (!I->isExternal() && !I->hasInternalLinkage()) 00085 ArgsRemainIncomplete.insert(I); 00086 00087 // We want to traverse the call graph in reverse post-order. To do this, we 00088 // calculate a post-order traversal, then reverse it. 00089 hash_set<DSGraph*> VisitedGraph; 00090 std::vector<DSGraph*> PostOrder; 00091 const BUDataStructures::ActualCalleesTy &ActualCallees = 00092 getAnalysis<BUDataStructures>().getActualCallees(); 00093 00094 // Calculate top-down from main... 00095 if (Function *F = M.getMainFunction()) 00096 ComputePostOrder(*F, VisitedGraph, PostOrder, ActualCallees); 00097 00098 // Next calculate the graphs for each unreachable function... 00099 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00100 ComputePostOrder(*I, VisitedGraph, PostOrder, ActualCallees); 00101 00102 VisitedGraph.clear(); // Release memory! 00103 00104 // Visit each of the graphs in reverse post-order now! 00105 while (!PostOrder.empty()) { 00106 inlineGraphIntoCallees(*PostOrder.back()); 00107 PostOrder.pop_back(); 00108 } 00109 00110 ArgsRemainIncomplete.clear(); 00111 GlobalsGraph->removeTriviallyDeadNodes(); 00112 00113 return false; 00114 } 00115 00116 00117 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) { 00118 DSGraph *&G = DSInfo[&F]; 00119 if (G == 0) { // Not created yet? Clone BU graph... 00120 G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F)); 00121 G->getAuxFunctionCalls().clear(); 00122 G->setPrintAuxCalls(); 00123 G->setGlobalsGraph(GlobalsGraph); 00124 } 00125 return *G; 00126 } 00127 00128 00129 void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited, 00130 std::vector<DSGraph*> &PostOrder, 00131 const BUDataStructures::ActualCalleesTy &ActualCallees) { 00132 if (F.isExternal()) return; 00133 DSGraph &G = getOrCreateDSGraph(F); 00134 if (Visited.count(&G)) return; 00135 Visited.insert(&G); 00136 00137 // Recursively traverse all of the callee graphs. 00138 const std::vector<DSCallSite> &FunctionCalls = G.getFunctionCalls(); 00139 00140 for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) { 00141 Instruction *CallI = FunctionCalls[i].getCallSite().getInstruction(); 00142 std::pair<BUDataStructures::ActualCalleesTy::const_iterator, 00143 BUDataStructures::ActualCalleesTy::const_iterator> 00144 IP = ActualCallees.equal_range(CallI); 00145 00146 for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first; 00147 I != IP.second; ++I) 00148 ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees); 00149 } 00150 00151 PostOrder.push_back(&G); 00152 } 00153 00154 00155 00156 00157 00158 // releaseMemory - If the pass pipeline is done with this pass, we can release 00159 // our memory... here... 00160 // 00161 // FIXME: This should be releaseMemory and will work fine, except that LoadVN 00162 // has no way to extend the lifetime of the pass, which screws up ds-aa. 00163 // 00164 void TDDataStructures::releaseMyMemory() { 00165 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 00166 E = DSInfo.end(); I != E; ++I) { 00167 I->second->getReturnNodes().erase(I->first); 00168 if (I->second->getReturnNodes().empty()) 00169 delete I->second; 00170 } 00171 00172 // Empty map so next time memory is released, data structures are not 00173 // re-deleted. 00174 DSInfo.clear(); 00175 delete GlobalsGraph; 00176 GlobalsGraph = 0; 00177 } 00178 00179 void TDDataStructures::inlineGraphIntoCallees(DSGraph &Graph) { 00180 // Recompute the Incomplete markers and eliminate unreachable nodes. 00181 Graph.maskIncompleteMarkers(); 00182 00183 // If any of the functions has incomplete incoming arguments, don't mark any 00184 // of them as complete. 00185 bool HasIncompleteArgs = false; 00186 const DSGraph::ReturnNodesTy &GraphReturnNodes = Graph.getReturnNodes(); 00187 for (DSGraph::ReturnNodesTy::const_iterator I = GraphReturnNodes.begin(), 00188 E = GraphReturnNodes.end(); I != E; ++I) 00189 if (ArgsRemainIncomplete.count(I->first)) { 00190 HasIncompleteArgs = true; 00191 break; 00192 } 00193 00194 // Now fold in the necessary globals from the GlobalsGraph. A global G 00195 // must be folded in if it exists in the current graph (i.e., is not dead) 00196 // and it was not inlined from any of my callers. If it was inlined from 00197 // a caller, it would have been fully consistent with the GlobalsGraph 00198 // in the caller so folding in is not necessary. Otherwise, this node came 00199 // solely from this function's BU graph and so has to be made consistent. 00200 // 00201 Graph.updateFromGlobalGraph(); 00202 00203 // Recompute the Incomplete markers. Depends on whether args are complete 00204 unsigned Flags 00205 = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs; 00206 Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals); 00207 00208 // Delete dead nodes. Treat globals that are unreachable as dead also. 00209 Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals); 00210 00211 // We are done with computing the current TD Graph! Now move on to 00212 // inlining the current graph into the graphs for its callees, if any. 00213 // 00214 const std::vector<DSCallSite> &FunctionCalls = Graph.getFunctionCalls(); 00215 if (FunctionCalls.empty()) { 00216 DEBUG(std::cerr << " [TD] No callees for: " << Graph.getFunctionNames() 00217 << "\n"); 00218 return; 00219 } 00220 00221 // Now that we have information about all of the callees, propagate the 00222 // current graph into the callees. Clone only the reachable subgraph at 00223 // each call-site, not the entire graph (even though the entire graph 00224 // would be cloned only once, this should still be better on average). 00225 // 00226 DEBUG(std::cerr << " [TD] Inlining '" << Graph.getFunctionNames() <<"' into " 00227 << FunctionCalls.size() << " call nodes.\n"); 00228 00229 const BUDataStructures::ActualCalleesTy &ActualCallees = 00230 getAnalysis<BUDataStructures>().getActualCallees(); 00231 00232 // Loop over all the call sites and all the callees at each call site. Build 00233 // a mapping from called DSGraph's to the call sites in this function that 00234 // invoke them. This is useful because we can be more efficient if there are 00235 // multiple call sites to the callees in the graph from this caller. 00236 std::multimap<DSGraph*, std::pair<Function*, const DSCallSite*> > CallSites; 00237 00238 for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) { 00239 Instruction *CallI = FunctionCalls[i].getCallSite().getInstruction(); 00240 // For each function in the invoked function list at this call site... 00241 std::pair<BUDataStructures::ActualCalleesTy::const_iterator, 00242 BUDataStructures::ActualCalleesTy::const_iterator> 00243 IP = ActualCallees.equal_range(CallI); 00244 // Loop over each actual callee at this call site 00245 for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first; 00246 I != IP.second; ++I) { 00247 DSGraph& CalleeGraph = getDSGraph(*I->second); 00248 assert(&CalleeGraph != &Graph && "TD need not inline graph into self!"); 00249 00250 CallSites.insert(std::make_pair(&CalleeGraph, 00251 std::make_pair(I->second, &FunctionCalls[i]))); 00252 } 00253 } 00254 00255 // Now that we built the mapping, actually perform the inlining a callee graph 00256 // at a time. 00257 std::multimap<DSGraph*,std::pair<Function*,const DSCallSite*> >::iterator CSI; 00258 for (CSI = CallSites.begin(); CSI != CallSites.end(); ) { 00259 DSGraph &CalleeGraph = *CSI->first; 00260 // Iterate through all of the call sites of this graph, cloning and merging 00261 // any nodes required by the call. 00262 ReachabilityCloner RC(CalleeGraph, Graph, DSGraph::StripModRefBits); 00263 00264 // Clone over any global nodes that appear in both graphs. 00265 for (DSScalarMap::global_iterator 00266 SI = CalleeGraph.getScalarMap().global_begin(), 00267 SE = CalleeGraph.getScalarMap().global_end(); SI != SE; ++SI) { 00268 DSScalarMap::const_iterator GI = Graph.getScalarMap().find(*SI); 00269 if (GI != Graph.getScalarMap().end()) 00270 RC.merge(CalleeGraph.getNodeForValue(*SI), GI->second); 00271 } 00272 00273 // Loop over all of the distinct call sites in the caller of the callee. 00274 for (; CSI != CallSites.end() && CSI->first == &CalleeGraph; ++CSI) { 00275 Function &CF = *CSI->second.first; 00276 const DSCallSite &CS = *CSI->second.second; 00277 DEBUG(std::cerr << " [TD] Resolving arguments for callee graph '" 00278 << CalleeGraph.getFunctionNames() 00279 << "': " << CF.getFunctionType()->getNumParams() 00280 << " args\n at call site (DSCallSite*) 0x" << &CS << "\n"); 00281 00282 // Get the formal argument and return nodes for the called function and 00283 // merge them with the cloned subgraph. 00284 RC.mergeCallSite(CalleeGraph.getCallSiteForArguments(CF), CS); 00285 ++NumTDInlines; 00286 } 00287 } 00288 00289 DEBUG(std::cerr << " [TD] Done inlining into callees for: " 00290 << Graph.getFunctionNames() << " [" << Graph.getGraphSize() << "+" 00291 << Graph.getFunctionCalls().size() << "]\n"); 00292 }