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

[Joern Wolfgang Rennecke <gnu@amylaar.uk>]

On 07/08/20 19:21, Marc Glisse wrote:
>
> 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?
I don't quite see yet how this relates to gcd, but how how about this:

First, we divide the right hand side of the comparison by the constant 
factor.  5 divided by 3
is one, with rest 2.  Now we want to express this rest two by wrapping 
overflow.
0x100000000 divided by 3 is 0x55555555 rest 1.  When we multiply 
0x55555555 again by three,
the rest is missing, so we get -1 in 32 bit.  So we try to express 2 as 
a multiple of -1:
2/-1 = -2

Thus, the quotient is 1 + 0x55555555 * -2 , which, using 32 bit wrapping 
arithmetic,
is 0x55555557, i.e. 1431655767 .
Again, because the constant factor (3) is odd, there can be no other 
solution.

However, there are cases were the second division will not be possible 
without rest.
Consider : 7*X == 3
3/7 is 0 rest 3.
0x100000000 / 7 is 0x24924924 rest 4
Since 3 cannot be represented as an integer multiple of -4, we can 
conclude that the predicate
is always false.

Also: 14*X == 28
has a non-zero power of two in the constant factor, so we have to factor 
out the power of two
(if the right hand side has a lower power of two, the predicate is 
always false) and consider
in modulo arithmetic with a number of bits less by the factored out 
power of two, i.e. 31 bit here:
7*X == 14
which is solved as above - but in 32 bit arithmetic - to
X == 2
and to convert back to 32 bit arithmetic, we get:
X & 0x7fffffff == 2
or
2*x == 4


Likewise, 14*X == 30 would be reduced to 7*X == 15 in 31 bit arithmetic, 
then we find that
we can't express the rest of 1 as an integer multiple of -2, so the 
predicate is always false.
  .
>
>> (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?
No, I just couldn't resist applying a smidge of number theory to a 
compiler problem.
I still have to herd other patches.
> Otherwise I'll try to do it eventually (no promise).
Would be nice.