第三章:程序的机器级表示(上)

2021-12-23 本文已影响0人乘瓠散人

汇编代码是沟通高级程序设计语言代码和低级机器代码的桥梁，通过可读的汇编代码，可以理解机器执行的每一条指令。本文通过对汇编指令的解读，对计算机中数据的存取，数据的传输，基本的算术和逻辑操作，条件控制语句的实现，以及过程调用的流程等进行了详细地介绍。

计算机执行的是机器代码，即编码低级操作的字节序列，而编译器输出的人类可读的汇编代码则是机器代码的文本表示，给出了程序中的每一条的指令。

机器级代码涉及两种抽象：

指令集架构(Instruction Set Architecture, ISA)定义机器级程序的格式和行为。比如x86-64，将程序的行为描述成好像每条指令顺序执行。但实际处理器的硬件并发执行多条指令，但是可以采取措施保证整体行为和ISA指定的顺序执行行为完全一致。
机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组，但存储器系统的实际实现是将多个硬件存储器和操作系统软件组合起来。

程序计数器(在x86-64中用%rip表示)给出了将要执行的下一条指令在内存中的地址。程序内存用虚拟地址来寻址，例如x86-64的虚拟地址是由64位的字来表示的，在目前的实现中，这些地址高16位必须为0，所以一个地址实际上能够制定的是 $2^{48}$ =64TB范围内的一个字节。操作系统负责管理虚拟地址空间，将虚拟地址翻译成实际处理器内存中的物理地址。

一个x86-64的CPU包含16个通用目的寄存器，用来存储整数数据和指针。它们的名字都以%r开头，每个寄存器都有特殊的用途。
栈指针%rsp最特殊，用来指明运行时栈的结束位置。剩下的15个寄存器又可分为调用者保存寄存器(caller saved)和被调用者保存寄存器(callee saved)。比如函数A调用了函数B，则函数A称为调用者，函数B称为被调用者。

被调用者保存和调用者保存寄存器

寄存器rax用来保存函数的返回值。对于x86-64处理器，寄存器rax是8个字节，如果变量a是long类型，占了8个字节，则寄存器rax的全部数据位用来保存变量a；否则若变量a是short类型，只需要2个字节存储，那么只用到寄存器的低16位%al。

寄存器%rax

机器代码和汇编代码示例

给定C语言代码文件mstore.c:

#include <stdio.h>

long mult2(long, long);

// x->%rdi, y->%rsi, dest->%rdx
void multstore(long x, long y, long *dest) {
    long t = mult2(x, y);
    *dest = t;
}

编译后可以得到汇编代码和对应的机器代码：

机器代码和汇编代码

push %rbx 将寄存器%rbx的内容压入程序栈中进行保存
mov %rdx, %rbx 将寄存器%rdx的内容(dest)复制到%rbx
callq 调用函数mult2，函数的返回值会保存到寄存器%rax中
mov %rax, (%rbx) 将%rax保存的值送到内存中，内存的地址位于%rbx中
pop %rbx 恢复寄存器%rbx原来存储的内容
retq 函数返回

汇编指令后缀q表示数据的类型：

C语言数据类型和汇编代码后缀

访问信息

大多数汇编指令由两部分构成：操作码和操作数。

操作数

操作数可被分为三种类型：

立即数：表示常数值，用$开头
寄存器：表示某个寄存器的内容，用 $r_a$ 表示寄存器 $a$ ，用 $R[r_a]$ 表示它的值。寄存器就是CPU内的一种数据存储部件，只不过容量比较小。
内存引用(寄存器加小括号)：根据计算出来的地址(通常被称为有效地址)访问某个内存位置。 $M_b[addr]$ 表示对存储在内存中从地址 $addr$ 开始的 $b$ 个字节值的引用，为了简便可省略 $b$

操作数格式

数据传送指令mov

mov指令将数据从一个位置复制到另一个位置，包含两个操作数：源操作数和目的操作数。注意，x86-64处理器有一条限制，就是mov指令的源操作数和目的操作数不能都是内存的地址。因此，当需要将一个数从内存的一个位置复制到另一个位置时，需要两条mov指令来完成：第一条指令将内存源位置的数值加载到寄存器；第二条指令再将该寄存器的值写入内存的目的位置。

数据传送示例

movq (%rdi), %rax 从寄存器%rdi保存的内存地址xp中读出数据到寄存器%rax Memory -> Register
movq %rsi, (%rdi) 将寄存器%rsi保存的变量y写到寄存器%rdi保存的内存地址xp指向的内存里*xp Register -> Memory
ret函数返回寄存器%rax中保存的值x
像x这样的局部变量通常保存在寄存器中，而不是内存中，因为访问寄存器比访问内存快得多。

该例子说明了如何用mov指令从内存中读值到寄存器，再从寄存器写到内存的过程。可以发现，C语言的指针其实就是地址。

xp是一个指针，y是一个整数：
long x = *xp;  读取存在xp所指位置中的值，并将它存放到名为x的局部变量中
*xp = y; 与之相反，将变量y的值写入到xp所指的位置。

压栈出栈指令pushq和popq

程序栈本质上是内存中的一个区域。栈的增长方向是从高地址向低地址，因此栈顶元素地址最低。栈指针%rsp保存着栈顶元素的地址。

压栈和出栈

压栈：将一个四字值压入栈中，先将栈指针减8，然后将值写到新的栈顶地址。比如pushq %rax表示将寄存器rax中保存的值压入栈中，本质是将数据从寄存器写入到内存。
出栈：从栈顶的位置读出数据写入到寄存器，再修改栈顶指针。比如popq %rdx表示先从栈顶位置读出值0x123，再将其写到寄存器%rdx中，最后栈顶指针%rsp的值增加回到0x108。注意此时值0x123仍然保留在内存位置0x100中，直到被下次push操作覆盖。无论如何，%rsp指向的地址总是栈顶。

算术和逻辑操作

下图列出了x86-64的一些算术和逻辑操作，这些操作可被分为四类：加载有效地址、一元操作、二元操作、移位。

算术和逻辑操作

leaq指令

leaq为加载有效地址指令，即将有效地址复制到寄存器中。比如leaq 7(%rdx, %rdx, 4), %rax表示把有效地址复制到寄存器%rax中。
根据内存地址的计算方式可知： $Imm(r_b, r_i, s) \rightarrow Imm + R[r_b] + R[r_i]*s$ ，因此可得7(%rdx, %rdx, 4) = 7 + %rdx + %rdx*4 = 7 + 5*%rdx。假如寄存器%rdx内保存的值为x，则有效地址的值为7+5x。注意leaq指令并不是去内存地址7 + 5x处读取数据，而是将有效地址7+5x这个值直接写入到寄存器%rax中。

此外，leaq指令还可以用来表示加法和有限的乘法运算。

leaq指令编译简单算术表达式

注意这里后两条leaq指令不能直接用leaq (%rax, %rdx, 12), %rax替代，因为比例因子取值只能是1,2,4,8，因此要将12分解。

一元和二元操作指令

一元操作指令只有一个操作数，既是源操作数又是目的操作数。比如incq(%rsp)会是栈顶的元素值加1，这种语法容易让人想到C语言中的加1运算符(++)和减1运算符(--)。

二元操作指令由两个操作数，第二个操作数既是源操作数又是目的操作数。比如指令subq %rax, %rdx表示是寄存器%rdx中的值减去%rax中的值。这种语法容易让人想到C语言中的赋值运算符，如x-=y。

移位指令

左移指令有两个，效果一样，均为在右侧填0；右移指令分为算术右移和逻辑右移，算术右移需要填符号位，逻辑右移填0。
表达式long t = z * 48 对应的汇编指令为：

leaq (%rdx, %rdx, 2), %rax
salq $4, %rax

第一步先计算3*z(R[%rdx] + R[%rdx] * 2=3*z)，用leaq指令实现，计算结果保存到寄存器%rax中；第二步将寄存器的值左移4位，等价于乘以2^4=16，即2^4 * R[%rax] = 16 * (3*z) = 48 * z。
注意这里编译器没有直接使用乘法指令操作，主要是因为乘法指令的执行时间较长，因此编译器在生成汇编指令时会优先考虑更高效的方式。

控制

条件码

C语言中的某些结构，比如条件分支语句，循环语句，要求有条件的执行指令。因此，除了整数寄存器，CPU还维护着一组条件码(condition code)寄存器，它们描述了最近执行的操作的属性，可以通过检测这些寄存器的值来执行条件分支指令。

条件码寄存器，每个条件码长度为1个比特位

CF(Carry Flag) 进位标志：当CPU最近执行的一条指令最高位产生了进位，则CF被置为1。可以用来检查无符号数操作的溢出。
ZF(Zero Flag) 零标志：当最近操作的结果等于0时，ZF会被置为1。
SF(Sign Flag) 符号标志：当最近操作的结果小于0时，SF会被置为1。
OF(Overflow Flag) 溢出标注：针对有符号数，当最近操作的结果导致正溢出或负溢出时，OF会被置为1。

条件码寄存器的值是由ALU在执行算术和逻辑运算指令时写入的，除了leaq指令，其他算术和逻辑操作指令都会改变条件码寄存器的内容。除此之外，还有2类指令可以设置条件码寄存器：

CMP S1, S2指令：基于S2 - S1，根据两个操作数的差来设置条件码寄存器。除了只设置条件码而不更新目的寄存器的值外，CMP指令和减法指令SUB行为一样。
TEST S1, S2指令：基于S1 & S2，和AND指令类似，除了只设置条件码而不更新目的寄存器的值。

比较函数及其汇编代码

上图左侧的C语言代码对应的汇编代码如图右侧所示。
这里sete指令表示set when equal，会根据条件码ZF的值对寄存器al进行赋值。最后mov指令对寄存器al进行零扩展，返回判断结果。
这里sete指令是SET类指令中的一个，该类指令可以根据条件码的某种组合，将一个字节设置为0或1，如下图所示：

每条指令根据条件码的某种组合，将一个字节置为0或1

跳转指令

正常执行的情况下，指令按照它们出现的顺序一条条执行。跳转指令(jump)会导致执行切换到程序中一个新的位置。

跳转指令和set指令名字设置类似

用条件控制来实现条件分支
当条件满足时，程序沿着一条路径执行，否则就走另一条路径。

条件语句的编译

用条件传送来实现条件分支
计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个。只有在一些受限制的情况中，这种策略才可行。

使用条件赋值的条件语句的编译

这里的cmovge S, R是条件传送指令，当传送条件满足时，会把源值S复制到目的R。

条件控制 VS. 条件传送

使用条件传送的代码会比使用条件控制的的代码效率更高。因为现代处理器通过流水线来获得高性能。当遇到条件跳转时，处理器会根据分支预测器来猜测每条跳转指令是否会执行，当发生错误预测时，处理器会丢掉它为该跳转指令后所有指令已做的工作，重新用从正确位置处起始的指令填充流水线，浪费了大量的时间，导致程序性能下降。

但是使用条件传送也不总是会提高代码的效率。比如各分支语句的求解需要大量的计算，那么当相对应的条件不满足时，这些计算就白费了。一般来说，只有当两个表达式都很容易计算时，编译器才会使用条件传送；大多数情况，即使分支预测错误的开销会超过复杂的计算，GCC还是会使用条件控制转移。

循环

C语言提供了多种循环结构，即do-while，while和for。汇编中没有相应的指令，而是用条件测试和跳转的组合来实现循环的效果。

阶乘程序的do-while版本代码

阶乘程序的while版本代码，编译器优化等级为-Og时的翻译方式

for循环可转成while循环：

阶乘程序的for版本代码

switch语句

switch语句可以根据一个整数索引值进行多重分支。通过使用跳转表(jump table)这种数据结构，使得实现更高效。

switch语句的编译

如图所示，跳转表jt是一个有7个元素的数组，每个元素都是一个指向代码位置的指针。这些元素对应的index为0 ~ 6，对应n的值为100 ~ 106。跳转表对于重复的情况，比如case 104和case 106用同样的代码标号loc_D，而对于缺失情况的处理，比如case 101和case 105使用默认情况的标号loc_def。

过程

过程是软件中一种很重要的抽象。它提供了一种封装代码的方式，用一组指定的参数和一个可选的返回值实现了某种功能，从而可以隐藏某个行为的具体实现。过程的具体实现是多样的，比如C语言中的函数，Java语言中的方法等。

我们以C语言中的函数调用为例，介绍过程的机制。假设函数P调用函数Q，函数Q执行完后返回到P。这些操作包含以下方面：

传递控制。在进入函数Q时，程序计数器必须被设置为Q的代码的起始地址，然后在返回时，要把程序计数器设置为P中调用Q后面那条指令的地址。
传递数据。P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值。
分配和释放内存。在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。

运行时栈

C语言过程调用机制的一个关键特性就是使用了栈数据结构提供的后进先出的内存管理原则。

运行时栈的结构

当Q在执行时，P以及所有向上追溯到P的调用链中的过程，都是暂时被挂起的。
x86-64的栈向低地址方向增长，当函数执行需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间，这部分空间称为函数的栈帧。当前正在执行的函数的帧总是在栈顶。
当函数P调用函数Q时，会把返回地址压入栈中，指明当Q返回时，要从P程序的哪个位置继续执行。这个返回地址的压栈操作是通过函数调用指令call来实现的。
Q的代码会扩展当前栈的边界，分配它的栈帧所需的空间。

传递控制

将控制从函数P转移到函数Q需要使用call指令。call指令会把程序计数器(PC)设置为Q的代码的起始位置，以实现函数调用；同时也会把返回地址压入栈中，该返回地址就是调用函数Q指令后面那条指令的地址。
当函数Q执行完返回，ret指令会从栈中将返回地址弹出，并写入到程序计数器PC中，继续执行函数P中的下一步操作。

传递数据

过程调用除了传递控制，还可能会传递数据。大部分过程间的数据传送是通过寄存器实现的。当P调用Q时，P的代码必须首先把参数复制到适当的寄存器中，类似地，当Q返回到P时，P的代码可以访问寄存器%rax中的返回值。

x86-64中，可以通过寄存器最多传递6个整型参数，会根据参数在参数列表中的顺序为它们分配寄存器，如下图所示：

传递函数参数的寄存器

如果一个函数有大于6个整型参数，超出6个的部分要通过栈来传递。如上图3-25中所示的参数n ~ 参数7。

包含不同类型参数的函数示例

上图函数有8个参数，参数1 ~ 6通过寄存器传递，参数7 ~ 8通过栈传递。注意通过栈传递参数时，所有的数据大小都向8的倍数对齐。如下图所示，变量a4虽然只占了一个字节，但是仍然为其分配了8个字节的存储空间。

栈传递参数

局部存储

运行时栈提供了一种简单的、在需要时分配、函数完成时释放局部存储的机制。下面讨论寄存器上的局部存储。

寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个过程是活动的，但是我们必须保证当一个过程(调用者)调用另一个过程(被调用者)时，被调用者不会覆盖调用者稍后会使用的寄存器值。

寄存器中有一些为被调用者保存寄存器。当过程P调用过程Q时，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用时是一样的。
其他寄存器除了栈指针%rsp，都分类为调用者保存寄存器。任何函数都能修改调用者保存寄存器。可以理解为，在过程P调用过程Q时，由于Q可以随意修改此类寄存器，因此在调用Q前调用者P需要保存好该数据。

参考：
Datawhale 开源 408 计划——《深入理解计算机系统》

第三章:程序的机器级表示(上)

机器代码和汇编代码示例

访问信息

操作数

数据传送指令mov

压栈出栈指令pushq和popq

算术和逻辑操作

leaq指令

一元和二元操作指令

移位指令

控制

条件码

跳转指令

循环

switch语句

过程

运行时栈

传递控制

传递数据

局部存储

猜你喜欢

热点阅读