常数折叠是编译器最佳化技术,被使用在现代的
编译器中。进阶的常数传播形式,或称之为稀疏有条件的常量传播,可以更精确地传播
常数及无缝的移除无用的程式码。
简介
常数折叠是一个在
编译时期简化常数的一个过程,常数在表示式中仅仅代表一个简单的数值,就像是
整数 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;
当 a 及 b 已经被简化为常数,他们的数值取代了程式码中任何一个使用到变数的地方,编译器接着将会使用
死码删除(dead code elimination)来消除他们:
int c;
if (true)
{
c = 2;
}
return c * 2;
在上述的程式,可以根据编译器的框架来判别可以用1或是其他的布林常数来取代 True ,伴随传统的常数传播,我们将得到相当多的最佳化,他无法改变程式的结构。
还有其他类似的最佳化,被称之为稀疏有条件的常量传播(sparse conditional constant propagation),他依据if状态选择了合适的分支,编译器侦测到 if 的描述中,将永远被赋予TRUE, c变数可以被消除,完成之后程式码变成:
return 4;
如果这个
虚拟码为一个函数,编译器将可将其以整数 4来取代,以消除无用的函数呼叫,改进整体的运行效能。