From e3d97c744772c075e11f372548cc8d848d555ee9 Mon Sep 17 00:00:00 2001
From: David Greene <greened@obbligato.org>
Date: Tue, 23 Feb 2010 17:37:50 +0000
Subject: [PATCH] Speed up cycle checking significantly by caching results.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96956 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 33899a411be..ef21a1592bb 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -6315,7 +6315,11 @@ bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
 }
 
 static void checkForCyclesHelper(const SDNode *N,
-                                 std::set<const SDNode *> &visited) {
+                                 std::set<const SDNode *> &visited,
+                                 std::set<const SDNode *> &checked) {
+  if (checked.find(N) != checked.end())
+    return;
+
   if (visited.find(N) != visited.end()) {
     dbgs() << "Offending node:\n";
     N->dumprFull();
@@ -6329,16 +6333,18 @@ static void checkForCyclesHelper(const SDNode *N,
   assert(inserted && "Missed cycle");
 
   for(unsigned i = 0; i < N->getNumOperands(); ++i) {
-    checkForCyclesHelper(N->getOperand(i).getNode(), visited);
+    checkForCyclesHelper(N->getOperand(i).getNode(), visited, checked);
   }
   visited.erase(i);
+  checked.insert(N);
 }
 
 void llvm::checkForCycles(const llvm::SDNode *N) {
 #ifdef XDEBUG
   assert(N && "Checking nonexistant SDNode");
   std::set<const SDNode *> visited;
-  checkForCyclesHelper(N, visited);
+  std::set<const SDNode *> checked;
+  checkForCyclesHelper(N, visited, checked);
 #endif
 }
 
-- 
2.34.1