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