程序优化（去除相关性、公共子表达式优化）

type

status

date

slug

summary

去除相关性

一、什么是相关性？

依赖关系分为控制依赖关系和数据依赖关系。

1、数据依赖

数据依赖是指两个操作访问同一个变量，且两个操作中有一个写操作。数据依赖依据对变量进行读写的先后顺序分为真依赖、输出依赖和反依赖3种类型。

依赖关系	示例	说明
真依赖	a=1;b=a	对a进行先写后读的操作（RAW）
输出依赖	a=1;a=2	对a进行先写后写的操作（WAW）
反依赖	a=b;b=1	对b进行先读后写的操作（WAR）

反依赖和输出依赖并没有引发语句之间数据值的传递，可以通过变量重命名等方式消除。真依赖引发了语句之间数据值的传递无法被消除。

2、控制依赖

控制依赖关系是由程序的控制结构引起的。

例如：

S2是否执行完全取决于语句S1中表达式的结果。

所以我们要减少去除依赖，下面将介绍一些方法破除依赖关系。

二、一些破除依赖关系的方法

1、标量拓展方法

首先介绍一下标量类型和标量扩展的区别：标量类型只能包含一个值。例如：整数类型int、short、long等、字符类型char、浮点类型float、double等、布尔类型bool都属于标量类型。标量拓展是将循环中的标量引用用编译器生成的临时数组引用替换，可以有效地消除一些由内存单元的重用而导致的依赖。例：6-75优化前

可以看到在优化前将T作为了一个int型的标量类型。T作为标量类型将数据临时存储在相同的存储单元里面。解决方法：如果每个迭代使用一个不同的单元作为临时变量，那么这些依赖就不复存在。可以消除标量类型带来的依赖，实现向量化。（就好像在运行QQ时，16GB运行内存的手机永远会比2GB运行内存的手机流畅）例：6-76优化后

优化前运行时间为：

优化后运行时间为：

2、标量重命名

标量重命名的目的是减少或者消除依赖例：代码6-77

在代码6-77里面S1语句到S4语句之间存在真依赖（对T进行先写后读），S1到S3之间存在输出依赖（对T进行先写后写的操作）。根据文档前面的内容可知，输出依赖被称为伪依赖，我们可以对伪依赖进行消除。解决方法：例代码6-78 将S3语句中的T重命名为T1后，程序语句中的S1到S4的真依赖，以及S1到S3的输出依赖都被消除掉。实现了对程序的相关优化。

优化前结果：

优化后结果：

3、数组重命名

数组的存储单元被重用有时会导致不必要的反依赖和输出依赖（这俩都是伪依赖），可以通过使用数组重命名的方法进行消除。数组重命名的本质在于区分“值传递“（真依赖，图a）和“相同存储空间竞争”（没有数据流动，是伪依赖，图cd）。如果我们令其使用不同的存储空间，就可以消除冗余的伪依赖。

例：代码6-79

在代码6-79中，代码S1到S3形成了一个依赖环。A[i]在循环中被用来传递两个不同的值（S1语句一次，S3语句一次，WAW），S2和S3由于A[i]形成反依赖（WAR）。所以可以通过数组重命名技术消除反依赖和输出依赖。解决方法例代码6-80：新定义一个一个A1[N]数组

可以看出消除了输出依赖和反依赖。但是新增加一个数组需要增加额外的内存空间。所以数组重命名的安全性和有利性比标量重命名复杂，这种代价可能会严重影响程序的性能。

优化前：

优化后：

公共子表达式优化

当程序中表达式含有两个或者更多的相同子表达式，仅需要计算一次子表达式的值就可以。含义是：如果一个表达式E之前已经被计算过了，并且从先前的计算到现在E中所有变量的值都没有发生变化，那么E 的这次出现就称为公共子表达式。对于这种表达式，没有必要花时间再对它重新进行计算，只需要直接用前面计算过的表达式结果代替E。其实就是删除冗余的子表达式，从而减少计算量和提高程序的运行速度。

例：代码6-81

从代码里面可以看出，多次计算了(a+b)的值，如果我们将(a+b)的运算结果存入中间变量里面，这样就少了几次加法操作。解决方法：添加中间变量tmp。优化后代码：

优化前结果：

优化后结果：