Factor SCEV traversal code so I can use it elsewhere. No functionality.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160203 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 884ceec..f0f3b1c 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -6894,59 +6894,27 @@
return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
}
+namespace {
+// Search for a SCEV expression node within an expression tree.
+// Implements SCEVTraversal::Visitor.
+struct SCEVSearch {
+ const SCEV *Node;
+ bool IsFound;
+
+ SCEVSearch(const SCEV *N): Node(N), IsFound(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 {
- SmallVector<const SCEV *, 8> Worklist;
- Worklist.push_back(S);
- do {
- S = Worklist.pop_back_val();
-
- 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());
-
- return false;
+ SCEVSearch Search(Op);
+ visitAll(S, Search);
+ return Search.IsFound;
}
void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {