如果你正在啃《编译原理》也就是大家常说的龙书，并且刚好卡在第八章，那你应该能理解我的感觉。前七章还在讨论词法、语法、中间代码生成，虽然也有难度，但至少处理的还是“程序长什么样”的问题；到了第八章，一下子切换到“怎么把中间代码变成真正能在机器上跑的目标代码”，需要同时考虑指令集、寻址方式、寄存器数量、临时变量的生死，信息量一下子大很多。这篇文章不是抄答案，而是把我自己做第八章部分课后题时的分析过程、踩坑记录和一些参考答案整理出来，给同样在学编译原理、准备考试或者在做课后练习的同学一个参考。
1. 代码生成的整体思路：为什么第八章让人又爱又恨
1.1 中间代码到目标代码，中间到底发生了什么
第八章讲的是编译管道的最后一段：代码生成。你手上有的是中间表示，可能是三地址代码、语法树，也可能是有向无环图（DAG），而你要交付的是能在目标机器上执行的汇编或机器指令。这中间有几个绕不开的问题：一个表达式如何映射到机器指令？数组元素怎么寻址？函数调用时的参数怎么传、栈帧怎么安排？寄存器这么少，临时变量怎么分配？
龙书第八章把这些拆成了几块来讲：先讲中间代码语言的基本形式，比如三地址代码中的各种语句类型；再讲如何把声明翻译成存储布局、把语句翻译成三地址代码；然后引入基本块和流图，把中间代码切成一个个“局部优化单元”；最后才是寄存器分配和简单的代码生成算法。
我做课后题时的最大感受是：这一章的题目不是孤立的，前面几节的题目基本是在练“怎么翻译”，后面几节则是在练“怎么优化”。如果你前面的翻译没搞明白，后面做DAG优化、活跃性分析就会一头雾水，因为你看不懂代码里哪些计算是重复的、哪些变量在基本块出口还活着。
1.2 为什么课后题值得一题一题做
很多人觉得龙书课后题偏理论，跟实际编译器开发距离远。但以我自己的体会，第八章这些题目恰恰是编译器后端里最实用的部分。数组寻址的计算方式、基本块划分规则、DAG上做公共子表达式删除、活跃变量迭代分析，这些概念在真实编译器优化层里都有对应实现。你如果去做LLVM的后端或者自己写一个简单的编译器，会发现遇到的问题跟课后题一模一样。
所以我的建议是：不要只背题目的答案，而是把每一道题当作一个小型编译器优化流程来走一遍，至少要在纸上画出流图、列出def/use表、手动迭代出活跃变量的不动点。这个过程虽然慢，但做完之后你会对后续的真实代码生成算法有更踏实的理解。
2. 数组与指针的翻译：8.5节习题的常规解法拆解
2.1 数组元素寻址的三地址代码长什么样
龙书第八章的习题里，有很大一部分是在练数组和指针的翻译，本质上是在练“怎么把高级语言里的下标访问拆成地址计算指令”。我拿一个常见的例子展开：假设有一个二维数组定义int a[10][20]，每个int占4字节，那么a[i][j]的地址该怎么算？
按照行优先存储，a[i][j]的偏移是(i * 20 + j) * 4，再拼上数组的基地址。三地址代码可以这样写：
t1 = i * 20 t2 = t1 + j t3 = t2 * 4 t4 = base_a + t3最后t4就是a[i][j]的地址。这里需要注意两个细节：
i * 20中的20是二维数组第二维的长度，不是字节数，因为下标计算先算出“第几行第几列”，最后再统一乘以元素宽度。- 有些同学会把
j * 4和i * 80拆开算，这样也正确：i * 80是行偏移，j * 4是列偏移，两者相加得到的就是字节偏移。但为了统一处理多维数组，龙书的做法是先算平铺下标再乘元素大小，更适合通用翻译。
实际做题你会发现，不优化的话，同一个数组元素如果出现多次（比如赋值语句的右值和左值都是a[i][j]），地址计算会被重复生成好几次。这时候DAG优化的威力就体现出来了，后面我会专门讲。
2.2 指针和左值处理的关键点
指针相关的翻译题，核心是理解“指针变量本身也是一个存储位置，它里面存的是另一个内存地址”。龙书里有一个典型习题是翻译下面这段声明：
int *p, *q; p = &x[0]; q = &y[0];翻译成三地址代码时，p = &x[0]并不是计算x[0]的内容，而是取x[0]的地址，也就是数组x的基地址。编译器通常会直接翻译成：
t1 = base_x p = t1更严格的写法会走一遍地址计算：
t1 = 0 * 4 t2 = base_x + t1 p = t2但很多实际编译器会做“常数折叠”和“强度削减”，直接把0 * 4算成0，最终结果就是p = base_x。做题时两种写法都能接受，但你要能说清楚为什么它们是等价的。
左值处理上还有一个容易出错的点：当指针变量p作为左值时，比如*p = x + y，翻译过程要先取出p的值，把它当作地址，再往这个地址里写计算结果。三地址代码大致是：
t1 = x + y t2 = load p // t2 = *p? 不对，这是取出指针变量p的值 store t2, t1 // 把t1的值写到地址t2也就是说，指针解引用和普通变量赋值的核心区别在于：普通赋值直接写到变量对应的存储位置；指针赋值多了一步“从指针变量中取地址”的操作。做题时每次看到*p，都要提醒自己先把p里的地址拿出来。
2.3 一个完整示例：朴素翻译与优化后翻译的对比
我拿一个很有代表性的赋值语句展开：a[i][j] = b[i][j] + c[i][j]。假设三个数组都是int a[10][20], b[10][20], c[10][20]。
先看不做任何优化的朴素翻译，为了清晰我直接给三地址代码：
1. t1 = i * 20 2. t2 = t1 + j 3. t3 = t2 * 4 4. t4 = base_b + t3 5. t5 = i * 20 6. t6 = t5 + j 7. t7 = t6 * 4 8. t8 = base_c + t7 9. t9 = load t4 10. t10 = load t8 11. t11 = t9 + t10 12. t12 = i * 20 13. t13 = t12 + j 14. t14 = t13 * 4 15. t15 = base_a + t14 16. store t15, t1116条指令，其中有三个几乎一样的地址计算块。这种翻译在许多基础编译器中确实会出现，因为代码生成器是逐条处理中间代码的，它每遇到一次b[i][j]就会重新生成一遍地址计算。
如果做公共子表达式删除，情况立刻不一样。i * 20、i * 20 + j、再乘以4，这三步对三个数组来说是公用的，只是基地址不同。优化后可以变成：
1. t1 = i * 20 2. t2 = t1 + j 3. t3 = t2 * 4 4. t4 = base_b + t3 5. t8 = base_c + t3 6. t9 = load t4 7. t10 = load t8 8. t11 = t9 + t10 9. t15 = base_a + t3 10. store t15, t11从16条降到10条，少掉的是重复的i * 20、t1 + j和t2 * 4。这就是第八章后面DAG优化的实际收益。你做题时最好两种版本都写出来，一个是翻译器“笨拙但正确”的行为，一个是优化器“聪明且紧凑”的行为，对照起来理解更深刻。
3. 基本块与流图：把一段代码切出“可优化单元”
3.1 基本块入口语句的判断规则
做8.6节习题的第一步，是把中间代码划分成基本块。基本块是一段顺序执行的指令序列，除了入口和出口，内部不能有任何分支或跳转目标。划分基本块的规则其实只有三条：
- 整个程序的第一条指令是入口语句。
- 任何跳转指令（条件跳转、无条件跳转）的目标语句是入口语句。
- 跳转指令的下一条语句是入口语句，因为跳转指令执行完以后，顺序流会从下一条继续（对于条件跳转的“假分支”就是顺序到下一句）。
拿到一段中间代码后，先按这三条规则把所有入口语句标出来，然后每个入口语句开始往下延伸，直到遇到下一个入口语句或者遇到一条跳转语句（跳转语句本身包含在块内，但它是块的最后一个语句）。
这里最容易被绕晕的是“跳转语句的下一条语句”和“跳转目标语句”都是在给后续语句打标记，每次都有同学分不清。简单记：一个跳转可能产生两个流向，一个是跳到目标，一个是顺序往下走，所以这两个落点都必须是基本块入口。
3.2 一个带循环的示例：完整划分过程
我拿一个含循环和条件分支的中间代码片段来做示范，这种结构在实际翻译中很常见：
1. i = 1 2. t1 = i * 4 3. t2 = a[t1] 4. if t2 < 0 goto L1 5. x = t2 + 1 6. goto L2 7. L1: x = -t2 8. L2: t3 = x * 2 9. t4 = t3 + k 10. if t5 > 0 goto L2 11. t6 = t5 + t3 12. t7 = t6 * i先找入口语句：
- 第1条是程序第一条，肯定是入口。
- 第4条是无条件跳转？不，第4条是
if t2 < 0 goto L1，它是一条条件跳转，它的跳转目标是第7条L1，所以第7条是入口。 - 第6条是
goto L2，是无条件跳转指令，它的下一条也就是第7条已经标记为入口了，它的跳转目标第8条L2也是入口。 - 第10条是
if t5 > 0 goto L2，它的目标还是第8条，已标记；它的下一条第11条也是入口。
整理下来入口语句是：1、7、8、11。注意第7条是跳转目标，第8条也是跳转目标，而第11条是条件跳转的下一条。
现在划分基本块：
- B1：第1条到第3条。为什么第4条不进来？因为第4条是条件跳转，块内不允许出现不是最后一条的跳转，所以B1在第3条结束。
- B2：第4条到第6条。这里第4条是条件跳转，但它的“假分支”会顺序执行第5条，第5条继续到第6条的无条件跳转，所以这3条必须在一个块里。
- B3：第7条，就是
x = -t2。它是跳转目标，后面第8条也是跳转目标，所以它单独成块。 - B4：第8条到第10条，三条语句。第10条是条件跳转，结束块。
- B5：第11条到第12条。
流图关系用文字写出来：
B1 -> B2：顺序执行 B2 -> B3：if t2 < 0 为真，跳到L1 B2 -> B4：if t2 < 0 为假，顺序执行第6条goto L2跳到8 B3 -> B4：第7条执行完顺序进入第8条 B4 -> B4：if t5 > 0 为真，跳到L2，也就是跳回自己 B4 -> B5：if t5 > 0 为假，顺序进入第11条 B5 -> 结束注意B4有一条自环边，说明这个基本块内部构成了循环。这种自环很有意义，做完活跃性分析之后你会发现，因为B4会跳回自己，B4出口处的某些变量的活跃信息会反过来影响B4自己的入口分析，形成迭代依赖。
这里要提醒一点：很多参考书在画流图时喜欢直接画箭头，但做习题时最好把每条边是“真分支”“假分支”还是“顺序流”标注出来，方便检查有没有漏边。我一开始做题经常漏掉B2到B4那条边，因为它的流向不是直接跳转，而是通过第6条goto L2间接转过去的。本质上B2的最后一条是无条件跳转，跳转目标就是第8条，所以这条边不能少。
4. DAG上做局部优化：让重复计算无处藏身
4.1 为什么DAG适合做局部优化
DAG（有向无环图）是第八章里特别重要的一个数据结构。它和普通语法树的区别在于：同一个子表达式在语法树里会出现多份拷贝，但在DAG里只会有一个节点。比如a + b出现了两次，语法树上会画两个+节点，但DAG会共用一个节点。
这种“共用节点”的特性，让DAG成为做公共子表达式删除的天然工具。你在建DAG的时候，每遇到一个新计算，就看看是不是已经存在完全相同的节点；如果存在，直接把变量名挂到旧节点上，而不新建节点。这样做完之后，从DAG反推回中间代码，重复计算自然就不见了。
还有一个浅层但重要的好处：DAG建完以后，如果一个节点没有父亲节点、也没有挂任何后续还会被使用的变量名，那它就是死代码，可以直接删掉。这个优化在习题里尤其好用，因为它能帮你检查出那些“算了但没人用”的垃圾指令。
4.2 一道8.6节习题的完整DAG构建过程
我直接用一个常见习题的基本块来演示，它足够小，可以手工画DAG，又有足够多的重复结构来体现优化效果：
t1 = a + b t2 = c + d t3 = t1 + t2 t4 = a + b t5 = t4 + t2 t6 = c + d t7 = t6 * t3先按顺序建DAG。手写的话可以一层一层列节点，我这里用文字描述：
- 叶子节点：
a、b、c、d。 - 第1条
t1 = a + b：建节点N1，表示a + b，挂上名字t1。 - 第2条
t2 = c + d：建节点N2，表示c + d，挂上名字t2。 - 第3条
t3 = t1 + t2：因为t1对应的节点是N1，t2对应N2，所以建节点N3，表示N1 + N2，挂上名字t3。 - 第4条
t4 = a + b：检查发现a + b已经存在节点N1，所以不新建节点，直接把名字t4挂到N1上。 - 第5条
t5 = t4 + t2：t4指向N1，t2指向N2，N1 + N2已经存在节点N3，所以直接把t5挂到N3上，不新建节点。 - 第6条
t6 = c + d：c + d已存在节点N2，直接把t6挂到N2上。 - 第7条
t7 = t6 * t3：t6指向N2，t3指向N3，N2 * N3是新组合，建节点N4，挂上名字t7。
建完DAG后，真正需要生成代码的节点是N1、N2、N3、N4。原来的7条指令里，t4、t5、t6都是从旧节点上直接挂名，不需要额外生成指令。从DAG重构代码，得到：
t1 = a + b t2 = c + d t3 = t1 + t2 t7 = t2 * t3这里t7 = t2 * t3可以写t2是因为t6和t2指向同一个节点N2，直接用最早的名字。
这还没完。注意节点N3挂了两个名字t3和t5，如果题目要求重写代码时保留“每个临时变量被赋值一次”的语义，并且t3和t5在后续代码中都会被使用，那也许需要额外生成一条t5 = t3的复制指令。但如果后续只使用t3或者只使用t5，就可以只保留一个。这种“根据活跃性决定保留哪个名字”的分析，正好是下一节活跃变量分析的用武之地。
4.3 从DAG结果反推可删除的死代码
同样是上面这个基本块，如果你把每个节点的“引用计数”记下来，也就是每个节点被多少个后代节点直接引用，删除死代码时就有依据了。比如在完整DAG里，N1被N3引用，N2被N3和N4引用，N3被N4引用，N4没有被任何节点引用，但t7是基本块的输出变量，需要保留。
如果基本块后面还有代码要用t1、t2、t7，那这4条指令都不能删。如果t1、t2、t3只是临时变量，后面根本不引用，那其实整个基本块只有t7 = (a+b+c+d) * (c+d)这一条计算是有用的。不过在普通三地址代码模型里，我们通常还是会保留所有“显式命名的临时变量”，因为后面程序可能还在用它们。做题时最好看清楚题目要求：有些题只说“删除公共子表达式”，有些题则会让你“同时删除无用代码”。
一个实用的经验是：建完DAG后，把所有“没有任何父节点且没有挂名字”的节点圈出来，这些就是死代码候选；如果某些节点挂了名字，但这些名字在基本块出口之后不再活跃，它们也可以视为死代码。这就是第八章把DAG和活跃性分析放在一起讲的原因，它们是配合使用的。
5. 活跃性分析：寄存器分配的“侦察兵”
5.1 def和use的精确定义
活跃性分析要解决的核心问题是：在每一条指令执行之前和之后，哪些变量的值还有可能在将来被使用？如果一个变量在某一点之后永远不会被读取，那它的值就是死的，编译器可以放心地释放它占用的寄存器，或者把它从寄存器里换出去。
做习题时首先要把每个基本块的def和use集合算对。龙书里的定义需要多读几遍：
def[B]是在基本块B中“被定值且定值前在该基本块中没有被使用过”的变量集合。use[B]是在基本块B中“被使用且使用前在该基本块中没有被定值过”的变量集合。
通俗理解：def是那些出生在本基本块的变量（本块内定值且定值前没人用）；use是那些本基本块“还没出生就用到了”的变量，也就是从外部传入的活跃变量。
判断时我习惯从块的第一条指令开始逐条扫，看到一个变量被赋值就先记入def，看到一个变量被读取就先判断它是否已经在def里，不在的话记入use。用这个办法不容易出错。
5.2 一个带循环的小流图：手工迭代到不动点
我设计一个小流图，它不大，但包含分支和循环，适合手算。四个基本块如下：
B1: 1. i = 1 2. c = a + b 3. if c > 0 goto L1 B2: 4. d = a + i 5. if d < n goto L1 B3 (L1): 6. t = c + d 7. c = t + i 8. goto L2 B4: 9. x = c + d先算每个基本块的def和use，用我刚才说的逐条扫描法：
- B1：第1条
i = 1，i被定值，记入def；第2条c = a + b，c被定值，记入def，同时a、b在本块内还没有被定值过，记入use；第3条if c > 0使用c，但c已经在def里，不记入use。所以def[B1]={i,c}，use[B1]={a,b}。 - B2：第4条
d = a + i，d定值记入def，a、i在本块内没有定值过，记入use；第5条if d < n，d在def里不算use，n没有被定值过，记入use。所以def[B2]={d}，use[B2]={a,i,n}。 - B3：第6条
t = c + d，t定值记入def，c、d在本块内没定值过，记入use；第7条c = t + i，c定值记入def，t在def里不算use，i没定值过，记入use。所以def[B3]={t,c}，use[B3]={c,d,i}。注意c既在use又在def，这是允许的，因为第6条先使用了外部传入的c，第7条又给c定了一个新值。 - B4：第9条
x = c + d，x定值记入def，c、d都没定值过，记入use。所以def[B4]={x}，use[B4]={c,d}。
然后按照数据流方程迭代：
in[B] = use[B] ∪ (out[B] - def[B])out[B] = ∪ in[S]，其中S是B的所有后继基本块
后继关系：B1后继是B2和B3；B2后继是B3和B4；B3后继是B2；B4没有后继。
初始时所有in、out都是空集。第一轮结束后的结果：
B1: in={a,b,d,n}, out={a,c,i,n} B2: in={a,c,i,n}, out={a,c,d,i,n} B3: in={a,c,d,i,n}, out={a,c,i,n} B4: in={c,d}, out={}这个结果已经是收敛后的不动点了，因为第二轮迭代每个集合都不再变化。你做题时一定要自己迭代至少两轮，不要只算一遍就结束，因为out[B3]依赖in[B2]，而in[B2]又依赖out[B3]，这种循环依赖必须通过迭代才能求解。
得到这个表以后，你能直观地看到：a在B1入口就是活跃的，然后一路活到B3出口，说明它跨越了好几个基本块，应该在寄存器里多待一会儿；d只在B2和B3之间活跃，生命期比较集中；x只在B4被定义，而且出口处不活跃，说明x算完以后立刻就没有使用价值，它的寄存器可以在B4出口释放。这些信息正是寄存器分配要用的。
5.3 寄存器分配就是给不重叠的生命期安排房间
我特别喜欢用一个类比来讲寄存器分配：寄存器就像酒店房间，变量就像房客。房客有入住时间和退房时间，多个房客只要时间不重叠，就可以共用同一个房间。活跃性分析就是在算每个变量的“入住时间”和“退房时间”，寄存器分配则是在安排谁住哪间房，尽量少开新房间，实在住不下就把某个房客的行李暂时存到仓库（内存）里，也就是spill。
有一个经典的小循环例子能说明寄存器分配的核心矛盾：
L1: t1 = i + 1 i = t1 if i < n goto L1在循环里，i每轮都被使用和重新定义，所以它必须一直待在寄存器里；n每轮比较都要用，也得常驻寄存器。t1的生命期很短，只在第一条语句到第二条语句之间活着。如果只有两个寄存器，i和n已经占满了，t1怎么办？答案是只能先把n溢出到内存，等执行完t1 = i + 1再重新加载n。这种“spill一次”的成本通常比“整个循环都用不到两个以上寄存器”的代价低得多。
做题时你不需要真的写一个完整的图着色分配器，但你要能从活跃性表里看出哪些变量该优先分配寄存器：那些在多个基本块入口和出口都活跃的变量，比如前面例子里的a、i、c，优先级最高；那些只在单个基本块内部存活、出口处已死的变量，比如t1、临时地址变量，优先级低，用普通临时寄存器就行。
6. 做题时容易踩的坑
6.1 基本块切分时最容易错的两个地方
第一个错是认为“条件跳转的下一条语句不算入口”。这是不对的，因为条件跳转有真假两个分支，假分支会顺序执行下一条语句，所以下一条必须是基本块入口。第二个错是把“跳转目标语句”和“跳转目标的上一条语句”混在一起。龙书的划分规则是以语句为最小单位，目标是第7条，那第7条就是入口，第6条不会因为紧跟其前面而被划进同一个块。
另外一个常见问题是：块内不允许出现“块中间有跳转指令，但跳转指令后面还有语句属于同一个块”的情况。严格来说，只有当跳转指令是该块最后一条指令时，它才属于这个块。如果遇到一个if在块中间，后面还有顺序执行的其他指令，说明前面的基本块入口标记出问题了，需要重新检查。
6.2 DAG节点合并要区分“值”和“变量名”
DAG里同一个节点可以挂多个变量名，比如a + b这个节点同时挂了t1和t4，但这不代表t1和t4在任何时候都等价。如果代码中途某个变量被重新赋值，比如t1 = a + b之后再来一条t1 = t1 + c，那后面的t1就指向一个新节点，不能继续挂在旧节点上。
做题时我建议给每个“定义”加个版本号，心里默念“变量名只是标签，DAG节点才是真正的值”。这样在建DAG时就会知道：一旦遇到一个变量被重新定义，就要让这个变量名切换到新节点，而不是继续挂在旧节点上。
6.3 活跃性分析用错初始化导致结果不稳定
活跃性分析的迭代是从空集开始的，初始化时所有in、out都是空集。有些同学为了“加速收敛”，会把后继基本块的use提前塞进out，这会导致第一次迭代结果看起来合理，但后续迭代反而乱了。
还有一点：迭代顺序不影响最终结果，因为数据流方程是单调的，不管你是从B1开始还是从B4开始，最后都会收敛到同一个不动点。但人工计算时最好还是按流图拓扑顺序来，遇到循环再回来迭代第二轮，这样不容易算漏。
6.4 写参考答案时，不要只写精简版，过程更重要
我做题时会把朴素的未优化版本、基本块划分结果、DAG重写结果放在一起对比。虽然最终答案可能只有几行优化后的代码，但如果没有中间过程，考试或面试时很难说清楚“为什么可以这样优化”。强烈建议你养成的习惯是：每道题都标注“优化前指令数”和“优化后指令数”，比如前面数组寻址的例子从16条降到10条，DAG的例子从7条降到4条，用数字说明优化收益，很有说服力。
7. 往后的方向：把课后题变成一个小代码生成器
第八章的题目做完之后，如果你想更进一步，可以自己做一个小实验：定义一套非常简单的指令集，比如只有load、store、add、mul、跳转这几条指令，然后用C语言或你熟悉的语言写一个极简代码生成器。先把三地址代码逐条翻译成指令，然后做基本块划分、DAG优化、活跃性分析、简单寄存器分配，每完成一个阶段就对比一下生成指令数量。
我第一次做这个实验的时候，用的就是第八章习题里最简单的数组寻址例子，结果发现，不优化时生成22条汇编，做完公共子表达式删除后变成13条，再做一遍寄存器分配后变成11条。那种“看到指令数量真的掉下来”的感觉，比单纯看参考答案要直观得多。
另外可以试试窥孔优化，算是第八章的一个延伸主题。窥孔优化的思路特别朴素：在生成的目标代码上滑动一个小窗口，比如连续几条指令，如果发现jump L后面跟着L:这种冗余跳转，或者load r, x之后马上store x, r这种无意义对，就直接删除或替换。虽然龙书第八章正文篇幅不长，但它的习题里会出现这类优化思想，自己动手实现一次收获很大。
最后再说一个我个人的体会：第八章这几类习题的价值不在于“会做”，而在于“能解释为什么这么做”。比如你能说出“基本块出口活跃的变量必须保留寄存器”这句话和活跃性迭代方程之间的关系，那你是真的理解了。如果只是会套公式，建议再做一遍DAG那组题，把每个变量名的指向变化都理清楚。编译原理学到第八章，很大程度上已经是在用工程思维解决性能问题，把这一章的题目吃透，对后面学习更复杂的优化算法会轻松很多。
