第39章 循环:几个迭代

多数循环语句只有一个迭代器。但是在汇编层面,一个迭代器也可能对应多个数据实体。

下面所示的是一个简单的例子。

#include <stdio.h>

void f(int *a1, int *a2, size_t cnt)
{
       size_t i;

       // copy from one array to another in some weird scheme
       for (i=0; i<cnt; i++)
              a1[i*3]=a2[i*7];
};

我们可以看到,每次迭代都有两次乘法运算,这是很耗费时间的操作。能不能优化一下呢?答案是肯定的。如果仔细看看程序代码,就会发现这个程序中的矩阵的参数是跳跃的,我们能比较容易地不用乘法就将它计算出来。

39.1 三个迭代器

指令清单39.1 采用MSVC 2013 x64优化的代码

f        PROC
; RDX=a1
; RCX=a2
; R8=cnt
         test      r8, r8         ; cnt==0? exit then
         je        SHORT $LN1@f
         npad      11
$LL3@f:
         mov       eax, DWORD PTR [rdx]
         lea       rcx, QWORD PTR [rcx+12]
         lea       rdx, QWORD PTR [rdx+28]
         mov       DWORD PTR [rcx-12], eax
         dec       r8
         jne       SHORT $LL3@f
$LN1@f:
         ret       0
f        ENDP

这里有三个迭代变量,它们是cnt变量以及2个数列参数(索引游标)。数列参数每次迭代都增加12或者28(其实这就是采用加法代替了源程序中的乘法)。因此我们可以采用C/C++语言重写代码如下。

#include <stdio.h>

void f(int *a1, int *a2, size_t cnt)
{
        size_t i;
        size_t idx1=0; idx2=0;

        // copy from one array to another in some weird scheme
        for (i=0; i<cnt; i++)
        {
               a1[idx1]=a2[idx2];
               idx1+=3;
               idx2+=7;
        };
};

这个程序可在每次迭代更新3个迭代参数,而不是1个。另外,编译器变相实现了两个乘法操作。

39.2 两个迭代器

GCC 4.9可以做得更好,只有两个迭代。

指令清单39.2 采用GCC 4.9 x64优化

; RDI=a1
; RSI=a2
; RDX=cnt
f:
        test     rdx, rdx ; cnt==0? exit then
        je       .L1
; calculate last element address in "a2" and leave it in RDX
        lea      rax, [0+rdx*4]
; RAX=RDX*4=cnt*4
        sal      rdx, 5
; RDX=RDX<<5=cnt*32
        sub      rdx, rax
; RDX=RDX-RAX=cnt*32-cnt*4=cnt*28
        add      rdx, rsi
; RDX=RDX+RSI=a2+cnt*28
.L3:
        mov      eax, DWORD PTR [rsi]
        add      rsi, 28
        add      rdi, 12
        mov      DWORD PTR [rdi-12], eax
        cmp      rsi, rdx
        jne      .L3
.L1:
        rep ret

这里没有计数器变量counter了,这是因为GCC编译器认为它没有必要。数组a2的最后一个参数在循环开始前就已经计算好了(很容易,其实就是cnt乘以7)。而且循环的结束条件也不复杂:第二个索引号指数达到那个可预先计算出来的临界值时,循环语句随即终止迭代。

其中涉及一些采用加/减/位移等办法来替代乘法运算的知识,有兴趣的读者请参阅本书16.1.3节。

上述汇编代码与下述C/C++程序相对应:

#include <stdio.h>

void f(int *a1, int *a2, size_t cnt)
{
        size_t i;
        size_t idx1=0; idx2=0;
        size_t last_idx2=cnt*7;

        // copy from one array to another in some weird scheme
        for (;;)
        {
                a1[idx1]=a2[idx2];
                idx1+=3;
                idx2+=7;
                if (idx2==last_idx2)
                        break;
        };
};

ARM64下的GCC(Linaro) 4.9采用了同种类型的编译方法。但是它计算的是数组a1的最后一个索引值,而不是像上面的程序那样以数组a2为边界条件。当然,程序的功能最终还是一样的。

指令清单39.3 ARM64下的GCC(Linaro) 4.9优化

; X0=a1
; X1=a2
; X2=cnt
f:
        cbz     x2, .L1             ; cnt==0? exit then
; calculate last element of "a1" array
        add     x2, x2, x2, lsl 1
; X2=X2+X2<<1=X2+X2*2=X2*3
        mov     x3, 0
        lsl     x2, x2, 2
; X2=X2<<2=X2*4=X2*3*4=X2*12
.L3:
        ldr     w4, [x1],28         ; load at X1, add 28 to X1 (post-increment)
        str     w4, [x0,x3]         ; store at X0+X3=a1+X3
        add     x3, x3, 12          ; shift X3
        cmp     x3, x2              ; end?
        bne     .L3
.L1:
        ret

MIPS下的GCC 4.4.5也差不多如此。

指令清单39.4 MIPS(IDA)下的GCC 4.4.5优化

; $a0=a1
; $a1=a2
; $a2=cnt
f:
; jump to loop check code:
               beqz     $a2, locret_24
; initialize counter (i) at 0:
               move     $v0, $zero ; branch delay slot, NOP
loc_8:
; load 32-bit word at $a1
               lw       $a3, 0($a1)
; increment counter (i):
               addiu    $v0, 1
; check for finish (compare "i" in $v0 and "cnt" in $a2):
               sltu     $v1, $v0, $a2
; store 32-bit word at $a0:
               sw        $a3, 0($a0)
; add 0x1C (28) to \$a1 at each iteration:
               addiu    $a1, 0x1C
; jump to loop body if i<cnt:
               bnez     $v1, loc_8
; add 0xC (12) to \$a0 at each iteration:
               addiu    $a0, 0xC ; branch delay slot
locret_24:
               jr       $ra
               or       $at, $zero ; branch delay slot, NOP

39.3 Intel C++ 2011实例

编译器的优化操作有时候会非常奇怪。但是无论它们采用了何种优化方式,程序的功能肯定忠于源程序。这里列出的是Intel C++ 2011编译器如何操作的例子。

指令清单39.5 Intel C++ 2011 (x64)优化

f        PROC
; parameter 1: rcx = a1
; parameter 2: rdx = a2
; parameter 3: r8 = cnt
.B1.1::                               ; Preds .B1.0
         test        r8, r8                                       ;8.14
         jbe         exit             ; Prob 50%                  ;8.14
                                      ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.2::                               ; Preds .B1.1
         cmp         r8, 6                                        ;8.2
         jbe         just_copy        ; Prob 50%                  ;8.2
                                      ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.3::                              ; Preds .B1.2
         cmp         rcx, rdx                                     ;9.11
         jbe         .B1.5          ; Prob 50%                   ;9.11
                                     ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.4::                              ; Preds .B1.3
         mov         r10, r8                                      ;9.11
         mov         r9, rcx                                      ;9.11
         shl         r10, 5                                       ;9.11
         lea         rax, QWORD PTR [r8*4]                        ;9.11
         sub         r9, rdx                                      ;9.11
         sub         r10, rax                                     ;9.11
         cmp         r9, r10                                      ;9.11
         jge         just_copy2      ; Prob 50%                   ;9.11
                                     ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.5::                              ; Preds .B1.3 .B1.4
         cmp         rdx, rcx                                     ;9.11
         jbe         just_copy       ; Prob 50%                   ;9.11
                                     ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.6::                              ; Preds .B1.5
         mov         r9, rdx                                      ;9.11
         lea         rax, QWORD PTR [r8*8]                        ;9.11
         sub         r9, rcx                                      ;9.11
         lea         r10, QWORD PTR [rax+r8*4]                    ;9.11
         cmp         r9, r10                                      ;9.11
         jl          just_copy       ; Prob 50%                   ;9.11
                                     ; LOE rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 ↙
    ↘ xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
just_copy2::                         ; Preds .B1.4 .B1.6
; R8 = cnt
; RDX = a2
; RCX = a1
         xor        r10d, r10d                                    ;8.2
         xor        r9d, r9d                                      ;
         xor        eax, eax                                      ;
                                     ; LOE rax rdx rcx rbx rbp rsi rdi r8 r9 r10 r12 r13 r14 r15 xmm6 xmm7 ↙
    ↘ xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.8::                              ; Preds .B1.8 just_copy2
         mov        r11d, DWORD PTR [rax+rdx]                     ;3.6
         inc        r10                                           ;8.2
         mov        DWORD PTR [r9+rcx], r11d                      ;3.6
         add        r9, 12                                        ;8.2
         add        rax, 28                                       ;8.2
         cmp        r10, r8                                       ;8.2
         jb         .B1.8             ; Prob 82%                  ;8.2
         jmp        exit              ; Prob 100%                 ;8.2
                                      ; LOE rax rdx rcx rbx rbp rsi rdi r8 r9 r10 r12 r13 r14 r15 xmm6 xmm7 ↙
    ↘ xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
just_copy::                           ; Preds .B1.2 .B1.5 .B1.6
; R8 = cnt
; RDX = a2
; RCX = a1
         xor        r10d, r10d                                    ;8.2
         xor        r9d, r9d                                      ;
         xor        eax, eax                                      ;
                                      ; LOE rax rdx rcx rbx rbp rsi rdi r8 r9 r10 r12 r13 r14 r15 xmm6 ↙
    ↘ xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.11::                              ; Preds .B1.11 just_copy
         mov        r11d, DWORD PTR [rax+rdx]                     ;3.6
         inc        r10                                           ;8.2
         mov        DWORD PTR [r9+rcx], r11d                      ;3.6
         add        r9, 12                                        ;8.2
         add        rax, 28                                       ;8.2
         cmp        r10, r8                                       ;8.2
         jb         .B1.11             ; Prob 82%                 ;8.2
                                       ; LOE rax rdx rcx rbx rbp rsi rdi r8 r9 r10 r12 r13 r14 r15 xmm6 ↙
    ↘ xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
exit::                                 ; Preds .B1.11 .B1.8 .B1.1
         ret                                                      ;10.1

上述程序首先根据输入参数确定分支,接着执行相应的例程。虽然它看起来就像是检查数组交叉分叉,但是编译器采用的是一种非常著名的内存块复制例程的优化方法。仔细分析就会发现,它所复制的例程居然完全相同。这或许是Intel C++编译器的某种不足吧。然而无论怎样,最后生成的程序功能正常。

本书刻意介绍这个例子,旨在让读者认识到:有些时候编译器的输出指令确实会让人感到摸不到头脑。然而只要程序功能正常,我们就不必进行深究了吧。