Avr-gcc using repeated addition instead of MULU instructions

Question

I recently compiled some C++ code for the ATmega1284P in Atmel Studio and was analyzing the timings of some routines using my scope. To my surprise, a loop I thought I had optimized was taking longer than expected.

After taking a peek at the assembly code, I noticed that the compiler has compiled the following multiplication:

word *= 10;

into repeated addition:

add    r28, r28
adc    r29, r29
add    r18, r18
adc    r19, r19
add    r18, r18
adc    r19, r19
add    r18, r18
adc    r19, r19
add    r18, r28
adc    r19, r29

Now although I admire the optimizations in this repeated addition, there is no reason to do so when the chip has hardware multiplication instructions available, like mul.

Why is gcc behaving this way and how can I tell it to use hardware multiplication instructions? Note that I have set up the multiplication so overflow is not an issue. word is a uint16_t.

Answer 1

Assuming that you want to optimize for speed:

Unless you really find out how many cycles it takes if you use mul, you can't compare.

So let’s try:

• If you use the mul instruction, you need two of them (the operand is 16 bit). So that already costs 4 cycles.
• You have to load constant 10 into one register: 1 cycle.
• Then you have to add both 16 bit results. That costs another 2 cycles.
• Then you have to consider, that the results of both muls always go into register pair r1:r0, but in order to add both results you have to move one of them to some other place: that costs 2 more cycles.

So that makes it already 4 + 1 + 2 + 2 = 9 cycles, just one cycle less than what you got with repeated addition, but you've used more registers. That alone may justify repeated addition (depending on what else is done, having used one more register may cost you more than one cycle).

EDIT:
The calculation above was a back-of-the-envelope calculation; further analysis (cf. 2012rcampion's answer) shows that moving a register pair can be done in 1 cycle (there's a special instruction) and for adding the two multiplication results one add is enough (because we are not interested in a full 3 byte result but want to do a wrap-around with 16-bit width); on the other hand additional measures are required: e.g. clearing the zero register (I guess r0).
Note also that the variant with mul uses much more registers: 7 instead of only 4; a high price because it may cause several more cycles (and code size) at other places.

Answer 2

I can't tell you why GCC is doing the multiply this way, but I can tell you that it is not faster than using mul. I used the the datasheet (section 33) to count the number of cycles the following routine takes (AVR-GCC 9.2.0, compiler explorer):

#include <stdint.h>

uint16_t times_ten(uint16_t word) {
    return word * 10;
}

For -O1 through -O3 (optimize for speed):

movw r18,r24 ; 1 cycle 
lsl r18      ; 1
rol r19      ; 1
lsl r18      ; 1
rol r19      ; 1
add r24,r18  ; 1
adc r25,r19  ; 1
lsl r24      ; 1
rol r25      ; 1
             ; 9 total

Note the combination of lsl and rol to multiply a register pair by two is the same speed as adding a register pair to itself with add and adc as shown in the question (2 cycles and 2 instructions).

And for -Os (optimize for code size):

ldi r18,lo8(10)  ; 1
movw r20,r24     ; 1
mul r18,r20      ; 2
movw r24,r0      ; 1
mul r18,r21      ; 2
add r25,r0       ; 1
clr __zero_reg__ ; 1
                 ; 9 total

Interestingly, both methods take the same number of cycles, and using mul uses fewer instructions. In fact, done multiple times as part of a larger function where 10 can be saved in a register and zeroing r1 can be deferred until the end, using mul would be two cycles faster!