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 #include "llvm/Analysis/DataStructure.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/Analysis/DSGraph.h"
  19 #include "Support/Debug.h"
  20 #include "Support/SCCIterator.h"
  21 #include "Support/Statistic.h"
  22 #include "Support/STLExtras.h"
  23 using namespace llvm;
  24
  25 namespace {
  26   RegisterAnalysis<CompleteBUDataStructures>
  27   X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
  28   Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined");
  29 }
  30
  31
  32 // run - Calculate the bottom up data structure graphs for each function in the
  33 // program.
  34 //
  35 bool CompleteBUDataStructures::run(Module &M) {
  36   BUDataStructures &BU = getAnalysis<BUDataStructures>();
  37   GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
  38   GlobalsGraph->setPrintAuxCalls();
  39
  40   // Our call graph is the same as the BU data structures call graph
  41   ActualCallees = BU.getActualCallees();
  42
  43 #if 1   // REMOVE ME EVENTUALLY
  44   // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
  45   // globals graph has been implemented in the BU pass)
  46   TDDataStructures &TD = getAnalysis<TDDataStructures>();
  47
  48   // The call graph extractable from the TD pass is _much more complete_ and
  49   // trustable than that generated by the BU pass so far.  Until this is fixed,
  50   // we hack it like this:
  51   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
  52     if (MI->isExternal()) continue;
  53     const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
  54
  55     for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
  56       if (CSs[CSi].isIndirectCall()) {
  57         Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
  58
  59         const std::vector<GlobalValue*> &Callees =
  60           CSs[CSi].getCalleeNode()->getGlobals();
  61         for (unsigned i = 0, e = Callees.size(); i != e; ++i)
  62           if (Function *F = dyn_cast<Function>(Callees[i]))
  63             ActualCallees.insert(std::make_pair(TheCall, F));
  64       }
  65     }
  66   }
  67 #endif
  68
  69   std::vector<DSGraph*> Stack;
  70   hash_map<DSGraph*, unsigned> ValMap;
  71   unsigned NextID = 1;
  72
  73   if (Function *Main = M.getMainFunction()) {
  74     if (!Main->isExternal())
  75       calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
  76   } else {
  77     std::cerr << "CBU-DSA: No 'main' function found!\n";
  78   }
  79
  80   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  81     if (!I->isExternal() && !DSInfo.count(I))
  82       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
  83
  84   GlobalsGraph->removeTriviallyDeadNodes();
  85   return false;
  86 }
  87
  88 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
  89   // Has the graph already been created?
  90   DSGraph *&Graph = DSInfo[&F];
  91   if (Graph) return *Graph;
  92
  93   // Copy the BU graph...
  94   Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
  95   Graph->setGlobalsGraph(GlobalsGraph);
  96   Graph->setPrintAuxCalls();
  97
  98   // Make sure to update the DSInfo map for all of the functions currently in
  99   // this graph!
 100   for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
 101        I != Graph->getReturnNodes().end(); ++I)
 102     DSInfo[I->first] = Graph;
 103
 104   return *Graph;
 105 }
 106
 107
 108
 109 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
 110                                                   std::vector<DSGraph*> &Stack,
 111                                                   unsigned &NextID,
 112                                          hash_map<DSGraph*, unsigned> &ValMap) {
 113   assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
 114   unsigned Min = NextID++, MyID = Min;
 115   ValMap[&FG] = Min;
 116   Stack.push_back(&FG);
 117
 118   // The edges out of the current node are the call site targets...
 119   for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
 120     Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
 121
 122     // Loop over all of the actually called functions...
 123     ActualCalleesTy::iterator I, E;
 124     for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
 125       if (!I->second->isExternal()) {
 126         DSGraph &Callee = getOrCreateGraph(*I->second);
 127         unsigned M;
 128         // Have we visited the destination function yet?
 129         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
 130         if (It == ValMap.end())  // No, visit it now.
 131           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
 132         else                    // Yes, get it's number.
 133           M = It->second;
 134         if (M < Min) Min = M;
 135       }
 136   }
 137
 138   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
 139   if (Min != MyID)
 140     return Min;         // This is part of a larger SCC!
 141
 142   // If this is a new SCC, process it now.
 143   bool IsMultiNodeSCC = false;
 144   while (Stack.back() != &FG) {
 145     DSGraph *NG = Stack.back();
 146     ValMap[NG] = ~0U;
 147
 148     DSGraph::NodeMapTy NodeMap;
 149     FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
 150
 151     // Update the DSInfo map and delete the old graph...
 152     for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
 153          I != NG->getReturnNodes().end(); ++I)
 154       DSInfo[I->first] = &FG;
 155     delete NG;
 156
 157     Stack.pop_back();
 158     IsMultiNodeSCC = true;
 159   }
 160
 161   // Clean up the graph before we start inlining a bunch again...
 162   if (IsMultiNodeSCC)
 163     FG.removeTriviallyDeadNodes();
 164
 165   Stack.pop_back();
 166   processGraph(FG);
 167   ValMap[&FG] = ~0U;
 168   return MyID;
 169 }
 170
 171
 172 /// processGraph - Process the BU graphs for the program in bottom-up order on
 173 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
 174 void CompleteBUDataStructures::processGraph(DSGraph &G) {
 175   hash_set<Instruction*> calls;
 176
 177   // The edges out of the current node are the call site targets...
 178   for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
 179     const DSCallSite &CS = G.getFunctionCalls()[i];
 180     Instruction *TheCall = CS.getCallSite().getInstruction();
 181
 182     assert(calls.insert(TheCall).second &&
 183            "Call instruction occurs multiple times in graph??");
 184
 185
 186     // The Normal BU pass will have taken care of direct calls well already,
 187     // don't worry about them.
 188
 189     // FIXME: if a direct callee had indirect callees, it seems like they could
 190     // be updated and we would have to reinline even direct calls!
 191
 192     if (!CS.getCallSite().getCalledFunction()) {
 193       // Loop over all of the actually called functions...
 194       ActualCalleesTy::iterator I, E;
 195       tie(I, E) = ActualCallees.equal_range(TheCall);
 196       unsigned TNum = 0, Num = std::distance(I, E);
 197       for (; I != E; ++I, ++TNum) {
 198         Function *CalleeFunc = I->second;
 199         if (!CalleeFunc->isExternal()) {
 200           // Merge the callee's graph into this graph.  This works for normal
 201           // calls or for self recursion within an SCC.
 202           DSGraph &GI = getOrCreateGraph(*CalleeFunc);
 203           ++NumCBUInlines;
 204           G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
 205                          DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
 206                          DSGraph::DontCloneAuxCallNodes);
 207           DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
 208                 << ":" << TNum << "/" << Num-1 << "] for "
 209                 << CalleeFunc->getName() << "["
 210                 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
 211                 << "] into '" /*<< G.getFunctionNames()*/ << "' ["
 212                 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
 213                 << "]\n");
 214         }
 215       }
 216     }
 217   }
 218
 219   // Recompute the Incomplete markers
 220   assert(G.getInlinedGlobals().empty());
 221   G.maskIncompleteMarkers();
 222   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
 223
 224   // Delete dead nodes.  Treat globals that are unreachable but that can
 225   // reach live nodes as live.
 226   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 227 }