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   // Start resolving calls...
  93   std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
  94
  95   DEBUG(cerr << "Inlining: " << F.getName() << "\n");
  96
  97   bool Inlined;
  98   do {
  99     Inlined = false;
 100     for (unsigned i = 0; i != FCs.size(); ++i) {
 101       // Copy the call, because inlining graphs may invalidate the FCs vector.
 102       std::vector<DSNodeHandle> Call = FCs[i];
 103
 104       // If the function list is not incomplete...
 105       if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
 106         // Start inlining all of the functions we can... some may not be
 107         // inlinable if they are external...
 108         //
 109         std::vector<GlobalValue*> Globals(Call[1]->getGlobals());
 110
 111         // Loop over the functions, inlining whatever we can...
 112         for (unsigned g = 0; g != Globals.size(); ++g) {
 113           // Must be a function type, so this cast MUST succeed.
 114           Function &FI = cast<Function>(*Globals[g]);
 115           if (&FI == &F) {
 116             // Self recursion... simply link up the formal arguments with the
 117             // actual arguments...
 118
 119             DEBUG(cerr << "Self Inlining: " << F.getName() << "\n");
 120
 121             if (Call[0]) // Handle the return value if present...
 122               Graph->RetNode->mergeWith(Call[0]);
 123
 124             // Resolve the arguments in the call to the actual values...
 125             ResolveArguments(Call, F, Graph->getValueMap());
 126
 127             // Erase the entry in the globals vector
 128             Globals.erase(Globals.begin()+g--);
 129           } else if (!FI.isExternal()) {
 130             DEBUG(std::cerr << "In " << F.getName() << " inlining: "
 131                   << FI.getName() << "\n");
 132
 133             // Get the data structure graph for the called function, closing it
 134             // if possible (which is only impossible in the case of mutual
 135             // recursion...
 136             //
 137             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 138
 139             DEBUG(cerr << "Got graph for " << FI.getName() << " in: "
 140                   << F.getName() << "\n");
 141
 142
 143
 144             // Clone the called function's graph into the current graph, keeping
 145             // track of where scalars in the old graph _used_ to point...
 146             map<Value*, DSNodeHandle> OldValMap;
 147
 148             // The clone call may invalidate any of the vectors in the data
 149             // structure graph.
 150             DSNode *RetVal = Graph->cloneInto(GI, OldValMap);
 151
 152             ResolveArguments(Call, FI, OldValMap);
 153
 154             if (Call[0])  // Handle the return value if present
 155               RetVal->mergeWith(Call[0]);
 156
 157             // Merge global value nodes in the inlined graph with the global
 158             // value nodes in the current graph if there are duplicates.
 159             //
 160             MergeGlobalNodes(Graph->getValueMap(), OldValMap);
 161
 162             // Erase the entry in the globals vector
 163             Globals.erase(Globals.begin()+g--);
 164           }
 165         }
 166
 167         if (Globals.empty()) {         // Inlined all of the function calls?
 168           // Erase the call if it is resolvable...
 169           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
 170           Inlined = true;
 171         } else if (Globals.size() != Call[1]->getGlobals().size()) {
 172           // Was able to inline SOME, but not all of the functions.  Construct a
 173           // new global node here.
 174           //
 175           assert(0 && "Unimpl!");
 176           Inlined = true;
 177         }
 178       }
 179     }
 180
 181     // Recompute the Incomplete markers.  If there are any function calls left
 182     // now that are complete, we must loop!
 183     if (Inlined) {
 184       Graph->maskIncompleteMarkers();
 185       Graph->markIncompleteNodes();
 186       Graph->removeDeadNodes();
 187     }
 188   } while (Inlined && !FCs.empty());
 189
 190   return *Graph;
 191 }