数据依赖分析

基本块内（顺序语句）的依赖关系比较简单。通常依赖关系分析的目的是获取嵌套循环L中的依赖关系信息，这需要找出循环体中每一对变量所引起的依赖关系。标量可以看作是数组元素的蜕化情形，且不同数组的元素不会引用相同的存储单元，因此依赖关系分析的关键在于判断L中两个下标含索引变量的同名数组元素^[1]在给定条件下是否表示同一个存储单元。在实际程序中，绝大多数数组元素的下标都是循环索引变量的线性表达式，因此主要考虑线性下标数组元素引用导致的依赖关系问题。

依赖关系分析可以转化为求解一组满足不等式的线性方程组整数解的问题，其中线性方程组根据循环索引变量的线性表达式得到，不等式根据循环边界得到。求解依赖关系的问题就是整数线性规划问题，整数线性规划问题是一个NP完全问题，目前没有已知的多项式复杂性的解法，通常采用测试的方法求解，求解算法可以分为精确测试法和近似测试法两类。精确测试法实际地求出线性方程组的整数通解，并检查是否有满足不等式约束的解。在依赖关系存在时，它可以给出相关迭代对集合和依赖距离，但是不能处理复杂的情况。近似测试法使用丢番图方程的理论，应用GCD（Greatest Common Divisor，最大公约数）检查线性方程组是否有整数解，然后测试方程组满足不等式约束条件的实数解是否存在。如果不存在实数解，则肯定不存在依赖关系，否则假设依赖关系存在。