This replaces the correct but slow code with a more aggressive scc-finder

based approach to find globals and call sites that need to be copied.  This
speeds up the BU pass on 176.gcc from 22s back up to 2.3s.  Not as good
as 1.5s, but at least it's correct :)


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

1 files changed, 97 insertions, 54 deletions

diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index ae4d51b3435..e0833c19621 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -1320,65 +1320,109 @@ void DSGraph::getFunctionArgumentsForCall(Function *F,
     }
 }
 
-/// PathExistsToClonedNode - Return true if there is a path from this node to a
-/// node cloned by RC that does not go through another global node.  Use the
-/// NodeInfo map to cache information so this is an efficient depth first
-/// traversal.
-static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC,
-                                   std::map<const DSNode*, bool> &NodeInfo) {
-  std::map<const DSNode*, bool>::iterator I = NodeInfo.find(N);
-  if (I != NodeInfo.end())
-    return I->second;
-
-  // FIXME: we are potentially re-scc'ing chunks of the graph for all of the
-  // roots!  We need an SCC iterator that supports multiple roots.
-  //
-  // FIXME: This should stop traversal of SCCs when we find something in RC!
-  scc_iterator<const DSNode*> SCCI = scc_begin(N), SCCE = scc_end(N);
-  for (; SCCI != SCCE; ++SCCI) {
-    std::vector<const DSNode*> &SCC = *SCCI;
-    assert(!SCC.empty() && "empty scc??");
+namespace {
+  // HackedGraphSCCFinder - This is used to find nodes that have a path from the
+  // node to a node cloned by the ReachabilityCloner object contained.  To be
+  // extra obnoxious it ignores edges from nodes that are globals, and truncates
+  // search at RC marked nodes.  This is designed as an object so that
+  // intermediate results can be memoized across invocations of
+  // PathExistsToClonedNode.
+  struct HackedGraphSCCFinder {
+    ReachabilityCloner &RC;
+    unsigned CurNodeId;
+    std::vector<const DSNode*> SCCStack;
+    std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo;
+    
+    HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) {
+      // Remove null pointer as a special case.
+      NodeInfo[0] = std::make_pair(0, false);
+    }
 
-    if (NodeInfo.count(SCC[0]))
-      continue;  // already processed.
+    std::pair<unsigned, bool> &VisitForSCCs(const DSNode *N);
 
-    bool SCCReachesClonedNode = false;
+    bool PathExistsToClonedNode(const DSNode *N) {
+      return VisitForSCCs(N).second;
+    }
 
-    for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
-      const DSNode *N = SCC[i];
+    bool PathExistsToClonedNode(const DSCallSite &CS) {
+      if (PathExistsToClonedNode(CS.getRetVal().getNode()))
+        return true;
+      for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
+        if (PathExistsToClonedNode(CS.getPtrArg(i).getNode()))
+          return true;
+      return false;
+    }
+  };
+}
 
-      if (RC.hasClonedNode(N)) {
-        SCCReachesClonedNode = true;
-        goto OutOfLoop;
-      }
+std::pair<unsigned, bool> &HackedGraphSCCFinder::
+VisitForSCCs(const DSNode *N) {
+  std::map<const DSNode*, std::pair<unsigned, bool> >::iterator
+    NodeInfoIt = NodeInfo.lower_bound(N);
+  if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N)
+    return NodeInfoIt->second;
+
+  unsigned Min = CurNodeId++;
+  unsigned MyId = Min;
+  std::pair<unsigned, bool> &ThisNodeInfo =
+    NodeInfo.insert(NodeInfoIt,
+                    std::make_pair(N, std::make_pair(MyId, false)))->second;
+
+  // Base case: if we find a global, this doesn't reach the cloned graph
+  // portion.
+  if (N->isGlobalNode()) {
+    ThisNodeInfo.second = false;
+    return ThisNodeInfo;
+  }
 
-      for (DSNode::const_edge_iterator EI = N->edge_begin(), E = N->edge_end();
-           EI != E; ++EI)
-        if (const DSNode *Succ = EI->getNode())
-          if (NodeInfo[Succ]) {
-            SCCReachesClonedNode = true;
-            goto OutOfLoop;
-          }
-    }
+  // Base case: if this does reach the cloned graph portion... it does. :)
+  if (RC.hasClonedNode(N)) {
+    ThisNodeInfo.second = true;
+    return ThisNodeInfo;
+  }
+
+  SCCStack.push_back(N);
 
-  OutOfLoop:
-    for (unsigned i = 0, e = SCC.size(); i != e; ++i)
-      NodeInfo[SCC[i]] = SCCReachesClonedNode;
+  // Otherwise, check all successors.
+  bool AnyDirectSuccessorsReachClonedNodes = false;
+  for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
+       EI != EE; ++EI) {
+    std::pair<unsigned, bool> &SuccInfo = VisitForSCCs(EI->getNode());
+    if (SuccInfo.first < Min) Min = SuccInfo.first;
+    AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second;
   }
 
-  return NodeInfo[N];
-}
+  if (Min != MyId)
+    return ThisNodeInfo;  // Part of a large SCC.  Leave self on stack.
 
-static bool PathExistsToClonedNode(const DSCallSite &CS, ReachabilityCloner &RC,
-                                   std::map<const DSNode*, bool> &NodeInfo) {
-  if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC, NodeInfo))
-    return true;
-  for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
-    if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC, NodeInfo))
-      return true;
-  return false;
-}
+  if (SCCStack.back() == N) {  // Special case single node SCC.
+    SCCStack.pop_back();
+    ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
+    return ThisNodeInfo;
+  }
 
+  // Find out if any direct successors of any node reach cloned nodes.
+  if (!AnyDirectSuccessorsReachClonedNodes)
+    for (unsigned i = SCCStack.size()-1; SCCStack[i] != N; --i)
+      for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
+           EI != EE; ++EI)
+        if (DSNode *N = EI->getNode())
+          if (NodeInfo[N].second) {
+            AnyDirectSuccessorsReachClonedNodes = true;
+            goto OutOfLoop;
+          }
+OutOfLoop:
+  // If any successor reaches a cloned node, mark all nodes in this SCC as
+  // reaching the cloned node.
+  if (AnyDirectSuccessorsReachClonedNodes)
+    while (SCCStack.back() != N) {
+      NodeInfo[SCCStack.back()].second = true;
+      SCCStack.pop_back();
+    }
+  SCCStack.pop_back();
+  ThisNodeInfo.second = true;
+  return ThisNodeInfo;
+}
 
 /// mergeInCallFromOtherGraph - This graph merges in the minimal number of
 /// nodes from G2 into 'this' graph, merging the bindings specified by the
@@ -1438,21 +1482,20 @@ void DSGraph::mergeInGraph(const DSCallSite &CS,
   // NodesReachCopiedNodes - Memoize results for efficiency.  Contains a
   // true/false value for every visited node that reaches a copied node without
   // going through a global.
-  std::map<const DSNode*, bool> NodesReachCopiedNodes;
-  NodesReachCopiedNodes[0] = false;  // Initialize null.
+  HackedGraphSCCFinder SCCFinder(RC);
 
   if (!(CloneFlags & DontCloneAuxCallNodes))
     for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
-      if (PathExistsToClonedNode(*I, RC, NodesReachCopiedNodes))
+      if (SCCFinder.PathExistsToClonedNode(*I))
         AuxCallToCopy.push_back(&*I);
 
-  DSScalarMap GSM = Graph.getScalarMap();
+  const DSScalarMap &GSM = Graph.getScalarMap();
   for (DSScalarMap::global_iterator GI = GSM.global_begin(),
          E = GSM.global_end(); GI != E; ++GI) {
     DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode();
     for (DSNode::edge_iterator EI = GlobalNode->edge_begin(),
            EE = GlobalNode->edge_end(); EI != EE; ++EI)
-      if (PathExistsToClonedNode(EI->getNode(), RC, NodesReachCopiedNodes)) {
+      if (SCCFinder.PathExistsToClonedNode(EI->getNode())) {
         GlobalsToCopy.push_back(*GI);
         break;
       }