On Fri, 7 Aug 2020, Joern Wolfgang Rennecke wrote:
this transformation is quite straightforward, without overflow, 3*X==15 is
the same as X==5 and 3*X==5 cannot happen.
Actually, with binary and decimal computers, this transformation (with
these specific numbers) is also valid for wrapping overflow. More
generally, it is valid for wrapping overflow if the right hand side of
the comparison is divisible without rest by the constant factor, and the
constant factor has no sub-factor that is a zero divisor for the ring
defined by the wrapping operation. For binary computers, the latter
condition can be more simply be restated as: The constant factor has to
be odd. (For decimal computers, it's: must not be divisible by two
and/or five.)
If we are going to handle the wrapping case, we shouldn't limit to the
non-wrapping meaning of multiplicity. 3*X==5 should become X==1431655767
(for a 32 bit type), etc.
Do we have an extended gcd somewhere in gcc, to help compute 1431655767?
(Even if the variable factor is wider than equality comparison, that is
not a problem as long as the comparison is not widened by the
transformation.)
On the other hand, the following generalizations would work only without
overflow:
- handling of inequality-comparisons - merely have to account for the sign of
the factor reversing the sense of
the inequality, e.g. -3*X >= 15 ---> X <= 5
And again for this one, we have to be careful how we round the division,
but we don't have to limit to the case where 15 is a multiple of 3. 3*X>7
can be replaced with X>2.
Those are two nice suggestions. Do you intend to write a patch? Otherwise
I'll try to do it eventually (no promise).
--
Marc Glisse
