lib/Analysis/DataStructure/BottomUpClosure.cpp

   1 //===- BottomUpClosure.cpp - Compute the bottom up interprocedure 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 pointer analysis.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Module.h"
  12 #include "llvm/DerivedTypes.h"
  13 #include "Support/StatisticReporter.h"
  14 #include <set>
  15 using std::map;
  16
  17 static RegisterAnalysis<BUDataStructures>
  18 X("budatastructure", "Bottom-up Data Structure Analysis Closure");
  19 AnalysisID BUDataStructures::ID = X;
  20
  21 // releaseMemory - If the pass pipeline is done with this pass, we can release
  22 // our memory... here...
  23 //
  24 void BUDataStructures::releaseMemory() {
  25   for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  26          E = DSInfo.end(); I != E; ++I)
  27     delete I->second;
  28
  29   // Empty map so next time memory is released, data structures are not
  30   // re-deleted.
  31   DSInfo.clear();
  32 }
  33
  34 // run - Calculate the bottom up data structure graphs for each function in the
  35 // program.
  36 //
  37 bool BUDataStructures::run(Module &M) {
  38   // Simply calculate the graphs for each function...
  39   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  40     if (!I->isExternal())
  41       calculateGraph(*I);
  42   return false;
  43 }
  44
  45
  46 // ResolveArguments - Resolve the formal and actual arguments for a function
  47 // call.
  48 //
  49 static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
  50                              map<Value*, DSNodeHandle> &ValueMap) {
  51   // Resolve all of the function arguments...
  52   Function::aiterator AI = F.abegin();
  53   for (unsigned i = 2, e = Call.size(); i != e; ++i) {
  54     // Advance the argument iterator to the first pointer argument...
  55     while (!isa<PointerType>(AI->getType())) ++AI;
  56
  57     // Add the link from the argument scalar to the provided value
  58     DSNode *NN = ValueMap[AI];
  59     NN->addEdgeTo(Call[i]);
  60     ++AI;
  61   }
  62 }
  63
  64 // MergeGlobalNodes - Merge all existing global nodes with globals
  65 // inlined from the callee or with globals from the GlobalsGraph.
  66 //
  67 static void MergeGlobalNodes(DSGraph& Graph,
  68                              map<Value*, DSNodeHandle> &OldValMap) {
  69   map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
  70   for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
  71        I != E; ++I)
  72     if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
  73       map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
  74       if (NHI != OldValMap.end())       // was it inlined from the callee?
  75         I->second->mergeWith(NHI->second);
  76       else                              // get it from the GlobalsGraph
  77         I->second->mergeWith(Graph.cloneGlobalInto(GV));
  78     }
  79
  80   // Add unused inlined global nodes into the value map
  81   for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
  82          E = OldValMap.end(); I != E; ++I)
  83     if (isa<GlobalValue>(I->first)) {
  84       DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
  85       if (NH == 0)
  86         NH = I->second;                     // Add the one just inlined.
  87     }
  88
  89 }
  90
  91 DSGraph &BUDataStructures::calculateGraph(Function &F) {
  92   // Make sure this graph has not already been calculated, or that we don't get
  93   // into an infinite loop with mutually recursive functions.
  94   //
  95   DSGraph *&Graph = DSInfo[&F];
  96   if (Graph) return *Graph;
  97
  98   // Copy the local version into DSInfo...
  99   Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
 100
 101   // Populate the GlobalsGraph with globals from this one.
 102   Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
 103
 104   // Save a copy of the original call nodes for the top-down pass
 105   Graph->saveOrigFunctionCalls();
 106
 107   // Start resolving calls...
 108   std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
 109
 110   DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");
 111
 112   // Add F to the PendingCallers list of each direct callee for use in the
 113   // top-down pass so we don't have to compute this again.  We don't want
 114   // to do it for indirect callees inlined later, so remember which calls
 115   // are in the original FCs set.
 116   std::set<const DSNode*> directCallees;
 117   for (unsigned i = 0; i < FCs.size(); ++i)
 118     directCallees.insert(FCs[i][1]); // ptr to function node
 119
 120   bool Inlined;
 121   do {
 122     Inlined = false;
 123
 124     for (unsigned i = 0; i != FCs.size(); ++i) {
 125       // Copy the call, because inlining graphs may invalidate the FCs vector.
 126       std::vector<DSNodeHandle> Call = FCs[i];
 127
 128       // If the function list is not incomplete...
 129       if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
 130         // Start inlining all of the functions we can... some may not be
 131         // inlinable if they are external...
 132         //
 133         std::vector<GlobalValue*> Callees(Call[1]->getGlobals());
 134
 135         // Loop over the functions, inlining whatever we can...
 136         for (unsigned c = 0; c != Callees.size(); ++c) {
 137           // Must be a function type, so this cast MUST succeed.
 138           Function &FI = cast<Function>(*Callees[c]);
 139           if (&FI == &F) {
 140             // Self recursion... simply link up the formal arguments with the
 141             // actual arguments...
 142
 143             DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
 144
 145             if (Call[0]) // Handle the return value if present...
 146               Graph->RetNode->mergeWith(Call[0]);
 147
 148             // Resolve the arguments in the call to the actual values...
 149             ResolveArguments(Call, F, Graph->getValueMap());
 150
 151             // Erase the entry in the callees vector
 152             Callees.erase(Callees.begin()+c--);
 153           } else if (!FI.isExternal()) {
 154             DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
 155                   << FI.getName() << "\n");
 156
 157             // Get the data structure graph for the called function, closing it
 158             // if possible (which is only impossible in the case of mutual
 159             // recursion...
 160             //
 161             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 162
 163             DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
 164                   << " in: " << F.getName() << "\n");
 165
 166             // Clone the callee's graph into the current graph, keeping
 167             // track of where scalars in the old graph _used_ to point,
 168             // and of the new nodes matching nodes of the old graph.
 169             std::map<Value*, DSNodeHandle> OldValMap;
 170             std::map<const DSNode*, DSNode*> OldNodeMap;
 171
 172             // The clone call may invalidate any of the vectors in the data
 173             // structure graph.  Strip locals and don't copy the list of callers
 174             DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
 175                                               /*StripScalars*/   true,
 176                                               /*StripAllocas*/   true,
 177                                               /*CopyCallers*/    false,
 178                                               /*CopyOrigCalls*/  false);
 179
 180             ResolveArguments(Call, FI, OldValMap);
 181
 182             if (Call[0])  // Handle the return value if present
 183               RetVal->mergeWith(Call[0]);
 184
 185             // Merge global value nodes in the inlined graph with the global
 186             // value nodes in the current graph if there are duplicates.
 187             //
 188             MergeGlobalNodes(*Graph, OldValMap);
 189
 190             // If this was an original call, add F to the PendingCallers list
 191             if (directCallees.find(Call[1]) != directCallees.end())
 192               GI.addCaller(F);
 193
 194             // Erase the entry in the Callees vector
 195             Callees.erase(Callees.begin()+c--);
 196
 197           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
 198                      FI.getName() == "fprintf" || FI.getName() == "open" ||
 199                      FI.getName() == "sprintf") {
 200
 201             // Erase the entry in the globals vector
 202             Callees.erase(Callees.begin()+c--);
 203           }
 204         }
 205
 206         if (Callees.empty()) {         // Inlined all of the function calls?
 207           // Erase the call if it is resolvable...
 208           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
 209           Inlined = true;
 210         } else if (Callees.size() != Call[1]->getGlobals().size()) {
 211           // Was able to inline SOME, but not all of the functions.  Construct a
 212           // new global node here.
 213           //
 214           assert(0 && "Unimpl!");
 215           Inlined = true;
 216         }
 217       }
 218     }
 219
 220     // Recompute the Incomplete markers.  If there are any function calls left
 221     // now that are complete, we must loop!
 222     if (Inlined) {
 223       Graph->maskIncompleteMarkers();
 224       Graph->markIncompleteNodes();
 225       Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ true);
 226     }
 227   } while (Inlined && !FCs.empty());
 228
 229   // Copy any unresolved call nodes into the Globals graph and
 230   // filter out unresolved call nodes inlined from the callee.
 231   if (!FCs.empty())
 232     Graph->GlobalsGraph->cloneCalls(*Graph);
 233
 234   Graph->maskIncompleteMarkers();
 235   Graph->markIncompleteNodes();
 236   Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
 237
 238   DEBUG(std::cerr << "  [BU] Done inlining: " << F.getName() << "\n");
 239
 240   return *Graph;
 241 }