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/Statistic.h"
  14 #include "DSCallSiteIterator.h"
  15
  16 namespace {
  17   RegisterAnalysis<TDDataStructures>   // Register the pass
  18   Y("tddatastructure", "Top-down Data Structure Analysis");
  19
  20   Statistic<> NumTDInlines("tddatastructures", "Number of graphs inlined");
  21 }
  22
  23 /// FunctionHasCompleteArguments - This function returns true if it is safe not
  24 /// to mark arguments to the function complete.
  25 ///
  26 /// FIXME: Need to check if all callers have been found, or rather if a
  27 /// funcpointer escapes!
  28 ///
  29 static bool FunctionHasCompleteArguments(Function &F) {
  30   return F.hasInternalLinkage();
  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   BUDataStructures &BU = getAnalysis<BUDataStructures>();
  38   GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
  39
  40   // Figure out which functions must not mark their arguments complete because
  41   // they are accessible outside this compilation unit.
  42   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  43     if (!FunctionHasCompleteArguments(*I))
  44       ArgsRemainIncomplete.insert(I);
  45
  46   // We want to traverse the call graph in reverse post-order.  To do this, we
  47   // calculate a post-order traversal, then reverse it.
  48   hash_set<DSGraph*> VisitedGraph;
  49   std::vector<DSGraph*> PostOrder;
  50   const BUDataStructures::ActualCalleesTy &ActualCallees =
  51     getAnalysis<BUDataStructures>().getActualCallees();
  52
  53   // Calculate top-down from main...
  54   if (Function *F = M.getMainFunction())
  55     ComputePostOrder(*F, VisitedGraph, PostOrder, ActualCallees);
  56
  57   // Next calculate the graphs for each unreachable function...
  58   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  59     ComputePostOrder(*I, VisitedGraph, PostOrder, ActualCallees);
  60
  61   VisitedGraph.clear();   // Release memory!
  62
  63   // Visit each of the graphs in reverse post-order now!
  64   while (!PostOrder.empty()) {
  65     inlineGraphIntoCallees(*PostOrder.back());
  66     PostOrder.pop_back();
  67   }
  68
  69   ArgsRemainIncomplete.clear();
  70   return false;
  71 }
  72
  73
  74 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
  75   DSGraph *&G = DSInfo[&F];
  76   if (G == 0) { // Not created yet?  Clone BU graph...
  77     G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
  78     G->getAuxFunctionCalls().clear();
  79     G->setPrintAuxCalls();
  80     G->setGlobalsGraph(GlobalsGraph);
  81   }
  82   return *G;
  83 }
  84
  85
  86 void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
  87                                         std::vector<DSGraph*> &PostOrder,
  88                       const BUDataStructures::ActualCalleesTy &ActualCallees) {
  89   if (F.isExternal()) return;
  90   DSGraph &G = getOrCreateDSGraph(F);
  91   if (Visited.count(&G)) return;
  92   Visited.insert(&G);
  93
  94   // Recursively traverse all of the callee graphs.
  95   const std::vector<DSCallSite> &FunctionCalls = G.getFunctionCalls();
  96
  97   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) {
  98     std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
  99       BUDataStructures::ActualCalleesTy::const_iterator>
 100          IP = ActualCallees.equal_range(&FunctionCalls[i].getCallInst());
 101
 102     for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 103          I != IP.second; ++I)
 104       ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
 105   }
 106
 107   PostOrder.push_back(&G);
 108 }
 109
 110
 111
 112
 113
 114 // releaseMemory - If the pass pipeline is done with this pass, we can release
 115 // our memory... here...
 116 //
 117 // FIXME: This should be releaseMemory and will work fine, except that LoadVN
 118 // has no way to extend the lifetime of the pass, which screws up ds-aa.
 119 //
 120 void TDDataStructures::releaseMyMemory() {
 121   for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
 122          E = DSInfo.end(); I != E; ++I) {
 123     I->second->getReturnNodes().erase(I->first);
 124     if (I->second->getReturnNodes().empty())
 125       delete I->second;
 126   }
 127
 128   // Empty map so next time memory is released, data structures are not
 129   // re-deleted.
 130   DSInfo.clear();
 131   delete GlobalsGraph;
 132   GlobalsGraph = 0;
 133 }
 134
 135 void TDDataStructures::inlineGraphIntoCallees(DSGraph &Graph) {
 136   // Recompute the Incomplete markers and eliminate unreachable nodes.
 137   Graph.removeTriviallyDeadNodes();
 138   Graph.maskIncompleteMarkers();
 139
 140   // If any of the functions has incomplete incoming arguments, don't mark any
 141   // of them as complete.
 142   bool HasIncompleteArgs = false;
 143   const DSGraph::ReturnNodesTy &GraphReturnNodes = Graph.getReturnNodes();
 144   for (DSGraph::ReturnNodesTy::const_iterator I = GraphReturnNodes.begin(),
 145          E = GraphReturnNodes.end(); I != E; ++I)
 146     if (ArgsRemainIncomplete.count(I->first)) {
 147       HasIncompleteArgs = true;
 148       break;
 149     }
 150
 151   // Now fold in the necessary globals from the GlobalsGraph.  A global G
 152   // must be folded in if it exists in the current graph (i.e., is not dead)
 153   // and it was not inlined from any of my callers.  If it was inlined from
 154   // a caller, it would have been fully consistent with the GlobalsGraph
 155   // in the caller so folding in is not necessary.  Otherwise, this node came
 156   // solely from this function's BU graph and so has to be made consistent.
 157   //
 158   Graph.updateFromGlobalGraph();
 159
 160   // Recompute the Incomplete markers.  Depends on whether args are complete
 161   unsigned Flags
 162     = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs;
 163   Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
 164
 165   // Delete dead nodes.  Treat globals that are unreachable as dead also.
 166   Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
 167
 168   // We are done with computing the current TD Graph! Now move on to
 169   // inlining the current graph into the graphs for its callees, if any.
 170   //
 171   const std::vector<DSCallSite> &FunctionCalls = Graph.getFunctionCalls();
 172   if (FunctionCalls.empty()) {
 173     DEBUG(std::cerr << "  [TD] No callees for: " << Graph.getFunctionNames()
 174                     << "\n");
 175     return;
 176   }
 177
 178   // Now that we have information about all of the callees, propagate the
 179   // current graph into the callees.  Clone only the reachable subgraph at
 180   // each call-site, not the entire graph (even though the entire graph
 181   // would be cloned only once, this should still be better on average).
 182   //
 183   DEBUG(std::cerr << "  [TD] Inlining '" << Graph.getFunctionNames() <<"' into "
 184                   << FunctionCalls.size() << " call nodes.\n");
 185
 186   const BUDataStructures::ActualCalleesTy &ActualCallees =
 187     getAnalysis<BUDataStructures>().getActualCallees();
 188
 189   // Loop over all the call sites and all the callees at each call site.
 190   // Clone and merge the reachable subgraph from the call into callee's graph.
 191   //
 192   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) {
 193     // For each function in the invoked function list at this call site...
 194     std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
 195       BUDataStructures::ActualCalleesTy::const_iterator>
 196           IP = ActualCallees.equal_range(&FunctionCalls[i].getCallInst());
 197
 198     // Multiple callees may have the same graph, so try to inline and merge
 199     // only once for each <callSite,calleeGraph> pair, not once for each
 200     // <callSite,calleeFunction> pair; the latter will be correct but slower.
 201     hash_set<DSGraph*> GraphsSeen;
 202
 203     // Loop over each actual callee at this call site
 204     for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 205          I != IP.second; ++I) {
 206       DSGraph& CalleeGraph = getDSGraph(*I->second);
 207       assert(&CalleeGraph != &Graph && "TD need not inline graph into self!");
 208
 209       // if this callee graph is already done at this site, skip this callee
 210       if (GraphsSeen.find(&CalleeGraph) != GraphsSeen.end())
 211         continue;
 212       GraphsSeen.insert(&CalleeGraph);
 213
 214       // Get the root nodes for cloning the reachable subgraph into each callee:
 215       // -- all global nodes that appear in both the caller and the callee
 216       // -- return value at this call site, if any
 217       // -- actual arguments passed at this call site
 218       // -- callee node at this call site, if this is an indirect call (this may
 219       //    not be needed for merging, but allows us to create CS and therefore
 220       //    simplify the merging below).
 221       hash_set<const DSNode*> RootNodeSet;
 222       for (DSGraph::ScalarMapTy::const_iterator
 223              SI = CalleeGraph.getScalarMap().begin(),
 224              SE = CalleeGraph.getScalarMap().end(); SI != SE; ++SI)
 225         if (GlobalValue* GV = dyn_cast<GlobalValue>(SI->first)) {
 226           DSGraph::ScalarMapTy::const_iterator GI=Graph.getScalarMap().find(GV);
 227           if (GI != Graph.getScalarMap().end())
 228             RootNodeSet.insert(GI->second.getNode());
 229         }
 230
 231       if (const DSNode* RetNode = FunctionCalls[i].getRetVal().getNode())
 232         RootNodeSet.insert(RetNode);
 233
 234       for (unsigned j=0, N=FunctionCalls[i].getNumPtrArgs(); j < N; ++j)
 235         if (const DSNode* ArgTarget = FunctionCalls[i].getPtrArg(j).getNode())
 236           RootNodeSet.insert(ArgTarget);
 237
 238       if (FunctionCalls[i].isIndirectCall())
 239         RootNodeSet.insert(FunctionCalls[i].getCalleeNode());
 240
 241       DEBUG(std::cerr << "     [TD] Resolving arguments for callee graph '"
 242             << CalleeGraph.getFunctionNames()
 243             << "': " << I->second->getFunctionType()->getNumParams()
 244             << " args\n          at call site (DSCallSite*) 0x"
 245             << &FunctionCalls[i] << "\n");
 246
 247       DSGraph::NodeMapTy NodeMapInCallee; // map from nodes to clones in callee
 248       DSGraph::NodeMapTy CompletedMap;    // unused map for nodes not to do
 249       CalleeGraph.cloneReachableSubgraph(Graph, RootNodeSet,
 250                                          NodeMapInCallee, CompletedMap,
 251                                          DSGraph::StripModRefBits |
 252                                          DSGraph::KeepAllocaBit);
 253
 254       // Transform our call site info into the cloned version for CalleeGraph
 255       DSCallSite CS(FunctionCalls[i], NodeMapInCallee);
 256
 257       // Get the formal argument and return nodes for the called function
 258       // and merge them with the cloned subgraph.  Global nodes were merged
 259       // already by cloneReachableSubgraph() above.
 260       CalleeGraph.getCallSiteForArguments(*I->second).mergeWith(CS);
 261
 262       ++NumTDInlines;
 263     }
 264   }
 265
 266   DEBUG(std::cerr << "  [TD] Done inlining into callees for: "
 267         << Graph.getFunctionNames() << " [" << Graph.getGraphSize() << "+"
 268         << Graph.getFunctionCalls().size() << "]\n");
 269 }
 270