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 namespace {
  17   RegisterAnalysis<TDDataStructures>   // Register the pass
  18   Y("tddatastructure", "Top-down Data Structure Analysis");
  19 }
  20
  21 // run - Calculate the top down data structure graphs for each function in the
  22 // program.
  23 //
  24 bool TDDataStructures::run(Module &M) {
  25   BUDataStructures &BU = getAnalysis<BUDataStructures>();
  26   GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
  27
  28   // Calculate top-down from main...
  29   if (Function *F = M.getMainFunction())
  30     calculateGraph(*F);
  31
  32   // Next calculate the graphs for each function unreachable function...
  33   for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
  34     if (!I->isExternal())
  35       calculateGraph(*I);
  36
  37   GraphDone.clear();    // Free temporary memory...
  38   return false;
  39 }
  40
  41 // releaseMemory - If the pass pipeline is done with this pass, we can release
  42 // our memory... here...
  43 //
  44 // FIXME: This should be releaseMemory and will work fine, except that LoadVN
  45 // has no way to extend the lifetime of the pass, which screws up ds-aa.
  46 //
  47 void TDDataStructures::releaseMyMemory() {
  48   return;
  49   for (hash_map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
  50          E = DSInfo.end(); I != E; ++I)
  51     delete I->second;
  52
  53   // Empty map so next time memory is released, data structures are not
  54   // re-deleted.
  55   DSInfo.clear();
  56   delete GlobalsGraph;
  57   GlobalsGraph = 0;
  58 }
  59
  60 /// ResolveCallSite - This method is used to link the actual arguments together
  61 /// with the formal arguments for a function call in the top-down closure.  This
  62 /// method assumes that the call site arguments have been mapped into nodes
  63 /// local to the specified graph.
  64 ///
  65 void TDDataStructures::ResolveCallSite(DSGraph &Graph,
  66                                        const DSCallSite &CallSite) {
  67   // Resolve all of the function formal arguments...
  68   Function &F = Graph.getFunction();
  69   Function::aiterator AI = F.abegin();
  70
  71   for (unsigned i = 0, e = CallSite.getNumPtrArgs(); i != e; ++i, ++AI) {
  72     // Advance the argument iterator to the first pointer argument...
  73     while (!DS::isPointerType(AI->getType())) ++AI;
  74
  75     // TD ...Merge the formal arg scalar with the actual arg node
  76     DSNodeHandle &NodeForFormal = Graph.getNodeForValue(AI);
  77     assert(NodeForFormal.getNode() && "Pointer argument has no dest node!");
  78     NodeForFormal.mergeWith(CallSite.getPtrArg(i));
  79   }
  80
  81   // Merge returned node in the caller with the "return" node in callee
  82   if (CallSite.getRetVal().getNode() && Graph.getRetNode().getNode())
  83     Graph.getRetNode().mergeWith(CallSite.getRetVal());
  84 }
  85
  86 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
  87   DSGraph *&G = DSInfo[&F];
  88   if (G == 0) { // Not created yet?  Clone BU graph...
  89     G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
  90     G->getAuxFunctionCalls().clear();
  91     G->setPrintAuxCalls();
  92     G->setGlobalsGraph(GlobalsGraph);
  93   }
  94   return *G;
  95 }
  96
  97
  98 /// FunctionHasCompleteArguments - This function returns true if it is safe not
  99 /// to mark arguments to the function complete.
 100 ///
 101 /// FIXME: Need to check if all callers have been found, or rather if a
 102 /// funcpointer escapes!
 103 ///
 104 static bool FunctionHasCompleteArguments(Function &F) {
 105   return F.hasInternalLinkage();
 106 }
 107
 108
 109 void TDDataStructures::calculateGraph(Function &F) {
 110   // Make sure this graph has not already been calculated, and that we don't get
 111   // into an infinite loop with mutually recursive functions.
 112   //
 113   if (GraphDone.count(&F)) return;
 114   GraphDone.insert(&F);
 115
 116   // Get the current functions graph...
 117   DSGraph &Graph = getOrCreateDSGraph(F);
 118
 119   // Recompute the Incomplete markers and eliminate unreachable nodes.
 120   Graph.maskIncompleteMarkers();
 121   unsigned Flags = FunctionHasCompleteArguments(F) ?
 122                             DSGraph::IgnoreFormalArgs : DSGraph::MarkFormalArgs;
 123   Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
 124   Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
 125
 126   const std::vector<DSCallSite> &CallSites = Graph.getFunctionCalls();
 127   if (CallSites.empty()) {
 128     DEBUG(std::cerr << "  [TD] No callees for: " << F.getName() << "\n");
 129   } else {
 130     // Loop over all of the call sites, building a multi-map from Callees to
 131     // DSCallSite*'s.  With this map we can then loop over each callee, cloning
 132     // this graph once into it, then resolving arguments.
 133     //
 134     std::multimap<Function*, const DSCallSite*> CalleeSites;
 135     for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
 136       const DSCallSite &CS = CallSites[i];
 137       if (CS.isDirectCall()) {
 138         if (!CS.getCalleeFunc()->isExternal())           // If it's not external
 139           CalleeSites.insert(std::make_pair(CS.getCalleeFunc(), &CS));// Keep it
 140       } else {
 141         const std::vector<GlobalValue*> &Callees =
 142           CS.getCalleeNode()->getGlobals();
 143
 144         // Loop over all of the functions that this call may invoke...
 145         for (unsigned c = 0, e = Callees.size(); c != e; ++c)
 146           if (Function *F = dyn_cast<Function>(Callees[c]))// If this is a fn...
 147             if (!F->isExternal())                          // If it's not extern
 148               CalleeSites.insert(std::make_pair(F, &CS));  // Keep track of it!
 149       }
 150     }
 151
 152     // Now that we have information about all of the callees, propagate the
 153     // current graph into the callees.
 154     //
 155     DEBUG(std::cerr << "  [TD] Inlining '" << F.getName() << "' into "
 156           << CalleeSites.size() << " callees.\n");
 157
 158     // Loop over all the callees...
 159     for (std::multimap<Function*, const DSCallSite*>::iterator
 160            I = CalleeSites.begin(), E = CalleeSites.end(); I != E; )
 161       if (I->first == &F) {  // Bottom-up pass takes care of self loops!
 162         ++I;
 163       } else {
 164         // For each callee...
 165         Function &Callee = *I->first;
 166         DSGraph &CG = getOrCreateDSGraph(Callee);  // Get the callee's graph...
 167
 168         DEBUG(std::cerr << "\t [TD] Inlining into callee '" << Callee.getName()
 169                         << "'\n");
 170
 171         // Clone our current graph into the callee...
 172         hash_map<Value*, DSNodeHandle> OldValMap;
 173         hash_map<const DSNode*, DSNodeHandle> OldNodeMap;
 174         CG.cloneInto(Graph, OldValMap, OldNodeMap,
 175                      DSGraph::StripModRefBits |
 176                      DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes |
 177                      DSGraph::DontCloneAuxCallNodes);
 178         OldValMap.clear();  // We don't care about the ValMap
 179
 180         // Loop over all of the invocation sites of the callee, resolving
 181         // arguments to our graph.  This loop may iterate multiple times if the
 182         // current function calls this callee multiple times with different
 183         // signatures.
 184         //
 185         for (; I != E && I->first == &Callee; ++I) {
 186           // Map call site into callee graph
 187           DSCallSite NewCS(*I->second, OldNodeMap);
 188
 189           // Resolve the return values...
 190           NewCS.getRetVal().mergeWith(CG.getRetNode());
 191
 192           // Resolve all of the arguments...
 193           Function::aiterator AI = Callee.abegin();
 194           for (unsigned i = 0, e = NewCS.getNumPtrArgs();
 195                i != e && AI != Callee.aend(); ++i, ++AI) {
 196             // Advance the argument iterator to the first pointer argument...
 197             while (AI != Callee.aend() && !DS::isPointerType(AI->getType()))
 198               ++AI;
 199             if (AI == Callee.aend()) break;
 200
 201             // Add the link from the argument scalar to the provided value
 202             DSNodeHandle &NH = CG.getNodeForValue(AI);
 203             assert(NH.getNode() && "Pointer argument without scalarmap entry?");
 204             NH.mergeWith(NewCS.getPtrArg(i));
 205           }
 206         }
 207
 208         // Done with the nodemap...
 209         OldNodeMap.clear();
 210
 211         // Recompute the Incomplete markers and eliminate unreachable nodes.
 212         CG.removeTriviallyDeadNodes();
 213         CG.maskIncompleteMarkers();
 214         CG.markIncompleteNodes(DSGraph::MarkFormalArgs |DSGraph::IgnoreGlobals);
 215         CG.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
 216       }
 217
 218     DEBUG(std::cerr << "  [TD] Done inlining into callees for: " << F.getName()
 219           << " [" << Graph.getGraphSize() << "+"
 220           << Graph.getFunctionCalls().size() << "]\n");
 221
 222     // Loop over all the callees... making sure they are all resolved now...
 223     Function *LastFunc = 0;
 224     for (std::multimap<Function*, const DSCallSite*>::iterator
 225            I = CalleeSites.begin(), E = CalleeSites.end(); I != E; ++I)
 226       if (I->first != LastFunc) {  // Only visit each callee once...
 227         LastFunc = I->first;
 228         calculateGraph(*I->first);
 229       }
 230   }
 231 }
 232