lib/Analysis/DataStructure/CompleteBottomUp.cpp

   1 //===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is the exact same as the bottom-up graphs, but we use take a completed
  11 // call graph and inline all indirect callees into their callers graphs, making
  12 // the result more useful for things like pool allocation.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "cbudatastructure"
  17 #include "llvm/Analysis/DataStructure/DataStructure.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/Analysis/DataStructure/DSGraph.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/ADT/SCCIterator.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 using namespace llvm;
  25
  26 namespace {
  27   RegisterPass<CompleteBUDataStructures>
  28   X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
  29   Statistic NumCBUInlines("cbudatastructures", "Number of graphs inlined");
  30 }
  31
  32
  33 // run - Calculate the bottom up data structure graphs for each function in the
  34 // program.
  35 //
  36 bool CompleteBUDataStructures::runOnModule(Module &M) {
  37   BUDataStructures &BU = getAnalysis<BUDataStructures>();
  38   GlobalECs = BU.getGlobalECs();
  39   GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
  40   GlobalsGraph->setPrintAuxCalls();
  41
  42   // Our call graph is the same as the BU data structures call graph
  43   ActualCallees = BU.getActualCallees();
  44
  45   std::vector<DSGraph*> Stack;
  46   hash_map<DSGraph*, unsigned> ValMap;
  47   unsigned NextID = 1;
  48
  49   Function *MainFunc = M.getMainFunction();
  50   if (MainFunc) {
  51     if (!MainFunc->isExternal())
  52       calculateSCCGraphs(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap);
  53   } else {
  54     DOUT << "CBU-DSA: No 'main' function found!\n";
  55   }
  56
  57   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  58     if (!I->isExternal() && !DSInfo.count(I)) {
  59       if (MainFunc) {
  60         DOUT << "*** CBU: Function unreachable from main: "
  61              << I->getName() << "\n";
  62       }
  63       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
  64     }
  65
  66   GlobalsGraph->removeTriviallyDeadNodes();
  67
  68
  69   // Merge the globals variables (not the calls) from the globals graph back
  70   // into the main function's graph so that the main function contains all of
  71   // the information about global pools and GV usage in the program.
  72   if (MainFunc && !MainFunc->isExternal()) {
  73     DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
  74     const DSGraph &GG = *MainGraph.getGlobalsGraph();
  75     ReachabilityCloner RC(MainGraph, GG,
  76                           DSGraph::DontCloneCallNodes |
  77                           DSGraph::DontCloneAuxCallNodes);
  78
  79     // Clone the global nodes into this graph.
  80     for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
  81            E = GG.getScalarMap().global_end(); I != E; ++I)
  82       if (isa<GlobalVariable>(*I))
  83         RC.getClonedNH(GG.getNodeForValue(*I));
  84
  85     MainGraph.maskIncompleteMarkers();
  86     MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
  87                                   DSGraph::IgnoreGlobals);
  88   }
  89
  90   return false;
  91 }
  92
  93 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
  94   // Has the graph already been created?
  95   DSGraph *&Graph = DSInfo[&F];
  96   if (Graph) return *Graph;
  97
  98   // Copy the BU graph...
  99   Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
 100   Graph->setGlobalsGraph(GlobalsGraph);
 101   Graph->setPrintAuxCalls();
 102
 103   // Make sure to update the DSInfo map for all of the functions currently in
 104   // this graph!
 105   for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
 106        I != Graph->retnodes_end(); ++I)
 107     DSInfo[I->first] = Graph;
 108
 109   return *Graph;
 110 }
 111
 112
 113
 114 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
 115                                                   std::vector<DSGraph*> &Stack,
 116                                                   unsigned &NextID,
 117                                          hash_map<DSGraph*, unsigned> &ValMap) {
 118   assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
 119   unsigned Min = NextID++, MyID = Min;
 120   ValMap[&FG] = Min;
 121   Stack.push_back(&FG);
 122
 123   // The edges out of the current node are the call site targets...
 124   for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
 125        CI != CE; ++CI) {
 126     Instruction *Call = CI->getCallSite().getInstruction();
 127
 128     // Loop over all of the actually called functions...
 129     callee_iterator I = callee_begin(Call), E = callee_end(Call);
 130     for (; I != E && I->first == Call; ++I) {
 131       assert(I->first == Call && "Bad callee construction!");
 132       if (!I->second->isExternal()) {
 133         DSGraph &Callee = getOrCreateGraph(*I->second);
 134         unsigned M;
 135         // Have we visited the destination function yet?
 136         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
 137         if (It == ValMap.end())  // No, visit it now.
 138           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
 139         else                    // Yes, get it's number.
 140           M = It->second;
 141         if (M < Min) Min = M;
 142       }
 143     }
 144   }
 145
 146   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
 147   if (Min != MyID)
 148     return Min;         // This is part of a larger SCC!
 149
 150   // If this is a new SCC, process it now.
 151   bool IsMultiNodeSCC = false;
 152   while (Stack.back() != &FG) {
 153     DSGraph *NG = Stack.back();
 154     ValMap[NG] = ~0U;
 155
 156     FG.cloneInto(*NG);
 157
 158     // Update the DSInfo map and delete the old graph...
 159     for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
 160          I != NG->retnodes_end(); ++I)
 161       DSInfo[I->first] = &FG;
 162
 163     // Remove NG from the ValMap since the pointer may get recycled.
 164     ValMap.erase(NG);
 165     delete NG;
 166
 167     Stack.pop_back();
 168     IsMultiNodeSCC = true;
 169   }
 170
 171   // Clean up the graph before we start inlining a bunch again...
 172   if (IsMultiNodeSCC)
 173     FG.removeTriviallyDeadNodes();
 174
 175   Stack.pop_back();
 176   processGraph(FG);
 177   ValMap[&FG] = ~0U;
 178   return MyID;
 179 }
 180
 181
 182 /// processGraph - Process the BU graphs for the program in bottom-up order on
 183 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
 184 void CompleteBUDataStructures::processGraph(DSGraph &G) {
 185   hash_set<Instruction*> calls;
 186
 187   // The edges out of the current node are the call site targets...
 188   unsigned i = 0;
 189   for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
 190        ++CI, ++i) {
 191     const DSCallSite &CS = *CI;
 192     Instruction *TheCall = CS.getCallSite().getInstruction();
 193
 194     assert(calls.insert(TheCall).second &&
 195            "Call instruction occurs multiple times in graph??");
 196
 197     // Fast path for noop calls.  Note that we don't care about merging globals
 198     // in the callee with nodes in the caller here.
 199     if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
 200       continue;
 201
 202     // Loop over all of the potentially called functions...
 203     // Inline direct calls as well as indirect calls because the direct
 204     // callee may have indirect callees and so may have changed.
 205     //
 206     callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall);
 207     unsigned TNum = 0, Num = 0;
 208     DEBUG(Num = std::distance(I, E));
 209     for (; I != E; ++I, ++TNum) {
 210       assert(I->first == TheCall && "Bad callee construction!");
 211       Function *CalleeFunc = I->second;
 212       if (!CalleeFunc->isExternal()) {
 213         // Merge the callee's graph into this graph.  This works for normal
 214         // calls or for self recursion within an SCC.
 215         DSGraph &GI = getOrCreateGraph(*CalleeFunc);
 216         ++NumCBUInlines;
 217         G.mergeInGraph(CS, *CalleeFunc, GI,
 218                        DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
 219                        DSGraph::DontCloneAuxCallNodes);
 220         DOUT << "    Inlining graph [" << i << "/"
 221              << G.getFunctionCalls().size()-1
 222              << ":" << TNum << "/" << Num-1 << "] for "
 223              << CalleeFunc->getName() << "["
 224              << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
 225              << "] into '" /*<< G.getFunctionNames()*/ << "' ["
 226              << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
 227              << "]\n";
 228       }
 229     }
 230   }
 231
 232   // Recompute the Incomplete markers
 233   G.maskIncompleteMarkers();
 234   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
 235
 236   // Delete dead nodes.  Treat globals that are unreachable but that can
 237   // reach live nodes as live.
 238   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 239 }