From 365e31c36caba2711b814134bf580434d9847490 Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Fri, 13 Jul 2012 23:33:03 +0000
Subject: Factor SCEV traversal code so I can use it elsewhere. No
 functionality.

llvm-svn: 160203
---
 llvm/lib/Analysis/ScalarEvolution.cpp | 70 ++++++++++-------------------------
 1 file changed, 19 insertions(+), 51 deletions(-)

(limited to 'llvm/lib/Analysis/ScalarEvolution.cpp')

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 884ceec7a00..f0f3b1cb66e 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -6894,59 +6894,27 @@ bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
   return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
 }
 
-bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
-  SmallVector<const SCEV *, 8> Worklist;
-  Worklist.push_back(S);
-  do {
-    S = Worklist.pop_back_val();
+namespace {
+// Search for a SCEV expression node within an expression tree.
+// Implements SCEVTraversal::Visitor.
+struct SCEVSearch {
+  const SCEV *Node;
+  bool IsFound;
 
-    switch (S->getSCEVType()) {
-    case scConstant:
-      break;
-    case scTruncate:
-    case scZeroExtend:
-    case scSignExtend: {
-      const SCEVCastExpr *Cast = cast<SCEVCastExpr>(S);
-      const SCEV *CastOp = Cast->getOperand();
-      if (Op == CastOp)
-        return true;
-      Worklist.push_back(CastOp);
-      break;
-    }
-    case scAddRecExpr:
-    case scAddExpr:
-    case scMulExpr:
-    case scUMaxExpr:
-    case scSMaxExpr: {
-      const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
-      for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
-           I != E; ++I) {
-        const SCEV *NAryOp = *I;
-        if (NAryOp == Op)
-          return true;
-        Worklist.push_back(NAryOp);
-      }
-      break;
-    }
-    case scUDivExpr: {
-      const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
-      const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
-      if (LHS == Op || RHS == Op)
-        return true;
-      Worklist.push_back(LHS);
-      Worklist.push_back(RHS);
-      break;
-    }
-    case scUnknown:
-      break;
-    case scCouldNotCompute:
-      llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
-    default:
-      llvm_unreachable("Unknown SCEV kind!");
-    }
-  } while (!Worklist.empty());
+  SCEVSearch(const SCEV *N): Node(N), IsFound(false) {}
 
-  return false;
+  bool follow(const SCEV *S) {
+    IsFound |= (S == Node);
+    return !IsFound;
+  }
+  bool isDone() const { return IsFound; }
+};
+}
+
+bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
+  SCEVSearch Search(Op);
+  visitAll(S, Search);
+  return Search.IsFound;
 }
 
 void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
-- 
cgit v1.2.3