窥孔优化

窥孔优化是一种优化编译器技术，在编译的后面阶段，寻找编译器生成的特定的指令序列，将该序列替换成性能更好的等效指令序列。该算法的可视范围极小，往往只能同时窥看几条指令，故名曰窥孔优化（指其犹如通过窥孔观察程序）。被优化掉的这少量指令序列被称为窥视孔或窗口。^[1]

例如：

• 对于指令序列：将寄存器A压入堆栈，然后立即将值弹出存回寄存器A的指令序列，窥孔优化删除这两条指令。
• 对于指令A加到A上，窥孔优化替换为算术左移。
• 对于浮点寄存器乘以8，窥孔优化会将浮点寄存器的指数部分加上3。
• 对于数组寻址操作将索引乘以4，将结果与基地址相加以获得指针值，然后解引用该指针，窥孔优化可能会使用一种硬件寻址模式，通过一条指令实现相同的结果。

1965年William Marshall McKeeman提出窥孔优化一词。^[2]

窥孔优化中常用的技术：^[3]

• 空序列——删除无用的操作
• 组合操作——用一项等价操作替换多项操作
• 代数定律 – 使用代数定律来简化或重新排序指令
• 特殊情况指令 – 使用为特殊操作数情况设计的指令
• 地址模式操作 – 使用地址模式来简化代码

还可以有其他类型的窥视孔优化。

以下为Java字节码

...
aload 1
aload 1
mul
...

可以替换为

...
aload 1
dup
mul
...

与大多数窥孔优化一样，这种优化对指令的效率做出了某些假设。例如，在这种情况下，假设dup操作（复制并推送到栈顶）比操作aload X（加载标识为X的局部变量并将其推送到栈上）更有效。

另一个例子是消除冗余load stores.

 a = b + c;
 d = a + e;

直接实现为

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add  c to the register, the register is now b+c
MOV R0, a  ; Copy the register to a
MOV a, R0  ; Copy a to the register
ADD e, R0  ; Add  e to the register, the register is now a+e [(b+c)+e]
MOV R0, d  ; Copy the register to d

但可以优化为

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add c to the register, which is now b+c (a)
MOV R0, a  ; Copy the register to a
ADD e, R0  ; Add e to the register, which is now b+c+e [(a)+e]
MOV R0, d  ; Copy the register to d

如果编译器在调用子例程之前将寄存器保存在栈上并在返回时恢复它们，则对子例程的连续调用可能会产生冗余栈指令。

假设编译器为每个过程调用生成以下Z80指令：

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR
 POP HL
 POP DE
 POP BC
 POP AF

如果有两个连续的子例程调用，它们将如下所示：

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 POP HL
 POP DE
 POP BC
 POP AF
 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

对于相同的寄存器，POP regs 后跟 PUSH 的序列通常是多余的。在冗余的情况下，窥孔优化将删除这些指令。在示例中，这将导致另一个冗余的 POP/PUSH 对出现在窥视孔中，并且这些将依次被删除。假设子程序 _ADDR2 不依赖于先前的寄存器值，则删除上例中的所有冗余代码最终将留下以下代码：

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

现代编译器经常使用模式匹配算法来实现窥孔优化。^[4]

• 目标码优化器（英语：Object code optimizer）
• Superoptimization（英语：Superoptimization）
• 源到源编译器

• The copt general-purpose peephole optimizer by Christopher W. Fraser
• The original paper