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     calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
  75   } else {
  76     std::cerr << "CBU-DSA: No 'main' function found!\n";
  77   }
  78
  79   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  80     if (!I->isExternal() && !DSInfo.count(I))
  81       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
  82
  83   GlobalsGraph->removeTriviallyDeadNodes();
  84   return false;
  85 }
  86
  87 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
  88   // Has the graph already been created?
  89   DSGraph *&Graph = DSInfo[&F];
  90   if (Graph) return *Graph;
  91
  92   // Copy the BU graph...
  93   Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
  94   Graph->setGlobalsGraph(GlobalsGraph);
  95   Graph->setPrintAuxCalls();
  96
  97   // Make sure to update the DSInfo map for all of the functions currently in
  98   // this graph!
  99   for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
 100        I != Graph->getReturnNodes().end(); ++I)
 101     DSInfo[I->first] = Graph;
 102
 103   return *Graph;
 104 }
 105
 106
 107
 108 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
 109                                                   std::vector<DSGraph*> &Stack,
 110                                                   unsigned &NextID,
 111                                          hash_map<DSGraph*, unsigned> &ValMap) {
 112   assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
 113   unsigned Min = NextID++, MyID = Min;
 114   ValMap[&FG] = Min;
 115   Stack.push_back(&FG);
 116
 117   // The edges out of the current node are the call site targets...
 118   for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
 119     Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
 120
 121     // Loop over all of the actually called functions...
 122     ActualCalleesTy::iterator I, E;
 123     for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
 124       if (!I->second->isExternal()) {
 125         DSGraph &Callee = getOrCreateGraph(*I->second);
 126         unsigned M;
 127         // Have we visited the destination function yet?
 128         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
 129         if (It == ValMap.end())  // No, visit it now.
 130           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
 131         else                    // Yes, get it's number.
 132           M = It->second;
 133         if (M < Min) Min = M;
 134       }
 135   }
 136
 137   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
 138   if (Min != MyID)
 139     return Min;         // This is part of a larger SCC!
 140
 141   // If this is a new SCC, process it now.
 142   bool IsMultiNodeSCC = false;
 143   while (Stack.back() != &FG) {
 144     DSGraph *NG = Stack.back();
 145     ValMap[NG] = ~0U;
 146
 147     DSGraph::NodeMapTy NodeMap;
 148     FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
 149
 150     // Update the DSInfo map and delete the old graph...
 151     for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
 152          I != NG->getReturnNodes().end(); ++I)
 153       DSInfo[I->first] = &FG;
 154     delete NG;
 155
 156     Stack.pop_back();
 157     IsMultiNodeSCC = true;
 158   }
 159
 160   // Clean up the graph before we start inlining a bunch again...
 161   if (IsMultiNodeSCC)
 162     FG.removeTriviallyDeadNodes();
 163
 164   Stack.pop_back();
 165   processGraph(FG);
 166   ValMap[&FG] = ~0U;
 167   return MyID;
 168 }
 169
 170
 171 /// processGraph - Process the BU graphs for the program in bottom-up order on
 172 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
 173 void CompleteBUDataStructures::processGraph(DSGraph &G) {
 174   hash_set<Instruction*> calls;
 175
 176   // The edges out of the current node are the call site targets...
 177   for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
 178     const DSCallSite &CS = G.getFunctionCalls()[i];
 179     Instruction *TheCall = CS.getCallSite().getInstruction();
 180
 181     assert(calls.insert(TheCall).second &&
 182            "Call instruction occurs multiple times in graph??");
 183
 184
 185     // The Normal BU pass will have taken care of direct calls well already,
 186     // don't worry about them.
 187
 188     // FIXME: if a direct callee had indirect callees, it seems like they could
 189     // be updated and we would have to reinline even direct calls!
 190
 191     if (!CS.getCallSite().getCalledFunction()) {
 192       // Loop over all of the actually called functions...
 193       ActualCalleesTy::iterator I, E;
 194       tie(I, E) = ActualCallees.equal_range(TheCall);
 195       unsigned TNum = 0, Num = std::distance(I, E);
 196       for (; I != E; ++I, ++TNum) {
 197         Function *CalleeFunc = I->second;
 198         if (!CalleeFunc->isExternal()) {
 199           // Merge the callee's graph into this graph.  This works for normal
 200           // calls or for self recursion within an SCC.
 201           DSGraph &GI = getOrCreateGraph(*CalleeFunc);
 202           ++NumCBUInlines;
 203           G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
 204                          DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
 205                          DSGraph::DontCloneAuxCallNodes);
 206           DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
 207                 << ":" << TNum << "/" << Num-1 << "] for "
 208                 << CalleeFunc->getName() << "["
 209                 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
 210                 << "] into '" /*<< G.getFunctionNames()*/ << "' ["
 211                 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
 212                 << "]\n");
 213         }
 214       }
 215     }
 216   }
 217
 218   // Recompute the Incomplete markers
 219   assert(G.getInlinedGlobals().empty());
 220   G.maskIncompleteMarkers();
 221   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
 222
 223   // Delete dead nodes.  Treat globals that are unreachable but that can
 224   // reach live nodes as live.
 225   G.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
 226 }