CSAPP 第三章：Machine-Level Representation of Programs

1. 程序编码 (Program Encoding)

编译过程：
- C 源代码 → 编译器 (gcc) → 汇编代码 (.s)
- 汇编器 → 机器码 (.o)
- 链接器 → 可执行文件
指令集架构 (ISA, Instruction Set Architecture)：
- ISA 定义了 CPU 可以理解的 指令格式、寄存器、寻址方式。
- 常见 ISA：
  - x86 (x86-64) → Windows / Linux 主流
  - ARM → 移动设备（iPhone、Android），Apple M1/M2 (macOS)
  - RISC-V → 新兴的开源架构，HarmonyOS

📌 程序在机器级就是 指令字节序列，CPU 按 ISA 执行。

2. 数据格式与寄存器 (Data Formats & Registers)

整数大小：

char：1B
short：2B
int：4B
long (x86-64)：8B
pointer：8B

x86-64 整数寄存器：

通用寄存器 (16 个)：
%rax, %rbx, %rcx, %rdx, %rsi, %rdi, %rsp, %rbp, %r8 ~ %r15

不同宽度：

64 位：%rax
32 位：%eax
16 位：%ax
8 位：%al

寻址方式总结

寻址方式	汇编写法	含义	示例
立即数寻址	`$Imm`	常量立即数	`movq $5, %rax` → rax=5
寄存器寻址	`%rax`	直接取寄存器值	`movq %rbx, %rax`
绝对寻址 (直接内存地址)	`Imm`	取内存地址 Imm 的值	`movq 0x600000, %rax`
基址寻址	`(Rb)`	取 `[Rb]`	`movq (%rbx), %rax` → rax=*rbx
基址+位移寻址	`D(Rb)`	取 `[Rb + D]`	`movq 8(%rbp), %rax` → rax=*(rbp+8)
基址+变址寻址	`(Rb, Ri)`	取 `[Rb + Ri]`	`movq (%rbp,%rcx), %rax`
基址+变址+比例	`(Rb, Ri, S)`	取 `[Rb + Ri*S]`	`movq (%rbp,%rcx,4), %rax`
位移+基址+变址+比例	`D(Rb, Ri, S)`	取 `[D + Rb + Ri*S]`	`movq 8(%rbp,%rcx,4), %rax` → rax=A[rcx]

3. 指令类型 (Instruction Types)

数据传送 (Data Movement)

movq $5, %rax → 立即数 → 寄存器
movq %rax, %rbx → 寄存器 → 寄存器
movq (%rax), %rbx → 内存 → 寄存器

算术与逻辑运算 (Arithmetic & Logic)

addq %rbx, %rax → rax = rax + rbx
subq $1, %rax → rax = rax - 1

乘法 (mul / imul)：

imulq %rbx → rdx:rax = rax * rbx （有符号）
mulq %rbx → rdx:rax = rax * rbx （无符号）

除法 (div / idiv)：

idivq %rbx → (rdx:rax ÷ rbx)，商在 rax，余数在 rdx

📌 注意：乘除法用法特殊

默认操作数是 %rax
结果跨寄存器 %rdx:%rax

控制指令 (Control Transfer)

jmp label → 无条件跳转
call func → 调用函数
ret → 返回函数

补充：`call` 和 `ret` 的副作用

指令	主要动作	副作用
call func	- 将返回地址 (下一条指令地址) 压栈 → `push %rip` - 跳转到函数入口 `func`	- 修改栈指针 `%rsp` (减 8) - 保存返回地址在栈中
ret	- 从栈顶弹出返回地址 → `pop %rip` - 跳转回调用点	- 修改栈指针 `%rsp` (加 8) - 取回返回地址并恢复执行

📌 解释：

call 会把 下一条指令的地址 (return address) 压到栈里，以便函数执行完可以返回。
ret 会把这个返回地址弹出，并跳转回去。
所以函数调用栈是通过 %rsp 管理的，递归和函数嵌套都依赖这一机制。

4. 控制 (Control)

条件码 (EFLAGS 寄存器)：
- ZF (Zero Flag)：结果是否为 0
- SF (Sign Flag)：结果是否为负
- CF (Carry Flag)：无符号溢出
- OF (Overflow Flag)：有符号溢出
条件跳转
- je/jz → if ZF = 1
- jg → if (ZF=0 && SF=OF) → signed greater
示例：
cmpq %rbx, %rax # 比较 rax 和 rbx jg Greater # 若 rax > rbx 跳转
条件数据传送 (Conditional Move)：
通常，条件传送只用于简单的分支代码。
- 指令：cmovxx src, dst
- 原理：根据条件码是否成立，决定是否执行数据传送。
- 例子：
  
  cmovl %rbx, %rax # if (SF≠OF) → rax = rbx
- 优点：避免分支跳转，减少 分支预测失败 的开销。

5. 过程调用 (Procedures)

调用约定 (x86-64 System V ABI)：
- 参数传递
  - 前 6 个整型/指针参数：%rdi, %rsi, %rdx, %rcx, %r8, %r9
  - 浮点参数（double/float）：传递在 %xmm0 ~ %xmm7
  - 第 7 个及之后参数：依次压入栈中（右到左顺序）
- 返回值
  - 整型/指针：%rax
  - 浮点数：%xmm0
过程调用的栈结构 (Stack Frame)
栈高地址 → 低地址方向：

|-----------------|  ← 高地址
| 参数 n+         |  （溢出参数）
|-----------------|
| 返回地址 (ret)  |  ← call 指令压入
|-----------------|
| 前一帧的 %rbp   |  ← 保存旧基址
|-----------------|
| 局部变量        |
| 临时空间        |
|-----------------|  ← %rsp 栈顶

📌 函数调用过程

caller（调用者）
- 把参数放到寄存器或栈
- call func → 压返回地址到栈，跳转
callee（被调函数）
- 建立新栈帧
  1
  2
  3
  push %rbp mov %rsp, %rbp sub $N, %rsp # 为局部变量留空间
- 保存需要保护的寄存器（callee-saved）
- 执行函数体
返回
- 恢复被保存的寄存器
- 销毁局部栈帧：leave = mov %rbp, %rsp; pop %rbp
- 返回：ret（弹出返回地址，跳回调用点）

Caller / Callee 寄存器保存约定

Caller-saved (易失性寄存器，调用者负责保存)：
%rax, %rcx, %rdx, %rsi, %rdi, %r8 ~ %r11
（如果调用者需要这些寄存器的值，必须在调用前保存，返回后恢复）
Callee-saved (非易失性寄存器，被调函数必须恢复)：
%rbx, %rbp, %r12 ~ %r15
（函数进入时如果要用这些寄存器，必须先保存，返回前恢复）

📌 栈对齐规则

System V ABI 要求：函数调用时 %rsp 必须是 16 字节对齐的
原因：SIMD 指令（如 SSE、AVX）要求 16B 对齐
常见现象：编译器会在函数栈帧里插入 padding，让 %rsp 保持对齐

分支和循环的例子

if 语句

if (x > y) {
    z = x;
} else {
    z = y;
}

    cmpq   %rsi, %rdi       # x : y
    jle    .L_else
    movq   %rdi, %rdx       # z = x
    jmp    .L_done
.L_else:
    movq   %rsi, %rdx       # z = y
.L_done:

while 循环

while (i < n) {
    sum += a[i];
    i++;
}

.L_top:
    cmpq   %rsi, %rdi
    jge    .L_done
    movq   (%rdx,%rdi,8), %rax
    addq   %rax, %rcx
    incq   %rdi
    jmp    .L_top
.L_done:

for 循环

1
2
3

for (i = 0; i < n; i++) {
    sum += a[i];
}

    movq   $0, %rdi
.L_top:
    cmpq   %rsi, %rdi
    jge    .L_done
    movq   (%rdx,%rdi,8), %rax
    addq   %rax, %rcx
    incq   %rdi
    jmp    .L_top
.L_done:

do-while 循环

do {
    sum += a[i];
    i++;
} while (i < n);

.L_body:
    movq   (%rdx,%rdi,8), %rax
    addq   %rax, %rcx
    incq   %rdi
    cmpq   %rsi, %rdi
    jl     .L_body

switch-case 示例

int foo(int x) {
    int y;
    switch(x) {
        case 0:
            y = 10;
            break;
        case 1:
            y = 20;
            break;
        case 2:
            y = 30;
            break;
        default:
            y = 40;
            break;
    }
    return y;
}

    cmpq    $2, %rdi          # compare x with max case (2)
    ja      .L_default        # if x > 2, jump to default
    jmp     *.L_jump_table(,%rdi,8)  # indirect jump via jump table

.L_case0:
    movq    $10, %rax
    jmp     .L_done

.L_case1:
    movq    $20, %rax
    jmp     .L_done

.L_case2:
    movq    $30, %rax
    jmp     .L_done

.L_default:
    movq    $40, %rax

.L_done:

跳转表 (Jump Table)

编译器会生成一个 连续的地址表，表中每个元素指向对应 case 标签的汇编地址。
jmp *.L_jump_table(,%rdi,8) 的意思：
1. %rdi = switch 的变量 x
2. 表中每个元素占 8 字节（64 位地址）
3. 根据 x 的值直接跳转到对应 case 标签
优点：
- 常量 case 值连续 → O(1) 跳转
- 不用一条条 cmp + jmp 比较
默认情况：
- 如果 x 超过最大 case，跳到 .L_default

switch-case 示例

int foo(int x) {
    int y;
    switch(x) {
        case 0:
            y = 10;
            break;
        case 1:
            y = 20;
            break;
        case 2:
            y = 30;
            break;
        default:
            y = 40;
            break;
    }
    return y;
}

    cmpq    $2, %rdi          # compare x with max case (2)
    ja      .L_default        # if x > 2, jump to default
    jmp     *.L_jump_table(,%rdi,8)  # indirect jump via jump table

.L_case0:
    movq    $10, %rax
    jmp     .L_done

.L_case1:
    movq    $20, %rax
    jmp     .L_done

.L_case2:
    movq    $30, %rax
    jmp     .L_done

.L_default:
    movq    $40, %rax

.L_done:

CSAPP 第三章：Machine-Level Representation of Programs

http://example.com/2025/09/04/chapter-machinecode/

Author

Newtown

Posted on

September 4, 2025

Licensed under

CSAPP bomb lab Previous

德语A1-Einheit4整理 Next

CSAPP 第三章：Machine-Level Representation of Programs

1. 程序编码 (Program Encoding)

2. 数据格式与寄存器 (Data Formats & Registers)

整数大小：

x86-64 整数寄存器：

寻址方式总结

3. 指令类型 (Instruction Types)

数据传送 (Data Movement)

算术与逻辑运算 (Arithmetic & Logic)

控制指令 (Control Transfer)

补充：call 和 ret 的副作用

4. 控制 (Control)

5. 过程调用 (Procedures)

📌 函数调用过程

Caller / Callee 寄存器保存约定

📌 栈对齐规则

分支和循环的例子

if 语句

while 循环

for 循环

do-while 循环

switch-case 示例

跳转表 (Jump Table)

switch-case 示例

补充：`call` 和 `ret` 的副作用