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