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