compiler-optimization - GCD 测试 - 测试循环语句之间的依赖关系

Question

我理解 GCD 如何在一个简单的例子上工作，如下所示:

for(i=1; i<=100; i++)
{
        X[2*i+3] = X[2*i] + 50;
}

我们首先将其转化为以下形式:X[a*i + b]和 X[c*i + d]a=2 , b=3 , c=2 , d=0和 GCD(a,c)=2和 (d-b)是 -3 .自 2不分-3 ，没有依赖是可能的。

但是我们如何在双重嵌套循环上进行这个 GCD 测试呢？

例如:

for (i=0; i<10; i++){
   for (j=0; j<10; j++){
       A[1+2*i + 20*j] = A[2+20*i + 2*j);
    }
}

Answer 1

在嵌套循环情况下应用 GCD 的“简单”方法是仅在数组本身是多层的情况下应用它；即，原始源代码使用多个下标而不是已经线性化的表达式。当然，如果您可以“反向转换”这些线性化下标，那么您将拥有等价物。

一旦您将问题转换为多维度问题，那么您可以简单地应用 GCD 测试“维度按维度”。如果任何维度显示没有依赖关系，那么您可以停止并声明整个多维度下标序列没有依赖关系。

当然，关键是将转换为多维索引问题为您提供了一个很好的特性，即在单个索引值和相应的索引表达式元组之间存在一对一的映射。没有这个问题就更难了。

这是我在 70 年代在 ASC Fortran 矢量化编译器中采用的方法，并且效果很好，特别是与非不相交情况的定向下标分析结合使用。 GCD 测试本身确实是不够的，但它确实为您提供了一种相对便宜的方法，可以在分析中尽早做出决定，然后您可以避免更昂贵的依赖性分析。