编译器优化 3 - 常量折叠和传播 - 察说花园

前面了解了 lto、thinlto、以及 inline 优化、死代码优化等。今天继续学习下常量折叠优化，

常量折叠和常量传播

常量折叠和常量传播有什么不同？它们似乎都做了同样的事情，而不是将常量保存到堆栈中或计算完整的算术表达式，而是简单地将其替换为可以在编译时获得的结果。两者之间有什么不同？

区别在于，常量传播不是将一个变量保存到堆栈中，因为我们知道它是一个常量，可以简单地将它插入到任何地方，它被用于机器代码中。而常数折叠是简单地评估，使用常数的表达式，并将结果代入机器码。

来吧，看一个例子

# 常量传播
x = 10
y = x + x + x
y = 10 + 10 + 10

# 常量折叠
y = 10 + 10 + 10
y = 30

这就是区别。常量传播只是用绑定的常量表达式替换绑定的变量，而常量折叠则是评估一个（无副作用的）表达式，其中所有输入都是编译时常量。

常量传播是一种编译器优化方法，它可以在编译期间用常量值替换变量或表达式，从而减少运行时的计算开销和代码大小。

常量传播有四种算法：简单常量传播、稀疏简单常量传播、条件常量传播和稀疏条件常量传播，它们的效率和精度各有不同。

常量折叠是一种与常量传播相关的优化方法，它可以将具有已知常量值的运算符表达式简化为操作数。

常量折叠是指在编译时识别和评估常量表达式的过程，而不是在运行时计算它们。常量表达式中的术语通常是简单的字面意义，例如整数字面意义 2，但它们也可能是变量，其值在编译时已经知道。考虑一下这个语句。

比如：i = 20* 20 * 10;

上面这个表达式，有 2 个乘号，很少有编译器的指令会对 2 个乘号做运算，并存到一个寄存器，比如我下才一个： mul_mul dst,src0,src1,src2,想这样的指令看起来就比较怪异。所以在编译的时候替换计算值为4000

常量折叠可以利用算术特性。如果 x 是数字，即使编译器不知道 x 的值，0*x 的值也是零。

注意，大部分编译器对 IEEE754 浮点数是无效的，因为 x 可能是 Infinity 或 NaN。不过，为了性能，某些编译器允许对常数这样做。

常数折叠可能不仅仅适用于数字。字符串和常量字符串的拼接可以被常量折叠。像 "abc"+"def"这样的代码可以被替换为 “abcdef“。

常数折叠和传播通常一起使用，以实现许多简化和减少，通过迭代交织，直到不再发生变化。所以继续来看看常量传播。

常数传播是在编译时将已知常数的值替换到表达式中的过程。这些常量包括上面定义的常量，以及应用于常量值的内在函数。考虑一下下面的伪代码。

  int x = 14;
  int y = 7 - x / 2;
  return y * (28 / x + 2)

把 x（传播 propagate）带入后，变成

  int x = 14;
  int y = 7 - 14 / 2;
  return y * (28 / 14 + 2);

继续传播，带入后的结果为：

  int x = 14;
  int y = 0;
  return 0;

举个维基百科例子，从至少需要 3 个寄存器和 7 条基础指令（别问，瞎猜的，具体数量还要取决于硬件的设计），一个分支，优化到只有一个寄存器的过程：

  int a = 30;
  int b = 9 - (a / 5);
  int c;

  c = b * 4;
  if (c > 10) {
     c = c - 10;
  }
  return c * (60 / a);

用一次常量的传播，然后是常量的折叠，得到

    int a = 30;
    int b = 3; //折叠 + 传播
    int c;

    c = b * 4;
    if (c > 10) {
        c = c - 10;
    }
    return c * 2; // 折叠

再重复 2 次：

  int a = 30;
  int b = 3;
  int c;

  c = 12;
  if (true) { // 传播 + 折叠
     c = 2;   // 传播 + 折叠
  }
  return c * 2;

由于 a 和 b 已经被简化为常数，并且它们的值在它们出现的地方都被替换了，编译器现在应用死代码消除法来丢弃它们，进一步减少了代码。

  int c;
  c = 12;

  if (true) {
     c = 2;
  }
  return c * 2;

我们肉眼就能看出来，if 这个分支里面始终都会别执行，难道编译器不行？别急，继续优化。

在上面的代码中，根据编译器框架，它可以是 1 或任何其他布尔结构，而不是 true。通过传统的常数传播，我们只能得到这么多的优化。它不能改变程序的结构。

还有一个类似的优化，叫做稀疏条件常量传播，它根据 if 条件选择适当的分支，编译器现在可以检测到 if 语句总是评估为真，c 本身可以被消除，进一步缩小代码。

return 4

这个伪代码构成了一个函数的主体，编译器可以进一步利用它评估为常数整数 4 的知识来消除对函数的不必要的调用，从而产生进一步的性能提升。

常数传播是在编译器中使用到达定义分析结果实现的。如果所有变量的达成定义都是相同的赋值，而这个赋值又给变量分配了一个相同的常数，那么这个变量就有一个常数值，可以用这个常数来代替。

常数传播也可以使条件分支简化为一个或多个无条件语句，此时条件表达式可以在编译时被评估为真或假，以确定唯一可能的结果。

顺便推荐一个编译器优化方案的一个集合，还提供了一些测试集，对于编译器开发的同事来说，太棒了。我要推荐给你，知行合一，来卷起来。

看名字就知道是什么：http://compileroptimizations.com

ps.最近有个尴尬的烦恼，打「什么」2 个字的时候，总是出现「SM」……