代码生成
代码生成
代码生成器是编译器后端的最后一环,它的输入是中间表示(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 子树可能有多种覆盖方式,通过动态规划为每个节点计算"用某种模式生成的最小代价",自底向上就能得到全局最小代价的指令序列。