编译器构造/优化

一位维基教科书用户已提名此页面进行清理。
你可以帮助使其变得更好。请查看任何相关讨论。

优化

在现代计算机上，如果编译器能够在几秒钟内翻译一个中等大小的源程序（比如大约 1000 行），那么它就可以被认为具有令人满意的性能。获得具有令人满意性能的编译器的方法与获得任何性能良好的程序的方法大致相同。

使用好的算法进行设计。
确保你的数据结构与算法相匹配。
使用具有干净简单接口的模块进行结构化。
使用清晰直观的代码进行实现。
当存在整体性能问题时
- 以合理的细节测量实际性能。
- 识别有问题的区域。
- 重新设计和重新实现这些问题区域。

在本书中，我们将考虑各种算法和数据结构，并讨论它们对性能的可能影响。

请注意，实际测量至关重要，因为问题往往并不像你猜测的那样。对于你的初始实现，你可能已经选择了已知性能较差的简单算法，以便快速获得可运行的程序。然而，你仍然应该详细测量性能，因为可能存在其他来源导致（至少部分）你的问题。

如果你非常幸运，你的实现语言可能有一些可选的功能，用于选择性地测量 CPU 时间。注意，只对少数关键例程激活此功能；计时开销很容易超过小型例程的执行时间，并扭曲结果。

更常见的情况是，你不走运，必须在选定例程中显式添加计时代码；确保你可以轻松地禁用它并在需要时启用它。通常，你必须在例程的开头和结尾插入对某些 CPU 计时例程的调用，然后减去这两个值以获得该例程的时间，其中将包括该例程调用的任何例程的时间。

多年来，人们报告了对实际编译器性能的各种测量结果。已知会导致问题的特定区域包括

对于每个源字符，在词法分析期间进行多次例程调用。
在词法分析期间跳过空格。
跳过注释。
在语法分析期间解码紧密打包的解析表。
在语义分析期间在名称表中查找内容。
确定某个名称是保留关键字还是用户可定义的标识符。

可以在维基百科的编译器优化文章中找到优化方法的广泛列表。优化是一个非常丰富且复杂的主题，因此本章只尝试介绍基础知识。

编译器内的优化关注的是以某种方式改进生成的代码，同时确保结果相同。从技术上讲，本章更合适的名称可能是“改进”，因为编译器只尝试改进程序员请求的操作。优化分为三类

速度；改进生成的代码的运行时性能。这是最常见的优化
空间；减少生成的代码的大小
安全性；减少数据结构被破坏的可能性（例如，确保不会写入非法数组元素）

不幸的是，许多“速度”优化会使代码变大，而许多“空间”优化会使代码变慢——这被称为空间时间权衡。

常见的优化算法

常见的优化算法处理特定情况

无用代码消除
公共子表达式消除
复制传播
代码移动
归纳变量消除
强度削弱
函数分块

无用代码消除

无用代码消除是一种大小优化（尽管它也会带来一些速度提升），旨在从生成的代码中删除逻辑上不可能的语句。无用代码是在任何情况下都不会执行的代码，无论输入如何。

考虑以下程序

a = 5
if (a != 5) {
  // Some complicated calculation
}
...

很明显，复杂的计算永远不会执行；由于在if语句之前分配给a的最后一个值是常量，因此我们可以在编译时计算结果。简单地替换参数会得到if (5 != 5)，结果为false。由于if(false)语句的主体永远不会执行——它是无用代码，因此我们可以重写代码

a = 5
// Some statements

该算法用于识别和删除无用代码部分

公共子表达式消除

公共子表达式消除是一种速度优化，它旨在通过代码流识别表达式（或表达式的一部分）来减少不必要的重新计算，这些表达式将计算出相同的值：如果表达式以前已经计算过并且操作数的值自上次计算以来没有改变，则可以避免重新计算表达式。

考虑以下程序

a = b + c
d = e + f
g = b + c

在上面的示例中，第一条和最后一条语句的右侧是相同的，并且操作数的值在两条语句之间没有改变；因此，可以认为此表达式具有公共子表达式。

可以通过将公共子表达式的值存储在可以缓存其结果的临时变量中来避免公共子表达式。应用公共子表达式消除技术后，程序将变为

t₀ = b + c
a = t₀
d = e + f
g = t₀

因此，在最后一条语句中，避免了重新计算表达式b + c。

复制传播

给定一个赋值语句 x=y，将后面对 x 的使用替换为 y，前提是没有对 x 或 y 进行中间赋值。在这里，代码将变小。例如

        x[i]=a;
        sum=x[i]+a;
        
        instead of this we can use:
        x[i]=a;
        sum=a+a;

 For x[i]=a, is copy statements.Use of 'a' for 'x[i]',
whenever possible after copy statement.Here it may not
appear to be code improvement, but opens up scope
for other optimizations.

代码移动

维基百科在循环不变代码移动中包含相关信息

这种优化技术主要用于减少程序中的源代码行数。例如，考虑下面的代码

for (i = 0; i < n; ++i) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

计算x = y + z和x * x可以移到循环之外，因为它们在循环内是不变的——它们在循环的迭代中不会改变——所以我们的优化代码将类似于以下代码

x = y + z;
t1 = x * x;
for (i = 0; i < n; ++i) {
    a[i] = 6 * i + t1;
}

此代码可以进一步优化。例如，强度削弱可以删除循环内的两个乘法运算（6*i和a[i]）。

另一个代码移动的例子

for(i=0;i<10;i++)
{
  a = a + c;
}

在上述代码中，a = a + c 可以移到 'for' 循环之外，新代码为

a = a + 10*c;

归纳变量消除

如果一个变量在循环的每次迭代中增加或减少一个固定量，则该变量被称为归纳变量。例如

      for(i=0; i<10; i++)
       {
        j=17*i;
       }

这里 i、j 是归纳变量。如果循环中有两个或多个归纳变量，则可能可以消除除一个以外的所有变量。最终，我们可以从这个循环中消除 j。

强度削弱

这个概念指的是编译器优化方法，即用更便宜的机器指令替换一些机器指令，同时保持结果等效。由于一些操作符具有不同的强度，即在内存中使用不同的空间。这种优化类型可以生成很高的收益，尤其是在针对不同的硬件时，编译器可以了解它可以利用的细微差异。

例如，*(乘法) 的强度“高于”+(加法)。
因此，在这种优化类型中，强度更高的操作符将被强度更低的操作符替换。

示例
假设
Length(S1 || S2)
其中 S1 和 S2 有一些值。

因此，如果我们应用该规则，则
Length(S1 || S2) ---(被替换为)--> [Length(S1) + Length(S2)]

因为 + 操作比 || 更便宜。
并且从上面的例子可以清楚地看出，结果不会改变。

函数分块

函数分块是一种编译器优化，用于提高代码局部性。通过分析信息，将很少执行的代码移出主函数体。这使得包含很少执行代码的内存页面可以被换出。