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 // TODO: FIXME
  20 namespace DataStructureAnalysis {
  21   // isPointerType - Return true if this first class type is big enough to hold
  22   // a pointer.
  23   //
  24   bool isPointerType(const Type *Ty);
  25 }
  26 using namespace DataStructureAnalysis;
  27
  28
  29 // releaseMemory - If the pass pipeline is done with this pass, we can release
  30 // our memory... here...
  31 //
  32 void BUDataStructures::releaseMemory() {
  33   // Delete all call site information
  34   CallSites.clear();
  35
  36   for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  37          E = DSInfo.end(); I != E; ++I)
  38     delete I->second;
  39
  40   // Empty map so next time memory is released, data structures are not
  41   // re-deleted.
  42   DSInfo.clear();
  43 }
  44
  45 // run - Calculate the bottom up data structure graphs for each function in the
  46 // program.
  47 //
  48 bool BUDataStructures::run(Module &M) {
  49   // Simply calculate the graphs for each function...
  50   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  51     if (!I->isExternal())
  52       calculateGraph(*I);
  53   return false;
  54 }
  55
  56 // ResolveArguments - Resolve the formal and actual arguments for a function
  57 // call.
  58 //
  59 static void ResolveArguments(DSCallSite &Call, Function &F,
  60                              map<Value*, DSNodeHandle> &ValueMap) {
  61   // Resolve all of the function arguments...
  62   Function::aiterator AI = F.abegin();
  63   for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) {
  64     // Advance the argument iterator to the first pointer argument...
  65     while (!isPointerType(AI->getType())) ++AI;
  66
  67     // Add the link from the argument scalar to the provided value
  68     DSNodeHandle &NN = ValueMap[AI];
  69     NN.addEdgeTo(Call.getPtrArgNode(i));
  70     ++AI;
  71   }
  72 }
  73
  74 DSGraph &BUDataStructures::calculateGraph(Function &F) {
  75   // Make sure this graph has not already been calculated, or that we don't get
  76   // into an infinite loop with mutually recursive functions.
  77   //
  78   DSGraph *&Graph = DSInfo[&F];
  79   if (Graph) return *Graph;
  80
  81   // Copy the local version into DSInfo...
  82   Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
  83
  84 #if 0
  85   // Populate the GlobalsGraph with globals from this one.
  86   Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
  87 #endif
  88
  89   // Start resolving calls...
  90   std::vector<DSCallSite> &FCs = Graph->getFunctionCalls();
  91
  92   DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");
  93
  94   bool Inlined;
  95   do {
  96     Inlined = false;
  97
  98     for (unsigned i = 0; i != FCs.size(); ++i) {
  99       // Copy the call, because inlining graphs may invalidate the FCs vector.
 100       DSCallSite Call = FCs[i];
 101
 102       // If the function list is complete...
 103       if ((Call.getCalleeNode().getNode()->NodeType & DSNode::Incomplete)==0) {
 104         // Start inlining all of the functions we can... some may not be
 105         // inlinable if they are external...
 106         //
 107         std::vector<GlobalValue*> Callees =
 108           Call.getCalleeNode().getNode()->getGlobals();
 109
 110         // Loop over the functions, inlining whatever we can...
 111         for (unsigned c = 0; c != Callees.size(); ++c) {
 112           // Must be a function type, so this cast MUST succeed.
 113           Function &FI = cast<Function>(*Callees[c]);
 114
 115           if (&FI == &F) {
 116             // Self recursion... simply link up the formal arguments with the
 117             // actual arguments...
 118             DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
 119
 120             // Handle the return value if present...
 121             if (Call.getReturnValueNode().getNode())
 122               Graph->getRetNode().mergeWith(Call.getReturnValueNode());
 123
 124             // Resolve the arguments in the call to the actual values...
 125             ResolveArguments(Call, F, Graph->getValueMap());
 126
 127             // Erase the entry in the callees vector
 128             Callees.erase(Callees.begin()+c--);
 129
 130           } else if (!FI.isExternal()) {
 131             DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
 132                   << FI.getName() << "\n");
 133
 134             // Get the data structure graph for the called function, closing it
 135             // if possible (which is only impossible in the case of mutual
 136             // recursion...
 137             //
 138             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 139
 140             DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
 141                   << " in: " << F.getName() << "\n");
 142
 143             // Record that the original DSCallSite was a call site of FI.
 144             // This may or may not have been known when the DSCallSite was
 145             // originally created.
 146             CallSites[&FI].push_back(Call);
 147
 148             // Clone the callee's graph into the current graph, keeping
 149             // track of where scalars in the old graph _used_ to point,
 150             // and of the new nodes matching nodes of the old graph.
 151             map<Value*, DSNodeHandle> OldValMap;
 152             map<const DSNode*, DSNode*> OldNodeMap;
 153
 154             // The clone call may invalidate any of the vectors in the data
 155             // structure graph.  Strip locals and don't copy the list of callers
 156             DSNodeHandle RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
 157                                                    /*StripScalars*/   true,
 158                                                    /*StripAllocas*/   true,
 159                                                    /*CopyCallers*/    false,
 160                                                    /*CopyOrigCalls*/  false);
 161
 162             // Resolve the arguments in the call to the actual values...
 163             ResolveArguments(Call, FI, OldValMap);
 164
 165             if (Call.getReturnValueNode().getNode())  // Handle the return value if present
 166               RetVal.mergeWith(Call.getReturnValueNode());
 167
 168             // Erase the entry in the Callees vector
 169             Callees.erase(Callees.begin()+c--);
 170
 171           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
 172                      FI.getName() == "fprintf" || FI.getName() == "open" ||
 173                      FI.getName() == "sprintf") {
 174
 175             // Erase the entry in the globals vector
 176             Callees.erase(Callees.begin()+c--);
 177           }
 178         }
 179
 180         if (Callees.empty()) {         // Inlined all of the function calls?
 181           // Erase the call if it is resolvable...
 182           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
 183           Inlined = true;
 184         } else if (Callees.size() != Call.getCalleeNode().getNode()->getGlobals().size()) {
 185           // Was able to inline SOME, but not all of the functions.  Construct a
 186           // new global node here.
 187           //
 188           assert(0 && "Unimpl!");
 189           Inlined = true;
 190         }
 191       }
 192     }
 193
 194     // Recompute the Incomplete markers.  If there are any function calls left
 195     // now that are complete, we must loop!
 196     if (Inlined) {
 197       Graph->maskIncompleteMarkers();
 198       Graph->markIncompleteNodes();
 199       Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
 200     }
 201   } while (Inlined && !FCs.empty());
 202
 203   Graph->maskIncompleteMarkers();
 204   Graph->markIncompleteNodes();
 205   Graph->removeTriviallyDeadNodes(false);
 206   Graph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true);
 207
 208   DEBUG(std::cerr << "  [BU] Done inlining: " << F.getName() << " ["
 209         << Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
 210         << "]\n");
 211
 212   return *Graph;
 213 }