常量折叠Constant folding)以及常量传播constant propagation)都是编译器优化技术,他们被使用在现代的编译器中。高级的常量传播形式,或称之为稀疏有条件的常量传播(sparse conditional constant propagation),可以更精确地传播常量及无缝的移除无用的代码

常量折叠

编辑

常量折叠是一个在编译时期简化常量的一个过程,常量在表示式中仅仅代表一个简单的数值,就像是整数 2,若是一个变量从未被修改也可作为常量,或者直接将一个变量被明确地被标注为常量,例如下面的描述:

  i = 320 * 200 * 32;

多数的现代编译器不会真的产生两个乘法的指令再将结果存储下来,取而代之的,他们会识别出语句的结构,并在编译时期将数值计算出来(在这个例子,结果为2,048,000),通常会在中介码(IR,intermediate representation)树中进行。

有些编译器,常量折叠会在初期就处理完,所以像是C语言的数组,初始化时就可以接受简单的运算表示式。而将常量折叠放在较后期的阶段的编译器,也相当常见。

常量折叠可以在编译器前端的IR树完成,在代码转换为三地址码之前。常量折叠也可以在后端完成,作为常量传播的附加功能。

常量折叠与跨平台编译

编辑

在实现一个跨平台编译器时,必须确保目标平台的算术运算的行为与编译平台结构是吻合的,而且启动常量折叠将会改变程序的行为,这在浮点数的运算中是非常重要的,浮点数精确度问题的影响是非常广的。

常量传播

编辑

常量传播是一个替代表示式中已知常量的过程,也是在编译时期进行,包含前述所定义,内置函数也适用于常量,以下列描述为例:

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

传播x变量将会变成:

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

持续传播,则会变成:(还可以再进一步的消除无用代码x及y来进行优化)

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

常量传播在编译器中使用定义可达性(Reaching definition)分析实现,如果一个变量的所有定义可达性,都是赋予相同的数值,那么这个变量将会是一个常量,而且会被常量取代。

常量传播也可能导致使状态的分支简化,或是变成更复杂,当状态表示式在编译时期可以被计算为TRUE或是FALSE时,就可以决定他唯一的一种可能。

优化的行为

编辑

常量折叠及传播通常会同时被使用在简化以及减少,借由交错使用他们,一直到没有必要再改变,举例来说:

  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;

再做一次:

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

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

ab 已经被简化为常量,他们的数值取代了代码中任何一个使用到变量的地方,编译器接着将会使用死码删除(dead code elimination)来消除他们:

  int c;

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

在上述的程序,可以根据编译器的框架来判别可以用1或是其他的布尔常量来取代 True ,伴随传统的常量传播,我们将得到相当多的优化,他无法改变程序的结构。

还有其他类似的优化,被称之为稀疏有条件的常量传播(sparse conditional constant propagation),他依据if狀態选择了合适的分支[1],编译器侦测到 if 的描述中,将永远被赋予TRUE, c变量可以被消除,完成之后代码变成:

  return 4;

如果这个伪代码为一个函数,编译器将可将其以整数 4来取代,以消除无用的函数调用,改进整体的运行性能。

参见

编辑

参考文献

编辑
  1. ^ Wegman, Mark N; Zadeck, F. Kenneth, Constant Propagation with Conditional Branches, ACM Transactions on Programming Languages and Systems, April 1991, 13 (2): 181–210 

延伸阅读

编辑
  • Muchnick, Steven S., Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997, ISBN 9781558603202