第14章 循环

14.1 举例说明

14.1.1 x86

x86指令集里有一条专门的LOOP指令。LOOP指令检测ECX寄存器的值是否是0,如果它不是0则将其递减,并将操作权交给操作符所指定的标签处(即跳转)。或许是因为循环指令过于复杂的缘故,我至今尚未见过直接使用LOOP指令将循环语句转译成汇编语句的编译器。所以,如果哪个程序直接使用LOOP指令进行循环控制,那它很可能就是手写的汇编程序。

C/C++语言的循环控制语句主要分为for()、while()、do/while()语句。

我们从for()语句开始演示。

for()语句定义了循环的初始态(计数器的初始值)、循环条件(在变量满足何等条件下继续进行循环),以及循环控制(每次循环后对变量进行什么操作,通常是递增或递减)。当然这种语句也必须声明循环体,即每次循环时要实现什么操作。简而言之,for()语句的使用方法是:

for (初始态;循环条件;循环控制)
{
    循环体;
}

根据for()语句所代表的各种功能,编译器会把for()语句在编译为4个相应的功能体。

我们一起来编译下面的程序:

#include <stdio.h>

void printing_function(int i)
{
        printf ("f(%d)\n", i);
};

int main() 
{
        int i;

        for (i=2; i<10; i++)
                printing_function(i);
        return 0; 
};

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

指令清单14.1 MSVC 2010

_i$ = -4 
_main   PROC
    push   ebp
    mov    ebp, esp
    push   ecx
    mov    DWORD PTR _i$[ebp], 2     ; 初始态
    jmp    SHORT $LN3@main
$LN2@main:
    mov    eax, DWORD PTR _i$[ebp]     ; 循环控制语句:
    add    eax, 1                      ; i递增1
    mov    DWORD PTR _i$[ebp], eax
$LN3@main:
    cmp    DWORD PTR _i$[ebp], 10      ; 判断是否满足循环条件
    jge    SHORT $LN1@main             ; 如果i=10 则终止循环语句
    mov    ecx, DWORD PTR _i$[ebp]     ; 循环体: call f(i)
    push   ecx
    call   _printing_function
    add    esp, 4
    jmp    SHORT $LN2@main             ; 跳到循环开始处
$LN1@main:                             ; 循环结束
    xor    eax, eax
    mov    esp, ebp
    pop    ebp
    ret     0
_main    ENDP

上面的汇编代码可以说是中规中矩。

使用GCC 4.4.1(未启用优化选项)编译上述程序,可得到下述汇编指令。

指令清单14.2 GCC 4.4.1

main            proc near

var_20          = dword    ptr -20h
var_4           = dword    ptr –4

                push       ebp
                mov        ebp, esp
                and        esp, 0FFFFFFF0h
                sub        esp, 20h
                mov        [esp+20h+var_4], 2 ; (i) initializing
                jmp        short loc_8048476
loc_8048465:
                mov        eax, [esp+20h+var_4]
                mov        [esp+20h+var_20], eax
                call       printing_function
                add        [esp+20h+var_4], 1 ; (i) increment
loc_8048476:
                cmp        [esp+20h+var_4], 9
                jle        short loc_8048465 ; if i<=9, continue loop
                mov        eax, 0
                leave
                retn
main            endp

在开启优化选项(/Ox)后,MSVC的编译结果如下。

指令清单14.3 Optimizing MSVC

_main    PROC
     push   esi
     mov    esi, 2
$LL3@main:
     push   esi
     call   _printing_function
     inc    esi
     add    esp, 4
     cmp    esi, 10     ; 0000000aH
     jl     SHORT $LL3@main
     xor    eax, eax
     pop    esi
     ret    0
_main    ENDP

在开启优化选项后,ESI寄存器成为了局部变量i的专用寄存器;而在通常情况下,局部变量都应当位于栈。可见,编译器会在局部变量为数不多的情况下进行这样的优化。

进行这种优化的前提条件是:被调用方函数不应当修改局部变量专用寄存器的值。当然,在本例中编译器能够判断函数printing_function ()不会修改ESI寄存器的值。在编译器决定给局部变量分配专用寄存器的时候,它会在函数序言部分保存这些专用寄存器的初始状态,然后在函数尾声里还原这些寄存器的原始值。因此,您可以在本例main()函数的序言和尾声中分别看见PUSH ESI/POP ESI指令。

现在启用GCC 4.4.1的最深程度优化选项-O3,看看生成的汇编指令。

指令清单14.4 Optimizing GCC 4.4.1

main            proc near

var_10          = dword ptr -10h

                push    ebp
                mov     ebp, esp
                and     esp, 0FFFFFFF0h
                sub     esp, 10h
                mov     [esp+10h+var_10], 2
                call    printing_function
                mov     [esp+10h+var_10], 3
                call    printing_function
                mov     [esp+10h+var_10], 4
                call    printing_function
                mov     [esp+10h+var_10], 5
                call    printing_function
                mov     [esp+10h+var_10], 6
                call    printing_function
                mov     [esp+10h+var_10], 7
                call    printing_function
                mov     [esp+10h+var_10], 8
                call    printing_function
                mov     [esp+10h+var_10], 9
                call    printing_function
                xor     eax, eax
                leave
                retn
main            endp

GCC把我们的循环指令给展开(分解)了。

编译器会对选代次数较少的循环进行循环分解(Loop unwinding)对处理。展开循环体以后代码的执行效率会有所提升,但是会增加程序代码的体积。

编译经验表明,展开循环体较大的循环结构并非良策。大型函数的缓存耗费的内存占有量(cache footprint)较大。[1]

我们把变量i的最大值调整到100,看看GCC是否还会分解循环。

指令清单14.5 GCC

                public main
main            proc near

var_20          = dword    ptr -20h

                push       ebp
                mov        ebp, esp
                and        esp, 0FFFFFFF0h
                push       ebx
                mov        ebx, 2 ; i=2
                sub        esp, 1Ch

; aligning label loc_80484D0 (loop body begin) by 16-byte border:
                nop
loc_80484D0:
; pass (i) as first argument to printing_function():
                mov        [esp+20h+var_20], ebx
                add        ebx, 1 ; i++
                call       printing_function
                cmp        ebx, 64h ; i==100?
                jnz        short loc_80484D0 ; if not, continue
                add        esp, 1Ch
                xor        eax, eax ; return 0
                pop        ebx
                mov        esp, ebp
                pop        ebp
                retn
main            endp

这就与MSVC 2010 /Ox编译出来的代码差不多了。唯一的区别是,GCC使用EBX寄存器充当变量i的专用寄存器。因为GCC能够判断后面的被调用方函数不会修改这个专用寄存器的值,所以它才会这样分配寄存器。在GCC不能进行相应判断,但是还决定给局部变量分配专用寄存器的时候,它就会在使用局部变量的那个函数的序言和尾声部分添加相应指令,利用数据栈保存和恢复专用寄存器的原始值。我们可以在main()函数里看到这种现象:它在函数的序言和尾声部分分别存储和恢复了局部变量专用寄存器ebx的原始值。

14.1.2 x86:OllyDbg

我们启用MSVC 2010的优化选项“/Ox”和“/Ob0”来编译上述程序,然后使用OllyDbg调试生成的可执行文件。

如图14.1所示,OllyDbg能够识别简单的循环语句,并用方括号进行标注。

..\TU\1401.tif{}

图14.1 OllyDbg:main()函数的启动代码

我们按F8键进行单步调试,将会看到ESI寄存器的值不断递增。我们运行到ESI的值(变量i)为6的时刻,如图14.2所示。

..\TU\1402.tif{}

图14.2 OllyDbg:i=6时的循环体

i=9的时候,循环语句会做最后一次迭代。进行了这次迭代之后,i值变为10,不会再触发条件转移指令JL。main()函数结束时的情况如图14.3所示。

..\TU\1403.tif{}

图14.3 OllyDbg:ESI=10之后,循环结束

14.1.3 x86:跟踪调试工具tracer

您可能也注意到了,直接使用OllyDbg这样的调试工具跟踪调试程序并不方便。所以我自己写了个调试工具tracer。[2]

使用IDA打开编译后的可执行文件,找到PUSH ESI(这条指令把参数传递给printing_function()函数),记下其地址0x401026,然后通过下述指令启动tracer程序:

tracer.exe -l:loops_2.exe bpx=loops_2.exe!0x00401026

上述指令会在BPX设置的断点地址处中断,输出此时各寄存器的状态。

tracer工具会把寄存器的状态输出到tracer.log:

PID=12884|New process loops_2.exe
(0) loops_2.exe!0x401026
EAX=0x00a328c8 EBX=0x00000000 ECX=0x6f0f4714 EDX=0x00000000
ESI=0x00000002 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=PF ZF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000003 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF PF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000004 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF PF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000005 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000006 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF PF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000007 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000008 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF AF SF IF
(0) loops_2.exe!0x401026
EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188
ESI=0x00000009 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8
EIP=0x00331026
FLAGS=CF PF AF SF IF
PID=12884|Process loops_2.exe exited. ExitCode=0 (0x0)

从中可以看到ESI寄存器的值从2递增到9。

tracer工具能够追查函数中任意地址处的寄存器状态。它名字中的trace就强调了其独首的追查功能。它能够在任意指令处设置断点,以记录指定寄存器的变化过程。此外,它还可以生成可被IDA调用的.idc脚本文件,并为指令添加注释。例如,我们知道main()函数的地址是0x00401020,就可以执行

tracer.exe -l:loops_2.exe bpf=loops_2.exe!0x00401020,trace:cc

BPF的意思就是在函数执行前设置断点。

这条指令可以生成两个脚本文件,即loops_2.exe.idc和loops_2.exe_clear.idc。我们使用IDA加载脚本文件loops_2.exe.idc之后的情形如图14.4所示。

..\TU\1404.tif{}

图14.4 IDA加载.idc脚本文件

根据Tracer给循环体进行的注释可知:ESI的值首先会从2递增到9。在递增指令结束之后,ESI的值再从3递增到0xA(10)。另外,在main()函数结束的时候,EAX的值会是零。

在生成注释文件的同时,tracer还会生成loops_2.ext.txt。这个文件会统计每条指令被执行的次数,并且标注了各寄存器数值的变化过程。

指令清单14.6 loops_2.exe.txt

0x401020 (.text+0x20), e= 1 [PUSH ESI] ESI=1
0x401021 (.text+0x21), e= 1 [MOV ESI, 2]
0x401026 (.text+0x26), e= 8 [PUSH ESI] ESI=2..9
0x401027 (.text+0x27), e= 8 [CALL 8D1000h] tracing nested maximum level (1) reached, skipping ↩
➥this CALL 8D1000h=0x8d1000
0x40102c (.text+0x2c), e=  8 [INC ESI] ESI=2..9 
0x40102d (.text+0x2d), e= 8 [ADD ESP, 4] ESP=0x38fcbc 
0x401030 (.text+0x30), e= 8 [CMP ESI, 0Ah] ESI=3..0xa
0x401033 (.text+0x33), e= 8 [JL 8D1026h] SF=false,true OF=false 
0x401035 (.text+0x35), e= 1 [XOR EAX, EAX]
0x401037 (.text+0x37), e= 1 [POP ESI]
0x401038 (.text+0x38), e= 1 [RETN] EAX=0

我们可以使用grep指令搜索特定的关键字。

14.1.4 ARM

Non-optimizing Keil 6/2013 (ARM mode)

main
         STMFD    SP!, {R4,LR}
         MOV      R4, #2
         B        loc_368
loc_35C  ; CODE XREF: main+1C
         MOV      R0, R4
         BL       printing_function
         ADD      R4, R4, #1

loc_368  ; CODE XREF: main+8
         CMP      R4, #0xA
         BLT      loc_35C
         MOV      R0, #0
         LDMFD    SP!, {R4,PC}

上述代码中的R4寄存器用于存储循环计数器(即变量i)。

“MOV R4, #2”给变量i进行初始化赋值。

“MOV R0, R4”和“BL printing_function”指令构成循环体。前者负责向被调用方函数传递参数,后者则直接调用printing_function ()函数。

“ADD R4, R4, #1”指令在每次迭代之后进行i++的运算。

“CMP R4, #0xA”指令会比较变量i和数字10(十六进制的0xA)。下一条指令BLT(Branch Less Than)会在i<10的情况下进行跳转;否则执行“MOV R0,#0”(处理返回值),并且退出当前函数。

Optimizing Keil 6/2013 (Thumb mode)

_main
           PUSH      {R4,LR}
           MOVS      R4, #2

loc_132                        ; CODE XREF: _main+E
           MOVS      R0, R4
           BL        printing_function
           ADDS      R4, R4, #1
           CMP       R4, #0xA
           BLT       loc_132
           MOVS      R0, #0
           POP       {R4,PC}

这段代码似乎不需更多解释。

Optimizing Xcode 4.6.3 (LLVM) (Thumb-2 mode)

_main
       PUSH            {R4,R7,LR}
       MOVW            R4, #0x1124 ; "%d\n"
       MOVS            R1, #2
       MOVT.W          R4, #0
       ADD             R7, SP, #4
       ADD             R4, PC
       MOV             R0, R4
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #3
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #4
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #5
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #6
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #7
       BLX             _printf
       MOV             R0, R4
       MOVS            R1, #8
       BLX             _printf
       MOV             R0, R4
       MOV             R1, #9
       BLX             _printf
       MOVS            R0, #0
       POP             {R4,R7,PC}

实际上,它把printing_function ()函数内部的指令直接代入了循环体:

void printing_function (int i)
{
    printf ("%d\n", i);
};

可见,LLVM不仅把循环控制语句展开为8个顺序执行的循环体,而且还在main()函数的循环体内直接代入了printing_function ()函数内部的指令。当循环体调用的函数不复杂且循环的次数不高时,LLVM编译器会把它们都拿出来进行分解和展开。

ARM64: Optimizing GCC 4.9.1

指令清单14.7 Optimizing GCC 4.9.1

printing_function:
; prepare second argument of printf():
        mov      w1, w0
; load address of the "f(%d)\n" string
        adrp     x0, .LC0
        add      x0, x0, :lo12:.LC0
; just branch here instead of branch with link and return:
        b        printf
main:
; save FP and LR in the local stack:
        stp      x29, x30, [sp, -32]!
; set up stack frame:
        add      x29, sp, 0
; save contents of X19 register in the local stack:
        str      x19, [sp,16]
; we will use W19 register as counter.
; set initial value of 2 to it:
        mov      w19, 2
.L3:
; prepare first argument of printing_function():
        mov      w0, w19
; increment counter register.
        add      w19, w19, 1
; W0 here still holds value of counter value before increment.
        bl       printing_function
; is it end?
        cmp      w19, 10
; no, jump to the loop body begin:
        bne      .L3
; return 0
        mov      w0, 0
; restore contents of X19 register:
        ldr      x19, [sp,16]
; restore FP and LR values:
        ldp      x29, x30, [sp], 32
        ret
.LC0:
        .string "f(%d)\n"

ARM64: Non-optimizing GCC 4.9.1

指令清单14.8 Non-optimizing GCC 4.9.1

printing_function:
; prepare second argument of printf():
        mov      w1, w0
; load address of the "f(%d)\n" string
        adrp     x0, .LC0
        add      x0, x0, :lo12:.LC0
; just branch here instead of branch with link and return:
        b        printf
main:
; save FP and LR in the local stack:
        stp      x29, x30, [sp, -32]!
; set up stack frame:
        add      x29, sp, 0
; save contents of X19 register in the local stack:
        str      x19, [sp,16]
; we will use W19 register as counter.
; set initial value of 2 to it:
        mov      w19, 2
.L3:
; prepare first argument of printing_function():
        mov      w0, w19
; increment counter register.
        add      w19, w19, 1
; W0 here still holds value of counter value before increment.
        bl       printing_function
; is it end?
        cmp      w19, 10
; no, jump to the loop body begin:
        bne      .L3
; return 0
        mov      w0, 0
; restore contents of X19 register:
        ldr      x19, [sp,16]
; restore FP and LR values:
        ldp      x29, x30, [sp], 32
        ret
.LC0:
        .string "f(%d)\n"
14.1.5 MIPS

指令清单14.9 Non-optimizing GCC 4.4.5 (IDA)

main:

; IDA is not aware of variable names in local stack
; We gave them names manually:
i               = -0x10
saved_FP        = -8
saved_RA        = -4

; function prologue:
                addiu    $sp, -0x28
                sw       $ra, 0x28+saved_RA($sp)
                sw       $fp, 0x28+saved_FP($sp)
                move     $fp, $sp
; initialize counter at 2 and store this value in local stack
                li       $v0, 2
                sw       $v0, 0x28+i($fp)
; pseudoinstruction. "BEQ $ZERO, $ZERO, loc_9C" there in fact:
                b        loc_9C
                or       $at, $zero ; branch delay slot, NOP
# ---------------------------------------------------------------------------
loc_80:                                  # CODE XREF: main+48
; load counter value from local stack and call printing_function():
                lw       $a0, 0x28+i($fp)
                jal      printing_function
                or       $at, $zero ; branch delay slot, NOP
; load counter, increment it, store it back:
                lw       $v0, 0x28+i($fp)
                or       $at, $zero ; NOP
                addiu    $v0, 1
                sw       $v0, 0x28+i($fp)
loc_9C:                                  # CODE XREF: main+18
; check counter, is it 10?
                lw       $v0, 0x28+i($fp)
                or       $at, $zero ; NOP
                slti     $v0, 0xA
; if it is less than 10, jump to loc_80 (loop body begin):
                bnez     $v0, loc_80
                or       $at, $zero ; branch delay slot, NOP
; finishing, return 0:
                move     $v0, $zero
; function epilogue:
                move     $sp, $fp
                lw       $ra, 0x28+saved_RA($sp)
                lw       $fp, 0x28+saved_FP($sp)
                addiu    $sp, 0x28
                jr       $ra
                or       $at, $zero ; branch delay slot, NOP

上述代码中的“B”指令属于IDA生成的伪指令。它原本的指令是BEQ。

14.1.6 其他

您可能注意到了,在对循环控制变量i进行初始化赋值之后,程序首先检查变量i是否满足循环条件。在满足循环表达式的情况下,才会运行循环体的指令。这恐怕是有意而为之。如果循环变量的初始值不能满足循环条件,那么整个循环体都不会被执行。例如,下面例子中的循环体就可能不会被执行:

for (i=0; i<total_entries_to_process; i++)
     loop_body;

如果变量total_entries_to_process等于零,就不应当执行循环体。所以,循环控制语句有必要首先检查控制变量的初始值是否满足循环条件。

在启用优化选项之后,如果编译器能够判断循环语句的初始状态不可能满足循环体的执行条件,那么它可能根本不会生成该循环体的条件检测指令和循环体的对应指令。在启用编译器的优化功能之后,在编译本例的源程序时,Keil、Xcode(LLVM)、MSVC都能做到这种程度的优化。

14.2 内存块复制

目前的计算机多数采取了SIMD和矢量化等技术,在内存中复制数据时,能够在每次迭代中复制4~8个字节。本节将从一个尽可能简单的例子开始演示。

#include <stdio.h>

void my_memcpy (unsigned char* dst, unsigned char* src, size_t cnt)
{
         size_t i;
         for (i=0; i<cnt; i++)
                  dst[i]=src[i];
};
14.2.1 编译结果

指令清单14.10 GCC 4.9 x64 optimized for size (-Os)

my_memcpy:
; RDI = destination address
; RSI = source address
; RDX = size of block

; initialize counter (i) at 0
          xor     eax, eax
.L2:
; all bytes copied? exit then:
          cmp     rax, rdx
          je      .L5
; load byte at RSI+i:
          mov     cl, BYTE PTR [rsi+rax]
; store byte at RDI+i:
          mov     BYTE PTR [rdi+rax], cl
          inc     rax ; i++
          jmp     .L2
.L5:
          ret

指令清单14.11 GCC 4.9 ARM64 optimized for size (-Os)

my_memcpy:
; X0 = destination address
; X1 = source address
; X2 = size of block

; initialize counter (i) at 0
          mov      x3, 0
.L2:
; all bytes copied? exit then:
          cmp      x3, x2
          beq      .L5
; load byte at X1+i:
          ldrb    w4, [x1,x3]
; store byte at X1+i:
          strb    w4, [x0,x3]
          add     x3,x3,1         ; i++
          b       .L2 
.L5:
          ret

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

my_memcpy PROC
; R0 = destination address
; R1 = source address
; R2 = size of block

        PUSH      {r4, lr}
; initialize counter (i) at 0
        MOVS      r3,#0
; condition checked at the end of function, so jump there:
        B         |L0.12|
|L0.6|
; load byte at R1+i:
        LDRB      r4,[r1,r3]
; store byte at R1+i:
        STRB      r4,[r0,r3]
; i++
        ADDS      r3,r3,#1
|L0.12|
; i<size?
        CMP       r3,r2
; jump to the loop begin if its so:'
        BCC       |L0.6|
        POP       {r4,pc}
        ENDP
14.2.2 编译为ARM模式的程序

在编辑ARM模式的应用程序时,Keil能够充分利用相应指令集的条件执行指令:

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

my_memcpy PROC
; R0 = destination address
; R1 = source address
; R2 = size of block

; initialize counter (i) at 0
        MOV     r3,#0
|L0.4|
; all bytes copied?
        CMP     r3,r2
; the following block is executed only if "less than" condition,
; i.e., if R2<R3 or i<size.
; load byte at R1+i:
        LDRBCC  r12,[r1,r3]
; store byte at R1+i:
        STRBCC  r12,[r0,r3]
; i++
        ADDCC   r3,r3,#1
; the last instruction of the "conditional block".
; jump to loop begin if i<size
; do nothing otherwise (i.e., if i>=size)
        BCC     |L0.4|
; return
        BX      lr
        ENDP

32位的ARM程序只用了一个转移指令,比thumb程序少了一个转移指令。

14.2.3 MIPS

指令清单14.14 GCC 4.4.5 optimized for size (-Os) (IDA)

my_memcpy:
; jump to loop check part:
                   b         loc_14
; initialize counter (i) at 0
; it will always reside in \$v0:
                   move     $v0, $zero ; branch delay slot

loc_8:                                          # CODE XREF: my_memcpy+1C
; load byte as unsigned at address in $t0 to $v1:
                   lbu      $v1, 0($t0)
; increment counter (i):
                   addiu    $v0, 1
; store byte at $a3
                   sb       $v1, 0($a3)

loc_14:                                        # CODE XREF: my_memcpy
; check if counter (i) in $v0 is still less then 3rd function argument ("cnt" in $a2):
                   sltu     $v1, $v0, $a2
; form address of byte in source block:
                   addu     $t0, $a1, $v0
; $t0 = $a1+$v0 = src+i
; jump to loop body if counter sill less then "cnt":
                   bnez     $v1, loc_8
; form address of byte in destination block (\$a3 = \$a0+\$v0 = dst+i):
                   addu     $a3, $a0, $v0 ; branch delay slot
; finish if BNEZ wasnt triggered:'
                   jr       $ra
                   or       $at, $zero ; branch delay slot, NOP

这里序言介绍的两个指令分别是LBU(Load Byte Unsigned)和SB(Store Byte)。与ARM模式的程序相似,所有的MIPS寄存器都是32位寄存器。在这两个平台上,我们无法像x86平台上那样直接对寄存器的低位进行直接操作。因此在对单个字节进行操作时,我们还是得访问整个32位寄存器。LBU指令加载字节型数据并且会清除寄存器的其他位。另外由于有符号数据存在符号位的问题,所以在处理有符号数的时候还要使用LB(Load Byte)指令把单字节的有符号数据扩展为等值的32位数据、再存储在寄存器里。SB指令的作用是把寄存器里的低8位复制到内存里。

14.2.4 矢量化技术

25.1.2节会详细介绍GCC的优化编译方式基于矢量化技术(Vectorization)的。

14.3 总结

当循环控制变量从2递增到9时,循环语句对应的汇编代码大体如下。

指令清单14.15 x86

    mov [counter], 2 ; initialization
    jmp check
body:
    ; loop body
    ; do something here
    ; use counter variable in local stack
    add [counter], 1 ; increment
check:
    cmp [counter], 9
    jle body

如果没有开启编译器的优化编译功能,那么控制变量的递增操作可能对应着3条汇编指令。

指令清单14.16 x86

    MOV [counter], 2 ; initialization
    JMP check
body:
    ; loop body
    ; do something here
    ; use counter variable in local stack
    MOV REG, [counter] ; increment
    INC REG
    MOV [counter], REG
check:
    CMP [counter], 9
    JLE body

当循环体较为短小时,编译器可能给循环控制变量分配专用的寄存器。

指令清单14.17 x86

    MOV EBX, 2 ; initialization
    JMP check
body:
    ; loop body
    ; do something here
    ; use counter in EBX, but do not modify it!
    INC EBX ; increment
check:
    CMP EBX, 9
    JLE body

编译器还可能调换部分指令的顺序。

指令清单14.18 x86

    MOV [counter], 2 ; initialization
    JMP label_check
label_increment:
    ADD [counter], 1 ; increment
label_check:
    CMP [counter], 10
    JGE exit
    ; loop body
    ; do something here
    ; use counter variable in local stack
    JMP label_increment
exit:

通常情况下,程序应当首先判断循环条件是否满足,然后再执行循环体。但是在编译器确定第一次迭代肯定会发生的情况下,它可能会调换循环体和判断语句的顺序。下面这个程序就是个典型的例子。

指令清单14.19 x86

    MOV REG, 2 ; initialization
body:
    ; loop body
    ; do something here
    ; use counter in REG, but do not modify it!
    INC REG ; increment
    CMP REG, 10
    JL body

编译器不会使用LOOP指令。由LOOP控制的循环控制语句比较少见。如果某段代码带有LOOP指令,那么您应当认为这是手写出来的汇编程序。

指令清单14.20 x86

    ; count from 10 to 1
    MOV ECX, 10
body:
    ; loop body
    ; do something here
    ; use counter in ECX, but do not modify it!
    LOOP body

ARM平台的R4寄存器专门用于存储循环控制变量。

指令清单14.21 ARM

    MOV R4, 2 ; initialization
    B check
body:
    ; loop body
    ; do something here
    ; use counter in R4, but do not modify it!
    ADD R4,R4, #1 ; increment
check:
    CMP R4, #10
    BLT body

14.4 练习题

14.4.1 题目1

为什么现在的编译器不再使用LOOP指令了?

14.4.2 题目2

使用您喜欢的操作系统和编译器编译14.1.1节的样本程序,然后修改这个可执行程序,使循环变量i可以从6递增到20。

14.4.3 题目3

请描述下述代码的功能。

指令清单14.22 由MSVC 2010 (启用/Ox选项)编译而得的代码

$SG2795 DB      '%d', 0aH, 00H

_main   PROC
        push   esi
        push   edi
        mov    edi,  DWORD PTR __imp__printf
        mov    esi, 100
        npad   3; align next label
$LL3@main:
        push   esi
        push   OFFSET $SG2795   ; '%d'
        call   edi
        dec    esi
        add    esp,  8
        test   esi,  esi
        jg     SHORT $LL3@main
        pop    edi
        xor    eax, eax
        pop    esi
        ret0
_main   ENDP

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

main PROC
         PUSH     {r4,lr}
         MOV      r4,#0x64
|L0.8|
         MOV      r1,r4
         ADR      r0,|L0.40|
         BL       __2printf
         SUB      r4,r4,#1
         CMP      r4,#0
         MOVLE    r0,#0
         BGT      |L0.8|
         POP      {r4,pc}
         ENDP

|L0.40|
         DCB      "%d\n",0

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

main PROC
         PUSH     {r4,lr}
         MOVS     r4,#0x64
|L0.40|
         MOVS     r1,r4
         ADR      r0,|L0.24|
         BL       __2printf
         SUBS     r4,r4,#1
         CMP      r4,#0
         BGT      |L0.4|
         MOVS     r0,#0
         POP      {r4,pc}
         ENDP

         DCW      0x0000
|L0.24|
         DCB      "%d\n",0

指令清单14.25 Optimizing GCC 4.9 (ARM64)

main:
         stp      x29, x30, [sp, -32]!
         add      x29, sp, 0
         stp      x19, x20, [sp,16]
         adrp     x20, .LC0
         mov      w19, 100
         add      x20, x20, :lo12:.LC0
.L2:
         mov      w1, w19
         mov      x0, x20
         bl       printf
         subs     w19, w19, #1
         bne      .L2
         ldp      x19, x20, [sp,16]
         ldp      x29, x30, [sp], 32
         ret
.LC0:
         .string  "%d\n"

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

main:

var_18           = -0x18
var_C            = -0xC
var_8            = -8
var_4            = -4

                 lui       $gp, (__gnu_local_gp >> 16)
                 addiu     $sp, -0x28
                 la        $gp, (__gnu_local_gp & 0xFFFF)
                 sw        $ra, 0x28+var_4($sp)
                 sw        $s1, 0x28+var_8($sp)
                 sw        $s0, 0x28+var_C($sp)
                 sw        $gp, 0x28+var_18($sp)
                 la        $s1, $LC0        # "%d\n"
                 li        $s0, 0x64  # 'd'

loc_28:                                  # CODE XREF: main+40
                 lw        $t9, (printf & 0xFFFF)($gp)
                 move      $a1, $s0
                 move      $a0, $s1
                 jalr      $t9
                 addiu     $s0, -1
                 lw        $gp, 0x28+var_18($sp)
                 bnez      $s0, loc_28
                 or        $at, $zero
                 lw        $ra, 0x28+var_4($sp)
                 lw        $s1, 0x28+var_8($sp)
                 lw        $s0, 0x28+var_C($sp)
                 jr        $ra
                 addiu     $sp, 0x28

$LC0:            .ascii "%d\n"<0>        # DATA XREF: main+1C
14.4.4 题目4

请描述下述代码的功能。

指令清单14.27 Optimizing MSVC 2010

$SG2795 DB      '%d', 0aH, 00H

_main   PROC
        push     esi
        push     edi
        mov      edi, DWORD PTR __imp_printf
        mov      esi, 1
        npad     3; align next label
$LL3@main:
        push     esi
        push     OFFSET $SG2795  ; '%d'
        call     edi
        add      esi, 3
        add      esp, 8
        cmp      esi, 100
        jl       SHORT $LL3@main
        pop      edi
        xor      eax, eax
        pop      esi
        ret      0
_main   ENDP

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

main  PROC
         PUSH    {r4,lr}
         MOV     r4,#1
|L0.8|
         MOV     r1,r4
         ADR     r0,|L0.40|
         BL      __2printf
         ADD     r4,r4,#3
         CMP     r4,#0x64
         MOVGE   r0,#0
         BLT     |L0.8|
         POP     {r4,pc}
         ENDP

|L0.40|
         DCB     "%d\n",0

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

main  PROC
         PUSH    {r4,lr}
         MOVS    r4,#1
|L0.4|
         MOVS    r1,r4
         ADR     r0,|L0.24|
         BL      __2printf
         ADDS    r4,r4,#3
         CMP     r4,#0x64
         BLT     |L0.4|
         MOVS    r0, #0
         POP     {r4,pc}
         ENDP

         DCW     0x0000
|L0.40|
         DCB     "%d\n",0

指令清单14.30 Optimizing GCC 4.9 (ARM64)

main:
         stp     x29, x30, [sp, -32]!
         add     x29, sp, 0
         stp     x19, x20, [sp,16]
         adrp    x20, .LC0
         mov     w19, 1
         add     x20, x20, :lo12:.LC0
.L2:
         mov     w1, w19
         mov     x0, x20
         add     w19, w19, 3
         bl      printf
         cmp     w19, 100
         bne     .L2
         ldp     x19, x20, [sp,16]
         ldp     x29, x30, [sp], 32
         ret
.LC0:
         .string "%d\n"

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

main:

var_18     = -0x18
var_10     = -0x10
var_C      = -0xC
var_8      = -8
var_4      = -4

           lui       $gp, (__gnu_local_gp >> 16)
           addiu     $sp, -0x28
           la        $gp, (__gnu_local_gp & 0xFFFF)
           sw        $ra, 0x28+var_4($sp)
           sw        $s2, 0x28+var_8($sp)
           sw        $s1, 0x28+var_C($sp)
           sw        $s0, 0x28+var_10($sp)
           sw        $gp, 0x28+var_18($sp)
           la        $s2, $LC0        # "%d\n"
           li        $s0, 1
           li        $s1, 0x64  # 'd'
loc_30:                                 # CODE XREF: main+48
           lw        $t9, (printf & 0xFFFF)($gp)
           move      $a1, $s0
           move      $a0, $s2
           jalr      $t9
           addiu     $s0, 3
           lw        $gp, 0x28+var_18($sp)
           bne       $s0, $s1, loc_30
           or        $at, $zero
           lw        $ra, 0x28+var_4($sp)
           lw        $s2, 0x28+var_8($sp)
           lw        $s1, 0x28+var_C($sp)
           lw        $s0, 0x28+var_10($sp)
           jr        $ra
           addiu     $sp, 0x28

$LC0:      .ascii    "%d\n"<0>           # DATA XREF: main+20

[1] 请参阅Dre07,及Int14, 3.4.1.7节。

[2] 如果您有兴趣,可以到作者的网站上下载。http://yurichev.com/tracer-en.html。