diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 36 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll | 21 |
2 files changed, 43 insertions, 14 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index b4c4da6..57c4265 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1974,7 +1974,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // multiplied together. If so, we can fold them. for (unsigned OtherIdx = Idx+1; OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); - ++OtherIdx) + ++OtherIdx) { + bool Retry = false; if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) { // {A,+,B}<L> * {C,+,D}<L> --> {A*C,+,A*D + B*C + B*D,+,2*B*D}<L> // @@ -1985,7 +1986,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // Rearranging, X = x, Y = y+z, Z = 2z. // // x = A*C, y = (A*D + B*C), z = B*D. - // Therefore X = A*C, Y = (A*D + B*C) + B*D and Z = 2*B*D. + // Therefore X = A*C, Y = A*D + B*C + B*D and Z = 2*B*D. for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); ++OtherIdx) if (const SCEVAddRecExpr *OtherAddRec = @@ -2002,19 +2003,28 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 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); - Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + // This can happen when AddRec or OtherAddRec have >3 operands. + // TODO: support these add-recs. + if (isLoopInvariant(NewStart, AddRecLoop) && + isLoopInvariant(NewStep, AddRecLoop) && + isLoopInvariant(NewSecondOrderStep, AddRecLoop)) { + 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); + Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + Retry = true; + } } - return getMulExpr(Ops); + if (Retry) + return getMulExpr(Ops); } + } // Otherwise couldn't fold anything into this recurrence. Move onto the // next one. diff --git a/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll b/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll index 2c4ef16..06f1b6f 100644 --- a/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll +++ b/test/Analysis/ScalarEvolution/SolveQuadraticEquation.ll @@ -35,7 +35,7 @@ return: ; preds = %bb5 ; PR10383 -; This used to crash. +; These next two used to crash. define void @test2(i1 %cmp, i64 %n) { entry: @@ -61,3 +61,22 @@ end: ret void } ; CHECK: Determining loop execution counts for: @test2 + +define i32 @test3() { +if.then466: + br i1 undef, label %for.cond539.preheader, label %for.inc479 + +for.inc479: + %a2.07 = phi i32 [ %add495, %for.inc479 ], [ 0, %if.then466 ] + %j.36 = phi i32 [ %inc497, %for.inc479 ], [ undef, %if.then466 ] + %mul484 = mul nsw i32 %j.36, %j.36 + %mul491 = mul i32 %j.36, %j.36 + %mul493 = mul i32 %mul491, %mul484 + %add495 = add nsw i32 %mul493, %a2.07 + %inc497 = add nsw i32 %j.36, 1 + br i1 undef, label %for.cond539.preheader, label %for.inc479 + +for.cond539.preheader: + unreachable +} +; CHECK: Determining loop execution counts for: @test3 |