Lecture 4: 机器级编程 II——控制流 (Machine Programming II: Control Flow)

目录 · ← l3 · l5 →

Lecture 4: 机器级编程 II——控制流 (Machine Programming II: Control Flow)

讲义对应：CMU 15-213 Lecture 4 — Machine Programming (Part II)（素材：F25-04-machine-beta.txt） 教材对应：CS:APP3e 第 3 章 3.6–3.7（控制流、过程基础） 关联 Lab：L2 Bomb Lab（Defusing a Binary Bomb）

4.1 概述

上一讲（Lecture 3）建立了”寄存器是名词、指令是动词”的机器级世界观：数据在寄存器与内存之间搬运，地址由 D(Rb,Ri,S) 寻址模式计算。但程序不只是直线执行——它要判断、要重复、要跳转。本讲回答一个核心问题：C 语言里的 if、while、for、switch，究竟是如何只用”条件码 + 跳转”这两样东西实现的？

答案是：CPU 内部有一组隐式的条件码（condition codes），算术/逻辑指令运行后顺手把结果的性质（是否为零、是否有进位、是否溢出、符号位）记录在一个特殊寄存器 RFLAGS 里；cmp 与 test 专门负责只设置条件码而不保存结果；set 指令把条件码组合翻译成 0/1 字节；jX 指令依据同一组条件码决定下一条指令的地址（修改 %rip）。一切控制流都是 goto——这是理解本讲的第一把钥匙。

讲义在本讲还顺带展开了过程（procedures）的动机与 x86-64 栈的 push/pop 语义，为 Lecture 5 的完整调用约定做铺垫；本笔记重点覆盖 3.6–3.7 的控制流部分，栈帧细节详见 Lecture 5。

4.2 核心概念与底层机制图解

4.2.1 处理器状态与条件码（Condition Codes）

• 定义与目的：条件码是 4 个单比特状态位，位于 RFLAGS 寄存器中，记录最近一次算术或逻辑运算结果的性质。它们是”硬件给程序员留下的免费副产品”——addq 除了算和，还顺手告诉你结果是不是 0。
• 直观解释：把它想成考场里的自动判卷灯。每做完一道运算题，墙上四盏灯自动亮/灭：ZF 亮表示”答案是零”，SF 亮表示”答案是负数”，CF 亮表示”无符号运算越界了”，OF 亮表示”有符号运算越界了”。你不需要重新看答案，只要抬头看灯。
• 底层机制图解：

        RFLAGS 低 16 位的布局（本讲只关心 OF/SF/ZF/CF 四位）
   bit: 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
       | 0| 0| 0| 0|OF| 0| 0| 0|SF|ZF| 0|AF| 0|PF| 0|CF|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                    bit11    bit7 bit6    bit4    bit2  bit0

   名字   英文全称                含义（以 a - b 的结果 t 为例）
   ----   ---------------------   ---------------------------------------------
   CF    Carry Flag              t 在"无符号"意义下发生进位/借位（最高位向外进 1）
   ZF    Zero Flag               t == 0（常用 testq %rax,%rax 单独探测）
   SF    Sign Flag               t 的最高位为 1，即"被解释为有符号数是负数"
   OF    Overflow Flag           t 在有符号意义下溢出（两正得负、或两负得正）

   设置者：add/sub/imul/and/or/xor/shl/shr/cmp/test 等（大部分算术逻辑指令）
   不设置者：mov 系列、lea —— 讲义特别强调 "lea 不碰条件码"，
             这正是编译器爱用 lea 做纯算术的原因：不会破坏已有的比较结果。

• 与机器码/硬件的对应：条件码由 ALU 直接产生（加减法器的进位链输出、结果的全零检测、符号位复制），在同一个时钟周期内写回标志寄存器，不额外消耗指令。这正是 cmp 高效的原因：它只做减法、不写回目的寄存器。
• 补充说明：讲义本讲只有一页”Conditional reminder slide”，上述 FLAGS 位编号与”mov/lea 不设条件码”的细节依据 Lecture 3 幻灯片与课堂活动 machine-control.txt 补齐。

4.2.2 cmp 与 test

• 定义与目的：为比较而生的两条”只设标志、不留结果”的指令。
• cmpq b, a：计算 a - b（AT&T 顺序是源在前、目的在后，所以 cmpq %rsi, %rdi 算的是 %rdi - %rsi），只设条件码，a 与 b 都不改变。
• testq b, a：计算 a & b，只设条件码，且只对 SF/ZF 有意义的解释成立（CF/OF 被清零）。
  • 最常见用法 testq %rax, %rax：同一个寄存器与自己与，只影响 ZF/SF，等价于”%rax 是零吗？是负数吗？”，比 cmpq $0, %rax 编码更短。
  • 次常见用法 testq %rX, %rY：探测两个寄存器的 1 位是否有交集（如位图中的”权限掩码”判断）。
• 与机器码/硬件的对应：cmp 与 sub、test 与 and 共享同一条数据通路，区别仅在于是否写回目的操作数。

4.2.3 set 指令族：把条件码变成 0/1

• 定义与目的：setX 依据条件码把目的操作数的最低字节写成 0 或 1，其余 7 字节不变。它让关系表达式（如 x > y）可以作为值参与运算，而不必产生分支。
• 直观解释：如果说 jX 是”看灯决定走哪条路”，setX 就是”看灯在纸上写 0 或 1”。二者读的是同一组灯。
• 关键陷阱——有符号用 g/l，无符号用 a/b：

   +--------+-----------------------+---------------+-----------------+----------+
   | C 关系 | 条件码（比较 a-b 后） | set 指令      | 条件跳转        | 类别     |
   +--------+-----------------------+---------------+-----------------+----------+
   | a == b | ZF                    | sete / setz   | je / jz         |          |
   | a != b | ~ZF                   | setne / setnz | jne / jnz       |          |
   | a < 0  | SF                    | sets          | js              |          |
   | a >= 0 | ~SF                   | setns         | jns             |          |
   +--------+-----------------------+---------------+-----------------+----------+
   | a > b  | ~(SF^OF) & ~ZF        | setg / setnle | jg / jnle       | signed   |
   | a >= b | ~(SF^OF)              | setge / setnl | jge / jnl       | 有符号   |
   | a < b  | SF^OF                 | setl / setnge | jl / jnge       | g / l    |
   | a <= b | (SF^OF) OR ZF         | setle / setng | jle / jng       |          |
   +--------+-----------------------+---------------+-----------------+----------+
   | a > b  | ~CF & ~ZF             | seta / setnbe | ja / jnbe       | unsigned |
   | a >= b | ~CF                   | setae / setnb | jae / jnb (jnc) | 无符号   |
   | a < b  | CF                    | setb / setnae | jb / jnae (jc)  | a / b    |
   | a <= b | CF OR ZF              | setbe / setna | jbe / jna       |          |
   +--------+-----------------------+---------------+-----------------+----------+

   记忆法："signed 用 g(reater)/l(ess)" —— g 与 l 字母形似 9 与 1，都是"带正负号的数字"；
           "unsigned 用 a(bove)/b(elow)" —— 只谈在数轴上位次高低，不谈正负。

• 与机器码/硬件的对应：setX %al 只写 1 字节，因此编译器几乎总要补一条 movzbl %al, %eax 把高位清零，才能得到一个合法的 int 返回值。若忘记清零，%rax 高位残留的垃圾会污染返回值——这是 Bomb Lab 中常见的”看起来对却返回值不对”的误读来源。

4.2.4 跳转指令：直接跳转与间接跳转

• 直接跳转（direct jump）：目的地在指令里写成标号，汇编器/链接器算出相对偏移。如 jmp .L8、je .L4。机器码里通常是 1–4 字节的相对位移（相对于下一条指令），这样代码可以整体重定位。
• 间接跳转（indirect jump）：目的地从寄存器或内存中读出，语法上以 * 标记：
  • jmp *%rax —— 跳到 %rax 里的地址；
  • jmp *(%rax) —— 从内存读出一个 8 字节地址再跳（函数指针调用就是这样）；
  • jmp *.L4(,%rdi,8) —— 跳到跳转表 .L4 的第 %rdi 项（switch 的实现）。
• 与硬件的对应：条件跳转的”跳或不跳”在流水线里由分支预测器（branch predictor）提前猜测；猜错就要冲刷流水线（branch misprediction），代价通常十几到二十个周期。这直接引出下一节的 cmov。

4.2.5 if-else 的编译：把条件取反，先跳到 else

• 定义与目的：C 的 if (Test) Then else Else 翻译成汇编时，编译器通常不按源码顺序生成，而是遵循一条被 CS:APP 称为”教科书式”的模板：

   C 源码                       翻译后的控制流（条件取反，先跳 else）
   ------------------------     -------------------------------------------
   if (Test)                    <求值 Test，设置条件码>
       Then                     j<Test 的反> <else>     ; 条件为假才跳走
   else                         <Then 的代码>
       Else                     jmp <done>              ; then 结束，跳过 else
                                <else>:
                                <Else 的代码>
                                <done>:

• 为什么要取反：Test 为真时不跳转，可以顺着流水线继续执行 then 分支——这既保持了指令的物理顺序贴近源码顺序，又避免了额外的无条件跳转。若条件为假，一次跳转直接到 else。
• 为什么 then 分支末尾要多一条 jmp done：否则 then 的代码会”贯穿”进 else。switch 的 fall-through 是语言特性，if-else 的贯穿则是 bug，编译器必须显式阻断。
• 直观解释：像地铁闸机。真条件就”直接往前走”，假条件才”拐到另一条道”；两条道走完后都要汇合到 done。
• 与机器码/硬件的对应：j<Test 的反> 是前一节条件码组合表的直接应用。若 Test 是 x < y（有符号），取反就是 x >= y，即 jge；若 Test 是 x == 0，取反就是 jne。乱序、嵌套、else if 链都只是这个模板的递归套用。

4.2.6 条件传送 cmov：用数据流换掉控制流

• 定义与目的：cmovX Src, Dest 在条件成立时才把 Src 拷进 Dest，否则保持不变。与 jX 读同一组条件码，但不改变 %rip——没有分支，也就没有预测失败。
• 直观解释：分支像路口问路（问错要掉头重走）；cmov 像提前把两条路的结果都拿到手里，再挑对的那份。代价是：两条路的结果都要先算出来。
• 两条铁律（本讲最容易被忽视的考点）：
  1. cmov 的两个候选值都会被执行求值，因此”先算再选”必须是无副作用、无非法访存的；
  2. 如果某个候选值的计算本身可能崩溃（例如解引用可能为 NULL 的指针 *p），编译器绝不能生成 cmov，只能保留真实分支。这正是 CS:APP 经典例子 xp ? *xp : 0 不能编译成 cmov 的原因。
• 为什么 GCC 在 -O1 以上偏爱 cmov：可预测性差的随机分支会不断预测失败，而 cmov 把控制相关（control dependence）转成数据相关（data dependence），执行时间恒定。代价是两条路径的计算都进关键路径，因此当分支高度可预测（如循环回边）或某条路径很昂贵时，分支反而更快。
• 与机器码/硬件的对应：cmovX 后缀与 setX/jX 共用同一张条件码表——cmove、cmovne、cmovs、cmovg/cmovl（有符号）、cmova/cmovb（无符号）等。硬件上就是给寄存器写口加一个条件使能位，不产生任何分支。

   分支版本（-Og：真分支）          cmov 版本（-O1：无分支）
+------------------------------+    +------------------------------+
| cmpq %rsi,%rdi              |     | movq %rsi,%rdx              |
| jge .L2   <- 可能预测失败   |     | subq %rdi,%rdx  ; y-x       |
| movq %rsi,%rax              |     | movq %rdi,%rax              |
| subq %rdi,%rax  ; y-x       |     | subq %rsi,%rax  ; x-y       |
| ret                         |     | cmpq %rsi,%rdi              |
| .L2:                        |     | cmovl %rdx,%rax ; 条件选择  |
|   movq %rdi,%rax            |     | ret                         |
|   subq %rsi,%rax ; x-y      |     +------------------------------+
|   ret                       |
+------------------------------+

4.2.7 循环的三种翻译与 guarded-do

循环的四个组成部分是初始化（Init）、测试（Test）、更新（Update）、循环体（Body）。讨论循环的 goto 形态时只需问一句：回跳（backward goto）在哪里？

• do-while：最自然的形态，循环体在前、测试在后，天然就是”先执行一次再回跳”，无需额外保护。
• while 的两种翻译：
  • 跳转到中间（jump to middle）：goto test; 开头，体后是 test: if (Test) goto loop;。-Og 采用，因为它逐字对应源码，便于调试。
  • guarded-do（转成 do-while）：先 if (!Test) goto done; 做一次入口守卫，然后把体与测试拼成 do-while 的好处是把两个跳转（一个是入口跳转、一个是删除冗余跳转）压缩成一个底部条件跳转，-O1 采用。
• for：先机械改写为 Init; while (Test) { Body; Update; }，再套用上面的 while 翻译。guarded-do 优化之所以安全，是因为 for 的初值测试在编译期常常可判定（如 i=0; i<64 恒真），入口守卫可以被直接删掉，于是 for 得到一个纯 do-while 结构。

4.2.8 switch 的编译与跳转表

switch 的编译有两套策略，取决于 case 值是否稠密：

1. 跳转表（jump table）：case 值落在稠密区间 [0, n-1] 时，编译器在 .rodata 段生成一张函数指针数组，用 jmp *.L4(,%rdi,8) 一次间接跳转完成分派——$O(1)$，无比较链。
2. 比较链 / 判定树（if-else chain）：case 稀疏时退化为若干次 cmp + 条件跳转。现代 GCC 还会对”连续小区间”用先减后无符号比较（subq $5,%rdi; cmpq $1,%rdi; ja）一次判掉 x==5 \|\| x==6。

   跳转表在内存中的布局（本笔记实测：gcc 12.2 -Og，grade() 函数）

   .text: grade 函数（编译器生成）
   +----------------------------------+
   | cmpq $0x7,%rdi    ; 上界检查     |
   | ja   .L2          ; x>7 走默认   |
   | jmpq *0x402008(,%rdi,8)          |
   +----------------------------------+
              |                           .rodata: 跳转表（基址 .L4 = 0x402008）
              |                           +--------------------------------------+
              |  地址 = 表基址 .L4 + x*8  | 表项地址    目标标签         返回值  |
              |                           +--------------------------------------+
              +------------------->       | 0x402008    .L11 (x=0)           10  |
                                          | 0x402010    .L12 (x=1)           20  |
                                          | 0x402018    .L9  (x=2)           30  |
                                          | 0x402020    .L8  (x=3)           40  |
                                          | 0x402028    .L7  (x=4)           50  |
                                          | 0x402030    .L6  (x=5)           60  |
   scale = 8：每个表项是一个              | 0x402038    .L5  (x=6)           70  |
   64 位代码地址，正好 8 字节。           | 0x402040    .L3  (x=7)           80  |
                                          +--------------------------------------+
   为什么放 .rodata？表在运行期只读，
   既防改写，也便于多进程共享物理页。

• 上界检查是必需的：jmp *.L4(,%rdi,8) 不做边界检查，负数或超界索引会读到表外内存并跳到任意地址。因此编译器一定先 cmpq $n-1,%rdi; ja default——注意这里用 无符号 ja，因为无符号比较把负索引也归入”大于”，一次比较同时挡掉负数与超界。
• 补充说明：讲义提到”较新的编译器会把跳转表从 8 字节地址改为 4 字节偏移“（rip + 表基址 + 偏移）；本笔记用 gcc -Og -fPIC 复现了该形态（4.3.3）。

4.3 代码示例与底层机制分析

4.3.1 示例一：关系表达式、set 与 if-else 分派

/* setdemo.c —— 用 gcc -Og -Wall -std=c11 -g -o setdemo setdemo.c 验证通过 */
#include <stdio.h>

int gt(long x, long y)                      { return x > y;  }  /* 有符号 */
int lt_u(unsigned long x, unsigned long y)  { return x < y;  }  /* 无符号 */

long classify(long x) {                     /* if-else 的教科书形态 */
    if (x < 0) return -1;
    else       return 1;
}

int main(void) {
    printf("%d %d | %d %d | %ld %ld\n",
           gt(5, 3), gt(3, 5), lt_u(1, 0), lt_u(0, 1),
           classify(-3), classify(3));
    return 0;   /* 输出：1 0 | 0 1 | -1 1 */
}

【代码做什么？】 gt 用有符号比较判断 x > y，返回 int 0/1；lt_u 语义相同形状但参数是 unsigned long，走无符号比较；classify 是课本最简 if-else。

【底层机制透视】 gt 与 lt_u 都不产生分支：比较指令只设条件码，setX 把条件码抄成 1 字节，movzbl 补零成完整的 int。classify 则相反——两条臂都只是常量，编译器选择”跳转”而不是”求值+选择”，因为常量不需要计算，跳转更省。

【与汇编 / 硬件的对应】（真实 gcc -Og -S 输出）

gt:
	cmpq	%rsi, %rdi        # 算 x - y，只设条件码
	setg	%al               # 有符号 >  → %al = 0/1
	movzbl	%al, %eax         # 把低字节零扩展成 32 位 int
	ret

lt_u:
	cmpq	%rsi, %rdi
	setb	%al               # 无符号 <  → 注意是 b 不是 l
	movzbl	%al, %eax
	ret

classify:
	testq	%rdi, %rdi        # x 是零吗？是负数吗？
	js	.L6               # SF=1（负数）就跳到 else 分支
	movl	$1, %eax          # then 分支：先做
	ret
.L6:
	movq	$-1, %rax         # else 分支
	ret

再看”两条臂都要汇合”的形态（真实 gcc -Og -S 输出）。把 if-else 的结果赋给变量、之后再统一处理，就出现了 4.2.5 节那个 done: 汇合点：

/* ifelse.c —— gcc -Og -Wall -std=c11 -g -o ifelse ifelse.c 验证通过，输出 "601 -6 | 602 -5" */
#include <stdio.h>

__attribute__((noinline)) long slow_then(long x) { return x * 3 + 1; }
__attribute__((noinline)) long slow_else(long x) { return x / 2 - 7; }

long pick(long x) {           /* 尾调用版：return 直接就是函数调用 */
    if (x > 100) return slow_then(x);
    else         return slow_else(x);
}

long pick2(long x) {          /* 非尾调用：两条臂汇合到同一出口 */
    long r;
    if (x > 100) r = slow_then(x);   /* Test: x > 100 */
    else         r = slow_else(x);
    return r + 1;                    /* <done> 汇合点 */
}

int main(void) {
    printf("%ld %ld | %ld %ld\n", pick(200), pick(2), pick2(200), pick2(2));
    return 0;
}

# -------- 尾调用版 pick：两条臂各自 ret，没有 done 汇合点 --------
pick:
	cmpq	$100, %rdi
	jle	.L4                  # 条件取反：x <= 100 跳到 else（4.2.5 的模板）
	call	slow_then            # then 分支：真条件顺行，不再跳转
	ret
.L4:                             # <else>:
	call	slow_else
	ret

# -------- 非尾调用版 pick2：必须保留 jmp 才能汇合到 done --------
pick2:
	cmpq	$100, %rdi
	jle	.L7
	call	slow_then
.L8:                             # <done>:
	addq	$1, %rax
	ret
.L7:                             # <else>:
	call	slow_else
	jmp	.L8                  # else 结束后跳向汇合点

对比两段真实产物可以看出：尾调用版里 then 与 else 各自 ret，没有共同的 done 标签；而非尾调用版多出一条 jmp .L8——它存在的唯一理由就是阻断 else 代码的贯穿，并在 done 处汇合。这正是 4.2.5 节模板中那条 jmp <done> 的实证。

【实测验证】 把 int gt/int lt_u 换成 int c_s(long a,long b){return a<0;}，gcc -Og 并不用 sets，而是 shrq $63,%rdi; movq %rdi,%rax——这提示”条件码→set→零扩展”只是一种标准形态，优化器会做等价改写；读懂语义比背指令序列更重要。

4.3.2 示例二：三种循环与 guarded-do

/* loops.c —— gcc -Og / -O1 -Wall -std=c11 -g 验证通过，输出 "0 8 16" */
#include <stdio.h>

long pcount_do(unsigned long x) {           /* do-while：体在前，测试在后 */
    long result = 0;
    do { result += x & 0x1; x >>= 1; } while (x);
    return result;
}

long pcount_while(unsigned long x) {        /* while */
    long result = 0;
    while (x) { result += x & 0x1; x >>= 1; }
    return result;
}

#define WSIZE 64
long pcount_for(unsigned long x) {          /* for：先改写成 while */
    long result = 0;
    for (unsigned i = 0; i < WSIZE; i++) result += (x >> i) & 0x1;
    return result;
}

int main(void) {
    printf("%ld %ld %ld\n",
           pcount_do(0), pcount_while(0xff), pcount_for(0x0f0f0f0fUL));
    return 0;
}

【代码做什么？】 三个函数都统计参数中 1 的个数（popcount），差别只在循环语法：do-while 至少执行一次；while 可能零次；for 把初始化/测试/更新三段写在一行。

【底层机制透视】 pcount_do 的汇编就是”体 + 底部条件回跳”，shrq %rdi 之后直接用 jne——因为 shrq 顺带设了 ZF，测试与移位合并成一条指令。pcount_while 在 -Og 下用”跳转到中间”，开头补一条 movl $0,%eax; jmp .L4。

【与汇编 / 硬件的对应】 gcc -Og 与 gcc -O1 的真实对比：

# ---------- gcc -Og：跳转到中间（jump to middle）----------
pcount_while:
	movl	$0, %eax
	jmp	.L4                  # 先跳到测试，再决定是否进入
.L5:
	movq	%rdi, %rdx
	andl	$1, %edx
	addq	%rdx, %rax
	shrq	%rdi
.L4:
	testq	%rdi, %rdi           # 测试
	jne	.L5                  # 回边
	ret

# ---------- gcc -O1：guarded-do（先守卫，再 do-while）----------
pcount_while:
	testq	%rdi, %rdi
	je	.L7                  # 入口守卫：x==0 直接返回 0
	movl	$0, %eax
.L6:
	movq	%rdi, %rdx
	andl	$1, %edx
	addq	%rdx, %rax
	shrq	%rdi
	jne	.L6                  # 底部回边，省掉顶部 test
	ret
.L7:
	movl	$0, %eax
	ret

# ---------- gcc -Og：pcount_for 的跳转到中间 ----------
pcount_for:
	movl	$0, %ecx
	movl	$0, %edx
	jmp	.L7
.L8:
	movq	%rdi, %rax
	shrq	%cl, %rax
	andl	$1, %eax
	addq	%rax, %rdx
	addl	$1, %ecx
.L7:
	cmpl	$63, %ecx            # i <= 63 即 i < 64
	jbe	.L8
	movq	%rdx, %rax
	ret

# ---------- gcc -O1：pcount_for 的 guarded-do ----------
pcount_for:
	movl	$0, %ecx
	movl	$0, %edx
.L10:
	movq	%rdi, %rax
	shrq	%cl, %rax
	andl	$1, %eax
	addq	%rdx, %rax
	movq	%rax, %rdx
	addl	$1, %ecx
	cmpl	$64, %ecx
	jne	.L10                # 入口守卫被完全优化掉（0<64 恒真）
	ret

【实测验证】 cmp 的两个比较点值得注意：-Og 用 cmpl $63,%ecx; jbe，-O1 改写成 cmpl $64,%ecx; jne——优化器把”上界 63 的闭区间”翻成”上界 64 的开区间＋不等比较”，这是归纳变量优化的常见副产品。

4.3.3 示例三：switch 的跳转表与稀疏退化

/* sw.c —— gcc -Og -Wall -std=c11 -g 验证通过，循环打印 0..7 的结果 */
#include <stdio.h>

long grade(long x) {                    /* case 0..7 稠密 → 触发跳转表 */
    switch (x) {
    case 0: return 10;  case 1: return 20;  case 2: return 30;  case 3: return 40;
    case 4: return 50;  case 5: return 60;  case 6: return 70;  case 7: return 80;
    default: return -1;
    }
}

long switch_eg(long x, long y, long z) { /* 讲义原例：case 稀疏 → 比较链 */
    long w = 1;
    switch (x) {
    case 1: w = y * z; break;
    case 2: w = y / z;          /* Fall Through，故意不 break */
    case 3: w += z; break;
    case 5:
    case 6: w -= z; break;
    default: w = 2;
    }
    return w;
}

int main(void) {
    for (long i = -1; i <= 8; i++) printf("%ld -> %ld\n", i, grade(i));
    printf("switch_eg(2,12,4) = %ld\n", switch_eg(2, 12, 4));
    return 0;
}

【代码做什么？】 grade 是均匀分布的稠密 switch；switch_eg 是讲义原例，含多重标签（5、6 共用一块）、贯穿（case 2 落入 case 3）、缺失标签（4 落 default）三种形态。

【内存布局 / 数据结构图解】 grade 的真实跳转表位于只读段。objdump -s -j .rodata 实测输出（为便于对齐，下面每行只摘两个 8 字节表项，省略行尾的 ASCII 注释列与后续的 printf 格式串）：

 .rodata
 402000  01000200 00000000   33114000 00000000   <- 前 8 字节是 _IO_stdin_used；
                                                     0x402008 起才是表：.L11 = 0x401133
 402010  65114000 00000000   39114000 00000000   <- x=1: 0x401165   x=2: 0x401139
 402020  3f114000 00000000   45114000 00000000   <- x=3: 0x40113f   x=4: 0x401145
 402030  4b114000 00000000   51114000 00000000   <- x=5: 0x40114b   x=6: 0x401151
 402040  57114000 00000000                       <- x=7: 0x401157

小端序（little-endian）在这里帮了大忙：33114000 00000000 从低地址往高地址读出的 8 字节即地址 0x0000000000401133。所以表在内存里看起来”数字是反的”。

【与汇编 / 硬件的对应】（真实输出）

grade:
	cmpq	$7, %rdi             # 上界检查
	ja	.L2                  # 无符号 ja：负数与 >7 都被挡到 default
	jmp	*.L4(,%rdi,8)        # 间接跳转：地址 = .L4 + x*8
	.section	.rodata
	.align 8
.L4:
	.quad	.L11                 # x = 0
	.quad	.L12                 # x = 1
	.quad	.L9                  # x = 2
	.quad	.L8                  # x = 3
	.quad	.L7                  # x = 4
	.quad	.L6                  # x = 5
	.quad	.L5                  # x = 6
	.quad	.L3                  # x = 7
	.text
.L11:
	movl	$10, %eax
	ret

switch_eg 在 -Og 下退化为判定树 + 区间技巧（真实输出，节选）：

switch_eg:
	movq	%rdx, %rcx
	cmpq	$3, %rdi
	je	.L20                 # x == 3 → w=1，再落入 merge
	jg	.L15                 # x > 3 → 处理 5/6/default
	cmpq	$1, %rdi
	je	.L16                 # case 1: imul
	cmpq	$2, %rdi
	jne	.L23                 # default: w = 2
	movq	%rsi, %rax
	cqto                         # 把 %rax 符号扩展到 %rdx:%rax（idiv 的被除数）
	idivq	%rcx                 # case 2: y/z
.L14:                            # merge:（case 2 贯穿进入 case 3）
	addq	%rcx, %rax           # w += z
	ret
.L23:
	movl	$2, %eax             # default
	ret
.L15:
	subq	$5, %rdi             # 把 5/6 平移到 0/1
	cmpq	$1, %rdi
	ja	.L24                 # 一次无符号比较同时排除负数与 >1
	movl	$1, %eax
	subq	%rdx, %rax           # w = 1 - z
	ret
.L16:
	movq	%rdx, %rax
	imulq	%rsi, %rax           # w = z * y
	ret
.L20:
	movl	$1, %eax             # case 3: w = 1
	jmp	.L14
.L24:
	movl	$2, %eax             # default（从 .L15 的区间判断溢出而来）
	ret

【实测验证】 用 gdb 直接读表（真实会话）：

$ gdb ./sw
(gdb) x/8xg 0x402008
0x402008:  0x0000000000401133  0x0000000000401165
0x402018:  0x0000000000401139  0x000000000040113f
0x402028:  0x0000000000401145  0x000000000040114b
0x402038:  0x0000000000401151  0x0000000000401157

第 0 项 0x401133 正是 grade+0xd（mov $0xa,%eax，即 return 10），与源码 case 0 吻合。这说明跳转表把”比较链”变成了”查表”：无论 x 取 0 还是 7，都只有 cmp+ja+jmp * 三条指令，耗时与 case 数量无关（$O(1)$）。另外两处值得记录：

• -O2 会把整张表删掉：grade 被识别为线性函数，编译成 leaq 5(%rdi,%rdi,4),%rax; addq %rax,%rax（即 10*x + 10）。跳转表只是优化器的一种选择，不是语义要求。
• -Og -fPIC 复现了讲义的”4 字节偏移表”：leaq .L4(%rip),%rdx; movslq (%rdx,%rdi,4),%rax; addq %rdx,%rax; jmp *%rax，表项是 .long .L11-.L4，体积减半且位置无关。

4.3.4 示例四：cmov 与分支的真实差异（本讲核心对照）

/* cmovdemo.c —— gcc -Og/-O1 -Wall -std=c11 -g 验证通过 */
#include <stdio.h>

long absdiff(long x, long y) {            /* 两条臂都是纯算术 → 可用 cmov */
    long result;
    if (x < y) result = y - x;
    else       result = x - y;
    return result;
}

long absval(long x) { return x < 0 ? -x : x; }

long cread(long *xp) { return xp ? *xp : 0; }   /* 不能 cmov：*xp 可能非法访存 */

long cread_alt(long *xp) {                /* 改写后两条臂都安全 → 可用 cmov */
    long zero = 0;
    if (!xp) xp = &zero;
    return *xp;
}

int main(void) {
    long v = 99;
    printf("%ld %ld | %ld %ld | %ld %ld %ld\n",
           absdiff(3, 7), absdiff(9, 7), absval(-5), absval(5),
           cread(&v), cread(NULL), cread_alt(NULL));
    return 0;   /* 输出：4 2 | 5 5 | 99 0 0 */
}

【代码做什么？】 absdiff 求差的绝对值；absval 求绝对值；cread 安全地读一个可能为 NULL 的指针；cread_alt 语义相同但把空指针改指向一个局部零变量。

【底层机制透视——两种编译产物的对比】（真实 gcc -S 输出）

# ===== absdiff @ -Og：真分支 =====
absdiff:
	cmpq	%rsi, %rdi
	jge	.L2                  # 分支：可能预测失败
	movq	%rsi, %rax
	subq	%rdi, %rax           # y - x
	ret
.L2:
	movq	%rdi, %rax
	subq	%rsi, %rax           # x - y
	ret

# ===== absdiff @ -O1：cmov =====
absdiff:
	movq	%rsi, %rdx
	subq	%rdi, %rdx           # 先算 y - x
	movq	%rdi, %rax
	subq	%rsi, %rax           # 再算 x - y
	cmpq	%rsi, %rdi
	cmovl	%rdx, %rax           # 只有 x<y 时才用第一份结果
	ret

# ===== absval @ -Og/@-O1：cmov 的紧凑形态 =====
absval:
	movq	%rdi, %rax
	negq	%rax                 # 先假设结果为 -x（negq 会设置 SF）
	cmovs	%rdi, %rax           # 若 -x 为负则取 x（这正是 x>0 的情形）
	ret

# ===== cread @ -O1：编译器拒绝 cmov，保留分支 =====
cread:
	movl	$0, %eax
	testq	%rdi, %rdi
	je	.L5                  # 必须短路：xp 为 NULL 时不能解引用
	movq	(%rdi), %rax
.L5:
	ret

# ===== cread_alt @ -O1：两臂都安全，于是生成 cmov =====
cread_alt:
	movq	$0, -8(%rsp)         # 栈上的 zero 变量
	leaq	-8(%rsp), %rax
	testq	%rdi, %rdi
	cmove	%rax, %rdi           # 若 xp==NULL，则改指向 &zero；无跳转
	movq	(%rdi), %rax
	ret

【内存布局 / 数据结构图解】 cread_alt 用栈上 8 字节（红色区域 red zone）换来一条无分支指令。注意 call 之后 %rsp 指向返回地址，-8(%rsp) 是它下方（更低地址）的 8 字节；movq $0,-8(%rsp) 只写内存，不改变 %rsp：

   高地址                                    ← 调用者的栈帧
   +---------------------------+
   |  ...（caller frame）      |
   +---------------------------+
   |  返回地址（call 压入）    |  <- %rsp 指向这里，全程不变
   +---------------------------+
   |  zero = 0（-8(%rsp)）     |  <- 红区；被 leaq 取地址，
   +---------------------------+     xp==NULL 时 %rdi 改指向这里
   低地址

【与汇编 / 硬件的对应】 两个事实直接来自讲义与课堂活动 machine-control.txt：

1. cmov 的候选值一定先被求值——absdiff @ -O1 里 y-x 和 x-y 两条 subq 都执行了，只是结果二选一。
2. cmov 不能被用来”跳过”危险的内存访问——cread 若错误地编译成 cmovq (%rdi),...，传入 NULL 就会段错误，程序语义被破坏。编译器必须保证：优化不得引入原程序不存在的异常。

这也给出了写代码的建议：想让 GCC 生成 cmov，就把两条臂都改写成”总是合法”的计算（如 cread_alt）。

4.4 实验关联：L2 Bomb Lab

Bomb Lab 是”控制流 + gdb”的实战考场：每个 phase 都靠 cmp/test 与 jX 决定”继续还是引爆”，正是本讲内容的直接应用。

第一步：定位函数。 bomb 的符号没有被剥离，直接看符号表就能拿到所有 phase 地址（本仓库 handouts/bomb/bomb/bomb 实测）：

$ objdump -t bomb | grep -E "phase_|explode"
0000000000400ee0 g  F .text  000000000000001c  phase_1
0000000000400efc g  F .text  0000000000000047  phase_2
0000000000400f43 g  F .text  000000000000008b  phase_3
000000000040100c g  F .text  0000000000000056  phase_4
0000000000401062 g  F .text  0000000000000092  phase_5
00000000004010f4 g  F .text  0000000000000110  phase_6
000000000040143a g  F .text  0000000000000022  explode_bomb
00000000004015c4 g  F .text  0000000000000095  phase_defused

（上面按地址排序便于阅读。bomb 的函数名没有被剥离是这份 bomb 的幸运之处——objdump -t 一跑，要读哪几个函数就一目了然。）

第二步：读懂 phase_1 的”比较+跳转”骨架。

$ objdump -d bomb | sed -n '/<phase_1>:/,/ret/p'
  400ee0:  48 83 ec 08        sub    $0x8,%rsp
  400ee4:  be 00 24 40 00     mov    $0x402400,%esi      # 第二个参数：目标字符串
  400ee9:  e8 4a 04 00 00     callq  401338 <strings_not_equal>
  400eee:  85 c0              test   %eax,%eax           # 返回值是 0 吗？
  400ef0:  74 05              je     400ef7 <phase_1+0x17>
  400ef2:  e8 43 05 00 00     callq  40143a <explode_bomb> # 不等则引爆
  400ef7:  48 83 c4 08        add    $0x8,%rsp
  400efb:  c3                 retq

test %eax,%eax + je 是”函数返回 0 就安全通过”的标准写法，%eax 里放的是 strings_not_equal 的返回值。剩下的事只有一件：看 0x402400 这个立即数指向什么。讲义特别提醒过——寄存器里的数字没有类型标签，要靠上下文判断哪些是地址：%rip 与 %rsp 永远是指针；出现在 mov (...) 这种解引用位置的值必定被当作地址；而 0x402400 落在 .rodata 地址范围内（info files 可查段边界），因此几乎肯定是字符串首地址。用 x/s 0x402400 一读即得答案。

第三步：gdb 三件套（断点、寄存器、内存）。

$ gdb ./bomb
(gdb) break explode_bomb          # 保命断点：一旦要炸就停下，不丢分
Breakpoint 1 at 0x40143a
(gdb) break phase_1               # 每进入一个 phase 先停下
(gdb) info breakpoints            # 确认两个断点都 y(启用)
(gdb) run psol.txt                # 用命令行参数喂入已解出的 phase，避免重复输入
(gdb) x/s 0x402400                # 按字符串格式看内存
0x402400:  "Border relations with Canada have never been better."
(gdb) info registers rdi rsi rsp  # 看参数寄存器与栈顶
(gdb) disassemble phase_2         # 反汇编当前 phase（不必再开 objdump）

第四步：用控制流知识逆推 phase_2。 phase_2 的骨架是”先检查首元素、再沿数组循环比较”：cmpl $0x1,(%rsp) 配合 je，然后用 %rbx 作移动指针、%rbp 作终止边界，循环体内 add %eax,%eax 后 cmp %eax,(%rbx)——把 -0x4(%rbx)（上一个元素）翻倍后与当前元素比较。能一眼看出 %rbx 是步长为 4 的整数指针、%rbp 是结束地址，正是 Lecture 3 寻址模式与本讲条件跳转的直接回报。

常见坑：①在 bomb 里用 gdb 的 call 命令调用函数会引爆（课堂活动明确警告）；②只设 break phase_1 而忘设 break explode_bomb，错一次就扣 1/2 分；③用 x/8xb 看字符串读不出 ASCII——用 x/s 或对照 man ascii；④忘记 bomb 支持 ./bomb psol.txt，反复手敲已解出的 phase。

4.5 常见错误与调试技巧

• 有符号/无符号跳转混用：C 中写 if (x < y) 而 x、y 是 unsigned，编译器仍用 setb/jb；若手写汇编误用 jl，负数会被判成”小于”。调试：objdump -d -M att 核对 j 后缀，或在 gdb 中 p (unsigned long)x 对比 p (long)x。
• cmp 操作数顺序反了：AT&T 是”源, 目的”，cmpq %rsi,%rdi 判断的是 %rdi 与 %rsi 的关系。调试：gdb -tui 打开汇编/寄存器分窗，stepi 单步并在 info registers eflags 中直接看 ZF/SF/CF/OF。
• setX %al 忘记零扩展：返回值高 24 位是垃圾。调试：p $rax 与 p $eax 一起打印对比；正确代码应看到 movzbl %al,%eax。
• 误以为 cmov 能防止非法访存：把 p ? *p : d 交给 -O2 后若被改写成无条件加载就会段错误（现代 GCC 不会这样做，但手写内联汇编极易犯错）。调试：valgrind ./prog 观察 Invalid read；或用 perf stat -e branch-misses ./prog 验证 cmov 化是否真的减少了预测失败。
• switch 索引越界：跳转表前必须有上界检查，否则 jmp *.L4(,%rdi,8) 会跳飞。调试：objdump -d 确认 ja 守卫存在；在 gdb 中 x/8xg <表基址> 核对表项是否落在 .text 范围内（info files 查看段边界）。
• 循环变量被优化掉导致断点失效：-O2 下 i 可能只存在于寄存器甚至被删除。调试：调循环用 -Og -g；用 break *0x401126 按地址下断点，x/i $rip 确认位置。
• Bomb Lab 中误用 call：在 gdb 里直接调用炸弹函数会触发爆炸判定。调试：只读不调——x/s、info registers、disassemble 都是安全的。
• 把 je 与 jz 当成不同指令：二者机器码完全相同，只是助记法不同。调试：objdump -d 会统一显示为同一个官方名字（machine-control.txt 明确说明：a.k.a. 名字的区分在机器语言中丢失）。

4.6 关键要点

• 控制流的全部基础设施只有两样：条件码 + goto。 if、while、for、switch 都只是 goto 的不同排版，理解回跳方向就理解了循环。
• 有符号关系用 g/l，无符号关系用 a/b；条件码组合 SF^OF 与 CF 是两套判断的分水岭，set 与 jX 共用同一张表。
• cmov 的本质是用数据流替代控制流：它换来分支预测的确定性，代价是两条路径都必须可安全求值；可能非法访存的表达式禁止 cmov 化。
• 跳转表是编译器对稠密 switch 的 $O(1)$ 分派，落在 .rodata，用 jmp *表(,%rdi,8) 加一次上界检查实现；稀疏时退回比较链，甚至用”先减后无符号比较”一次判掉连续小区间。
• -Og 追求与源码逐行对应，-O1 以上才做 guarded-do、cmov 化等改写；调试读汇编前务必先确认优化级别，否则会把优化产物误当源码语义。
• Bomb Lab 的成功公式 = objdump -d 定位 + gdb 断点保命 + 条件码推演：先设 break explode_bomb，再用 info registers 与 x/s 反推输入。

4.7 思考题（带答案）

题 1（汇编推演题）：下面的函数 quiz 由 gcc -Og 编译（真实产物），请写出它等价的 C 代码，并给出 (a,b) 为 (5,3)、(-1,3)、(7,7) 时的返回值。

quiz:
	cmpq	%rsi, %rdi
	jg	.L6                 # a > b
	movl	$0, %eax
.L2:
	cmpq	%rsi, %rdi
	je	.L8                 # a == b
.L3:
	cmpq	%rdi, %rsi
	jnb	.L4                 # b >= a（无符号）
	orq	$4, %rax
.L4:
	xorq	%rsi, %rdi
	js	.L9                 # (a^b) < 0
.L1:
	ret
.L6:
	movl	$1, %eax
	jmp	.L2
.L8:
	movl	$2, %eax
	jmp	.L3
.L9:
	orq	$8, %rax
	jmp	.L1

答案：它等价于对 4 个独立条件做按位累加：

/* quiz.c —— gcc -Og -Wall -std=c11 -g 验证通过，输出 5 / 12 / 2 */
#include <stdio.h>

long quiz(long a, long b) {
    long r = 0;
    if (a > b)  r = 1;                        /* = 1，不是 |= */
    if (a == b) r = 2;                        /* = 2，覆盖前面的值 */
    if ((unsigned long)a > (unsigned long)b) r |= 4;
    if ((a ^ b) < 0)                         r |= 8;   /* a、b 异号 */
    return r;
}

int main(void) {
    long c[][2] = {{5, 3}, {-1, 3}, {7, 7}};
    for (int i = 0; i < 3; i++)
        printf("(%2ld,%2ld) -> %ld\n", c[i][0], c[i][1], quiz(c[i][0], c[i][1]));
    return 0;
}

推演要点：jnb 是”无符号 %rsi >= %rdi“，即 (unsigned)a > (unsigned)b 时才不置 4 位，故 orq $4 出现在跳转未发生时；xorq %rsi,%rdi 的 js 判的是异号（一正一负时符号位为 1）。实测结果：(5,3) → 5（1+4）、(-1,3) → 12（4+8，负数在无符号下更大）、(7,7) → 2（仅相等，7>7 不成立，a^b=0 非负）。

题 2（易错直觉题）：既然 cmov 能避免分支预测失败、又快又稳，为什么下面的函数不会被编译成 cmov？如果强行用 cmov 会怎样？

/* cread.c —— gcc -O1 -Wall -std=c11 -g 验证通过 */
long cread(long *xp) { return xp ? *xp : 0; }

（把它补成完整程序验证：int main(void){ long v=99; printf("%ld %ld\n", cread(&v), cread(NULL)); return 0; }，输出 99 0。）

答案：cmov 要求两个候选值都被求值，即必须无条件执行 *xp；当 xp == NULL 时这就是一次非法访存（段错误），原程序并不会因此崩溃。C 语义下”优化不得引入原程序不存在的行为”，因此编译器必须保留分支形成短路求值。想用上 cmov 的正确写法是把两条臂都变成安全计算（cread_alt：先让 xp 指向本地 zero，再统一解引用），实测 -O1 生成 cmove %rax,%rdi 且无跳转分支。

题 3（计算题）：某稠密 switch 的跳转表放在 .rodata，基址为 0x402008，被 jmp *.L4(,%rdi,8) 使用。若某个时刻 %rdi = 3，（a）该表项位于哪个地址？（b）为什么 scale 必须是 8？（c）如果编译器改用讲义提到的”4 字节偏移”表，同样的 %rdi = 3 会读到什么，最终目标地址如何算出？

答案：（a）0x402008 + 3*8 = 0x402020（实测该处正是 0x40113f，即 grade 的 x==3 分支）。（b）每个表项要容纳一个 64 位代码地址，即 8 字节，D(Rb,Ri,S) 的 scale 只能取 1/2/4/8，正好用 8。（c）偏移表每项 4 字节，%rdi=3 时读 0x402008+3*4 = 0x402014 处的 32 位值，按 movslq 符号扩展为 64 位后与表基址相加得到目标地址，即 目标 = 表基址 + 偏移；这样表体积减半，且天然位置无关（PIC 友好）。

题 4（易错直觉题）：有同学说”for 循环的汇编里一定有 i++ 和 i < N 两条指令，所以照这个模式去认循环就行”。这个想法错在哪？

答案：错在把源码结构当成汇编结构的判据。第一，-O1 的 guarded-do 会把入口的初值测试整条删掉，循环只剩底部的 cmpl $64,%ecx; jne；第二，循环变量可能完全消失——pcount_for 在更激进的优化下会被向量化或直接识别成 popcount；第三，for 与 while 编译出的汇编可以完全一致（machine-control.txt 问题 17 正是在问”若不看名字，能否分辨源码写的是 for 还是 while”——答案是不能）。正确做法是看回边（backward jump）：哪里有向后跳转、哪里的条件码决定是否重复，哪里就是循环。