HTML CSS JAVASCRIPT PYTHON PYTHON2 JAVA C C++ C# SQL Excel Linux AI BOOTSTRAP PHP 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ
❮ 上一节 下一节 ❯

编译器设计 - 代码优化

优化是一种程序转换技术，它试图通过减少代码消耗资源（即 CPU、内存）并提供高速来改进代码。

在优化中，高级通用编程结构被非常高效的低级编程代码所取代。代码优化过程必须遵循以下三个规则：

  • 输出代码不得以任何方式改变程序的含义。

  • 优化应提高程序的速度，如果可能，程序应减少对资源的需求。

  • 优化本身应该很快，并且不应延迟整个编译过程。

可以在编译过程的各个级别上努力优化代码。

  • 一开始，用户可以更改/重新排列代码或使用更好的算法来编写代码。

  • 生成中间代码后，编译器可以通过地址计算和改进循环来修改中间代码。

  • 在生成目标机器代码时，编译器可以利用内存层次结构和 CPU寄存器。

优化大致可分为两类：机器独立优化和机器相关优化。

机器独立优化

在这种优化中，编译器接收中间代码并转换不涉及任何 CPU 寄存器和/或绝对内存位置的部分代码。例如：

do
{
   item = 10;
   value = value + item; 
} while(value<100);

此代码涉及标识符 item 的重复分配，如果我们这样说的话：

Item = 10;
do
{
   value = value + item; 
} while(value<100);

不仅可以节省 CPU 周期，还可以在任何处理器上使用。

机器相关优化

机器相关优化是在生成目标代码后，根据目标机器架构转换代码时进行的。它涉及 CPU 寄存器，可能具有绝对内存引用而不是相对引用。机器相关优化器努力最大限度地利用内存层次结构。

基本块

源代码通常有许多指令，这些指令始终按顺序执行，并被视为代码的基本块。这些基本块之间没有任何跳转语句，即当执行第一条指令时，同一基本块中的所有指令将按照其出现的顺序执行，而不会丢失程序的流程控制。

程序可以有各种构造作为基本块，如 IF-THEN-ELSE、SWITCH-CASE 条件语句和循环，如 DO-WHILE、FOR 和 REPEAT-UNTIL 等。

基本块识别

我们可以使用以下算法来查找程序中的基本块：

  • 从基本块开始的位置搜索所有基本块的头语句：

    • 程序的第一个语句。
    • 任何分支（条件/无条件）的目标语句。
    • 任何分支语句之后的语句。

  • 头语句及其后的语句构成基本块。

  • 基本块不包含任何其他基本块的任何头语句。

从代码生成和优化的角度来看，基本块都是重要的概念。

Basic Blocks

基本块在识别变量方面起着重要作用，这些变量是在单个基本块中多次使用。如果任何变量被多次使用，则除非块完成执行，否则无需清空分配给该变量的寄存器内存。

控制流图

程序中的基本块可以通过控制流图表示。控制流图描述了程序控制如何在块之间传递。它是一种有用的工具，有助于优化，帮助定位程序中任何不需要的循环。

控制流图

循环优化

大多数程序在系统中以循环形式运行。优化循环以节省 CPU 周期和内存是必要的。循环可以通过以下技术进行优化：

  • 不变代码：驻留在循环中并在每次迭代中计算相同值的代码片段称为循环不变代码。此代码可以移出循环，只需保存一次即可，而不是每次迭代都计算一次。

  • 归纳分析：如果变量的值在循环内被循环不变值改变，则该变量称为归纳变量。

  • 强度降低：有些表达式会消耗更多的 CPU 周期、时间和内存。这些表达式应该用更便宜的表达式替换，而不会影响表达式的输出。例如，乘法 (x * 2) 比 (x << 1) 占用更多的 CPU 周期，但结果相同。

死代码消除

死代码是一个或多个代码语句，它们：

  • 从不执行或无法访问，
  • 或者如果执行，它们的输出永远不会被使用。

因此，死代码在任何程序操作中都不起作用，因此可以简单地将其消除。

部分死代码

有些代码语句的计算值仅在某些情况下使用，即有时使用这些值，有时则不使用。此类代码称为部分死代码。

部分死代码

上面的控制流图描述了一段程序，其中变量"a"用于分配表达式"x * y"的输出。我们假设分配给"a"的值从未在循环内使用。控制离开循环后，立即为"a"分配变量"z"的值，该值将在程序的后面使用。我们在此得出结论，赋值代码'a'从未在任何地方使用过，因此可以将其消除。

死代码

同样，上图显示条件语句始终为假，这意味着在真的情况下编写的代码永远不会被执行，因此可以将其删除。

部分冗余

冗余表达式在并行路径中计算多次，操作数没有任何变化。而部分冗余表达式在路径中计算多次，操作数没有任何变化。例如，

冗余表达式

[冗余表达式]

 部分冗余表达式

[部分冗余表达式]

循环不变代码是部分冗余的，可以使用代码移动技术消除。

部分冗余代码的另一个示例可以是：

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

我们假设操作数（y 和 z）的值从将变量 a 赋值给变量 c 时没有改变。这里，如果条件语句为真，则 y OP z 计算两次，否则计算一次。可以使用代码移动来消除这种冗余，如下所示：

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

这里，无论条件是真还是假；y OP z 都应该只计算一次。

❮ 上一节 下一节 ❯