Re: Simplify X * C1 == C2 with undefined overflow

[Marc Glisse <marc.glisse@inria.fr>]

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