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