1.18. REPLACING ARITHMETIC INSTRUCTIONS TO OTHER ONES
ARM64
GCC 4.9 for ARM64 is also terse, thanks to the shift modifiers:
Listing 1.197: Optimizing GCC (Linaro) 4.9 ARM64; a7
f1:
lsl x1, x0, 3
; X1=X0<<3=X08=a8
sub x0, x1, x0
; X0=X1-X0=a8-a=a*7
ret
; a28
f2:
lsl x1, x0, 5
; X1=X0<<5=a32
sub x0, x1, x0, lsl 2
; X0=X1-X0<<2=a32-a<<2=a32-a4=a28
ret
; a17
f3:
add x0, x0, x0, lsl 4
; X0=X0+X0<<4=a+a16=a*17
ret
Booth’s multiplication algorithm
There was a time when computers were big and that expensive, that some of them lacked hardware
support of multiplication operation inCPU, like Data General Nova. And when one need multiplication
operation, it can be provided at software level, for example, using Booth’s multiplication algorithm. This
is a multiplication algorithm which uses only addition operation and shifts.
What modern optimizing compilers do, isn’t the same, but the goal (multiplication) and resources (faster
operations) are the same.
1.18.2 Division.
Division using shifts
Example of division by 4:
unsigned int f(unsigned int a)
{
return a/4;
};
We get (MSVC 2010):
Listing 1.198: MSVC 2010_a$ = 8 ; size = 4
_f PROC
mov eax, DWORD PTR _a$[esp-4]
shr eax, 2
ret 0
_f ENDP
TheSHR(SHift Right) instruction in this example is shifting a number by 2 bits to the right. The two freed
bits at left (e.g., two most significant bits) are set to zero. The two least significant bits are dropped. In
fact, these two dropped bits are the division operation remainder.
TheSHRinstruction works just likeSHL, but in the other direction.