Ok, I'm tired of pulling out all my timers to check stuff in, just do it.

[oota-llvm.git] / lib / Analysis / DataStructure / BottomUpClosure.cpp

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 31b8021613171965be896913024fdca8bce13fc0..de83f383c624986d7ed2e1c1de5558360e184e55 100644 (file)
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -1,4 +1,11 @@
 //===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
 //
 // This file implements the BUDataStructures class, which represents the
 // Bottom-Up Interprocedural closure of the data structure graph over the
@@ -7,13 +14,17 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "DSCallSiteIterator.h"
 #include "llvm/Analysis/DataStructure.h"
 #include "llvm/Module.h"
 #include "Support/Statistic.h"
+#include "Support/Debug.h"
+#include "DSCallSiteIterator.h"
+using namespace llvm;
 
 namespace {
   Statistic<> MaxSCC("budatastructure", "Maximum SCC Size in Call Graph");
+  Statistic<> NumBUInlines("budatastructures", "Number of graphs inlined");
+  Statistic<> NumCallEdges("budatastructures", "Number of 'actual' call edges");
   
   RegisterAnalysis<BUDataStructures>
   X("budatastructure", "Bottom-up Data Structure Analysis");
@@ -35,7 +46,7 @@ bool BUDataStructures::run(Module &M) {
 
   // Calculate the graphs for any functions that are unreachable from main...
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-    if (!I->isExternal() && DSInfo.find(I) == DSInfo.end()) {
+    if (!I->isExternal() && !DSInfo.count(I)) {
 #ifndef NDEBUG
       if (MainFunc)
         std::cerr << "*** Function unreachable from main: "
@@ -43,6 +54,16 @@ bool BUDataStructures::run(Module &M) {
 #endif
       calculateReachableGraphs(I);    // Calculate all graphs...
     }
+
+  NumCallEdges += ActualCallees.size();
+
+  // At the end of the bottom-up pass, the globals graph becomes complete.
+  // FIXME: This is not the right way to do this, but it is sorta better than
+  // nothing!  In particular, externally visible globals and unresolvable call
+  // nodes at the end of the BU phase should make things that they point to
+  // incomplete in the globals graph.
+  // 
+  GlobalsGraph->maskIncompleteMarkers();
   return false;
 }
 
@@ -73,7 +94,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
                                            std::vector<Function*> &Stack,
                                            unsigned &NextID, 
                                      hash_map<Function*, unsigned> &ValMap) {
-  assert(ValMap.find(F) == ValMap.end() && "Shouldn't revisit functions!");
+  assert(!ValMap.count(F) && "Shouldn't revisit functions!");
   unsigned Min = NextID++, MyID = Min;
   ValMap[F] = Min;
   Stack.push_back(F);
@@ -173,6 +194,9 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
       }
     }
 
+    // Clean up the graph before we start inlining a bunch again...
+    SCCGraph->removeTriviallyDeadNodes();
+
     // Now that we have one big happy family, resolve all of the call sites in
     // the graph...
     calculateGraph(*SCCGraph);
@@ -232,11 +256,11 @@ void BUDataStructures::calculateGraph(DSGraph &Graph) {
     
     // Resolve the current call...
     Function *Callee = *I;
-    const DSCallSite &CS = I.getCallSite();
+    DSCallSite CS = I.getCallSite();
 
     if (Callee->isExternal()) {
       // Ignore this case, simple varargs functions we cannot stub out!
-    } else if (ReturnNodes.find(Callee) != ReturnNodes.end()) {
+    } else if (ReturnNodes.count(Callee)) {
       // Self recursion... simply link up the formal arguments with the
       // actual arguments...
       DEBUG(std::cerr << "    Self Inlining: " << Callee->getName() << "\n");
@@ -245,20 +269,24 @@ void BUDataStructures::calculateGraph(DSGraph &Graph) {
       Graph.mergeInGraph(CS, *Callee, Graph, 0);
 
     } else {
+      ActualCallees.insert(std::make_pair(CS.getCallSite().getInstruction(),
+                                          Callee));
+
       // Get the data structure graph for the called function.
       //
       DSGraph &GI = getDSGraph(*Callee);  // Graph to inline
       
       DEBUG(std::cerr << "    Inlining graph for " << Callee->getName()
             << "[" << GI.getGraphSize() << "+"
-            << GI.getAuxFunctionCalls().size() << "] into [" 
-            << Graph.getGraphSize() << "+"
+            << GI.getAuxFunctionCalls().size() << "] into '"
+            << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() << "+"
             << Graph.getAuxFunctionCalls().size() << "]\n");
       
       // Handle self recursion by resolving the arguments and return value
       Graph.mergeInGraph(CS, *Callee, GI,
                          DSGraph::KeepModRefBits | 
                          DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes);
+      ++NumBUInlines;
 
 #if 0
       Graph.writeGraphToFile(std::cerr, "bu_" + F.getName() + "_after_" +
@@ -273,13 +301,18 @@ void BUDataStructures::calculateGraph(DSGraph &Graph) {
 
   TempFCs.clear();
 
-  // Recompute the Incomplete markers.  If there are any function calls left
-  // now that are complete, we must loop!
+  // Re-materialize nodes from the globals graph.
+  // Do not ignore globals inlined from callees -- they are not up-to-date!
+  Graph.getInlinedGlobals().clear();
+  Graph.updateFromGlobalGraph();
+
+  // Recompute the Incomplete markers
   Graph.maskIncompleteMarkers();
   Graph.markIncompleteNodes(DSGraph::MarkFormalArgs);
-  // FIXME: materialize nodes from the globals graph as neccesary...
+
+  // Delete dead nodes.  Treat globals that are unreachable but that can
+  // reach live nodes as live.
   Graph.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 
   //Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());
 }
-