lib/Analysis/DataStructure/BottomUpClosure.cpp

   1 //===- BottomUpClosure.cpp - Compute the bottom up interprocedure closure -===//
   2 //
   3 // This file implements the BUDataStructures class, which represents the
   4 // Bottom-Up Interprocedural closure of the data structure graph over the
   5 // program.  This is useful for applications like pool allocation, but **not**
   6 // applications 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/StatisticReporter.h"
  14 using std::map;
  15
  16 AnalysisID BUDataStructures::ID(AnalysisID::create<BUDataStructures>());
  17
  18 // releaseMemory - If the pass pipeline is done with this pass, we can release
  19 // our memory... here...
  20 //
  21 void BUDataStructures::releaseMemory() {
  22   for (map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
  23          E = DSInfo.end(); I != E; ++I)
  24     delete I->second;
  25
  26   // Empty map so next time memory is released, data structures are not
  27   // re-deleted.
  28   DSInfo.clear();
  29 }
  30
  31 // run - Calculate the bottom up data structure graphs for each function in the
  32 // program.
  33 //
  34 bool BUDataStructures::run(Module &M) {
  35   // Simply calculate the graphs for each function...
  36   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  37     if (!I->isExternal())
  38       calculateGraph(*I);
  39   return false;
  40 }
  41
  42
  43 // ResolveArguments - Resolve the formal and actual arguments for a function
  44 // call.
  45 //
  46 static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
  47                              map<Value*, DSNodeHandle> &ValueMap) {
  48   // Resolve all of the function arguments...
  49   Function::aiterator AI = F.abegin();
  50   for (unsigned i = 2, e = Call.size(); i != e; ++i) {
  51     // Advance the argument iterator to the first pointer argument...
  52     while (!isa<PointerType>(AI->getType())) ++AI;
  53
  54     // Add the link from the argument scalar to the provided value
  55     DSNode *NN = ValueMap[AI];
  56     NN->addEdgeTo(Call[i]);
  57     ++AI;
  58   }
  59 }
  60
  61 // MergeGlobalNodes - Merge global value nodes in the inlined graph with the
  62 // global value nodes in the current graph if there are duplicates.
  63 //
  64 static void MergeGlobalNodes(map<Value*, DSNodeHandle> &ValMap,
  65                              map<Value*, DSNodeHandle> &OldValMap) {
  66   // Loop over all of the nodes inlined, if any of them are global variable
  67   // nodes, we must make sure they get properly added or merged with the ValMap.
  68   //
  69   for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
  70          E = OldValMap.end(); I != E; ++I)
  71     if (isa<GlobalValue>(I->first)) {
  72       DSNodeHandle &NH = ValMap[I->first];  // Look up global in ValMap.
  73       if (NH == 0) {        // No entry for the global yet?
  74         NH = I->second;     // Add the one just inlined...
  75       } else {
  76         NH->mergeWith(I->second); // Merge the two globals together.
  77       }
  78     }
  79
  80 }
  81
  82 DSGraph &BUDataStructures::calculateGraph(Function &F) {
  83   // Make sure this graph has not already been calculated, or that we don't get
  84   // into an infinite loop with mutually recursive functions.
  85   //
  86   DSGraph *&Graph = DSInfo[&F];
  87   if (Graph) return *Graph;
  88
  89   // Copy the local version into DSInfo...
  90   Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
  91
  92   // Save a copy of the original call nodes for the top-down pass
  93   Graph->saveOrigFunctionCalls();
  94
  95   // Start resolving calls...
  96   std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
  97
  98   DEBUG(std::cerr << "Inlining: " << F.getName() << "\n");
  99
 100   bool Inlined;
 101   do {
 102     Inlined = false;
 103     for (unsigned i = 0; i != FCs.size(); ++i) {
 104       // Copy the call, because inlining graphs may invalidate the FCs vector.
 105       std::vector<DSNodeHandle> Call = FCs[i];
 106
 107       // If the function list is not incomplete...
 108       if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
 109         // Start inlining all of the functions we can... some may not be
 110         // inlinable if they are external...
 111         //
 112         std::vector<GlobalValue*> Globals(Call[1]->getGlobals());
 113
 114         // Loop over the functions, inlining whatever we can...
 115         for (unsigned g = 0; g != Globals.size(); ++g) {
 116           // Must be a function type, so this cast MUST succeed.
 117           Function &FI = cast<Function>(*Globals[g]);
 118           if (&FI == &F) {
 119             // Self recursion... simply link up the formal arguments with the
 120             // actual arguments...
 121
 122             DEBUG(std::cerr << "Self Inlining: " << F.getName() << "\n");
 123
 124             if (Call[0]) // Handle the return value if present...
 125               Graph->RetNode->mergeWith(Call[0]);
 126
 127             // Resolve the arguments in the call to the actual values...
 128             ResolveArguments(Call, F, Graph->getValueMap());
 129
 130             // Erase the entry in the globals vector
 131             Globals.erase(Globals.begin()+g--);
 132           } else if (!FI.isExternal()) {
 133             DEBUG(std::cerr << "In " << F.getName() << " inlining: "
 134                   << FI.getName() << "\n");
 135
 136             // Get the data structure graph for the called function, closing it
 137             // if possible (which is only impossible in the case of mutual
 138             // recursion...
 139             //
 140             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 141
 142             DEBUG(std::cerr << "Got graph for " << FI.getName() << " in: "
 143                   << F.getName() << "\n");
 144
 145             // Remember the callers for each callee for use in the top-down
 146             // pass so we don't have to compute this again
 147             GI.addCaller(F);
 148
 149             // Clone the callee's graph into the current graph, keeping
 150             // track of where scalars in the old graph _used_ to point
 151             // and of the new nodes matching nodes of the old graph ...
 152             std::map<Value*, DSNodeHandle> OldValMap;
 153             std::map<const DSNode*, DSNode*> OldNodeMap; // unused
 154
 155             // The clone call may invalidate any of the vectors in the data
 156             // structure graph.
 157             DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap);
 158
 159             ResolveArguments(Call, FI, OldValMap);
 160
 161             if (Call[0])  // Handle the return value if present
 162               RetVal->mergeWith(Call[0]);
 163
 164             // Merge global value nodes in the inlined graph with the global
 165             // value nodes in the current graph if there are duplicates.
 166             //
 167             MergeGlobalNodes(Graph->getValueMap(), OldValMap);
 168
 169             // Erase the entry in the globals vector
 170             Globals.erase(Globals.begin()+g--);
 171           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
 172                      FI.getName() == "fprintf" || FI.getName() == "open" ||
 173                      FI.getName() == "sprintf") {
 174
 175             // Erase the entry in the globals vector
 176             Globals.erase(Globals.begin()+g--);
 177           }
 178         }
 179
 180         if (Globals.empty()) {         // Inlined all of the function calls?
 181           // Erase the call if it is resolvable...
 182           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
 183           Inlined = true;
 184         } else if (Globals.size() != Call[1]->getGlobals().size()) {
 185           // Was able to inline SOME, but not all of the functions.  Construct a
 186           // new global node here.
 187           //
 188           assert(0 && "Unimpl!");
 189           Inlined = true;
 190         }
 191       }
 192     }
 193
 194     // Recompute the Incomplete markers.  If there are any function calls left
 195     // now that are complete, we must loop!
 196     if (Inlined) {
 197       Graph->maskIncompleteMarkers();
 198       Graph->markIncompleteNodes();
 199       Graph->removeDeadNodes();
 200     }
 201   } while (Inlined && !FCs.empty());
 202
 203   return *Graph;
 204 }