基本块的优化

本文概述

• 1.保留结构的转换
• 2.代数变换

优化过程可以应用于基本块。在优化时, 我们不需要更改由该块计算的表达式集。

基本块优化有两种类型。这些如下：

1. 保留结构的转换
2. 代数变换

1.保留结构的转换

基本块上的主要保留结构转换如下：

• 常见子表达式消除
• 消除死代码
• 重命名临时变量
• 两个独立的相邻语句的互换

（a）共同的副表达消除：

在公共子表达式中, 不需要一遍又一遍地对其进行计算。取而代之的是, 你可以一次计算它, 并在再次遇到它时将其保存在引用的位置。

a : = b + c
b : = a - d 
c : = b + c                        
d : = a - d

在上面的表达式中, 第二和第四表达式计算出相同的表达式。因此, 可以按以下方式转换块：

a : = b + c 
b : = a - d                                                       
c : = b + c
d : = b

（b）消除死代码

• 程序可能包含大量无效代码。
• 一旦声明和定义一次, 而忘记将其删除, 则可能导致这种情况, 因为它们毫无用处。
• 假设语句x：= y + z出现在一个块中, 并且x是死符号, 这意味着它以后将不再使用。然后, 无需更改基本块的值, 就可以安全地删除此语句。

（c）重命名临时变量

可以将语句t：= b + c更改为u：= b + c, 其中t是一个临时变量, u是一个新的临时变量。 t的所有实例都可以用u替换, 而无需更改基本块值。

（d）陈述的互换

假设一个块具有以下两个相邻的语句：

t1 : = b + c 
t2 : = x + y

当t1的值不影响t2的值时, 这两个语句可以互换而不会影响block的值。

2.代数变换

• 在代数变换中, 我们可以将表达式集更改为代数等效集。因此, 可以从基本块中消除表达式x：= x + 0或x：= x * 1, 而无需更改表达式集。
• 恒定折叠是一类相关的优化。在这里, 在编译时, 我们评估常量表达式, 并用它们的值替换常量表达式。因此, 表达式5 * 2.7将被13.5代替。
• 有时, 意外的公共子表达式由诸如<=, > =, <, >, +, =等的关系运算符生成。
• 有时, 在不更改基本块值的情况下, 将关联表达式应用于公开子表达式。如果源代码具有分配

a:= b + c
                e:= c +d +b

可能会生成以下中间代码：

a:= b + c
                t:= c +d
                e:= t + b