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.
