编译原理第八章代码生成与优化：基本块、DAG与活跃性分析实战解析-北京尧图网络

如果你正在啃《编译原理》也就是大家常说的龙书并且刚好卡在第八章那你应该能理解我的感觉。前七章还在讨论词法、语法、中间代码生成虽然也有难度但至少处理的还是“程序长什么样”的问题到了第八章一下子切换到“怎么把中间代码变成真正能在机器上跑的目标代码”需要同时考虑指令集、寻址方式、寄存器数量、临时变量的生死信息量一下子大很多。这篇文章不是抄答案而是把我自己做第八章部分课后题时的分析过程、踩坑记录和一些参考答案整理出来给同样在学编译原理、准备考试或者在做课后练习的同学一个参考。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 - B3if t2 0 为真跳到L1 B2 - B4if t2 0 为假顺序执行第6条goto L2跳到8 B3 - B4第7条执行完顺序进入第8条 B4 - B4if t5 0 为真跳到L2也就是跳回自己 B4 - B5if 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对应的节点是N1t2对应N2所以建节点N3表示N1 N2挂上名字t3。第4条t4 a b检查发现a b已经存在节点N1所以不新建节点直接把名字t4挂到N1上。第5条t5 t4 t2t4指向N1t2指向N2N1 N2已经存在节点N3所以直接把t5挂到N3上不新建节点。第6条t6 c dc d已存在节点N2直接把t6挂到N2上。第7条t7 t6 * t3t6指向N2t3指向N3N2 * 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 (abcd) * (cd)这一条计算是有用的。不过在普通三地址代码模型里我们通常还是会保留所有“显式命名的临时变量”因为后面程序可能还在用它们。做题时最好看清楚题目要求有些题只说“删除公共子表达式”有些题则会让你“同时删除无用代码”。一个实用的经验是建完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 1i被定值记入def第2条c a bc被定值记入def同时a、b在本块内还没有被定值过记入use第3条if c 0使用c但c已经在def里不记入use。所以def[B1]{i,c}use[B1]{a,b}。B2第4条d a id定值记入defa、i在本块内没有定值过记入use第5条if d nd在def里不算usen没有被定值过记入use。所以def[B2]{d}use[B2]{a,i,n}。B3第6条t c dt定值记入defc、d在本块内没定值过记入use第7条c t ic定值记入deft在def里不算usei没定值过记入use。所以def[B3]{t,c}use[B3]{c,d,i}。注意c既在use又在def这是允许的因为第6条先使用了外部传入的c第7条又给c定了一个新值。B4第9条x c dx定值记入defc、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和B3B2后继是B3和B4B3后继是B2B4没有后继。初始时所有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那组题把每个变量名的指向变化都理清楚。编译原理学到第八章很大程度上已经是在用工程思维解决性能问题把这一章的题目吃透对后面学习更复杂的优化算法会轻松很多。

编译原理第八章代码生成与优化：基本块、DAG与活跃性分析实战解析

相关推荐

Linux上搭建vsftpd FTP服务器：匿名、本地与虚拟用户配置实战

数字电路流水线性能比较：延迟、吞吐率与功耗的量化分析方法

手写C++神经网络：穿透深度学习黑箱的底层实践

更多资讯

Highcharts表格直驱可视化：HTML Table自动转图表教程

仿站式训练：用HTML、CSS与JavaScript体系化提升前端布局与还原能力

Unity AssetBundle构建慢的三大底层原因与架构级解决方案

macOS窗口移动工具开发实战：从Accessibility API到全局快捷键

FFmpeg实战指南：从安装配置到音视频处理与项目集成全解

BCT脑网络分析实战指南：从MATLAB安装到可发表指标计算

今日更新

AReaL 调试指南：从 Agent Workflow 验证到分布式训练死锁诊断

MATLAB实现GPS L1 C/A信号仿真与二维捕获验证

彻底搞懂ASCII、Unicode与UTF-8：从乱码根源到编码实战

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？