编译器中的优化

• 编译器如何优化
• • 函数内联
  • 常量折叠和常量传播
  • 指针消除
  • 公共子表达式消除
  • 寄存器变量
  • 生命周期分析
  • 合并相同的分支
  • 消除跳转
  • 循环展开
  • 循环不变代码移动
  • 归纳变量
  • 调度
  • 代数化简
  • 去虚拟化

编译器如何优化

现代编译器能够对代码做很多修改，以提高性能。了解编译器可以做什么，不可以做什么，对开发者来说是有用的。下边的小节描述了开发者需要了解的一些编译器优化的内容。

函数内联

编译器可以用被调用函数体来替换原来的函数调用。例子：

// Example 8.1a
float square (float a) {
      return a * a;
}

float parabola (float x) {
      return square(x) + 1.0f;
}

编译器可以用square里的代码替换对square的调用：

// Example 8.1b
float parabola (float x) {
      return x * x + 1.0f;
}

函数内联的好处有：

• 消除了调用与返回以及参数传递的开销。
• 代码缓存更好，因为代码变得连续。
• 如果被内联函数仅有一处调用，代码变得更小。
• 函数内联可以为其他优化创造机会，如下面解释那样。

函数内联的坏处是，如果被内联函数有多处调用且该函数大，代码变得更大。如果函数小且仅从一处或少数几个地方调用，编译器很可能内联它。

常量折叠和常量传播

仅包含常量的表达式或子表达式将被计算后的结果替代。例子：

// Example 8.2a
double a, b;
a = b + 2.0 / 3.0;

编译器将它替代为

// Example 8.2b
a = b + 0.666666666666666666667;

这实际上相当方便。写2.0 / 3.0比计算这个值并表示为十进制要更容易。建议将这样一个子表达式封装在括号里，确保编译器识别为子表达式。例如，b*2.0 / 3.0将被计算为(b*2.0) / 3.0，而不是b * (2.0 / 3.0)，除非你将常量子表达式封装在括号里。

常量可以通过一系列计算传播：

// Example 8.3a
float parabola (float x) {
      return x * x + 1.0f;
}

float a, b;
a = parabola (2.0f);
b = a + 1.0f;

编译器将它替代为

// Example 8.3b
a = 5.0f;
b = 6.0f;

如果表达式包含不能内联或在编译时刻计算的函数，不可能常量折叠与常量传播。例如：

// Example 8.4
double a = sin(0.8);

函数sin定义在一个单独的函数库中，你不能预期编译器能够内联这个函数并在编译时刻计算它。某些编译器能够在编译时刻计算大多数最常见的数学函数，比如sqrt与pow，但更复杂的函数不能，如sin。

指针消除

如果指向目标已知，指针或引用可以被消除。例子：

// Example 8.5a
void Plus2 (int * p) {
     *p = *p + 2;
}

int a;
Plus2 (&a);

编译器将它替代为

// Example 8.5b
a += 2;

公共子表达式消除

如果同一个子表达式出现多次，编译器可能仅计算一次。例子：

// Example 8.6a
int a, b, c;
b = (a+1) * (a+1);
c = (a+1) / 4;

编译器将它替代为

// Example 8.6b
int a, b, c, temp;
temp = a+1;
b = temp * temp;
c = temp / 4;

寄存器变量

最常用的变量保存在寄存器里（参考寄存器存储）。

在32位系统中，整数寄存器变量最大数量是大约6个，在64位系统中是14个。
在32位系统中，浮点寄存器变量最大数量是8个，在64位系统中是16个（如果AVX512指令集可用，则是32个）。在32位系统中，某些编译器创建浮点寄存器变量有困难，除非启用SSE2（或更新的）指令集。

编译器将选择最常用的变量用作寄存器变量。这包括指针与引用，它们可以保存在整数寄存器里。寄存器变量典型的候选有临时中间结果、循环计数器、函数参数、指针、引用、this指针、公共子表达式以及归纳变量（参见下面）。

如果一个变量有指针或引用援引它，则不能保存在寄存器中。因此，应该避免使用对可从寄存器储存获益的变量使用指针或引用。

生命周期分析

变量的生命期是使用该变量的代码范围。优化编译器可以对多个变量使用相同的寄存器，如果它们的生命期不重叠或者它们确定有相同的值。在可用寄存器数量有限时，这是有用的。例子：

// Example 8.7
int SomeFunction (int a, int x[]) {
     int b, c;
     x[0] = a;
     b = a + 1;
     x[1] = b;
     c = b + 1;
     return c;
}

在这个例子中，a，b与c可以共享同一个寄存器，因为它们的生命期不重叠。如果将c = b + 1改为c = a + 2，那么a与b不能共享寄存器，因为它们的生命期现在重叠了。

编译器通常不能对保存在内存里的对象使用这个原则。不能对不同的对象使用相同的内存区域，即使它们的生命期不重叠。如何创建共享相同内存区域的不同对象，后续会讨论。

合并相同的分支

通过合并相同的代码片段，代码可以变得更紧凑。例子：

// Example 8.8a
double x, y, z; bool b;

if (b) {
     y = sin(x);
     z = y + 1.;
}
else {
     y = cos(x);
     z = y + 1.;
}

编译器将它替换为

// Example 8.8b
double x, y; bool b;

if (b) {
     y = sin(x);
}
else {
     y = cos(x);
}
z = y + 1.;

消除跳转

通过拷贝要跳转的目标代码，可以避免跳转。例子：

// Example 8.9a
int SomeFunction (int a, bool b) {
     if (b) {
          a = a * 2;
     }
     else {
          a = a * 3;
     }
     return a + 1;
}

这个代码有从a = a*2;到return a+1;的跳转。编译器可以通过拷贝return语句消除这个跳转：

// Example 8.9b
int SomeFunction (int a, bool b) {
     if (b) {
          a = a * 2;
          return a + 1;
     }
     else {
          a = a * 3;
          return a + 1;
     }
}

如果条件可以总是被约简为true或false，可以消除分支：

// Example 8.10a
if (true) {
     a = b;
}
else {
     a = c;
}

可以被约简为：

// Example 8.10b
a = b;

如果根据前一个分支条件已知，分支也可以被消除。例子：

// Example 8.11a
int SomeFunction (int a, bool b) {
     if (b) {
          a = a * 2;
     }
     else {
          a = a * 3;
     }

     if (b) {
          return a + 1;
     }
     else {
          return a - 1;
     }
}

编译器可以将这约简为：

// Example 8.11b
int SomeFunction (int a, bool b) {
     if (b) {
          a = a * 2;
          return a + 1;
     }
     else {
          a = a * 3;
          return a - 1;
     }
}

循环展开

如果要求高度优化，某些编译器将展开循环。参考循环展开。如果循环体非常小或者它开启了进一步优化的可能，这可能是有好处的。重复计数很小的循环可以被完全展开，以避免循环开销。例子：

// Example 8.12a
int i, a[2];
for (i = 0; i < 2; i++) a[i] = i+1;

编译器将这约简为：

// Example 8.12b
int a[2];
a[0] = 1; a[1] = 2;

不幸，某些编译器展开太多。过度的循环展开不是最优的，因为它在代码缓存中占据了太多空间，并填满某些微处理器所具有的循环缓冲。在某些情形里，关闭编译器中循环展开选项可能是有帮助的。

循环不变代码移动

如果一个计算不依赖于循环计数器，可以把它移出循环。例子：

// Example 8.13a
int i, a[100], b;
for (i = 0; i < 100; i++) {
     a[i] = b * b + 1;
}

编译器可能将这改变为：

// Example 8.13b
int i, a[100], b, temp;
temp = b * b + 1;
for (i = 0; i < 100; i++) {
     a[i] = temp;
}

归纳变量

一个循环计数器的线性函数的表达式，可以通过将先前值加上一个常量来计算。例子：

// Example 8.14a
int i, a[100];
for (i = 0; i < 100; i++) {
     a[i] = i * 9 + 3;
}

为了避免乘法，编译器可能把它改变为：

// Example 8.14b
int i, a[100], temp;
temp = 3;
for (i = 0; i < 100; i++) {
     a[i] = temp;
     temp += 9;
}

归纳变量通常用于计算数组元素的地址。例子：

// Example 8.15a
struct S1 {double a; double b;};
S1 list[100]; int i;
for (i = 0; i < 100; i++) {
     list[i].a = 1.0;
     list[i].b = 2.0;
}

为了访问list中的一个元素，编译器必须计算其地址。list[i]的地址等于list的起始地址加上i*sizeof(S1)。这是可以通过归纳变量计算的i的线性函数。编译器可以使用相同的归纳变量来访问list[i].a与list[i].b。它还消除了i，在这个归纳变量的最终值可以预先计算时，把它用作循环计数器。这将代码约简为：

// Example 8.15b
struct S1 {double a; double b;};
S1 list[100], *temp;
for (temp = &list[0]; temp < &list[100]; temp++) {
     temp->a = 1.0;
     temp->b = 2.0;
}

因数sizeof(S1) = 16实际上隐藏在例子8.15b中的C++语法背后。&list[100]的整数表示是(int)(&list[100]) = (int)(&list[0]) + 100*16，且temp++实际上把temp的整数值加上16。

编译器不需要归纳变量来计算简单类型的数组元素的地址，因为对数组元素地址的计算，如果该地址可以表示为基址加上常量加上索引乘以因子1、2、4或8，CPU有硬件支持；其他非基础类型则不可以。如果例子8.15a中的a与b是float，而不是double，sizeof(S1)将是8，将不需要归纳变量，因为CPU对索引乘8有硬件支持。

常见的编译器不会对浮点表达式或更复杂的整数表达式创建归纳变量。如何对多项式计算使用归纳变量，后续再讨论。

调度

为了并行执行的目的，编译器可以重排指令。例子：

// Example 8.16
float a, b, c, d, e, f, x, y;
x = a + b + c;
y = d + e + f;

编译器可以交错这个例子中的两个公式，首先计算a+b，然后d+e，然后第一个和加上c，第二个和加上f，然后第一个结果保存在x，最后第二个结果保存在y中。这样的目的是帮助CPU并行进行多个计算。现代CPU实际上能够无需编译器的帮助重排指令，但编译器可以使重排对CPU更容易。

代数化简

大多数编译器可以使用基本代数规则化简简单的代数表达式。例如，编译器会将表达式-(-a)改为a。

我不认为程序员会常常写像-(-a)的表达式，但这样的表达式可能作为其他优化的一个结果，比如函数内联。作为宏展开的结果，可约简表达式也相当常见。

不过，程序员确实经常写出可以约简的表达式。这是因为非约简表达式更好地解释了程序背后的逻辑，或者因为程序员没有想过代数约简。例如，程序员倾向于写if (!a && !b)，而不是等价的if (!(a||b))，即使后者少一个操作符。幸好，所有的编译器都能够进行这个情形的约简。

你不能期待编译器约简复杂的代数表达式。例如，一个编译器能够将(a*b*c)+(c*b*a)约简为a*b*c*2。在编译器中实现许多代数规则是相当困难的。在布尔代数的情形里，实现一个可以约简任何表达式的通用算法（比如Quine-McCluskey或Espresso）是可能的，但我测试过的编译器看起来没有这样做的。

相比浮点表达式，编译器更擅长约简整数表达式，即使两者的代数规则是相同的。这是因为浮点表达式的代数操作可能有预期外的效应。这个效应可由下面的例子展示：

// Example 8.17
char a = -100, b = 100, c = 100, y;
y = a + b + c;

根据代数规则，可以写：

y = c + b + a;

如果子表达式c+b可以在别处重用，这可能是有益的。现在设想：a是一个大的负数，b和c是大的正数，c+b产生了溢出。整数溢出会产生值回绕，从而产生一个负值。幸运地，c+b的溢出被后续加上a后的另一个溢出抵消了。a+b+c产生了和c+b+a相同的结果，尽管后者涉及了上溢和下溢，而前者没有。这就是整数表达式的代数操作是安全的原因（除了<，<=，>与>=操作符）。

相同的结论不适用于浮点表达式。在上溢与下溢时，浮点变量不会回绕。浮点变量的范围是如此大，我们无需太担心上溢与下溢，除了在特殊的数学应用中。但我们必须考虑精度损失。让我们使用浮点值重复上面的例子：

// Example 8.18
float a = -1.0E8, b = 1.0E8, c = 1.23456, y;
y = a + b + c;

这里的计算给出a+b=0，然后0+1.23456 = 1.23456。但如果我们改变操作数的次序，首先加b与c，将不会得到相同的结果。b+c = 100000001.23456。float类型大约能保存7位有效数字，因此b+c的值将被取整到10000000。在向这个值加上a时，我们得到0，而不是1.23456。

结论是，改变浮点操作数的次序有损失精度的风险。编译器将不会这样做，除非你指定允许浮点计算损失精度的选项。即使打开所有相关的优化选项，编译器将不会进行这样明显的约简，如0/a = 0，因为如果a是0或无穷或NAN（不是一个数字），表达式将是无效的。不同的编译器行为不同，因为它们允许或不允许精度损失的不同选项。

你不能依赖编译器在浮点代码上进行任何代数约简。手动进行约简更安全。

去虚拟化

若已知需要哪个版本的虚函数，优化编译器可以绕过用于虚函数调用的虚表查找。例子：

// Example 8.19. Devirtualization
class C0 {
public:
     virtual void f();
};

class C1 : public C0 {
public:
     virtual void f();
};

void g() {
     C1 obj1;
     C0 * p = & obj1;
     p->f(); // Virtual call to C1::f
}

没有优化时，编译器需要在虚表中查找，看调用p->f()去往C0::f还是C1::f。但优化编译器将看到p总是指向类C1的一个对象，因此它可以直接调用C1::f，无需使用虚表。不幸的是，只有少数编译器能够进行这个优化。