在计算机编程中,编译时与运行时的界限通常很明确。编译时,将程序编译成机器代码,然后运行。C++通过模板元编程技术跨越了这条线,使用编译器来“运行”元程序。动态编程语言(例如,Python)则以相反的方式跨越这条线,允许在运行时生成函数(“更高层次的函数”)。以下是一个概念验证,展示了如何在C++中使用LLVM编译器基础设施实现更高层次的函数,以及它们如何有助于运行时代码优化。
静态代码优化
C++编译器可以进行相当复杂的代码优化。然而,可以进行多少优化取决于编译器对代码的了解程度。例如,一个简单的优化是“强度降低”。通常,面对如下代码:
int divide(int x, int z) {
return x / z;
}
编译器别无选择,将使用昂贵的除法指令。然而,如果对x和z有更多的了解,可以进行许多额外的优化。例如,如果知道z在编译时的值,可以将已知值嵌入到函数中(或专门化模板函数):
int divide8(int x) {
return x / 8;
}
现在,编译器可以优化除法,用一个便宜的右移替换它:
int divide8_opt(int x) {
return x >> 3;
}
这种和类似的优化可以显著提高应用程序的性能。
目标特定的优化
额外的优化取决于目标机器:如果事先知道应用程序将在Core 2机器上运行,可以使用SSE 4.1指令来实现额外的优化。然而,在大多数情况下,应用程序预计将在各种机器上运行,因此使用“最小公分母”方法,发出与Pentium兼容的可执行文件,从而失去潜在的性能提升。
动态代码优化
如果能够将部分编译过程推迟到运行时,将有更多的优化机会。首先,可以为应用程序实际运行的机器生成优化代码——仅在运行在Core 2机器上时使用SSE4.1等扩展。其次,可以创建依赖于编译时不可用值的代码。例如,数据包过滤器可能在运行时扫描网络流量以寻找特定模式。然而,这些模式相对静态,并且不经常变化(参见此例子
)。
LLVM是一个高质量、平台独立的编译基础设施。它支持编译到中间“位码”,以及高效的即时(JIT)编译和执行。对于LLVM和编写编译器的良好介绍,请参见优秀的LLVM教程。LLVM提供了生成位码的工具,然后它可以优化、编译和执行。
DynCompiler是一个动态代码编译的领域特定语言(DSEL)的概念验证(即:不要期望它对玩具问题之外的任何东西都能工作,有一个漂亮的语法,或者做任何有用的事情),它使用LLVM来做实际的工作。使用DynCompiler,可以创建一个“更高层次的函数”——或者一个用于创建其他函数的函数。例如,以下函数可以为给定的系数a、b和c创建一个特定的二次多项式(ax^2+bx+c):
typedef int (*FType)(int);
FType build_quad(int a, int b, int c) {
DEF_FUNC(quad) RETURNS_INT
ARG_INT(x);
BEGIN
DEF_INT(tmp);
tmp = a*x*x + b*x + c;
RETURN(tmp);
END
return (FType)FPtr;
}
请注意,build_quad()
返回一个函数——它不是二次函数本身(就像函数模板不是“具体”函数一样)。要创建一个实际的函数:
FType f1 = build_quad(1, 2, 1);
// f1(x) := x^2 + 2*x + 1
现在可以像使用任何其他函数一样使用它:
for(int x = 0; x < 10; x++) {
std::cout << "f1(" << x << ") = " << f1(x) << std::endl;
}
DynCompiler有一个丑陋的语法——这是预处理器的限制和懒惰的结果。函数生成器有一个名称和一个返回类型(仅支持“int”和“double”):
DEF_FUNC(name) RETURNS_INT
或者:
DEF_FUNC(name) RETURNS_DOUBLE
对于返回一个double的函数。结果函数的参数由以下提供:
ARG_INT(x);
// 整数
ARG_DOUBLE(x);
// 双精度
实际的函数代码以BEGIN
开始:
BEGIN
局部变量可以使用DEF_INT
和DEF_DOUBLE
定义:
DEF_INT(tmp);
然后可以(几乎)正常使用这些变量:
tmp = a*x + b;
请注意,此时代码尚未评估,除了像a和b这样的“正常”C++变量。因此,在执行此行时a=3,b=2,上述代码将被评估为:
tmp = 3*x + 2;
请注意,未使用的变量或在使用前未初始化的变量将生成错误。从函数返回值是通过:
RETURN_INT(expr);
或者
RETURN_DOUBLE(expr);
请注意,函数必须返回一个值。函数块以END
结束。基本的控制流由IF
和WHILE
提供:
IF(x > 0)
IF(y > 0)
z = x*y;
IFEND
ELSE
z = 0
IFEND
此外,可以使用PRINT(expr)
打印到标准输出:
PRINT(i);
最后,在END
之后,FPtr
将指向新创建的函数。然而,需要将指针转换为实际的函数类型:
f1 = (FType)FPtr;