编译器设计 - 代码优化

---

---

优化是一种程序转换技术，它试图通过减少资源消耗（即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等。

基本块识别

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

• 搜索所有基本块的头部语句，从中开始一个基本块。

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

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

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

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

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

控制流图

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

循环优化

大多数程序在系统中作为循环运行。为了节省CPU周期和内存，优化循环是必要的。可以使用以下技术优化循环：

• 不变代码：位于循环中并在每次迭代中计算相同值的代码片段称为循环不变代码。可以通过将其保存为仅计算一次而不是每次迭代来将其移出循环。

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

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

死代码消除

死代码是一个或多个代码语句，这些语句：

• 要么从未执行或无法访问，
• 要么如果执行，则其输出从未使用。

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

部分死代码

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

上面的控制流图描述了一段程序，其中变量“a”用于赋值表达式“x * y”的输出。让我们假设分配给“a”的值在循环内从未使用过。在控制离开循环后立即，将变量“z”的值赋给“a”，这将在程序的后面使用。我们在此得出结论， “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 只应计算一次。