Grow the EQ classes for globals at the end of the BU pass. This shrinks

memory usage in the TD pass for 254.gap from 31.3MB to 3.9MB.


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

1 files changed, 93 insertions, 0 deletions

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index f585329a33..0f45a989c0 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -30,6 +30,88 @@ namespace {
   X("budatastructure", "Bottom-up Data Structure Analysis");
 }
 
+/// BuildGlobalECs - Look at all of the nodes in the globals graph.  If any node
+/// contains multiple globals, DSA will never, ever, be able to tell the globals
+/// apart.  Instead of maintaining this information in all of the graphs
+/// throughout the entire program, store only a single global (the "leader") in
+/// the graphs, and build equivalence classes for the rest of the globals.
+static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) {
+  DSScalarMap &SM = GG.getScalarMap();
+  EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs();
+  for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end();
+       I != E; ++I) {
+    if (I->getGlobalsList().size() <= 1) continue;
+
+    // First, build up the equivalence set for this block of globals.
+    const std::vector<GlobalValue*> &GVs = I->getGlobalsList();
+    GlobalValue *First = GVs[0];
+    for (unsigned i = 1, e = GVs.size(); i != e; ++i)
+      GlobalECs.unionSets(First, GVs[i]);
+    
+    // Next, get the leader element.
+    assert(First == GlobalECs.getLeaderValue(First) &&
+           "First did not end up being the leader?");
+    
+    // Next, remove all globals from the scalar map that are not the leader.
+    assert(GVs[0] == First && "First had to be at the front!");
+    for (unsigned i = 1, e = GVs.size(); i != e; ++i) {
+      ECGlobals.insert(GVs[i]);
+      SM.erase(SM.find(GVs[i]));
+    }
+    
+    // Finally, change the global node to only contain the leader.
+    I->clearGlobals();
+    I->addGlobal(First);
+  }
+  
+  DEBUG(GG.AssertGraphOK());
+}
+
+/// EliminateUsesOfECGlobals - Once we have determined that some globals are in
+/// really just equivalent to some other globals, remove the globals from the
+/// specified DSGraph (if present), and merge any nodes with their leader nodes.
+static void EliminateUsesOfECGlobals(DSGraph &G,
+                                     const std::set<GlobalValue*> &ECGlobals) {
+  DSScalarMap &SM = G.getScalarMap();
+  EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs();
+
+  bool MadeChange = false;
+  for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end();
+       GI != E; ) {
+    GlobalValue *GV = *GI++;
+    if (!ECGlobals.count(GV)) continue;
+
+    const DSNodeHandle &GVNH = SM[GV];
+    assert(!GVNH.isNull() && "Global has null NH!?");
+
+    // Okay, this global is in some equivalence class.  Start by finding the
+    // leader of the class.
+    GlobalValue *Leader = GlobalECs.getLeaderValue(GV);
+
+    // If the leader isn't already in the graph, insert it into the node
+    // corresponding to GV.
+    if (!SM.global_count(Leader)) {
+      GVNH.getNode()->addGlobal(Leader);
+      SM[Leader] = GVNH;
+    } else {
+      // Otherwise, the leader is in the graph, make sure the nodes are the
+      // merged in the specified graph.
+      const DSNodeHandle &LNH = SM[Leader];
+      if (LNH.getNode() != GVNH.getNode())
+        LNH.mergeWith(GVNH);
+    }
+
+    // Next step, remove the global from the DSNode.
+    GVNH.getNode()->removeGlobal(GV);
+
+    // Finally, remove the global from the ScalarMap.
+    SM.erase(GV);
+    MadeChange = true;
+  }
+
+  DEBUG(if(MadeChange) G.AssertGraphOK());
+}
+
 // run - Calculate the bottom up data structure graphs for each function in the
 // program.
 //
@@ -85,6 +167,17 @@ bool BUDataStructures::runOnModule(Module &M) {
   // Mark external globals incomplete.
   GlobalsGraph->markIncompleteNodes(DSGraph::IgnoreGlobals);
 
+  // Grow the equivalence classes for the globals to include anything that we
+  // now know to be aliased.
+  std::set<GlobalValue*> ECGlobals;
+  BuildGlobalECs(*GlobalsGraph, ECGlobals);
+  if (!ECGlobals.empty()) {
+    DEBUG(std::cerr << "Eliminating " << ECGlobals.size() << " EC Globals!\n");
+    for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
+           E = DSInfo.end(); I != E; ++I)
+      EliminateUsesOfECGlobals(*I->second, ECGlobals);
+  }
+
   // Merge the globals variables (not the calls) from the globals graph back
   // into the main function's graph so that the main function contains all of
   // the information about global pools and GV usage in the program.