LLVM API Documentation
00001 //===- BottomUpClosure.cpp - Compute bottom-up interprocedural 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 BUDataStructures class, which represents the 00011 // Bottom-Up Interprocedural closure of the data structure graph over the 00012 // program. This is useful for applications like pool allocation, but **not** 00013 // applications like alias analysis. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/DataStructure/DataStructure.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/ADT/Statistic.h" 00020 #include "llvm/Support/Debug.h" 00021 #include "DSCallSiteIterator.h" 00022 using namespace llvm; 00023 00024 namespace { 00025 Statistic<> MaxSCC("budatastructure", "Maximum SCC Size in Call Graph"); 00026 Statistic<> NumBUInlines("budatastructures", "Number of graphs inlined"); 00027 Statistic<> NumCallEdges("budatastructures", "Number of 'actual' call edges"); 00028 00029 RegisterAnalysis<BUDataStructures> 00030 X("budatastructure", "Bottom-up Data Structure Analysis"); 00031 } 00032 00033 using namespace DS; 00034 00035 // run - Calculate the bottom up data structure graphs for each function in the 00036 // program. 00037 // 00038 bool BUDataStructures::runOnModule(Module &M) { 00039 LocalDataStructures &LocalDSA = getAnalysis<LocalDataStructures>(); 00040 GlobalsGraph = new DSGraph(LocalDSA.getGlobalsGraph()); 00041 GlobalsGraph->setPrintAuxCalls(); 00042 00043 Function *MainFunc = M.getMainFunction(); 00044 if (MainFunc) 00045 calculateReachableGraphs(MainFunc); 00046 00047 // Calculate the graphs for any functions that are unreachable from main... 00048 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00049 if (!I->isExternal() && !DSInfo.count(I)) { 00050 #ifndef NDEBUG 00051 if (MainFunc) 00052 std::cerr << "*** Function unreachable from main: " 00053 << I->getName() << "\n"; 00054 #endif 00055 calculateReachableGraphs(I); // Calculate all graphs... 00056 } 00057 00058 NumCallEdges += ActualCallees.size(); 00059 00060 // At the end of the bottom-up pass, the globals graph becomes complete. 00061 // FIXME: This is not the right way to do this, but it is sorta better than 00062 // nothing! In particular, externally visible globals and unresolvable call 00063 // nodes at the end of the BU phase should make things that they point to 00064 // incomplete in the globals graph. 00065 // 00066 GlobalsGraph->removeTriviallyDeadNodes(); 00067 GlobalsGraph->maskIncompleteMarkers(); 00068 return false; 00069 } 00070 00071 void BUDataStructures::calculateReachableGraphs(Function *F) { 00072 std::vector<Function*> Stack; 00073 hash_map<Function*, unsigned> ValMap; 00074 unsigned NextID = 1; 00075 calculateGraphs(F, Stack, NextID, ValMap); 00076 } 00077 00078 DSGraph &BUDataStructures::getOrCreateGraph(Function *F) { 00079 // Has the graph already been created? 00080 DSGraph *&Graph = DSInfo[F]; 00081 if (Graph) return *Graph; 00082 00083 // Copy the local version into DSInfo... 00084 Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(*F)); 00085 00086 Graph->setGlobalsGraph(GlobalsGraph); 00087 Graph->setPrintAuxCalls(); 00088 00089 // Start with a copy of the original call sites... 00090 Graph->getAuxFunctionCalls() = Graph->getFunctionCalls(); 00091 return *Graph; 00092 } 00093 00094 unsigned BUDataStructures::calculateGraphs(Function *F, 00095 std::vector<Function*> &Stack, 00096 unsigned &NextID, 00097 hash_map<Function*, unsigned> &ValMap) { 00098 assert(!ValMap.count(F) && "Shouldn't revisit functions!"); 00099 unsigned Min = NextID++, MyID = Min; 00100 ValMap[F] = Min; 00101 Stack.push_back(F); 00102 00103 // FIXME! This test should be generalized to be any function that we have 00104 // already processed, in the case when there isn't a main or there are 00105 // unreachable functions! 00106 if (F->isExternal()) { // sprintf, fprintf, sscanf, etc... 00107 // No callees! 00108 Stack.pop_back(); 00109 ValMap[F] = ~0; 00110 return Min; 00111 } 00112 00113 DSGraph &Graph = getOrCreateGraph(F); 00114 00115 // The edges out of the current node are the call site targets... 00116 for (DSCallSiteIterator I = DSCallSiteIterator::begin_aux(Graph), 00117 E = DSCallSiteIterator::end_aux(Graph); I != E; ++I) { 00118 Function *Callee = *I; 00119 unsigned M; 00120 // Have we visited the destination function yet? 00121 hash_map<Function*, unsigned>::iterator It = ValMap.find(Callee); 00122 if (It == ValMap.end()) // No, visit it now. 00123 M = calculateGraphs(Callee, Stack, NextID, ValMap); 00124 else // Yes, get it's number. 00125 M = It->second; 00126 if (M < Min) Min = M; 00127 } 00128 00129 assert(ValMap[F] == MyID && "SCC construction assumption wrong!"); 00130 if (Min != MyID) 00131 return Min; // This is part of a larger SCC! 00132 00133 // If this is a new SCC, process it now. 00134 if (Stack.back() == F) { // Special case the single "SCC" case here. 00135 DEBUG(std::cerr << "Visiting single node SCC #: " << MyID << " fn: " 00136 << F->getName() << "\n"); 00137 Stack.pop_back(); 00138 DSGraph &G = getDSGraph(*F); 00139 DEBUG(std::cerr << " [BU] Calculating graph for: " << F->getName()<< "\n"); 00140 calculateGraph(G); 00141 DEBUG(std::cerr << " [BU] Done inlining: " << F->getName() << " [" 00142 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() 00143 << "]\n"); 00144 00145 if (MaxSCC < 1) MaxSCC = 1; 00146 00147 // Should we revisit the graph? 00148 if (DSCallSiteIterator::begin_aux(G) != DSCallSiteIterator::end_aux(G)) { 00149 ValMap.erase(F); 00150 return calculateGraphs(F, Stack, NextID, ValMap); 00151 } else { 00152 ValMap[F] = ~0U; 00153 } 00154 return MyID; 00155 00156 } else { 00157 // SCCFunctions - Keep track of the functions in the current SCC 00158 // 00159 hash_set<DSGraph*> SCCGraphs; 00160 00161 Function *NF; 00162 std::vector<Function*>::iterator FirstInSCC = Stack.end(); 00163 DSGraph *SCCGraph = 0; 00164 do { 00165 NF = *--FirstInSCC; 00166 ValMap[NF] = ~0U; 00167 00168 // Figure out which graph is the largest one, in order to speed things up 00169 // a bit in situations where functions in the SCC have widely different 00170 // graph sizes. 00171 DSGraph &NFGraph = getDSGraph(*NF); 00172 SCCGraphs.insert(&NFGraph); 00173 // FIXME: If we used a better way of cloning graphs (ie, just splice all 00174 // of the nodes into the new graph), this would be completely unneeded! 00175 if (!SCCGraph || SCCGraph->getGraphSize() < NFGraph.getGraphSize()) 00176 SCCGraph = &NFGraph; 00177 } while (NF != F); 00178 00179 std::cerr << "Calculating graph for SCC #: " << MyID << " of size: " 00180 << SCCGraphs.size() << "\n"; 00181 00182 // Compute the Max SCC Size... 00183 if (MaxSCC < SCCGraphs.size()) 00184 MaxSCC = SCCGraphs.size(); 00185 00186 // First thing first, collapse all of the DSGraphs into a single graph for 00187 // the entire SCC. We computed the largest graph, so clone all of the other 00188 // (smaller) graphs into it. Discard all of the old graphs. 00189 // 00190 for (hash_set<DSGraph*>::iterator I = SCCGraphs.begin(), 00191 E = SCCGraphs.end(); I != E; ++I) { 00192 DSGraph &G = **I; 00193 if (&G != SCCGraph) { 00194 { 00195 DSGraph::NodeMapTy NodeMap; 00196 SCCGraph->cloneInto(G, SCCGraph->getScalarMap(), 00197 SCCGraph->getReturnNodes(), NodeMap); 00198 } 00199 // Update the DSInfo map and delete the old graph... 00200 for (DSGraph::ReturnNodesTy::iterator I = G.getReturnNodes().begin(), 00201 E = G.getReturnNodes().end(); I != E; ++I) 00202 DSInfo[I->first] = SCCGraph; 00203 delete &G; 00204 } 00205 } 00206 00207 // Clean up the graph before we start inlining a bunch again... 00208 SCCGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00209 00210 // Now that we have one big happy family, resolve all of the call sites in 00211 // the graph... 00212 calculateGraph(*SCCGraph); 00213 DEBUG(std::cerr << " [BU] Done inlining SCC [" << SCCGraph->getGraphSize() 00214 << "+" << SCCGraph->getAuxFunctionCalls().size() << "]\n"); 00215 00216 std::cerr << "DONE with SCC #: " << MyID << "\n"; 00217 00218 // We never have to revisit "SCC" processed functions... 00219 00220 // Drop the stuff we don't need from the end of the stack 00221 Stack.erase(FirstInSCC, Stack.end()); 00222 return MyID; 00223 } 00224 00225 return MyID; // == Min 00226 } 00227 00228 00229 // releaseMemory - If the pass pipeline is done with this pass, we can release 00230 // our memory... here... 00231 // 00232 void BUDataStructures::releaseMemory() { 00233 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 00234 E = DSInfo.end(); I != E; ++I) { 00235 I->second->getReturnNodes().erase(I->first); 00236 if (I->second->getReturnNodes().empty()) 00237 delete I->second; 00238 } 00239 00240 // Empty map so next time memory is released, data structures are not 00241 // re-deleted. 00242 DSInfo.clear(); 00243 delete GlobalsGraph; 00244 GlobalsGraph = 0; 00245 } 00246 00247 void BUDataStructures::calculateGraph(DSGraph &Graph) { 00248 // Move our call site list into TempFCs so that inline call sites go into the 00249 // new call site list and doesn't invalidate our iterators! 00250 std::vector<DSCallSite> TempFCs; 00251 std::vector<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls(); 00252 TempFCs.swap(AuxCallsList); 00253 00254 DSGraph::ReturnNodesTy &ReturnNodes = Graph.getReturnNodes(); 00255 00256 // Loop over all of the resolvable call sites 00257 unsigned LastCallSiteIdx = ~0U; 00258 for (DSCallSiteIterator I = DSCallSiteIterator::begin(TempFCs), 00259 E = DSCallSiteIterator::end(TempFCs); I != E; ++I) { 00260 // If we skipped over any call sites, they must be unresolvable, copy them 00261 // to the real call site list. 00262 LastCallSiteIdx++; 00263 for (; LastCallSiteIdx < I.getCallSiteIdx(); ++LastCallSiteIdx) 00264 AuxCallsList.push_back(TempFCs[LastCallSiteIdx]); 00265 LastCallSiteIdx = I.getCallSiteIdx(); 00266 00267 // Resolve the current call... 00268 Function *Callee = *I; 00269 DSCallSite CS = I.getCallSite(); 00270 00271 if (Callee->isExternal()) { 00272 // Ignore this case, simple varargs functions we cannot stub out! 00273 } else if (ReturnNodes.count(Callee)) { 00274 // Self recursion... simply link up the formal arguments with the 00275 // actual arguments... 00276 DEBUG(std::cerr << " Self Inlining: " << Callee->getName() << "\n"); 00277 00278 // Handle self recursion by resolving the arguments and return value 00279 Graph.mergeInGraph(CS, *Callee, Graph, 0); 00280 00281 } else { 00282 ActualCallees.insert(std::make_pair(CS.getCallSite().getInstruction(), 00283 Callee)); 00284 00285 // Get the data structure graph for the called function. 00286 // 00287 DSGraph &GI = getDSGraph(*Callee); // Graph to inline 00288 00289 DEBUG(std::cerr << " Inlining graph for " << Callee->getName() 00290 << "[" << GI.getGraphSize() << "+" 00291 << GI.getAuxFunctionCalls().size() << "] into '" 00292 << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() << "+" 00293 << Graph.getAuxFunctionCalls().size() << "]\n"); 00294 Graph.mergeInGraph(CS, *Callee, GI, 00295 DSGraph::KeepModRefBits | 00296 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes); 00297 ++NumBUInlines; 00298 00299 #if 0 00300 Graph.writeGraphToFile(std::cerr, "bu_" + F.getName() + "_after_" + 00301 Callee->getName()); 00302 #endif 00303 } 00304 } 00305 00306 // Make sure to catch any leftover unresolvable calls... 00307 for (++LastCallSiteIdx; LastCallSiteIdx < TempFCs.size(); ++LastCallSiteIdx) 00308 AuxCallsList.push_back(TempFCs[LastCallSiteIdx]); 00309 00310 TempFCs.clear(); 00311 00312 // Recompute the Incomplete markers 00313 assert(Graph.getInlinedGlobals().empty()); 00314 Graph.maskIncompleteMarkers(); 00315 Graph.markIncompleteNodes(DSGraph::MarkFormalArgs); 00316 00317 // Delete dead nodes. Treat globals that are unreachable but that can 00318 // reach live nodes as live. 00319 Graph.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00320 00321 // When this graph is finalized, clone the globals in the graph into the 00322 // globals graph to make sure it has everything, from all graphs. 00323 DSScalarMap &MainSM = Graph.getScalarMap(); 00324 ReachabilityCloner RC(*GlobalsGraph, Graph, DSGraph::StripAllocaBit); 00325 00326 // Clone everything reachable from globals in the function graph into the 00327 // globals graph. 00328 for (DSScalarMap::global_iterator I = MainSM.global_begin(), 00329 E = MainSM.global_end(); I != E; ++I) 00330 RC.getClonedNH(MainSM[*I]); 00331 00332 //Graph.writeGraphToFile(std::cerr, "bu_" + F.getName()); 00333 }