[Bug tree-optimization/49552] missed optimization: test for zero remainder after division by a constant.

["wouter.vermaelen at scarlet dot be" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49552

--- Comment #2 from Wouter Vermaelen <wouter.vermaelen at scarlet dot be> 2011-06-28 12:22:11 UTC ---
> Confirmed.  Is this possible for all constant moduli?

It is. I recommend you get a copy of the book I mentioned before. The theory
behind the transformation is much better explained there than I could ever do
here. But I'll try to give a recipe to construct the routine for a specific
constant:
(all examples are for 32-bit, but it should be easy enough to generalize)

There are 3 different cases:

    (x % C) == 0

* 'x' is unsigned, 'C' is odd:

    return (x * Cinv) <= (0xffffffff / C);

Where Cinv is the multiplicative inverse of C  (C * Cinv = 1 (modulo pow(2,
32))). Cinv is the same 'magic number' as is used to optimize exact-division
(division where it's known that the remainder will be zero).



* 'x' is unsigned, 'C' is even:

Split 'C' in an odd factor and a power of two.

    C = Codd * Ceven
    where Ceven = pow(2, k)

Now we test that 'x' is both divisible by 'Codd' and 'Ceven'.

    return !(x & (Ceven - 1)) && ((x * Codd_inv) <= (0xffffffff / Codd))

When a rotate-right instruction is available, the expression above can be
rewritten so that it only requires one test:

    return rotateRight(x * Codd_inv, k) <= (0xffffffff / C); // unsigned
comparison



* 'x' is signed, (C can be odd or even)

(I admit, I don't fully understand the theory behind this transformation, so
I'll only give the final result).

    constexpr unsigned A = (0x7fffffff / Codd) & -(1 << k);
    constexpr unsigned B = k ? (A >> (k - 1)) : (A << 1);
    return rotateRight((x * Codd_inv) + A, k) <= B;   // unsigned comparison