From 647580483c3d3066c28cc76421a3cc06d2820852 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Fri, 22 Jun 2007 21:31:16 +0000
Subject: [PATCH] Rework topo_sort so eliminate some behavior that scaled
 terribly.  This reduces the time to optimize 403.gcc from 18.2s to 17.5s, and
 has an even larger effect on larger testcases.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37708 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/GVNPRE.cpp | 97 +++++++++++++-------------------
 1 file changed, 40 insertions(+), 57 deletions(-)

diff --git a/lib/Transforms/Scalar/GVNPRE.cpp b/lib/Transforms/Scalar/GVNPRE.cpp
index 013d00c8c9a..b3970c97d2f 100644
--- a/lib/Transforms/Scalar/GVNPRE.cpp
+++ b/lib/Transforms/Scalar/GVNPRE.cpp
@@ -650,71 +650,54 @@ void GVNPRE::clean(SmallPtrSet<Value*, 32>& set) {
 /// topo_sort - Given a set of values, sort them by topological
 /// order into the provided vector.
 void GVNPRE::topo_sort(SmallPtrSet<Value*, 32>& set, std::vector<Value*>& vec) {
-  SmallPtrSet<Value*, 32> toErase;
-  for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
-       I != E; ++I) {
-    if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
-      for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
-        if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
-            VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
-          toErase.insert(*SI);
-        }
-      }
-    else if (CmpInst* C = dyn_cast<CmpInst>(*I))
-      for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
-        if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
-            VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
-          toErase.insert(*SI);
-        }
-      }
-  }
-  
-  std::vector<Value*> Q;
+  SmallPtrSet<Value*, 32> visited;
+  std::vector<Value*> stack;
   for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
        I != E; ++I) {
-    if (toErase.count(*I) == 0)
-      Q.push_back(*I);
-  }
-  
-  SmallPtrSet<Value*, 32> visited;
-  while (!Q.empty()) {
-    Value* e = Q.back();
+    if (visited.count(*I) == 0)
+      stack.push_back(*I);
+    
+    while (!stack.empty()) {
+      Value* e = stack.back();
   
-    if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
-      Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
-      Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
+      if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
+        Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
+        Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
+    
+        if (l != 0 && isa<Instruction>(l) &&
+            visited.count(l) == 0)
+          stack.push_back(l);
+        else if (r != 0 && isa<Instruction>(r) &&
+                 visited.count(r) == 0)
+          stack.push_back(r);
+        else {
+          vec.push_back(e);
+          visited.insert(e);
+          stack.pop_back();
+        }
+      } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
+        Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
+        Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
       
-      if (l != 0 && isa<Instruction>(l) &&
-          visited.count(l) == 0)
-        Q.push_back(l);
-      else if (r != 0 && isa<Instruction>(r) &&
-               visited.count(r) == 0)
-        Q.push_back(r);
-      else {
-        vec.push_back(e);
+        if (l != 0 && isa<Instruction>(l) &&
+            visited.count(l) == 0)
+          stack.push_back(l);
+        else if (r != 0 && isa<Instruction>(r) &&
+                 visited.count(r) == 0)
+          stack.push_back(r);
+        else {
+          vec.push_back(e);
+          visited.insert(e);
+          stack.pop_back();
+        }
+      } else {
         visited.insert(e);
-        Q.pop_back();
-      }
-    } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
-      Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
-      Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
-      
-      if (l != 0 && isa<Instruction>(l) &&
-          visited.count(l) == 0)
-        Q.push_back(l);
-      else if (r != 0 && isa<Instruction>(r) &&
-               visited.count(r) == 0)
-        Q.push_back(r);
-      else {
         vec.push_back(e);
-        visited.insert(e);
-        Q.pop_back();
+        stack.pop_back();
       }
-    } else {
-      visited.insert(e);
-      vec.push_back(e);
-      Q.pop_back();
     }
+    
+    stack.clear();
   }
 }
 
-- 
2.34.1