diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 33 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll | 37 |
2 files changed, 54 insertions, 16 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 8859c3b..6d28f69 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1735,7 +1735,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; - // Otherwise, add the folded AddRec by the non-liv parts. + // Otherwise, add the folded AddRec by the non-live parts. for (unsigned i = 0;; ++i) if (Ops[i] == AddRec) { Ops[i] = NewRec; @@ -1960,7 +1960,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; - // Otherwise, multiply the folded AddRec by the non-liv parts. + // Otherwise, multiply the folded AddRec by the non-live parts. for (unsigned i = 0;; ++i) if (Ops[i] == AddRec) { Ops[i] = NewRec; @@ -1976,22 +1976,29 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); ++OtherIdx) if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) { - // F * G, where F = {A,+,B}<L> and G = {C,+,D}<L> --> - // {A*C,+,F*D + G*B + B*D}<L> + // {A,+,B}<L> * {C,+,D}<L> --> {A*C,+,A*D + B*C + B*D,+,2*B*D}<L> for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); ++OtherIdx) if (const SCEVAddRecExpr *OtherAddRec = dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx])) if (OtherAddRec->getLoop() == AddRecLoop) { - const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; - const SCEV *NewStart = getMulExpr(F->getStart(), G->getStart()); - const SCEV *B = F->getStepRecurrence(*this); - const SCEV *D = G->getStepRecurrence(*this); - const SCEV *NewStep = getAddExpr(getMulExpr(F, D), - getMulExpr(G, B), - getMulExpr(B, D)); - const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep, - F->getLoop(), + const SCEV *A = AddRec->getStart(); + const SCEV *B = AddRec->getStepRecurrence(*this); + const SCEV *C = OtherAddRec->getStart(); + const SCEV *D = OtherAddRec->getStepRecurrence(*this); + const SCEV *NewStart = getMulExpr(A, C); + const SCEV *BD = getMulExpr(B, D); + const SCEV *NewStep = getAddExpr(getMulExpr(A, D), + getMulExpr(B, C), BD); + const SCEV *NewSecondOrderStep = + getMulExpr(BD, getConstant(BD->getType(), 2)); + + SmallVector<const SCEV *, 3> AddRecOps; + AddRecOps.push_back(NewStart); + AddRecOps.push_back(NewStep); + AddRecOps.push_back(NewSecondOrderStep); + const SCEV *NewAddRec = getAddRecExpr(AddRecOps, + AddRec->getLoop(), SCEV::FlagAnyWrap); if (Ops.size() == 2) return NewAddRec; Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec); diff --git a/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll b/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll index ec95141..2c4ef16 100644 --- a/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll +++ b/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll @@ -1,11 +1,11 @@ ; RUN: opt < %s -analyze -scalar-evolution \ -; RUN: -scalar-evolution-max-iterations=0 | grep {backedge-taken count is 100} +; RUN: -scalar-evolution-max-iterations=0 | FileCheck %s + ; PR1101 @A = weak global [1000 x i32] zeroinitializer, align 32 - -define void @test(i32 %N) { +define void @test1(i32 %N) { entry: %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0] br label %bb3 @@ -30,3 +30,34 @@ bb5: ; preds = %bb3 return: ; preds = %bb5 ret void } +; CHECK: Determining loop execution counts for: @test1 +; CHECK-NEXT: backedge-taken count is 100 + + +; PR10383 +; This used to crash. + +define void @test2(i1 %cmp, i64 %n) { +entry: + br label %for.body1 + +for.body1: + %a0.08 = phi i64 [ 0, %entry ], [ %inc512, %for.body1 ] + %inc512 = add i64 %a0.08, 1 + br i1 %cmp, label %preheader, label %for.body1 + +preheader: + br label %for.body2 + +for.body2: + %indvar = phi i64 [ 0, %preheader ], [ %indvar.next, %for.body2 ] + %tmp111 = add i64 %n, %indvar + %tmp114 = mul i64 %a0.08, %indvar + %mul542 = mul i64 %tmp114, %tmp111 + %indvar.next = add i64 %indvar, 1 + br i1 undef, label %end, label %for.body2 + +end: + ret void +} +; CHECK: Determining loop execution counts for: @test2 |