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   // Calculate top-down from main...
  47   if (Function *F = M.getMainFunction())
  48     calculateGraphFrom(*F);
  49
  50   // Next calculate the graphs for each function unreachable function...
  51   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  52     if (!I->isExternal() && !DSInfo.count(I))
  53       calculateGraphFrom(*I);
  54
  55   ArgsRemainIncomplete.clear();
  56   return false;
  57 }
  58
  59 // releaseMemory - If the pass pipeline is done with this pass, we can release
  60 // our memory... here...
  61 //
  62 // FIXME: This should be releaseMemory and will work fine, except that LoadVN
  63 // has no way to extend the lifetime of the pass, which screws up ds-aa.
  64 //
  65 void TDDataStructures::releaseMyMemory() {
  66   for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
  67          E = DSInfo.end(); I != E; ++I) {
  68     I->second->getReturnNodes().erase(I->first);
  69     if (I->second->getReturnNodes().empty())
  70       delete I->second;
  71   }
  72
  73   // Empty map so next time memory is released, data structures are not
  74   // re-deleted.
  75   DSInfo.clear();
  76   delete GlobalsGraph;
  77   GlobalsGraph = 0;
  78 }
  79
  80
  81 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
  82   DSGraph *&G = DSInfo[&F];
  83   if (G == 0) { // Not created yet?  Clone BU graph...
  84     G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
  85     G->getAuxFunctionCalls().clear();
  86     G->setPrintAuxCalls();
  87     G->setGlobalsGraph(GlobalsGraph);
  88   }
  89   return *G;
  90 }
  91
  92
  93 void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
  94                                         std::vector<DSGraph*> &PostOrder,
  95                       const BUDataStructures::ActualCalleesTy &ActualCallees) {
  96   if (F.isExternal()) return;
  97   DSGraph &G = getOrCreateDSGraph(F);
  98   if (Visited.count(&G)) return;
  99   Visited.insert(&G);
 100
 101   // Recursively traverse all of the callee graphs.
 102   const std::vector<DSCallSite> &FunctionCalls = G.getFunctionCalls();
 103
 104   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) {
 105     std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
 106       BUDataStructures::ActualCalleesTy::const_iterator>
 107          IP = ActualCallees.equal_range(&FunctionCalls[i].getCallInst());
 108
 109     for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 110          I != IP.second; ++I)
 111       ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
 112   }
 113
 114   PostOrder.push_back(&G);
 115 }
 116
 117
 118
 119 void TDDataStructures::calculateGraphFrom(Function &F) {
 120   // We want to traverse the call graph in reverse post-order.  To do this, we
 121   // calculate a post-order traversal, then reverse it.
 122   hash_set<DSGraph*> VisitedGraph;
 123   std::vector<DSGraph*> PostOrder;
 124   ComputePostOrder(F, VisitedGraph, PostOrder,
 125                    getAnalysis<BUDataStructures>().getActualCallees());
 126   VisitedGraph.clear();   // Release memory!
 127
 128   // Visit each of the graphs in reverse post-order now!
 129   while (!PostOrder.empty()) {
 130     inlineGraphIntoCallees(*PostOrder.back());
 131     PostOrder.pop_back();
 132   }
 133 }
 134
 135
 136 void TDDataStructures::inlineGraphIntoCallees(DSGraph &Graph) {
 137   // Recompute the Incomplete markers and eliminate unreachable nodes.
 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   unsigned Flags
 152     = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs;
 153   Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
 154   Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
 155
 156   const std::vector<DSCallSite> &FunctionCalls = Graph.getFunctionCalls();
 157   if (FunctionCalls.empty()) {
 158     DEBUG(std::cerr << "  [TD] No callees for: " << Graph.getFunctionNames()
 159                     << "\n");
 160     return;
 161   }
 162
 163   // Now that we have information about all of the callees, propagate the
 164   // current graph into the callees.
 165   //
 166   DEBUG(std::cerr << "  [TD] Inlining '" << Graph.getFunctionNames() <<"' into "
 167                   << FunctionCalls.size() << " call nodes.\n");
 168
 169   const BUDataStructures::ActualCalleesTy &ActualCallees =
 170     getAnalysis<BUDataStructures>().getActualCallees();
 171
 172   // Only inline this function into each real callee once.  After that, just
 173   // merge information into arguments...
 174   hash_map<DSGraph*, DSGraph::NodeMapTy> InlinedSites;
 175
 176   // Loop over all the callees... cloning this graph into each one exactly once,
 177   // keeping track of the node mapping information...
 178   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) {
 179     // Inline this graph into each function in the invoked function list.
 180     std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
 181       BUDataStructures::ActualCalleesTy::const_iterator>
 182           IP = ActualCallees.equal_range(&FunctionCalls[i].getCallInst());
 183
 184     int NumArgs = 0;
 185     if (IP.first != IP.second) {
 186       NumArgs = IP.first->second->getFunctionType()->getNumParams();
 187       for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 188            I != IP.second; ++I)
 189         if (NumArgs != (int)I->second->getFunctionType()->getNumParams()) {
 190           NumArgs = -1;
 191           break;
 192         }
 193     }
 194
 195     if (NumArgs == -1) {
 196       std::cerr << "ERROR: NONSAME NUMBER OF ARGUMENTS TO CALLEES\n";
 197     }
 198
 199     for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 200          I != IP.second; ++I) {
 201       DSGraph &CG = getDSGraph(*I->second);
 202       assert(&CG != &Graph && "TD need not inline graph into self!");
 203
 204       if (!InlinedSites.count(&CG)) {  // If we haven't already inlined into CG
 205         DEBUG(std::cerr << "     [TD] Inlining graph into callee graph '"
 206               << CG.getFunctionNames() << "': " << I->second->getFunctionType()->getNumParams() << " args\n");
 207         DSGraph::ScalarMapTy OldScalarMap;
 208         DSGraph::ReturnNodesTy ReturnNodes;
 209         CG.cloneInto(Graph, OldScalarMap, ReturnNodes, InlinedSites[&CG],
 210                      DSGraph::StripModRefBits | DSGraph::KeepAllocaBit |
 211                      DSGraph::DontCloneCallNodes |
 212                      DSGraph::DontCloneAuxCallNodes);
 213         ++NumTDInlines;
 214       }
 215     }
 216   }
 217
 218   // Loop over all the callees...
 219   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) {
 220     // Inline this graph into each function in the invoked function list.
 221     std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
 222       BUDataStructures::ActualCalleesTy::const_iterator>
 223           IP = ActualCallees.equal_range(&FunctionCalls[i].getCallInst());
 224     for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
 225          I != IP.second; ++I) {
 226       DSGraph &CG = getDSGraph(*I->second);
 227       DEBUG(std::cerr << "     [TD] Resolving arguments for callee graph '"
 228                       << CG.getFunctionNames() << "'\n");
 229
 230       // Transform our call site information into the cloned version for CG
 231       DSCallSite CS(FunctionCalls[i], InlinedSites[&CG]);
 232
 233       // Get the arguments bindings for the called function in CG... and merge
 234       // them with the cloned graph.
 235       CG.getCallSiteForArguments(*I->second).mergeWith(CS);
 236     }
 237   }
 238
 239   DEBUG(std::cerr << "  [TD] Done inlining into callees for: "
 240         << Graph.getFunctionNames() << " [" << Graph.getGraphSize() << "+"
 241         << Graph.getFunctionCalls().size() << "]\n");
 242 }
 243