Please use GitHub pull requests for new patches. Phabricator shutdown timeline
Changeset View
Standalone View
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 9,095 Lines • ▼ Show 20 Lines | if (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) { | ||||
// If there is a loop-invariant, force it into the RHS. | // If there is a loop-invariant, force it into the RHS. | ||||
std::swap(LHS, RHS); | std::swap(LHS, RHS); | ||||
Pred = ICmpInst::getSwappedPredicate(Pred); | Pred = ICmpInst::getSwappedPredicate(Pred); | ||||
} | } | ||||
bool ControllingFiniteLoop = | bool ControllingFiniteLoop = | ||||
ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L); | ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L); | ||||
// Simplify the operands before analyzing them. | // Simplify the operands before analyzing them. | ||||
(void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0, | (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0); | ||||
(EnableFiniteLoopControl ? ControllingFiniteLoop | |||||
: false)); | |||||
// If we have a comparison of a chrec against a constant, try to use value | // If we have a comparison of a chrec against a constant, try to use value | ||||
// ranges to answer this query. | // ranges to answer this query. | ||||
if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) | if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) | ||||
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) | if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) | ||||
if (AddRec->getLoop() == L) { | if (AddRec->getLoop() == L) { | ||||
// Form the constant range. | // Form the constant range. | ||||
ConstantRange CompRange = | ConstantRange CompRange = | ||||
▲ Show 20 Lines • Show All 56 Lines • ▼ Show 20 Lines | if (RHS->getType()->isPointerTy()) { | ||||
RHS = getLosslessPtrToIntExpr(RHS); | RHS = getLosslessPtrToIntExpr(RHS); | ||||
if (isa<SCEVCouldNotCompute>(RHS)) | if (isa<SCEVCouldNotCompute>(RHS)) | ||||
return RHS; | return RHS; | ||||
} | } | ||||
ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L); | ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L); | ||||
if (EL.hasAnyInfo()) return EL; | if (EL.hasAnyInfo()) return EL; | ||||
break; | break; | ||||
} | } | ||||
case ICmpInst::ICMP_SLE: | |||||
case ICmpInst::ICMP_ULE: | |||||
// Since the loop is finite, an invariant RHS cannot include the boundary | |||||
// value, otherwise it would loop forever. | |||||
if (!EnableFiniteLoopControl || !ControllingFiniteLoop || | |||||
!isLoopInvariant(RHS, L)) | |||||
break; | |||||
RHS = getAddExpr(getOne(RHS->getType()), RHS); | |||||
mkazantsev: Can this overflow? | |||||
Not Done ReplyInline ActionsYes, it can. Although it can't overflow in loop L, it still may overflow somewhere out of the loop. See test file pr60944.ll below. StephenFan: Yes, it can. Although it can't overflow in loop `L`, it still may overflow somewhere out of the… | |||||
Not Done ReplyInline ActionsI don't quite get the logic here. Imagine that the loops has two exits, one exit is iv <= MAX_INT (so it is never taken) and another exit is guaranteed to exit in 100 iterations (so the loop is finite). Then you just turn this first exit condition into iv < MIN_INT which is trivially false and immediately exit on the 1st iteration. To me it doesn't matter if the loop is finite or not, you cannot add one here. mkazantsev: I don't quite get the logic here. Imagine that the loops has two exits, one exit is `iv <=… | |||||
ControllingFiniteLoop is ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L). This means that the lopo is finite *and* only has one exit. nikic: `ControllingFiniteLoop` is `ControlsExit && loopHasNoAbnormalExits(L) &&… | |||||
Not Done ReplyInline ActionsI don't understand. Here is what ControlsExit is from the comment of computeExitLimitFromCond: /// \p ControlsExit is true if ExitCond directly controls the exit /// branch. In this case, we can assume that the loop exits only if the /// condition is true and can infer that failing to meet the condition prior /// to integer wraparound results in undefined behavior. It doesn't mean that there is only one exit. It only means that, no matter what exit is taken, the condition is going to be true. How do you infer ability to add 1 and guarantee the new (non-equivalent) condition under the same circumstances? mkazantsev: I don't understand. Here is what `ControlsExit` is from the comment of… | |||||
nikic: Clarified in https://github.com/llvm/llvm-project/commit/6d70812789c2583333c25ff15c5e2b166d66ce… | |||||
[[fallthrough]]; | |||||
case ICmpInst::ICMP_SLT: | case ICmpInst::ICMP_SLT: | ||||
case ICmpInst::ICMP_ULT: { // while (X < Y) | case ICmpInst::ICMP_ULT: { // while (X < Y) | ||||
bool IsSigned = Pred == ICmpInst::ICMP_SLT; | bool IsSigned = ICmpInst::isSigned(Pred); | ||||
ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, | ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, | ||||
AllowPredicates); | AllowPredicates); | ||||
if (EL.hasAnyInfo()) return EL; | if (EL.hasAnyInfo()) return EL; | ||||
break; | break; | ||||
} | } | ||||
case ICmpInst::ICMP_SGE: | |||||
case ICmpInst::ICMP_UGE: | |||||
// Since the loop is finite, an invariant RHS cannot include the boundary | |||||
// value, otherwise it would loop forever. | |||||
if (!EnableFiniteLoopControl || !ControllingFiniteLoop || | |||||
!isLoopInvariant(RHS, L)) | |||||
break; | |||||
RHS = getAddExpr(getMinusOne(RHS->getType()), RHS); | |||||
[[fallthrough]]; | |||||
case ICmpInst::ICMP_SGT: | case ICmpInst::ICMP_SGT: | ||||
case ICmpInst::ICMP_UGT: { // while (X > Y) | case ICmpInst::ICMP_UGT: { // while (X > Y) | ||||
bool IsSigned = Pred == ICmpInst::ICMP_SGT; | bool IsSigned = ICmpInst::isSigned(Pred); | ||||
ExitLimit EL = | ExitLimit EL = | ||||
howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit, | howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit, | ||||
AllowPredicates); | AllowPredicates); | ||||
if (EL.hasAnyInfo()) return EL; | if (EL.hasAnyInfo()) return EL; | ||||
break; | break; | ||||
} | } | ||||
default: | default: | ||||
break; | break; | ||||
▲ Show 20 Lines • Show All 1,379 Lines • ▼ Show 20 Lines | if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B)) | ||||
return true; | return true; | ||||
// Otherwise assume they may have a different value. | // Otherwise assume they may have a different value. | ||||
return false; | return false; | ||||
} | } | ||||
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, | bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, | ||||
const SCEV *&LHS, const SCEV *&RHS, | const SCEV *&LHS, const SCEV *&RHS, | ||||
unsigned Depth, | unsigned Depth) { | ||||
bool ControllingFiniteLoop) { | |||||
bool Changed = false; | bool Changed = false; | ||||
// Simplifies ICMP to trivial true or false by turning it into '0 == 0' or | // Simplifies ICMP to trivial true or false by turning it into '0 == 0' or | ||||
// '0 != 0'. | // '0 != 0'. | ||||
auto TrivialCase = [&](bool TriviallyTrue) { | auto TrivialCase = [&](bool TriviallyTrue) { | ||||
LHS = RHS = getConstant(ConstantInt::getFalse(getContext())); | LHS = RHS = getConstant(ConstantInt::getFalse(getContext())); | ||||
Pred = TriviallyTrue ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; | Pred = TriviallyTrue ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; | ||||
return true; | return true; | ||||
}; | }; | ||||
▲ Show 20 Lines • Show All 112 Lines • ▼ Show 20 Lines | bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, | ||||
if (HasSameValue(LHS, RHS)) { | if (HasSameValue(LHS, RHS)) { | ||||
if (ICmpInst::isTrueWhenEqual(Pred)) | if (ICmpInst::isTrueWhenEqual(Pred)) | ||||
return TrivialCase(true); | return TrivialCase(true); | ||||
if (ICmpInst::isFalseWhenEqual(Pred)) | if (ICmpInst::isFalseWhenEqual(Pred)) | ||||
return TrivialCase(false); | return TrivialCase(false); | ||||
} | } | ||||
// If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by | // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by | ||||
// adding or subtracting 1 from one of the operands. This can be done for | // adding or subtracting 1 from one of the operands. | ||||
// one of two reasons: | |||||
// 1) The range of the RHS does not include the (signed/unsigned) boundaries | |||||
// 2) The loop is finite, with this comparison controlling the exit. Since the | |||||
// loop is finite, the bound cannot include the corresponding boundary | |||||
// (otherwise it would loop forever). | |||||
switch (Pred) { | switch (Pred) { | ||||
case ICmpInst::ICMP_SLE: | case ICmpInst::ICMP_SLE: | ||||
if (ControllingFiniteLoop || !getSignedRangeMax(RHS).isMaxSignedValue()) { | if (!getSignedRangeMax(RHS).isMaxSignedValue()) { | ||||
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, | RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, | ||||
SCEV::FlagNSW); | SCEV::FlagNSW); | ||||
Pred = ICmpInst::ICMP_SLT; | Pred = ICmpInst::ICMP_SLT; | ||||
Changed = true; | Changed = true; | ||||
} else if (!getSignedRangeMin(LHS).isMinSignedValue()) { | } else if (!getSignedRangeMin(LHS).isMinSignedValue()) { | ||||
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, | LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, | ||||
SCEV::FlagNSW); | SCEV::FlagNSW); | ||||
Pred = ICmpInst::ICMP_SLT; | Pred = ICmpInst::ICMP_SLT; | ||||
Changed = true; | Changed = true; | ||||
} | } | ||||
break; | break; | ||||
case ICmpInst::ICMP_SGE: | case ICmpInst::ICMP_SGE: | ||||
if (ControllingFiniteLoop || !getSignedRangeMin(RHS).isMinSignedValue()) { | if (!getSignedRangeMin(RHS).isMinSignedValue()) { | ||||
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, | RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, | ||||
SCEV::FlagNSW); | SCEV::FlagNSW); | ||||
Pred = ICmpInst::ICMP_SGT; | Pred = ICmpInst::ICMP_SGT; | ||||
Changed = true; | Changed = true; | ||||
} else if (!getSignedRangeMax(LHS).isMaxSignedValue()) { | } else if (!getSignedRangeMax(LHS).isMaxSignedValue()) { | ||||
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, | LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, | ||||
SCEV::FlagNSW); | SCEV::FlagNSW); | ||||
Pred = ICmpInst::ICMP_SGT; | Pred = ICmpInst::ICMP_SGT; | ||||
Changed = true; | Changed = true; | ||||
} | } | ||||
break; | break; | ||||
case ICmpInst::ICMP_ULE: | case ICmpInst::ICMP_ULE: | ||||
if (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) { | if (!getUnsignedRangeMax(RHS).isMaxValue()) { | ||||
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, | RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, | ||||
SCEV::FlagNUW); | SCEV::FlagNUW); | ||||
Pred = ICmpInst::ICMP_ULT; | Pred = ICmpInst::ICMP_ULT; | ||||
Changed = true; | Changed = true; | ||||
} else if (!getUnsignedRangeMin(LHS).isMinValue()) { | } else if (!getUnsignedRangeMin(LHS).isMinValue()) { | ||||
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS); | LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS); | ||||
Pred = ICmpInst::ICMP_ULT; | Pred = ICmpInst::ICMP_ULT; | ||||
Changed = true; | Changed = true; | ||||
} | } | ||||
break; | break; | ||||
case ICmpInst::ICMP_UGE: | case ICmpInst::ICMP_UGE: | ||||
if (ControllingFiniteLoop || !getUnsignedRangeMin(RHS).isMinValue()) { | if (!getUnsignedRangeMin(RHS).isMinValue()) { | ||||
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS); | RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS); | ||||
Pred = ICmpInst::ICMP_UGT; | Pred = ICmpInst::ICMP_UGT; | ||||
Changed = true; | Changed = true; | ||||
} else if (!getUnsignedRangeMax(LHS).isMaxValue()) { | } else if (!getUnsignedRangeMax(LHS).isMaxValue()) { | ||||
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, | LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, | ||||
SCEV::FlagNUW); | SCEV::FlagNUW); | ||||
Pred = ICmpInst::ICMP_UGT; | Pred = ICmpInst::ICMP_UGT; | ||||
Changed = true; | Changed = true; | ||||
} | } | ||||
break; | break; | ||||
default: | default: | ||||
break; | break; | ||||
} | } | ||||
// TODO: More simplifications are possible here. | // TODO: More simplifications are possible here. | ||||
// Recursively simplify until we either hit a recursion limit or nothing | // Recursively simplify until we either hit a recursion limit or nothing | ||||
// changes. | // changes. | ||||
if (Changed) | if (Changed) | ||||
return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1, | return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1); | ||||
ControllingFiniteLoop); | |||||
return Changed; | return Changed; | ||||
} | } | ||||
bool ScalarEvolution::isKnownNegative(const SCEV *S) { | bool ScalarEvolution::isKnownNegative(const SCEV *S) { | ||||
return getSignedRangeMax(S).isNegative(); | return getSignedRangeMax(S).isNegative(); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 4,459 Lines • Show Last 20 Lines |
Can this overflow?