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;


add    r28, r28


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.

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.

• Ahah! The fact that the value is stored in a r1:r0 escaped me. That makes sense for a multiply-by 10 being optimized down to additions. I tried multiplying by 100 and it used mul's like I expected. Marked as accepted. Apr 28, 2021 at 8:21
• Ten additions still seems less than optimal, wouldn't 5 additions followed by an ROR be better? Apr 28, 2021 at 15:53
• Glen Yates: Perhaps because the registers are 8-bit registers? (Not a rhetorical question) Apr 28, 2021 at 16:08
• @PeterMortensen: Yep, it looks like each add+adc pair is a single 16 bit addition. So what the assembly code quoted by the OP seems to be doing is calculating 2 * word (one doubling) and 8 * word (three doublings) and then adding them together. Five 16 bit additions all together. (It also seems to assume that the original value of word is found both in r18/r19 and in r28/ r29. Presumably that's ensured by something before the quoted code that the OP left out.) Apr 28, 2021 at 16:26
• @PeterMortensen Thanks, my assembly experience is from a different platform and of course I meant LSL and ROL instead of right shifts and rolls. Apr 28, 2021 at 16:37

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
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
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!

• Interesting... I have considered moving to Atmelcrochip's new IDE, which has an improved compiler and the extra option to pay some enormous fee for 'revolutionary optimizations.' Perhaps being a little more intelligent with multiplication is one of those perks, but I think I'll stick with my additions for now... Apr 29, 2021 at 0:24
• Note that the variant without mul uses only 4 registers (r18, r19, r24, r25) while the variant with mul uses 7 registers (r0, r1, r18, r20, r21, r24, r25); a big disadvantage of the latter.
– Curd
Apr 30, 2021 at 12:20
• @Hackstaar: The revolutionary optimizations from Microchip are: They are disabling optimizations avr-gcc would perform, and make you pay for the version that has them enabled. Better stick with a complier not "improved" by Microchip. For the optimization in question though, it's what avr-gcc does per default, and it matches its cost computation: It doesn't see the movw in the -O3 version because that it introduced by the register allocator, which runs much later than instruction selection. Nov 29 at 20:08

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
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 place3 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"
"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 required2, 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

2For 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.

3Using pass numbers from avr-gcc v8.

New contributor
emacs drives me nuts is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.