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