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