# Simplify X * C1 == C2 with undefined overflow

Marc Glisse marc.glisse@inria.fr
Fri Aug 7 18:21:33 GMT 2020

```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
```