[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 #21 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Probably should punt early if integer_onep (treeop1), that case should have
been optimized earlier, but if it isn't, we shouldn't miscompile.

Another thing is if *arg1 is < 0 or >= treeop1, again, I'd hope we have
optimized that already to false (or true for NE_EXPR), but if not, we shouldn't
miscompile.

Another thing is that C4 needs to be adjusted, if *arg1 is bigger than
all_ones%treeop1, then we need to subtract 1 from C4 - e.g. for x % 3 == 0
we want to expand it as x * 0xaaaaaaab <= 0x55555555, while for x % 3 == 1
we should expand as x * 0xaaaaaaab - 1 * 0xaaaaaaab <= 0x55555555 - 1, because
0xffffffff % 3 == 0 and thus there is one more case where x % 3 == 0 compared
to x % 3 == 1 and x % 3 == 2 cases.

Hacker's Delight 10-17 mentions <= (2^prec - 1) / c1 rather than <= (2^prec) /
c1, probably should do that too.