LLVM API Documentation

BottomUpClosure.cpp

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