MENU

编译器笔记--代码优化(高级优化)

July 15, 2023 • 阅读: 649 • 笔记&折腾

优化可以应用于编译器的多个阶段。

通常最好在尽可能的最高抽象级别解决问题。例如,一旦我们生成了具体的汇编代码,我们最多能做的就是消除一些冗余指令。但是,如果我们使用线性 IR,我们可以通过智能寄存器分配来加速长代码序列。如果我们在 DAG 或 AST 级别上工作,我们就可以消除整个未使用的代码块。
优化可以发生在程序内的不同范围。局部优化是指仅限于单个基本块的更改,该基本块是没有任何流程控制的直线代码序列。全局优化是指应用于函数(或过程、方法等)整个主体的更改,由控制流图组成,其中每个节点都是一个基本块。过程间优化甚至更大,并且考虑到不同函数之间的关系。一般来说,更大范围的优化更具挑战性,但更有潜力改进程序。

优化视角

作为一名程序员(编译器的用户),保持对编译器优化的洞察力非常重要。大多数生产编译器在使用默认选项运行时不会执行任何重大优化。有几个原因。原因之一是编译时间:在最初开发和调试程序时,您希望能够快速编辑、编译和测试多次。几乎所有优化都需要额外的编译时间,这对程序的初始开发阶段没有帮助。另一个原因是,并非所有优化都会自动改进程序:它们可能会导致程序使用更多内存,甚至运行更长时间!另一个原因是优化可能会混淆调试工具,从而难以将程序执行与源代码联系起来。
如果程序运行速度没有期望的那么快,两个建议:

  • 检查程序的整体算法复杂性:改进程序的算法可能比低级优化产生更大的好处。
  • 衡量程序的性能。使用一些标准分析工具来准确测量您的程序大部分时间花费在哪里,然后通过重写或启用适当的编译器优化来改进该代码。

一旦程序按照第一原则编写得很好,那么就该考虑启用特定的编译器优化。大多数优化都是针对代码中的特定行为模式而设计的,这些行为模式对编写高质量代码也很有帮助。

高级优化

常量折叠

案例:

const int seconds_per_minute=60;
const int minutes_per_hour=60;
const int hours_per_day=24;
int seconds_per_day = seconds_per_minute * minutes_per_hour * hours_per_day;

最终结果是相同的 (86400),但在代码中对于这几个数字的用途和来源是固定。然而,如果按字面翻译成汇编,该程序将包含三个多余的常量、几次内存查找和两次乘法才能获得相同的结果。如果在复杂程序的内部循环中完成,这可能会造成很大的浪费。

常量折叠是通过将多个常量组合成单个常量来代替表达式(或表达式的一部分)的技术。树中具有两个常量子节点的运算符节点可以转换为具有预先计算的运算结果的单个节点。该过程可以级联,以便将复杂的表达式简化为单个常量。实际上,它将程序的一些工作从执行时转移到编译时。

这可以通过执行表达式树的后序遍历的递归函数来实现。以下是伪代码:

struct expr * expr_fold( struct expr *e )
{
    expr_fold( e->left )
    expr_fold( e->right )
    if( e->left and e->right are both constants ) {
        f = expr_create( EXPR_CONSTANT );
        f->value = e->operator applied to e->left->value and e->right->value
        expr_delete(e->left);
        expr_delete(e->right);
        return f;
    } else {
        return e;
    }
}

必须小心的是,提前计算的结果与运行时执行的结果完全相同。这需要使用相同精度的变量并处理边界情况,例如下溢、溢出和除以零。在这些情况下,通常会强制出现编译时错误,而不是计算意外结果。

强度缩减

强度缩减是将昂贵操作的特殊情况转换为成本较低的操作的技术。例如,用于浮点值求幂的源代码表达式 xˆy 通常被实现为对函数 pow(x,y) 的调用,该函数可能被实现为泰勒级数的展开。然而,在 x^2 的特殊情况下,我们可以替换表达式 x*x 来完成同样的事情。这避免了函数调用和多次循环迭代的额外成本。以类似的方式,乘以/除以任何二的幂可以分别用按位左/右移位来代替。例如,x*8 可以替换为 x<<3

一些编译器还包含标准库中操作强度降低的规则。例如,最新版本的 gcc 将对 printf(s) 的调用替换为常量字符串 s ,以等效调用 put(s)。在这种情况下,强度的降低来自于减少必须链接到程序中的代码量:puts 非常简单,而 printf 具有大量功能和进一步的代码依赖性

循环展开

考虑使用循环多次计算简单表达式的变体的常见结构:

for(i=0;i<400;i++) {
    a[i] = i*2 + 10;
}

在任何汇编语言中,每次只需要循环体中的几条指令来计算 a[i] 的值。但是,控制循环所需的指令将占执行时间的很大一部分:每次通过循环时,我们都必须检查 i 是否<400 并跳回循环顶部。
循环展开是将一个循环转换为另一个迭代次数较少但每次迭代执行更多工作的技术。循环内的重复次数称为展开因子。上面的例子可以安全地转换为:

for(i=0;i<400;i+=4) {
    a[i] = i*2 + 10;
    a[i+1] = (i+1)*2 + 10;
    a[i+2] = (i+2)*2 + 10;
    a[i+3] = (i+3)*2 + 10;
}

// 或者

for(i=0;i<400;i++) {
    a[i] = i*2 + 10;
    i++;
    a[i] = i*2 + 10;
    i++;
    a[i] = i*2 + 10;
    i++;
    a[i] = i*2 + 10;
}

增加每个循环迭代的工作量可以节省一些不必要的 i<400 评估,并且还消除了指令流中的分支,从而避免了微处理器内的流水线停顿和其他复杂性。

但是一个循环应该展开多少呢?展开的循环每次迭代可以包含 4、8、16 甚至更多项。在极端情况下,编译器可以完全消除循环,并将其替换为有限的语句序列,每个语句都有一个常量值:

a[0] = 0 + 10;
a[1] = 2 + 10;
a[2] = 4 + 10;
. . .

随着展开因子的增加,循环结构中不必要的工作被消除。然而,增加代码大小有其自身的成本:处理器必须不断从内存加载新指令,而不是一遍又一遍地读取相同的指令。如果展开的循环导致工作集大于指令缓存,则性能可能会比原始代码更差。

因此,对于何时使用循环展开没有硬性规定。编译器通常具有用于展开的全局选项,可以通过放置在特定循环之前的 #pragma 对其进行修改。可能需要手动实验才能获得特定程序的良好结果。

代码提升

有时,循环内的代码片段在循环的每次迭代中都是恒定的。在这种情况下,没有必要在每次迭代时重新计算,因此代码可以移动到循环之前的块,这称为代码提升。例如,本例中的数组索引在整个循环中是恒定的,并且可以在循环体之前计算一次:

for(i=0;i<400;i++) {
    a[x*y] += i;
}

// 提升为

t = x*y;
for(i=0;i<400;i++) {
    a[t] += i;
}

与循环展开不同,代码提升是一种相对良性的优化。优化的唯一成本是计算结果必须在循环期间占用临时位置(这会稍微增加寄存器压力)或本地存储消耗。这可以通过消除不必要的计算来抵消。

函数内联

函数内联是直接在代码中用函数调用的效果替换函数调用的过程。这对于为了提高代码的清晰度或模块化性而存在但不执行大量计算的简短函数特别有用。例如,假设在循环内多次调用简单函数二次函数,如下所示:

int quadratic( int a, int b, int x ) {
    return a*x*x + b*x + 30;
}
for(i=0;i<1000;i++) {
    y = quadratic(10,20,i*2);
}

设置参数和调用函数的开销可能超过在函数本身内进行少量加法和乘法的成本。通过将函数代码内联到循环中,我们可以提高程序的整体性能。

函数内联最容易在 AST 或 DAG 等高级表示上执行。首先,必须复制函数体,然后必须替换调用的参数。请注意,在此评估级别,参数不一定是常量,但可能是包含未绑定值的复杂表达式。

例如,在 a=10、b=20、x=i*2 的绑定下,上面的 quadratic 调用可以用表达式(a*x*x+b*x+30) 代替。执行此替换后,未绑定的变量(例如 i)相对于调用二次方的范围,而不是相对于定义它的范围。结果代码如下所示:

for(i=0;i<1000;i++) {
    y = 10*(i*2)*(i*2) + 20*(i*2) + 30;
}

此示例突出显示了函数内联的隐藏潜在成本:以前计算一次然后用作函数参数的表达式(如 i*2 )现在计算多次,这可能会增加表达式的成本。另一方面,这种扩展可以通过代数优化来抵消,代数优化现在有机会简化函数与其具体参数的组合。例如,将常量折叠应用于上面的示例会产生以下结果:

for(i=0;i<1000;i++) {
    y = 40*i*i + 40*i + 30;
}

一般来说,函数内联最适用于调用频繁且相对于调用成本而言几乎没有做任何工作的简单叶函数。然而,自动做出这一决定很难做到正确,因为好处相对明显,但增加代码大小和重复评估的成本却不太容易量化。因此,许多语言提供了一个关键字(如 C 和 C++ 中的 inline),允许程序员手动做出此决定。

死代码检测和消除

已编译的程序包含一定数量的完全无法访问且在任何可能的输入下都不会执行的代码的情况并不罕见。这可能很简单,就像程序员犯了一个错误,他意外地从最终语句之前的函数返回。或者,可能是由于按顺序应用了多个优化,最终导致永远不会执行的分支。无论哪种方式,编译器都可以通过为程序员标记它或直接删除它。

死代码检测通常在执行常量折叠和其他表达式优化之后在控制流图上执行。例如,考虑以下代码片段及其控制流图:

if( x<y ) {
    return 10;
} else {
    print "hello";
}
print "goodbye";
return 30;

return 语句会导致函数立即终止,并且(从控制流图的角度来看)是执行路径的结束。在这里,if 语句的 true 分支立即返回,而 false 分支则继续执行下一个语句。对于 x 和 y 的某些值,有可能到达每个语句。然而,如果我们做一些小小的改变,就像这样:

if( x<y ) {
    return 10;
} else {
    return 20;
}
print "goodbye";
return 30;

然后,if 语句的两个分支都以 return 终止,并且不可能到达最终的 print 和 return 语句。这(可能)是程序员的错误,应该被标记。

创建控制流图后,确定可达性就很简单:从函数的入口点开始遍历 CFG,标记每个被访问的节点。一旦遍历完成,任何未标记的节点都被认为是不可到达的。编译器可能会生成适当的错误消息,或者干脆不为无法访问的部分生成代码。

当与其他形式的静态分析相结合时,可达性分析变得特别强大。在上面的示例中,假设变量 x 和 y 分别定义为常量 100 和 200。常量折叠可以将 x<y 简化成 TRUE,那么 else 分支永远也不会被访问,会被标记为不可达。