[llvm-bugs] [Bug 28672] New: Integer divide by constant close to UINT*_MAX can be compare rather than divide

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=28672

            Bug ID: 28672
           Summary: Integer divide by constant close to UINT*_MAX can be
                    compare rather than divide
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: simon.hosie at arm.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

When doing unsigned division by an integer which is greater than `UINT_MAX / 2`
(or another range limit in place of UINT_MAX, as appropriate), the result can
be only 0 or 1, and this can be evaluated with a compare rather than a
reciprocal-multiply (or divide).

For example:

    uint32_t f(uint32_t x) { return (x + 1) % 4000569407; }

is equivalent to:

    uint32_t f(uint32_t x) { x++; return x < 4000569407 ? x : x - 4000569407; }

Clang gives me:

        clang --target=arm-linux-gnueabihf -O3 -S -o- p1modk.c

        ldr     r1, .LCPI0_0        // 316062335
        add     r0, r0, #1
        umull   r1, r2, r0, r1
        sub     r1, r0, r2
        add     r1, r2, r1, lsr #1
        ldr     r2, .LCPI0_1        // 4000569407
        lsr     r1, r1, #31
        mul     r1, r1, r2
        sub     r0, r0, r1

I expect something more like:

        ldr     r1, =4000569407
        add     r0, r0, #1
        cmp     r0, r1
        subhs   r0, r0, r1


Note that this applicable in loops containing the `x = (x + 1) % k;` idiom if x
can be shown to be never greater than k (even if k is variable, I think).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20160722/1aa08d81/attachment.html>