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/Analysis/DataStructure/DSGraph.h" 00019 #include "llvm/Module.h" 00020 #include "llvm/ADT/Statistic.h" 00021 #include "llvm/Support/Debug.h" 00022 #include "llvm/Support/Timer.h" 00023 #include <iostream> 00024 using namespace llvm; 00025 00026 namespace { 00027 Statistic<> MaxSCC("budatastructure", "Maximum SCC Size in Call Graph"); 00028 Statistic<> NumBUInlines("budatastructures", "Number of graphs inlined"); 00029 Statistic<> NumCallEdges("budatastructures", "Number of 'actual' call edges"); 00030 00031 RegisterAnalysis<BUDataStructures> 00032 X("budatastructure", "Bottom-up Data Structure Analysis"); 00033 } 00034 00035 /// BuildGlobalECs - Look at all of the nodes in the globals graph. If any node 00036 /// contains multiple globals, DSA will never, ever, be able to tell the globals 00037 /// apart. Instead of maintaining this information in all of the graphs 00038 /// throughout the entire program, store only a single global (the "leader") in 00039 /// the graphs, and build equivalence classes for the rest of the globals. 00040 static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) { 00041 DSScalarMap &SM = GG.getScalarMap(); 00042 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 00043 for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); 00044 I != E; ++I) { 00045 if (I->getGlobalsList().size() <= 1) continue; 00046 00047 // First, build up the equivalence set for this block of globals. 00048 const std::vector<GlobalValue*> &GVs = I->getGlobalsList(); 00049 GlobalValue *First = GVs[0]; 00050 for (unsigned i = 1, e = GVs.size(); i != e; ++i) 00051 GlobalECs.unionSets(First, GVs[i]); 00052 00053 // Next, get the leader element. 00054 assert(First == GlobalECs.getLeaderValue(First) && 00055 "First did not end up being the leader?"); 00056 00057 // Next, remove all globals from the scalar map that are not the leader. 00058 assert(GVs[0] == First && "First had to be at the front!"); 00059 for (unsigned i = 1, e = GVs.size(); i != e; ++i) { 00060 ECGlobals.insert(GVs[i]); 00061 SM.erase(SM.find(GVs[i])); 00062 } 00063 00064 // Finally, change the global node to only contain the leader. 00065 I->clearGlobals(); 00066 I->addGlobal(First); 00067 } 00068 00069 DEBUG(GG.AssertGraphOK()); 00070 } 00071 00072 /// EliminateUsesOfECGlobals - Once we have determined that some globals are in 00073 /// really just equivalent to some other globals, remove the globals from the 00074 /// specified DSGraph (if present), and merge any nodes with their leader nodes. 00075 static void EliminateUsesOfECGlobals(DSGraph &G, 00076 const std::set<GlobalValue*> &ECGlobals) { 00077 DSScalarMap &SM = G.getScalarMap(); 00078 EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); 00079 00080 bool MadeChange = false; 00081 for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); 00082 GI != E; ) { 00083 GlobalValue *GV = *GI++; 00084 if (!ECGlobals.count(GV)) continue; 00085 00086 const DSNodeHandle &GVNH = SM[GV]; 00087 assert(!GVNH.isNull() && "Global has null NH!?"); 00088 00089 // Okay, this global is in some equivalence class. Start by finding the 00090 // leader of the class. 00091 GlobalValue *Leader = GlobalECs.getLeaderValue(GV); 00092 00093 // If the leader isn't already in the graph, insert it into the node 00094 // corresponding to GV. 00095 if (!SM.global_count(Leader)) { 00096 GVNH.getNode()->addGlobal(Leader); 00097 SM[Leader] = GVNH; 00098 } else { 00099 // Otherwise, the leader is in the graph, make sure the nodes are the 00100 // merged in the specified graph. 00101 const DSNodeHandle &LNH = SM[Leader]; 00102 if (LNH.getNode() != GVNH.getNode()) 00103 LNH.mergeWith(GVNH); 00104 } 00105 00106 // Next step, remove the global from the DSNode. 00107 GVNH.getNode()->removeGlobal(GV); 00108 00109 // Finally, remove the global from the ScalarMap. 00110 SM.erase(GV); 00111 MadeChange = true; 00112 } 00113 00114 DEBUG(if(MadeChange) G.AssertGraphOK()); 00115 } 00116 00117 // run - Calculate the bottom up data structure graphs for each function in the 00118 // program. 00119 // 00120 bool BUDataStructures::runOnModule(Module &M) { 00121 LocalDataStructures &LocalDSA = getAnalysis<LocalDataStructures>(); 00122 GlobalECs = LocalDSA.getGlobalECs(); 00123 00124 GlobalsGraph = new DSGraph(LocalDSA.getGlobalsGraph(), GlobalECs); 00125 GlobalsGraph->setPrintAuxCalls(); 00126 00127 IndCallGraphMap = new std::map<std::vector<Function*>, 00128 std::pair<DSGraph*, std::vector<DSNodeHandle> > >(); 00129 00130 std::vector<Function*> Stack; 00131 hash_map<Function*, unsigned> ValMap; 00132 unsigned NextID = 1; 00133 00134 Function *MainFunc = M.getMainFunction(); 00135 if (MainFunc) 00136 calculateGraphs(MainFunc, Stack, NextID, ValMap); 00137 00138 // Calculate the graphs for any functions that are unreachable from main... 00139 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00140 if (!I->isExternal() && !DSInfo.count(I)) { 00141 #ifndef NDEBUG 00142 if (MainFunc) 00143 std::cerr << "*** Function unreachable from main: " 00144 << I->getName() << "\n"; 00145 #endif 00146 calculateGraphs(I, Stack, NextID, ValMap); // Calculate all graphs. 00147 } 00148 00149 NumCallEdges += ActualCallees.size(); 00150 00151 // If we computed any temporary indcallgraphs, free them now. 00152 for (std::map<std::vector<Function*>, 00153 std::pair<DSGraph*, std::vector<DSNodeHandle> > >::iterator I = 00154 IndCallGraphMap->begin(), E = IndCallGraphMap->end(); I != E; ++I) { 00155 I->second.second.clear(); // Drop arg refs into the graph. 00156 delete I->second.first; 00157 } 00158 delete IndCallGraphMap; 00159 00160 // At the end of the bottom-up pass, the globals graph becomes complete. 00161 // FIXME: This is not the right way to do this, but it is sorta better than 00162 // nothing! In particular, externally visible globals and unresolvable call 00163 // nodes at the end of the BU phase should make things that they point to 00164 // incomplete in the globals graph. 00165 // 00166 GlobalsGraph->removeTriviallyDeadNodes(); 00167 GlobalsGraph->maskIncompleteMarkers(); 00168 00169 // Mark external globals incomplete. 00170 GlobalsGraph->markIncompleteNodes(DSGraph::IgnoreGlobals); 00171 00172 // Grow the equivalence classes for the globals to include anything that we 00173 // now know to be aliased. 00174 std::set<GlobalValue*> ECGlobals; 00175 BuildGlobalECs(*GlobalsGraph, ECGlobals); 00176 if (!ECGlobals.empty()) { 00177 NamedRegionTimer X("Bottom-UP EC Cleanup"); 00178 std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; 00179 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 00180 E = DSInfo.end(); I != E; ++I) 00181 EliminateUsesOfECGlobals(*I->second, ECGlobals); 00182 } 00183 00184 // Merge the globals variables (not the calls) from the globals graph back 00185 // into the main function's graph so that the main function contains all of 00186 // the information about global pools and GV usage in the program. 00187 if (MainFunc && !MainFunc->isExternal()) { 00188 DSGraph &MainGraph = getOrCreateGraph(MainFunc); 00189 const DSGraph &GG = *MainGraph.getGlobalsGraph(); 00190 ReachabilityCloner RC(MainGraph, GG, 00191 DSGraph::DontCloneCallNodes | 00192 DSGraph::DontCloneAuxCallNodes); 00193 00194 // Clone the global nodes into this graph. 00195 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), 00196 E = GG.getScalarMap().global_end(); I != E; ++I) 00197 if (isa<GlobalVariable>(*I)) 00198 RC.getClonedNH(GG.getNodeForValue(*I)); 00199 00200 MainGraph.maskIncompleteMarkers(); 00201 MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | 00202 DSGraph::IgnoreGlobals); 00203 } 00204 00205 return false; 00206 } 00207 00208 DSGraph &BUDataStructures::getOrCreateGraph(Function *F) { 00209 // Has the graph already been created? 00210 DSGraph *&Graph = DSInfo[F]; 00211 if (Graph) return *Graph; 00212 00213 DSGraph &LocGraph = getAnalysis<LocalDataStructures>().getDSGraph(*F); 00214 00215 // Steal the local graph. 00216 Graph = new DSGraph(GlobalECs, LocGraph.getTargetData()); 00217 Graph->spliceFrom(LocGraph); 00218 00219 Graph->setGlobalsGraph(GlobalsGraph); 00220 Graph->setPrintAuxCalls(); 00221 00222 // Start with a copy of the original call sites... 00223 Graph->getAuxFunctionCalls() = Graph->getFunctionCalls(); 00224 return *Graph; 00225 } 00226 00227 static bool isVAHackFn(const Function *F) { 00228 return F->getName() == "printf" || F->getName() == "sscanf" || 00229 F->getName() == "fprintf" || F->getName() == "open" || 00230 F->getName() == "sprintf" || F->getName() == "fputs" || 00231 F->getName() == "fscanf" || F->getName() == "malloc" || 00232 F->getName() == "free"; 00233 } 00234 00235 static bool isResolvableFunc(const Function* callee) { 00236 return !callee->isExternal() || isVAHackFn(callee); 00237 } 00238 00239 static void GetAllCallees(const DSCallSite &CS, 00240 std::vector<Function*> &Callees) { 00241 if (CS.isDirectCall()) { 00242 if (isResolvableFunc(CS.getCalleeFunc())) 00243 Callees.push_back(CS.getCalleeFunc()); 00244 } else if (!CS.getCalleeNode()->isIncomplete()) { 00245 // Get all callees. 00246 unsigned OldSize = Callees.size(); 00247 CS.getCalleeNode()->addFullFunctionList(Callees); 00248 00249 // If any of the callees are unresolvable, remove the whole batch! 00250 for (unsigned i = OldSize, e = Callees.size(); i != e; ++i) 00251 if (!isResolvableFunc(Callees[i])) { 00252 Callees.erase(Callees.begin()+OldSize, Callees.end()); 00253 return; 00254 } 00255 } 00256 } 00257 00258 00259 /// GetAllAuxCallees - Return a list containing all of the resolvable callees in 00260 /// the aux list for the specified graph in the Callees vector. 00261 static void GetAllAuxCallees(DSGraph &G, std::vector<Function*> &Callees) { 00262 Callees.clear(); 00263 for (DSGraph::afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I) 00264 GetAllCallees(*I, Callees); 00265 } 00266 00267 unsigned BUDataStructures::calculateGraphs(Function *F, 00268 std::vector<Function*> &Stack, 00269 unsigned &NextID, 00270 hash_map<Function*, unsigned> &ValMap) { 00271 assert(!ValMap.count(F) && "Shouldn't revisit functions!"); 00272 unsigned Min = NextID++, MyID = Min; 00273 ValMap[F] = Min; 00274 Stack.push_back(F); 00275 00276 // FIXME! This test should be generalized to be any function that we have 00277 // already processed, in the case when there isn't a main or there are 00278 // unreachable functions! 00279 if (F->isExternal()) { // sprintf, fprintf, sscanf, etc... 00280 // No callees! 00281 Stack.pop_back(); 00282 ValMap[F] = ~0; 00283 return Min; 00284 } 00285 00286 DSGraph &Graph = getOrCreateGraph(F); 00287 00288 // Find all callee functions. 00289 std::vector<Function*> CalleeFunctions; 00290 GetAllAuxCallees(Graph, CalleeFunctions); 00291 00292 // The edges out of the current node are the call site targets... 00293 for (unsigned i = 0, e = CalleeFunctions.size(); i != e; ++i) { 00294 Function *Callee = CalleeFunctions[i]; 00295 unsigned M; 00296 // Have we visited the destination function yet? 00297 hash_map<Function*, unsigned>::iterator It = ValMap.find(Callee); 00298 if (It == ValMap.end()) // No, visit it now. 00299 M = calculateGraphs(Callee, Stack, NextID, ValMap); 00300 else // Yes, get it's number. 00301 M = It->second; 00302 if (M < Min) Min = M; 00303 } 00304 00305 assert(ValMap[F] == MyID && "SCC construction assumption wrong!"); 00306 if (Min != MyID) 00307 return Min; // This is part of a larger SCC! 00308 00309 // If this is a new SCC, process it now. 00310 if (Stack.back() == F) { // Special case the single "SCC" case here. 00311 DEBUG(std::cerr << "Visiting single node SCC #: " << MyID << " fn: " 00312 << F->getName() << "\n"); 00313 Stack.pop_back(); 00314 DSGraph &G = getDSGraph(*F); 00315 DEBUG(std::cerr << " [BU] Calculating graph for: " << F->getName()<< "\n"); 00316 calculateGraph(G); 00317 DEBUG(std::cerr << " [BU] Done inlining: " << F->getName() << " [" 00318 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() 00319 << "]\n"); 00320 00321 if (MaxSCC < 1) MaxSCC = 1; 00322 00323 // Should we revisit the graph? Only do it if there are now new resolvable 00324 // callees. 00325 GetAllAuxCallees(Graph, CalleeFunctions); 00326 if (!CalleeFunctions.empty()) { 00327 ValMap.erase(F); 00328 return calculateGraphs(F, Stack, NextID, ValMap); 00329 } else { 00330 ValMap[F] = ~0U; 00331 } 00332 return MyID; 00333 00334 } else { 00335 // SCCFunctions - Keep track of the functions in the current SCC 00336 // 00337 std::vector<DSGraph*> SCCGraphs; 00338 00339 unsigned SCCSize = 1; 00340 Function *NF = Stack.back(); 00341 ValMap[NF] = ~0U; 00342 DSGraph &SCCGraph = getDSGraph(*NF); 00343 00344 // First thing first, collapse all of the DSGraphs into a single graph for 00345 // the entire SCC. Splice all of the graphs into one and discard all of the 00346 // old graphs. 00347 // 00348 while (NF != F) { 00349 Stack.pop_back(); 00350 NF = Stack.back(); 00351 ValMap[NF] = ~0U; 00352 00353 DSGraph &NFG = getDSGraph(*NF); 00354 00355 // Update the Function -> DSG map. 00356 for (DSGraph::retnodes_iterator I = NFG.retnodes_begin(), 00357 E = NFG.retnodes_end(); I != E; ++I) 00358 DSInfo[I->first] = &SCCGraph; 00359 00360 SCCGraph.spliceFrom(NFG); 00361 delete &NFG; 00362 00363 ++SCCSize; 00364 } 00365 Stack.pop_back(); 00366 00367 std::cerr << "Calculating graph for SCC #: " << MyID << " of size: " 00368 << SCCSize << "\n"; 00369 00370 // Compute the Max SCC Size. 00371 if (MaxSCC < SCCSize) 00372 MaxSCC = SCCSize; 00373 00374 // Clean up the graph before we start inlining a bunch again... 00375 SCCGraph.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00376 00377 // Now that we have one big happy family, resolve all of the call sites in 00378 // the graph... 00379 calculateGraph(SCCGraph); 00380 DEBUG(std::cerr << " [BU] Done inlining SCC [" << SCCGraph.getGraphSize() 00381 << "+" << SCCGraph.getAuxFunctionCalls().size() << "]\n"); 00382 00383 std::cerr << "DONE with SCC #: " << MyID << "\n"; 00384 00385 // We never have to revisit "SCC" processed functions... 00386 return MyID; 00387 } 00388 00389 return MyID; // == Min 00390 } 00391 00392 00393 // releaseMemory - If the pass pipeline is done with this pass, we can release 00394 // our memory... here... 00395 // 00396 void BUDataStructures::releaseMyMemory() { 00397 for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), 00398 E = DSInfo.end(); I != E; ++I) { 00399 I->second->getReturnNodes().erase(I->first); 00400 if (I->second->getReturnNodes().empty()) 00401 delete I->second; 00402 } 00403 00404 // Empty map so next time memory is released, data structures are not 00405 // re-deleted. 00406 DSInfo.clear(); 00407 delete GlobalsGraph; 00408 GlobalsGraph = 0; 00409 } 00410 00411 DSGraph &BUDataStructures::CreateGraphForExternalFunction(const Function &Fn) { 00412 Function *F = const_cast<Function*>(&Fn); 00413 DSGraph *DSG = new DSGraph(GlobalECs, GlobalsGraph->getTargetData()); 00414 DSInfo[F] = DSG; 00415 DSG->setGlobalsGraph(GlobalsGraph); 00416 DSG->setPrintAuxCalls(); 00417 00418 // Add function to the graph. 00419 DSG->getReturnNodes().insert(std::make_pair(F, DSNodeHandle())); 00420 00421 if (F->getName() == "free") { // Taking the address of free. 00422 00423 // Free should take a single pointer argument, mark it as heap memory. 00424 DSNode *N = new DSNode(0, DSG); 00425 N->setHeapNodeMarker(); 00426 DSG->getNodeForValue(F->arg_begin()).mergeWith(N); 00427 00428 } else { 00429 std::cerr << "Unrecognized external function: " << F->getName() << "\n"; 00430 abort(); 00431 } 00432 00433 return *DSG; 00434 } 00435 00436 00437 void BUDataStructures::calculateGraph(DSGraph &Graph) { 00438 // If this graph contains the main function, clone the globals graph into this 00439 // graph before we inline callees and other fun stuff. 00440 bool ContainsMain = false; 00441 DSGraph::ReturnNodesTy &ReturnNodes = Graph.getReturnNodes(); 00442 00443 for (DSGraph::ReturnNodesTy::iterator I = ReturnNodes.begin(), 00444 E = ReturnNodes.end(); I != E; ++I) 00445 if (I->first->hasExternalLinkage() && I->first->getName() == "main") { 00446 ContainsMain = true; 00447 break; 00448 } 00449 00450 // If this graph contains main, copy the contents of the globals graph over. 00451 // Note that this is *required* for correctness. If a callee contains a use 00452 // of a global, we have to make sure to link up nodes due to global-argument 00453 // bindings. 00454 if (ContainsMain) { 00455 const DSGraph &GG = *Graph.getGlobalsGraph(); 00456 ReachabilityCloner RC(Graph, GG, 00457 DSGraph::DontCloneCallNodes | 00458 DSGraph::DontCloneAuxCallNodes); 00459 00460 // Clone the global nodes into this graph. 00461 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), 00462 E = GG.getScalarMap().global_end(); I != E; ++I) 00463 if (isa<GlobalVariable>(*I)) 00464 RC.getClonedNH(GG.getNodeForValue(*I)); 00465 } 00466 00467 00468 // Move our call site list into TempFCs so that inline call sites go into the 00469 // new call site list and doesn't invalidate our iterators! 00470 std::list<DSCallSite> TempFCs; 00471 std::list<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls(); 00472 TempFCs.swap(AuxCallsList); 00473 00474 bool Printed = false; 00475 std::vector<Function*> CalledFuncs; 00476 while (!TempFCs.empty()) { 00477 DSCallSite &CS = *TempFCs.begin(); 00478 00479 CalledFuncs.clear(); 00480 00481 // Fast path for noop calls. Note that we don't care about merging globals 00482 // in the callee with nodes in the caller here. 00483 if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) { 00484 TempFCs.erase(TempFCs.begin()); 00485 continue; 00486 } else if (CS.isDirectCall() && isVAHackFn(CS.getCalleeFunc())) { 00487 TempFCs.erase(TempFCs.begin()); 00488 continue; 00489 } 00490 00491 GetAllCallees(CS, CalledFuncs); 00492 00493 if (CalledFuncs.empty()) { 00494 // Remember that we could not resolve this yet! 00495 AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin()); 00496 continue; 00497 } else { 00498 DSGraph *GI; 00499 Instruction *TheCall = CS.getCallSite().getInstruction(); 00500 00501 if (CalledFuncs.size() == 1) { 00502 Function *Callee = CalledFuncs[0]; 00503 ActualCallees.insert(std::make_pair(TheCall, Callee)); 00504 00505 // Get the data structure graph for the called function. 00506 GI = &getDSGraph(*Callee); // Graph to inline 00507 DEBUG(std::cerr << " Inlining graph for " << Callee->getName()); 00508 00509 DEBUG(std::cerr << "[" << GI->getGraphSize() << "+" 00510 << GI->getAuxFunctionCalls().size() << "] into '" 00511 << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+" 00512 << Graph.getAuxFunctionCalls().size() << "]\n"); 00513 Graph.mergeInGraph(CS, *Callee, *GI, 00514 DSGraph::StripAllocaBit|DSGraph::DontCloneCallNodes); 00515 ++NumBUInlines; 00516 } else { 00517 if (!Printed) 00518 std::cerr << "In Fns: " << Graph.getFunctionNames() << "\n"; 00519 std::cerr << " calls " << CalledFuncs.size() 00520 << " fns from site: " << CS.getCallSite().getInstruction() 00521 << " " << *CS.getCallSite().getInstruction(); 00522 std::cerr << " Fns ="; 00523 unsigned NumPrinted = 0; 00524 00525 for (std::vector<Function*>::iterator I = CalledFuncs.begin(), 00526 E = CalledFuncs.end(); I != E; ++I) { 00527 if (NumPrinted++ < 8) std::cerr << " " << (*I)->getName(); 00528 00529 // Add the call edges to the call graph. 00530 ActualCallees.insert(std::make_pair(TheCall, *I)); 00531 } 00532 std::cerr << "\n"; 00533 00534 // See if we already computed a graph for this set of callees. 00535 std::sort(CalledFuncs.begin(), CalledFuncs.end()); 00536 std::pair<DSGraph*, std::vector<DSNodeHandle> > &IndCallGraph = 00537 (*IndCallGraphMap)[CalledFuncs]; 00538 00539 if (IndCallGraph.first == 0) { 00540 std::vector<Function*>::iterator I = CalledFuncs.begin(), 00541 E = CalledFuncs.end(); 00542 00543 // Start with a copy of the first graph. 00544 GI = IndCallGraph.first = new DSGraph(getDSGraph(**I), GlobalECs); 00545 GI->setGlobalsGraph(Graph.getGlobalsGraph()); 00546 std::vector<DSNodeHandle> &Args = IndCallGraph.second; 00547 00548 // Get the argument nodes for the first callee. The return value is 00549 // the 0th index in the vector. 00550 GI->getFunctionArgumentsForCall(*I, Args); 00551 00552 // Merge all of the other callees into this graph. 00553 for (++I; I != E; ++I) { 00554 // If the graph already contains the nodes for the function, don't 00555 // bother merging it in again. 00556 if (!GI->containsFunction(*I)) { 00557 GI->cloneInto(getDSGraph(**I)); 00558 ++NumBUInlines; 00559 } 00560 00561 std::vector<DSNodeHandle> NextArgs; 00562 GI->getFunctionArgumentsForCall(*I, NextArgs); 00563 unsigned i = 0, e = Args.size(); 00564 for (; i != e; ++i) { 00565 if (i == NextArgs.size()) break; 00566 Args[i].mergeWith(NextArgs[i]); 00567 } 00568 for (e = NextArgs.size(); i != e; ++i) 00569 Args.push_back(NextArgs[i]); 00570 } 00571 00572 // Clean up the final graph! 00573 GI->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00574 } else { 00575 std::cerr << "***\n*** RECYCLED GRAPH ***\n***\n"; 00576 } 00577 00578 GI = IndCallGraph.first; 00579 00580 // Merge the unified graph into this graph now. 00581 DEBUG(std::cerr << " Inlining multi callee graph " 00582 << "[" << GI->getGraphSize() << "+" 00583 << GI->getAuxFunctionCalls().size() << "] into '" 00584 << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+" 00585 << Graph.getAuxFunctionCalls().size() << "]\n"); 00586 00587 Graph.mergeInGraph(CS, IndCallGraph.second, *GI, 00588 DSGraph::StripAllocaBit | 00589 DSGraph::DontCloneCallNodes); 00590 ++NumBUInlines; 00591 } 00592 } 00593 TempFCs.erase(TempFCs.begin()); 00594 } 00595 00596 // Recompute the Incomplete markers 00597 Graph.maskIncompleteMarkers(); 00598 Graph.markIncompleteNodes(DSGraph::MarkFormalArgs); 00599 00600 // Delete dead nodes. Treat globals that are unreachable but that can 00601 // reach live nodes as live. 00602 Graph.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00603 00604 // When this graph is finalized, clone the globals in the graph into the 00605 // globals graph to make sure it has everything, from all graphs. 00606 DSScalarMap &MainSM = Graph.getScalarMap(); 00607 ReachabilityCloner RC(*GlobalsGraph, Graph, DSGraph::StripAllocaBit); 00608 00609 // Clone everything reachable from globals in the function graph into the 00610 // globals graph. 00611 for (DSScalarMap::global_iterator I = MainSM.global_begin(), 00612 E = MainSM.global_end(); I != E; ++I) 00613 RC.getClonedNH(MainSM[*I]); 00614 00615 //Graph.writeGraphToFile(std::cerr, "bu_" + F.getName()); 00616 } 00617 00618 static const Function *getFnForValue(const Value *V) { 00619 if (const Instruction *I = dyn_cast<Instruction>(V)) 00620 return I->getParent()->getParent(); 00621 else if (const Argument *A = dyn_cast<Argument>(V)) 00622 return A->getParent(); 00623 else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V)) 00624 return BB->getParent(); 00625 return 0; 00626 } 00627 00628 /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program. 00629 /// These correspond to the interfaces defined in the AliasAnalysis class. 00630 void BUDataStructures::deleteValue(Value *V) { 00631 if (const Function *F = getFnForValue(V)) { // Function local value? 00632 // If this is a function local value, just delete it from the scalar map! 00633 getDSGraph(*F).getScalarMap().eraseIfExists(V); 00634 return; 00635 } 00636 00637 if (Function *F = dyn_cast<Function>(V)) { 00638 assert(getDSGraph(*F).getReturnNodes().size() == 1 && 00639 "cannot handle scc's"); 00640 delete DSInfo[F]; 00641 DSInfo.erase(F); 00642 return; 00643 } 00644 00645 assert(!isa<GlobalVariable>(V) && "Do not know how to delete GV's yet!"); 00646 } 00647 00648 void BUDataStructures::copyValue(Value *From, Value *To) { 00649 if (From == To) return; 00650 if (const Function *F = getFnForValue(From)) { // Function local value? 00651 // If this is a function local value, just delete it from the scalar map! 00652 getDSGraph(*F).getScalarMap().copyScalarIfExists(From, To); 00653 return; 00654 } 00655 00656 if (Function *FromF = dyn_cast<Function>(From)) { 00657 Function *ToF = cast<Function>(To); 00658 assert(!DSInfo.count(ToF) && "New Function already exists!"); 00659 DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs); 00660 DSInfo[ToF] = NG; 00661 assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!"); 00662 00663 // Change the Function* is the returnnodes map to the ToF. 00664 DSNodeHandle Ret = NG->retnodes_begin()->second; 00665 NG->getReturnNodes().clear(); 00666 NG->getReturnNodes()[ToF] = Ret; 00667 return; 00668 } 00669 00670 if (const Function *F = getFnForValue(To)) { 00671 DSGraph &G = getDSGraph(*F); 00672 G.getScalarMap().copyScalarIfExists(From, To); 00673 return; 00674 } 00675 00676 std::cerr << *From; 00677 std::cerr << *To; 00678 assert(0 && "Do not know how to copy this yet!"); 00679 abort(); 00680 }