3.6.7 循环

3.6.7 循环

C 语言提供了多种循环结构，即 do-while、while 和 for。汇编中没有相应的指令存在，可以用条件测试和跳转组合起来实现循环的效果。GCC 和其他编译器产生的循环代码主要基于两种基本的循环模式。我们会循序渐进地研究循环的翻译，从 do-while 开始，然后再研究具有更复杂实现的循环，并覆盖这两种模式。

1. do-while 循环

do-while 语句的通用形式如下：

do
    body-statement
while (test-expr);

这个循环的效果就是重复执行 body-statement，对 test-expr 求值，如果求值的结果为非零，就继续循环。可以看到，body-statement 至少会执行一次。

这种通用形式可以被翻译成如下所示的条件和 goto 语句：

loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;

也就是说，每次循环，程序会执行循环体里的语句，然后执行测试表达式。如果测试为真，就回去再执行一次循环。

看一个示例，图 3-19a 给出了一个函数的实现，用 do-while 循环来计算函数参数的阶乘，写作 n!。这个函数只计算 n > 0 时 n 的阶乘的值。

练习题 3.22

A. 用一个 32 位 int 表示 n!，最大的 n 的值是多少？

B. 如果用一个 64 位 long 表示，最大的 n 的值是多少？

图 3-19b 所示的 goto 代码展示了如何把循环变成低级的测试和条件跳转的组合。result 初始化之后，程序开始循环。首先执行循环体，包括更新变量 result 和 n。然后测试 n > 1，如果是真，跳转到循环开始处。图 3-19c 所示的汇编代码就是 goto 代码的原型。条件跳转指令 jg（第 7 行）是实现循环的关键指令，它决定了是需要继续重复还是退出循环。

long fact_do(long n)
{
    long result = 1;
    do {
        result *= n;
        n = n-1;
    } while (n > 1);
    return result;
}

a）C 代码

long fact_do_goto(long n)
{
    long result = 1;
loop:
    result *= n;
    n = n-1;
    if (n > 1)
        goto loop;
    return result;
}

b）等价的 goto 版本

long fact_do(long n)
n in %rdi

1  fact_do:
2      movl  $1, %eax        Set result = 1
3  .L2:                      loop:
4      imulq %rdi, %rax      Compute result *= n
5      subq  $1, %rdi        Decrement n
6      cmpq  $1, %rdi        Compare n:1
7      jg    .L2             If >, goto loop
8      rep; ret              Return

c）对应的汇编代码

图 3-19　阶乘程序的 do-while 版本的代码。条件跳转会使得程序循环

逆向工程像图 3-19c 中那样的汇编代码，需要确定哪个寄存器对应的是哪个程序值。本例中，这个对应关系很容易确定：我们知道 n 在寄存器 %rdi 中传递给函数。可以看到寄存器 %rax 初始化为 1（第 2 行）。（注意，虽然指令的目的寄存器是 %eax，它实际上还会把 %rax 的高 4 字节设置为 0。）还可以看到这个寄存器还会在第 4 行被乘法改变值。此外，%rax 用来返回函数值，所以通常会用来存放需要返回的程序值。因此我们断定 %rax 对应程序值 result。

练习题 3.23 已知 C 代码如下：

long dw_loop(long x) {
    long y = x*x;
    long *p = &x;
    long n = 2*x;
    do {
        x += y;
        (*p)++;
        n--;
    } while (n > 0);
    return x;
}

GCC 产生的汇编代码如下：

long dw_loop(long x)
x initially in %rdi

1  dw_loop:
2      movq  %rdi, %rax
3      movq  %rdi, %rcx
4      imulq %rdi, %rcx
5      leaq  (%rdi,%rdi), %rdx
6  .L2:
7      leaq  1(%rcx,%rax), %rax
8      subq  $1, %rdx
9      testq %rdx, %rdx
10     jg    .L2
11     rep; ret

A. 哪些寄存器用来存放程序值 x、y 和 n？

B. 编译器如何消除对指针变量 p 和表达式 (*p)++ 隐含的指针间接引用的需求？

C. 对汇编代码添加一些注释，描述程序的操作，类似于图 3-19c 中所示的那样。

旁注　逆向工程循环

理解产生的汇编代码与原始源代码之间的关系，关键是找到程序值和寄存器之间的映射关系。对于图 3-19 的循环来说，这个任务非常简单，但是对于更复杂的程序来说，就可能是更具挑战性的任务。C 语言编译器常常会重组计算，因此有些 C 代码中的变量在机器代码中没有对应的值；而有时，机器代码中又会引入源代码中不存在的新值。此外，编译器还常常试图将多个程序值映射到一个寄存器上，来最小化寄存器的使用率。

我们描述 fact_do 的过程对于逆向工程循环来说，是一个通用的策略。看看在循环之前如何初始化寄存器，在循环中如何更新和测试寄存器，以及在循环之后又如何使用寄存器。这些步骤中的每一步都提供了一个线索，组合起来就可以解开谜团。做好准备，你会看到令人惊奇的变换，其中有些情况很明显是编译器能够优化代码，而有些情况很难解释编译器为什么要选用那些奇怪的策略。根据我们的经验，GCC 常常做的一些变换，非但不能带来性能好处，反而甚至可能降低代码性能。

2. while 循环

while 语句的通用形式如下：

while (test-expr)
    body-statement

与 do-while 的不同之处在于，在第一次执行 body-statement 之前，它会对 test-expr 求值，循环有可能就中止了。有很多种方法将 while 循环翻译成机器代码，GCC 在代码生成中使用其中的两种方法。这两种方法使用同样的循环结构，与 do-while 一样，不过它们实现初始测试的方法不同。

第一种翻译方法，我们称之为跳转到中间（jump to middle），它执行一个无条件跳转跳到循环结尾处的测试，以此来执行初始的测试。可以用以下模板来表达这种方法，这个模板把通用的 while 循环格式翻译到 goto 代码：

goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t)
        goto loop;

作为一个示例，图 3-20a 给出了使用 while 循环的阶乘函数的实现。这个函数能够正确地计算 0! = 1。它旁边的函数 fact_while_jm_goto（图 3-20b）是 GCC 带优化命令行选项 -Og 时产生的汇编代码的 C 语言翻译。比较 fact_while（图 3-20a）和 fact_do（图 3-19a）的代码，可以看到它们非常相似，区别仅在于循环前的 goto test 语句使得程序在修改 result 或 n 的值之前，先执行对 n 的测试。图的最下面（图 3-20c）给出的是实际产生的汇编代码。

练习题 3.24 对于如下 C 代码：

long loop_while(long a, long b)
{
    long result = ____________________;
    while (____________________) {
        result = ____________________;
        a = ____________________;
    }
    return result;
}

以命令行选项 -Og 运行 GCC 产生如下代码：

long loop_while(long a, long b)
a in %rdi, b in %rsi

1  loop_while:
2      movl  $1, %eax
3      jmp   .L2
4  .L3:
5      leaq  (%rdi,%rsi), %rdx
6      imulq %rdx, %rax
7      addq  $1, %rdi
8  .L2:
9      cmpq  %rsi, %rdi
10     jl    .L3
11     rep; ret

可以看到编译器使用了跳转到中间的翻译方法，在第 3 行用 jmp 跳转到以标号 .L2 开始的测试。填写 C 代码中缺失的部分。

long fact_while(long n)
{
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n-1;
    }
    return result;
}

a）C 代码

long fact_while_jm_goto(long n)
{
    long result = 1;
    goto test;
loop:
    result *= n;
    n = n-1;
test:
    if (n > 1)
        goto loop;
    return result;
}

b）等价的 goto 版本

long fact_while(long n)
n in %rdi

fact_while:
    movl  $1, %eax        Set result = 1
    jmp   .L5             Goto test
.L6:                      loop:
    imulq %rdi, %rax      Compute result *= n
    subq  $1, %rdi        Decrement n
.L5:                      test:
    cmpq  $1, %rdi        Compare n:1
    jg    .L6             If >, goto loop
    rep; ret              Return

c）对应的汇编代码

图 3-20　使用跳转到中间翻译方法的阶乘算法的 while 版本的 C 代码和汇编代码。C 函数 fact_while_jm_goto 说明了汇编代码版本的操作

第二种翻译方法，我们称之为 guarded-do，首先用条件分支，如果初始条件不成立就跳过循环，把代码变换为 do-while 循环。当使用较高优化等级编译时，例如使用命令行选项 -O1，GCC 会采用这种策略。可以用如下模板来表达这种方法，把通用的 while 循环格式翻译成 do-while 循环：

t = test-expr;
if (!t)
    goto done;
do
    body-statement
while (test-expr);
done:

相应地，还可以把它翻译成 goto 代码如下：

t = test-expr;
if (!t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;
done:

利用这种实现策略，编译器常常可以优化初始的测试，例如认为测试条件总是满足。

再来看个例子，图 3-21 给出了图 3-20 所示阶乘函数同样的 C 代码，不过给出的是 GCC 使用命令行选项 -O1 时的编译。图 3-21c 给出实际生成的汇编代码，图 3-21b 是这个汇编代码更易读的 C 语言表示。根据 goto 代码，可以看到如果对于 n 的初始值有 n <= 1，那么将跳过该循环。该循环本身的基本结构与该函数 do-while 版本产生的结构（图 3-19）一样。不过，一个有趣的特性是，循环测试（汇编代码的第 9 行）从原始 C 代码的 n > 1 变成了 n != 1。编译器知道只有当 n > 1 时才会进入循环，所以将 n 减 1 意味着 n > 1 或者 n = 1。因此，测试 n != 1 就等价于测试 n > 1。

long fact_while(long n)
{
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n-1;
    }
    return result;
}

a）C 代码

long fact_while_gd_goto(long n)
{
    long result = 1;
    if (n <= 1)
        goto done;
loop:
    result *= n;
    n = n-1;
    if (n != 1)
        goto loop;
done:
    return result;
}

b）等价的 goto 版本

long fact_while(long n)
n in %rdi

1  fact_while:
2      cmpq  $1, %rdi        Compare n:1
3      jle   .L7             If <=, goto done
4      movl  $1, %eax        Set result = 1
5  .L6:                      loop:
6      imulq %rdi, %rax      Compute result *= n
7      subq  $1, %rdi        Decrement n
8      cmpq  $1, %rdi        Compare n:1
9      jne   .L6             If !=, goto loop
10     rep; ret              Return
11 .L7:                      done:
12     movl  $1, %eax        Compute result = 1
13     ret                   Return

c）对应的汇编代码

图 3-21　使用 guarded-do 翻译方法的阶乘算法的 while 版本的 C 代码和汇编代码。函数 fact_while_gd_goto 说明了汇编代码版本的操作

练习题 3.25 对于如下 C 代码：

long loop_while2(long a, long b)
{
    long result = ____________________;
    while (____________________) {
        result = ____________________;
        b = ____________________;
    }
    return result;
}

以命令行选项 -O1 运行 GCC，产生如下代码：

a in %rdi, b in %rsi

1  loop_while2:
2      testq %rsi, %rsi
3      jle   .L8
4      movq  %rsi, %rax
5  .L7:
6      imulq %rdi, %rax
7      subq  %rdi, %rsi
8      testq %rsi, %rsi
9      jg    .L7
10     rep; ret
11 .L8:
12     movq  %rsi, %rax
13     ret

可以看到编译器使用了 guarded-do 的翻译方法，在第 3 行使用了 jle 指令使得当初始测试不成立时，忽略循环代码。填写缺失的 C 代码。注意汇编语言中的控制结构不一定与根据翻译规则直接翻译 C 代码得到的完全一致。特别地，它有两个不同的 ret 指令（第 10 行和第 13 行）。不过，你可以根据等价的汇编代码行为填写 C 代码中缺失的部分。

练习题 3.26 函数 fun_a 有如下整体结构：

long fun_a(unsigned long x) {
    long val = 0;
    while (...) {
        ...
    }
    return ...;
}

GCC C 编译器产生如下汇编代码：

long fun_a(unsigned long x)
x in %rdi

1  fun_a:
2      movl  $0, %eax
3      jmp   .L5
4  .L6:
5      xorq  %rdi, %rax
6      shrq  %rdi             Shift right by 1
7  .L5:
8      testq %rdi, %rdi
9      jne   .L6
10     andl  $1, %eax
11     ret

逆向工程这段代码的操作，然后完成下面作业：

A. 确定这段代码使用的循环翻译方法。

B. 根据汇编代码版本填写 C 代码中缺失的部分。

C. 用自然语言描述这个函数是计算什么的。

3. for 循环

for 循环的通用形式如下：

for (init-expr; test-expr; update-expr)
    body-statement

C 语言标准说明（有一个例外，练习题 3.29 中有特别说明），这样一个循环的行为与下面这段使用 while 循环的代码的行为一样：

init-expr;
while (test-expr) {
    body-statement
    update-expr;
}

程序首先对初始表达式 init-expr 求值，然后进入循环；在循环中它先对测试条件 test-expr 求值，如果测试结果为“假”就会退出，否则执行循环体 body-statement；最后对更新表达式 update-expr 求值。

GCC 为 for 循环产生的代码是 while 循环的两种翻译之一，这取决于优化的等级。也就是，跳转到中间策略会得到如下 goto 代码：

init-expr;
goto test;
loop:
    body-statement
    update-expr;
test:
    t = test-expr;
    if (t)
        goto loop;

而 guarded-do 策略得到：

init-expr;
t = test-expr;
if (!t)
    goto done;
loop:
    body-statement
    update-expr;
    t = test-expr;
    if (t)
        goto loop;
done:

作为一个示例，考虑用 for 循环写的阶乘函数：

long fact_for(long n)
{
    long i;
    long result = 1;
    for (i = 2; i <= n; i++)
        result *= i;
    return result;
}

如上述代码所示，用 for 循环编写阶乘函数最自然的方式就是将从 2 一直到 n 的因子乘起来，因此，这个函数与我们使用 while 或者 do-while 循环的代码很不一样。

这段代码中的 for 循环的不同组成部分如下：

组成部分	表达式
init-expr	i = 2
test-expr	i <= n
update-expr	i++
body-statement	result *= i;

用这些部分替换前面给出的模板中相应的位置，就把 for 循环转换成了 while 循环，得到下面的代码：

long fact_for_while(long n)
{
    long i = 2;
    long result = 1;
    while (i <= n) {
        result *= i;
        i++;
    }
    return result;
}

对 while 循环进行跳转到中间变换，得到如下 goto 代码：

long fact_for_jm_goto(long n)
{
    long i = 2;
    long result = 1;
    goto test;
loop:
    result *= i;
    i++;
test:
    if (i <= n)
        goto loop;
    return result;
}

确实，仔细查看使用命令行选项 -Og 的 GCC 产生的汇编代码，会发现它非常接近于以下模板：

long fact_for(long n)
n in %rdi

fact_for:
    movl  $1, %eax        Set result = 1
    movl  $2, %edx        Set i = 2
    jmp   .L8             Goto test
.L9:                      loop:
    imulq %rdx, %rax      Compute result *= i
    addq  $1, %rdx        Increment i
.L8:                      test:
    cmpq  %rdi, %rdx      Compare i:n
    jle   .L9             If <=, goto loop
    rep; ret              Return

练习题 3.27 先把 fact_for 转换成 while 循环，再进行 guarded-do 变换，写出 fact_for 的 goto 代码。

综上所述，C 语言中三种形式的所有的循环——do-while、while 和 for——都可以用一种简单的策略来翻译，产生包含一个或多个条件分支的代码。控制的条件转移提供了将循环翻译成机器代码的基本机制。

练习题 3.28 函数 fun_b 有如下整体结构：

long fun_b(unsigned long x) {
    long val = 0;
    long i;
    for (...; ...; ...) {
        ...
    }
    return val;
}

GCC C 编译器产生如下汇编代码：

long fun_b(unsigned long x)
x in %rdi

1  fun_b:
2      movl  $64, %edx
3      movl  $0, %eax
4  .L10:
5      movq  %rdi, %rcx
6      andl  $1, %ecx
7      addq  %rax, %rax
8      orq   %rcx, %rax
9      shrq  %rdi             Shift right by 1
10     subq  $1, %rdx
11     jne   .L10
12     rep; ret

逆向工程这段代码的操作，然后完成下面的工作：

A. 根据汇编代码版本填写 C 代码中缺失的部分。

B. 解释循环前为什么没有初始测试也没有初始跳转到循环内部的测试部分。

C. 用自然语言描述这个函数是计算什么的。

练习题 3.29 在 C 语言中执行 continue 语句会导致程序跳到当前循环迭代的结尾。当处理 continue 语句时，将 for 循环翻译成 while 循环的描述规则需要一些改进。例如，考虑下面的代码：

/* Example of for loop containing a continue statement */
/* Sum even numbers between 0 and 9 */
long sum = 0;
long i;
for (i = 0; i < 10; i++) {
    if (i & 1)
        continue;
    sum += i;
}

A. 如果我们简单地直接应用将 for 循环翻译到 while 循环的规则，会得到什么呢？产生的代码会有什么错误呢？

B. 如何用 goto 语句来替代 continue 语句，保证 while 循环的行为同 for 循环的行为完全一样？