diff options
author | Nick Lewycky <nicholas@mxc.ca> | 2008-11-16 04:14:25 +0000 |
---|---|---|
committer | Nick Lewycky <nicholas@mxc.ca> | 2008-11-16 04:14:25 +0000 |
commit | d72a81ee647b4474e2d1307335e520b871666507 (patch) | |
tree | 4f580217a4619efa170afbfecaaaff76ff531240 | |
parent | 808e3a92661c19cfc466523bfcc3cd506edad7ee (diff) | |
download | external_llvm-d72a81ee647b4474e2d1307335e520b871666507.zip external_llvm-d72a81ee647b4474e2d1307335e520b871666507.tar.gz external_llvm-d72a81ee647b4474e2d1307335e520b871666507.tar.bz2 |
Don't brute-force analyze cubic or higher polynomials.
If this patch causes a performance regression for anyone, please let me know,
and it can be fixed in a different way with much more effort.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59384 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 21 | ||||
-rw-r--r-- | test/Analysis/ScalarEvolution/2008-11-15-CubicOOM.ll | 19 |
2 files changed, 19 insertions, 21 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 3ff0935..3f43a79 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2967,27 +2967,6 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, } } - // Fallback, if this is a general polynomial, figure out the progression - // through brute force: evaluate until we find an iteration that fails the - // test. This is likely to be slow, but getting an accurate trip count is - // incredibly important, we will be able to simplify the exit test a lot, and - // we are almost guaranteed to get a trip count in this case. - ConstantInt *TestVal = ConstantInt::get(getType(), 0); - ConstantInt *EndVal = TestVal; // Stop when we wrap around. - do { - ++NumBruteForceEvaluations; - SCEVHandle Val = evaluateAtIteration(SE.getConstant(TestVal), SE); - if (!isa<SCEVConstant>(Val)) // This shouldn't happen. - return new SCEVCouldNotCompute(); - - // Check to see if we found the value! - if (!Range.contains(cast<SCEVConstant>(Val)->getValue()->getValue())) - return SE.getConstant(TestVal); - - // Increment to test the next index. - TestVal = ConstantInt::get(TestVal->getValue()+1); - } while (TestVal != EndVal); - return new SCEVCouldNotCompute(); } diff --git a/test/Analysis/ScalarEvolution/2008-11-15-CubicOOM.ll b/test/Analysis/ScalarEvolution/2008-11-15-CubicOOM.ll new file mode 100644 index 0000000..89e9efa --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-11-15-CubicOOM.ll @@ -0,0 +1,19 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution +; PR2602 + +define i32 @a() nounwind { +entry: + br label %bb + +bb: ; preds = %bb, %entry + %w.0 = phi i32 [ 0, %entry ], [ %tmp, %bb ] ; <i32> [#uses=2] + %e.0 = phi i32 [ 0, %entry ], [ %e.1, %bb ] ; <i32> [#uses=2] + %w.1 = add i32 0, %w.0 ; <i32>:0 [#uses=1] + %tmp = add i32 %e.0, %w.0 ; <i32>:1 [#uses=1] + %e.1 = add i32 %e.0, 1 ; <i32>:2 [#uses=1] + %cond = icmp eq i32 %w.1, -1 ; <i1>:3 [#uses=1] + br i1 %cond, label %return, label %bb + +return: ; preds = %bb + ret i32 undef +} |