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

["wilco at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

Wilco <wilco at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |wilco at gcc dot gnu.org

--- Comment #9 from Wilco <wilco at gcc dot gnu.org> ---
(In reply to Andi Kleen from comment #8)
> I'm not sure if it works with other numbers too.
> 
> (need to dig through Hacker's delight & Matters Computational to see if they
> have anything on it)
> 
> But it could be extended for other word lengths at least
> 
> BTW there are some other cases, will file a bug shortly on those too.

It works for any C where (divisor*C) MOD 2^32 == 1 (or -1). You can support any
kind of comparison, it doesn't need to be with 0 (but zero is the easiest). I
forgot whether I made it work for signed too, but it's certainly possible to
skip the sign handling in x % 4 == 0 even if x is signed.

While this is faster in general than computing the full modulo result, it
wouldn't be if you need the division result as well. So this works best on
single-use modulos used in comparisons, at the same time as general divisions
are expanded.