[IRCE] Fix miscompile with range checks against negative values
In the patch rL329547, we have lifted the over-restrictive limitation on collected range
checks, allowing to work with range checks with the end of their range not being
provably non-negative. However it appeared that the non-negativity of this value was
assumed in the utility function `ClampedSubtract`. In particular, its reasoning is based
on the fact that `0 <= SINT_MAX - X`, which is not true if `X` is negative.
The function `ClampedSubtract` is only called twice, once with `X = 0` (which is OK)
and the second time with `X = IRC.getEnd()`, where we may now see the problem if
the end is actually a negative value. In this case, we may sometimes miscompile.
This patch is the conservative fix of the miscompile problem. Rather than rejecting
non-provably non-negative `getEnd()` values, we will check it for non-negativity in
runtime. For this, we use function `smax(smin(X, 0), -1) + 1` that is equal to `1` if `X`
is non-negative and is equal to 0 if `X` is negative. If we multiply `Begin, End` of safe
iteration space by this function calculated for `X = IRC.getEnd()`, we will get the original
`[Begin, End)` if `IRC.getEnd()` was non-negative (and, thus, `ClampedSubtract` worked
correctly) and the empty range `[0, 0)` in case if ` IRC.getEnd()` was negative.
So we in fact prohibit execution of the main loop if at least one of range checks was
made against a negative value (and we figured it out in runtime). It is still better than
what we have before (non-negativity had to be proved in compile time) and prevents
us from miscompile, however it is sometiles too restrictive for unsigned range checks
against a negative value (which in fact can be eliminated).
Once we re-implement `ClampedSubtract` in a way that it handles negative `X` correctly,
this limitation can be lifted, too.
Differential Revision: https://reviews.llvm.org/D46860
Reviewed By: samparker
llvm-svn: 332809
diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index aa7c2b3..e2f2970 100644
--- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -813,6 +813,13 @@
SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, Zero);
}
+static bool isKnownNegativeInLoop(const SCEV *BoundSCEV, const Loop *L,
+ ScalarEvolution &SE) {
+ const SCEV *Zero = SE.getZero(BoundSCEV->getType());
+ return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
+ SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, BoundSCEV, Zero);
+}
+
Optional<LoopStructure>
LoopStructure::parseLoopStructure(ScalarEvolution &SE,
BranchProbabilityInfo *BPI, Loop &L,
@@ -1700,6 +1707,10 @@
// values, depending on type of latch condition that defines IV iteration
// space.
auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
+ // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
+ // This is required to ensure that SINT_MAX - X does not overflow signed and
+ // that X - Y does not overflow unsigned if Y is negative. Can we lift this
+ // restriction and make it work for negative X either?
if (IsLatchSigned) {
// X is a number from signed range, Y is interpreted as signed.
// Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
@@ -1729,8 +1740,34 @@
};
const SCEV *M = SE.getMinusSCEV(C, A);
const SCEV *Zero = SE.getZero(M->getType());
- const SCEV *Begin = ClampedSubtract(Zero, M);
- const SCEV *End = ClampedSubtract(getEnd(), M);
+
+ // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
+ auto SCEVCheckNonNegative = [&](const SCEV *X) {
+ const Loop *L = IndVar->getLoop();
+ const SCEV *One = SE.getOne(X->getType());
+ // Can we trivially prove that X is a non-negative or negative value?
+ if (isKnownNonNegativeInLoop(X, L, SE))
+ return One;
+ else if (isKnownNegativeInLoop(X, L, SE))
+ return Zero;
+ // If not, we will have to figure it out during the execution.
+ // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
+ const SCEV *NegOne = SE.getNegativeSCEV(One);
+ return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
+ };
+ // FIXME: Current implementation of ClampedSubtract implicitly assumes that
+ // X is non-negative (in sense of a signed value). We need to re-implement
+ // this function in a way that it will correctly handle negative X as well.
+ // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
+ // end up with a negative X and produce wrong results. So currently we ensure
+ // that if getEnd() is negative then both ends of the safe range are zero.
+ // Note that this may pessimize elimination of unsigned range checks against
+ // negative values.
+ const SCEV *REnd = getEnd();
+ const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
+
+ const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
+ const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
return InductiveRangeCheck::Range(Begin, End);
}