上一节:

  编译器设计 - 代码优化

  • 简述

    优化是一种程序转换技术，它试图通过使代码消耗更少的资源（即CPU、内存）并提供高速来改进代码。
    在优化中，高级通用编程结构被非常有效的低级编程代码所取代。代码优化过程必须遵循以下三个规则：
    • 输出代码不得以任何方式改变程序的含义。
    • 优化应该提高程序的速度，如果可能的话，程序应该需要更少的资源。
    • 优化本身应该很快，并且不应该延迟整个编译过程。
    可以在编译过程的各个级别上努力优化代码。
    • 一开始，用户可以更改/重新排列代码或使用更好的算法来编写代码。
    • 生成中间代码后，编译器可以通过地址计算和改进循环来修改中间代码。
    • 在生成目标机器代码时，编译器可以利用内存层次结构和 CPU 寄存器。
    优化可以大致分为两种类型：机器无关和机器相关。

  • 与机器无关的优化

    在此优化中，编译器接收中间代码并转换不涉及任何 CPU 寄存器和/或绝对内存位置的部分代码。例如： 
    
do
{
   item = 10;
   value = value + item; 
} while(value<100);
    此代码涉及标识符项的重复分配，如果我们这样说： 
    
Item = 10;
do
{
   value = value + item; 
} while(value<100);
    不仅应该节省 CPU 周期，而且可以在任何处理器上使用。

  • 机器相关优化

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

  • 基本块

    源代码通常有许多指令，这些指令总是按顺序执行，被认为是代码的基本块。这些基本块之间没有任何跳转语句，即在执行第一条指令时，同一基本块中的所有指令都将按照它们出现的顺序执行，而不会失去程序的流程控制。
    一个程序可以有各种结构作为基本块，如 IF-THEN-ELSE、SWITCH-CASE 条件语句和循环，如 DO-WHILE、FOR 和 REPEAT-UNTIL 等。

    基本块识别

    我们可以使用以下算法来查找程序中的基本块：
    • 搜索基本块开始的所有基本块的标题语句：
      • 程序的第一个语句。
      • 作为任何分支目标的语句（条件/无条件）。
      • 任何分支语句之后的语句。
    • 标题语句及其后面的语句构成一个基本块。
    • 基本块不包括任何其他基本块的任何标题语句。
    从代码生成和优化的角度来看，基本块都是重要的概念。
    基本块
    基本块在识别变量方面发挥着重要作用，这些变量在单个基本块中被多次使用。如果任何变量被多次使用，则分配给该变量的寄存器内存不需要清空，除非该块完成执行。

    控制流图

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

  • 循环优化

    大多数程序在系统中作为循环运行。有必要优化循环以节省 CPU 周期和内存。循环可以通过以下技术进行优化：
    • Invariant code：驻留在循环中并在每次迭代中计算相同值的代码片段称为循环不变代码。该代码可以通过将其保存为仅计算一次而不是每次迭代来移出循环。
    • Induction analysis：如果一个变量的值在循环内被循环不变的值改变，则该变量称为归纳变量。
    • Strength reduction: 有些表达式会消耗更多的 CPU 周期、时间和内存。这些表达式应该替换为更便宜的表达式，而不会影响表达式的输出。例如，乘法 (x * 2) 在 CPU 周期方面比 (x << 1) 更昂贵，并且产生相同的结果。

  • 死码消除

    死代码是一个或多个代码语句，它们是：
    • 要么从未执行过，要么无法到达，
    • 或者如果被执行，它们的输出永远不会被使用。
    因此，死代码在任何程序操作中都不起作用，因此可以简单地消除它。

    部分死代码

    有些代码语句的计算值仅在某些情况下使用，即有时使用这些值，有时不使用。这样的代码被称为部分死代码。
    部分死代码
    上面的控制流程图描述了一个程序块，其中变量“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 应该只计算一次。
上一节: