第 110 / 187 篇

9.4.3. 汇编中的循环

说明

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

9.4.3. Loops in Assembly

与 if 语句一样,汇编中的循环也是用分支指令实现的。不过,循环能让指令根据所求条件的结果被重复执行。

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

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

The sumUp function in the following example sums up all the positive integers from 1 to a user-defined integer n. 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
17
18
19
20
21
Dump of assembler code for function sumUp:
0x0724 <+0>: sub sp, sp, #0x20
0x0728 <+4>: str w0, [sp, #12]
0x072c <+8>: str wzr, [sp, #24]
0x0730 <+12>: mov w0, #0x1
0x0734 <+16>: str w0, [sp, #28]
0x0738 <+20>: b 0x758 <sumUp+52>
0x073c <+24>: ldr w1, [sp, #24]
0x0740 <+28>: ldr w0, [sp, #28]
0x0744 <+32>: add w0, w1, w0
0x0748 <+36>: str w0, [sp, #24]
0x074c <+40>: ldr w0, [sp, #28]
0x0750 <+44>: add w0, w0, #0x1
0x0754 <+48>: str w0, [sp, #28]
0x0758 <+52>: ldr w1, [sp, #28]
0x075c <+56>: ldr w0, [sp, #12]
0x0760 <+60>: cmp w1, w0
0x0764 <+64>: b.le 0x73c <sumUp+24>
0x0768 <+68>: ldr w0, [sp, #24]
0x076c <+72>: add sp, sp, #0x20
0x0770 <+76>: ret

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

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 store some temporary values:

1
2
3
4
5
0x0724 <+0>:  sub  sp, sp, #0x20   //grow stack by 32 bytes (new stack frame)
0x0728 <+4>: str w0, [sp, #12] //store n at sp+12 (n)
0x072c <+8>: str wzr, [sp, #24] //store 0 at sp+24 (total)
0x0730 <+12>: mov w0, #0x1 //w0 = 1
0x0734 <+16>: str w0, [sp, #28] //store 1 at sp+28 (i)

具体来说,它们:

Specifically, they:

  • 让调用栈增长 32 字节,标出新的栈帧。
  • Grow the call stack by 32 bytes, marking the new frame.
  • 把第一个参数(n)存到栈位置 sp + 12 处。
  • Store the first parameter (n) at stack location sp + 12.
  • 把值 0 存到栈位置 sp + 24 处,表示 total。
  • Store the value 0 at stack location sp + 24, indicating total.
  • 把值 1 复制到寄存器 w0 中。
  • Copy the value 1 into register w0.
  • 把值 1 存到栈位置 sp + 28 处,表示 i。
  • Store the value 1 at stack location sp + 28, indicating i.

回想一下,栈上的位置存放的是函数中的临时变量。为简单起见,我们把 sp + 24 标记的位置称为 total,把 sp + 28 称为 i。sumUp 的输入参数(n)位于栈地址 sp + 12 处。尽管临时变量被放在栈上,但要记住,在第一条指令(sub sp, sp, #0x20)执行之后,栈指针就没有再改变过。

Recall that stack locations store temporary variables in a function. For simplicity we will refer to the location marked by sp + 24 as total and sp + 28 as i. The input parameter to sumUp (n) is located at stack address sp + 12. 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 (sub sp, sp, #0x20).

循环的核心

The Heart of the Loop

sumUp 函数中接下来的 12 条指令是这个循环的核心:

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

1
2
3
4
5
6
7
8
9
10
11
12
0x0738 <+20>: b     0x758 <sumUp+52>  // goto <sumUp+52>
0x073c <+24>: ldr w1, [sp, #24] // w1 = total
0x0740 <+28>: ldr w0, [sp, #28] // w0 = i
0x0744 <+32>: add w0, w1, w0 // w0 = i + total
0x0748 <+36>: str w0, [sp, #24] // store (total + i) in total
0x074c <+40>: ldr w0, [sp, #28] // w0 = i
0x0750 <+44>: add w0, w0, #0x1 // w0 = i + 1
0x0754 <+48>: str w0, [sp, #28] // store (i+1) in i (i.e. i++)
0x0758 <+52>: ldr w1, [sp, #28] // w1 = i
0x075c <+56>: ldr w0, [sp, #12] // w0 = n
0x0760 <+60>: cmp w1, w0 // compare i and n
0x0764 <+64>: b.le 0x73c <sumUp+24> // if (i <= n) goto <sumUp+24>
  • 第一条指令是直接跳转到 <sumUp+52>,它把程序计数器寄存器(pc)设为地址 0x758。
  • The first instruction is a direct jump to <sumUp+52>, which sets the program counter register (pc) to address 0x758.
  • 接下来执行的两条指令(位于 <sumUp+52> 和 <sumUp+56>)把 i 和 n 分别加载到寄存器 w1 和 w0 中。
  • The next two instructions that execute (at <sumUp+52> and <sumUp+56>) load i and n into registers w1 and w0, respectively.
  • <sumUp+60> 处的 cmp 指令比较 i 和 n,设置相应的条件标志。程序计数器 pc 前进到下一条指令,即地址 0x764。
  • The cmp instruction at <sumUp+60> compares i and n, setting the appropriate condition flags. The program counter pc advances to the next instruction, or address 0x764.
  • 如果 i 小于或等于 n,<sumUp+64> 处的 b.le 指令就把 pc 寄存器替换为地址 0x73c。
  • The b.le instruction at <sumUp+64> replaces the pc register with address 0x73c if i is less than or equal to n.

如果走了分支(也就是说,如果 i <= n),程序的执行跳转到 <sumUp+24>,并执行下面的指令:

If the branch is taken (that is, if i <= n), program execution jumps to <sumUp+24> and the following instructions execute:

  • <sumUp+24> 和 <sumUp+28> 处的 ldr 指令把 total 和 i 分别加载到寄存器 w1 和 w0 中。
  • The ldr instructions at <sumUp+24> and <sumUp+28> load total and i into registers w1 and w0, respectively.
  • 然后,<sumUp+32> 处的 add 指令把 total 加到 i 上(即 i + total),并把结果存入 w0。
  • The add instruction at <sumUp+32> then adds total to i (i.e., i + total) and stores the result in w0.
  • 然后,<sumUp+36> 处的 str 指令用寄存器 w0 中的值更新 total(即 total = total + i)。
  • The str instruction at <sumUp+36> then updates total with the value in register w0 (i.e., total = total + i)
  • <sumUp+40> 处的 ldr 指令把 i 加载到寄存器 w0 中。
  • The ldr instruction at <sumUp+40> loads i into register w0.
  • <sumUp+44> 处的 add 指令把 i 加 1,并把结果存入寄存器 w0。
  • The add instruction at <sumUp+44> adds 1 to i and stores the result in register w0.
  • <sumUp+48> 处的 str 指令用寄存器 w0 中存放的值更新 i(即 i = i + 1)。
  • The str instruction at <sumUp+48> updates i with the value stored in register w0 (i.e., i = i + 1)
  • <sumUp+52> 和 <sumUp+56> 处的 ldr 指令把 i 和 n 分别加载到寄存器 w1 和 w0 中。
  • The ldr instructions at <sumUp+52> and <sumUp+56> load i and n into registers w1 and w0, respectively.
  • <sumUp+60> 处的 cmp 指令比较 i 和 n,并设置相应的条件码标志。
  • The cmp instruction at <sumUp+60> compares i to n and sets the appropriate condition code flags.
  • 接着执行 b.le 指令。如果 i 小于或等于 n,程序的执行跳回 <sumUp+24>,pc 被设为 0x73c,<sumUp+24> 到 <sumUp+64> 之间的指令再次执行。否则,寄存器 pc 被设为顺序中下一条指令的地址,即 0x768(<sumUp+68>)。
  • The b.le instruction then executes. If i is less than or equal to n, program execution jumps back to <sumUp+24>, pc is set to 0x73c, and the instructions between <sumUp+24> and <sumUp+64> repeat execution. Otherwise, register pc is set to the address of the next instruction in sequence, or 0x768 (<sumUp+68>).

如果没有走分支(即 i 大于 n),就执行下面的指令:

If the branch is not taken (i.e., i is greater than n), the following instructions execute:

1
2
3
0x0768 <+68>:  ldr   w0, [sp, #24]   // w0 = total
0x076c <+72>: add sp, sp, #0x20 // restore stack
0x0770 <+76>: ret // return w0 (total)

这些指令把 total 复制到返回寄存器 w0,通过收缩 sp 恢复调用栈,然后退出函数。因此,函数退出时返回 total。

These instructions copy total to the return register w0, restore the call stack by shrinking sp, 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 side by side:

表 1. 把 sumUp() 翻译成 goto 形式的 C 代码

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
17
18
19
20
21
<sumUp>:
<+0>: sub sp, sp, #0x20
<+4>: str w0, [sp, #12]
<+8>: str wzr, [sp, #24]
<+12>: mov w0, #0x1
<+16>: str w0, [sp, #28]
<+20>: b 0x758 <sumUp+52>
<+24>: ldr w1, [sp, #24]
<+28>: ldr w0, [sp, #28]
<+32>: add w0, w1, w0
<+36>: str w0, [sp, #24]
<+40>: ldr w0, [sp, #28]
<+44>: add w0, w0, #0x1
<+48>: str w0, [sp, #28]
<+52>: ldr w1, [sp, #28]
<+56>: ldr w0, [sp, #12]
<+60>: cmp w1, w0
<+64>: b.le 0x73c <sumUp+24>
<+68>: ldr w0, [sp, #24]
<+72>: add sp, sp, #0x20
<+76>: ret

翻译出的 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 yields identical assembly code 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
17
18
19
20
21
Dump of assembler code for function sumUp2:
0x0774 <+0>: sub sp, sp, #0x20 // grow stack by 32 bytes (new frame)
0x0778 <+4>: str w0, [sp, #12] // store n at sp+12 (n)
0x077c <+8>: str wzr, [sp, #24] // store 0 at sp+24 (total)
0x0780 <+12>: mov w0, #0x1 // w0 = 1
0x0784 <+16>: str w0, [sp, #28] // store 1 at sp+28 (i)
0x0788 <+20>: b 0x7a8 <sumUp2+52> // goto <sumUp2+52>
0x078c <+24>: ldr w1, [sp, #24] // w1 = total
0x0790 <+28>: ldr w0, [sp, #28] // w0 = i
0x0794 <+32>: add w0, w1, w0 // w0 = total + i
0x0798 <+36>: str w0, [sp, #24] // store (total+i) in total
0x079c <+40>: ldr w0, [sp, #28] // w0 = i
0x07a0 <+44>: add w0, w0, #0x1 // w0 = i + 1
0x07a4 <+48>: str w0, [sp, #28] // store (i+1) in i (i.e. i += 1)
0x07a8 <+52>: ldr w1, [sp, #28] // w1 = i
0x07ac <+56>: ldr w0, [sp, #12] // w0 = n
0x07b0 <+60>: cmp w1, w0 // compare i and n
0x07b4 <+64>: b.le 0x78c <sumUp2+24> // if (i <= n) goto <sumUp2+24>
0x07b8 <+68>: ldr w0, [sp, #24] // w0 = total
0x07bc <+72>: add sp, sp, #0x20 // restore stack
0x07c0 <+76>: ret // return w0 (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 循环表示:

This 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;
}