ARM multiply compiler optimization

Question

I need help interpreting this compiler optimization:

   ;R12 = 0x88888889;
    UMULL           LR, R2, R12, R3 ; R3 * 0x88888889;
    MOV             R2, R2,LSR#3 ; ((R3 * 0x88888889 << 32) >> 3)
    RSB             R2, R2, R2,LSL#4 ; (R3 * 0x88888889 >> 32 >> 3) << 16
    RSB             R2, R2, R3,LSL#1 ; (R3 << 1) - ((R3 * 0x88888889 >> 32 >> 3) << 16);

currently i interpreted this like so (not sure it is correct):

(R3 * 2) - ((R3 * 0x88888889 * 120) / 0xFFFFFFFF);

I found that it maybe integer division, I hope someone can help me understand this optimization better

Thanks.

Answer 1

You are on the right lines with integer division.

The first 3 instructions are reasonably clear -

• R2 after UMULL is the result of an integer division by 1.875 (= 0x100000000 / 0x88888889)
• the following MOV is then a further integer divide by 8 resulting in R2 now containing the original R3 divided by 15 (= 1.875 * 8)
• the first RSB is then a multiplication by 15 (= R2 * 16 - R2 )

At this point R2 = 15 * int( R3 / 15 ).

The last RSB then gives the final result R2 = R3 * 2 - 15 * int( R3 / 15 ).

Edit: in fact, this can be simplified to R2 = R3 + (R3 % 15) (where % is the modulo operator.)

You can see example compilations of both of these formulae here.