编译器设计中的局部优化

优化是编译过程中的一个重要阶段。有多种类型的优化。我们在之前的章节中介绍了全局优化的概念，这里将解释局部优化的作用。

当我们想要让程序运行更快时，很容易想到大的改动或复杂的解决方案。但有时，正是这些小的改动最为重要。局部优化就是编译器中的这样一个阶段，因为它专注于改进代码的特定部分。通过仔细检查局部优化中的指令序列，它使目标程序更小、更快。

在本章中，我们将了解局部优化是什么以及为什么它有用。

什么是局部优化？

局部优化完全关乎效率。它通过针对代码的小段落（通常在一个块或函数内）进行优化来实现改进。与关注整个程序的全局优化不同，局部优化处理代码中更小、更局部的部分。

局部优化有时被称为机器相关优化，因为它以特定于目标机器的方式改进指令。通过这样做，局部优化在保持相同输出的同时，为我们提供资源更少的目標程序。

为什么局部优化很重要？

我们必须理解为什么需要局部或机器相关的优化。想象你从车里把杂货搬到家里。如果你一次只拿一件物品，会很累人。但如果你优化一下，一次拿几件物品，就能节省时间和精力。局部优化的工作方式与之相同。

在编程中，一段未优化的指令序列可能会浪费资源，比如执行不必要的计算或重复努力。局部优化通过简化这些指令来修复这个问题。因此，它运行更快，内存使用更低。

局部优化的示例

为了正确理解局部优化，让我们看一个示例。考虑这段代码片段，其目标是计算三个变量之和，a + b + c −

lw $t0, a         # 将 a 加载到寄存器 $t0  
lw $t1, b         # 将 b 加载到寄存器 $t1  
add $t2, $t1, $t0 # 将 a 和 b 相加，将结果存储在 $t2  
sw $t2, temp1     # 将和 (a + b) 存储到 temp1  
lw $t2, temp1     # 将 temp1 重新加载到寄存器 $t2  
lw $t1, c         # 将 c 加载到寄存器 $t1  
add $t2, $t1, $t2 # 将 c 加到 (a + b)，将结果存储在 $t2  
sw $t2, temp2     # 将最终结果 (a + b + c) 存储到 temp2  

这段代码能工作，但效率不高。如果我们仔细看标记为temp1的行，(a + b)的值被存储到内存中，然后又被加载回寄存器中使用。这个额外的步骤实际上没有帮助，只会减慢速度。

优化的指令序列

应用局部优化后，不必要的加载/存储操作被移除。优化后的代码如下 −

lw $t0, a         # 将 a 加载到寄存器 $t0  
lw $t1, b         # 将 b 加载到寄存器 $t1  
add $t2, $t1, $t0 # 将 a 和 b 相加，将结果存储在 $t2  
lw $t1, c         # 将 c 加载到寄存器 $t1  
add $t2, $t1, $t2 # 将 c 加到 (a + b)，将结果存储在 $t2  
sw $t2, temp2     # 将最终结果 (a + b + c) 存储到 temp2  

这里，通过跳过temp1步骤，我们消除了两条指令。这个小的改动可能看起来不大，但在更大的程序或重复操作中，它能产生显著的影响。

局部优化的技术

局部优化提供了一些巧妙的技巧来清理代码。让我们来看看几个关键技术 −

Load / Store Optimization

正如我们在示例中看到的，不必要的 load 和 store 操作可以被移除。这减少了内存访问，使程序运行更快。

Constant Folding

如果一个值可以在编译时计算出来，编译器就会用计算结果替换该计算。例如 −

int x = 3 * 5;

编译器不必在程序执行期间执行乘法运算，而是直接赋值 x = 15。

Eliminating Redundant Instructions

有时相同的指令在没有对输入进行任何更改的情况下会多次出现，而局部优化会消除这些重复项。

Strength Reduction

有时这涉及用更廉价的操作替换昂贵的操作。例如，将乘以 2 替换为左移操作。在大多数机器上，这更快。

局部优化的挑战

我们了解了局部优化的好处；现在让我们看看它的局限性 −

• Trade-offs − 简化代码的某一部分可能会使另一部分效率降低。找到合适的平衡点可能有些挑战。
• Machine-Dependence − 因为局部优化通常针对特定硬件定制指令，它在不同机器上可能无法发挥同样良好的效果。
• Code Clarity − 高度优化的代码可能更难理解或调试。这对于没有编写过它的开发者尤其如此。

虽然局部优化关注小段代码，但它的好处会累积起来。因此，通过改进单个代码块，它有助于提升程序的整体性能。这就像修补道路上的坑洞一样。看起来不如修建一条新高速公路那样重大，但它让旅程更顺畅、更快速。

同时，需要记住的是，局部优化只是整个工作的一部分。它与其他优化技术（如全局优化或更好的算法设计）结合使用时效果最佳。

关键局部优化技术

在本节中，我们将详细讨论一些重要的局部优化技术。

常量折叠

这种方法很有趣。它在编译时而非运行时评估常量表达式。如果一个算术运算仅涉及常量，则编译器会预计算结果并用常量值替换该表达式。

示例：优化前

int x = 5 * 2;  
int y = x + 10;  

中间表示 (IR) −

(MUL, 5, 2, x)  
(ADD, x, 10, y)    

常量折叠后，

由于 5 * 2 = 10，编译器将 x 替换为 10 −

(MOV, 10, , x)  
(ADD, 10, 10, y)    

它进一步简化为 −

(MOV, 10, , x)  
(MOV, 20, , y)   

在这里，编译器移除了不必要的计算并直接赋值。这个简单技巧使代码相当优化。

公共子表达式消除

公共子表达式消除 (CSE) 在一个基本块内识别并移除重复表达式。如果一个表达式重复出现，则编译器仅计算一次并重用结果。

示例：优化前

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

中间表示 (IR)

(ADD, b, c, T1)  
(ADD, T1, e, d)   

由于 b + c 被计算了两次，我们重用 T1 而非重复计算 −

经过 CSE 优化后，

(ADD, b, c, T1)  
(ADD, T1, e, d)    

在这里，我们可以看到它消除了冗余，并减少了指令数量。

死代码消除

死代码消除技术移除那些对程序输出没有影响的语句。

示例：优化前

int x = 10;  
x = 20;  
y = x * 2;     

中间表示 (IR)

(MOV, 10, , x)  
(MOV, 20, , x)  
(MUL, x, 2, y)       

由于 x = 10 从未被使用，因此编译器在优化后会移除它。

死代码消除后，

(MOV, 20, , x)  
(MUL, x, 2, y)       

它移除了不必要的指令，从而提升了性能。

强度削减

在这里，强度削减将计算代价高的操作替换为更简单、更快的操作。

示例：优化前

x = y * 8;        

乘法代价较高，但 y * 8 可以重写为 −

x = y << 3;         

中间表示 (IR)

(SHL, y, 3, x)         

移位 (SHL) 操作比乘法更快。这提升了性能。

窥孔优化

窥孔优化是最常被讨论的优化方案之一。它扫描基本块中的一小组指令（窥孔），并将低效模式替换为优化的版本。

示例：优化前

(MOV, x, R1)  
(ADD, R1, 0, R1)          

由于加 0 什么也不做，因此编译器移除该指令 −

窥孔优化后，

(MOV, x, R1)           

这使指令序列更短、更快。

示例：应用多种局部优化

考虑以下 Java 表达式 −

int a = (x + 2) * (x + 2);             

编译器生成的未优化原子序列 −

(ADD, x, 2, T1)  
(ADD, x, 2, T2)  
(MUL, T1, T2, a)               

我们已经了解了一组优化技术。如果我们看到它们实际应用，就能明白它们非常有用。例如，公共子表达式消除 (CSE) 识别到 x + 2 被计算了两次，我们只需计算一次并重用它。

强度削减 − 如果 MUL 是乘以 2 的幂，我们将其替换为 移位操作。

使用局部技术优化的代码 −

(ADD, x, 2, T1)  
(MUL, T1, T1, a)                 

在这里，仅剩下两个操作，这大大提升了效率。

Local Optimization 的实际应用

Local optimization 用于 −

• Compilers (GCC, LLVM, Clang) − 这使得编译代码的高效执行。
• Embedded Systems − 优化单个块并减少低功耗设备中的执行时间。
• JIT Compilers (Java, JavaScript, Python) − 提升解释型语言的运行时性能。

Local Optimization 技术的比较

下表突出了不同 local optimization 技术的目的和效果 −

结论

在本章中，我们解释了 local optimization 的概念及其在使程序更快、更高效方面的作用。从基础开始，我们探讨了 local optimization 如何关注代码的小部分以及其重要性。

通过一个简单示例，我们演示了移除不必要的 load/store 指令如何简化代码。我们还介绍了关键技术，如 constant folding 和 load/store optimization，以及这一过程中伴随的挑战。