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
  16 static RegisterAnalysis<TDDataStructures>
  17 Y("tddatastructure", "Top-down Data Structure Analysis Closure");
  18
  19 // releaseMemory - If the pass pipeline is done with this pass, we can release
  20 // our memory... here...
  21 //
  22 void TDDataStructures::releaseMemory() {
  23   for (std::map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  24          E = DSInfo.end(); I != E; ++I)
  25     delete I->second;
  26
  27   // Empty map so next time memory is released, data structures are not
  28   // re-deleted.
  29   DSInfo.clear();
  30 }
  31
  32 // run - Calculate the top down data structure graphs for each function in the
  33 // program.
  34 //
  35 bool TDDataStructures::run(Module &M) {
  36   // Simply calculate the graphs for each function...
  37   for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
  38     if (!I->isExternal())
  39       calculateGraph(*I);
  40   return false;
  41 }
  42
  43 /// ResolveCallSite - This method is used to link the actual arguments together
  44 /// with the formal arguments for a function call in the top-down closure.  This
  45 /// method assumes that the call site arguments have been mapped into nodes
  46 /// local to the specified graph.
  47 ///
  48 void TDDataStructures::ResolveCallSite(DSGraph &Graph,
  49                                        const DSCallSite &CallSite) {
  50   // Resolve all of the function formal arguments...
  51   Function &F = Graph.getFunction();
  52   Function::aiterator AI = F.abegin();
  53
  54   for (unsigned i = 0, e = CallSite.getNumPtrArgs(); i != e; ++i, ++AI) {
  55     // Advance the argument iterator to the first pointer argument...
  56     while (!DataStructureAnalysis::isPointerType(AI->getType())) ++AI;
  57
  58     // TD ...Merge the formal arg scalar with the actual arg node
  59     DSNodeHandle &NodeForFormal = Graph.getNodeForValue(AI);
  60     if (NodeForFormal.getNode())
  61       NodeForFormal.mergeWith(CallSite.getPtrArg(i));
  62   }
  63
  64   // Merge returned node in the caller with the "return" node in callee
  65   if (CallSite.getRetVal().getNode() && Graph.getRetNode().getNode())
  66     Graph.getRetNode().mergeWith(CallSite.getRetVal());
  67 }
  68
  69
  70 static DSNodeHandle copyHelper(const DSNodeHandle* fromNode,
  71                                std::map<const DSNode*, DSNode*> *NodeMap) {
  72   return DSNodeHandle((*NodeMap)[fromNode->getNode()], fromNode->getOffset());
  73 }
  74
  75
  76 DSGraph &TDDataStructures::calculateGraph(Function &F) {
  77   // Make sure this graph has not already been calculated, or that we don't get
  78   // into an infinite loop with mutually recursive functions.
  79   //
  80   DSGraph *&Graph = DSInfo[&F];
  81   if (Graph) return *Graph;
  82
  83   BUDataStructures &BU = getAnalysis<BUDataStructures>();
  84   DSGraph &BUGraph = BU.getDSGraph(F);
  85   Graph = new DSGraph(BUGraph);
  86
  87   const std::vector<DSCallSite> *CallSitesP = BU.getCallSites(F);
  88   if (CallSitesP == 0) {
  89     DEBUG(std::cerr << "  [TD] No callers for: " << F.getName() << "\n");
  90     return *Graph;  // If no call sites, the graph is the same as the BU graph!
  91   }
  92
  93   // Loop over all call sites of this function, merging each one into this
  94   // graph.
  95   //
  96   DEBUG(std::cerr << "  [TD] Inlining callers for: " << F.getName() << "\n");
  97   const std::vector<DSCallSite> &CallSites = *CallSitesP;
  98   for (unsigned c = 0, ce = CallSites.size(); c != ce; ++c) {
  99     const DSCallSite &CallSite = CallSites[c];  // Copy
 100     Function &Caller = CallSite.getCaller();
 101     assert(!Caller.isExternal() && "Externals function cannot 'call'!");
 102
 103     DEBUG(std::cerr << "\t [TD] Inlining caller #" << c << " '"
 104           << Caller.getName() << "' into callee: " << F.getName() << "\n");
 105
 106     if (&Caller == &F) {
 107       // Self-recursive call: this can happen after a cycle of calls is inlined.
 108       ResolveCallSite(*Graph, CallSite);
 109     } else {
 110       // Recursively compute the graph for the Caller.  That should
 111       // be fully resolved except if there is mutual recursion...
 112       //
 113       DSGraph &CG = calculateGraph(Caller);  // Graph to inline
 114
 115       DEBUG(std::cerr << "\t\t[TD] Got graph for " << Caller.getName()
 116                       << " in: " << F.getName() << "\n");
 117
 118       // These two maps keep track of where scalars in the old graph _used_
 119       // to point to, and of new nodes matching nodes of the old graph.
 120       std::map<Value*, DSNodeHandle> OldValMap;
 121       std::map<const DSNode*, DSNode*> OldNodeMap;
 122
 123       // Clone the Caller's graph into the current graph, keeping
 124       // track of where scalars in the old graph _used_ to point...
 125       // Do this here because it only needs to happens once for each Caller!
 126       // Strip scalars but not allocas since they are alive in callee.
 127       //
 128       DSNodeHandle RetVal = Graph->cloneInto(CG, OldValMap, OldNodeMap,
 129                                              /*StripScalars*/ true,
 130                                              /*StripAllocas*/ false,
 131                                              /*CopyCallers*/  true,
 132                                              /*CopyOrigCalls*/false);
 133
 134       // Make a temporary copy of the call site, and transform the argument node
 135       // pointers.
 136       DSCallSite TmpCallSite(CallSite, std::bind2nd(std::ptr_fun(&copyHelper),
 137                                                     &OldNodeMap));
 138       ResolveCallSite(*Graph, CallSite);
 139     }
 140   }
 141
 142   // Recompute the Incomplete markers and eliminate unreachable nodes.
 143   Graph->maskIncompleteMarkers();
 144   Graph->markIncompleteNodes(/*markFormals*/ !F.hasInternalLinkage()
 145                              /*&& FIXME: NEED TO CHECK IF ALL CALLERS FOUND!*/);
 146   Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
 147
 148   DEBUG(std::cerr << "  [TD] Done inlining callers for: " << F.getName() << " ["
 149         << Graph->getGraphSize() << "+" << Graph->getFunctionCalls().size()
 150         << "]\n");
 151
 152   return *Graph;
 153 }