收敛操作语义¶

概述 ¶

一些并行执行环境以组的形式执行线程，这些组允许使用称为收敛操作的特殊原语在组内进行高效通信。收敛操作的结果对执行它的线程集（即，收敛地）敏感。当控制流发散时，即同一组的线程遵循CFG中的不同路径，该组并非所有线程都可能参与此通信。这是将收敛操作与其他线程间通信区分开来的决定性特征。

收敛操作涉及线程间通信或同步，这些通信或同步发生在内存模型之外，其中参与通信的线程集受控制流隐式影响。

例如，在以下 GPU 计算内核中，预期收敛操作期间的通信将精确发生在实现定义的执行范围（例如工作组或子组）中，对于这些范围，condition 为真。

void example_kernel() {
    ...
    if (condition)
        convergent_operation();
    ...
}

在结构化编程语言中，通常有一种直观且明确的方法来确定预期通信的线程。但是，即使在结构化编程语言中，情况也不总是如此，并且在非结构化控制流中，这种直觉完全失效。本文档描述了 LLVM 中的形式语义，即如何确定收敛操作的通信线程集。

本文档中的定义将许多细节留空，例如首先如何形成线程组。它侧重于与确定通用程序转换的正确性和与收敛相关的分析（例如一致性分析）相关的疑问。

收敛操作 ¶

在 LLVM IR 中，如上所述，在线程之间进行通信的唯一方法是调用目标定义的收敛内联函数。因此，只有 LLVM IR 中的调用点（call、invoke 或 callbr 指令）会导致收敛操作。

如果 LLVM IR 中的函数具有 convergent 属性，则称该函数为收敛函数。

如果 LLVM IR 中的调用点是对收敛函数的直接调用，或者具有 convergent 属性或 convergencectrl 操作数捆绑，则称该调用点为收敛调用点。

信息性说明

如果该函数或从其传递调用的任何函数包含收敛调用点，则可能必须将该函数视为收敛函数。生成 convergent 属性的前端在发出函数和函数调用时应考虑到这一点。但情况并非总是如此。

非收敛函数可能包含收敛操作；此类操作不直接依赖于作为单个通信组进入函数的线程集。相反，这些操作依赖于函数体中实现定义的线程子集，如机会主义收敛操作中所示。

收敛操作示例 ¶

（本节为信息性。）

像素着色器中的纹理采样 ¶

以下风格化的像素着色器使用内置函数 textureSample 在给定坐标集处对纹理进行采样。纹理采样需要坐标的屏幕空间导数来确定样本的详细程度（mipmap 级别）。它们通常通过获取相邻像素之间的差异来近似，这些像素由同一组中的不同线程计算。

void example_shader() {
  ...
  color = textureSample(texture, coordinates);
  if (condition) {
    use(color);
  }
  ...
}

从纯粹的单线程角度来看，将 textureSample 沉入 if 语句似乎是合法的。但是，如果对于某些相邻像素条件为假，则它们对应的线程将不会一起在组中执行，这使得不可能将坐标的差异作为屏幕空间导数的近似值。在实践中，结果将是未定义的值。

也就是说，textureSample 操作符合我们对收敛操作的定义。

它与隐式依赖于控制流的线程集通信。

正确性取决于此线程集。

编译器前端可以发出表示收敛约束的 IR，如下所示。

define void @example_shader() convergent {
  %entry = call token @llvm.experimental.convergence.entry()
  ...
  %color = call T @textureSample(U %texture, V %coordinates) [ "convergencectrl"(token %entry) ]
  br i1 %condition, label %then, label %end

then:
  call void @use(T %color)
  br label %end

end:
  ret void
}

llvm.experimental.convergence.entry 内联函数本身是 convergent，我们期望它至少在同一“四边形”（一组 2x2 像素，为了近似屏幕空间导数而一起评估）的所有线程之间进行通信。这一事实不是通用 LLVM IR 语义的一部分；它必须在其他地方定义，例如作为目标特定 ABI 定义的一部分和/或参考一些相关的 API 规范。

由于 @textureSample 调用然后在其 convergencectrl 捆绑中使用 entry 内联函数生成的令牌，并且没有其他控制依赖项，因此它必须在同一组线程之间进行通信。这向通用程序转换指示禁止下沉 @textureSample 调用。（如果程序转换可以以某种方式证明，例如通过依靠可以分析具有更多知识的程序的目标特定回调，则程序转换仍然可以下沉调用，即 %condition 在由收敛令牌 %entry 引用的线程中始终保持一致。）

发散控制流内的归约 ¶

以下示例显示，在面对收敛操作时，合并分支的公共代码可能是错误的。

void example_kernel() {
  delta = ...
  if (delta > 0) {
    total_gains = subgroupAdd(delta);
    ...
  } else {
    total_losses = subgroupAdd(delta);
    ...
  }
}

计算 total_gains 的 subgroupAdd 将由子组（波）中 delta 为正的线程子集执行，因此将所有这些线程的 delta 值加起来；类似地，计算 total_losses 的 subgroupAdd 也是如此。

如果我们将 subgroupAdd 提升并合并到 if 语句之上，它将对所有线程的 delta 求和。

编译器前端可以发出表示收敛约束的 IR，如下所示。

define void @example_kernel() convergent {
  %entry = call token @llvm.experimental.convergence.entry()
  %delta = ...
  %cc = icmp sgt i32 %delta, 0
  br i1 %cc, label %then, label %else

then:
  %total_gains = call i32 @subgroupAdd(i32 %delta) [ "convergencectrl"(token %entry) ]
  ...
  br label %end

else:
  %total_losses = call i32 @subgroupAdd(i32 %delta) [ "convergencectrl"(token %entry) ]
  ...
  br label %end

end:
  ...
}

entry 内联函数的行为与前面的示例相同：假设 @example_kernel 是一个 OpenCL 内核（如“子组”术语所暗示的那样），我们期望它在“子组”内的所有线程之间进行通信。这通常映射到 GPU 硬件上的 SIMD 向量。

对 @subgroupAdd 的调用使用 entry 内联函数生成的令牌，但它们也有一个额外的控制依赖项。根据本文档中定义的规则，它们仅在实际最终执行相应（静态）调用点的线程子集之间进行通信。

提升它们将删除控制依赖项并导致它们在 entry 内联函数通信的完整线程集中进行通信。同样，如果可以证明 %cc 在相关线程集中始终保持一致，则允许提升：在这种情况下，@subgroupAdd 已经在原始程序中的完整线程集中进行通信。

收敛控制的激励示例 ¶

（本节为信息性。）

非结构化控制流 ¶

考虑一个跳转线程如何以在没有本文档中描述的收敛内联函数的情况下使语义变得不明确的方式移除结构的示例。

void example_original() {
entry:
    ...
    br i1 %cond1, label %then1, label %mid

then1:
    ...
    %cond2 = ...
    br label %mid

mid:
    %flag = phi i1 [ true, %entry ], [ %cond2, %then1 ]
    br i1 %flag, label %then2, label %end

then2:
    ...
    call void @subgroupControlBarrier()
    ...
    br label %end

end:
}

void example_jumpthreaded() {
entry:
    ...
    br i1 %cond1, label %then1, label %then2

then1:
    ...
    %cond2 = ...
    br i1 %cond2, label %then2, label %end

then2:
    ...
    call void @subgroupControlBarrier()
    ...
    br label %end

end:
}

控制屏障是否保证在两种情况下都在同一组线程之间同步？文献中的不同实现可能会对这个问题给出不同的答案。

在后支配节点处重新收敛的实现中，线程在第一个版本中的 mid 处重新收敛，以便执行控制屏障的所有线程（在一个子组/波中）都一起执行。在第二个版本中，通过不同路径到达控制屏障的线程分别同步：第一个（也是唯一一个）后支配节点是 end，因此线程在此之前不会重新收敛。
以拓扑方式对基本块进行排序并确保每个基本块的最大重新收敛的实现将在两个版本中表现相同。

我们通常认为无环控制流中的重新收敛必须是最大的。编译器前端可以如下增强原始代码。

define void @example_original() convergent {
entry:
  %entry = call token @llvm.experimental.convergence.entry()
  ...
  br i1 %cond1, label %then1, label %mid

then1:
  ...
  %cond2 = ...
  br label %mid

mid:
  %flag = phi i1 [ true, %entry ], [ %cond2, %then1 ]
  br i1 %flag, label %then2, label %end

then2:
  ...
  call void @subgroupControlBarrier() [ "convergencectrl"(token %entry) ]
  ...
  br label %end

end:
}

如果 S 是入口内联函数与之通信的线程集，则 @subgroupControlBarrier 调用将与实际到达调用点的 S 的子集进行通信。这组线程在跳转线程后不会发生变化，因此上述问题的答案保持不变。

机会性收敛操作 ¶

一些程序具有包含一系列收敛操作的局部代码区域，其中代码并不关心其执行的线程的确切集合，而只关心所有操作在序列中线程集相同。（如果序列中收敛操作的子集具有其他非统一的控制依赖关系，则这是不可能的。但是，代码可能仍然需要线程集在逻辑上与这些控制依赖关系的条件一致。）在这种情况下，llvm.experimental.convergence.anchor 可用于表达所需的语义。

以下示例函数可以是假设的“追加缓冲区”实现的一部分，其中线程有条件地将固定大小的记录连续写入全局缓冲区。函数 @reserveSpaceInBuffer 返回调用线程应在其处存储数据的缓冲区索引。

这可以通过在每个线程中使用简单的原子操作来递增分配计数器来实现。

但是，以下实现可能在某些硬件上性能更高，因为它仅对整个线程组使用单个原子操作。为此，它首先确定组的总大小，这将成为原子操作的操作数，然后将原子操作的结果广播到组的所有线程，以便每个线程可以计算其在缓冲区中的个体位置。

define i32 @reserveSpaceInBuffer() {    ; NOTE: _not_ a convergent function!
entry:
  %anchor = call token @llvm.experimental.convergence.anchor()

  %ballot = call i64 @subgroupBallot(i1 true) [ "convergencectrl"(token %anchor) ]
  %numThreads.p = call i64 @llvm.ctpop.i64(i64 %ballot)
  %numThreads = trunc i64 %numThreads.p to i32

  %absoluteThreadIdx = call i32 @getSubgroupLocalInvocationId()
  %absoluteThreadIdx.ext = zext i32 %absoluteThreadIdx to i64
  %mask.p = shl i64 1, %absoluteThreadIdx.ext
  %mask = sub i64 %mask.p, 1

  %maskedBallot = and i64 %ballot, %mask
  %relativeThreadIdx.p = call i64 @llvm.ctpop.i64(i64 %maskedBallot)
  %relativeThreadIdx = trunc i64 %relativeThreadIdx.p to i32

  %isFirstThread = icmp eq i32 %relativeThreadIdx, 0
  br i1 %isFirstThread, label %then, label %end

then:
  %baseOffset.1 = atomicrmw add ptr @bufferAllocationCount, i32 %numThreads monotonic
  br label %end

end:
  %baseOffset.2 = phi i32 [ undef, %entry ], [ %baseOffset.1, %then ]
  %baseOffset = call i32 @subgroupBroadcastFirst(i32 %baseOffset.2) [ "convergencectrl"(token %anchor) ]
  %offset = add i32 %baseOffset, %relativeThreadIdx
  ret i32 %offset
}

这里的关键是函数实际上并不关心它被调用时的线程集。它获取任何可用的线程集。函数的实现所关心的只是初始的 @subgroupBallot（用于检索一起执行锚点的线程的位掩码）与最终的 @subgroupBroadcastFirst使用相同的线程集执行。就收敛而言，正确性不需要其他任何东西。

函数 @reserveSpaceInBuffer 本身 _不是_ convergent：调用者可以随意移动函数的调用点。这可以通过更改为原子操作分组的线程集来改变实际的行为。这在程序的输出中是可见的，因为输出在缓冲区中出现的顺序发生了变化。但是，这并没有破坏 @reserveSpaceInBuffer 与其调用者之间的整体契约——这是有道理的：由于涉及原子操作，输出的顺序无论如何都是不确定的。

如果内联了函数，则锚内联函数的使用也表明，通常由收敛操作的存在禁止的某些转换实际上是被允许的，只要它们不破坏由锚控制的代码区域。

扩展循环：循环中的不同出口 ¶

高级语言通常提供 break 语句，用于将控制权转移出循环语句。在大多数情况下，循环是结构化的，因此循环内部的收敛性没有歧义。但是，当 break 受循环内部的不同条件的控制依赖时，就会出现歧义。考虑以下示例

void example() {
  // A
  ...
  for (...) {
    // B
    if (condition) { // divergent condition
      // C
      convergent_op();
      break;
    }
    // D
    ...
  }
  // E
}

在此程序中，对 convergent_op() 的调用在词法上“位于” for 循环内。但是，当转换为 LLVM IR 时，基本块 B 是以不同分支结束的退出块，基本块 C 是循环的出口。因此，对 convergent_op() 的调用位于循环之外。这导致程序员的期望与编译后的程序之间存在不匹配。该调用应在循环的每次迭代中由一起执行分支以退出循环的线程收敛执行。但是，在编译时，所有在不同迭代中执行不同退出的线程首先在基本块 C 的开头收敛，然后一起执行对 convergent_op() 的调用。

在这种情况下，llvm.experimental.convergence.loop 可用于表达所需的语义。对该内联函数的调用放置在循环头中，它跟踪循环的每次迭代。由此产生的令牌用作收敛调用的 convergencectrl 操作数。 loop 内联函数的语义确保收敛调用仅由在给定迭代中收敛退出循环的线程收敛执行。

define void @example() convergent {
  %entry = call token @llvm.experimental.convergence.entry()
  br label %for

for:
  %inner = call token @llvm.experimental.convergence.loop() ["convergencectrl"(token %entry)]
  %for.cond = i1 ...
  br i1 %for.cond, label %B, label %E

B:
  ...
  %condition = i1 ...
  br i1 %condition, label %C, label %D

C:
  call void @convergent_op() ["convergencectrl"(token %inner)]
  br label %E

D:
  ...
  br label %for

E:
  ...
  ret void
}

同一程序的 LLVM IR 版本显示了一个由基本块 %for、%B 和 %D 组成的循环，而 %C 是在退出块 %B 末尾的不同分支到达的出口。但是，使用收敛控制令牌清楚地表明，块 %C 必须仅由那些收敛地从 %B 到 %C 执行退出边的线程收敛执行。换句话说，%C 的收敛执行受循环内对 llvm.experimental.convergence.loop 内联函数的调用的控制。该循环有效地扩展到包括位于循环之外的所有使用此令牌的指令。

动态实例和收敛令牌 ¶

LLVM IR 指令的每次执行都发生在指令的动态实例中。动态实例是我们用来讨论收敛操作中通信线程的形式对象。LLVM 程序中所有操作（无论是收敛的还是非收敛的）都定义了动态实例。收敛控制主要与收敛操作的动态实例有关，因为它们通过线程间通信影响程序的执行。非收敛操作的动态实例与确定值的一致性相关。

由不同线程执行同一收敛操作产生的动态实例可能是收敛的。在执行收敛操作时，执行收敛动态实例的线程集是相互通信的线程集。收敛令牌捕获此收敛，如下所述。

收敛令牌是 token 类型的值，即它们不能用于 phi 或 select 指令中。收敛令牌值表示产生它的指令的动态实例。

收敛操作可以有一个可选的 convergencectrl 操作数捆绑包，其中包含一个收敛令牌操作数，以定义相对于定义令牌的操作的通信线程集。

令 U 为除收敛控制内联函数调用之外的收敛操作，D 为定义用作 U 的 convergencectrl 操作数的令牌值的收敛操作。当且仅当两个线程中的令牌值由 D 的收敛动态实例返回时，这两个线程执行 U 的收敛动态实例。

注意

文本将收敛令牌值定义为表示动态实例。但是，如果我们假设收敛的动态实例产生相同的令牌值，那么我们几乎可以将令牌值视为表示线程集——具体来说，是执行定义指令 D 的收敛动态实例的线程集 S。

在此直观的图景中，当收敛令牌值 T 用于指令 I 上的 convergencectrl 捆绑包时，则在 I 中通信的线程集是令牌值表示的线程集 S 的一个子集。具体来说，它是最终执行 I 同时使用令牌值的线程子集。

这本身并不能作为定义：如果同一线程多次执行 I 呢？线程 1 中 I 的哪个执行与线程 2 中 I 的哪个执行通信？只要 D 和 I 处于相同的循环（或周期）嵌套级别，依赖于动态实例的概念就可以对这个问题给出可靠的答案。

D 和 I 处于不同循环嵌套级别的情况被静态规则禁止——处理这种情况是 llvm.experimental.convergence.loop 的目的。

收敛控制内联函数 ¶

本节描述可用于生成收敛令牌的目标独立内联函数。

如果间接调用收敛控制内联函数，则行为未定义。

`llvm.experimental.convergence.entry`¶

token @llvm.experimental.convergence.entry() convergent readnone

此内联函数用于将函数内部的动态实例与调用方中的动态实例关联起来。

如果函数从 LLVM 范围之外调用，则此内联函数的动态实例的收敛性由环境定义。例如
1. 在 OpenCL 的 *内核启动* 中，可以在内存模型之外进行通信的最大线程集是一个 *工作组*。因此，一个合适的选项是指定 OpenCL 中来自单个工作组的所有线程执行此内联函数的收敛动态实例。
2. 在 C/C++ 程序中，线程独立启动，它们只能通过内存模型进行通信。因此，C/C++ 程序中此内联函数的动态实例永远不会收敛。
如果函数是从 LLVM IR 中的调用点调用的，则当且仅当两个线程都通过执行调用点的收敛动态实例进入函数时，这两个线程才会执行此内联函数的收敛动态实例。

此内联函数在一个函数中最多只能出现一次，并且只能出现在函数的入口块中。如果此内联函数出现在基本块中，则它必须位于同一基本块中任何其他收敛操作之前。

如果此内联函数出现在非收敛函数中，则为错误。

在对此内联函数的调用中指定 convergencectrl 操作数捆绑是错误的。

函数内联将此内联函数替换为操作数捆绑中的令牌。例如

// Before inlining:

void callee() convergent {
  %tok = call token @llvm.experimental.convergence.entry()
  convergent_operation(...) [ "convergencectrl"(token %tok) ]
}

void main() {
  %outer = call token @llvm.experimental.convergence.anchor()
  for (...) {
    %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
    callee() [ "convergencectrl"(token %inner) ]
  }
}

// After inlining:

void main() {
  %outer = call token @llvm.experimental.convergence.anchor()
  for (...) {
    %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
    convergent_operation(...) [ "convergencectrl"(token %inner) ]
  }
}

`llvm.experimental.convergence.loop`¶

token @llvm.experimental.convergence.loop() [ "convergencectrl"(token) ] convergent readnone

此内联函数表示在控制流循环内部确定收敛时虚构计数器递增的位置。

令 U 为对此内联函数的调用，D 为定义用作 U 的 convergencectrl 操作数的令牌值的收敛操作。当且仅当以下条件满足时，两个线程执行 U 的收敛动态实例：

两个线程中的令牌值都由 D 的收敛动态实例返回，并且，
存在一个整数 *n*，使得两个线程都使用该令牌值第 *n* 次执行 U。

在对此内联函数的调用中省略 convergencectrl 操作数捆绑是错误的。

如果此内联函数出现在基本块中，则它必须位于同一基本块中任何其他收敛操作之前。

循环的核心

如果循环 C 包含此内联函数的出现 H，其令牌操作数在 C 之外定义，则 H 被称为 C 的核心。

注意

循环的静态规则意味着核心只能出现在自然循环的头部。这确保了核心紧密地体现了循环迭代的直观概念。如果放宽此限制，则所得语义即使对于不可约循环也提供了“循环迭代”的新概念。但这允许自然循环在除其头部之外的节点中具有核心，这对循环迭代在收敛方面的含义产生了有趣的影响。目前，我们不允许这种情况，因为它的实际应用非常罕见。

`llvm.experimental.convergence.anchor`¶

token @llvm.experimental.convergence.anchor() convergent readnone

此内联函数生成一个初始收敛令牌，该令牌独立于任何“外部范围”。执行此内联函数的收敛动态实例的线程集由实现定义。

在对此内联函数的调用中传递 convergencectrl 操作数捆绑是错误的。

注意

预期是，“恰好同时处于活动状态”的组中的所有线程将执行收敛动态实例，以便程序可以检测可以在程序的某个局部区域内高效通信的最大线程集。

不受控制的收敛操作 ¶

具有显式 convergencectrl 操作数捆绑的收敛操作称为 *受控收敛操作*。所有其他收敛操作都被称为 *不受控制* 的。

不受控制的收敛操作被认为具有由 convergent 属性单独确定的 *隐式收敛控制*。LLVM 中实现的 convergent 属性的语义与已记录的语义不同。该实现尝试遵循关于收敛操作的常见直觉，该直觉仍然未完全指定。因此，无法将隐式收敛控制完全转换为显式收敛控制令牌，并且这两种模式不能在同一函数中混合使用。

如果一个函数包含受控收敛操作，则该函数中的所有收敛操作必须要么是受控操作，要么是对收敛控制内联函数的调用。

推断令牌 ¶

（本节仅供参考）

有时，可能需要根据显式收敛控制令牌重新解释隐式收敛控制。例如，当内联函数调用时，可能会发生这种情况，并且调用方或被调用方包含不受控制的收敛操作。

不受控制的收敛操作的一些用法可能需要满足以下属性：

对于环境定义的线程组（例如 OpenCL 工作组或子组），如果组中的一个线程执行收敛操作，则该组中的所有线程都与该线程一起收敛地执行该操作。

就显式收敛控制而言，这意味着每个收敛操作 X 上的 convergencectrl 操作数最终必须源自对 llvm.experimental.convergence.entry 内联函数的调用。这保留了在达到 X 时收敛的线程组与最初以收敛方式开始执行程序的线程组相同的可能性。相比之下，llvm.experimental.convergence.anchor 内联函数捕获了一个由实现定义的线程组，这不足以支持上述属性。

根据显式收敛控制令牌近似隐式收敛控制的一种方法是以下过程，该过程保留了上述属性：

将每个不可约循环转换为可约循环。
在函数入口块的开头插入对 llvm.experimental.convergence.entry 的调用。
在每个循环头的开头插入对 llvm.experimental.convergence.loop 的调用。如果此循环是最外层循环，则 convergencectrl 操作数是对函数入口块中的 llvm.experimental.convergence.entry 的调用。否则，convergencectrl 操作数是对父循环头部中的 llvm.experimental.convergence.loop 的调用。
对于每个不受控制的收敛操作 X，添加一个 convergencectrl 操作数捆绑，使用由定义 D 定义的令牌，该定义是此操作的同级。 D 始终支配 X — 如果 X 不在任何循环中，则 D 是对 llvm.experimental.convergence.entry 的调用；否则 D 是 X 的父循环的核心。

静态规则 ¶

LLVM IR 中的 *格式良好的* 程序必须满足关于循环和收敛区域的以下静态规则。

闭合路径 ¶

CFG 中的闭合路径是 CFG 中节点和边的连接序列，其起点和终点相同。

CFG 中每个包含除 llvm.experimental.convergence.loop 使用之外的收敛令牌 T 使用的闭合路径也必须包含 T 的定义。
CFG 中每个包含收敛令牌 T 的两个不同使用的闭合路径也必须包含 T 的定义。
CFG 中每个包含两个不同的收敛令牌 T1 和 T2 的使用的闭合路径也必须包含其中至少一个的定义。

总而言之，这些规则意味着对于每个闭合路径 C，最多只能有一个收敛令牌 T 在 C 中使用但在其外部定义，并且 T 只能在 C 中使用一次，并且只能由 llvm.experimental.convergence.loop 使用。

在每个包含令牌 T 的使用 U 但不包含 T 的定义的闭合路径中，U 必须支配闭合路径中的所有节点。

这意味着 llvm.experimental.convergence.loop 只能作为自然循环的头部出现。

充分条件：根据循环的特性，只需证明上述属性对循环成立，而非闭合路径。简而言之，任何违反上述一个或多个静态规则的闭合路径都包含一个也违反相同规则的循环。

收敛区域 ¶

收敛令牌 T 的收敛区域是指 T 存活且被使用的最小区域，即，由 T 的定义 D 支配且可以到达 T 的使用的程序点集。

以下关于收敛区域的静态规则必须由有效的程序满足。

如果令牌 T1 的收敛区域 R 包含收敛令牌 T2 的使用，则 R 必须也包含 T2 的定义。（换句话说，收敛区域必须合理地嵌套。）

注意

为简洁起见，本文档使用“令牌定义 D 的收敛区域”一词来实际指代由 D 定义的令牌 T 的收敛区域。

推断非收敛 ¶

当目标或环境保证线程不使用收敛操作进行通信，或者线程永远不会发散时，程序中的动态实例是无关紧要的，优化器可以删除调用点或函数上 convergent 属性的任何出现，以及调用点上的任何显式 convergencectrl 操作数捆绑。

如果优化器可以证明此调用点的执行始终导致对非收敛函数的调用，则它可以从调用点删除 convergent 属性和任何显式 convergencectrl 操作数捆绑。

如果优化器可以证明函数不包含对 llvm.experimental.convergence.entry 的调用，或者任何不受控制的收敛操作，则它可以删除函数上的 convergent 属性。

内存模型非交互 ¶

操作是否收敛这一事实不会影响其在内存模型目的中的处理方式。特别是，一个 convergent 且 readnone 的操作不会引入额外的排序约束，就内存模型而言。既没有隐含的屏障，也没有在内存屏障意义上或在同步线程执行的控制屏障意义上的隐含屏障。

信息说明：执行收敛动态实例的线程不一定同时执行。

其他交互 ¶

一个函数可以同时是 convergent 和 speculatable，表示该函数没有未定义的行为并且除了计算结果之外没有其他影响，但仍然受执行该函数的线程集的影响。这通常会阻止对函数调用的推测，除非 convergent 强加的约束以其他方式进一步放松。

受控最大收敛 ¶

每个受控收敛操作的动态实例上的已收敛关系完全由收敛令牌的语义定义。但是，对 llvm.experimental.convergence.anchor 的调用的实现定义的收敛也取决于如果它发生在不可约循环内所选择的循环层次结构。

当收敛操作 D 定义的令牌在另一个收敛操作 U 中使用时，实现必须确保在 U 处收敛的线程是所有在 D 处收敛后到达 U 的线程。在大多数实现中，可以合理地假设只有这些线程在从 D 到 U 的任何路径上的每个节点处都收敛。换句话说，在 D 处的已收敛关系生成线程组，这些线程组只能在每个组内收敛，而在 D 的收敛区域内。

所有这些都会影响动态实例上的最大已收敛关系，进而影响 D 的收敛区域中静态实例的m-收敛属性。

受控最大已收敛关系

根据收敛控制令牌的语义，收敛操作的动态实例在受控最大已收敛关系中相关联。

不同线程为同一非收敛操作 X 生成的动态实例 X1 和 X2 在受控最大已收敛关系中相关联，当且仅当

这两个线程都执行了每个令牌定义 D 的收敛动态实例，使得 X 位于 D 的收敛区域内，并且，

要么 X 不包含在任何循环中，要么对于包含 X 的每个具有头 H 的循环 C

在各自线程中先于 X1 的 H 的每个动态实例 H1 都是收敛于 X2 之前，并且，

在各自线程中先于 X2 的 H 的每个动态实例 H2 都是收敛于 X1 之前，

不假设 X1 与 X2 收敛。

受控 m-收敛静态实例

当且仅当以下条件满足时，给定 CFG 中的节点 X 被报告为 m-收敛：

对于任何令牌定义 D，使得 X 位于 D 的收敛区域内，D 本身是 m-收敛的，并且，

包含 X 的每个循环都满足以下必要条件

循环内的每个发散分支都满足发散入口准则，并且，

从外部发散分支没有到达循环的发散路径。

循环出口处的时序发散 ¶

当循环具有发散出口时，最大收敛假设所有线程在出口块处收敛。但是，如果循环外部的受控收敛操作使用循环内部的操作 D 定义的令牌，则 D 的收敛区域现在扩展到循环外部。如果两个线程在退出循环之前执行了 D 的收敛动态实例，则它们将继续执行 D 的收敛区域中节点的收敛动态实例。因此，对于在循环内部定义的值 V，T 的收敛区域内的 V 的任何使用 U 都使用 V 的收敛动态实例的输出。如果 V 是统一的，则其在这样的 U 处的使用也是统一的。换句话说，时序发散仅适用于 D 的收敛区域之外的 V 的使用。

关于循环的静态规则的理由 ¶

（本节为信息性。）

注意

为方便起见，我们使用运算符 == 来表示关系 converged-with，并使用运算符 != 来表示其否定。

考虑一个具有（错误的！）收敛控制的循环，如下面的伪代码所示。

; WARNING: Example of incorrect convergence control!

%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  ...
  call void @convergent.op() [ "convergencectrl"(token %anchor) ]
  ...
}

关于循环的第一个静态规则禁止此代码。

我们必须这样做第一个正式论点是，决定两个线程是否执行 @convergent.op 的收敛动态实例的动态规则会导致此代码中的逻辑矛盾。假设两个线程执行锚点的收敛动态实例，然后执行循环的两次迭代。线程 1 执行 @convergent.op 的动态实例 I1 和 I2，线程 2 执行动态实例 J1 和 J2。使用所有规则，我们可以推导出

I1 != I2 和 J1 != J2 由动态实例的基本规则得出。
根据关于受控收敛操作的第一个动态规则，I1 == J1：两个线程执行相同的静态指令，同时使用由指令的收敛动态实例（锚点）生成的收敛令牌值。
根据相同的论点，I1 == J2。同样，I2 == J1 和 I2 == J2。

人们可能会直观地倾向于认为I1 和 J2是在不同的循环迭代中执行的，但这对于正式的论证来说完全无关紧要。LLVM IR 语义中没有任何机制可以形成不同线程中循环迭代之间的关联，除非是本文档中定义的规则——并且本文档中的规则需要循环核心内在函数来讨论循环迭代。
根据传递性，我们有I1 == I2 和 J1 == J2。这是一个矛盾。

通过插入如下所示的循环核心内在函数，可以解决此问题，它建立了跨线程的循环迭代之间的关系。

%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  %loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
  ...
  call void @convergent.op() [ "convergencectrl"(token %loop) ]
  ...
}

在两个线程执行锚点的收敛动态实例，然后执行循环的两次迭代的相同场景中，关于循环核心内在函数的动态规则意味着两个线程分别在其各自的第一次迭代中执行循环核心内在函数的收敛动态实例，然后再次在其各自的第二次迭代中执行。

然后，这意味着它们在第一次迭代中执行@convergent.op 的收敛动态实例I1 == J1，然后在第二次迭代中执行I2 == J2。该规则是“当且仅当”规则，因此它也意味着I1 != J2 和 I2 != J1，因为这些执行看到的%loop令牌值源自循环内在函数的非收敛动态实例。

有人可能会问，我们是否可以更改动态规则而不是添加关于循环的静态规则。由于更深层次的困难，这是不切实际的。考虑以下循环，它再次使用了错误的收敛控制

; WARNING: Example of incorrect convergence control!

; (A)
%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  ; (B)
  if (condition1) {
    ; (C)
    call void @convergent.op.1() [ "convergencectrl"(token %anchor) ]
  }
  ; (D)
  if (condition2) {
    ; (E)
    call void @convergent.op.2() [ "convergencectrl"(token %anchor) ]
  }
  ; (F)
}
; (G)

假设两个线程执行锚点的收敛动态实例，然后执行以下基本块序列

Thread 1: A B C D F B D E F G
Thread 2: A B D E F B C D F G

也就是说，两个线程都执行循环的两次迭代，但它们在不同的迭代中执行不同的收敛操作。如果没有形成跨线程的循环迭代之间的关系，那么就没有合理的方法来定义收敛操作的哪些动态实例应该在跨线程之间相同（如果有的话）。

同样，这可以通过添加循环核心内在函数来解决，最自然的方式是

; (A)
%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  ; (B)
  %loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
  if (condition1) {
    ; (C)
    call void @convergent.op.1() [ "convergencectrl"(token %loop) ]
  }
  ; (D)
  if (condition2) {
    ; (E)
    call void @convergent.op.2() [ "convergencectrl"(token %loop) ]
  }
  ; (F)
}
; (G)

令%loop(i;j) 为线程i 执行循环核心内在函数的第j 次执行的动态实例，类似地，@op.k(i) 和 @op.k(i) 为线程i 执行@convergent.op.k 的动态实例。然后我们有

%loop(1;j) == %loop(2;j)，对于j = 1, 2，因为关于循环核心内在函数的动态规则。
%loop(i;1) != %loop(i;2)，对于i = 1, 2，因为基本规则是同一个线程的不同执行发生在不同的动态实例中。
@op.1(1) != @op.1(2)，因为@op.1(1) 使用引用%loop(1;1) 的%loop 令牌值，而@op.1(2) 使用引用%loop(2;2) == %loop(1;2) 的令牌值，这与%loop(1;1) 不同。
类似地，@op.2(1) != @op.2(2)。

但是，可以以不同的方式插入循环核心内在函数，代价是还需要插入一个独立的锚点

; (A)
%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  ; (B)
  if (condition1) {
    ; (C)
    %loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
    call void @convergent.op.1() [ "convergencectrl"(token %loop) ]
  }
  ; (D)
  if (condition2) {
    ; (E)
    %free = call token @llvm.experimental.convergence.anchor()
    call void @convergent.op.2() [ "convergencectrl"(token %free) ]
  }
  ; (F)
}
; (G)

这导致了在其他地方也提到的“循环迭代的非自然计数”。令%loop(i) 为线程i 执行循环核心内在函数的动态实例（每个线程只执行一次），令@op.k(i) 与之前相同。然后

%loop(1) == %loop(2)，因为关于循环核心内在函数的动态规则。
@op.1(1) == @op.1(2)，因为@op.1(i) 使用引用%loop(i) 的%loop 的值，并且%loop(1) == %loop(2)。
@op.2(1) == @op.2(2) 是否已定义由对%free 锚点内在函数的使用决定。

在实践中，它们几乎肯定必须是非收敛动态实例。考虑一下，如果实现严格遵循程序中给出的指令顺序，则线程的执行可以“对齐”如下
```
Thread 1: A B         C D F B D E F G
Thread 2: A B D E F B C D F         G
```
因此，@op.2(1) 在物理上比@op.2(2) 稍后执行，并且线程之间无法进行通信，这意味着它们执行非收敛动态实例。

也就是说，可以想象实际上没有任何数据或其他依赖项会强制执行此执行顺序。在这种情况下，高度乱序的实现可能会允许通信。这就是为什么本文档中定义的规则对@op.2(1) == @op.2(2) 是否成立保持沉默。

这种类型的收敛控制在实际程序中出现的可能性相对较小。它的可能性仅仅是模型的逻辑结果。

如果收敛操作被嵌套循环替换，并且嵌套循环的循环核心内在函数直接引用%anchor，则会出现类似的问题，因此适用于它们的关于循环的静态规则的变体

; WARNING: Example of incorrect convergence control!

%anchor = call token @llvm.experimental.convergence.anchor()
for (;;) {
  if (condition1) {
    for (;;) {
      %loop1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
    }
  }
  if (condition2) {
    for (;;) {
      %loop2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
    }
  }
}

存在一个循环（CFG 中的闭合遍历），它通过使用%anchor 的两个循环核心内在函数，但不通过%anchor 的定义，因此此代码无效。

程序转换正确性的示例 ¶

（本节为信息性。）

如前几节中的规则所暗示的那样，如果程序转换保留或细化了收敛操作的语义，则它们相对于收敛操作是正确的。这意味着转换后的程序中通信线程的集合必须在原始程序中是可能的。

如果仅关注单线程的程序转换不会将收敛操作下沉或提升到分支的另一侧，则通常是保守正确的。这即使对于更改控制流图的程序转换也适用。

例如，展开不包含收敛操作的循环不会破坏循环外部收敛操作所需的任何保证。

循环展开示例 ¶

我们在这里考虑三种循环展开

部分展开，没有已知的循环次数倍数，因此需要一个“尾部”来收集剩余的元素。
按循环次数倍数进行部分展开，因此不需要“尾部”。
完全展开，它消除了循环。

当使用@llvm.experimental.convergence.loop 时，第一种是禁止的。我们用一些例子来说明推理。

首先，如果所有收敛操作都引用回循环内的锚点，则可以以所有这些方式展开任意包含收敛操作的循环，即使有“尾部”也是如此。例如（在伪代码中）

while (counter > 0) {
  %tok = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
  counter--;
}

这可以展开为

while (counter >= 2) {
  %tok = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
  %tok = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
  counter -= 2;
}
while (counter > 0) {
  %tok = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
  counter--;
}

如果存在初始计数器值不是 2 的倍数的线程，则这可能会更改收敛操作的行为。特别是，所有具有奇数循环次数的线程现在都可能在其各自的最终迭代中一起执行收敛操作，因为底层实现可能会尝试将尽可能多的线程组合在一起以执行“尾部”。

此更改是允许的，因为锚点内在函数具有实现定义的收敛行为，并且循环展开转换被认为是实现的一部分。另一种推理方式是，虽然代码的可能行为发生了变化，但对其行为的保证保持不变。

如果循环包含不受控制的收敛操作，则禁止这种展开。

当必须引入“尾部”或“余数”时，展开引用循环外部生成的令牌的收敛操作的循环是被禁止的。考虑

; (A)
%outer = call token @llvm.experimental.convergence.anchor()
while (counter > 0) {
  %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
  ; (B)
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  counter--;
}
; (C)

为了理解为什么展开是被禁止的，考虑两个线程执行锚点的收敛动态实例，然后分别执行 3 次和 4 次循环迭代

Thread 1: A B B B C
Thread 2: A B B B B C

根据循环核心内在函数的动态规则，这些线程在前 3 次迭代中执行循环内在函数的收敛动态实例，然后线程 2 单独执行另一个动态实例。

根据一般收敛操作的动态规则，线程在第一次 3 次迭代中执行@convergent.operation 的收敛动态实例（即，线程 1 在迭代n 中执行的动态实例与线程 2 在迭代n 中执行的动态实例相同，对于n = 1,2,3；迭代 1 中执行的动态实例与迭代 2 中执行的动态实例不同，依此类推）。

现在假设循环按因子 2 展开，这需要如下所示的余数

; (A)
%outer = call token @llvm.experimental.convergence.anchor()
while (counter >= 2) {
  %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
  ; (B)
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  counter -= 2;
}
; (C)
if (counter > 0) {
  %remainder = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
  ; (D)
  call void @convergent.operation() [ "convergencectrl"(token %remainder) ]
}
; (E)

首先，请注意围绕循环内在函数的一些有趣问题

它没有在展开的循环中复制。这是为了符合静态规则。
目前尚不清楚循环内联是否应该在剩余部分重复，或者 D 中最终的 @convergent.operation 是否应该只引用 %inner（在 SSA 形式下是可能的）或直接引用 %outer。此处做出的决定是任意的，并且不会改变后续的论点。最终，这根本不重要，因为无论如何转换都是不正确的。

线程现在执行以下块序列

Thread 1: A B C D E
Thread 2: A B B C D E

类似于上面的论点，它们在展开循环的第一次迭代中执行 %inner 内联和 @convergent.operation 的收敛动态实例，这对应于原始循环的前 2 次迭代。

但是，它们对原始循环的第 3 次迭代执行不同的静态调用 @convergent.operation。在线程 1 中，该迭代对应于剩余部分中的调用，而在线程 2 中，它对应于展开循环中对 @convergent.operation 的第一次调用。因此，它们执行非收敛动态实例，这意味着原始循环第 3 次迭代的通信线程集不同。这就是展开不正确的原因。

另一方面，允许不带“尾部”的展开。例如，假设行程计数器已知是 2 的倍数，我们可以按如下方式展开循环

%outer = call token @llvm.experimental.convergence.anchor()
while (counter > 0) {
  %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  counter -= 2;
}

再次注意，循环内联没有重复。

llvm.experimental.convergence.loop 内联通常预期出现在自然循环的头部。但是，它也可能出现在循环的非头部块中。在这种情况下，通常无法展开循环。

提升和下沉 ¶

通常，禁止对收敛操作进行提升和下沉。这是因为将操作移动到控制流中的不同点通常会改变到达操作的线程集，因此改变执行操作的收敛动态实例的线程集。根据定义，这会改变参与收敛操作通信的线程集，这通常会改变其结果。

不过，有一些例外情况，其中大多数都需要额外的知识。

例如，通常允许跨越 *统一* 条件分支（即在每个可能的相关线程集中，所有线程都始终采用相同方向）进行提升和下沉。有关简要讨论，请参阅控制流内部约简示例的结尾。

某些收敛操作可以提升但不能下沉，反之亦然。一个简单的例子是 subgroupShuffle(data, id) 操作。它返回由 id 标识的线程的 data 操作数，其中线程 ID 是固定的，并在启动时分配给每个线程。如果线程 id 不在通信线程集中，则结果未定义（或者可能存在 UB，具体取决于语言和环境）。因此，在以下伪代码示例中允许提升

define void @example(...) convergent {
  %entry = call token @llvm.experimental.convergence.entry()
  %data = ...
  %id = ...
  if (condition) {
    %shuffled = call i32 @subgroupShuffle(i32 %data, i32 %id) [ "convergencectrl"(token %entry) ]
    ...
  } else {
    %shuffled = call i32 @subgroupShuffle(i32 %data, i32 %id) [ "convergencectrl"(token %entry) ]
    ...
  }
}

提升对 @subgroupShuffle 的调用后，通信线程集是原始程序中两个线程集的并集，因此，只有在原始程序中 %id 超出范围时，它才会在提升后超出范围。

但是，可能禁止在以下程序中对 @subgroupShuffle 进行推测性执行

define void @example(...) convergent {
  %entry = call token @llvm.experimental.convergence.entry()
  %data = ...
  %id = ...
  if (condition) {
    %shuffled = call i32 @subgroupShuffle(i32 %data, i32 %id) [ "convergencectrl"(token %entry) ]
    ...
  }
}

无法保证 %id 在 condition 为假时的线程中的值。如果 @subgroupShuffle 定义为在 %id 位于通信线程集之外时具有 UB，则推测和提升 @subgroupShuffle 可能会引入 UB。

另一方面，如果 @subgroupShuffle 定义为在 %id “超出范围”时仅生成未定义的值或 poison 作为结果，则推测是可以的。

即使 llvm.experimental.convergence.anchor 被标记为 convergent，在某些情况下也可以将其下沉。例如，在伪代码中

%tok = call token @llvm.experimental.convergence.anchor()
if (condition) {
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
}

假设 %tok 仅在条件块内使用，则可以将锚点下沉。其理由是双重的。首先，锚点具有实现定义的行为，而下沉是实现的一部分。其次，在原始程序中，与 @convergent.operation 通信的线程集会自动成为 condition 为真的线程的子集。

锚点可以在无环控制流中提升。例如

if (condition) {
  %tok1 = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok1) ]
} else {
  %tok2 = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok2) ]
}

可以提升锚点，得到

%tok = call token @llvm.experimental.convergence.anchor()
if (condition) {
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
} else {
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
}

行为保持不变，因为每个静态收敛操作仅与具有相同 condition 值的线程通信。相比之下，禁止提升收敛操作本身。

禁止将锚点提升和下沉到循环内外。例如

for (;;) {
  %tok = call token @llvm.experimental.convergence.anchor()
  call void @convergent.operation() [ "convergencectrl"(token %tok) ]
}

提升锚点将使程序根据静态有效性规则无效。反之

%outer = call token @llvm.experimental.convergence.anchor()
while (counter > 0) {
  %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
  call void @convergent.operation() [ "convergencectrl"(token %inner) ]
  counter--;
}

如果将锚点下沉到循环中，则程序将保持有效，但其行为最终可能不同。如果锚点位于循环内，则每次循环迭代都会有一个新的锚点的动态实例，并且参与这些锚点的动态实例的线程集可以在任意实现定义的方式中有所不同。通过有关收敛操作的动态实例的动态规则，这反过来意味着执行 @convergent.operation 的线程集在每次循环迭代中都可能以任意实现定义的方式有所不同。

收敛操作可以与其锚点一起下沉。同样，在伪代码中

%tok = call token @llvm.experimental.convergence.anchor()
%a = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
%b = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
if (condition) {
  use(%a, %b)
}

假设 %tok、%a 和 %b 仅在条件块内使用，则所有这些都可以一起下沉

if (condition) {
  %tok = call token @llvm.experimental.convergence.anchor()
  %a = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
  %b = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
  use(%a, %b)
}

其理由是锚点内联具有实现定义的行为，并且下沉转换被认为是实现的一部分：下沉将限制通信线程集为 condition 为真的那些线程，但这可能在原始程序中由于某些其他任意原因而发生。

但是，仅下沉生成 %b 的收敛操作将是不正确的。这将允许 condition 为假的线程在 %a 处通信，但在 %b 处不通信，而原始程序不允许这样做。

请注意，入口内联的行为不同。在下述代码片段中，禁止下沉收敛操作

%tok = call token @llvm.experimental.convergence.entry()
%a = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
%b = call T @pure.convergent.operation(...) [ "convergencectrl"(token %tok) ]
if (condition) {
  use(%a, %b)
}

文档

参与

其他链接

此页面

收敛操作语义¶

概述 ¶

收敛操作 ¶

收敛操作示例 ¶

像素着色器中的纹理采样 ¶

发散控制流内的归约 ¶

收敛控制的激励示例 ¶

非结构化控制流 ¶

机会性收敛操作 ¶

扩展循环：循环中的不同出口 ¶

动态实例和收敛令牌 ¶

收敛控制内联函数 ¶

`llvm.experimental.convergence.entry`¶

`llvm.experimental.convergence.loop`¶

`llvm.experimental.convergence.anchor`¶

不受控制的收敛操作 ¶

推断令牌 ¶

静态规则 ¶

闭合路径 ¶

收敛区域 ¶

推断非收敛 ¶

内存模型非交互 ¶

其他交互 ¶

受控最大收敛 ¶

循环出口处的时序发散 ¶

关于循环的静态规则的理由 ¶

程序转换正确性的示例 ¶

循环展开示例 ¶

提升和下沉 ¶