LLVM API Documentation

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 #define DEBUG_TYPE "cbudatastructure"
00017 #include "llvm/Analysis/DataStructure/DataStructure.h"
00018 #include "llvm/Module.h"
00019 #include "llvm/Analysis/DataStructure/DSGraph.h"
00020 #include "llvm/Support/Debug.h"
00021 #include "llvm/ADT/SCCIterator.h"
00022 #include "llvm/ADT/Statistic.h"
00023 #include "llvm/ADT/STLExtras.h"
00024 #include <iostream>
00025 using namespace llvm;
00026 
00027 namespace {
00028   RegisterAnalysis<CompleteBUDataStructures>
00029   X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
00030   Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined");
00031 }
00032 
00033 
00034 // run - Calculate the bottom up data structure graphs for each function in the
00035 // program.
00036 //
00037 bool CompleteBUDataStructures::runOnModule(Module &M) {
00038   BUDataStructures &BU = getAnalysis<BUDataStructures>();
00039   GlobalECs = BU.getGlobalECs();
00040   GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
00041   GlobalsGraph->setPrintAuxCalls();
00042 
00043   // Our call graph is the same as the BU data structures call graph
00044   ActualCallees = BU.getActualCallees();
00045 
00046   std::vector<DSGraph*> Stack;
00047   hash_map<DSGraph*, unsigned> ValMap;
00048   unsigned NextID = 1;
00049 
00050   Function *MainFunc = M.getMainFunction();
00051   if (MainFunc) {
00052     if (!MainFunc->isExternal())
00053       calculateSCCGraphs(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap);
00054   } else {
00055     std::cerr << "CBU-DSA: No 'main' function found!\n";
00056   }
00057 
00058   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00059     if (!I->isExternal() && !DSInfo.count(I))
00060       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
00061 
00062   GlobalsGraph->removeTriviallyDeadNodes();
00063 
00064 
00065   // Merge the globals variables (not the calls) from the globals graph back
00066   // into the main function's graph so that the main function contains all of
00067   // the information about global pools and GV usage in the program.
00068   if (MainFunc && !MainFunc->isExternal()) {
00069     DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
00070     const DSGraph &GG = *MainGraph.getGlobalsGraph();
00071     ReachabilityCloner RC(MainGraph, GG,
00072                           DSGraph::DontCloneCallNodes |
00073                           DSGraph::DontCloneAuxCallNodes);
00074 
00075     // Clone the global nodes into this graph.
00076     for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
00077            E = GG.getScalarMap().global_end(); I != E; ++I)
00078       if (isa<GlobalVariable>(*I))
00079         RC.getClonedNH(GG.getNodeForValue(*I));
00080 
00081     MainGraph.maskIncompleteMarkers();
00082     MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
00083                                   DSGraph::IgnoreGlobals);
00084   }
00085 
00086   return false;
00087 }
00088 
00089 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
00090   // Has the graph already been created?
00091   DSGraph *&Graph = DSInfo[&F];
00092   if (Graph) return *Graph;
00093 
00094   // Copy the BU graph...
00095   Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
00096   Graph->setGlobalsGraph(GlobalsGraph);
00097   Graph->setPrintAuxCalls();
00098 
00099   // Make sure to update the DSInfo map for all of the functions currently in
00100   // this graph!
00101   for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
00102        I != Graph->retnodes_end(); ++I)
00103     DSInfo[I->first] = Graph;
00104 
00105   return *Graph;
00106 }
00107 
00108 
00109 
00110 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
00111                                                   std::vector<DSGraph*> &Stack,
00112                                                   unsigned &NextID,
00113                                          hash_map<DSGraph*, unsigned> &ValMap) {
00114   assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
00115   unsigned Min = NextID++, MyID = Min;
00116   ValMap[&FG] = Min;
00117   Stack.push_back(&FG);
00118 
00119   // The edges out of the current node are the call site targets...
00120   for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
00121        CI != CE; ++CI) {
00122     Instruction *Call = CI->getCallSite().getInstruction();
00123 
00124     // Loop over all of the actually called functions...
00125     callee_iterator I = callee_begin(Call), E = callee_end(Call);
00126     for (; I != E && I->first == Call; ++I) {
00127       assert(I->first == Call && "Bad callee construction!");
00128       if (!I->second->isExternal()) {
00129         DSGraph &Callee = getOrCreateGraph(*I->second);
00130         unsigned M;
00131         // Have we visited the destination function yet?
00132         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
00133         if (It == ValMap.end())  // No, visit it now.
00134           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
00135         else                    // Yes, get it's number.
00136           M = It->second;
00137         if (M < Min) Min = M;
00138       }
00139     }
00140   }
00141 
00142   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
00143   if (Min != MyID)
00144     return Min;         // This is part of a larger SCC!
00145 
00146   // If this is a new SCC, process it now.
00147   bool IsMultiNodeSCC = false;
00148   while (Stack.back() != &FG) {
00149     DSGraph *NG = Stack.back();
00150     ValMap[NG] = ~0U;
00151 
00152     FG.cloneInto(*NG);
00153 
00154     // Update the DSInfo map and delete the old graph...
00155     for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
00156          I != NG->retnodes_end(); ++I)
00157       DSInfo[I->first] = &FG;
00158 
00159     // Remove NG from the ValMap since the pointer may get recycled.
00160     ValMap.erase(NG);
00161     delete NG;
00162 
00163     Stack.pop_back();
00164     IsMultiNodeSCC = true;
00165   }
00166 
00167   // Clean up the graph before we start inlining a bunch again...
00168   if (IsMultiNodeSCC)
00169     FG.removeTriviallyDeadNodes();
00170 
00171   Stack.pop_back();
00172   processGraph(FG);
00173   ValMap[&FG] = ~0U;
00174   return MyID;
00175 }
00176 
00177 
00178 /// processGraph - Process the BU graphs for the program in bottom-up order on
00179 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
00180 void CompleteBUDataStructures::processGraph(DSGraph &G) {
00181   hash_set<Instruction*> calls;
00182 
00183   // The edges out of the current node are the call site targets...
00184   unsigned i = 0;
00185   for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
00186        ++CI, ++i) {
00187     const DSCallSite &CS = *CI;
00188     Instruction *TheCall = CS.getCallSite().getInstruction();
00189 
00190     assert(calls.insert(TheCall).second &&
00191            "Call instruction occurs multiple times in graph??");
00192 
00193     // Fast path for noop calls.  Note that we don't care about merging globals
00194     // in the callee with nodes in the caller here.
00195     if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
00196       continue;
00197 
00198     // Loop over all of the potentially called functions...
00199     // Inline direct calls as well as indirect calls because the direct
00200     // callee may have indirect callees and so may have changed.
00201     //
00202     callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall);
00203     unsigned TNum = 0, Num = 0;
00204     DEBUG(Num = std::distance(I, E));
00205     for (; I != E; ++I, ++TNum) {
00206       assert(I->first == TheCall && "Bad callee construction!");
00207       Function *CalleeFunc = I->second;
00208       if (!CalleeFunc->isExternal()) {
00209         // Merge the callee's graph into this graph.  This works for normal
00210         // calls or for self recursion within an SCC.
00211         DSGraph &GI = getOrCreateGraph(*CalleeFunc);
00212         ++NumCBUInlines;
00213         G.mergeInGraph(CS, *CalleeFunc, GI,
00214                        DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
00215                        DSGraph::DontCloneAuxCallNodes);
00216         DEBUG(std::cerr << "    Inlining graph [" << i << "/"
00217               << G.getFunctionCalls().size()-1
00218               << ":" << TNum << "/" << Num-1 << "] for "
00219               << CalleeFunc->getName() << "["
00220               << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
00221               << "] into '" /*<< G.getFunctionNames()*/ << "' ["
00222               << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
00223               << "]\n");
00224       }
00225     }
00226   }
00227 
00228   // Recompute the Incomplete markers
00229   G.maskIncompleteMarkers();
00230   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
00231 
00232   // Delete dead nodes.  Treat globals that are unreachable but that can
00233   // reach live nodes as live.
00234   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
00235 }