第16章 数学计算指令的替换

出于性能优化的考虑,编译器可能会将1条数学运算指令替换为其他的1条、甚至是一组等效指令。

例如LEA指令通常替代其他的简单计算指令:请参见附录A.6.2节。

ADD和SUB指令同样可以相互替换。例如,指令清单52.1的第18行就是如此。

16.1 乘法

16.1.1 替换为加法运算

我们通过下述程序进行演示。

指令清单16.1 Optimizing MSVC 2010

unsigned int f(unsigned int a)
{
         return a*8;
};

如果使用MSVC 2010(启用/Ox)进行编译,编译器会把“乘以8”的运算指令拆解为3条加法指令。很明显MSVC认为替换后的程序性能更高。

_TEXT   SEGMENT
_a$ = 8                         ; size = 4
_f      PROC
; File c:\polygon\c\2.c
        mov     eax, DWORD PTR _a$[esp-4]
        add     eax, eax
        add     eax, eax
        add     eax, eax
        ret     0 
_f      ENDP
_TEXT   ENDS
END
16.1.2 替换为位移运算

编译器通常会把“乘以2”“除以2”的运算指令处理为位移运算指令:

unsigned int f(unsigned int a)
{
        return a*4;
};

指令清单16.2 Non-optimizing MSVC 2010

_a$ = 8          ; size = 4
_f       PROC
         push    ebp
         mov     ebp, esp
         mov     eax, DWORD PTR _a$[ebp]
         shl     eax, 2
         pop     ebp
         ret     0
_f       ENDP

“乘以4”的运算就是把被乘数左移2位、再把位移产生的空缺位添上0的运算。就好比在心算计算3×100的时候,我们就是在3后面的空缺位添加两个零。

位移指令的示意图如下所示。

..\TU\p1601.tif

右侧产生的空缺位都由零填充。

乘以4的ARM指令如下所示。

指令清单16.3 Non-optimizing Keil 6/2013 (ARM mode)

f  PROC
        LSL     r0,r0,#2
        BX      lr
        ENDP

对应的MIPS指令如下所示。

指令清单16.4 Optimizing GCC 4.4.5 (IDA)

                jr      $ra
                sll     $v0, $a0, 2 ; branch delay slot

其中,SLL是逻辑左移“Shift Left Logical”的缩写。

16.1.3 替换为位移、加减法的混合运算

即使乘数是7或17,乘法运算仍然可以用非乘法运算指令配合位移指令实现。其算术原理也不难推测。

32位

#include <stdint.h>

int f1(int a)
{
         return a*7;
};

int f2(int a)
{
         return a*28;
};

int f3(int a)
{
         return a*17;
};

x86

指令清单16.5 Optimizing MSVC 2012

; a*7
_a$ = 8
_f1      PROC
         mov     ecx, DWORD PTR _a$[esp-4]
; ECX=a
         lea     eax, DWORD PTR [ecx*8]
; EAX=ECX*8
         sub     eax, ecx
; EAX=EAX-ECX=ECX*8-ECX=ECX*7=a*7
         ret     0 
_f1     ENDP

; a*28
_a$ = 8
_f2     PROC
         mov     ecx, DWORD PTR _a$[esp-4]
; ECX=a
         lea     eax, DWORD PTR [ecx*8]
; EAX=ECX*8
         sub     eax, ecx
; EAX=EAX-ECX=ECX*8-ECX=ECX*7=a*7
         shl     eax, 2
; EAX=EAX<<2=(a*7)*4=a*28
         ret     0 
_f2     ENDP

; a*17
_a$ = 8
_f3     PROC
         mov     eax, DWORD PTR _a$[esp-4]
; EAX=a
         shl     eax, 4
; EAX=EAX<<4=EAX*16=a*16
         add     eax, DWORD PTR _a$[esp-4]
; EAX=EAX+a=a*16+a=a*17
         ret     0
_f3     ENDP

ARM

ARM指令集的位移运算指令有3个操作符,可在位移运算符后再进行一次加法运算。故而Keil生成的代码更为短小。

指令清单16.6 Optimizing Keil 6/2013 (ARM mode)

; a*7
||f1|| PROC
         RSB       r0,r0,r0,LSL #3
; R0=R0<<3-R0=R0*8-R0=a*8-a=a*7
         BX        lr 
         ENDP

; a*28
||f2|| PROC
         RSB      r0,r0,r0,LSL #3
; R0=R0<<3-R0=R0*8-R0=a*8-a=a*7
         LSL      r0,r0,#2
; R0=R0<<2=R0*4=a*7*4=a*28
         BX       lr
         ENDP

; a*17
||f3|| PROC
         ADD      r0,r0,r0,LSL #4
; R0=R0+R0<<4=R0+R0*16=R0*17=a*17
         BX       lr
         ENDP

然而Thumb模式的位移指令不支持这种运算。编译器无法优化f2()。

指令清单16.7 Optimizing Keil 6/2013 (Thumb mode)

; a*7
||f1||  PROC
          LSLS      r1,r0,#3
; R1=R0<<3=a<<3=a*8
          SUBS      r0,r1,r0
; R0=R1-R0=a*8-a=a*7
          BX        lr
          ENDP

; a*28
||f2|| PROC
          MOVS      r1,#0x1c ; 28
; R1=28
          MULS      r0,r1,r0
; R0=R1*R0=28*a
          BX        lr
          ENDP

; a*17
||f3|| PROC
          LSLS      r1,r0,#4
; R1=R0<<4=R0*16=a*16
          ADDS      r0,r0,r1
; R0=R0+R1=a+a*16=a*17
          BX        lr
          ENDP

MIPS

指令清单16.8 Optimizing GCC 4.4.5 (IDA)

_f1:
                  sll      $v0, $a0, 3
; $v0 = $a0<<3 = $a0*8
                  jr       $ra
                  subu     $v0, $a0 ; branch delay slot
; $v0 = $v0-$a0 = $a0*8-$a0 = $a0*7

_f2:
                  sll      $v0, $a0, 5
; $v0 = $a0<<5 = $a0*32
                  sll      $a0, 2
; $a0 = $a0<<2 = $a0*4
                  jr       $ra
                  subu     $v0, $a0 ; branch delay slot
; $v0 = $a0*32-$a0*4 = $a0*28

_f3:
                  sll      $v0, $a0, 4
; $v0 = $a0<<4 = $a0*16
                  jr       $ra
                  addu     $v0, $a0 ; branch delay slot
; $v0 = $a0*16+$a0 = $a0*17

64位

#include <stdint.h>

int64_t f1(int64_t a)
{
        return a*7;
};
int64_t f2(int64_t a)
{
        return a*28;
};

int64_t f3(int64_t a)
{
        return a*17;
};

x64

指令清单16.9 Optimizing MSVC 2012

; a*7 
f1:
        lea     rax, [0+rdi*8]
; RAX=RDI*8=a*8
        sub     rax, rdi
; RAX=RAX-RDI=a*8-a=a*7
        ret

; a*28 
f2:
        lea     rax, [0+rdi*4]
; RAX=RDI*4=a*4
        sal     rdi, 5
; RDI=RDI<<5=RDI*32=a*32
        sub     rdi, rax
; RDI=RDI-RAX=a*32-a*4=a*28
        mov     rax, rdi
        ret

; a*17 
f3:
        mov     rax, rdi
        sal     rax, 4
; RAX=RAX<<4=a*16
        add     rax, rdi
; RAX=a*16+a=a*17
        ret

ARM64

由于ARM64模式的位移指令同样可进行加法运算,所以这种程序要短一些。

指令清单16.10 Optimizing GCC (Linaro) 4.9 ARM64

; a*7
f1:
        lsl     x1, x0, 3
; X1=X0<<3=X0*8=a*8
        sub     x0, x1, x0
; X0=X1-X0=a*8-a=a*7
        ret

; a*28
f2:
        lsl     x1, x0, 5
; X1=X0<<5=a*32
        sub     x0, x1, x0, lsl 2
; X0=X1-X0<<2=a*32-a<<2=a*32-a*4=a*28
        ret

; a*17
f3:
        add     x0, x0, x0, lsl 4
; X0=X0+X0<<4=a+a*16=a*17
        ret

16.2 除法运算

16.2.1 替换为位移运算

本节围绕下述源程序进行演示:

unsigned int f(unsigned int a)
{
       return a/4;
};

使用MSVC 2010编译上述程序,可得到如下所示的指令。

指令清单16.11 MSVC 2010

_a$ = 8                                         ; size = 4
_f      PROC
        mov     eax, DWORD PTR _a$[esp-4]
        shr     eax, 2
        ret     0
_f      ENDP

上述代码中的SHR(SHift Right)指令将EAX寄存器中的数值右移2位,使用零填充位移产生的空缺位,并且舍弃那些被右移指令移动出存储空间的比特位。实际上,那些被舍弃的比特位正是除法运算的余数。

SHR指令和SHL指令的运算模式相同,只是位移方向不同。

..\TU\p1602.tif

右移与余数的关系与十进制运算的移动小数点运算相似:当被除数为23、除数为10时,我们将23的小数点左移一位,2为商、3为余数。

毕竟本例是整数运算,商也应当是整数(不会是浮点数),所以我们舍弃余数完全没有问题。

“除以4”运算的ARM程序如下所示。

指令清单16.12 Non-optimizing Keil 6/2013 (ARM mode)

f  PROC
        LSR     r0,r0,#2
        BX      lr
        ENDP

“除以4”运算的MIPS程序如下所示。

指令清单16.13 Optimizing GCC 4.4.5 (IDA)

                jr       $ra
                srl      $v0, $a0, 2 ; branch delay slot

上述程序中的SRL指令是“逻辑右移指令/Shift-Right Logical”。

16.3 练习题

16.3.1 题目1

请分析下列程序的功能。

指令清单16.14 Optimizing MSVC 2010

_a$ = 8
_f      PROC
        mov     ecx, DWORD PTR _a$[esp-4]
        lea     eax, DWORD PTR [ecx*8]
        sub     eax, ecx
        ret     0
_f      ENDP

指令清单16.15 Non-optimizing Keil 6/2013 (ARM mode)

f PROC
        RSB     r0,r0,r0,LSL #3
        BX      lr
        ENDP

指令清单16.16 Non-optimizing Keil 6/2013 (Thumb mode)

f PROC
        LSLS    r1,r0,#3
        SUBS    r0,r1,r0
        BX      lr
        ENDP

指令清单16.17 Optimizing GCC 4.9 (ARM64)

f:
        lsl     w1, w0, 3
        sub     w0, w1, w0
        ret

指令清单16.18 Optimizing GCC 4.4.5 (MIPS) (IDA)

f:
                sll      $v0, $a0, 3
                jr       $ra
                subu     $v0, $a0