lib/Analysis/DataStructure/TopDownClosure.cpp

   1 //===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===//
   2 //
   3 // This file implements the TDDataStructures class, which represents the
   4 // Top-down Interprocedural closure of the data structure graph over the
   5 // program.  This is useful (but not strictly necessary?) for applications
   6 // 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 using std::map;
  15
  16 static RegisterAnalysis<TDDataStructures>
  17 Y("tddatastructure", "Top-down Data Structure Analysis Closure");
  18 AnalysisID TDDataStructures::ID = Y;
  19
  20 // releaseMemory - If the pass pipeline is done with this pass, we can release
  21 // our memory... here...
  22 //
  23 void TDDataStructures::releaseMemory() {
  24   for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  25          E = DSInfo.end(); I != E; ++I)
  26     delete I->second;
  27
  28   // Empty map so next time memory is released, data structures are not
  29   // re-deleted.
  30   DSInfo.clear();
  31 }
  32
  33 // run - Calculate the top down data structure graphs for each function in the
  34 // program.
  35 //
  36 bool TDDataStructures::run(Module &M) {
  37   // Simply calculate the graphs for each function...
  38   for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
  39     if (!I->isExternal())
  40       calculateGraph(*I);
  41   return false;
  42 }
  43
  44
  45 // ResolveArguments - Resolve the formal and actual arguments for a function
  46 // call by merging the nodes for the actual arguments at the call site Call[]
  47 // (these were copied over from the caller's graph into the callee's graph
  48 // by cloneInto, and the nodes can be found from OldNodeMap) with the
  49 // corresponding nodes for the formal arguments in the callee.
  50 //
  51 static void ResolveArguments(std::vector<DSNodeHandle> &Call,
  52                              Function &callee,
  53                              std::map<Value*, DSNodeHandle> &CalleeValueMap,
  54                              std::map<const DSNode*, DSNode*> OldNodeMap,
  55                              bool ignoreNodeMap) {
  56   // Resolve all of the function formal arguments...
  57   Function::aiterator AI = callee.abegin();
  58   for (unsigned i = 2, e = Call.size(); i != e; ++i) {
  59     // Advance the argument iterator to the first pointer argument...
  60     while (!isa<PointerType>(AI->getType())) ++AI;
  61
  62     // TD ...Merge the formal arg scalar with the actual arg node
  63     DSNode* actualArg = Call[i];
  64     DSNode *nodeForActual = ignoreNodeMap? actualArg : OldNodeMap[actualArg];
  65     assert(nodeForActual && "No node found for actual arg in callee graph!");
  66
  67     DSNode *nodeForFormal = CalleeValueMap[AI]->getLink(0);
  68     if (nodeForFormal)
  69       nodeForFormal->mergeWith(nodeForActual);
  70     ++AI;
  71   }
  72 }
  73
  74 // MergeGlobalNodes - Merge all existing global nodes with globals
  75 // inlined from the callee or with globals from the GlobalsGraph.
  76 //
  77 static void MergeGlobalNodes(DSGraph& Graph,
  78                              map<Value*, DSNodeHandle> &OldValMap) {
  79   map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
  80   for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
  81        I != E; ++I)
  82     if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
  83       map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
  84       if (NHI != OldValMap.end())       // was it inlined from the callee?
  85         I->second->mergeWith(NHI->second);
  86       else                              // get it from the GlobalsGraph
  87         I->second->mergeWith(Graph.cloneGlobalInto(GV));
  88     }
  89
  90   // Add unused inlined global nodes into the value map
  91   for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
  92          E = OldValMap.end(); I != E; ++I)
  93     if (isa<GlobalValue>(I->first)) {
  94       DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
  95       if (NH == 0)
  96         NH = I->second;                     // Add the one just inlined.
  97     }
  98 }
  99
 100 // Helper function to push a caller's graph into the calleeGraph,
 101 // once per call between the caller and the callee.
 102 // Remove each such resolved call from the OrigFunctionCalls vector.
 103 // NOTE: This may produce O(N^2) behavior because it uses linear search
 104 // through the vector OrigFunctionCalls to find all calls to this callee.
 105 //
 106 void TDDataStructures::pushGraphIntoCallee(DSGraph &callerGraph,
 107                                            DSGraph &calleeGraph,
 108                                  std::map<Value*, DSNodeHandle> &OldValMap,
 109                                  std::map<const DSNode*, DSNode*> &OldNodeMap) {
 110
 111   Function& caller = callerGraph.getFunction();
 112
 113   // Loop over all function calls in the caller to find those to this callee
 114   std::vector<std::vector<DSNodeHandle> >& FunctionCalls =
 115     callerGraph.getOrigFunctionCalls();
 116
 117   for (unsigned i = 0, ei = FunctionCalls.size(); i != ei; ++i) {
 118
 119     std::vector<DSNodeHandle>& Call = FunctionCalls[i];
 120     assert(Call.size() >= 2 && "No function pointer in Call?");
 121     DSNodeHandle& callee = Call[1];
 122     std::vector<GlobalValue*> funcPtrs(callee->getGlobals());
 123
 124     // Loop over the function pointers in the call, looking for the callee
 125     for (unsigned f = 0; f != funcPtrs.size(); ++f) {
 126
 127       // Must be a function type, so this cast MUST succeed.
 128       Function &callee = cast<Function>(*funcPtrs[f]);
 129       if (&callee != &calleeGraph.getFunction())
 130         continue;
 131
 132       // Found a call to the callee.  Inline its graph
 133       // copy caller pointer because inlining may modify the callers vector
 134
 135       // Merge actual arguments from the caller with formals in the callee.
 136       // Don't use the old->new node map if this is a self-recursive call.
 137       ResolveArguments(Call, callee, calleeGraph.getValueMap(), OldNodeMap,
 138                        /*ignoreNodeMap*/ &caller == &callee);
 139
 140       // If its not a self-recursive call, merge global nodes in the inlined
 141       // graph with the corresponding global nodes in the current graph
 142       if (&caller != &callee)
 143         MergeGlobalNodes(calleeGraph, OldValMap);
 144
 145       // Merge returned node in the caller with the "return" node in callee
 146       if (Call[0])
 147         calleeGraph.getRetNode()->mergeWith(OldNodeMap[Call[0]]);
 148
 149       // Erase the entry in the globals vector
 150       funcPtrs.erase(funcPtrs.begin()+f--);
 151
 152     } // for each function pointer in the call node
 153   } // for each original call node
 154 }
 155
 156
 157 DSGraph &TDDataStructures::calculateGraph(Function &F) {
 158   // Make sure this graph has not already been calculated, or that we don't get
 159   // into an infinite loop with mutually recursive functions.
 160   //
 161   DSGraph *&Graph = DSInfo[&F];
 162   if (Graph) return *Graph;
 163
 164   // Copy the local version into DSInfo...
 165   DSGraph& BUGraph = getAnalysis<BUDataStructures>().getDSGraph(F);
 166   Graph = new DSGraph(BUGraph);
 167
 168   // Find the callers of this function recorded during the BU pass
 169   std::set<Function*> &PendingCallers = BUGraph.getPendingCallers();
 170
 171   DEBUG(std::cerr << "  [TD] Inlining callers for: " << F.getName() << "\n");
 172
 173   for (std::set<Function*>::iterator I=PendingCallers.begin(),
 174          E=PendingCallers.end(); I != E; ++I) {
 175     Function& caller = **I;
 176     assert(! caller.isExternal() && "Externals unexpected in callers list");
 177
 178     DEBUG(std::cerr << "\t [TD] Inlining " << caller.getName()
 179                     << " into callee: " << F.getName() << "\n");
 180
 181     // These two maps keep track of where scalars in the old graph _used_
 182     // to point to, and of new nodes matching nodes of the old graph.
 183     // These remain empty if no other graph is inlined (i.e., self-recursive).
 184     std::map<const DSNode*, DSNode*> OldNodeMap;
 185     std::map<Value*, DSNodeHandle> OldValMap;
 186
 187     if (&caller == &F) {
 188       // Self-recursive call: this can happen after a cycle of calls is inlined.
 189       pushGraphIntoCallee(*Graph, *Graph, OldValMap, OldNodeMap);
 190     }
 191     else {
 192       // Recursively compute the graph for the caller.  That should
 193       // be fully resolved except if there is mutual recursion...
 194       //
 195       DSGraph &callerGraph = calculateGraph(caller);  // Graph to inline
 196
 197       DEBUG(std::cerr << "\t\t[TD] Got graph for " << caller.getName()
 198                       << " in: " << F.getName() << "\n");
 199
 200       // Clone the caller's graph into the current graph, keeping
 201       // track of where scalars in the old graph _used_ to point...
 202       // Do this here because it only needs to happens once for each caller!
 203       // Strip scalars but not allocas since they are visible in callee.
 204       //
 205       DSNode *RetVal = Graph->cloneInto(callerGraph, OldValMap, OldNodeMap,
 206                                         /*StripScalars*/   true,
 207                                         /*StripAllocas*/   false,
 208                                         /*CopyCallers*/    true,
 209                                         /*CopyOrigCalls*/  false);
 210
 211       pushGraphIntoCallee(callerGraph, *Graph, OldValMap, OldNodeMap);
 212     }
 213   }
 214
 215   // Recompute the Incomplete markers and eliminate unreachable nodes.
 216   Graph->maskIncompleteMarkers();
 217   Graph->markIncompleteNodes(/*markFormals*/ ! F.hasInternalLinkage()
 218                              /*&& FIXME: NEED TO CHECK IF ALL CALLERS FOUND!*/);
 219   Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
 220
 221   DEBUG(std::cerr << "  [TD] Done inlining callers for: "
 222                   << F.getName() << "\n");
 223
 224   return *Graph;
 225 }