跳到主要内容

代码生成

代码生成​

代码生成器是编译器后端的最后一环,它的输入是中间表示(IR,比如三地址码、SSA 或者一棵较低层次的树),输出是目标机器可以直接执行的汇编代码或机器码。表面看只是"翻译",但要生成质量过关的代码,得同时解决三个难题:指令选择(用哪些机器指令来覆盖 IR)、寄存器分配(哪些值放寄存器、哪些放内存)、指令调度(指令之间怎么排序才不卡流水线)。

通俗理解:中端产出的 IR 像是一份"菜谱",只告诉你要做什么菜;代码生成器则是拿着这份菜谱、在一间只有若干个灶台和有限锅具的厨房里,安排每一步用哪口锅、什么时候放料、火候怎么排。锅(寄存器)不够就得倒进冰箱(内存)里,工序不对就会互相等待。

目标机器模型​

要生成好代码,编译器必须建立一个准确的机器模型:CPU 有多少通用寄存器、内存访问的相对代价是多少、指令集支持哪些寻址方式、指令流水线有几级。

RISC(如 ARM、RISC-V)指令数量少、格式规整、每条指令通常单周期,运算只在寄存器之间发生,访存靠专门的 LOAD/STORE。CISC(如 x86)指令种类繁多,一条指令可以直接把内存操作数带进来,比如 ADD [ebx+4], eax。RISC 让编译器的选择空间小但决策清晰,CISC 则给指令选择带来更多"合并机会",也更多"陷阱"。

基本块和流图​

代码生成之前,编译器会把 IR 切成基本块(Basic Block)——一段只有一个入口、一个出口,中间不能跳入也不能跳出的直线代码。划分规则很朴素:从函数第一条指令起,遇到跳转指令就结束当前块,遇到跳转目标就开启新块。

基本块之间用有向边连接就得到控制流图(CFG)。基本块内部可以做局部优化和寄存器分配,块与块之间则要考虑全局属性,比如某个变量是否跨块活跃。

指令选择​

指令选择本质上是"用机器指令的图案去覆盖 IR 树",可以形式化为树模式匹配。每条机器指令对应一个树模式和一个代价,比如:

LOAD  R, mem          (代价 3)
MOV R, mem (代价 1,仅 CISC 支持)
ADD R1, R2, R3 (代价 1)
ADD R1, R2, #imm (代价 1)

一棵 IR 子树可能有多种覆盖方式,通过动态规划为每个节点计算"用某种模式生成的最小代价",自底向上就能得到全局最小代价的指令序列。

以 a[i] = b + 2 为例,一种典型的 x86 翻译是:

mov  eax, [b]         ; 取 b
add eax, 2 ; b + 2
mov ecx, [i] ; 取 i
mov [a + ecx*4], eax ; 写回 a[i],用基址+变址+比例寻址

同样的语义,若在 RISC 上就要写成 LOAD/ADD/LOAD/SHL/ADD/STORE 一串更细粒度的指令。

寄存器分配​

寄存器只有十几到几十个,而中间变量可能有成百上千个,分配策略直接影响性能。

最朴素的方案是把每个变量都放栈上,每条指令执行前 LOAD 一次、执行后 STORE 一次。正确但慢得令人发指。

基本块内的分配可以用一种"按需装入 + LRU 淘汰"的堆栈式策略:为每个虚拟寄存器维护"下一次使用"信息,需要腾寄存器时把最远才会用到的那个溢出(spill)到栈。

全局寄存器分配跨基本块生效,经典方法是图着色。做法是:

  1. 构造干扰图,节点是虚拟寄存器,两个变量若在某点同时活跃就连一条边。
  2. 用 k 种颜色(k 等于物理寄存器数)为图着色,相邻节点不同色。
  3. 若图不可 k-着色,就选一个"高度数、低使用频率"的节点溢出到内存,重来。

图着色代价高,JIT 编译器(如 HotSpot、V8)更常用线性扫描:把变量活跃区间按起点排序,从左往右扫描,维护当前活跃集合,冲突时按启发式规则溢出。质量略逊图着色,但速度足以在运行期使用。

指令调度​

现代 CPU 是流水线执行的,如果相邻两条指令有数据依赖或者共用一个功能单元,就会出现冒险(hazard),迫使流水线插入气泡。指令调度就是在不改变语义的前提下重排指令,把独立指令穿插进依赖链之间。

例如 LOAD 后紧跟对该寄存器的使用,可能要等一个周期;如果调度器能把一条无关的加法插到中间,气泡就消失了。这块内容属于指令级并行性的范畴,会在下一章展开讨论。

窥孔优化​

代码生成完后,编译器还会用一个小"窗口"(几条指令)滑过代码,做局部替换,这就是窥孔优化(Peephole Optimization)。常见规则:

  • 冗余装载消除:STORE R, [x]; LOAD R, [x] 后半条可以直接删掉。
  • 常量折叠:MOV R, 3; ADD R, 4 合成 MOV R, 7。
  • 跳转折叠:JMP L1; L1: JMP L2 缩成 JMP L2;条件跳转跳到无条件跳转的目标可以直接改写。
  • 强度削弱:MUL R, 8 换成 SHL R, 3。

窥孔优化便宜、见效快,是几乎所有后端都必做的收尾环节。

现代实践​

工业级编译器都把这些技术打包在后端里。LLVM 后端把 IR 逐步下降(Legalize、Select、Schedule、Register Allocate、Emit),用 TableGen 描述目标机器,指令选择用 DAG 匹配或 GlobalISel,寄存器分配提供 basic、greedy、fast 多种策略。GCC 则通过 RTL 中间层和机器描述文件(.md)走类似的流程,同样含有指令选择、寄存器分配(IRA + LRA)、调度和 peephole 各个阶段。理解本章的这些概念,就能读懂它们的日志和调优选项,也能在写内联汇编、编译器插件或自定义 ISA 后端时少踩坑。