对于一个很复杂的常量表达式,编译器会算出结果再编译吗?

抑或是很忠实地把这个表达式完全翻译成机器码,留给最终的程序去解决? ps:本人使用vs2010和keil uv4 都是c语言 但是也希望了解别的高级语言在这方面的问题
关注者
76
被浏览
10160
把常量表达式的值求出来作为常量嵌在最终生成的代码中,这种优化叫做常量折叠(constant folding)。题主的问题:
对于一个很复杂的常量表达式,编译器会算出结果再编译吗?
抑或是很忠实地把这个表达式完全翻译成机器码,留给最终的程序去解决?
这种问题会有几个维度。挑两个来说说:
  • 涉及的常量折叠是否为语言规范所强制要求的。如果是的话,那么符合规范的编译器就一定要做这样的常量折叠。
  • 如果不属于上一条的情况,那么这就是编译器的实现质量的问题。一个编译器可以自由选择是否做常量折叠(或其它常量相关)优化。同一个编译器有可能可以配置在不同的优化层级上工作,或许有些在低优化层级没有被常量折叠的代码,在高优化层级会被优化。

常量折叠的概念自身很简单。对此没啥了解的同学可以先跳个老传送门:Optimizing C++ Code : Constant-Folding

=========================================

语言规范要求做常量折叠的情况

Java

例如说在Java语言中,下面这些情况都会被认为是语言规范所规定的编译时常量表达式:
  • Java原始类型(byte、boolean、short、char、int、float、long、double)以及java.lang.String的字面量
  • 声明为static final的Java原始类型或java.lang.String类型的静态字段,并且带有以常量表达式来初始化的情况(如果没有初始化表达式或者初始化表达式不是常量表达式的话则不算)
  • 声明为final修饰的原始类型或java.lang.String类型的局部变量,并且带有以常量表达式来初始化的情况(类似于上一条)
  • 以常量表达式为操作数的算术和关系运算表达式,以及String拼接运算符('+')
所以,在Java中,下面的表达式都是语言规范强制要求的常量表达式:
1         // int literal, type: int, value: 1
1.0       // double literal, type: double, value: 1.0d
"foobar"  // string literal, type: java.lang.String, value: "foobar"
"foo" + 1 // constant string concatenation expression, type: java.lang.String, value: "foo1"
1 < 2     // constant relational expression, type: boolean, value: true
然后下面的Foo类中的几个声明:
class Foo {
         static final int BAR = 37 + 2 + 3; // yes
  public static final int BAZ = BAR + 1;    // yes
  public static final int GOO;              // no: no initializer
  public static final int QUUX =
      Integer.valueOf(42).intValue();       // no: initializer not a constant expression

  public static int example() {
    final int x = 42;                       // yes
    int y = 42;                             // no
    final int z = "foobar".length();        // no: initializer not a constant expression
  }
}
像这样的情况,Java语言编译器(例如javac、ECJ)在遇到相关的运算符时,必须要检查其操作数是否都为常量表达式,如果是的话就必须在编译时对该运算符做常量折叠。

C#在语言规范里也有类似的规定。

当然,即便一个表达式从Java语言规范的角度看不是强制的常量表达式,编译器还是有自由在语义允许的前提下把代码优化为在编译时求值。例如说,像下面的例子,目前主流的桌面/服务器端JVM里的JIT编译器都可以彻底优化掉:
  public static int foo() {
    int x = 40;
    int y = new int[2].length;
    return x + 0 + y;
  }
可以被一些JIT编译器优化到等价于:
  public static int foo() {
    return 42;
  }

C

C语言当然也有类似的规定。请参考 Constant expressions
最典型的,整型字面量、sizeof()运算符(当参数不是VLA时),以及各种算术、关系/比较运算符在所有操作数都是整型常量时,整个表达式都会算是整型常量表达式。所以像是说 40 + 1 + (4 > 3) 这个表达式就是一个整型常量表达式,必须在编译时求值。
C语言里有些语言结构是要求操作数一定要是常量表达式的,例如说非VLA的数组声明里面指定数组长度的表达式。如果有局部变量声明 int a[10 + 2]; ,而10 + 2被允许在运行时才求值的话,那么这个数组的大小就要在运行时才知道,就变成一个VLA了。

C++

早期版本的C++的常量表达式的规定跟C语言是颇为相似的。加入模版支持后,通过模版元编程实现复杂的编译时求值的技巧被人发掘出来,变得很有趣。
C++11开始支持的constexpr修饰符则进一步扩大了非模版语法下能表达的编译时求值的语法结构的范围,C++14、C++17都对此做了进一步扩展。

D语言

D语言也有跟C语言相似的常量表达式,此外它还特别强调它的编译器支持“CTFE”(Compile Time Function Evaluation),也就是说如果一个函数调用传入的所有参数都是编译时常量,而且这个函数满足一些(不那么多的)限制,那么这个函数调用就会被编译时求值。
放俩传送门:

=========================================

编译器提供的特殊查询支持

GCC有一个编译器内建函数(builtin function),
__builtin_constant_p(x)
可以检测传入的参数表达式是否为编译器可以在编译时做常量折叠的表达式。请参考官方文档的描述:
Other Builtins - Using the GNU Compiler Collection (GCC)
Clang也支持这个编译器内建函数。

=========================================

一个C语言的综合例子

举个综合例子,来看看从语言规范上看并没有要求在编译时彻底求值,但编译器自身通过优化实现了彻底求值的情况。

int fib(int);

int foo() {
  return fib(21); // 17711
}

int fib(int n) {
  int a = 1, b = 0;
  for (int i = 0; i < n; i++) {
    int t = a;
    a = a + b;
    b = t;
  }
  return a;
}
用Clang 3.0到3.9.1测个遍,这些版本的Clang在-O2下都可以把foo()完全静态求值,变成等价于:
int foo() {
  return 17711;
}
这里没有任何const修饰,也不依赖于诸如C++14开始支持的扩展版constexpr,全靠Clang编译器自己决定做的优化而达到这样的效果。其它主流的C/C++优化编译器在-O3、/Ox之类的优化层级上对这个例子似乎都还不会把foo()彻底的静态求值掉,例如说试了下GCC 4.4.7到6.0,然后ICC 13、17,然后MSVC CL 19,都做了一些优化但是没有完全静态求值。

=========================================

编译器中常量相关优化的极入门介绍

简单说说这三种优化:
  • 常量折叠(constant folding)
  • 常量传播(constant propagation)
  • 条件常量传播(conditional constant propagation)及其改良版,稀疏条件常量传播(sparse conditional constant propagation,SCCP)

1、常量折叠

常量折叠是编译器里最基本最常见的优化,没有之一。连很多基本上不做优化或者只做很简单优化的编译器都会实现常量折叠,例如TCC(Tiny C Compiler)。

本文前面讲的很多东西都是跟常量折叠相关的。看似很直观明了对不对?

简单的常量折叠确实是很简单的。例如说,如果用C++写一个类C语言的编译器,在它做语法分析/构建AST的时候,可以做类似这样的事情:
Node* Parser::ParseAdditiveExpression() {
  Node* expr = ParseMultiplicativeExpression();

  while (Token() == '+' || Token() == '-') {
    Operator op;
    if (Token() == '+') {
      Match('+');
      op = OP_BINARYADD;
    } else {
      assert0(Token() == '-');
      Match('-');
      op = OP_BINARYSUB;
    }
    Node* left = expr;
    Node* right = ParseMultiplicativeExpression();
    expr = CreateBinaryExpression(op, left, right);
  }

  return expr;
}

Node* CreateBinaryExpression(Operator op, Node* left, Node* right) {
  // constant fold simple cases
  if (left->IsConstant() && right->IsConstant()) {
    switch (op) {
    case OP_BINARYADD: {
        Type type = PromototedTypeFor(left, right);
        switch (type) {
        case T_INT:
          return new Constant(T_INT, left->IntConstantValue(), right->IntConstantValue());
        case T_LONG:
          return new Constant(T_LONG, left->LongConstantValue(), right->LongConstantValue());
        // other types ...
        }
      }
      // other operators ...
    }
  }

  // otherwise create the node
  return new BinaryExpression(op, left, right);
}
这样,对于下面的表达式,
1 + 2 + 5
在做语法分析+构建AST的时候就可以将其常量折叠为8了,简略步骤是:
Step 1:
  1 + 2 + 5
  ^

  expr = Constant(T_INT, 1)

Step 2:
  1 + 2 + 5
      ^

  expr = CreateBinaryExpression(OP_BINARYADD, Constant(T_INT, 1), Constant(T_INT, 2))
       = Constant(T_INT, 3)

Step 3:
  1 + 2 + 5
          ^

  expr = CreateBinaryExpression(OP_BINARYADD, Constant(T_INT, 3), Constant(T_INT, 5))
       = Constant(T_INT, 8)
如果把完整的AST构造出来再做折叠的话可能看起来更明显一些:
Step 0:
    +
   / \
  +   5
 / \
1   2

Step 1:
    +
   / \
  3   5

Step 2:
    8
可以很明显地看到,这个AST上的两个加法的操作数都是常量表达式。

但是上面的做法碰到稍微复杂那么一丁点的情况就纱布了:
x + 1 + 2
假如x是一个局部变量,不是常量表达式,那么按照上面的做法,如果构造出完整AST的话会是:
    +
   / \
  +   2
 / \
x   1
虽然字面上看1 + 2是一个常量加法,但实际编译器看到的结构却是 (x + 1) + 2 而不是 x + (1 + 2) ,所以1和2并不是相邻的。
可以看到,对下面的加法,x + 1由于x不是常量所以这个加法也不是常量表达式,然后对上面的加法由于左手边操作数不是常量表达式,所以这个加法也不是常量表达式。于是上面的简易常量折叠就无法把这段代码优化为 x + 3。

那要怎么办呢?很简单,让常量折叠的逻辑多看一层就好了。就这个例子而言,对上面的加法,它应该看看其操作数是否是常量,如果不是的话该操作数是否有部分操作数是常量,是的话就根据加法的结合律来旋转AST的结构并折叠常量。
Step 0:
    +
   / \
  +   2
 / \
x   1

Step 1: rotate
  +
 / \
x   +
   / \
  1   2

Step 2: constant fold
  +
 / \
x   3

这就是一种模式匹配。但如果编译器需要为优化去匹配太多的模式,实现起来就会很繁琐。所以贯穿于优化编译器里的一个思想就是代码的规范化(canonicalize)——尽可能把多种等价形式的代码规范化为一种统一的形式,这样后续的模式匹配就只要匹配较少形状的代码了。

例如说,再稍微复杂一点的表达式:
1 + x + 2
对应的完整AST:
    +
   / \
  +   2
 / \
1   x
这个无论从源码字面上还是从AST上看,常量都没有紧挨在一起。所以要怎么办?
(顺带:TCC在遇到这样的代码时就无法把它常量折叠为 x + 3,咳咳)

一种思路就是:在创建AST节点的时候,对于二元运算,在满足交换律的情况下,总是把常量放在右手边。所以就会有:
Step 0:
    +
   / \
  +   2
 / \
1   x

Step 1: commute
    +
   / \
  +   2
 / \
x   1

Step 2: rotate ...
后面就跟上一个例子一模一样了,不再赘述。

综上,对这组简单的常量折叠例子,我们可以对AST定义下述改写规则:
  • c1 + c2 => c3
    • 其中c3的数值等于c1 + c2的数值
  • c + x => x + c
    • 根据交换律把常量移到右手边
  • (x + c1) + c2 => x + (c1 + c2)
    • 向下看一层,将常量向右推
  • (x + c) + y => (x + y) + c
  • x + (y + c) => (x + y) + c
  • (x + c1) + (y + c2) => (x + y) + (c1 + c2)
    • 向下看一层,将常量向右推
重复应用这组改写规则直到不能进一步改写,我们就能把一串加法表达式中所有常量加法都尽可能向右边推并且折叠起来了。

常量折叠还可以利用上某些算术恒等性,例如说 x + 0 == x ,x * 0 == 0 , x * 1 == x ,等等。这样,即便参与运算的操作数只有一边是常量(另一边是不是常量都无所谓),利用这些特殊性质我们还是可以做常量折叠。

当然,要应对一串表达式中的常量折叠,除了上面的树改写(或者DAG改写)的方法外,还有不少其它方式,其中不乏更“简单粗暴”的。
例如说,可以把整棵表达式树“拍扁”(flatten)成一个扁平的多项式,通过排序/分组把相同变量的项合并起来(不包含变量的项也合并起来),就完成了从这棵表达式树中提取出所有常量项并折叠之的操作,顺带还可以有效简化多项式里涉及变量的项的运算。

2、常量传播

上面提到的常量折叠是一种只关注非常局部的信息、效果也仅限于非常局部的范围的一种优化。单独应用它的话,最大的局限性在于它一般处理不了涉及变量的操作,因为它不会主动去了解变量的定值(definition,或者叫赋值 assignment 也可以)的情况。

那么考虑下面的例子:
int x = 40;
int y = x + 2;
像C语言、Java语言之类的,语言规范层面上都不会把y的初始化表达式 x + 2 规定为一个常量表达式。但我们直觉上觉得编译器应该能把它也给常量折叠起来。差在哪里了呢?

差就差在这里要提到的“常量传播”(constant propagation)优化上。变量x的定值是一个常量,int型的40,如果把这个信息传播到后面所有使用变量x的地方去,那么那些地方就可以把x当作一个常量来看待,于是就可以做相应的常量优化了,例如说上面所说的常量折叠。

可是一个变量之所以叫做“变量”就是因为它允许被多次赋值(拥有多个定值),假如例子改为:
int x = 40;
x = rand();
int y = x + 2;
则变量x有两个定值,一个是常量40,而另一个是个未知数值的函数调用返回值,这样在变量y的初始化表达式处, x + 2 就不能把x看作常量来做优化了,因为x在此处并不应该去常量的那个定值,而要取另一个定值而它不是常量。

所以,要实现常量传播,它必须要依赖一种叫做“到达定值”(reaching definition)的前向数据流分析(forward data-flow analysis)。它要确定某个定值能被传播到哪些使用点,或者反过来说,某个使用点上应该采用哪个版本的定值。如果在某个使用点上发现应该使用的定值是一个常量的话,就可以在此处做诸如常量折叠之类的常量优化了。
对编译原理有一定了解的同学,如果听说过SSA形式的话,此时应该会会心一笑。没错,这个意义上的常量传播在SSA形式里是免费的 >_<

3、条件常量传播


所谓“条件常量传播”(conditional constant propagation),是一种结合了常量折叠、常量传播与无用代码消除(dead code elimination)的优化。它最有趣的效果就是:通过常量传播与常量折叠,可能可以消除掉代码里的某些分支(由于条件是常量),此时可能会发现出更多的常量,于是又能消除更多分支…

试想这样的例子:
int x = 40;
int y = 42;
int z = 1;

if (x > y) {
  z = 2;
}

if (z > 1) {
  x = y;
}
当我们单纯应用常量折叠时,这个例子没有任何可优化的地方。
当我们先应用常量传播然后再常量折叠,则这个例子可以被优化为:
int x = 40;
int y = 42;
int z = 1;

if (FALSE) { // x > y == FALSE
  z = 2;
}

if (z > 1) {
  x = y;
}
这里会使得例子中的一个条件分支变成无用代码,但在消除它之前,我们并不能做更多的优化了。

如果对这个例子应用上条件常量传播,它就会发现并消除掉这块无用代码,并且进一步发现在 if (z > 1) 处变量z的定值肯定是常量1:
int x = 40;
int y = 42;
int z = 1;

if (FALSE) { // z > 1 == FALSE
  x = y;
}
于是最终这个条件分支也被看作无用代码被消除掉。

大家还可以试试看涉及循环的例子。这边我就不另外举例了,有兴趣的同学可以参考Wikipedia上的例子:Constant folding

CCP是一种简单而强大的优化,可以简化相当做的代码,为其它优化更有效地进行奠定了良好的基础。

应用在SSA形式上的CCP叫做SCCP。这也算是现代优化编译器中的看家本领了,没实现CCP / SCCP都不好意思出来见人…