diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1669,7 +1669,14 @@ Value *ExitCond, bool ExitIfTrue, bool ControlsExit, bool AllowPredicates); - + Optional + computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L, + Value *ExitCond, bool ExitIfTrue, + bool ControlsExit, bool AllowPredicates); + ExitLimit computeExitLimitFromCondFromBinOpHelper( + ExitLimitCacheTy &Cache, const Loop *L, BinaryOperator *BO, + bool EitherMayExit, bool ExitIfTrue, bool ControlsExit, + bool AllowPredicates, const Constant *NeutralElement); /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of the ICmpInst /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -7521,114 +7521,10 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsExit, bool AllowPredicates) { - // Check if the controlling expression for this loop is an And or Or. - if (BinaryOperator *BO = dyn_cast(ExitCond)) { - if (BO->getOpcode() == Instruction::And) { - // Recurse on the operands of the and. - bool EitherMayExit = !ExitIfTrue; - ExitLimit EL0 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(0), ExitIfTrue, - ControlsExit && !EitherMayExit, AllowPredicates); - ExitLimit EL1 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(1), ExitIfTrue, - ControlsExit && !EitherMayExit, AllowPredicates); - // Be robust against unsimplified IR for the form "and i1 X, true" - if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) - return CI->isOne() ? EL0 : EL1; - if (ConstantInt *CI = dyn_cast(BO->getOperand(0))) - return CI->isOne() ? EL1 : EL0; - const SCEV *BECount = getCouldNotCompute(); - const SCEV *MaxBECount = getCouldNotCompute(); - if (EitherMayExit) { - // Both conditions must be true for the loop to continue executing. - // Choose the less conservative count. - if (EL0.ExactNotTaken == getCouldNotCompute() || - EL1.ExactNotTaken == getCouldNotCompute()) - BECount = getCouldNotCompute(); - else - BECount = - getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken); - if (EL0.MaxNotTaken == getCouldNotCompute()) - MaxBECount = EL1.MaxNotTaken; - else if (EL1.MaxNotTaken == getCouldNotCompute()) - MaxBECount = EL0.MaxNotTaken; - else - MaxBECount = - getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken); - } else { - // Both conditions must be true at the same time for the loop to exit. - // For now, be conservative. - if (EL0.MaxNotTaken == EL1.MaxNotTaken) - MaxBECount = EL0.MaxNotTaken; - if (EL0.ExactNotTaken == EL1.ExactNotTaken) - BECount = EL0.ExactNotTaken; - } - - // There are cases (e.g. PR26207) where computeExitLimitFromCond is able - // to be more aggressive when computing BECount than when computing - // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and - // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken - // to not. - if (isa(MaxBECount) && - !isa(BECount)) - MaxBECount = getConstant(getUnsignedRangeMax(BECount)); - - return ExitLimit(BECount, MaxBECount, false, - {&EL0.Predicates, &EL1.Predicates}); - } - if (BO->getOpcode() == Instruction::Or) { - // Recurse on the operands of the or. - bool EitherMayExit = ExitIfTrue; - ExitLimit EL0 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(0), ExitIfTrue, - ControlsExit && !EitherMayExit, AllowPredicates); - ExitLimit EL1 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(1), ExitIfTrue, - ControlsExit && !EitherMayExit, AllowPredicates); - // Be robust against unsimplified IR for the form "or i1 X, true" - if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) - return CI->isZero() ? EL0 : EL1; - if (ConstantInt *CI = dyn_cast(BO->getOperand(0))) - return CI->isZero() ? EL1 : EL0; - const SCEV *BECount = getCouldNotCompute(); - const SCEV *MaxBECount = getCouldNotCompute(); - if (EitherMayExit) { - // Both conditions must be false for the loop to continue executing. - // Choose the less conservative count. - if (EL0.ExactNotTaken == getCouldNotCompute() || - EL1.ExactNotTaken == getCouldNotCompute()) - BECount = getCouldNotCompute(); - else - BECount = - getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken); - if (EL0.MaxNotTaken == getCouldNotCompute()) - MaxBECount = EL1.MaxNotTaken; - else if (EL1.MaxNotTaken == getCouldNotCompute()) - MaxBECount = EL0.MaxNotTaken; - else - MaxBECount = - getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken); - } else { - // Both conditions must be false at the same time for the loop to exit. - // For now, be conservative. - if (EL0.MaxNotTaken == EL1.MaxNotTaken) - MaxBECount = EL0.MaxNotTaken; - if (EL0.ExactNotTaken == EL1.ExactNotTaken) - BECount = EL0.ExactNotTaken; - } - // There are cases (e.g. PR26207) where computeExitLimitFromCond is able - // to be more aggressive when computing BECount than when computing - // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and - // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken - // to not. - if (isa(MaxBECount) && - !isa(BECount)) - MaxBECount = getConstant(getUnsignedRangeMax(BECount)); - - return ExitLimit(BECount, MaxBECount, false, - {&EL0.Predicates, &EL1.Predicates}); - } - } + // Handle BinOp conditions (And, Or). + if (auto LimitFromBinOp = computeExitLimitFromCondFromBinOp( + Cache, L, ExitCond, ExitIfTrue, ControlsExit, AllowPredicates)) + return *LimitFromBinOp; // With an icmp, it may be feasible to compute an exact backedge-taken count. // Proceed to the next level to examine the icmp. @@ -7660,6 +7556,80 @@ return computeExitCountExhaustively(L, ExitCond, ExitIfTrue); } +Optional +ScalarEvolution::computeExitLimitFromCondFromBinOp( + ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue, + bool ControlsExit, bool AllowPredicates) { + // Check if the controlling expression for this loop is an And or Or. + if (auto *BO = dyn_cast(ExitCond)) { + if (BO->getOpcode() == Instruction::And) + return computeExitLimitFromCondFromBinOpHelper( + Cache, L, BO, !ExitIfTrue, ExitIfTrue, ControlsExit, AllowPredicates, + ConstantInt::get(BO->getType(), 1)); + if (BO->getOpcode() == Instruction::Or) + return computeExitLimitFromCondFromBinOpHelper( + Cache, L, BO, ExitIfTrue, ExitIfTrue, ControlsExit, AllowPredicates, + ConstantInt::get(BO->getType(), 0)); + } + return None; +} + +ScalarEvolution::ExitLimit +ScalarEvolution::computeExitLimitFromCondFromBinOpHelper( + ExitLimitCacheTy &Cache, const Loop *L, BinaryOperator *BO, + bool EitherMayExit, bool ExitIfTrue, bool ControlsExit, + bool AllowPredicates, const Constant *NeutralElement) { + ExitLimit EL0 = computeExitLimitFromCondCached( + Cache, L, BO->getOperand(0), ExitIfTrue, ControlsExit && !EitherMayExit, + AllowPredicates); + ExitLimit EL1 = computeExitLimitFromCondCached( + Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, + AllowPredicates); + // Be robust against unsimplified IR for the form "op i1 X, + // NeutralElement" + if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) + return CI == NeutralElement ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast(BO->getOperand(0))) + return CI == NeutralElement ? EL1 : EL0; + const SCEV *BECount = getCouldNotCompute(); + const SCEV *MaxBECount = getCouldNotCompute(); + if (EitherMayExit) { + // Both conditions must be same for the loop to continue executing. + // Choose the less conservative count. + if (EL0.ExactNotTaken == getCouldNotCompute() || + EL1.ExactNotTaken == getCouldNotCompute()) + BECount = getCouldNotCompute(); + else + BECount = + getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken); + if (EL0.MaxNotTaken == getCouldNotCompute()) + MaxBECount = EL1.MaxNotTaken; + else if (EL1.MaxNotTaken == getCouldNotCompute()) + MaxBECount = EL0.MaxNotTaken; + else + MaxBECount = getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken); + } else { + // Both conditions must be same at the same time for the loop to exit. + // For now, be conservative. + if (EL0.MaxNotTaken == EL1.MaxNotTaken) + MaxBECount = EL0.MaxNotTaken; + if (EL0.ExactNotTaken == EL1.ExactNotTaken) + BECount = EL0.ExactNotTaken; + } + + // There are cases (e.g. PR26207) where computeExitLimitFromCond is able + // to be more aggressive when computing BECount than when computing + // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and + // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken + // to not. + if (isa(MaxBECount) && + !isa(BECount)) + MaxBECount = getConstant(getUnsignedRangeMax(BECount)); + + return ExitLimit(BECount, MaxBECount, false, + { &EL0.Predicates, &EL1.Predicates }); +} + ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,