第 80 / 187 篇

7.4.3. 汇编中的循环

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C7-x86_64/loops.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

7.4.3. Loops in Assembly

与 if 语句一样,汇编中的循环也是用跳转指令实现的。不过,循环让指令可以根据对条件求值的结果被重新执行。

Like if statements, loops in assembly are also implemented using jump instructions. However, loops enable instructions to be revisited based on the result of an evaluated condition.

下例中的 sumUp 函数把从 1 到用户给定整数之间的所有正整数加起来。这段代码故意写得不够优化,以便演示 C 中的 while 循环。

The sumUp function shown in the following example sums up all the positive integers from 1 to a user-defined integer. This code is intentionally written suboptimally to illustrate a while loop in C.

1
2
3
4
5
6
7
8
9
10
11
int sumUp(int n) {
//initialize total and i
int total = 0;
int i = 1;

while (i <= n) { //while i is less than or equal to n
total += i; //add i to total
i++; //increment i by 1
}
return total;
}

编译这段代码并用 GDB 反汇编,得到如下汇编代码:

Compiling this code and disassembling it using GDB yields the following assembly code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Dump of assembler code for function sumUp:
0x400526 <+0>: push %rbp
0x400527 <+1>: mov %rsp,%rbp
0x40052a <+4>: mov %edi,-0x14(%rbp)
0x40052d <+7>: mov $0x0,-0x8(%rbp)
0x400534 <+14>: mov $0x1,-0x4(%rbp)
0x40053b <+21>: jmp 0x400547 <sumUp+33>
0x40053d <+23>: mov -0x4(%rbp),%eax
0x400540 <+26>: add %eax,-0x8(%rbp)
0x400543 <+29>: add $0x1,-0x4(%rbp)
0x400547 <+33>: mov -0x4(%rbp),%eax
0x40054a <+36>: cmp -0x14(%rbp),%eax
0x40054d <+39>: jle 0x40053d <sumUp+23>
0x40054f <+41>: mov -0x8(%rbp),%eax
0x400552 <+44>: pop %rbp
0x400553 <+45>: retq

同样,在这个例子中我们不会明确地画出栈。不过,我们鼓励读者自己把栈画出来。

Again, we will not draw out the stack explicitly in this example. However, we encourage readers to draw the stack out themselves.

前五条指令

The First Five Instructions

这个函数的前五条指令为函数的执行准备好栈,并为函数执行设置好临时值:

The first five instructions of this function set the stack up for function execution and set up temporary values for function execution:

1
2
3
4
5
0x400526 <+0>:  push %rbp              # save %rbp onto the stack
0x400527 <+1>: mov %rsp,%rbp # update the value of %rbp (new frame)
0x40052a <+4>: mov %edi,-0x14(%rbp) # copy n to %rbp-0x14
0x40052d <+7>: mov $0x0,-0x8(%rbp) # copy 0 to %rbp-0x8 (total)
0x400534 <+14>: mov $0x1,-0x4(%rbp) # copy 1 to %rbp-0x4 (i)

回想一下,栈上的位置存放函数中的临时变量。为了简单起见,我们把 %rbp-0x8 所标记的位置称为 total,把 %rbp - 0x4 称为 i。sumUp 的输入参数(n)被移到栈位置 %rbp-0x14。尽管临时变量被放在了栈上,但要记住,执行完第一条指令(即 push %rbp)之后,栈指针就没有再改变过。

Recall that stack locations store temporary variables in a function. For simplicity we will refer to the location marked by %rbp-0x8 as total and %rbp - 0x4 as i. The input parameter to sumUp (n) is moved to stack location %rbp-0x14. Despite the placement of temporary variables on the stack, keep in mind that the stack pointer has not changed after the execution of the first instruction (i.e., push %rbp).

译注

这里没有用 sub 移动 %rsp,就把变量放在了 %rsp 下方,这是因为 sumUp 是叶子函数(不再调用其他函数)。x86-64 System V ABI 规定栈指针下方有 128 字节的「红区」(red zone),叶子函数可以直接使用而不必调整 %rsp。

循环的核心

The Heart of the Loop

sumUp 函数中接下来的七条指令构成了循环的核心:

The next seven instructions in the sumUp function represent the heart of the loop:

1
2
3
4
5
6
7
0x40053b <+21>:  jmp    0x400547 <sumUp+33>  # goto <sumUp+33>
0x40053d <+23>: mov -0x4(%rbp),%eax # copy i to %eax
0x400540 <+26>: add %eax,-0x8(%rbp) # add i to total (total += i)
0x400543 <+29>: add $0x1,-0x4(%rbp) # add 1 to i (i += 1)
0x400547 <+33>: mov -0x4(%rbp),%eax # copy i to %eax
0x40054a <+36>: cmp -0x14(%rbp),%eax # compare i to n
0x40054d <+39>: jle 0x40053d <sumUp+23> # if (i <= n) goto <sumUp+23>
  • 第一条指令是直接跳转到 <sumUp+33>,它把指令指针(%rip)设为地址 0x400547。
  • The first instruction is a direct jump to <sumUp+33>, which sets the instruction pointer (%rip) to address 0x400547.
  • 接下来执行的指令是 mov -0x4(%rbp),%eax,它把 i 的值放到寄存器 %eax 中。寄存器 %rip 更新为 0x40054a。
  • The next instruction that executes is mov -0x4(%rbp),%eax, which places the value of i in register %eax. Register %rip is updated to 0x40054a.
  • <sumUp+36> 处的 cmp 指令比较 i 和 n,并设置相应的条件码寄存器。寄存器 %rip 被设为 0x40054d。
  • The cmp instruction at <sumUp+36> compares i to n and sets the appropriate condition code registers. Register %rip is set to 0x40054d.

然后执行 jle 指令。接下来执行哪些指令,取决于是否走分支。

The jle instruction then executes. The instructions that execute next depend on whether or not the branch is taken.

假设走了分支(即 i <= n 为真)。那么指令指针被设为 0x40053d,程序的执行跳到 <sumUp+23>。接着依次执行以下指令:

Suppose that the branch is taken (i.e., i <= n is true). Then the instruction pointer is set to 0x40053d and program execution jumps to <sumUp+23>. The following instructions then execute in sequence:

  • <sumUp+23> 处的 mov 指令把 i 复制到寄存器 %eax。
  • The mov instruction at <sumUp+23> copies i to register %eax.
  • add %eax,-0x8(%rbp) 把 i 加到 total 上(即 total += i)。
  • The add %eax,-0x8(%rbp) adds i to total (i.e., total += i).
  • 接着,<sumUp+29> 处的 add 指令把 i 加 1(即 i += 1)。
  • The add instruction at <sumUp+29> then adds 1 to i (i.e., i += 1).
  • <sumUp+33> 处的 mov 指令把更新后的 i 值复制到寄存器 %eax。
  • The mov instruction at <sumUp+33> copies the updated value of i to register %eax.
  • 然后 cmp 指令比较 i 和 n,并设置相应的条件码寄存器。
  • The cmp instruction then compares i to n and sets the appropriate condition code registers.
  • 接着执行 jle。如果 i 小于或等于 n,程序的执行再次跳到 <sumUp+23>,循环(定义在 <sumUp+23> 和 <sumUp+39> 之间)重复执行。
  • Next, jle executes. If i is less than or equal to n, program execution once again jumps to <sumUp+23> and the loop (defined between <sumUp+23> and <sumUp+39>) repeats.

如果没有走分支(即 i 不小于或等于 n),则执行以下指令:

If the branch is not taken (i.e., i is not less than or equal to n), the following instructions execute:

1
2
3
0x40054f <+41>:  mov    -0x8(%rbp),%eax     # copy total to %eax
0x400552 <+44>: pop %rbp # restore rbp
0x400553 <+45>: retq # return (total)

这些指令把 total 复制到寄存器 %eax,把 %rbp 恢复为原来的值,然后退出函数。因此,函数在退出时返回 total。

These instructions copy total to register %eax, restore %rbp to its original value, and exit the function. Thus, the function returns total upon exit.

表 1 展示了 sumUp 函数的汇编形式和 C 的 goto 形式:

Table 1 shows the assembly and C goto forms of the sumUp function:

表 1. 把 sumUp 翻译成 C 的 goto 形式

Table 1. Translating sumUp into goto C form.

汇编

Assembly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<sumUp>:
<+0>: push %rbp
<+1>: mov %rsp,%rbp
<+4>: mov %edi,-0x14(%rbp)
<+7>: mov $0x0,-0x8(%rbp)
<+14>: mov $0x1,-0x4(%rbp)
<+21>: jmp 0x400547 <sumUp+33>
<+23>: mov -0x4(%rbp),%eax
<+26>: add %eax,-0x8(%rbp)
<+29>: add $0x1,-0x4(%rbp)
<+33>: mov -0x4(%rbp),%eax
<+36>: cmp -0x14(%rbp),%eax
<+39>: jle 0x40053d <sumUp+23>
<+41>: mov -0x8(%rbp),%eax
<+44>: pop %rbp
<+45>: retq

翻译出的 goto 形式

Translated goto Form

1
2
3
4
5
6
7
8
9
10
11
12
13
int sumUp(int n) {
int total = 0;
int i = 1;
goto start;
body:
total += i;
i += 1;
start:
if (i <= n) {
goto body;
}
return total;
}

上面的代码也等价于下面这段不含 goto 语句的 C 代码:

The preceding code is also equivalent to the following C code without goto statements:

1
2
3
4
5
6
7
8
9
int sumUp(int n) {
int total = 0;
int i = 1;
while (i <= n) {
total += i;
i += 1;
}
return total;
}

汇编中的 for 循环

for Loops in Assembly

sumUp 函数中的主循环也可以写成 for 循环:

The primary loop in the sumUp function can also be written as a for loop:

1
2
3
4
5
6
7
8
int sumUp2(int n) {
int total = 0; //initialize total to 0
int i;
for (i = 1; i <= n; i++) { //initialize i to 1, increment by 1 while i<=n
total += i; //updates total by i
}
return total;
}

这个版本生成的汇编代码与我们的 while 循环示例完全相同。下面再列出这段汇编代码,并为每一行加上英文注解:

This version yields assembly code identical to our while loop example. We repeat the assembly code below and annotate each line with its English translation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Dump of assembler code for function sumUp2:
0x400554 <+0>: push %rbp #save %rbp
0x400555 <+1>: mov %rsp,%rbp #update %rpb (new stack frame)
0x400558 <+4>: mov %edi,-0x14(%rbp) #copy %edi to %rbp-0x14 (n)
0x40055b <+7>: movl $0x0,-0x8(%rbp) #copy 0 to %rbp-0x8 (total)
0x400562 <+14>: movl $0x1,-0x4(%rbp) #copy 1 to %rbp-0x4 (i)
0x400569 <+21>: jmp 0x400575 <sumUp2+33> #goto <sumUp2+33>
0x40056b <+23>: mov -0x4(%rbp),%eax #copy i to %eax [loop]
0x40056e <+26>: add %eax,-0x8(%rbp) #add i to total (total+=i)
0x400571 <+29>: addl $0x1,-0x4(%rbp) #add 1 to i (i++)
0x400575 <+33>: mov -0x4(%rbp),%eax #copy i to %eax [start]
0x400578 <+36>: cmp -0x14(%rbp),%eax #compare i with n
0x40057b <+39>: jle 0x40056b <sumUp2+23> #if (i <= n) goto loop
0x40057d <+41>: mov -0x8(%rbp),%eax #copy total to %eax
0x400580 <+44>: pop %rbp #prepare to leave the function
0x400581 <+45>: retq #return total

要理解为什么这段代码的 for 循环版本与 while 循环版本生成的汇编完全相同,回想一下,for 循环的表示形式是:

To understand why the for loop version of this code results in identical assembly to the while loop version of the code, recall that the for loop has the following representation:

1
2
3
for ( <initialization>; <boolean expression>; <step> ){
<body>
}

它等价于下面的 while 循环表示形式:

and is equivalent to the following while loop representation:

1
2
3
4
5
<initialization>
while (<boolean expression>) {
<body>
<step>
}

由于每个 for 循环都可以用 while 循环表示,下面两个 C 程序都是前面那段汇编的等价表示:

Since every for loop can be represented by a while loop, the following two C programs are equivalent representations for the previous assembly:

表 2. 编写 sumUp 函数的两种等价方式

Table 2. Equivalent ways to write the sumUp function.

for 循环

For loop

1
2
3
4
5
6
7
8
int sumUp2(int n) {
int total = 0;
int i = 1;
for (i; i <= n; i++) {
total += i;
}
return total;
}

while 循环

While loop

1
2
3
4
5
6
7
8
9
int sumUp(int n){
int total = 0;
int i = 1;
while (i <= n) {
total += i;
i += 1;
}
return total;
}