This is an archive of the discontinued LLVM Phabricator instance.

[IRCE] Fix miscompile with range checks against negative values
ClosedPublic

Authored by mkazantsev on May 14 2018, 7:25 PM.

Details

Summary

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.

Diff Detail

Event Timeline

mkazantsev created this revision.May 14 2018, 7:25 PM
mkazantsev edited the summary of this revision. (Show Details)May 14 2018, 7:29 PM
This revision is now accepted and ready to land.May 16 2018, 3:10 AM
This revision was automatically updated to reflect the committed changes.