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

[wouter.vermaelen at scarlet dot be]

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

           Summary: missed optimization: test for zero remainder after
                    division by a constant.
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassig...@gcc.gnu.org
        ReportedBy: wouter.vermae...@scarlet.be


Just like there are tricks to transform a division by a constant into a
multiplication and some shifts, there are also tricks to test if the remainder
of some division by a constant will be equal to zero.

Some examples:

bool is_mod3_zero(unsigned x)
{
    // equivalent to: return (x % 3) == 0;
    return (x * 0xaaaaaaab) <= (0xffffffff / 3);
}

bool is_mod28_zero(unsigned x)
{
    // equivalent to: return (x % 28) == 0;
    // return !(x & 3) && ((x * 0xb6db6db7) <= (0xffffffff / 7));
    return rotateRight(x * 0xb6db6db7, 2) <= (0xffffffff / 28);
}

bool is_signed_mod28_zero(int x)
{
    // equivalent to: return (x % 28) == 0;
    const unsigned c = (0x7fffffff / 7) & -(1 << 2);
    unsigned q = rotateRight((x * 0xb6db6db7) + c, 2);
    return q <= (c >> (2 - 1));
}


I found this trick in the book "Hacker's delight", chapter 10-16 "Test for Zero
Remainder after Division by a Constant". The book also explains the theory
behind this transformation.

It would be nice if gcc could automatically perform this optimization.



Bonus:

bool is_mod3_one(unsigned x)
{
    // equivalent to: return (x % 3) == 1;
    // only correct if 'x + 2' does not overflow
    //    (sometimes this can be derived from VRP)
    return ((x + (3 - 1)) * 0xaaaaaaab) <= (0xffffffff / 3);
}