This is an archive of the discontinued LLVM Phabricator instance.

Differential D91864

[NFC] Reduce code duplication in binop processing in computeExitLimitFromCondCached
ClosedPublic

Authored by mkazantsev on Nov 20 2020, 5:13 AM.

Details

Reviewers
nikic
reames
lebedev.ri
Commits
rG47e31d1b5eac: [NFC] Reduce code duplication in binop processing in…
Summary

Handling of and and or vastly uses copy-paste. Factored out into
a helper function as preparation step for further fix (see PR48225).

Diff Detail

Event Timeline

mkazantsev created this revision.Nov 20 2020, 5:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 20 2020, 5:13 AM
Herald added subscribers: llvm-commits, hiraditya. · View Herald Transcript
mkazantsev requested review of this revision.Nov 20 2020, 5:13 AM
nikic accepted this revision.Nov 21 2020, 8:51 AM

LGTM

This revision is now accepted and ready to land.Nov 21 2020, 8:51 AM
Closed by commit rG47e31d1b5eac: [NFC] Reduce code duplication in binop processing in… (authored by mkazantsev). · Explain WhyNov 22 2020, 11:08 PM
This revision was automatically updated to reflect the committed changes.
mkazantsev added a commit: rG47e31d1b5eac: [NFC] Reduce code duplication in binop processing in….

Revision Contents

PathSize
llvm/
include/
llvm/
Analysis/
9 lines
lib/
Analysis/
186 lines

Diff 306959

llvm/include/llvm/Analysis/ScalarEvolution.h

Show First 20 Lines • Show All 1,663 Lines • ▼ Show 20 Lines ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
const Loop *L, Value *ExitCond, const Loop *L, Value *ExitCond,
bool ExitIfTrue, bool ExitIfTrue,
bool ControlsExit, bool ControlsExit,
bool AllowPredicates); bool AllowPredicates);
ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
Value *ExitCond, bool ExitIfTrue, Value *ExitCond, bool ExitIfTrue,
bool ControlsExit, bool ControlsExit,
bool AllowPredicates); bool AllowPredicates);
Optional<ScalarEvolution::ExitLimit>
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 /// Compute the number of times the backedge of the specified loop will
/// execute if its exit condition were a conditional branch of the ICmpInst /// execute if its exit condition were a conditional branch of the ICmpInst
/// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
/// to use a minimal set of SCEV predicates in order to return an exact /// to use a minimal set of SCEV predicates in order to return an exact
/// answer. /// answer.
ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue, bool ExitIfTrue,
bool IsSubExpr, bool IsSubExpr,
▲ Show 20 Lines • Show All 519 Lines • Show Last 20 Lines

llvm/lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 7,515 Lines • ▼ Show 20 Lines ExitLimit EL = computeExitLimitFromCondImpl(Cache, L, ExitCond, ExitIfTrue,
ControlsExit, AllowPredicates); ControlsExit, AllowPredicates);
Cache.insert(L, ExitCond, ExitIfTrue, ControlsExit, AllowPredicates, EL); Cache.insert(L, ExitCond, ExitIfTrue, ControlsExit, AllowPredicates, EL);
return EL; return EL;
} }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue, ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
bool ControlsExit, bool AllowPredicates) { bool ControlsExit, bool AllowPredicates) {
// Check if the controlling expression for this loop is an And or Or. // Handle BinOp conditions (And, Or).
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) { if (auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
if (BO->getOpcode() == Instruction::And) { Cache, L, ExitCond, ExitIfTrue, ControlsExit, AllowPredicates))
// Recurse on the operands of the and. return *LimitFromBinOp;
bool EitherMayExit = !ExitIfTrue;
ExitLimit EL0 = computeExitLimitFromCondCached( // With an icmp, it may be feasible to compute an exact backedge-taken count.
Cache, L, BO->getOperand(0), ExitIfTrue, // Proceed to the next level to examine the icmp.
ControlsExit && !EitherMayExit, AllowPredicates); if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
ExitLimit EL1 = computeExitLimitFromCondCached( ExitLimit EL =
Cache, L, BO->getOperand(1), ExitIfTrue, computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsExit);
ControlsExit && !EitherMayExit, AllowPredicates); if (EL.hasFullInfo() || !AllowPredicates)
// Be robust against unsimplified IR for the form "and i1 X, true" return EL;
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1)))
return CI->isOne() ? EL0 : EL1; // Try again, but use SCEV predicates this time.
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsExit,
return CI->isOne() ? EL1 : EL0; /*AllowPredicates=*/true);
const SCEV *BECount = getCouldNotCompute(); }
const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) { // Check for a constant condition. These are normally stripped out by
// Both conditions must be true for the loop to continue executing. // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
// Choose the less conservative count. // preserve the CFG and is temporarily leaving constant conditions
if (EL0.ExactNotTaken == getCouldNotCompute() || // in place.
EL1.ExactNotTaken == getCouldNotCompute()) if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
BECount = getCouldNotCompute(); if (ExitIfTrue == !CI->getZExtValue())
else // The backedge is always taken.
BECount = return getCouldNotCompute();
getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken);
if (EL0.MaxNotTaken == getCouldNotCompute())
MaxBECount = EL1.MaxNotTaken;
else if (EL1.MaxNotTaken == getCouldNotCompute())
MaxBECount = EL0.MaxNotTaken;
else else
MaxBECount = // The backedge is never taken.
getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken); return getZero(CI->getType());
} 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 // If it's not an integer or pointer comparison then compute it the hard way.
// to be more aggressive when computing BECount than when computing return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
// 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<SCEVCouldNotCompute>(MaxBECount) &&
!isa<SCEVCouldNotCompute>(BECount))
MaxBECount = getConstant(getUnsignedRangeMax(BECount));
return ExitLimit(BECount, MaxBECount, false, Optional<ScalarEvolution::ExitLimit>
{&EL0.Predicates, &EL1.Predicates}); 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<BinaryOperator>(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;
} }
if (BO->getOpcode() == Instruction::Or) {
// Recurse on the operands of the or. ScalarEvolution::ExitLimit
bool EitherMayExit = ExitIfTrue; ScalarEvolution::computeExitLimitFromCondFromBinOpHelper(
ExitLimitCacheTy &Cache, const Loop *L, BinaryOperator *BO,
bool EitherMayExit, bool ExitIfTrue, bool ControlsExit,
bool AllowPredicates, const Constant *NeutralElement) {
ExitLimit EL0 = computeExitLimitFromCondCached( ExitLimit EL0 = computeExitLimitFromCondCached(
Cache, L, BO->getOperand(0), ExitIfTrue, Cache, L, BO->getOperand(0), ExitIfTrue, ControlsExit && !EitherMayExit,
ControlsExit && !EitherMayExit, AllowPredicates); AllowPredicates);
ExitLimit EL1 = computeExitLimitFromCondCached( ExitLimit EL1 = computeExitLimitFromCondCached(
Cache, L, BO->getOperand(1), ExitIfTrue, Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit,
ControlsExit && !EitherMayExit, AllowPredicates); AllowPredicates);
// Be robust against unsimplified IR for the form "or i1 X, true" // Be robust against unsimplified IR for the form "op i1 X,
// NeutralElement"
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1)))
return CI->isZero() ? EL0 : EL1; return CI == NeutralElement ? EL0 : EL1;
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0)))
return CI->isZero() ? EL1 : EL0; return CI == NeutralElement ? EL1 : EL0;
const SCEV *BECount = getCouldNotCompute(); const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) { if (EitherMayExit) {
// Both conditions must be false for the loop to continue executing. // Both conditions must be same for the loop to continue executing.
// Choose the less conservative count. // Choose the less conservative count.
if (EL0.ExactNotTaken == getCouldNotCompute() || if (EL0.ExactNotTaken == getCouldNotCompute() ||
EL1.ExactNotTaken == getCouldNotCompute()) EL1.ExactNotTaken == getCouldNotCompute())
BECount = getCouldNotCompute(); BECount = getCouldNotCompute();
else else
BECount = BECount =
getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken); getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken);
if (EL0.MaxNotTaken == getCouldNotCompute()) if (EL0.MaxNotTaken == getCouldNotCompute())
MaxBECount = EL1.MaxNotTaken; MaxBECount = EL1.MaxNotTaken;
else if (EL1.MaxNotTaken == getCouldNotCompute()) else if (EL1.MaxNotTaken == getCouldNotCompute())
MaxBECount = EL0.MaxNotTaken; MaxBECount = EL0.MaxNotTaken;
else else
MaxBECount = MaxBECount = getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken);
getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken);
} else { } else {
// Both conditions must be false at the same time for the loop to exit. // Both conditions must be same at the same time for the loop to exit.
// For now, be conservative. // For now, be conservative.
if (EL0.MaxNotTaken == EL1.MaxNotTaken) if (EL0.MaxNotTaken == EL1.MaxNotTaken)
MaxBECount = EL0.MaxNotTaken; MaxBECount = EL0.MaxNotTaken;
if (EL0.ExactNotTaken == EL1.ExactNotTaken) if (EL0.ExactNotTaken == EL1.ExactNotTaken)
BECount = EL0.ExactNotTaken; BECount = EL0.ExactNotTaken;
} }
// There are cases (e.g. PR26207) where computeExitLimitFromCond is able // There are cases (e.g. PR26207) where computeExitLimitFromCond is able
// to be more aggressive when computing BECount than when computing // to be more aggressive when computing BECount than when computing
// MaxBECount. In these cases it is possible for EL0.ExactNotTaken and // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and
// EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken
// to not. // to not.
if (isa<SCEVCouldNotCompute>(MaxBECount) && if (isa<SCEVCouldNotCompute>(MaxBECount) &&
!isa<SCEVCouldNotCompute>(BECount)) !isa<SCEVCouldNotCompute>(BECount))
MaxBECount = getConstant(getUnsignedRangeMax(BECount)); MaxBECount = getConstant(getUnsignedRangeMax(BECount));
return ExitLimit(BECount, MaxBECount, false, return ExitLimit(BECount, MaxBECount, false,
{&EL0.Predicates, &EL1.Predicates}); { &EL0.Predicates, &EL1.Predicates });
} }
}
// With an icmp, it may be feasible to compute an exact backedge-taken count.
// Proceed to the next level to examine the icmp.
if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
ExitLimit EL =
computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsExit);
if (EL.hasFullInfo() || !AllowPredicates)
return EL;
// Try again, but use SCEV predicates this time.
return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsExit,
/*AllowPredicates=*/true);
}
// Check for a constant condition. These are normally stripped out by
// SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
// preserve the CFG and is temporarily leaving constant conditions
// in place.
if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
if (ExitIfTrue == !CI->getZExtValue())
// The backedge is always taken.
return getCouldNotCompute();
else
// The backedge is never taken.
return getZero(CI->getType());
}
// If it's not an integer or pointer comparison then compute it the hard way.
return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
}
ScalarEvolution::ExitLimit ScalarEvolution::ExitLimit
ScalarEvolution::computeExitLimitFromICmp(const Loop *L, ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
ICmpInst *ExitCond, ICmpInst *ExitCond,
bool ExitIfTrue, bool ExitIfTrue,
bool ControlsExit, bool ControlsExit,
bool AllowPredicates) { bool AllowPredicates) {
// If the condition was exit on true, convert the condition to exit on false // If the condition was exit on true, convert the condition to exit on false
▲ Show 20 Lines • Show All 5,681 Lines • Show Last 20 Lines