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