[Bug middle-end/82853] Optimize x % 3 == 0 without modulo

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853

--- Comment #24 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Wilco from comment #23)
> (In reply to Jakub Jelinek from comment #22)
> > So, while it isn't correct to replace x % 3U == 1 by (x - 1) % 3U == 0,
> > because
> > for x == 0 the test will yield a different value, as 0xffffffffU % 3U is 0
> > and
> > 0 % 3U is also 0, x % 3U == 1 is equivalent to (x - 1) * 0xaaaaaaabU <=
> > 0x55555554U, but x % 3U == 0 is equivalent to x * 0xaaaaaaabU <= 0x55555555U.
> > Now to see if something useful can be used also for the even divisors.
> 
> Yes for this case it is safe to do (x - 1) * 0xaaaaaaab < 0x55555555, but
> you can also do x * 0xaaaaaaab >= 0xaaaaaaab which is even simpler.

Yeah, a special case, todo++.

> Basically (x % C) == N is simpler for 2 values of N.

I meant that for C odd it works for any value, x % C == D for C odd and D <= -1
% C then (x - D) * mod_inv (C) <= -1 / C, otherwise if C is odd and D > -1 % C
then
(x - D) * mod_inv (C) < -1 / C.
Just if C is even it is more complicated.  
For C positive odd and signed modulo with D == 0 it can be done easily too
(will implement tomorrow).