diff options
author | Andrew Trick <atrick@apple.com> | 2012-07-18 05:14:03 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2012-07-18 05:14:03 +0000 |
commit | 18a1b616ea123548b61a037c4f4fea4133aac1b5 (patch) | |
tree | f41fafe249013177ea6e9283fa9e75351c9837dc | |
parent | 76bd9386f1e1487a49c7c34ff95078dea20e3154 (diff) | |
download | external_llvm-18a1b616ea123548b61a037c4f4fea4133aac1b5.zip external_llvm-18a1b616ea123548b61a037c4f4fea4133aac1b5.tar.gz external_llvm-18a1b616ea123548b61a037c4f4fea4133aac1b5.tar.bz2 |
SCEVTraversal: Add a visited set.
Expression trees may be DAGs. Make sure traversal has linear complexity.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160426 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 4 |
1 files changed, 3 insertions, 1 deletions
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index cf15f73..ded1297 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -15,6 +15,7 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -505,9 +506,10 @@ namespace llvm { class SCEVTraversal { SV &Visitor; SmallVector<const SCEV *, 8> Worklist; + SmallPtrSet<const SCEV *, 8> Visited; void push(const SCEV *S) { - if (Visitor.follow(S)) + if (Visited.insert(S) && Visitor.follow(S)) Worklist.push_back(S); } public: |