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