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/DataStructure.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/Analysis/DataStructure/DSGraph.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/ADT/SCCIterator.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/ADT/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 #if 1   // REMOVE ME EVENTUALLY
  41   // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
  42   // globals graph has been implemented in the BU pass)
  43   TDDataStructures &TD = getAnalysis<TDDataStructures>();
  44
  45   ActualCallees.clear();
  46
  47   // The call graph extractable from the TD pass is _much more complete_ and
  48   // trustable than that generated by the BU pass so far.  Until this is fixed,
  49   // we hack it like this:
  50   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
  51     if (MI->isExternal()) continue;
  52     const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
  53
  54     for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
  55       Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
  56
  57       if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees
  58         const std::vector<GlobalValue*> &Callees =
  59           CSs[CSi].getCalleeNode()->getGlobals();
  60         for (unsigned i = 0, e = Callees.size(); i != e; ++i)
  61           if (Function *F = dyn_cast<Function>(Callees[i]))
  62             ActualCallees.insert(std::make_pair(TheCall, F));
  63       } else {        // direct call: insert the single callee directly
  64         ActualCallees.insert(std::make_pair(TheCall,
  65                                             CSs[CSi].getCalleeFunc()));
  66       }
  67     }
  68   }
  69 #else
  70   // Our call graph is the same as the BU data structures call graph
  71   ActualCallees = BU.getActualCallees();
  72 #endif
  73
  74   std::vector<DSGraph*> Stack;
  75   hash_map<DSGraph*, unsigned> ValMap;
  76   unsigned NextID = 1;
  77
  78   if (Function *Main = M.getMainFunction()) {
  79     if (!Main->isExternal())
  80       calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
  81   } else {
  82     std::cerr << "CBU-DSA: No 'main' function found!\n";
  83   }
  84
  85   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  86     if (!I->isExternal() && !DSInfo.count(I))
  87       calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
  88
  89   GlobalsGraph->removeTriviallyDeadNodes();
  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));
 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::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
 106        I != Graph->getReturnNodes().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 (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
 125     Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
 126
 127     // Loop over all of the actually called functions...
 128     ActualCalleesTy::iterator I, E;
 129     for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
 130       if (!I->second->isExternal()) {
 131         DSGraph &Callee = getOrCreateGraph(*I->second);
 132         unsigned M;
 133         // Have we visited the destination function yet?
 134         hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
 135         if (It == ValMap.end())  // No, visit it now.
 136           M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
 137         else                    // Yes, get it's number.
 138           M = It->second;
 139         if (M < Min) Min = M;
 140       }
 141   }
 142
 143   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
 144   if (Min != MyID)
 145     return Min;         // This is part of a larger SCC!
 146
 147   // If this is a new SCC, process it now.
 148   bool IsMultiNodeSCC = false;
 149   while (Stack.back() != &FG) {
 150     DSGraph *NG = Stack.back();
 151     ValMap[NG] = ~0U;
 152
 153     DSGraph::NodeMapTy NodeMap;
 154     FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
 155
 156     // Update the DSInfo map and delete the old graph...
 157     for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
 158          I != NG->getReturnNodes().end(); ++I)
 159       DSInfo[I->first] = &FG;
 160     delete NG;
 161
 162     Stack.pop_back();
 163     IsMultiNodeSCC = true;
 164   }
 165
 166   // Clean up the graph before we start inlining a bunch again...
 167   if (IsMultiNodeSCC)
 168     FG.removeTriviallyDeadNodes();
 169
 170   Stack.pop_back();
 171   processGraph(FG);
 172   ValMap[&FG] = ~0U;
 173   return MyID;
 174 }
 175
 176
 177 /// processGraph - Process the BU graphs for the program in bottom-up order on
 178 /// the SCC of the __ACTUAL__ call graph.  This builds "complete" BU graphs.
 179 void CompleteBUDataStructures::processGraph(DSGraph &G) {
 180   hash_set<Instruction*> calls;
 181
 182   // The edges out of the current node are the call site targets...
 183   for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
 184     const DSCallSite &CS = G.getFunctionCalls()[i];
 185     Instruction *TheCall = CS.getCallSite().getInstruction();
 186
 187     assert(calls.insert(TheCall).second &&
 188            "Call instruction occurs multiple times in graph??");
 189
 190
 191     // Loop over all of the potentially called functions...
 192     // Inline direct calls as well as indirect calls because the direct
 193     // callee may have indirect callees and so may have changed.
 194     //
 195     ActualCalleesTy::iterator I, E;
 196     tie(I, E) = ActualCallees.equal_range(TheCall);
 197     unsigned TNum = 0, Num = std::distance(I, E);
 198     for (; I != E; ++I, ++TNum) {
 199       Function *CalleeFunc = I->second;
 200       if (!CalleeFunc->isExternal()) {
 201         // Merge the callee's graph into this graph.  This works for normal
 202         // calls or for self recursion within an SCC.
 203         DSGraph &GI = getOrCreateGraph(*CalleeFunc);
 204         ++NumCBUInlines;
 205         G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
 206                        DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
 207                        DSGraph::DontCloneAuxCallNodes);
 208         DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
 209               << ":" << TNum << "/" << Num-1 << "] for "
 210               << CalleeFunc->getName() << "["
 211               << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
 212               << "] into '" /*<< G.getFunctionNames()*/ << "' ["
 213               << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
 214               << "]\n");
 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 }