From 1104645eefa134ff3dd2c911d2aaa0dffb38f59f Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 29 Jun 2010 23:43:06 +0000 Subject: [PATCH] Fix ScalarEvolution's tripcount computation for chains of loops where each loop's induction variable's start value is the exit value of a preceding loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107224 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 102 ++++++++++++--------- .../Transforms/IndVarSimplify/tripcount_compute.ll | 66 ++++++++++++- 2 files changed, 125 insertions(+), 43 deletions(-) diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index a416764cda2..b5acd6bfd6e 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4337,54 +4337,51 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { - std::vector Operands; - Operands.reserve(I->getNumOperands()); + SmallVector Operands; + bool MadeImprovement = false; for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *Op = I->getOperand(i); if (Constant *C = dyn_cast(Op)) { Operands.push_back(C); - } else { - // If any of the operands is non-constant and if they are - // non-integer and non-pointer, don't even try to analyze them - // with scev techniques. - if (!isSCEVable(Op->getType())) - return V; - - const SCEV *OpV = getSCEVAtScope(Op, L); - if (const SCEVConstant *SC = dyn_cast(OpV)) { - Constant *C = SC->getValue(); - if (C->getType() != Op->getType()) - C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else if (const SCEVUnknown *SU = dyn_cast(OpV)) { - if (Constant *C = dyn_cast(SU->getValue())) { - if (C->getType() != Op->getType()) - C = - ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else - return V; - } else { - return V; - } + continue; } + + // If any of the operands is non-constant and if they are + // non-integer and non-pointer, don't even try to analyze them + // with scev techniques. + if (!isSCEVable(Op->getType())) + return V; + + const SCEV *OrigV = getSCEV(Op); + const SCEV *OpV = getSCEVAtScope(OrigV, L); + MadeImprovement |= OrigV != OpV; + + Constant *C = 0; + if (const SCEVConstant *SC = dyn_cast(OpV)) + C = SC->getValue(); + if (const SCEVUnknown *SU = dyn_cast(OpV)) + C = dyn_cast(SU->getValue()); + if (!C) return V; + if (C->getType() != Op->getType()) + C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, + Op->getType(), + false), + C, Op->getType()); + Operands.push_back(C); } - Constant *C = 0; - if (const CmpInst *CI = dyn_cast(I)) - C = ConstantFoldCompareInstOperands(CI->getPredicate(), - Operands[0], Operands[1], TD); - else - C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), - &Operands[0], Operands.size(), TD); - if (C) + // Check to see if getSCEVAtScope actually made an improvement. + if (MadeImprovement) { + Constant *C = 0; + if (const CmpInst *CI = dyn_cast(I)) + C = ConstantFoldCompareInstOperands(CI->getPredicate(), + Operands[0], Operands[1], TD); + else + C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), + &Operands[0], Operands.size(), TD); + if (!C) return V; return getSCEV(C); + } } } @@ -4434,7 +4431,29 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // If this is a loop recurrence for a loop that does not contain L, then we // are dealing with the final value computed by the loop. if (const SCEVAddRecExpr *AddRec = dyn_cast(V)) { - if (!L || !AddRec->getLoop()->contains(L)) { + // First, attempt to evaluate each operand. + // Avoid performing the look-up in the common case where the specified + // expression has no loop-variant portions. + for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { + const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); + if (OpAtScope == AddRec->getOperand(i)) + continue; + + // Okay, at least one of these operands is loop variant but might be + // foldable. Build a new instance of the folded commutative expression. + SmallVector NewOps(AddRec->op_begin(), + AddRec->op_begin()+i); + NewOps.push_back(OpAtScope); + for (++i; i != e; ++i) + NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L)); + + AddRec = cast(getAddRecExpr(NewOps, AddRec->getLoop())); + break; + } + + // If the scope is outside the addrec's loop, evaluate it by using the + // loop exit value of the addrec. + if (!AddRec->getLoop()->contains(L)) { // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); @@ -4443,6 +4462,7 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // Then, evaluate the AddRec. return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); } + return AddRec; } diff --git a/test/Transforms/IndVarSimplify/tripcount_compute.ll b/test/Transforms/IndVarSimplify/tripcount_compute.ll index 6eaa4c5c6b6..8835b9627fd 100644 --- a/test/Transforms/IndVarSimplify/tripcount_compute.ll +++ b/test/Transforms/IndVarSimplify/tripcount_compute.ll @@ -1,9 +1,12 @@ +; RUN: opt < %s -indvars -S | FileCheck %s + ; These tests ensure that we can compute the trip count of various forms of ; loops. If the trip count of the loop is computable, then we will know what ; the exit value of the loop will be for some value, allowing us to substitute ; it directly into users outside of the loop, making the loop dead. -; -; RUN: opt < %s -indvars -loop-deletion -simplifycfg -S | not grep br + +; CHECK: @linear_setne +; CHECK: ret i32 100 define i32 @linear_setne() { entry: @@ -19,6 +22,9 @@ loopexit: ; preds = %loop ret i32 %i } +; CHECK: @linear_setne_2 +; CHECK: ret i32 100 + define i32 @linear_setne_2() { entry: br label %loop @@ -33,6 +39,9 @@ loopexit: ; preds = %loop ret i32 %i } +; CHECK: @linear_setne_overflow +; CHECK: ret i32 0 + define i32 @linear_setne_overflow() { entry: br label %loop @@ -47,6 +56,9 @@ loopexit: ; preds = %loop ret i32 %i } +; CHECK: @linear_setlt +; CHECK: ret i32 100 + define i32 @linear_setlt() { entry: br label %loop @@ -61,6 +73,9 @@ loopexit: ; preds = %loop ret i32 %i } +; CHECK: @quadratic_setlt +; CHECK: ret i32 34 + define i32 @quadratic_setlt() { entry: br label %loop @@ -76,6 +91,9 @@ loopexit: ; preds = %loop ret i32 %i } +; CHECK: @chained +; CHECK: ret i32 200 + define i32 @chained() { entry: br label %loop @@ -98,3 +116,47 @@ loop2: ; preds = %loop2, %loopexit loopexit2: ; preds = %loop2 ret i32 %j } + +; CHECK: @chained4 +; CHECK: ret i32 400 + +define i32 @chained4() { +entry: + br label %loop + +loop: ; preds = %loop, %entry + %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] ; [#uses=3] + %i.next = add i32 %i, 1 ; [#uses=1] + %c = icmp ne i32 %i.next, 100 ; [#uses=1] + br i1 %c, label %loop, label %loopexit + +loopexit: ; preds = %loop + br label %loop2 + +loop2: ; preds = %loop2, %loopexit + %j = phi i32 [ %i.next, %loopexit ], [ %j.next, %loop2 ] ; [#uses=3] + %j.next = add i32 %j, 1 ; [#uses=1] + %c2 = icmp ne i32 %j.next, 200 ; [#uses=1] + br i1 %c2, label %loop2, label %loopexit2 + +loopexit2: ; preds = %loop + br label %loop8 + +loop8: ; preds = %loop2, %loopexit + %k = phi i32 [ %j.next, %loopexit2 ], [ %k.next, %loop8 ] ; [#uses=3] + %k.next = add i32 %k, 1 ; [#uses=1] + %c8 = icmp ne i32 %k.next, 300 ; [#uses=1] + br i1 %c8, label %loop8, label %loopexit8 + +loopexit8: ; preds = %loop2 + br label %loop9 + +loop9: ; preds = %loop2, %loopexit + %l = phi i32 [ %k.next, %loopexit8 ], [ %l.next, %loop9 ] ; [#uses=3] + %l.next = add i32 %l, 1 ; [#uses=1] + %c9 = icmp ne i32 %l.next, 400 ; [#uses=1] + br i1 %c9, label %loop9, label %loopexit9 + +loopexit9: ; preds = %loop2 + ret i32 %l.next +} -- 2.11.0