CSAPP 第三章 程序的机器级表示（一）x86-64指令基础与过程调用的机器级实现

发表于 | 分类于

可惜，成大事者，有反应快的，有反应慢的，有记忆力好的，有记忆力差的，唯独没有无法自律的。

1. Intel处理器历史沿革

处理器 年份 字长 重要特点
8086 1978 16位 MS-DOS，20位地址空间，1980年Intel提出8087浮点协处理器，建立了x86的浮点模型，称为x87
80286 1982 16位 MS-Windows，增加了更多的寻址模式
i386 1985 32位 Intel系列第一台支持Unix操作系统的机器，平坦寻址模式(flat addressing mode)
i486 1989 32位 集成浮点单元到处理器芯片上
Pentium 1993 32位 性能改善
PentiumPro 1995 32位 新的处理器设计，称为P7微体系结构，指令集中增加”条件传送(conditional move)”指令
Pentium/MMX 1997 32位 增加了一类新的处理整数向量的指令
Pentium II 1997 32位 P6微体系架构的延申
Pentium III 1999 32位 引入SSE，一类处理整数或浮点数向量的指令，芯片上包含二级告诉缓存
Pentium IV 2000 32位 SSE2，增加了新的数据类型（包括双精度浮点数），编译器可以使用SSE指令而不是x87指令来编译浮点代码
Pentium 4E 2004 64位 超线程，x86-64
Core 2 2006 64位 Intel第一个多核处理器，但不支持超线程
Core i7 Nehalem 2008 64位 多核+超线程，最初版本每个芯片最多四核，每核双线程
Core i7 Sandy Bridge 2011 64位 引入对SSE的扩展AVX，支持把数据装进256位的向量
Core i7 Haswell 2013 64位 AVX扩展至AVX2

2. 程序编码

相比C语言代码，机器级编程更靠近底层。这体现在两方面

  1. 借助了更底层的抽象
    • 指令集体系架构
    • 虚拟内存：将内存看成单个按字节寻址的数组。而C语言有各种数据类型、指针、变量名等更高层的抽象。
  2. 对程序员暴露了更多机器的细节
    • 程序计数器：%rip
    • 整数寄存器文件：16个命名64位寄存器
    • 条件码寄存器：保存最近执行的算术或逻辑指令的状态信息
    • 一组向量寄存器：可以存放一个或多个整数或浮点数值

2.1. 编译器相关

1
2
linux> gcc -Og -S hello.c
linux> gcc -Og -c hello.c
  • -S表示生成.s汇编文件
  • -c表示编译并汇编，生成目标.o文件

展示程序的字节表示

首先通过反汇编器确定函数对应的机器代码长度，例如14字节，然后在目标文件上运行GDB，使用下面的命令：

1
(gdb) x/14xb hello

14xb表示14个16进制表示的字节。

反汇编器的使用

1
linux> objdump -d hello.o

注：x86-64指令长度从1到15字节不等。

3. x86-64指令

3.1. 整数寄存器文件

前八个寄存器在8086时就已经存在，后期IA32中变化为32位，x86-64中变化为64位

  • %rax: 返回值
    • %eax, %ax, %al
  • %rbx: 被调用者保存
    • %ebx, %bx, %bl
  • %rcx: 第四个参数
    • %ecx, %cx, %cl
  • %rdx: 第三个参数
    • %edx, %dx, %dl
  • %rsi: 第二个参数
    • %esi, %si, %sil
  • %rdi: 第一个参数
    • %edi, %di, %dil
  • %rbp: 被调用者保存，base pointer
    • %ebp, %bp, %bpl
  • %rsp: 栈指针
    • %esp, %sp, %spl

后八个寄存器在x86-64中添加

  • %r8: 第五个参数
  • %r9: 第六个参数
  • %r10: 调用者保存
  • %r11: 调用者保存
  • %r12: 被调用者保存
  • %r13: 被调用者保存
  • %r14: 被调用者保存
  • %r15: 被调用者保存

对于访问低32位，低16位，低8位，以%r8为例，分别是%r8d, %r8w, %r8b。

注意：当指令以寄存器作为目标，对于生成小于8个字节的指令

  • 生成1字节和2字节数字的指令会保持剩下的字节不变
  • 生成4字节数字的指令会把高位4个字节置0

3.2. 寻址模式

寻址模式 格式 操作数值
立即数 $Imm Imm
寄存器 ra R[ra]
绝对寻址 Imm M[Imm]
间接寻址 (ra) M[R[ra]]
(基址+偏移量)寻址 Imm(rb) M[Imm + R[rb]]
变址寻址 (rb, ri) M[R[rb]+R[ri]]
变址寻址 Imm(rb,ri) M[Imm+R[rb]+R[ri]]
比例变址寻址 (,ri,s) M[R[ri]*s]
比例变址寻址 Imm(,ri,s) M[Imm+R[ri]*s]
比例变址寻址 (rb,ri,s) M[R[rb]+R[ri]*s]
比例变址寻址 Imm(rb,ri,s) M[Imm+R[rb]+R[ri]*s]
  • rb: base register
  • ri: index register
  • s: scale

总的来说汇编指令有三类：

  • 在内存和寄存器间转移数据
  • 对寄存器或内存执行算术运算
  • 控制转移/分支跳转

3.3. 数据传送指令

  • MOV S, D
    • 两个操作数不能都指向内存位置
    • movl指令会把寄存器高位4字节设置为0
    • movq指令只能以表示为32位补码数字的立即数作为源操作数，符号扩展到64位然后放到目的位置
    • movabsq能以任意64位立即数值作为源操作数
  • MOVZ S, D
    • 零扩展
    • 寄存器或内存作为源，寄存器作为目的
    • 后缀为
      • bw, bl, wl, bq, wq。没有lq，因为对于movl默认零扩展。
  • MOVS S, R
    • 符号扩展
    • 寄存器或内存作为源，寄存器作为目的
    • cltq：%rax <- 符号扩展(%eax)

栈相关指令

  • 栈指针指向栈顶元素地址
  • pushq S
    • R[%rsp] <- R[%rsp] - 8; M[R[%rsp]] <- S
  • popq D
    • D <- M[R[%rsp]]; R[%rsp] <- R[%rsp] + 8

3.4. 算术和逻辑指令

  • leaq S, D: D <- &S加载有效地址
    • 无其他大小的变种
    • 是movq指令的变种，指令形式是从内存读数据到寄存器，但是没有引用内存。仅是计算出内存地址。
    • 目的操作数必须是寄存器
  • 一元
    • INC D: 加1
    • DEC D: 减1
    • NEG D: 取负
    • NOT D: 取补
  • 二元
    • ADD S, D
    • SUB S, D
    • IMUL S, D
    • XOR S, D
    • OR S, D
    • AND S, D
  • 移位
    • SAL k, D
    • SHL k, D: 和SAL等价
    • SAR k, D: 算术右移
    • SHR k, D: 算术左移

3.5. 控制转移指令

3.5.1. 条件码寄存器

  • CF: 进位标志，最高位产生了进位。无符号操作溢出。
  • ZF: 零标志，最近的操作结果为0。
  • SF: 符号标志，最近的操作结果为负数。
  • OF: 溢出标志，补码溢出。

对于t = a + b，对上面条件码寄存器的赋值等价于

  • CF: (unsigned) t < (unsigned) a
  • ZF: (t == 0)
  • SF: (t < 0)
  • OF: (a<0 == b<0) && (t<0 != a<0)
    • a和b同号，但是它们的和的结果不同号

3.5.2. 影响条件码寄存器值的指令

  1. 算术和逻辑运算除了leaq指令，均会影响条件码寄存器
  2. CMP S1, S2: 等价于S2 - S1
    • 行为和SUB相同，但是仅设置条件码寄存器
  3. TEST S1, S2: 等价于S2 & S1
    • 行为和AND相同，但是仅设置条件码寄存器
    • 例：TEST %rax, %rax测试%rax的正负性

3.5.3. 访问条件码

条件码寄存器不能通过名字直接访问，只能间接访问。访问条件码有下面三种方式

  • SET指令: 根据条件码的某种组合将一个字节设置为0或者1
  • 条件跳转到程序的某个其他部分
  • 有条件传送数据

SET指令

  • sete: set when equal
  • setne
  • sets: set when signed
  • setns
  • setg: set when great
    • 测试有符号大于
  • setge
  • setl: set when less
  • setle
  • seta: set when above
    • 测试无符号大于
  • setae
  • setb: set when below
    • 测试无符号小于
  • setbe

有符号测试和无符号测试的实现

  • 本质上通过条件码寄存器的组合实现
  • 测试有符号比较
    • 例：测试有符号小于
      • OF = 0无溢出时，SF = 1表明小于，SF = 0表明大于等于
      • OF = 1有溢出时，若负溢出则表明小于，若正溢出则表明大于，因此SF = 0表明小于，SF = 1 表明大于
    • 因此，setl由OF和SF的异或值获得，其它有符号测试的结果基于OF^SF和ZF的其它组合
  • 测试无符号比较
    • 当a - b < 0时，CF为1。因此无符号比较通过

例：计算a < b的结果

1
2
3
4
5
comp:
  comq %rsi, %rdi
  setl %al
  movzbl %al, %eax
  ret

上面代码利用了”生成四字节的指令会将高位四字节清零”的规则。

3.5.4. 跳转指令

  • jmp无条件跳转指令
    • 直接跳转: 跳转目标作为指令的一部分编码给出
    • 间接跳转: 跳转目标从寄存器或内存位置读出
      • 以寄存器%rax中的值作为跳转目标：jmp *%rax
      • 以寄存器%rax指向的内存中的值为跳转目标：jmp *(%rax)
  • jmp Label
  • jmp *Operand
  • je Label
  • jne Label
  • js Label
  • jns Label
  • jg Label
  • jge Label
  • jl Label
  • jle Label
  • ja Label
  • jae Label
  • jb Label
  • jbe Label

跳转指令的编码

  • PC相对地址：编码为目标地址与跳转指令后一条指令的地址之差
  • 绝对地址

3.5.5. 条件传送指令

源寄存器或内存地址S -> 目的寄存器R

  • cmov S, R
  • cmovne S, R
  • cmovs S, R
  • cmovns S, R
  • cmovg S, R
  • cmovge S, R
  • cmovl S, R
  • cmovle S, R
  • cmova S, R
  • cmovae S, R
  • cmovb S, R
  • cmovbe S, R

注意:

  • 条件传送指令不支持单字节的传送。
  • 由于目的地址一定是寄存器，因此汇编器能够从目标寄存器名推断出操作数长度，因此不需要像无条件传送一样显示给出操作数长度。

3.6. 条件分支的翻译

3.6.1. 基于条件跳转实现

if-else语句

if-else语句当不满足条件表达式时会发生跳转，因此会被翻译为

1
2
3
4
5
6
7
8
  t = expr
  if (!t)
    goto false
  then-statement
  goto done;
false:
  else-statement
done:

3.6.2. 基于数据的条件传送实现

除了条件传送，另一种实现条件操作的方法是计算条件操作的两种结果，然后根据条件是否满足从中选取一个。注意：仅在有限情况下能使用这种方法。

使用条件传送没有分支预测失败的开销，更符合现代处理器的性能特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long absdiff(long x, long y)
{
  long result;
  if (x < y)
    result = y - x;
  else
    result = x - y;
  return result;
}

// 编译结果
absdiff:
  movq %rsi, %rax
  subq %rdi, %rax
  movq %rdi, %rdx
  subq %rsi, %rdx
  cmpq %rsi, %rdi
  cmovge %rdx, %rax
  ret
  • 如果另一个分支会导致错误或副作用则不能使用条件传送
  • 如果两个分支均需要耗费大量计算，条件传送也不总是能提高性能

3.7. 循环语句的翻译

3.7.1. do-while

1
2
3
4
5
loop:
  body-statement
  t = test-expr;
  if (t)
    goto loop;

3.7.2. while

-Og时的翻译结果

1
2
3
4
5
6
7
  goto test;
loop:
  body-statement
test:
  t = test-expr;
  if (t)
    goto loop;

-O1时的翻译结果，guarded-do翻译

1
2
3
4
5
6
7
8
9
t = test-expr;
if (!t)
  goto done;
loop:
  body-statement
  t = test-expr;
  if (t)
    goto loop
done:

3.7.3. for-loop

for循环等价于

1
2
3
4
5
init-expr
while (test-expr) {
  body-statement
  update-expr;
}

因此也有两种翻译方式。

3.8. switch语句的翻译

  • switch语句根据一个整数值进行多重分支(multiway branching)，借助跳转表实现
    • 跳转表：数组，每一个表项是一个代码段的地址，整数值作为索引映射到某个代码段。
    • 相比于if-else的优势: 通过跳转表执行多重分支的时间和分支数量无关。不论哪个代码块均只需一次跳转表引用。
    • 当分支较多，且值的范围跨越比较小时，GCC会使用跳转表翻译switch语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void *jt[7] = {
  &&loc_A, &&loc_def, &&loc_B, &&loc_C, ...
}
if (index > 6)
  goto loc_def;
goto *jt[index]

loc_A:
  body
  goto done;
loc_B:
  body
  /* fall through */
loc_C:
  body
  goto done;
loc_def:
  body
done:

汇编实现：

  • 无符号比较，索引超过跳转表范围，直接进入default
  • 其余情况，根据索引跳转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
my_switch:
movq %rdx, %rcx
cmpq $6, %rdi     # x - 6
ja .L8            # use default
jmp *.L4(,%rdi,8) # goto *Jtab[x]

.L3:
 # body
ret
.L5:
 # body
ret
...

# jump table
.section .rodata
.align 8
.L4:
.quad .L8 # x = 0
.quad .L3 # x = 1
.quad .L5 # x = 2
.quad .L9 # x = 3
.quad .L8 # x = 4
.quad .L7 # x = 5
.quad .L7 # x = 6

4. 过程调用的实现

过程调用包括下面三个机制：

  • 控制转移: 程序计数器的维护
  • 传递数据: 参数传递
  • 分配和释放内存: 栈内存的维护

假设函数P调用函数Q，栈空间的布局应当如下：

stack-layout.png

4.1. 控制转移

  • 进入调用
    • 压入返回地址: 调用指令的下一条指令的地址应当压入当前栈帧中
    • 设置pc: 程序计数器应当设置为调用的起始地址
  • 调用返回
    • 弹出返回地址: 从栈中弹出返回的地址
    • 设置pc: 设置程序计数器为弹出的地址

相关指令

  • call Label
  • call *Operand
  • ret

注意到call和ret分别包含了pushq和popq的动作。

4.2. 数据传递

  • x86-64通过寄存器功能传递6个参数
大小 1 2 3 4 5 6
64位 %rdi %rsi %rdx %rcx %r8 %r9
32位 %edi %esi %edx %ecx %r8d %r9d
16位 %di %si %dx %cx %r8w %r9w
8位 %dil %sil %dl %cl %r8b %r9b

注：若有更多参数，则应逆序压入栈。例如参数8位于8(%rsp)，参数7位于(%rsp)。

4.3. 栈上的局部存储

对于下面这些情况，局部数据需要放在内存中：

  • 寄存器不足以存放所有本地数据
  • 对一个局部变量使用&，改变量需要一个内存地址
  • 对数组或结构体局部变量，需要能够通过数组或结构引用访问到

注：需要存储在栈上的变量按照声明顺序依次放/压入栈中。例如对于x1，x2，x3，x4，则x1内存地址在上，x4内存地址在线。

4.4. 寄存器的局部存储

寄存器组被所有过程共享，为了确保被调用过程不会覆盖调用过程之后会使用的寄存器，x86-64遵循如下惯例：

  • 被调用者保存寄存器：%rbx, %rbp 和 %r12 ~ %r15
    • 不使用这些寄存器
    • 把原始值压入栈中，并在返回前弹出栈
  • 调用者保存寄存器: 除%rsp和被调用者保存的之外的其它的寄存器

4.5. 小结

过程调用抽象保证了每次函数调用都有

  • 私有的信息（返回地址、被调用者保存寄存器的值）
  • 独立的局部变量存储栈空间