LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

CompleteBottomUp.cpp

Go to the documentation of this file.
00001 //===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===//
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 is the exact same as the bottom-up graphs, but we use take a completed
00011 // call graph and inline all indirect callees into their callers graphs, making
00012 // the result more useful for things like pool allocation.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Analysis/DataStructure/DataStructure.h"
00017 #include "llvm/Module.h"
00018 #include "llvm/Analysis/DataStructure/DSGraph.h"
00019 #include "llvm/Support/Debug.h"
00020 #include "llvm/ADT/SCCIterator.h"
00021 #include "llvm/ADT/Statistic.h"
00022 #include "llvm/ADT/STLExtras.h"
00023 using namespace llvm;
00024 
00025 namespace {
00026   RegisterAnalysis<CompleteBUDataStructures>
00027   X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
00028   Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined");
00029 }
00030 
00031 
00032 // run - Calculate the bottom up data structure graphs for each function in the
00033 // program.
00034 //
00035 bool CompleteBUDataStructures::runOnModule(Module &M) {
00036   BUDataStructures &BU = getAnalysis<BUDataStructures>();
00037   GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
00038   GlobalsGraph->setPrintAuxCalls();
00039 
00040 #if 1   // REMOVE ME EVENTUALLY
00041   // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
00042   // globals graph has been implemented in the BU pass)
00043   TDDataStructures &TD = getAnalysis<TDDataStructures>();
00044 
00045   ActualCallees.clear();
00046 
00047   // The call graph extractable from the TD pass is _much more complete_ and
00048   // trustable than that generated by the BU pass so far.  Until this is fixed,
00049   // we hack it like this:
00050   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
00051     if (MI->isExternal()) continue;
00052     const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
00053 
00054     for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
00055       Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
00056 
00057       if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees
00058         const std::vector<GlobalValue*> &Callees =
00059           CSs[CSi].getCalleeNode()->getGlobals();
00060         for (unsigned i = 0, e = Callees.size(); i != e; ++i)
00061           if (Function *F = dyn_cast<Function>(Callees[i]))
00062             ActualCallees.insert(std::make_pair(TheCall, F));
00063       } else {        // direct call: insert the single callee directly
00064         ActualCallees.insert(std::make_pair(TheCall,
00065                                             CSs[CSi].getCalleeFunc()));
00066       }
00067     }
00068   }
00069 #else
00070   // Our call graph is the same as the BU data structures call graph
00071   ActualCallees = BU.getActualCallees();
00072 #endif
00073 
00074   std::vector<DSGraph*> Stack;
00075   hash_map<DSGraph*, unsigned> ValMap;
00076   unsigned NextID = 1;
00077 
00078   if (Function *Main = M.getMainFunction()) {
00079     if (!Main->isExternal())
00080       calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
00081   } else {
00082     std::cerr << "CBU-DSA: No 'main' function found!\n";
00083   }
00084   
00085   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00086     if (!I->isExternal() && !DSInfo.count(I))
00087       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
00088 
00089   GlobalsGraph->removeTriviallyDeadNodes();
00090   return false;
00091 }
00092 
00093 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
00094   // Has the graph already been created?
00095   DSGraph *&Graph = DSInfo[&F];
00096   if (Graph) return *Graph;
00097 
00098   // Copy the BU graph...
00099   Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
00100   Graph->setGlobalsGraph(GlobalsGraph);
00101   Graph->setPrintAuxCalls();
00102 
00103   // Make sure to update the DSInfo map for all of the functions currently in
00104   // this graph!
00105   for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
00106        I != Graph->getReturnNodes().end(); ++I)
00107     DSInfo[I->first] = Graph;
00108 
00109   return *Graph;
00110 }
00111 
00112 
00113 
00114 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
00115                                                   std::vector<DSGraph*> &Stack,
00116                                                   unsigned &NextID, 
00117                                          hash_map<DSGraph*, unsigned> &ValMap) {
00118   assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
00119   unsigned Min = NextID++, MyID = Min;
00120   ValMap[&FG] = Min;
00121   Stack.push_back(&FG);
00122 
00123   // The edges out of the current node are the call site targets...
00124   for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
00125     Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
00126 
00127     // Loop over all of the actually called functions...
00128     ActualCalleesTy::iterator I, E;
00129     for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
00130       if (!I->second->isExternal()) {
00131         DSGraph &Callee = getOrCreateGraph(*I->second);
00132         unsigned M;
00133         // Have we visited the destination function yet?
00134         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
00135         if (It == ValMap.end())  // No, visit it now.
00136           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
00137         else                    // Yes, get it's number.
00138           M = It->second;
00139         if (M < Min) Min = M;
00140       }
00141   }
00142 
00143   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
00144   if (Min != MyID)
00145     return Min;         // This is part of a larger SCC!
00146 
00147   // If this is a new SCC, process it now.
00148   bool IsMultiNodeSCC = false;
00149   while (Stack.back() != &FG) {
00150     DSGraph *NG = Stack.back();
00151     ValMap[NG] = ~0U;
00152 
00153     DSGraph::NodeMapTy NodeMap;
00154     FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
00155 
00156     // Update the DSInfo map and delete the old graph...
00157     for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
00158          I != NG->getReturnNodes().end(); ++I)
00159       DSInfo[I->first] = &FG;
00160 
00161     // Remove NG from the ValMap since the pointer may get recycled.
00162     ValMap.erase(NG);
00163     delete NG;
00164     
00165     Stack.pop_back();
00166     IsMultiNodeSCC = true;
00167   }
00168 
00169   // Clean up the graph before we start inlining a bunch again...
00170   if (IsMultiNodeSCC)
00171     FG.removeTriviallyDeadNodes();
00172   
00173   Stack.pop_back();
00174   processGraph(FG);
00175   ValMap[&FG] = ~0U;
00176   return MyID;
00177 }
00178 
00179 
00180 /// processGraph - Process the BU graphs for the program in bottom-up order on
00181 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
00182 void CompleteBUDataStructures::processGraph(DSGraph &G) {
00183   hash_set<Instruction*> calls;
00184 
00185   // The edges out of the current node are the call site targets...
00186   for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
00187     const DSCallSite &CS = G.getFunctionCalls()[i];
00188     Instruction *TheCall = CS.getCallSite().getInstruction();
00189 
00190     assert(calls.insert(TheCall).second &&
00191            "Call instruction occurs multiple times in graph??");
00192       
00193 
00194     // Loop over all of the potentially called functions...
00195     // Inline direct calls as well as indirect calls because the direct
00196     // callee may have indirect callees and so may have changed.
00197     // 
00198     ActualCalleesTy::iterator I, E;
00199     tie(I, E) = ActualCallees.equal_range(TheCall);
00200     unsigned TNum = 0, Num = std::distance(I, E);
00201     for (; I != E; ++I, ++TNum) {
00202       Function *CalleeFunc = I->second;
00203       if (!CalleeFunc->isExternal()) {
00204         // Merge the callee's graph into this graph.  This works for normal
00205         // calls or for self recursion within an SCC.
00206         DSGraph &GI = getOrCreateGraph(*CalleeFunc);
00207         ++NumCBUInlines;
00208         G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
00209                        DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
00210                        DSGraph::DontCloneAuxCallNodes);
00211         DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
00212               << ":" << TNum << "/" << Num-1 << "] for "
00213               << CalleeFunc->getName() << "["
00214               << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
00215               << "] into '" /*<< G.getFunctionNames()*/ << "' ["
00216               << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
00217               << "]\n");
00218       }
00219     }
00220   }
00221 
00222   // Recompute the Incomplete markers
00223   assert(G.getInlinedGlobals().empty());
00224   G.maskIncompleteMarkers();
00225   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
00226 
00227   // Delete dead nodes.  Treat globals that are unreachable but that can
00228   // reach live nodes as live.
00229   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
00230 }