编译优化 - 窥孔优化
文章目录
代码编译优化旨在提升代码质量和性能,而窥孔优化(peephole optimization) 就是其中的一种优化技术,本文将简单介绍一下。
1、peephole optimization
窥孔优化类似于滑动窗口,针对一小组编译器生成的指令序列进行优化,而不需要过多关注上下文、控制流等。
比如对指令进行替换,提前定好了匹配的规则来进行操作。如下图中乘 8 的操作指令,可以优化替换为左移 3 的操作指令,这样就提升了指令执行的性能。
这里举例只用了单条指令来说明,实际是对指令序列来进行操作。在窥孔优化中,定义了很多的规则,如果能够匹配上,然后就会对其进行优化。大多数规则,是改写为性能更快或者指令更少的方式。
虽然窥孔优化只针对小部分指令序列进行优化,但是被其简化后的指令,实际上在整个上下文优化时,也可能得到了再次优化的机会。
通常这些规则都是人工手写的,但编译器并不会直接根据规则进行替换,有以下几个步骤:
- 给定一组指令序列来进行优化
- 计算每种可能得到的优化序列
- 比较结果是否与原指令序列一致
- 检查新的等价优化序列是否有更低的消耗,再决定是否替换
而实际实现不一定依据上面的步骤,在 LLVM 中的窥孔优化,看起来更像是按固定顺序优先级来进行的。它对 Machine IR 级别的函数来进行操作,在 PeepholeOptimizer::runOnMachineFunction
函数中可以看到,已经安排好固定的优化顺序了,如果前面的优化判断可以生效,就不进行判断后面的优化了。
由于只考虑一小部分的指令,也容易导致 bug 的发生,所以 LLVM 可以使用 Alive 工具来进行正确性的验证,之前有写过关于 Alive 的简介,其对于验证代码转换和优化操作非常重要。
而可能的一种 bug,比如在 x86 架构上有两种实现加法的指令方式,窥孔优化可能会进行替换。但这两种加法不完全等价,一种可能会影响到 carry-flag register(携带判断标识的寄存器),而另一种没有。编译器可能认为在比较的指令如 cmp 之后就没问题,但这时候进行窥孔优化就会产生 side-effect(副作用),对上下文产生了影响,实际上应该进行完整的语义分析验证来保证正确性。
2、优化技术
这里举一些窥孔优化可以进行的优化技术,有很多,不做一一列举了:
2.1、冗余消除(Redundant load and store elimination)
当然消除还应该判断 def-use 链路的相关指令,避免误删。
|
|
2.2、常量折叠(Constant folding)
|
|
2.3、强度消减(Strength Reduction)
|
|
参考
- Peephole optimization - wiki
- Peephole Optimization - pdf
- LLVM 中的窥孔优化
- Why Do Peephole Optimizations Work?
- Peephole Optimization in Compiler Design
- The CPython Peephole Optimizer and You
- Adding peephole optimization to Clang
- Practical formal techniques and tools for developing LLVM’s peephole optimizations
- Termination-Checking for LLVM Peephole Optimizations
- Verified Peephole Optimizations for CompCert
文章作者 calssion
上次更新 2023-11-05