LLVM API Documentation
00001 //===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===// 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 pass is the same as the complete bottom-up graphs, but 00011 // with functions partitioned into equivalence classes and a single merged 00012 // DS graph for all functions in an equivalence class. After this merging, 00013 // graphs are inlined bottom-up on the SCCs of the final (CBU) call graph. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "ECGraphs" 00018 #include "llvm/Analysis/DataStructure/DataStructure.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Module.h" 00021 #include "llvm/Pass.h" 00022 #include "llvm/Analysis/DataStructure/DSGraph.h" 00023 #include "llvm/Support/CallSite.h" 00024 #include "llvm/Support/Debug.h" 00025 #include "llvm/ADT/SCCIterator.h" 00026 #include "llvm/ADT/Statistic.h" 00027 #include "llvm/ADT/EquivalenceClasses.h" 00028 #include "llvm/ADT/STLExtras.h" 00029 #include <iostream> 00030 using namespace llvm; 00031 00032 namespace { 00033 RegisterAnalysis<EquivClassGraphs> X("eqdatastructure", 00034 "Equivalence-class Bottom-up Data Structure Analysis"); 00035 Statistic<> NumEquivBUInlines("equivdatastructures", 00036 "Number of graphs inlined"); 00037 Statistic<> NumFoldGraphInlines("Inline equiv-class graphs bottom up", 00038 "Number of graphs inlined"); 00039 } 00040 00041 #ifndef NDEBUG 00042 template<typename GT> 00043 static void CheckAllGraphs(Module *M, GT &ECGraphs) { 00044 DSGraph &GG = ECGraphs.getGlobalsGraph(); 00045 00046 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 00047 if (!I->isExternal()) { 00048 DSGraph &G = ECGraphs.getDSGraph(*I); 00049 if (G.retnodes_begin()->first != I) 00050 continue; // Only check a graph once. 00051 00052 DSGraph::NodeMapTy GlobalsGraphNodeMapping; 00053 G.computeGToGGMapping(GlobalsGraphNodeMapping); 00054 } 00055 } 00056 #endif 00057 00058 // getSomeCalleeForCallSite - Return any one callee function at a call site. 00059 // 00060 Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{ 00061 Function *thisFunc = CS.getCaller(); 00062 assert(thisFunc && "getSomeCalleeForCallSite(): Not a valid call site?"); 00063 DSGraph &DSG = getDSGraph(*thisFunc); 00064 DSNode *calleeNode = DSG.getNodeForValue(CS.getCalledValue()).getNode(); 00065 std::map<DSNode*, Function *>::const_iterator I = 00066 OneCalledFunction.find(calleeNode); 00067 return (I == OneCalledFunction.end())? NULL : I->second; 00068 } 00069 00070 // runOnModule - Calculate the bottom up data structure graphs for each function 00071 // in the program. 00072 // 00073 bool EquivClassGraphs::runOnModule(Module &M) { 00074 CBU = &getAnalysis<CompleteBUDataStructures>(); 00075 GlobalECs = CBU->getGlobalECs(); 00076 DEBUG(CheckAllGraphs(&M, *CBU)); 00077 00078 GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs); 00079 GlobalsGraph->setPrintAuxCalls(); 00080 00081 ActualCallees = CBU->getActualCallees(); 00082 00083 // Find equivalence classes of functions called from common call sites. 00084 // Fold the CBU graphs for all functions in an equivalence class. 00085 buildIndirectFunctionSets(M); 00086 00087 // Stack of functions used for Tarjan's SCC-finding algorithm. 00088 std::vector<DSGraph*> Stack; 00089 std::map<DSGraph*, unsigned> ValMap; 00090 unsigned NextID = 1; 00091 00092 Function *MainFunc = M.getMainFunction(); 00093 if (MainFunc && !MainFunc->isExternal()) { 00094 processSCC(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap); 00095 } else { 00096 std::cerr << "Fold Graphs: No 'main' function found!\n"; 00097 } 00098 00099 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00100 if (!I->isExternal()) 00101 processSCC(getOrCreateGraph(*I), Stack, NextID, ValMap); 00102 00103 DEBUG(CheckAllGraphs(&M, *this)); 00104 00105 getGlobalsGraph().removeTriviallyDeadNodes(); 00106 getGlobalsGraph().markIncompleteNodes(DSGraph::IgnoreGlobals); 00107 00108 // Merge the globals variables (not the calls) from the globals graph back 00109 // into the main function's graph so that the main function contains all of 00110 // the information about global pools and GV usage in the program. 00111 if (MainFunc && !MainFunc->isExternal()) { 00112 DSGraph &MainGraph = getOrCreateGraph(*MainFunc); 00113 const DSGraph &GG = *MainGraph.getGlobalsGraph(); 00114 ReachabilityCloner RC(MainGraph, GG, 00115 DSGraph::DontCloneCallNodes | 00116 DSGraph::DontCloneAuxCallNodes); 00117 00118 // Clone the global nodes into this graph. 00119 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), 00120 E = GG.getScalarMap().global_end(); I != E; ++I) 00121 if (isa<GlobalVariable>(*I)) 00122 RC.getClonedNH(GG.getNodeForValue(*I)); 00123 00124 MainGraph.maskIncompleteMarkers(); 00125 MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | 00126 DSGraph::IgnoreGlobals); 00127 } 00128 00129 // Final processing. Note that dead node elimination may actually remove 00130 // globals from a function graph that are immediately used. If there are no 00131 // scalars pointing to the node (e.g. because the only use is a direct store 00132 // to a scalar global) we have to make sure to rematerialize the globals back 00133 // into the graphs here, or clients will break! 00134 for (Module::global_iterator GI = M.global_begin(), E = M.global_end(); 00135 GI != E; ++GI) 00136 // This only happens to first class typed globals. 00137 if (GI->getType()->getElementType()->isFirstClassType()) 00138 for (Value::use_iterator UI = GI->use_begin(), E = GI->use_end(); 00139 UI != E; ++UI) 00140 // This only happens to direct uses by instructions. 00141 if (Instruction *User = dyn_cast<Instruction>(*UI)) { 00142 DSGraph &DSG = getOrCreateGraph(*User->getParent()->getParent()); 00143 if (!DSG.getScalarMap().count(GI)) { 00144 // If this global does not exist in the graph, but it is immediately 00145 // used by an instruction in the graph, clone it over from the 00146 // globals graph. 00147 ReachabilityCloner RC(DSG, *GlobalsGraph, 0); 00148 RC.getClonedNH(GlobalsGraph->getNodeForValue(GI)); 00149 } 00150 } 00151 00152 return false; 00153 } 00154 00155 00156 // buildIndirectFunctionSets - Iterate over the module looking for indirect 00157 // calls to functions. If a call site can invoke any functions [F1, F2... FN], 00158 // unify the N functions together in the FuncECs set. 00159 // 00160 void EquivClassGraphs::buildIndirectFunctionSets(Module &M) { 00161 const ActualCalleesTy& AC = CBU->getActualCallees(); 00162 00163 // Loop over all of the indirect calls in the program. If a call site can 00164 // call multiple different functions, we need to unify all of the callees into 00165 // the same equivalence class. 00166 Instruction *LastInst = 0; 00167 Function *FirstFunc = 0; 00168 for (ActualCalleesTy::const_iterator I=AC.begin(), E=AC.end(); I != E; ++I) { 00169 if (I->second->isExternal()) 00170 continue; // Ignore functions we cannot modify 00171 00172 CallSite CS = CallSite::get(I->first); 00173 00174 if (CS.getCalledFunction()) { // Direct call: 00175 FuncECs.insert(I->second); // -- Make sure function has equiv class 00176 FirstFunc = I->second; // -- First callee at this site 00177 } else { // Else indirect call 00178 // DEBUG(std::cerr << "CALLEE: " << I->second->getName() 00179 // << " from : " << I->first); 00180 if (I->first != LastInst) { 00181 // This is the first callee from this call site. 00182 LastInst = I->first; 00183 FirstFunc = I->second; 00184 // Instead of storing the lastInst For Indirection call Sites we store 00185 // the DSNode for the function ptr arguemnt 00186 Function *thisFunc = LastInst->getParent()->getParent(); 00187 DSGraph &TFG = CBU->getDSGraph(*thisFunc); 00188 DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode(); 00189 OneCalledFunction[calleeNode] = FirstFunc; 00190 FuncECs.insert(I->second); 00191 } else { 00192 // This is not the first possible callee from a particular call site. 00193 // Union the callee in with the other functions. 00194 FuncECs.unionSets(FirstFunc, I->second); 00195 #ifndef NDEBUG 00196 Function *thisFunc = LastInst->getParent()->getParent(); 00197 DSGraph &TFG = CBU->getDSGraph(*thisFunc); 00198 DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode(); 00199 assert(OneCalledFunction.count(calleeNode) > 0 && "Missed a call?"); 00200 #endif 00201 } 00202 } 00203 00204 // Now include all functions that share a graph with any function in the 00205 // equivalence class. More precisely, if F is in the class, and G(F) is 00206 // its graph, then we include all other functions that are also in G(F). 00207 // Currently, that is just the functions in the same call-graph-SCC as F. 00208 // 00209 DSGraph& funcDSGraph = CBU->getDSGraph(*I->second); 00210 for (DSGraph::retnodes_iterator RI = funcDSGraph.retnodes_begin(), 00211 RE = funcDSGraph.retnodes_end(); RI != RE; ++RI) 00212 FuncECs.unionSets(FirstFunc, RI->first); 00213 } 00214 00215 // Now that all of the equivalences have been built, merge the graphs for 00216 // each equivalence class. 00217 // 00218 DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n"); 00219 for (EquivalenceClasses<Function*>::iterator EQSI = FuncECs.begin(), E = 00220 FuncECs.end(); EQSI != E; ++EQSI) { 00221 if (!EQSI->isLeader()) continue; 00222 00223 EquivalenceClasses<Function*>::member_iterator SI = 00224 FuncECs.member_begin(EQSI); 00225 assert(SI != FuncECs.member_end() && "Empty equiv set??"); 00226 EquivalenceClasses<Function*>::member_iterator SN = SI; 00227 ++SN; 00228 if (SN == FuncECs.member_end()) 00229 continue; // Single function equivalence set, no merging to do. 00230 00231 Function* LF = *SI; 00232 00233 #ifndef NDEBUG 00234 DEBUG(std::cerr <<" Equivalence set for leader " << LF->getName() <<" = "); 00235 for (SN = SI; SN != FuncECs.member_end(); ++SN) 00236 DEBUG(std::cerr << " " << (*SN)->getName() << "," ); 00237 DEBUG(std::cerr << "\n"); 00238 #endif 00239 00240 // This equiv class has multiple functions: merge their graphs. First, 00241 // clone the CBU graph for the leader and make it the common graph for the 00242 // equivalence graph. 00243 DSGraph &MergedG = getOrCreateGraph(*LF); 00244 00245 // Record the argument nodes for use in merging later below. 00246 std::vector<DSNodeHandle> ArgNodes; 00247 00248 for (Function::arg_iterator AI = LF->arg_begin(), E = LF->arg_end(); 00249 AI != E; ++AI) 00250 if (DS::isPointerType(AI->getType())) 00251 ArgNodes.push_back(MergedG.getNodeForValue(AI)); 00252 00253 // Merge in the graphs of all other functions in this equiv. class. Note 00254 // that two or more functions may have the same graph, and it only needs 00255 // to be merged in once. 00256 std::set<DSGraph*> GraphsMerged; 00257 GraphsMerged.insert(&CBU->getDSGraph(*LF)); 00258 00259 for (++SI; SI != FuncECs.member_end(); ++SI) { 00260 Function *F = *SI; 00261 DSGraph *&FG = DSInfo[F]; 00262 00263 DSGraph &CBUGraph = CBU->getDSGraph(*F); 00264 if (GraphsMerged.insert(&CBUGraph).second) { 00265 // Record the "folded" graph for the function. 00266 for (DSGraph::retnodes_iterator I = CBUGraph.retnodes_begin(), 00267 E = CBUGraph.retnodes_end(); I != E; ++I) { 00268 assert(DSInfo[I->first] == 0 && "Graph already exists for Fn!"); 00269 DSInfo[I->first] = &MergedG; 00270 } 00271 00272 // Clone this member of the equivalence class into MergedG. 00273 MergedG.cloneInto(CBUGraph); 00274 } 00275 00276 // Merge the return nodes of all functions together. 00277 MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]); 00278 00279 // Merge the function arguments with all argument nodes found so far. 00280 // If there are extra function args, add them to the vector of argNodes 00281 Function::arg_iterator AI2 = F->arg_begin(), AI2end = F->arg_end(); 00282 for (unsigned arg = 0, numArgs = ArgNodes.size(); 00283 arg != numArgs && AI2 != AI2end; ++AI2, ++arg) 00284 if (DS::isPointerType(AI2->getType())) 00285 ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2)); 00286 00287 for ( ; AI2 != AI2end; ++AI2) 00288 if (DS::isPointerType(AI2->getType())) 00289 ArgNodes.push_back(MergedG.getNodeForValue(AI2)); 00290 DEBUG(MergedG.AssertGraphOK()); 00291 } 00292 } 00293 DEBUG(std::cerr << "\n"); 00294 } 00295 00296 00297 DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) { 00298 // Has the graph already been created? 00299 DSGraph *&Graph = DSInfo[&F]; 00300 if (Graph) return *Graph; 00301 00302 DSGraph &CBUGraph = CBU->getDSGraph(F); 00303 00304 // Copy the CBU graph... 00305 Graph = new DSGraph(CBUGraph, GlobalECs); // updates the map via reference 00306 Graph->setGlobalsGraph(&getGlobalsGraph()); 00307 Graph->setPrintAuxCalls(); 00308 00309 // Make sure to update the DSInfo map for all functions in the graph! 00310 for (DSGraph::retnodes_iterator I = Graph->retnodes_begin(); 00311 I != Graph->retnodes_end(); ++I) 00312 if (I->first != &F) { 00313 DSGraph *&FG = DSInfo[I->first]; 00314 assert(FG == 0 && "Merging function in SCC twice?"); 00315 FG = Graph; 00316 } 00317 00318 return *Graph; 00319 } 00320 00321 00322 unsigned EquivClassGraphs:: 00323 processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID, 00324 std::map<DSGraph*, unsigned> &ValMap) { 00325 std::map<DSGraph*, unsigned>::iterator It = ValMap.lower_bound(&FG); 00326 if (It != ValMap.end() && It->first == &FG) 00327 return It->second; 00328 00329 DEBUG(std::cerr << " ProcessSCC for function " << FG.getFunctionNames() 00330 << "\n"); 00331 00332 unsigned Min = NextID++, MyID = Min; 00333 ValMap[&FG] = Min; 00334 Stack.push_back(&FG); 00335 00336 // The edges out of the current node are the call site targets... 00337 for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end(); 00338 CI != CE; ++CI) { 00339 Instruction *Call = CI->getCallSite().getInstruction(); 00340 00341 // Loop over all of the actually called functions... 00342 for (callee_iterator I = callee_begin(Call), E = callee_end(Call); 00343 I != E; ++I) 00344 if (!I->second->isExternal()) { 00345 // Process the callee as necessary. 00346 unsigned M = processSCC(getOrCreateGraph(*I->second), 00347 Stack, NextID, ValMap); 00348 if (M < Min) Min = M; 00349 } 00350 } 00351 00352 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); 00353 if (Min != MyID) 00354 return Min; // This is part of a larger SCC! 00355 00356 // If this is a new SCC, process it now. 00357 bool MergedGraphs = false; 00358 while (Stack.back() != &FG) { 00359 DSGraph *NG = Stack.back(); 00360 ValMap[NG] = ~0U; 00361 00362 // If the SCC found is not the same as those found in CBU, make sure to 00363 // merge the graphs as appropriate. 00364 FG.cloneInto(*NG); 00365 00366 // Update the DSInfo map and delete the old graph... 00367 for (DSGraph::retnodes_iterator I = NG->retnodes_begin(); 00368 I != NG->retnodes_end(); ++I) 00369 DSInfo[I->first] = &FG; 00370 00371 // Remove NG from the ValMap since the pointer may get recycled. 00372 ValMap.erase(NG); 00373 delete NG; 00374 MergedGraphs = true; 00375 Stack.pop_back(); 00376 } 00377 00378 // Clean up the graph before we start inlining a bunch again. 00379 if (MergedGraphs) 00380 FG.removeTriviallyDeadNodes(); 00381 00382 Stack.pop_back(); 00383 00384 processGraph(FG); 00385 ValMap[&FG] = ~0U; 00386 return MyID; 00387 } 00388 00389 00390 /// processGraph - Process the CBU graphs for the program in bottom-up order on 00391 /// the SCC of the __ACTUAL__ call graph. This builds final folded CBU graphs. 00392 void EquivClassGraphs::processGraph(DSGraph &G) { 00393 DEBUG(std::cerr << " ProcessGraph for function " 00394 << G.getFunctionNames() << "\n"); 00395 00396 hash_set<Instruction*> calls; 00397 00398 // Else we need to inline some callee graph. Visit all call sites. 00399 // The edges out of the current node are the call site targets... 00400 unsigned i = 0; 00401 for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE; 00402 ++CI, ++i) { 00403 const DSCallSite &CS = *CI; 00404 Instruction *TheCall = CS.getCallSite().getInstruction(); 00405 00406 assert(calls.insert(TheCall).second && 00407 "Call instruction occurs multiple times in graph??"); 00408 00409 if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) 00410 continue; 00411 00412 // Inline the common callee graph into the current graph, if the callee 00413 // graph has not changed. Note that all callees should have the same 00414 // graph so we only need to do this once. 00415 // 00416 DSGraph* CalleeGraph = NULL; 00417 callee_iterator I = callee_begin(TheCall), E = callee_end(TheCall); 00418 unsigned TNum, Num; 00419 00420 // Loop over all potential callees to find the first non-external callee. 00421 for (TNum = 0, Num = std::distance(I, E); I != E; ++I, ++TNum) 00422 if (!I->second->isExternal()) 00423 break; 00424 00425 // Now check if the graph has changed and if so, clone and inline it. 00426 if (I != E) { 00427 Function *CalleeFunc = I->second; 00428 00429 // Merge the callee's graph into this graph, if not already the same. 00430 // Callees in the same equivalence class (which subsumes those 00431 // in the same SCCs) have the same graph. Note that all recursion 00432 // including self-recursion have been folded in the equiv classes. 00433 // 00434 CalleeGraph = &getOrCreateGraph(*CalleeFunc); 00435 if (CalleeGraph != &G) { 00436 ++NumFoldGraphInlines; 00437 G.mergeInGraph(CS, *CalleeFunc, *CalleeGraph, 00438 DSGraph::StripAllocaBit | 00439 DSGraph::DontCloneCallNodes | 00440 DSGraph::DontCloneAuxCallNodes); 00441 DEBUG(std::cerr << " Inlining graph [" << i << "/" 00442 << G.getFunctionCalls().size()-1 00443 << ":" << TNum << "/" << Num-1 << "] for " 00444 << CalleeFunc->getName() << "[" 00445 << CalleeGraph->getGraphSize() << "+" 00446 << CalleeGraph->getAuxFunctionCalls().size() 00447 << "] into '" /*<< G.getFunctionNames()*/ << "' [" 00448 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() 00449 << "]\n"); 00450 } 00451 } 00452 00453 #ifndef NDEBUG 00454 // Now loop over the rest of the callees and make sure they have the 00455 // same graph as the one inlined above. 00456 if (CalleeGraph) 00457 for (++I, ++TNum; I != E; ++I, ++TNum) 00458 if (!I->second->isExternal()) 00459 assert(CalleeGraph == &getOrCreateGraph(*I->second) && 00460 "Callees at a call site have different graphs?"); 00461 #endif 00462 } 00463 00464 // Recompute the Incomplete markers. 00465 G.maskIncompleteMarkers(); 00466 G.markIncompleteNodes(DSGraph::MarkFormalArgs); 00467 00468 // Delete dead nodes. Treat globals that are unreachable but that can 00469 // reach live nodes as live. 00470 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00471 00472 // When this graph is finalized, clone the globals in the graph into the 00473 // globals graph to make sure it has everything, from all graphs. 00474 ReachabilityCloner RC(*G.getGlobalsGraph(), G, DSGraph::StripAllocaBit); 00475 00476 // Clone everything reachable from globals in the function graph into the 00477 // globals graph. 00478 DSScalarMap &MainSM = G.getScalarMap(); 00479 for (DSScalarMap::global_iterator I = MainSM.global_begin(), 00480 E = MainSM.global_end(); I != E; ++I) 00481 RC.getClonedNH(MainSM[*I]); 00482 00483 DEBUG(std::cerr << " -- DONE ProcessGraph for function " 00484 << G.getFunctionNames() << "\n"); 00485 }