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