MENU

编译器笔记--代码优化(低级优化)

July 15, 2023 • 阅读: 992 • 笔记&折腾

到目前为止讨论的所有优化都可以应用于程序的高级结构,而无需考虑特定的目标机器。

低级优化更多地从底层机器的特性角度进行思考和优化,实践案例:# 针对LLVM的RISCV后端的的codesize优化 (BLT to BLEZ)

窥孔优化

窥视孔优化是指非常狭隘地关注一小部分代码(可能只是两到三个指令)并在该部分内进行安全、集中的更改的任何优化。这些优化在编译的最后阶段很容易实现,但总体效果有限。

冗余负载消除是一种常见的窥孔优化。修改和使用同一变量的表达式序列很容易导致两条相邻指令将寄存器保存到内存中,然后立即再次加载相同的值:

// Before
MOVQ %R8, x
MOVQ x, %R8

// After
MOVQ %R8, x

一个细微的变化是,对不同寄存器的加载可以转换为寄存器之间的直接移动,从而节省不必要的加载和管道停顿:

// Before
MOVQ %R8, x
MOVQ x, %R9

// After
MOVQ %R8, x
MOVQ %R8, %R9

指令选择

在某些简单的代码生成方法中,其中 AST(或 DAG)的每个节点都被至少一条指令(在某些情况下,多条指令)替换。在丰富的 CISC 指令集中,单个指令可以轻松组合多个操作,例如取消引用指针、访问内存以及执行算术运算。
为了利用这些强大的指令,我们可以使用通过树覆盖来选择指令的技术。这个想法是首先将架构中的每个可能的指令表示为模板树,其中叶子可以是可以替换为指令的寄存器、常量或内存地址。

例如,X86 ADDQ 指令的一种变体可以将两个寄存器相加。这可用于在 DAG 中实现 IADD 节点,前提是 IADD 的叶子存储在寄存器中。一旦加法完成,ADDQ 将结果放置在与第二个参数相同的寄存器中。这全部表示为与 DAG 的一部分相匹配的树片段,以及选择特定寄存器编号后要发出的指令:

以下是一些可以表示为树模板的x86指令的更多示例:

顶部的简单指令只是将 DAG 中的一个实体替换为另一个实体:MOV $Cj, Ri 将常量转换为寄存器,而 MOV Mx, Ri 将内存位置转换为寄存器。更丰富的指令具有更多的结构:复数负载 MOV Cj(Rl,8), Ri 可用于表示加法、乘法和解引用的组合。
以上并不是完整的X86指令集。即使要描述一个重要的子集,也需要数百个条目,每个指令有多个条目来捕获每个指令的多个变化。 (例如,您需要一个用于两个寄存器上的 ADDQ 的模板,另一个用于寄存器-内存组合。)但这是一项可行的任务,并且可能比手写完整的代码生成器更容易完成。
编写完整的模板库后,代码生成器的工作是检查树中是否有与指令模板匹配的子树。当找到一个时,就会发出相应的指令(适当替换寄存器号等),并将树的匹配部分替换为模板的右侧。

例如,假设我们希望为语句 a[i] = b + 1; 生成 X86 代码。而a和i分别是基指针上方位置40和32的局部变量。
下图展示了树重写的步骤,在每个 DAG 中,方框表示与上图中的规则匹配的子树:

  1. 先执行左边的IADD来计算表达式的值。看看我们的模板表,没有 IADD 可以直接将内存位置添加到常量中。因此,我们选择规则 (2),它发出指令 MOVQ b, %R0 并将模板的左侧(内存位置)转换为右侧(寄存器 %R0)。
  2. 现在我们可以看到一个寄存器的IADD和一个常量,它与规则(4)的模板匹配。我们发出指令 ADDQ $1, %R0 并用寄存器 %R0 替换 IADD 子树。
  3. 现在让我们看看树的另一边。我们可以使用规则(5)来匹配从 %RBP+32 加载变量 i 的整个子树,发出指令 MOVQ 32(%RBP), %R1 并将子树替换为寄存器 %R1。
  4. 以类似的方式,我们可以使用规则(6)通过发出 LEAQ 40(%RBP), %R2 来计算 a 的地址。请注意,这实际上是专门用于寄存器和基址指针的三地址加法。与规则 4 不同,它不会修改源寄存器。
  5. 最后,模板规则 (7) 与剩余的大部分内容匹配。我们可以发出 MOVQ %R0,(%R2,%R1,8) ,它将 R1 中的值存储到 a 的计算数组地址中。模板的左侧被右侧替换,只留下寄存器 %R0。随着树完全缩减为单个寄存器,代码生成完成,并且寄存器%R0可以被释放。

在简单的代码生成方案下,这个 16 节点 DAG 将产生(至少)16 条输出指令。通过使用树覆盖,我们将输出减少为以下五个指令:

MOVQ b,%R0
ADDQ $1,%R0
MOVQ 32(%RBP),%R1
LEAQ 40(%RBP),%R2
MOVQ %R0,(%R2,%R1,8)