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/Analysis/DSGraph.h"
  12 #include "llvm/Module.h"
  13 #include "llvm/DerivedTypes.h"
  14 #include "Support/Statistic.h"
  15 using std::map;
  16 using std::vector;
  17
  18 static RegisterAnalysis<TDDataStructures>
  19 Y("tddatastructure", "Top-down Data Structure Analysis Closure");
  20
  21 // releaseMemory - If the pass pipeline is done with this pass, we can release
  22 // our memory... here...
  23 //
  24 void TDDataStructures::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 top down data structure graphs for each function in the
  35 // program.
  36 //
  37 bool TDDataStructures::run(Module &M) {
  38   // Simply calculate the graphs for each function...
  39   for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
  40     if (!I->isExternal())
  41       calculateGraph(*I);
  42   return false;
  43 }
  44
  45 #if 0
  46
  47 // MergeGlobalNodes - Merge all existing global nodes with globals
  48 // inlined from the callee or with globals from the GlobalsGraph.
  49 //
  50 static void MergeGlobalNodes(DSGraph &Graph,
  51                              map<Value*, DSNodeHandle> &OldValMap) {
  52   map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
  53   for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
  54        I != E; ++I)
  55     if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
  56       map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
  57       if (NHI != OldValMap.end())       // was it inlined from the callee?
  58         I->second->mergeWith(NHI->second);
  59       else                              // get it from the GlobalsGraph
  60         I->second->mergeWith(Graph.cloneGlobalInto(GV));
  61     }
  62
  63   // Add unused inlined global nodes into the value map
  64   for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
  65          E = OldValMap.end(); I != E; ++I)
  66     if (isa<GlobalValue>(I->first)) {
  67       DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
  68       if (NH == 0)
  69         NH = I->second;                     // Add the one just inlined.
  70     }
  71 }
  72
  73 #endif
  74
  75 /// ResolveCallSite - This method is used to link the actual arguments together
  76 /// with the formal arguments for a function call in the top-down closure.  This
  77 /// method assumes that the call site arguments have been mapped into nodes
  78 /// local to the specified graph.
  79 ///
  80 void TDDataStructures::ResolveCallSite(DSGraph &Graph,
  81                                    const BUDataStructures::CallSite &CallSite) {
  82   // Resolve all of the function formal arguments...
  83   Function &F = Graph.getFunction();
  84   Function::aiterator AI = F.abegin();
  85
  86   for (unsigned i = 2, e = CallSite.Context.size(); i != e; ++i, ++AI) {
  87     // Advance the argument iterator to the first pointer argument...
  88     while (!DataStructureAnalysis::isPointerType(AI->getType())) ++AI;
  89
  90     // TD ...Merge the formal arg scalar with the actual arg node
  91     DSNodeHandle &NodeForFormal = Graph.getNodeForValue(AI);
  92     if (NodeForFormal.getNode())
  93       NodeForFormal.mergeWith(CallSite.Context[i]);
  94   }
  95
  96   // Merge returned node in the caller with the "return" node in callee
  97   if (CallSite.Context[0].getNode() && Graph.getRetNode().getNode())
  98     Graph.getRetNode().mergeWith(CallSite.Context[0]);
  99 }
 100
 101 DSGraph &TDDataStructures::calculateGraph(Function &F) {
 102   // Make sure this graph has not already been calculated, or that we don't get
 103   // into an infinite loop with mutually recursive functions.
 104   //
 105   DSGraph *&Graph = DSInfo[&F];
 106   if (Graph) return *Graph;
 107
 108   BUDataStructures &BU = getAnalysis<BUDataStructures>();
 109   DSGraph &BUGraph = BU.getDSGraph(F);
 110   Graph = new DSGraph(BUGraph);
 111
 112   const vector<BUDataStructures::CallSite> *CallSitesP = BU.getCallSites(F);
 113   if (CallSitesP == 0) {
 114     DEBUG(std::cerr << "  [TD] No callers for: " << F.getName() << "\n");
 115     return *Graph;  // If no call sites, the graph is the same as the BU graph!
 116   }
 117
 118   // Loop over all call sites of this function, merging each one into this
 119   // graph.
 120   //
 121   DEBUG(std::cerr << "  [TD] Inlining callers for: " << F.getName() << "\n");
 122   const vector<BUDataStructures::CallSite> &CallSites = *CallSitesP;
 123   for (unsigned c = 0, ce = CallSites.size(); c != ce; ++c) {
 124     const BUDataStructures::CallSite &CallSite = CallSites[c];  // Copy
 125     Function &Caller = *CallSite.Caller;
 126     assert(!Caller.isExternal() && "Externals function cannot 'call'!");
 127
 128     DEBUG(std::cerr << "\t [TD] Inlining caller #" << c << " '"
 129           << Caller.getName() << "' into callee: " << F.getName() << "\n");
 130
 131     if (&Caller == &F) {
 132       // Self-recursive call: this can happen after a cycle of calls is inlined.
 133       ResolveCallSite(*Graph, CallSite);
 134     } else {
 135       // Recursively compute the graph for the Caller.  That should
 136       // be fully resolved except if there is mutual recursion...
 137       //
 138       DSGraph &CG = calculateGraph(Caller);  // Graph to inline
 139
 140       DEBUG(std::cerr << "\t\t[TD] Got graph for " << Caller.getName()
 141                       << " in: " << F.getName() << "\n");
 142
 143       // These two maps keep track of where scalars in the old graph _used_
 144       // to point to, and of new nodes matching nodes of the old graph.
 145       std::map<Value*, DSNodeHandle> OldValMap;
 146       std::map<const DSNode*, DSNode*> OldNodeMap;
 147
 148       // Clone the Caller's graph into the current graph, keeping
 149       // track of where scalars in the old graph _used_ to point...
 150       // Do this here because it only needs to happens once for each Caller!
 151       // Strip scalars but not allocas since they are alive in callee.
 152       //
 153       DSNodeHandle RetVal = Graph->cloneInto(CG, OldValMap, OldNodeMap,
 154                                              /*StripScalars*/ true,
 155                                              /*StripAllocas*/ false,
 156                                              /*CopyCallers*/  true,
 157                                              /*CopyOrigCalls*/false);
 158
 159       // Make a temporary copy of the call site, and transform the argument node
 160       // pointers.
 161       BUDataStructures::CallSite TmpCallSite = CallSite;
 162       for (unsigned i = 0, e = CallSite.Context.size(); i != e; ++i) {
 163         const DSNode *OldNode = TmpCallSite.Context[i].getNode();
 164         TmpCallSite.Context[i].setNode(OldNodeMap[OldNode]);
 165       }
 166
 167       ResolveCallSite(*Graph, CallSite);
 168
 169 #if 0
 170       // If its not a self-recursive call, merge global nodes in the inlined
 171       // graph with the corresponding global nodes in the current graph
 172       if (&caller != &callee)
 173         MergeGlobalNodes(calleeGraph, OldValMap);
 174 #endif
 175     }
 176   }
 177
 178
 179   // Recompute the Incomplete markers and eliminate unreachable nodes.
 180   Graph->maskIncompleteMarkers();
 181   Graph->markIncompleteNodes(/*markFormals*/ !F.hasInternalLinkage()
 182                              /*&& FIXME: NEED TO CHECK IF ALL CALLERS FOUND!*/);
 183 #if 0
 184   Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
 185 #endif
 186
 187   DEBUG(std::cerr << "  [TD] Done inlining callers for: " << F.getName() << " ["
 188         << Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
 189         << "]\n");
 190
 191   return *Graph;
 192 }