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!

Answer 3

Why is gcc behaving this way?

So why? Let's have a look at the cost computation in gcc/config/avr/avr.cc:avr_rtx_costs():

    case E_HImode:
      if (AVR_HAVE_MUL)
        {
          rtx op0 = XEXP (x, 0);
          rtx op1 = XEXP (x, 1);
          ...

          if (...)
            ...
          else if (register_operand (op0, HImode)
                   && (u8_operand (op1, HImode)
                       || s8_operand (op1, HImode)))
            {
              *total = COSTS_N_INSNS (!speed ? 6 : 9);
              return true;
            }

This is the cost for multiplication of a 16-bit integral value with an 8-bit compile-time constant (signed or unsigned). The costs are:

• 9 (in unity of ticks) when compiling for speed,
• 6 (in units of words) otherwise, e.g. when compiling for size.

Such a sequence would read something like

    ldi  R_ten,     10     ; 1
    mul  R_in.lo8,  R_ten  ; 2
    movw R_OUT,     R0     ; 1
    mul  R_IN.hi8,  R_ten  ; 2
    add  R_OUT.hi8, R0     ; 1
    clr __zero_reg__       ; 1

where the output register must not overlap with any of the input registers. The actual costs are 6 words and 8 ticks, and to me it is not completely clear why avr-gcc is using 9 ticks in the cost model. Such penalty would usually account for costs that are not visible at that stage, like high register pressure or additional moves forced by early-clobber. And indeed, the real sequence has a superfluous move instruction and actually costs 9 ticks...

Where are the costs of the shift+add sequence? They are not visible here. The costs are used during instruction selection when lowering tree-SSA to RTL. The middle-end knows some algorithms to expand mul-with-const and will add costs for the required operations: (3 * shift + 1 * add) * 2 bytes = 8 ticks.

So shift+add appears cheaper than MUL. Tree-SSA → RTL lowering takes place³ in pass 234 out of 316, and costs due to register allocation (like spills, reloads or moves) are not available because reg alloc takes place later, at pass 280 / 316.

---

and how can I tell it to use hardware multiplication instructions?

There is no such option. Instruction selection follows from the device familiy, which follows from -mmcu=.... If you insist on using MUL, you'd have to use inline assembly like for example:

__attribute__((__always_inline__))
static inline uint16_t mul_u16_u8 (uint16_t a, uint8_t b)
{
#if defined __AVR_HAVE_MUL__
    uint16_t result;
    __asm ("mul  %A[in16], %[in8]"  "\n\t"
           "movw %[res], r0"        "\n\t"
           "mul  %B[in16], %[in8]"  "\n\t"
           "add  %B[res], r0"       "\n\t"
           "clr  __zero_reg__"
           : [res] "=&r" (result)
           : [in16] "r" (a), [in8] "r" (b));
    return result;
#else
    return a * b;
#endif
}

uint16_t use_mul_u16_u8 (uint16_t x)
{
    return mul_u16_u8 (x, 10);
}

The inline squence takes 7 ticks, and setting b = 10 takes one more tick. Assuming no other instructions are required², it consumes 8 ticks. The final CLR is required due to avr-gcc ABI, see this answer.

What does not work though is something like

__attribute__((__optimize__("Os"), __always_inline__))
static inline uint16_t mul_Os (uint16_t a, uint8_t b)
{
    return a * b;
}

uint16_t use_mul_Os (uint16_t x)
{
    return mul_Os (x, 10);
}

and compile with -O2. Inlining takes place prior to instructio selection, and even though GCC annotates every RTL insn whether to optimize for size or speed, it doesn't work out here (dunno if that could be considered a GCC problem).

---

Footnotes

²For the test case, the assumption does not hold because the output operand of the asm is early clobber, and both result and 1st input will occupy R25:R24, hence at least one more MOVW is needed.

³Using pass numbers from avr-gcc v8.