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