编译器设计-代码优化

编译器设计-代码优化

Compiler Design - Code Optimization

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

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

输出代码无论如何不能改变程序的含义。

优化应该提高程序的速度，如果可能的话，程序应该需要更少的资源。

优化本身应该是快速的，不应该延迟整个编译过程。

优化代码的工作可以在编译过程的不同级别进行。

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

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

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

优化可以大致分为两类：独立于机器的优化和依赖于机器的优化。

机器独立优化Machine-independent Optimization

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

do

{

item=10;

value=value + item;

}while(value<100);

此代码涉及重复分配标识符项，一旦：

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

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

机器相关优化Machine-dependent Optimization

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

基本块Basic Blocks

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

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

基本块识别Basic block identification

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

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

程序的第一个语句。

任何分支的目标语句（条件/无条件）。

任何分支语句之后的语句。

Header语句及其后面的语句构成一个基本块。

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

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

基本块在识别变量方面起着重要作用，这些变量在一个基本块中被多次使用。如果某个变量被多次使用，则分配给该变量的寄存器内存不需要清空，除非块完成执行。 控制流图Control Flow Graph

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

回路优化Loop Optimization

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

不变代码Invariant code：驻留在循环中并在每次迭代时计算相同值的代码片段称为循环不变代码。通过将代码保存为只计算一次而不是每次迭代，可以将此代码移出循环。

归纳分析Induction analysis：如果一个变量的值在循环中被循环不变的值改变，则称之为归纳变量。

强度降低Strength reduction：有些表达式消耗更多的CPU周期、时间和内存。在不影响表达式输出的情况下，这些表达式应替换为更便宜的表达式。例如，乘法（x*2）在CPU周期方面比（x<1）昂贵，并且产生相同的结果。

死码消除Dead-code Elimination

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

要么从未执行，要么无法实现，

或者如果执行了，它们的输出就永远不会被使用。

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

部分死代码Partially dead code

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

上面的控制流图描述了一个程序块，其中变量“a”用于分配表达式“x*y”的输出。假设分配给“a”的值从未在立即循环在控件离开循环后，“a”被赋给变量“z”的值，该值稍后将在程序中使用。我们在此得出结论，“a”的赋值代码从未在任何地方使用过，因此它有资格被删除。

同样，上面的图片描述了条件语句总是false，这意味着以true case编写的代码永远不会执行，因此可以删除它。

部分冗余Partial Redundancy

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

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

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

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

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

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

这里，条件是真是假；y OP z只应计算一次。