Use a separate globals graph to hold externally visible nodes.

This changes both the bottom-up and top-down propagation so that
globals and other external objects do not have to appear in every
function, but only in functions in which they are referenced or
they can be used to access something else that is referenced.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3170 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 78 insertions, 43 deletions

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index c8b45b50cc..3ea7f0c96a 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -11,17 +11,18 @@
 #include "llvm/Module.h"
 #include "llvm/DerivedTypes.h"
 #include "Support/StatisticReporter.h"
+#include <set>
 using std::map;
 
 static RegisterAnalysis<BUDataStructures>
-X("budatastructure", "Bottom-Up Data Structure Analysis Closure");
+X("budatastructure", "Bottom-up Data Structure Analysis Closure");
 AnalysisID BUDataStructures::ID = X;
 
 // releaseMemory - If the pass pipeline is done with this pass, we can release
 // our memory... here...
 //
 void BUDataStructures::releaseMemory() {
-  for (map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
+  for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
          E = DSInfo.end(); I != E; ++I)
     delete I->second;
 
@@ -60,23 +61,29 @@ static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
   }
 }
 
-// MergeGlobalNodes - Merge global value nodes in the inlined graph with the
-// global value nodes in the current graph if there are duplicates.
+// MergeGlobalNodes - Merge all existing global nodes with globals
+// inlined from the callee or with globals from the GlobalsGraph.
 //
-static void MergeGlobalNodes(map<Value*, DSNodeHandle> &ValMap,
+static void MergeGlobalNodes(DSGraph& Graph,
                              map<Value*, DSNodeHandle> &OldValMap) {
-  // Loop over all of the nodes inlined, if any of them are global variable
-  // nodes, we must make sure they get properly added or merged with the ValMap.
-  //
+  map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
+  for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
+       I != E; ++I)
+    if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
+      map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
+      if (NHI != OldValMap.end())       // was it inlined from the callee?
+        I->second->mergeWith(NHI->second);
+      else                              // get it from the GlobalsGraph
+        I->second->mergeWith(Graph.cloneGlobalInto(GV));
+    }
+
+  // Add unused inlined global nodes into the value map
   for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
          E = OldValMap.end(); I != E; ++I)
     if (isa<GlobalValue>(I->first)) {
-      DSNodeHandle &NH = ValMap[I->first];  // Look up global in ValMap.
-      if (NH == 0) {        // No entry for the global yet?
-        NH = I->second;     // Add the one just inlined...
-      } else {
-        NH->mergeWith(I->second); // Merge the two globals together.
-      }
+      DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
+      if (NH == 0)
+        NH = I->second;                     // Add the one just inlined.
     }
 
 }
@@ -91,17 +98,29 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
   // Copy the local version into DSInfo...
   Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
 
+  // Populate the GlobalsGraph with globals from this one.
+  Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
+
   // Save a copy of the original call nodes for the top-down pass
   Graph->saveOrigFunctionCalls();
-  
+
   // Start resolving calls...
   std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
 
-  DEBUG(std::cerr << "Inlining: " << F.getName() << "\n");
+  DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");
+
+  // Add F to the PendingCallers list of each direct callee for use in the
+  // top-down pass so we don't have to compute this again.  We don't want
+  // to do it for indirect callees inlined later, so remember which calls
+  // are in the original FCs set.
+  std::set<const DSNode*> directCallees;
+  for (unsigned i = 0; i < FCs.size(); ++i)
+    directCallees.insert(FCs[i][1]); // ptr to function node
 
   bool Inlined;
   do {
     Inlined = false;
+
     for (unsigned i = 0; i != FCs.size(); ++i) {
       // Copy the call, because inlining graphs may invalidate the FCs vector.
       std::vector<DSNodeHandle> Call = FCs[i];
@@ -111,17 +130,17 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
         // Start inlining all of the functions we can... some may not be
         // inlinable if they are external...
         //
-        std::vector<GlobalValue*> Globals(Call[1]->getGlobals());
+        std::vector<GlobalValue*> Callees(Call[1]->getGlobals());
 
         // Loop over the functions, inlining whatever we can...
-        for (unsigned g = 0; g != Globals.size(); ++g) {
+        for (unsigned c = 0; c != Callees.size(); ++c) {
           // Must be a function type, so this cast MUST succeed.
-          Function &FI = cast<Function>(*Globals[g]);
+          Function &FI = cast<Function>(*Callees[c]);
           if (&FI == &F) {
             // Self recursion... simply link up the formal arguments with the
             // actual arguments...
-           
-            DEBUG(std::cerr << "Self Inlining: " << F.getName() << "\n");
+
+            DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
 
             if (Call[0]) // Handle the return value if present...
               Graph->RetNode->mergeWith(Call[0]);
@@ -129,10 +148,10 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
             // Resolve the arguments in the call to the actual values...
             ResolveArguments(Call, F, Graph->getValueMap());
 
-            // Erase the entry in the globals vector
-            Globals.erase(Globals.begin()+g--);
+            // Erase the entry in the callees vector
+            Callees.erase(Callees.begin()+c--);
           } else if (!FI.isExternal()) {
-            DEBUG(std::cerr << "In " << F.getName() << " inlining: "
+            DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
                   << FI.getName() << "\n");
             
             // Get the data structure graph for the called function, closing it
@@ -141,49 +160,54 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
             //
             DSGraph &GI = calculateGraph(FI);  // Graph to inline
 
-            DEBUG(std::cerr << "Got graph for " << FI.getName() << " in: "
-                  << F.getName() << "\n");
-
-            // Remember the callers for each callee for use in the top-down
-            // pass so we don't have to compute this again
-            GI.addCaller(F);
+            DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
+                  << " in: " << F.getName() << "\n");
 
             // Clone the callee's graph into the current graph, keeping
-            // track of where scalars in the old graph _used_ to point
-            // and of the new nodes matching nodes of the old graph ...
+            // track of where scalars in the old graph _used_ to point,
+            // and of the new nodes matching nodes of the old graph.
             std::map<Value*, DSNodeHandle> OldValMap;
-            std::map<const DSNode*, DSNode*> OldNodeMap; // unused
+            std::map<const DSNode*, DSNode*> OldNodeMap;
 
             // The clone call may invalidate any of the vectors in the data
-            // structure graph.
-            DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap);
+            // structure graph.  Strip locals and don't copy the list of callers
+            DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
+                                              /*StripScalars*/   true,
+                                              /*StripAllocas*/   true,
+                                              /*CopyCallers*/    false,
+                                              /*CopyOrigCalls*/  false);
 
             ResolveArguments(Call, FI, OldValMap);
 
             if (Call[0])  // Handle the return value if present
               RetVal->mergeWith(Call[0]);
-            
+
             // Merge global value nodes in the inlined graph with the global
             // value nodes in the current graph if there are duplicates.
             //
-            MergeGlobalNodes(Graph->getValueMap(), OldValMap);
+            MergeGlobalNodes(*Graph, OldValMap);
+
+            // If this was an original call, add F to the PendingCallers list
+            if (directCallees.find(Call[1]) != directCallees.end())
+              GI.addCaller(F);
+
+            // Erase the entry in the Callees vector
+            Callees.erase(Callees.begin()+c--);
 
-            // Erase the entry in the globals vector
-            Globals.erase(Globals.begin()+g--);
           } else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
                      FI.getName() == "fprintf" || FI.getName() == "open" ||
                      FI.getName() == "sprintf") {
 
             // Erase the entry in the globals vector
-            Globals.erase(Globals.begin()+g--);
+            Callees.erase(Callees.begin()+c--);
           }
         }
 
-        if (Globals.empty()) {         // Inlined all of the function calls?
+        if (Callees.empty()) {         // Inlined all of the function calls?
           // Erase the call if it is resolvable...
           FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
           Inlined = true;
-        } else if (Globals.size() != Call[1]->getGlobals().size()) {
+        } else if (Callees.size() != Call[1]->getGlobals().size()) {
           // Was able to inline SOME, but not all of the functions.  Construct a
           // new global node here.
           //
@@ -198,9 +222,20 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
     if (Inlined) {
       Graph->maskIncompleteMarkers();
       Graph->markIncompleteNodes();
-      Graph->removeDeadNodes();
+      Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ true);
     }
   } while (Inlined && !FCs.empty());
 
+  // Copy any unresolved call nodes into the Globals graph and
+  // filter out unresolved call nodes inlined from the callee.
+  if (!FCs.empty())
+    Graph->GlobalsGraph->cloneCalls(*Graph);
+
+  Graph->maskIncompleteMarkers();
+  Graph->markIncompleteNodes();
+  Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
+
+  DEBUG(cerr << "  [BU] Done inlining: " << F.getName() << "\n");
+
   return *Graph;
 }