diff options
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 7 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 36 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll | 7 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/trip-count3.ll | 6 | ||||
| -rw-r--r-- | test/Transforms/IndVarSimplify/loop_evaluate_6.ll | 6 |
5 files changed, 51 insertions, 11 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 211c0ca..8578958 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -332,6 +332,13 @@ namespace llvm { const SCEVHandle &SymName, const SCEVHandle &NewVal); + /// getBECount - Subtract the end and start values and divide by the step, + /// rounding up, to get the number of times the backedge is executed. Return + /// CouldNotCompute if an intermediate computation overflows. + SCEVHandle getBECount(const SCEVHandle &Start, + const SCEVHandle &End, + const SCEVHandle &Step); + /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed /// yet. diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 5a7e1b6..272aeb3 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -3788,6 +3788,33 @@ bool ScalarEvolution::isLoopGuardedByCond(const Loop *L, return false; } +/// getBECount - Subtract the end and start values and divide by the step, +/// rounding up, to get the number of times the backedge is executed. Return +/// CouldNotCompute if an intermediate computation overflows. +SCEVHandle ScalarEvolution::getBECount(const SCEVHandle &Start, + const SCEVHandle &End, + const SCEVHandle &Step) { + const Type *Ty = Start->getType(); + SCEVHandle NegOne = getIntegerSCEV(-1, Ty); + SCEVHandle Diff = getMinusSCEV(End, Start); + SCEVHandle RoundUp = getAddExpr(Step, NegOne); + + // Add an adjustment to the difference between End and Start so that + // the division will effectively round up. + SCEVHandle Add = getAddExpr(Diff, RoundUp); + + // Check Add for unsigned overflow. + // TODO: More sophisticated things could be done here. + const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1); + SCEVHandle OperandExtendedAdd = + getAddExpr(getZeroExtendExpr(Diff, WideTy), + getZeroExtendExpr(RoundUp, WideTy)); + if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd) + return CouldNotCompute; + + return getUDivExpr(Add, Step); +} + /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// CouldNotCompute. @@ -3869,16 +3896,11 @@ HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // Finally, we subtract these two values and divide, rounding up, to get // the number of times the backedge is executed. - SCEVHandle BECount = getUDivExpr(getAddExpr(getMinusSCEV(End, Start), - getAddExpr(Step, NegOne)), - Step); + SCEVHandle BECount = getBECount(Start, End, Step); // The maximum backedge count is similar, except using the minimum start // value and the maximum end value. - SCEVHandle MaxBECount = getUDivExpr(getAddExpr(getMinusSCEV(MaxEnd, - MinStart), - getAddExpr(Step, NegOne)), - Step); + SCEVHandle MaxBECount = getBECount(MinStart, MaxEnd, Step);; return BackedgeTakenInfo(BECount, MaxBECount); } diff --git a/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll b/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll index fc6bbb1..8fb1604 100644 --- a/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll +++ b/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll @@ -1,4 +1,9 @@ -; RUN: llvm-as < %s | opt -analyze -scalar-evolution -disable-output |& grep {/u 3} +; RUN: llvm-as < %s | opt -analyze -scalar-evolution -disable-output \ +; RUN: | grep {Loop bb: Unpredictable backedge-taken count\\.} + +; ScalarEvolution can't compute a trip count because it doesn't know if +; dividing by the stride will have a remainder. This could theoretically +; be teaching it how to use a more elaborate trip count computation. define i32 @f(i32 %x) nounwind readnone { entry: diff --git a/test/Analysis/ScalarEvolution/trip-count3.ll b/test/Analysis/ScalarEvolution/trip-count3.ll index a95138f..35c8683 100644 --- a/test/Analysis/ScalarEvolution/trip-count3.ll +++ b/test/Analysis/ScalarEvolution/trip-count3.ll @@ -1,5 +1,9 @@ ; RUN: llvm-as < %s | opt -scalar-evolution -analyze -disable-output \ -; RUN: | grep {backedge-taken count is ((64 + (-64 smax (-1 + (-1 \\* %0))) + %0) /u 64)} +; RUN: | grep {Loop bb3\\.i: Unpredictable backedge-taken count\\.} + +; ScalarEvolution can't compute a trip count because it doesn't know if +; dividing by the stride will have a remainder. This could theoretically +; be teaching it how to use a more elaborate trip count computation. target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" target triple = "x86_64-unknown-linux-gnu" diff --git a/test/Transforms/IndVarSimplify/loop_evaluate_6.ll b/test/Transforms/IndVarSimplify/loop_evaluate_6.ll index 35fbf52..0d17a80 100644 --- a/test/Transforms/IndVarSimplify/loop_evaluate_6.ll +++ b/test/Transforms/IndVarSimplify/loop_evaluate_6.ll @@ -1,7 +1,9 @@ ; RUN: llvm-as < %s | opt -indvars -loop-deletion | llvm-dis | grep phi | count 1 +; XFAIL: * -; Indvars should be able to evaluate this loop, allowing loop deletion -; to delete it. +; Indvars can't evaluate this loop, because ScalarEvolution can't compute +; an exact trip count, because it doesn't know if dividing by the stride will +; have a remainder. It could be done with more aggressive VRP though. define i32 @test(i32 %x_offs) nounwind readnone { entry: |