Conversion of control dependence to data dependence

[ysh329]

J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren.
Conversion of control dependence to data dependence. In POPL, pages 177–189. ACM, 1983.
https://dl.acm.org/doi/pdf/10.1145/567067.567085

1. 试图解决的问题：

文章解决的问题是如何将控制依赖（Control Dependence）转换为数据依赖（Data Dependence），以便在复杂的控制流情况下，能够更有效地进行程序分析和自动向量化。在存在复杂的控制流时，仅依赖数据依赖是不够的，因为控制依赖可能会引入循环，这些循环可能无法被向量化。

2. 论文的关键思想和关键见解：

关键思想：通过消除goto语句并引入逻辑变量，将所有的控制依赖转换为数据依赖。这样，语句间的控制依赖就变得显式，并可以通过控制逻辑变量的定义和使用来表达。
关键见解：文章提出了一种系统化的方法，将控制依赖转换为数据依赖，使得原本因控制流复杂而无法向量化的代码区域得以转换和向量化。

3. 关键机制及其实现：

IF转换（IF Conversion）：一种将控制流转换为基于条件的执行流程的技术。在IF转换中，所有的goto语句被消除，并通过逻辑变量来控制语句的执行。例如，原本通过goto实现的跳转，通过设置条件变量来实现相同的逻辑。
前向转换（Forward Conversion）：一种特殊类型的IF转换，它处理前向分支，即分支目标在分支语句之后。通过设置条件变量来控制语句的执行，从而消除goto语句。
分支重定位（Branch Relocation）：一种处理退出分支（exit branches）的技术，它通过引入退出标志（exit flags）和逻辑变量来重新组织程序流，确保在修改后的程序中仅在原始程序中会执行该语句时才执行。
前向分支（Forward Branch）：指分支目标在分支语句之后的控制流。例如，IF (condition) GOTO label，如果条件满足，则程序会跳转到label处执行。
后向分支（Backward Branch）：指分支目标在分支语句之前的控制流，这种分支会创建隐含的循环。由于它们不能直接被消除，需要特别的处理方法。

4. 主要结果和结论：

文章展示了IF转换算法在PFC（一个在莱斯大学开发的实验性向量化程序）中的实现，并证明了该算法能够处理复杂的控制流问题，使得原本无法向量化的代码区域得以转换和向量化。通过将控制依赖转换为数据依赖，PFC能够向量化包含条件转移的循环语句。此外，文章还讨论了布尔简化（Boolean Simplification）在IF转换中的应用，以及如何通过简化逻辑条件来提高输出程序的可读性。

最终，文章得出结论，IF转换是一个极其有价值的转换过程，它不仅对向量化有重要意义，还可以应用于数据流语言、代码结构化和goto消除等领域。它证明了在实际的程序转换系统中，任何分支构造都可以成功地转换为结构化构造。

关键词解释：

• 向量化（Vectorization）：一种程序优化技术，将标量操作转换为可以并行执行的向量操作，以提高性能。
• 控制依赖（Control Dependence）：当一个语句的执行流依赖于另一个语句的执行结果时，称这两个语句之间存在控制依赖。
• 数据依赖（Data Dependence）：当一个语句的执行需要另一个语句计算的数据时，称这两个语句之间存在数据依赖。

[ysh329]

摘要

程序分析方法，特别是那些支持自动向量化（Automatic Vectorization，一种编译器优化技术，它能够自动识别并转换程序中的循环或代码段，使其能够在向量处理器上并行执行，从而提高性能），基于语句间依赖的概念，当一个语句计算的值被另一个语句需要时，两个语句之间就存在依赖。基于这个概念，已经开发出了强大的程序转换系统，这些系统能够将顺序程序转换成更适合向量或并行机器的形式。

语句间依赖（Inter-statement Dependence）：在程序分析中，指一个语句的执行可能依赖于另一个语句的执行结果或计算值：

• 数据依赖（Data Dependence）：程序中一个操作需要另一个操作的数据作为输入，这种依赖关系限制了操作可以并行执行的方式。
• 控制依赖（Control Dependence）：程序的执行流程中的一个决策点（如条件语句）会影响其他语句的执行，这种依赖关系与数据流动无关，而是与控制流相关。

这些系统中的依赖分析是基于数据依赖的。在复杂控制流存在的情况下，仅仅数据依赖不足以转换程序，因为控制依赖的引入。当一个语句的执行可以阻止另一个语句的执行时，就存在控制依赖。控制依赖并不适合方便地融入基于依赖的程序转换器。

一种解决方案是通过消除goto语句（goto Statement，一种无条件跳转语句，允许程序流程从一个位置跳转到另一个位置，这可能会使得程序的控制流变得复杂）并引入逻辑变量来控制程序中语句的执行，将所有控制依赖转换为数据依赖。在这个方案中，动作语句被转换为IF语句。IF语句的条件表达式中的变量可以被视为控制被控制语句的输入。结果是，语句之间的控制依赖变成了通过控制逻辑变量的定义和使用明确表达的数据依赖。

本文提出了一种系统化的方法，以这种方式将控制依赖转换为数据依赖。这里介绍的算法已在PFC中实现，PFC是一个在莱斯大学编写的实验性向量化程序。

[ysh329]

这篇文章描述了一个名为PFC（Parallel Form Converter）的系统，它能够将用Fortran编写的顺序程序转换成Fortran 8x形式的并行程序。转换的核心思想是识别并替换循环（loops）为数组操作（array operations），以利用向量计算机和阵列处理器的能力。下面是PFC转换标量程序为向量程序的一般步骤，以及一个具体的Fortran代码示例和其转换过程：

转换步骤概述：

1. 子标标准化（Subscript Standardization）：将所有子标转换为循环变量的线性函数。
2. 依赖性测试（Dependence Testing）：检测循环中的语句是否依赖于自身，即是否在循环迭代中使用了之前迭代的结果。
3. 向量代码生成（Vector Code Generation）：如果语句不依赖于自身，则将其转换为向量语句。

具体Fortran代码示例：

考虑以下Fortran代码片段，它是一个简单的温度更新循环，其中使用了嵌套循环：

DO 100 I = 1, N
  T(I) = T(I) + DT * (Q(I) - Q(I+1))
100 CONTINUE

这里，T 是温度数组，Q 是热流数组，DT 是时间步长，N 是数组的大小。

转换过程：

1. 子标标准化：首先，我们需要确保循环中的所有数组索引都是循环变量的线性函数。在上面的例子中，T(I) 和 Q(I) 已经是 I 的线性函数，而 Q(I+1) 需要被转换，以避免循环中的递归依赖。

2. 循环变量替换：如果 Q(I+1) 可以被替换为不依赖于当前迭代的表达式，例如，如果 Q 的值在每次迭代中都是独立的，我们可以简单地将 Q(I+1) 替换为 Q(MOD(I, N) + 1)，以避免递归引用。

3. 依赖性测试：使用依赖性测试来确定是否可以将循环转换为向量形式。这通常涉及到检查循环中的语句是否形成了依赖链，即一个语句是否使用了另一个在同一循环中较早迭代的语句的输出。

4. 向量代码生成：如果依赖性测试表明没有自身依赖，那么可以将循环转换为向量形式，如下所示：

T(1:N) = T(1:N) + DT * (Q(1:N) - Q(2:N+1))

这里，我们使用了数组切片来表示整个数组的操作，这是Fortran 8x或更高版本中支持的向量操作。

注意：

• 实际的转换过程可能更复杂，需要考虑多种因素，如循环的嵌套、条件语句、数组的多维性等。
• PFC系统可能还包含其他优化步骤，如死代码消除、循环展开等，以进一步提高并行效率。

这个例子展示了如何将顺序Fortran程序转换为可能在向量计算机上更高效执行的并行形式。在实际应用中，PFC会使用更复杂的算法来分析和转换程序，以充分利用硬件的并行处理能力。

[ysh329]

2.6 用户定义的子程序

有一些用来增强用户定义的sub-routines和函数的方法：

1. array会作为subroutines的传参
2. 一个函数的返回值可能是array
3. 标量函数的声明可以用在array或vector上，来进行elementwise的操作。

3. The Translation Process

现在把 Fortran 程序转换为 Fortran 8x的向量化的陈鼓型，下面将会描述几个重要的问题。如下是被转换的程序：

最终目的是，将(3)和(4)这两条移除，并转为向量赋值。只要没有在串行循环和向量语句之间的语义上的不同，就是有可能的。考虑一个更加简单的例子：

如果将这个转为如下的向量赋值：

我们必须确保转换前后没有语义上的不同。

[ysh329]

下面，我们将会介绍如何把 Fortran 程序转换为 Fortran 8x 的向量化版本，下面从几个重要的方面来讲。假设要向量化的 Fortran 代码片段如下：

DO 20 I = 1, 100
    KI = I
    DO 10 J = 1, 300, 3
        KI = KI + 2
        U(J) = U(J) * W(KI)
        V(J+3) = V(J) + W(KI)
    CONTINUE
CONTINUE

[ysh329]

在编译器优化中，"DO-loop normalization"也称为"循环规范化""循环标准化"，是一种将循环变换为一种更标准形式的技术，循环规范化的过程一般都会有（下面仅罗列当前关注的重点，并非完整流程）：

• 统一起始点/步长等：使得循环变量从1开始迭代，直到达到某个上限值，步长即增量为1。起始点和步长的统一，使得循环相关的变量简单且常见（也可以说是代码直观，可读性好），有助于编译器更容易识别、分析和应用特定的优化策略。
• 简化条件表达式：规范化后的循环条件通常更简单，比如使用 <= 或 < 来比较循环变量和上限值，这减少了条件表达式的复杂性。
• 引入新变量：如果需要，引入新的循环变量以实现这种变换，从而减少循环体内部对原始循环变量的依赖和变换。
• 替换引用：在循环内部，将对旧循环变量的所有引用替换为新循环变量的表达式。

规范化后循环控制结构形式更标准，当所有的循环都遵循相同的模式时，循环结构就具有更高的一致性，这有助于开发者更快地理解和修改代码。

循环变换前：

for (int i = 0; i < n; i++) {
    // 使用i的代码
}

循环变换后：

for (int i = 1; i <= n; i++) {
    // 使用i的代码，可能需要将i替换为i-1
}

循环变量i从1开始，每次增加1，直到达到上限n。如果循环体内部使用了原始的循环变量，比如数组索引或计算，这些引用将需要根据新的循环变量进行调整。

循环规范化的目的是为了让编译器更容易识别和应用其他优化技术，比如循环展开（loop unrolling）、强度削弱（strength reduction）等。通过规范化，编译器可以生成更高效的代码，因为它简化了循环控制结构，使得循环的行为更加清晰和一致。

还是回到我们的 fortran 示例代码中：

DO 20 I = 1, 100
    KI= I
    DO 10 j = 1, 100
        KI = KI + 2
        U(3*j-2) = U(3*j-2)*W(KI)
        V(3*j+1) = V(3*j-2)+W(KI)
    CONTINUE
    J = 301
CONTINUE

[ysh329]

[ysh329]

一个在循环的一个迭代中计算值并在另一个迭代中直接或间接被同一语句使用的语句，不能通过翻译来向量化；否则，该语句可能会被向量化。

DO 100 I = 1, 100
    A(I) = A(I) + C
100 CONTINUE

!可以翻译向量化为如下代码

A(1:100) = A(1:100) + C

但是关键是fetch before store的问题，下面不能通过翻译来向量化。

DO 100 I = 1, 100
    A(I) = A(I - 1) + B(I)
100 CONTINUE

正确区分这两种情况需要研究值在定义和使用之间的流动。

经典的数据流分析将变量的定义和使用之间的关系建模为一个有向图：

• 其中每个顶点代表一个语句。
• 每条边代表从定义到使用的直接数据流链接。
• 这些链接通常称为数据依赖。

Use-Def Chain

在编译器理论中，"use-def chain"（使用-定义链）是一种数据流分析技术，用于追踪程序中变量的定义（def）和使用（use）之间的关系。这种链通过记录每个变量的最后一次赋值位置和第一次使用位置来帮助理解程序的行为，从而可以进行各种优化。

例如，考虑以下简单的Fortran代码片段：

A = B + C  ! 定义A
D = A + E  ! 使用A
A = F      ! 重新定义A
B = G      ! 定义B
C = A * H  ! 使用A

在这个例子中，我们可以看到：

• 变量A首先在A = B + C中被定义，然后在D = A + E中被使用。
• 接着A在A = F中被重新定义，这意味着之前定义的A的使用（即D = A + E中的A）和这个新的定义没有关系。
• 变量B在B = G中被定义，但在上面的代码片段中没有被使用。
• 最后，变量C在C = A * H中被定义并使用最新的定义（即A = F中的A）。

因此，对于变量A，我们有两个use-def链：

• 第一个定义A = B + C和第一个使用D = A + E形成一个use-def链。
• 第二个定义A = F和使用C = A * H形成另一个use-def链。

use-def链在编译器中用于多种目的，包括但不限于：

• 死代码消除：如果一个变量在某个点被定义后没有被使用，那么这个定义之前的任何代码都是死代码，可以被优化掉。
• 常量传播：如果一个变量的定义是一个常量，那么在所有使用该变量的地方都可以用这个常量来替换。
• 循环优化：通过分析循环中的use-def链，编译器可以确定哪些变量在循环中只被赋值一次，从而进行适当的优化。

在PFC（Program to Convert Fortran to Parallel Form）这样的向量化程序转换系统中，use-def链有助于识别可以并行执行的循环迭代，以及在转换过程中保持程序的正确性。

然而，按照 Kuck 的说法，依赖这个词用来表示语句 S2 使用 S1 可能创建的值之间的关系。如果 S2 依赖于 S1，那么存在一系列语句 X1 ... Xn，使得 X0=S1，Xn=S2 且对于所有 i（0 ≤ i ≤ n），X(i+1) 直接依赖于 X(i)。根据这些术语，一个语句只有在它不依赖于自身的情况下才能被向量化。