Division by small constants

[tkoenig1]

... by multiplication with the inverse, as described in Hacker's Delight and other sources.

unsigned long d13(unsigned long a)
{
    return a / 13;
}

gives a straightforward, but slow

        div     r1,r1,#13
        ret

compared to (same compiler, x86)

        movq    %rdi, %rax
        movabsq $5675921253449092805, %rcx      # imm = 0x4EC4EC4EC4EC4EC5
        mulq    %rcx
        movq    %rdx, %rax
        shrq    $2, %rax
        retq

which is likely to be much faster.

[tkoenig1]

This transformation is only useful when optimizing, but not when optimizing for size (via -Os).

[bagel99]

Whenever there is hardware, based on timing this can be considered.

[bagel99]

Try again with commit af7ee91ac91db0ac489c686eb35daf15ceb1f32f. Transformation not done when compiling for size.

[tkoenig1]

Code is now

        carry   r2,{O}
        mul     r1,r1,#5675921253449092805
        srl     r1,r2,<0:2>
        ret

so this is now implemented. Thanks!

[bagel99]

This optimization generates larger code and often uses an extra register. As far as it being faster, until we have hardware its not clear.

[bagel99]

This optimization has been removed.