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

[wilco at gcc dot gnu.org]

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

--- Comment #12 from Wilco <wilco at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #11)
> (In reply to Wilco from comment #9)
> > It works for any C where (divisor*C) MOD 2^32 == 1 (or -1).
> 
> For x%3==0, i.e. z==0 for x==3*y+z with 0<=y<55555556 and 0<=z<3. 
> Indeed, x*0xaaaaaaab==y+z*0xaaaaaaab is in the right range precisely for
> z==0 and the same can be done for any odd number.

You can make it work for even numbers as well, eg. (x % 10) == 0 -> (x % 5) ==
0 && (x & 1) == 0. If you can avoid branches then it may still be faster.

> > You can support any kind of comparison, it doesn't need to be with 0 (but zero is the easiest).
> 
> Any ==cst will yield a range test. It is less obvious that inequalities are
> transformed to a contiguous range... (try x%7<3 maybe)

Indeed, expanding into x % 7 == 0 || x % 7 == 1 || x % 7 == 2 is unlikely to be
a good idea. However you can change x % 7 >= 1 into x % 7 != 0 or x % 7 < 6
into x % 7 != 6 which are single ranges.