lib/Analysis/DataStructure/BottomUpClosure.cpp

   1 //===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
   2 //
   3 // This file implements the BUDataStructures class, which represents the
   4 // Bottom-Up Interprocedural closure of the data structure graph over the
   5 // program.  This is useful for applications like pool allocation, but **not**
   6 // applications like alias analysis.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Analysis/DSGraph.h"
  12 #include "llvm/Module.h"
  13 #include "Support/Statistic.h"
  14 using std::map;
  15
  16 static RegisterAnalysis<BUDataStructures>
  17 X("budatastructure", "Bottom-up Data Structure Analysis Closure");
  18
  19 using namespace DS;
  20
  21
  22 // releaseMemory - If the pass pipeline is done with this pass, we can release
  23 // our memory... here...
  24 //
  25 void BUDataStructures::releaseMemory() {
  26   // Delete all call site information
  27   CallSites.clear();
  28
  29   for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  30          E = DSInfo.end(); I != E; ++I)
  31     delete I->second;
  32
  33   // Empty map so next time memory is released, data structures are not
  34   // re-deleted.
  35   DSInfo.clear();
  36 }
  37
  38 // run - Calculate the bottom up data structure graphs for each function in the
  39 // program.
  40 //
  41 bool BUDataStructures::run(Module &M) {
  42   // Simply calculate the graphs for each function...
  43   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  44     if (!I->isExternal())
  45       calculateGraph(*I);
  46   return false;
  47 }
  48
  49 DSGraph &BUDataStructures::calculateGraph(Function &F) {
  50   // Make sure this graph has not already been calculated, or that we don't get
  51   // into an infinite loop with mutually recursive functions.
  52   //
  53   DSGraph *&Graph = DSInfo[&F];
  54   if (Graph) return *Graph;
  55
  56   // Copy the local version into DSInfo...
  57   Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
  58
  59 #if 0
  60   // Populate the GlobalsGraph with globals from this one.
  61   Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
  62 #endif
  63
  64   // Start resolving calls...
  65   std::vector<DSCallSite> &FCs = Graph->getFunctionCalls();
  66
  67   DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");
  68
  69   bool Inlined;
  70   do {
  71     Inlined = false;
  72
  73     for (unsigned i = 0; i != FCs.size(); ++i) {
  74       // Copy the call, because inlining graphs may invalidate the FCs vector.
  75       DSCallSite Call = FCs[i];
  76
  77       // If the function list is complete...
  78       if ((Call.getCallee().getNode()->NodeType & DSNode::Incomplete)==0) {
  79         // Start inlining all of the functions we can... some may not be
  80         // inlinable if they are external...
  81         //
  82         std::vector<GlobalValue*> Callees =
  83           Call.getCallee().getNode()->getGlobals();
  84
  85         // Loop over the functions, inlining whatever we can...
  86         for (unsigned c = 0; c != Callees.size(); ++c) {
  87           // Must be a function type, so this cast MUST succeed.
  88           Function &FI = cast<Function>(*Callees[c]);
  89
  90           if (&FI == &F) {
  91             // Self recursion... simply link up the formal arguments with the
  92             // actual arguments...
  93             DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
  94
  95             // Handle self recursion by resolving the arguments and return value
  96             Graph->mergeInGraph(Call, *Graph, true);
  97
  98             // Erase the entry in the callees vector
  99             Callees.erase(Callees.begin()+c--);
 100
 101           } else if (!FI.isExternal()) {
 102             DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
 103                   << FI.getName() << "\n");
 104
 105             // Get the data structure graph for the called function, closing it
 106             // if possible (which is only impossible in the case of mutual
 107             // recursion...
 108             //
 109             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 110
 111             DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
 112                   << " in: " << F.getName() << "\n");
 113
 114             // Record that the original DSCallSite was a call site of FI.
 115             // This may or may not have been known when the DSCallSite was
 116             // originally created.
 117             std::vector<DSCallSite> &CallSitesForFunc = CallSites[&FI];
 118             CallSitesForFunc.push_back(Call);
 119             CallSitesForFunc.back().setResolvingCaller(&F);
 120             CallSitesForFunc.back().setCallee(0);
 121
 122             // Handle self recursion by resolving the arguments and return value
 123             Graph->mergeInGraph(Call, GI, true);
 124
 125             // Erase the entry in the Callees vector
 126             Callees.erase(Callees.begin()+c--);
 127
 128           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
 129                      FI.getName() == "fprintf" || FI.getName() == "open" ||
 130                      FI.getName() == "sprintf") {
 131             // FIXME: These special cases (eg printf) should go away when we can
 132             // define functions that take a variable number of arguments.
 133
 134             // FIXME: at the very least, this should update mod/ref info
 135             // Erase the entry in the globals vector
 136             Callees.erase(Callees.begin()+c--);
 137           }
 138         }
 139
 140         if (Callees.empty()) {         // Inlined all of the function calls?
 141           // Erase the call if it is resolvable...
 142           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
 143           Inlined = true;
 144         } else if (Callees.size() !=
 145                    Call.getCallee().getNode()->getGlobals().size()) {
 146           // Was able to inline SOME, but not all of the functions.  Construct a
 147           // new global node here.
 148           //
 149           assert(0 && "Unimpl!");
 150           Inlined = true;
 151         }
 152       }
 153     }
 154
 155     // Recompute the Incomplete markers.  If there are any function calls left
 156     // now that are complete, we must loop!
 157     if (Inlined) {
 158       Graph->maskIncompleteMarkers();
 159       Graph->markIncompleteNodes();
 160       Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
 161     }
 162   } while (Inlined && !FCs.empty());
 163
 164   Graph->maskIncompleteMarkers();
 165   Graph->markIncompleteNodes();
 166   Graph->removeTriviallyDeadNodes(false);
 167   Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
 168
 169   DEBUG(std::cerr << "  [BU] Done inlining: " << F.getName() << " ["
 170         << Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
 171         << "]\n");
 172
 173   return *Graph;
 174 }