下载掌阅APP，畅读海量书库
立即打开
循环的一次迭代通过数组下标的形式引用内存地址单元，这种引用方式可以分为读引用和写引用两种情况。前者从引用的内存地址单元获取数据，后者向引用的内存地址单元写入数据。在串行程序中，循环的不同迭代之间是顺序执行的。当循环的各个迭代访问各自独立的内存地址单元时，这些循环迭代之间将不会产生依赖关系，意味着循环不同迭代之间的顺序可以被优化编译器重新调整，以充分利用并行计算机体系结构上多数据流并行的特性。判定一个循环的不同迭代是否能够安全地并行执行需要分析不同的引用方式。早在1966年，Bernstein就指出了一种如何确定一个循环两个不同迭代 I 0 和 I 1 能够安全地并行执行的条件：如果
（1）迭代 I 0 不会向迭代 I 1 读引用的内存地址单元内写入数据；
（2）迭代 I 1 不会向迭代 I 0 读引用的内存地址单元内写入数据；
（3）迭代 I 0 和 I 1 不产生对相同内存地址单元的写引用；
那么编译器就可以通过调整原始程序中循环不同迭代之间的执行顺序，使迭代 I 0 和 I 1 能够被并行执行。这种判定方式被称为Bernstein 条件 ，它保证了调整计算顺序之后的程序仍然维持（preserve）原始程序的计算语义。一个先进的优化编译器必须具备判定不同循环迭代之间是否满足Bernstein条件的能力。有些书籍和论文中也将维持翻译为保留，指不破坏原始程序的计算语义，可理解为变换前后的程序对相同的输入产生相同的输出。
当两个不同的循环迭代不满足Bernstein条件时，就称这两个循环迭代之间是相关的，这种相关性被称为依赖。依赖代表了优化编译器在对程序实施变换时必须遵循的约束。首先，优化编译器对程序实施的变换必须保证数据按原始程序的语义被生产和使用，这种约束导致的依赖称为 数据依赖 。其次，由原始程序中使用控制结构引起的依赖称为 控制依赖 。本章所涉及的内容主要是数据依赖，在一些特殊的情况下，我们会考虑控制结构对数据依赖产生的影响，关于如何处理控制依赖，请参考文献[3]，本书将不再过多介绍控制依赖的具体内容。
如图3.1所示的 n 层循环嵌套代码，假设语句 S 0 通过循环索引（ i 1 ,i 2 ,…,i n ）的某种函数形式作为 m 维数组 A 的下标引用内存地址单元，那么语句 S 1 和 S 2 之间的数据依赖定义如下。
图3.1 循环嵌套语句之间的依赖关系代码示例
定义3.1 数据依赖
从语句 S 1 到语句 S 2 存在数据依赖或称语句 S 2 依赖于语句 S 1 ，当且仅当（1）语句 S 1 和 S 2 引用相同的内存地址单元，并且其中至少有一个语句的引用类型为写引用，（2）存在一条从语句 S 1 到 S 2 的可能的运行时执行路径。
不难发现，数据依赖定义中的第一个条件对应上文所述的Bernstein条件，第二个条件则限定了语句 S 1 和 S 2 在运行时可能的执行顺序，这将有助于消除那些不满足Bernstein条件同时又不可能存在运行时可执行路径的语句之间的依赖。例如，当语句 S 1 和 S 2 分别位于某个if控制语句的不同分支并且不满足Bernstein条件时，优化编译器可以判定这两个语句之间不存在数据依赖关系。虽然这里的数据依赖关系以循环结构为背景提出，但同样适用于顺序结构和分支结构下语句之间数据依赖的情况。
优化编译器能够正确分析依赖关系的意义在于依赖关系可以用于指导和选择优化编译器对循环嵌套实施的变换，这些变换将改变原始程序中循环不同迭代之间的执行顺序，但前提条件是不能破坏依赖关系，这样才能够保证在相同的输入下，变换后的程序将会产生与原始程序相同的执行结果。在优化编译器中，语句之间的数据依赖关系往往用 依赖图 的方式表示。
定义3.2 依赖图
语句的依赖图是一个有向环图，用有序二元组 G =（ V,E ）表示。其中 V 为结点或顶点集合，每个结点或顶点代表一个语句， E 为边集合，每个边代表两个语句之间的依赖。
对于图3.1所示的 n 层循环嵌套，语句 S 1 和 S 2 之间存在依赖关系时，优化编译器可以描述为语句 S 2 依赖于 S 1 。但对于图3.2所示情况，如果用语句 S 1 依赖于自身这样的描述显然是不够精确的，因为这种语句自身的依赖关系是由循环的不同迭代导致的。
图3.2 语句自身的依赖关系代码示例
精确描述循环嵌套内语句之间的依赖关系需要在描述过程中体现循环迭代。由于优化编译器需要维持变换前后有依赖关系的操作之间的“生产–消费”关系，这种关系可以描述成一个逻辑上的时间先后顺序关系。对于 n 层循环嵌套内的某个语句，我们可以对它指定一个 n 元组来表示其对应的逻辑时间节点，称为 字典序 。
定义3.3 字典序
给定一个 n 层循环嵌套，该循环嵌套内的语句 S 的字典序可以表示成一个 n 元组（ i 1 ,i 2 ,…,i n ），其中 i k （1≤ i ≤ n ）表示语句 S 在第 k 层循环上的字典序。
利用字典序，我们可以将语句进行实例化。所谓实例化是指根据字典序计算出某个语句在一次循环迭代中的执行实例。对于图3.1中的两个语句 S 1 和 S 2 ，其语句实例的集合可以表示成
{ S 1 （ i 1 ,i 2 ,…,i n ）: L k ≤ i k ≤ U k ∧ 1≤ k ≤ n } （3-1）
和
{ S 2 （ i 1 ,i 2 ,…,i n ）: L k ≤ i k ≤ U k ∧ 1≤ k ≤ n } （3-2）
类似地，图3.2中语句 S 1 的实例集合可以表示成
{ S 1 （ i ）:0≤ i ≤ N } （3-3）
其中， N 为编译阶段的符号常量。
字典序也可以用于精确描述如图3.2所示的自身依赖关系。我们可以称语句 S 1 的所有实例集合
{ S 1 （ i ）:1≤ i ≤ N } （3-4）
依赖于其自身的另外一个实例集合
{ S 1 （ i ）:0≤ i ≤ N− 1} （3-5）
字典序还提供了一种能够比较不同语句实例之间执行先后顺序的机制，我们称这种逻辑上的执行先后顺序关系为 顺序关系 （order relation）。当某个语句实例在另外一个语句实例之前执行时，我们称这种关系为 字典序小于 （lexicographically smaller）。
定义3.4 字典序小于
给定两个字典序（ i 1 ,i 2 ,…,i n ）和（ j 1 ,j 2 ,…,j n ），（ i 1 ,i 2 ,…,i n ） ≺ （ j 1 ,j 2 ,…,j n ）表示（ i 1 ,i 2 ,…,i n ）按字典序小于（ j 1 ,j 2 ,…,j n ），当且仅当
（1）（ i 1 ,i 2 ,…,i n −1 ） ≺ （ j 1 ,j 2 ,…,j n −1 ）；或者
（2）（ i 1 ,i 2 ,…,i n −1 ）=（ j 1 ,j 2 ,…,j n −1 ）和 i n <j n 同时成立。
由于逻辑运行时间节点是由循环迭代来定义的，因此我们也用字典序来表示某一个循环迭代。同时，当给字典序的 n 元组指定一个语句的名字时，这种命名的字典序可以用于表示某个语句实例的逻辑运行时间节点。仿照字典序小于的定义，可以很方便地定义字典序小于或等于≼、字典序大于 ≻ 和字典序大于或等于≽等符号。
下面我们来讨论依赖的分类。
根据数据依赖的定义，产生依赖的两个语句至少有一个会向内存地址单元写入数据，这导致程序中可能发生的依赖有3种，分别是：
（1） 流依赖 ：语句 S 1 向内存地址单元写入数据之后，语句 S 2 从相同的内存地址单元读出数据；
（2） 反依赖 ：语句 S 1 从内存地址单元读出数据之后，语句 S 2 向相同的内存地址单元写入数据；
（3） 输出依赖 ：语句 S 1 和 S 2 对相同的内存地址单元写入数据。
其中，流依赖也称为 真依赖 ，对应计算机程序中不同操作之间的“生产–消费”关系，通常为程序 数据流 关系的一个超集。反依赖和输出依赖也统称为 伪依赖 或 假依赖 ，这是因为这两种类型的依赖关系并不是因算法设计而产生的依赖关系，而是由于计算机上有限的内存地址空间而导致的假的依赖关系。当计算机上有足够的内存地址空间来存放程序引用的所有数据时，这种依赖关系可以通过标量扩展（scalar expansion）、数组私有化（array privatization）等优化方式来消除。在以指令级流水并行为目标的底层编译优化阶段，依赖也被称为数据冲突或数据相关。其中，流依赖对应“写后读”数据冲突，反依赖对应“读后写”数据冲突，输出依赖对应“写后写”数据冲突。
当两个语句都从相同内存地址单元读取数据时，根据依赖的定义，这两个语句之间不存在依赖关系。但是在有些优化编译器中，将这种关系称为 输入依赖 ，并且在实施循环变换时将这种关系也作为优化的目标来决定需要实现的循环变换，这是因为考虑输入依赖的循环变换会提升程序数据的时间局部性。
在定义数据依赖时，我们用从语句 S 1 到 S 2 存在数据依赖或称语句 S 2 依赖于 S 1 来描述依赖关系。在依赖图中，依赖关系对应两个结点之间的一条有向边，该有向边从依赖图中对应语句 S 1 的结点（称为依赖的 源点 ）出发，指向依赖图中的另外一个语句 S 2 对应的结点（称为当前依赖的 汇点 ）。对于循环嵌套内的依赖关系，可以用 距离向量 来描述。
定义3.5 距离向量
假设从 n 层循环嵌套一次迭代 （ i 1 ,i 2 ,…,i n ） 中的语句 S 1 到迭代 （ j 1 ,j 2 ,…,j n ） 中的语句 S 2 有依赖，则依赖距离向量 d 定义为长度为 n 的向量，即
d =（ j 1 −i 1 ,j 2 −i 2 ,…,j n −i n ） （3-6）
距离向量 d 描述的是产生依赖关系的两个语句实例对应字典序的差。这意味着（ i 1 ,i 2 ,…,i n ） ≺ （ j 1 ,j 2 ,…,j n ）当且仅当 d 的最左非0分量大于0。也就是说，依赖是由距离向量的最左边大于0的分量决定的。我们说字典序代表一个逻辑时间节点，如果将一个字典序（ i 1 ,i 2 ,…,i n ）从左至右的分量分别看作年、月、日等时间单位，那么一个字典序定义了一个日期。时间单位越大，意味着其对应的分量在字典序中的位置越靠左。当比较两个日期的先后关系时，比较结果由时间单位最大的分量决定。例如，2022年1月5日和2022年3月1日这两个日期可以分别用字典序（2022,1,5）和（2022,3,1）表示，前者在时间顺序上早于后者，这种顺序关系是由第二个分量决定的。
距离向量可以衍生出依赖 满足 的定义。
定义3.6 依赖满足
依赖在 i k （1≤ k ≤ n ）循环上得到满足，或称在第 k （1≤ k ≤ n ）层上得到满足，当且仅当 i k 是距离向量 d 的最左非0分量。
可以得出的一个结论是：一个正确的依赖距离向量 d 的最左非0分量一定是大于0的，否则在原始程序中一定存在一个语句实例，它的依赖源点在其后执行，这显然不符合算法设计的逻辑。
并不是所有的循环依赖都可以用距离向量描述，例如图3.3所示的循环嵌套，因无法确定距离向量的最低维度的分量，就不能用距离向量来描述。
图3.3 无法使用距离向量描述的循环依赖
与距离向量对应的还有方向向量，定义如下。
定义3.7 方向向量
假设从 n 层循环嵌套一次迭代（ i 1 ,i 2 ,…,i n ）中的语句 S 1 到迭代（ j 1 ,j 2 ,…,j n ）中的语句 S 2 有依赖，那么依赖方向向量 D 定义为长度为 n 的向量，其第 k （1≤ k ≤ n ）个向量为
方向向量的符号可以看作箭头，箭头的方向指向依赖的源点，或被解释成“依赖于”。有些书籍用方向向量作为高级优化的基础，因为方向向量代表了依赖源点和汇点之间的字顺序关系。本书将同时使用依赖距离向量和依赖满足来说明高级优化。
一个可能发生的情况是：距离向量的所有分量都为0,也就是说产生依赖的两个语句的字典序完全相同。如图3.1所示，语句 S 1 和 S 2 的字典序完全相同，也就是说依赖和循环迭代不相关，此时用字典序无法精确描述这种依赖关系，因此在优化编译器中有循环无关依赖和循环携带依赖之分。
并不是所有的循环都可以通过方向向量来描述依赖关系，例如图3.4所示的嵌套循环，由于每一次循环迭代都依赖于前一次的计算结果，因此整个循环是无法并行的。
图3.4 无法使用依赖向量和方向向量
语句 S 2 依赖于 S 1 ，要求存在一条可能的执行路径使 S 1 和 S 2 两者引用相同的内存地址单元，同时 S 1 的逻辑时间节点早于 S 2 的逻辑时间节点。可能满足上述条件的情况有两种：
（1）语句 S 1 和 S 2 在不同循环迭代内引用相同的内存地址单元，并且 S 1 对应的循环迭代按字典序小于 S 2 对应的循环迭代；
（2）语句 S 1 和 S 2 在相同循环迭代内引用相同的内存地址单元，但在循环内 S 1 的位置在 S 2 之前。
第一种情况属于 循环携带依赖 ，第二种情况属于 循环无关依赖 ，所以，我们有如下定义。
定义3.8 循环携带依赖
从语句 S 1 到语句 S 2 有一个循环携带依赖，当且仅当 S 1 在迭代（ i 1 ,i 2 ,…,i n ）中引用内存地址单元 M ，而 S 2 也在其迭代（ j 1 ,j 2 ,…,j n ）中引用相同的内存地址单元 M ，并且依赖在 i k （1≤ k ≤ n ）循环上得到满足。
对于循环无关依赖，我们需要在字典序的基础上再引入一个常数分量 d ，用于区分不同语句在相同循环迭代内的不同位置。假设 n 层循环内有 s 个语句，这 s 个语句在原始程序中有先后顺序，那么可以令1≤ d ≤ s 用以区分这 s 个语句在原始程序中的先后顺序。当把这 s 个语句想象成同一个语句的不同实例时，这 s 个语句可以看作一个 i n 循环完全展开之后的语句实例顺序排列，这样就可以将常数分量 d 理解成 i n 循环的字典序，两者的字典序关系也可以按照字典序大于或小于的关系来区分。所以，我们有如下定义。
定义3.9 循环无关依赖
从语句 S 1 对语句 S 2 有一个循环无关依赖，当且仅当存在 S 1 和 S 2 在相同循环迭代（ i 1 ,i 2 ,…,i n ）内，并且引用相同的内存地址单元，但两者的常数分量满足 d s 1 <d s 2 。
循环无关依赖和循环携带依赖对并行化产生的影响不同，原因在于不同并行化的粒度不一样，影响并行化的约束就会有所不同。例如，循环无关依赖不影响循环交换，这种变换将有利于开发外层循环的并行性，但循环交换必须考虑循环携带依赖。另一方面，循环无关依赖在实现最内层循环的向量化时是必须考虑的因素。此外，循环携带依赖还引申出其他书籍上常用的概念，即 依赖的层 ，它表示依赖在循环嵌套的第几层上得到满足。
研究依赖的原因在于依赖是优化编译器实现程序变换的约束，即只要满足原始程序的依赖，我们就认为这个变换是合法的。一个程序变换是合法的，通常是指变换后的程序不改变原始程序的语义，但语句的执行顺序和/或程序的控制结构可以发生改变，即变换后的程序只需要保证在相同的输入下产生与原始程序相同的计算结果，而程序运行的时间可以发生改变，这也是我们利用优化编译器实现程序自动变换的依据。我们对 等价计算 的定义如下。
定义3.10 等价计算
两个计算是等价的，如果对相同的输入，它们按相同的顺序执行输出语句时，输出变量产生相同的值。
我们将等价计算的定义局限在程序的输入和输出上，因为这是用户最关心的指标。这里给出的等价计算的定义对优化编译器的要求并不严格。对于一个程序而言，每一个执行任务的语句都是通过从内存地址单元读取数据或写入数据来改变程序的状态的，所以在程序执行过程中的某一时刻，程序的状态应该是指当前内存地址单元中所有数据值的集合，内存地址单元中数据值的变化意味着程序状态的变化。如果从更严格的角度来定义等价计算，那么只有两个完全以相同状态序列执行的计算任务才能够被认为是等价的。显然，这种定义对优化编译器实施循环变换的限制太过严格，因为这将会使那些改变程序语句顺序的变换无法保证变换后的程序与原始程序等价。
等价计算的定义允许用不同的语句序列计算相同的输出，不同的语句序列可能会导致程序在特定目标体系结构上所需的时间不同。优化编译器的目标就是找到一个在特定目标体系结构上执行时间最短或接近最短的语句执行顺序，从而达到在目标体系结构上提升程序性能的目的。这种为了寻求最短执行时间的语句序列变换的过程被称为 重排序变换 。
定义3.11 重排序变换
重排序变换是任何这样的程序变换，它仅改变程序语句的执行序列，但不增加或减少任意语句在循环迭代中的任何实例。
重排序变换不会增加或删减原始程序的任何语句实例，这意味着重排序变换后原始程序中的所有依赖都仍存在。但值得注意的是，重排序变换可能导致原始程序某个依赖的源点和汇点之间的顺序关系发生逆转。此时，该重排序变换将破坏原始程序的依赖关系，无法保证变换后的程序与原始程序具有相同的语义。因此，我们需要定义一个重排序变换的合法性原则，来阻止优化编译器对程序实施不合法的重排序变换。
定义3.12 重排序变换的合法性
一个应用到程序上的重排序变换是合法的，当且仅当它能够维持程序中的所有依赖，即该重排序变换维持原始程序所有依赖源点和汇点的顺序关系。
现在，我们可以根据前面所有的定义来给出优化编译器在实施重排序变换时所必须遵循的原则。
定理3.1 依赖的基本定理
如果一个重排序变换维持原始程序中的所有依赖，那么它将维持原始程序的语义
。
在以循环嵌套为核心的高级编译优化阶段，如何证伪循环迭代间和/或循环迭代内的依赖关系是实现循环并行、提升数据局部性的关键。现代优化编译器采用各种各样的依赖关系分析手段来证实依赖存在或不存在的事实。当不同的循环迭代之间或相同迭代内的不同语句之间的确存在数据依赖关系时，我们称一个优化编译器能够证实依赖；类似地，当语句之间一定不会存在数据依赖关系时，我们称一个优化编译器能够证伪依赖。证实依赖通常比较容易做到，因为对于未知情况，优化编译器总是可以保守地认为两个语句之间存在数据依赖。对于证实依赖，优化编译器不会实施任何重排序变换，也不会有违反原始程序计算语义的风险。然而，优化编译器总是试图在依赖不存在的情况下利用静态分析手段证伪依赖，但受到静态分析能力的限制，证伪依赖并不是一件容易的事情。
一个优化编译器证实或证伪依赖的过程称为 依赖关系分析 。根据优化编译器的目标不同，依赖关系分析的结果可以包含许多信息，我们将在后面章节更具体地介绍这些内容。根据两个语句之间数据依赖的定义，两个语句之间存在数据依赖的一个前提条件是这两个语句访问相同的内存地址单元，而多重循环嵌套中的语句通过数组下标访问内存地址单元，所以优化编译器证伪依赖的能力往往取决于循环嵌套中数组下标表达式的复杂度。现在我们将依赖关系分析局限在判定两个语句访问相同内存地址单元所使用的数组下标是否相等，即 依赖测试 的范畴。
然而，即便我们将依赖关系分析局限在依赖测试这样的范畴，优化编译器面临的问题仍然是十分复杂的。在实际应用程序中，数组下标表达式可以是任意形式，这意味着依赖测试是一个不可判定问题，因为编译器无法在编译阶段确定数组下标在运行时的值，也意味着优化编译器在静态分析阶段不可能直接根据数组下标表达式的值确定依赖是否存在。幸运的是，一个优化编译器虽然没有办法在编译阶段确定某个数组下标表达式可能的值，但可以根据循环和程序参数确定某个数组下标可能的取值范围。因此，一个简单而直观的依赖测试方法是通过比较两个不同的数组下标表达式可能的取值范围是否相交来证实或证伪依赖。
数组下标表达式用于描述某个语句访问的内存地址相对于数组起始地址的偏移量，它是循环索引变量的函数。由于字典序和循环索引变量构成的向量完全对应，所以一个数组下标表达式可以看作一个循环嵌套字典序的函数。这种函数关系可以是所有循环索引变量的任意组合形式，比如一个数组下标表达式可以是所有循环索引变量的非齐次和/或非线性表达式函数，也可以是另外一个数组的某个元素。用现有的数学方法去分析所有可能出现的情况是一项十分困难的任务。即便利用数学方法能够对这样一般化的问题给出一个明确的结果，也很难将数学方法利用计算机程序实现。
所以，在现代优化编译器中，结合实际应用程序中出现的大多数情况，优化编译器对数组下标表达式进行了进一步简化，即在未明确说明的前提下，一个优化编译器总是假设数组下标表达式是所有循环索引变量的仿射表达式，即所有的下标表达式的形式为
a 1 ×i 1 + a 2 ×i 2 + … + a n ×i n + c （3-8）
其中， i k （1≤ k ≤ n ）为循环索引变量， a k （1≤ k ≤ n ）为该数组下标表达式中循环索引变量对应的系数。从直观意义上讲，仿射变换可以看作线性变换的基础上增加一个常数项。为了描述方便，我们省略乘法符号，即优化编译器总假设一个数组下标表达式具有
a 1 i 1 + a 2 i 2 + … + a n i n + c （3-9）
的形式。
判定两个形如式（3-9）的数组下标表达式是否相等，等价于判定一个线性丢番图（Diophantine）
方程组是否有整数解，这是一个NP完全问题。丢番图方程也被称为不定方程或整系数多项式方程，方程中的未知量取值只能是整数。所以，即便我们已经对数组下标表达式做了许多简化处理，在优化编译器中证伪依赖依然是非常困难的。在理想情况下，我们总是期望一个优化编译器仅在两个数组下标表达式不可能相等时才证伪依赖，但是由于证伪依赖问题的复杂性，这种理想的情况在当前的优化编译器中也无法实现。我们必须考虑的一个情况是：在既不能证实也不能证伪依赖时，优化编译器应该如何处理。
如果在不能证实或证伪依赖的情况下，一个优化编译器激进地认为两个语句之间不存在数据依赖，这种情况下，优化编译器就有可能对程序实施重排序变换以提升程序的性能。如果在运行时两个数组下标表达式的值相等，那么变换后的程序将无法维持原始程序的语义，这将违反等价计算的定义。所以，在不能证实或证伪依赖的情况下，一个优化编译器不能认为两个语句之间不存在数据依赖。也就是说，优化编译器在无法证实或证伪依赖的情况下，必须保守地认为语句之间存在数据依赖。这种采用保守策略的依赖测试也被称为 保守测试 。事实上，编译器所采取的优化必须都是保守的，因为与性能相比，优化的正确性总是更重要的。
在这些前提条件下，我们开始考虑如何判定数组下标是否有可能相等。对于如图3.1所示的情况，要判定数组 A 的下标是否有可能相等，就要考虑数组下标的所有维度。如果我们同时考虑数组的所有维度，那么显然问题将变得复杂，判定过程也更加烦琐；如果程序允许优化编译器对每个维度独立地证实或证伪依赖，那么问题将变得相对简单。所以，从下标表达式不同维度是否可以独立判定的角度来看，可以将多维数组的下标表达式分为 独立下标 和 耦合下标 两大类 [2 , 22] 。
定义3.13 独立下标
假设
n
层循环嵌套内存在对
m
维数组
A
的内存地址访问，如图3.1所示。称数组
A
的第
k
（1≤
k
≤
m
）个下标为独立下标，当且仅当
（1≤
l
≤
n
）,
（1≤
k
′
≤
m∧k
′
≠
k
），其中
表示循环索引
i
l
在第
k
个下标表达式
h
k
（
i
1
,i
2
,…,i
n
）中的系数。
对应地，我们有如下定义。
定义3.14 耦合下标
假设 n 层循环嵌套内存在对 m 维数组 A 的内存地址访问，如图3.1所示。称数组 A 的第 k （1≤ k ≤ m ）个下标为耦合下标，当且仅当该下标不是独立下标。
优化编译器总是可以单独对独立下标表达式判定依赖是否存在，并且判定的结果总是可靠的。换句话说，如果一个优化编译器能够证伪独立下标之间的依赖，那么这个多维数组就不存在依赖。相反，耦合下标虽然也允许优化编译器独立判定某个维度下标的依赖，但结果却是不可靠的，因为该下标维度上的循环索引还会在其他下标维度上存在，该维度上存在依赖，并不代表着多维数组的两次引用之间就一定存在依赖。
更进一步地，我们来讨论多维数组下标某个维度上的复杂性。对于多维数组下标的一个维度，我们可以根据该维度上出现的循环索引个数将某个数组下标维度划分为：
（1）ZIV（Zero Index Variable）下标：下标中不包含任何循环索引的引用；
（2）SIV（Single Index Variable）下标：下标中仅有一个循环索引的引用；
（3）MIV（Multiple Index Variable）下标：下标中有多于一个循环索引的引用。这些分类方式为高效的依赖测试奠定了良好的基础。下面我们介绍几种不同的依赖测试。