# ARM multiply compiler optimization

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.

• only pattern i see is converting it to the next highest (available) even number, repeat 15 times, then switch to odd numbers, repeat 15 times, even numbers... (multiples of 15 are themselves) no clue what that is though, sorry – mumbel Aug 2 '20 at 0:31

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.