optimizing_cpp(6)

六、编译器层次的优化

1.编译器如何优化

1.1内联函数

编译器可以自动在调用函数时将函数名替换为函数体，即转为内联函数。

内联函数优点：

节约了调用、返回和参数传递的开销。
因为代码变得连续了，代码缓存的效率会更高。
如果只调用一次内联函数，那么代码就会变得更小。
函数内联可以使其他优化成为可能，下面会详细描述。

1.2常量折叠（constant folding）和常量传播(constant propagation)

常量折叠是指只包含常量的表达式或子表达式将会被计算结果替换：

1
2
3

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

编译器将会替换成下面的代码：

1 2	// Example 8.2b a = b + 0.666666666666666666667;

常量传播指在依赖链上，若上游结果为常量，下游结果也为常量，则都会被替换成常量

// 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;

当表达式包含不能被内联的函数或者不能再编译时期计算的时候，常量折叠和常量传播就不可能起作用。例如：

1
2
3

// Example 8.4

double a = sin(0.8);

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

1.3消除指针

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

// Example 8.5a

void Plus2 (int * p)
{
    *p = *p + 2;
}
int a;
Plus2 (&a);

可能被编译器替换成：

1
2
3

// Example 8.5b

a += 2;

1.4消除公共子表达式

如果相同的子表达式出现多次，那么编译器可能只会计算一次。例如：

// 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;

1.5寄存器变量

最常用的变量存储被在寄存器中

在 32位系统中，整数寄存器变量的最大数量大约是 6个，在 64位系统中大约是 14个。

在 32位系统中，浮点寄存器变量的最大数量为 8个，在 64位系统中为 16个。一些编译器很难在 32位系统中生成浮点寄存器变量，除非启用了SSE2（或更高版本）指令集。

编译器将选择最常用的变量做为寄存器变量。这包括指针和引用，它们可以存储在整数寄存器中。寄存器变量的典型候选对象是临时中间变量、循环计数器、函数参数、指针、引用、this 指针、公共子表达式和归纳变量（见下文）。

如果一个变量被取地址，也就是有指针指向它，此时它一定在内存中就不能在寄存器中，因此，对于可能受益于寄存器存储的变量，尽量避免指针或者引用。

1.6活动范围分析

变量的活动范围是指变量被使用的代码范围。对于活动范围不重叠的变量，编译器优化可以使用相同的寄存器。这在可用寄存器数量有限的时候是非常有用的。例如：

// 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 就不能使用相同的寄存器，因为它们的活动范围现在重叠了。

编译器通常不会将此原则用于存储在内存中的对象。对于不同的对象，它不会使用相同的内存区域，即使它们的活动范围不重叠。

1.7合并相同的分支

通过合并相同的代码片段，可以使代码更加紧凑。例如：

// 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.;

1.8消除跳转

可以通过复制它跳转到的代码来避免跳转。例如：

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;
    }
}

如果条件可以被简化为永远为真或永远为假，则可以消除分支：

// Example 8.10a

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

可以被简化为：

1
2
3

// 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;
    }
}

1.9循环展开

如果循环体非常小，或者它使进一步优化成为可能，那么这可能是有利的。重复计数非常小的循环可以完全展开，以避免循环开销。例如：

// 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;

这样就可以发挥流水线的优势。

不幸的是，一些编译器展开太多。过多的循环展开不是最优的，因为它会占用太多的代码缓存空间，并且会填满某些微处理器的循环缓冲区。在某些情况下，关闭编译器中的循环展开选项是有用的。

1.10移动循环中的不变代码

如果计算独立于循环计数器，则可以将其移出循环。例如：

// 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;
}

1.11归纳变量（Induction variables）

循环计数器的线性函数表达式可以通过在前一个值上添加一个常数来计算。例如：

// 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 有硬件可以寄计算 index 乘上 8。

1.12排序

编译器可以为了并行执行对指令重新排序。例如：

// 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 更容易地对指令进行重新排序。

1.13代数化简

多数编译器可以使用代数的基本定律来化简简单的代数表达式。例如，编译器可以将表达式 -(-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 的值是 $-100+100+100 = 100$。现在，根据代数规则，我们可以这样写：

1	y = c + b + a;

如果子表达式 c+b 可以在其他地方重用，那么这可能很有用。在这个例子中，我们使用的是 8 位整数，范围从-128到+127。整数溢出将使值反转（wrap around）。127 加 1 等于 -128，减 1 等于 -128。计算 c+b 会产生溢出，结果是 -56 而不是 200。接下来，我们将 -100 加到 -56 中，这将产生一个下溢，得到 100，而不是 -156。令人惊讶的是，我们得到了正确的结果，因为向上溢出和向下溢出相互抵消了。这就是为什么对整数表达式使用代数操作是安全的（<、<=、> 和 >= 运算符除外）。

同样的讨论不适用于浮点表达式。浮点变量在上溢和下溢时，不会反转。浮点变量的范围非常大，除了在特殊的数学应用中，我们不必太担心上溢和下溢。但是我们必须担心精度的损失。让我们用浮点数重复上面的例子：

// 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。浮点类型的精度大约为7位有效数字，因此 b+c 的值四舍五入为 100000000。把 a 加到这个数上得到 0，而不是 1.23456。

这里讨论的结果是，改变浮点操作数的顺序，就有丢失精度的风险。除非你指定一个允许不需要精确的浮点运算的选项，否则编译器不会这么做。即使打开了所有相关的优化选项，编译器也不会执行诸如 0/a = 0这样的明显简化，因为如果 a 为 0、无穷大或 NAN（不是一个数字），这将是无效的。不同的编译器的行为不同，因为对于哪些不精确应该被允许，哪些不应该被允许，存在不同的观点。

不能依赖编译器对浮点代码执行任何代数消减，只能依赖于对整数代码进行最简单的缩减。手动消减会更安全。我测试了在7个不同的编译器，简化各种代数表达式的能力。结果如下表8.1所示。

1.14去虚拟化（Devirtualization）

如果知道所需要虚函数的版本，编译器优化可以绕过虚函数表查找，直接调用虚函数。例如：

// 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，而不使用虚函数表。不幸的是，很少有编译器能够进行这种优化。

2.不同编译器的比较

Agner Fog对不同编译器做了比较，如下表，可以作为参考

Optimization method	Microsoft	Borland	Intel	Gnu	PathScale	PGI	Digital Mars	Watcom	Codeplay
Function inlining	X	-	X	X	X	X	-	-	X
Constant folding	X	X	X	X	X	X	X	X	X
Constant propagation	X	-	X	X	X	X	-	-	X
Pointer elimination	X	X	X	X	X	X	X	X	X
Common subexpression elimin, integer	X	(X)	X	X	X	X	X	X	X
Common subexpression elimin, float	X	-	X	X	X	X	-	X	X
Register variables, integer	X	X	X	X	X	X	X	X	X
Register variables, float	X	-	X	X	X	X	-	X	X
Live range analysis	X	X	X	X	X	X	X	X	X
Join identical branches	X	-	-	X	-	-	-	X	-
Eliminate jumps	X	X	X	X	X	X	-	X	X
Eliminate branches	X	-	X	X	X	X	-	-	-
Remove branch that is always true/false	X	-	X	X	X	X	X	X	X
Loop unrolling	X	-	X	X	X	X	-	-	X
Loop invariant code motion	X	-	X	X	X	X	X	X	X
Induction variables for array elements	X	X	X	X	X	X	X	X	X
Induction variables for other integer expressions	X	-	X	X	X	-	X	X	X
Induction variables for float expressions	-	-	-	-	-	-	-	-	-
Automatic vectorization	-	-	X	X	X	X	-	-	X
Devirtualization	-	-	-	X	-	-	-	-	-
Profile-guided optimization	X	-	X	X	X	X	-	-	-
Whole program optimization	X	-	X	X	X	-	-	-	-

Integer algebra reductions:
`a+b = b+a`	X	(X)	X	X	X	X	-	X	X
`ab = ba`	X	(X)	X	X	X	X	-	X	X
`a+b+c = a+(b+c)`	X	-	X	X	-	-	X	X	-
`a+b+c = c+a+b`	X	-	-	X	-	-	-	-	-
`a+b+c+d = (a+b)+(c+d)`	-	-	X	X	-	-	-	-	-
`ab+ac = a*(b+c)`	X	-	X	X	X	-	-	-	X
`axxx+bxx+cx+d = <br>((ax+b)x+c)*x+d</br>`	X	-	X	X	X	-	X	X	X
`XXXXX*X=((X<sup>2</sup>)<sup>2</sup>)<sup>2</sup>`	-	-	-	X	-	-	-	-	-
`a+a+a+a=a*4`	X	-	X	X	-	-	-	-	X
`-(-a)=a`	X	-	X	X	X	X	X	X	-
`a-(-b)=a+b`	X	-	X	X	X	X	-	X	-
`a-a = 0`	X	-	X	X	X	X	X	X	X
`a+0 = a`	X	X	X	X	X	X	X	X	X
`a*0 = 0`	X	X	X	X	X	X	X	-	X
`a*1 = a`	X	X	X	X	X	X	X	X	X
`(-a)(-b) = ab`	X	-	X	X	X	-	-	-	-
`a/a = 1`	-	-	-	-	X	-	-	-	X
`a/1 = a`	X	X	X	X	X	X	X	X	X
`0/a = 0`	-	-	-	X	X	-	-	X	X
`(-a == -b) = (a == b)`	-	-	-	X	X	-	-	-	-
`(a-c == b+c) = (a == b)`	-	-	-	-	X	-	-	-	-
`!(a < b) = (a >= b)`	X	X	X	X	X	X	X	X	X
`(a<b && b<c && a<c) = (a<b && b<c)`	-	-	-	-	-	-	-	-	-
Multiply by constant = shift and add	X	X	X	X	-	X	X	X	-
Divide by constant = multiply and shift	X	-	X	X	X	(-)	X	-	-

Floating point algebra reductions:
`a+b = b+a`	X	-	X	X	X	X	-	-	X
`ab = ba`	X	-	X	X	X	X	-	-	X
`a+b+c = a+(b+c)`	X	-	X	X	-	-	-	-	-
`(a+b)+c = a+(b+c)`	-	-	X	X	-	-	-	-	-
`abc = a(bc)`	X	-	X	-	-	-	-	-	-
`a+b+c+d = (a+b)+(c+d)`	-	-	-	X	-	-	-	-	-
`ab+ac = a*(b+c)`	X	-	-	-	X	-	-	-	-
`axxx+bxx+cx+d = <br>((ax+b)x+c)*x+d</br>`	X	-	X	X	X	-	-	-	-
`XXXXX*X=((X<sup>2</sup>)<sup>2</sup>)<sup>2</sup>`	-	-	-	X	-	-	-	-	-
`a+a+a+a=a*4`	X	-	X	X	-	-	-	-	-
`-(-a)=a`	-	-	X	X	X	X	X	X	-
`a-(-b)=a+b`	-	-	-	X	X	X	-	X	-
`a+0 = a`	X	-	X	X	X	X	X	X	-
`a*0 = 0`	-	-	X	X	X	X	-	X	X
`a*1 = a`	X	-	X	X	X	X	X	-	X
`(-a)(-b) = ab`	-	-	-	X	X	X	-	-	-
`a/a = 1`	-	-	-	-	X	-	-	-	X
`a/1 = a`	X	-	X	X	X	-	X	-	-
`0/a = 0`	-	-	-	X	X	-	-	X	X
`(-a == -b) = (a == b)`	-	-	-	X	X	-	-	-	-
`(-a > -b) = (a < b)`	-	-	X	X	-	-	-	-	X
Divide by constant = multiply by reciprocal	X	X	-	X	X	-	-	X	-

Boolean algebra reductions:
`!(!a) = a`	X	-	X	X	X	X	X	X	X
`(a&&b)\|\|(a&&c) = a&&(b\|\|c)`	X	-	X	X	X	-	-	-	-
`!a && !b = !(a\|\|b)`	X	X	X	X	X	X	X	X	X
`a && !a = false`,`a \|\| !b = true`	X	-	X	X	X	X	-	-	-
`a && true = a`,`a \|\| false = a`	X	X	X	X	X	X	X	X	-
`a && false = false`,`a \|\| true = true`	X	-	X	X	X	X	X	X	-
`a && a = a`	X	-	X	X	X	X	-	-	-
`(a&&b) \|\| (a&&!b) = a`	X	-	-	X	X	-	-	-	-
`(a&&b) \|\| (!a&&c) = a ? b : c`	X	-	X	X	-	-	-	-	-
`(a&&b) \|\| (!a&&c) \|\| (b&&c) = a ? b : c`	X	-	-	X	-	-	-	-	-
`(a&&b) \|\| (a&&b&&c) = a&&b`	X	-	-	X	X	-	-	-	-
`(a&&b) \|\| (a&&c) \|\| (a&&b&&c) = a&&(b\|\|c)`	X	-	-	X	X	-	-	-	-
`(a&&!b) \|\| (!a&&b) = a XOR b`	-	-	-	-	-	-	-	-	-

Bit vector algebra reductions:
`~(~a) = a`	X	-	X	X	X	X	X	-	-
`(a&b)\|(a&c) = a&(b\|c)`	X	-	X	X	X	X	-	-	X
`(a\|b)&(a\|c) = a\|(b&c)`	X	-	X	X	X	X	-	-	X
`~a & ~b = ~(a \| b)`	-	-	X	X	X	X	-	-	-
`a & a = a`	X	-	-	X	X	X	-	-	X
`a & ~a = 0`	-	-	-	X	X	X	-	-	-
`a & -1 = a`,`a \| 0 = a`	X	-	X	X	X	X	X	X	X
`a & 0 = 0`,`a \| -1 = -1`	X	-	X	X	X	X	X	X	X
`(a&b) \| (~a&c) \| (b&c) = (a&b) \| (~a&c)`	-	-	-	-	-	-	-	-	-
`a&b&c&d = (a&b)&(c&d)`	-	-	-	X	-	-	-	-	-
`a ^ 0 = a`	X	X	X	X	X	-	X	X	X
`a ^ -1 = ~a`	X	-	X	X	X	-	X	X	-
`a ^ a = 0`	X	-	X	X	X	X	-	X	X
`a ^ ~a = -1`	-	-	-	X	X	X	-	-	-
`(a&~b) \| (~a&b) = a ^ b`	-	-	-	-	-	-	-	-	-
`~a ^ ~b = a ^ b`	-	-	-	X	X	-	-	-	-
`a<<b<<c = a<<(b+c)`	X	-	X	X	X	-	-	X	X

Integer XMM (vector) reductions:
Common subexpression elimination	X	n.a.	X	X	X	-	n.a.	n.a.	X
Constant folding	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a+b = b+a`, `ab = ba`	-	n.a.	-	X	-	-	n.a.	n.a.	X
`(a+b)+c = a+(b+c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`ab+ac = a*(b+c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`XXXXX*X=((X<sup>2</sup>)<sup>2</sup>)<sup>2</sup>`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a+a+a+a = a*4`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`-(-a) = a`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a-a = 0`	-	n.a.	X	-	-	-	n.a.	n.a.	-
`a+0 = a`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a*0 = 0`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a*1 = a`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`(-a)(-b) = ab`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`!(a < b) = (a >= b)`	-	n.a.	-	-	-	-	n.a.	n.a.	-

Floating point XMM (vector) reductions:
`a+b = b+a`, `ab = ba`	X	n.a.	-	X	-	-	n.a.	n.a.	X
`(a+b)+c = a+(b+c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`ab+ac = a*(b+c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`-(-a) = a`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a-a = 0`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a+0 = a`	-	n.a.	X	-	-	-	n.a.	n.a.	-
`a*0 = 0`	-	n.a.	X	-	-	-	n.a.	n.a.	-
`a*1 = a`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a/1 = a`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`0/a = 0`	-	n.a.	X	X	-	-	n.a.	n.a.	-
Divide by constant = multiply by reciprocal	-	n.a.	-	-	-	-	n.a.	n.a.	-

Boolean XMM (vector) reductions:
`~(~a) = a`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`(a&b)\|(a&c) = a&(b\|c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a & a = a`, `a \| a = a`	-	n.a.	X	X	-	-	n.a.	n.a.	-
`a & ~a = 0`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a & -1 = a`, `a \| 0 = a`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a & 0 = 0`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a \| -1 = -1`	-	n.a.	-	-	-	-	n.a.	n.a.	-
`a ^ a = 0`	-	n.a.	X	X	-	-	n.a.	n.a.	-
`andnot(a,a) = 0`	-	n.a.	-	X	-	-	n.a.	n.a.	-
`a<<b<<c = a<<(b+c)`	-	n.a.	-	-	-	-	n.a.	n.a.	-

Tabel 8.1. Comparison of optimizations in different C++ compilers

测试中所有相关的优化选项都被打开，包括放宽浮点精度。被测试的编译器版本如下：

Microsoft C++ Compiler v. 14.00 for 80x86 / x64 (Visual Studio 2005).
Borland C++ 5.82 (Embarcadero/CodeGear/Borland C++ Builder 5, 2009).
Intel C++ Compiler v. 11.1 for IA-32/Intel64, 2009.
Gnu C++ v. 4.1.0, 2006 (Red Hat).
PathScale C++ v. 3.1, 2007.
PGI C++ v. 7.1-4, 2008.
Digital Mars Compiler v. 8.42n, 2004.
Open Watcom C/C++ v. 1.4, 2005.
Codeplay VectorC v. 2.1.7, 2004.

没有发现Microsoft、Intel、Gnu 和PathScale 编译器的 32位和 64位代码的优化功能有任何差异。

3.编译器优化的障碍

3.1无法跨模块优化

编译器除了正在编译的模块外，没有关于其他模块中的函数的信息。这阻止了它对函数调用进行优化。例如：

// Example 8.20
//module1.cpp

int Func1(int x)
{
    return x*x + 1;
}

//module2.cpp
int Func2()
{
    int a = Func1(2);
    ...
}

假如 Func1 和 Func2 在同一个模块中，那么编译器将能够进行函数内联和常量传播，并将 a 化简为常量5。但是在编译 module2.cpp 时，编译器没有关于 Func1 的必要信息。

解决这个问题最简单的方法是使用 #include 指令将多个 .cpp 模块组合成一个模块。这个方法适用于所有编译器。有些编译器有一个称为“全程序优化”的特性，它将支持跨模块的优化

3.2指针别名（pointer aliasing）

当通过指针或引用访问变量时，编译器可能无法完全排除所指向的变量与代码中的其他变量相同的可能性。例如：

// Example 8.21

void Func1 (int a[], int * p)
{
    int i;
    for (i = 0; i < 100; i++)
    {
        a[i] = *p + 2;
    }
}

void Func2()
{
    int list[100];
    Func1(list, &list[8]);
}

在这里，需要重新加载 *p 并计算 *p+2 100次，因为 p 所指向的值与循环过程中会发生变化的 a[] 中的一个元素相同。不允许假定 *p+2 是可以移出循环的循环不变代码。例 8.21确实是一个非常刻意的例子，但关键是编译器不能排除这种刻意的例子存在的理论可能性。因此，编译器不能假设 *p+2 是一个可以移动到循环外部的循环不变表达式。

大多数编译器都有一个假设没有指针别名（*/Oa* ）的选项。克服可能的指针别名障碍的最简单方法是打开这个选项。这要求你仔细分析代码中的所有指针和引用，以确保在代码的同一部分中没有以一种以上的方式访问任何变量或对象。如果编译器支持的，还可以通过使用关键字 __restrict 或 __restrict__ 告诉编译器某个特定指针不是任何变量的别名。

我们永远不能确定编译器是否接受关于没有指针别名的提示。确保代码得到优化的唯一方法是显式地进行优化。在例 8.21中，如果你确信指针不是数组中的任何元素的别名，那么可以先计算 *p+2 并将其存储在循环外部的临时变量中。这种方法要求你能够预先知道优化的障碍在哪里。

3.3动态内存分配

动态分配（使用new或malloc）的任何数组或对象都必须通过指针进行访问。对于程序员来说，指向不同动态分配的对象的指针没有重叠或混淆是很明显的，但是编译器通常看不到这一点。它还阻止了编译器以最佳的方式来对齐数据，或者阻止编译器知道对象是对齐的。最好在需要的函数中声明对象和固定大小的数组。

3.4纯函数（Pure functions）

纯函数的定义是：

如果函数的调用参数相同，则永远返回相同的结果。它不依赖于程序执行期间函数外部任何状态或数据的变化，必须只依赖于其输入参数。
该函数不会产生任何可观察的副作用，例如网络请求，输入和输出设备或数据突变（mutation）。

多次使用相同参数调用纯函数肯定会得到相同的结果。编译器可以消除包含纯函数调用的常见子表达式，并且可以移出包含纯函数调用的循环不变代码。不幸的是，如果函数是在不同的模块或函数库中定义的，编译器则无法知道函数是否为纯函数。

因此，当涉及纯函数调用时，如公共子表达式消除、常量传播和移动循环不变代码这种优化应该手动优化。

Gnu 编译器和用于Linux 的Intel 编译器都有一个属性，该属性可以用于声明函数原型，以告诉编译器这是一个纯函数。例如：

// Example 8.22

#ifdef __GNUC__
#define pure_function __attribute__((const))
#else
#define pure_function
#endif

double Func1(double) pure_function ;
double Func2(double x)
{
    return Func1(x) * Func1(x) + 1.;
}

在这里，Gnu 编译器将只调用 Func1一次，而其他编译器将会调用两次。

其他一些编译器（Microsoft，Intel )知道像 sqrt、pow和 log 这样的标准库函数是纯函数，但不幸的是，无法告诉这些编译器用户定义的函数是纯函数。

3.5虚函数和函数指针

编译器几乎不可准确地预测将调用虚函数的哪个版本，或者函数指针指向什么。因此，它不能内联这些函数，也不能对函数调用进行优化。

3.6代数化简

大多数编译器可以做简单的代数化简，比如-(a) = a，但是它们不能做更复杂的化简。代数化简是一个复杂的过程，这很难在编译器中实现。

由于数学的纯粹性（mathematical purity），许多代数化简是不被允许的。在许多情况下，可以构造一些晦涩的例子，其中化简会导致溢出或精度损失，特别是在浮点表达式中（参见第74页TODO）。编译器不能排除特定情况下某个特定化简无效的可能性，但是程序员可以。因此，在许多情况下有必要显式地进行代数化简。

整数表达式不太容易出现溢出和精度损失的问题，原因见代数化简。因此，编译器可以对整数表达式进行比浮点数表达式更多的化简。大多数涉及整数加法、减法和乘法的化简在所有情况下都是被允许的，而许多涉及除法和关系运算符（如“>”）的化简，由于数学的纯粹性是不被允许的。例如，由于存在隐藏的溢出的可能性，编译器不能将整数表达式 -a > -b 化简为 a < b。

六.2不同编译器的比较显示了编译器在某些情况下，能够进行哪些化简，以及不能进行哪些化简。编译器无法完成的所有化简都必须由程序员手动完成。

3.7浮点归纳变量

编译器不能生成浮点归纳变量的原因与它们不能对浮点表达式进行代数化简的原因相同。因此，有必要手动完成这项工作。当循环计数器的函数通过以前的值计算比使用循环计数器计算更有效时，这个方法就很有用。循环计数器的$n$次多项式的任何表达式都可以通过$n$次加法来计算，而不需要使用乘法。下面的例子展示了使用加法二阶多项式的原理：

// Example 8.23a. Loop to make table of polynomial

const double A = 1.1, B = 2.2, C = 3.3;  // Polynomial coefficients
double Table[100];                       // Table
int x; // Loop counter
for (x = 0; x < 100; x++)
{
    Table[x] = A*x*x + B*x + C;          // Calculate polynomial
}

这个多项式的计算通过两个归纳变量，只需要两个加法就可以完成：

// Example 8.23b. Calculate polynomial with induction variables

const double A = 1.1, B = 2.2, C = 3.3; // Polynomial coefficients
double Table[100];                      // Table
int x;                                  // Loop counter
const double A2 = A + A;                // = 2*A
double Y = C;                           // = A*x*x + B*x + C
double Z = A + B;                       // = Delta Y
for (x = 0; x < 100; x++)
{
    Table[x] = Y;                       // Store result
    Y += Z;                             // Update induction variable Y
    Z += A2;                            // Update induction variable Z
}

例8.23b中的循环中有两个循环依赖链（loop-carried dependency chain），即两个归纳变量 Y 和 Z。每个依赖链都有一个延迟，这个延迟与浮点加法的延迟相同。这个延迟足够小，说明该方法是合适的。一个较长的循环依赖链会使归纳变量方法变得不利，除非该值是从一个两次或多次迭代的值计算出来的。

如果你考虑到每个值都是从序列中位于 r 位置之前的值计算出来的，其中 r 是一个向量中的元素数或循环展开因子，那么归纳变量的方法也可以向量化。要在每种情况下找到正确的公式，需要一点数学知识。

3.8内联函数的非内联副本

函数内联的复杂性在于，同一个函数可能从另一个模块调用。为了在另一个模块中调用该函数，编译器必须生成一个内联函数的非内联的副本，如果没有其他模块调用这个函数，那么这个非内联副本就是无用代码。这种代码片段降低了缓存的效率。

有很多方法可以解决这个问题。如果一个函数没有被任何其他模块引用，那么将关键字 static 添加到函数定义中。这将告诉编译器不能从任何其他模块调用该函数。静态声明使编译器更容易评估使函数内联是否是最优的，并防止编译器生成未使用的内联函数副本。static关键字还使各种其他优化成为可能，由于这些函数在其他模块中是无法访问的，因此编译器不必遵守任何特定的函数调用约定。可以用 static 声明所有本地非成员函数。

不幸的是，这个方法并不适用于类成员函数，因为 static 关键字对于成员函数有不同的含义。可以通过在类定义中声明函数体来强制使成员函数内联。这将防止编译器生成函数的非内联副本，但它的缺点是，即使在不适合内联的情况下（例如，如果成员函数很大，并且从许多不同的地方调用），函数也总是内联的。

一些编译器有一个选项(Windows：/Gy,* Linux*：- fffunction -sections)，允许链接器删除未引用的函数。建议打开此选项

4.cpu优化的障碍

现代 CPU 可以通过乱序执行指令来进行很多优化，阻碍其优化的障碍就是第五节提到的依赖链。因此要避免长依赖链尤其是具有长延迟的循环依赖链。

5.编译器优化选项

一下介绍下常见的编译器优化选项

debug与release，调试版本在开发期间使用，发行版本最终使用。

大小优化与速度优化，当代码非常快时，希望可执行文件尽量小，或者当代码缓存非常关键时也希望软件大小尽量小。当cpu访问和内存访问消耗巨大时，应进行速度优化。

一些编译器提供配置分析引导的优化。其工作方式如下。首先，编译程序并使之支持分析。然后使用分析器进行测试运行，分析器确定程序流以及每个函数和分支执行的次数。然后，编译器可以使用这些信息来优化代码，并将不同的函数按最佳顺序排列。

一些编译器支持全程序优化。这可以通过两个步骤进行编译。所有源文件首先被编译成中间文件格式，而不是通常的目标文件格式。然后在第二步中将中间文件链接在一起后完成编译。寄存器分配和函数内联是在第二步中完成的。中间文件格式没有标准化。它甚至不兼容同一编译器的不同版本。因此，不可能以这种格式分发函数库。

其他编译器提供了将多个 .cpp 文件编译为单个对象文件的可能性。这使编译器能够在启用过程间优化时进行跨模块优化。一种更原始但更有效的方法是通过 #include 指令将所有源文件连接到一个文件中，并声明所有函数为静态或内联的。这将使编译器能够对整个程序进行过程间优化。

可以使用SSE2，AVX等向量指令集进行优化。

可以选择使用较新的指令集（当不需要兼容旧版本的cpu时）

可以选择关闭异常处理使代码更高效，前提是不需要异常处理。

可以关闭对运行时类型识别（RTTI）的支持。

如果你确定代码没有指针别名，请使用“假设没有指针混叠“（assume no pointer aliasing）选项。（在3.2中提到过）

如果选项“函数级链接”（function level linking）可用，可以打开该选项。

许多编译器都有“标准栈帧”（standard stack frame）或“帧指针“（frame pointer）选项。标准栈帧用于调试和异常处理。省略标准堆栈帧可以使函数调用更快，并节省出一个额外的寄存器用于其他目的。这是有利的，因为寄存器是一种稀缺资源。除非程序依赖异常处理，否则不要使用堆栈帧。

6.优化指令

某些关键字可以使编译器给出特定的优化，当然许多指令使特定于编译器的。

6.1适用于所有c++编译器的关键字

register：告诉编译器这是寄存器变量

volatile：告诉编译器不要优化此变量，此变量会一直在内存中

const：常量，编译器在许多情况下会优化常量，如常量展开和常量传递。

static：使用static修饰内联函数会使内联函数更加高效

6.2特定编译器的关键字

快速函数调用。__fastcall或者 __attribute__((fastcall))。fastcall 修饰符可以使函数调用在 32位模式下更快。前两个整型参数将会在寄存器而不是栈中传递（对于 CodeGear编译器 则是前三个参数）。快速调用函数在编译器之间不兼容。在 64位模式下不需要快速调用，因为参数已经在寄存器中传递的。

纯函数。__attribute__((const))（Linux only），制定函数位纯函数。这将允许消除公共子表达式和移动循环不变代码。

假设没有指针别名。__declspec(noalias) 或 __restrict 或 #pragma optimize("a", on)，假设没有指针别名。

数据对齐。__declspec(align(16)) 或 __atrribute__((aligned(16)))，指定数组和结构体的对齐。