收敛操作语义

概述

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

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

例如，在以下 GPU 计算内核中，预期在收敛操作期间的通信会精确地发生在实现定义的执行范围（例如工作组或子组）中 condition 为 true 的那些线程之间

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

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

本文档中的定义留下了许多开放的细节，例如线程组最初是如何形成的。它侧重于与决定通用程序转换和收敛相关分析（例如一致性分析）的正确性相关的问题。

收敛操作

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

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

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

信息性注释

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

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

收敛操作的示例

（本节是信息性的。）

像素着色器中的纹理采样

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

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

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

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

  1. 它与一组线程通信，该线程集隐式地依赖于控制流。

  2. 正确性取决于这组线程。

编译器前端可以发出 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内在函数本身是收敛的，我们期望它至少在同一“四元组”的所有线程之间进行通信——一个 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 将由子组（wave）中 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 处重新收敛，以便所有执行控制屏障的线程（在子组/wave 内）一起执行。在第二个版本中，通过不同路径到达控制屏障的线程分别同步：第一个（也是唯一的）后支配器是 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 是 entry 内在函数与之通信的线程集，则 @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 本身不是 收敛的：调用者可以自由地移动函数的调用站点，只要他们认为合适。这实际上可能会改变行为，通过更改为原子操作分组在一起的线程集。这在程序的输出中是可见的，因为输出在缓冲区中出现的顺序已更改。但是，这不会破坏 @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。

在这个直观的图中，当指令 I 上的 convergencectrl 束使用收敛令牌值 T 时，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

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

  1. 如果从 LLVM 范围之外调用该函数，则此内在函数的动态实例的收敛是环境定义的。例如

    1. 在 OpenCL 内核启动中，可以在内存模型外部通信的最大线程集是工作组。因此，一个合适的选择是指定来自 OpenCL 中单个工作组的所有线程执行此内在函数的收敛动态实例。

    2. 在 C/C++ 程序中，线程是独立启动的，它们只能通过内存模型进行通信。因此，C/C++ 程序中此内在函数的动态实例永远不会收敛。

  2. 如果该函数是从 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 的收敛动态实例：

  1. 两个线程中的令牌值都是由 D 的收敛动态实例返回的，并且，

  2. 存在一个整数 n，使得两个线程都使用该令牌值第 n 次执行 U。

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

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

循环的核心

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

注意

循环的静态规则暗示核心只能出现在自然循环的头部。这确保了核心紧密地表示循环迭代的直观概念。如果放宽此限制，则生成的语义为甚至不可约循环提供了一种新的“循环迭代”概念。但这允许自然循环在其头部以外的节点中具有核心，这对于循环迭代在收敛方面的含义具有有趣的后果。目前，我们不允许这种情况，因为其实际应用非常罕见。

llvm.experimental.convergence.anchor

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

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

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

注意

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

不受控制的收敛操作

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

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

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

推断令牌

（本节是信息性的）

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

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

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

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

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

  1. 将每个不可约循环转换为可约循环。

  2. 在函数的入口块的开头插入对 llvm.experimental.convergence.entry 的调用。

  3. 在每个循环头的开头插入对 llvm.experimental.convergence.loop 的调用。 如果此循环是最外层循环，则 convergencectrl 操作数是对函数入口块中 llvm.experimental.convergence.entry 的调用。 否则，convergencectrl 操作数是对父循环头中 llvm.experimental.convergence.loop 的调用。

  4. 对于每个不受控制的收敛操作 X，使用由定义 D 定义的令牌添加一个 convergencectrl 操作数束，其中 D 是此操作的 同级。 D 始终支配 X — 如果 X 不在任何循环中，则 D 是对 llvm.experimental.convergence.entry 的调用；否则 D 是 X 的父循环的核心。

静态规则

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

闭合路径

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

  1. CFG 中每个包含收敛令牌 T 的使用的闭合路径（llvm.experimental.convergence.loop 的使用除外）也必须包含 T 的定义。

  2. CFG 中每个包含收敛令牌 T 的两个不同使用的闭合路径也必须包含 T 的定义。

  3. CFG 中每个包含两个不同收敛令牌 T1 和 T2 的使用的闭合路径也必须包含至少其中一个的定义。

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

  1. 在每个包含令牌 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-收敛属性。

受控最大已收敛关系

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

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

    1. 两个线程都执行了每个令牌定义 D 的收敛动态实例，使得 X 在 D 的收敛区域中，并且，

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

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

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

      • 无需假设 X1 与 X2 收敛。

受控 m-收敛静态实例

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

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

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

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

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

循环退出时的时序发散

当循环具有发散出口时，最大收敛假设所有线程在出口块处收敛。 但是，如果循环外的受控收敛操作使用由循环内的操作 D 定义的令牌，则 D 的收敛区域现在扩展到循环之外。 如果两个线程在退出循环之前执行了 D 的收敛动态实例，则它们继续执行 D 的收敛区域中循环外节点的收敛动态实例。 因此，对于循环内定义的值 V，在 T 的收敛区域内的任何 U 处使用 V 都使用 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。 使用所有规则，我们可以推导出

  1. I1 != I2 和 J1 != J2 由动态实例的基本规则得出。

  2. I1 == J1 根据关于受控收敛操作的第一个动态规则：当使用由指令（锚点）的收敛动态实例产生的收敛令牌值时，两个线程执行相同的静态指令。

  3. I1 == J2 根据相同的论点。 此外，I2 == J1 和 I2 == J2。

    人们可能直观地倾向于认为 I1 和 J2 在不同的循环迭代中执行，这一事实对于正式论证完全不相关。 LLVM IR 语义中没有机制用于在不同线程中的循环迭代之间形成关联，除非本文档中定义的规则 – 并且本文档中的规则需要循环核心内在函数来讨论循环迭代。

  4. 通过传递性，我们有 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 的执行的动态实例。 那么我们有

  1. 对于 j = 1, 2，%loop(1;j) == %loop(2;j)，因为关于循环核心内在函数的动态规则。

  2. 对于 i = 1, 2，%loop(i;1) != %loop(i;2)，因为相同线程的不同执行发生在不同的动态实例中这一基本规则。

  3. @op.1(1) != @op.1(2)，因为 @op.1(1) 使用 %loop 的令牌值，该令牌值引用 %loop(1;1)，而 @op.1(2) 使用引用 %loop(2;2) == %loop(1;2) 的令牌值，这与 %loop(1;1) 不同。

  4. 类似地，@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) 与之前相同。 那么

  1. %loop(1) == %loop(2) 因为关于循环核心内在函数的动态规则。

  2. @op.1(1) == @op.1(2) 因为 @op.1(i) 使用 %loop 的值，该值引用 %loop(i)，并且 %loop(1) == %loop(2)。

  3. @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)

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

  1. 它没有在展开的循环内重复。 这是为了符合静态规则。

  2. 目前尚不清楚循环内在函数是否应该在余数中重复，或者 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 次迭代。

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

另一方面，允许不带“尾部”的展开。 例如，假设行程计数器已知是 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 内在函数通常预计会出现在自然循环的头部。 但是，它也可以出现在循环的非头部块中。 在这种情况下，循环通常无法展开。

提升和下沉

一般来说，禁止收敛操作的提升和下沉。 这是因为将操作移动到控制流中的不同点通常会更改到达该操作的线程集，因此也会更改执行该操作的收敛动态实例的线程集。 按照定义，这会更改参与收敛操作通信的线程集，这通常会更改其结果。

但是，存在许多例外情况，尽管其中大多数情况都需要额外的知识。

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

一些收敛操作可以被提升（hoisted）但不能被下沉（sunk），反之亦然。一个简单的例子是 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) ]
    ...
  }
}

在 condition 为假的线程中，无法保证 %id 的值。如果 @subgroupShuffle 被定义为当 %id 超出通信线程集时具有未定义行为（UB），那么推测性执行和提升 @subgroupShuffle 可能会引入 UB。

另一方面，如果 @subgroupShuffle 被定义为当 %id “超出范围”时，仅仅产生一个未定义的值或 poison 作为结果，那么推测性执行是可以接受的。

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

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

假设 %tok 仅在条件块内部使用，则锚点（anchor）可以被下沉。理由有两方面。首先，锚点具有实现定义的行为，而下沉是实现的一部分。其次，在原始程序中，在 @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)
}

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

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

请注意，entry intrinsic 的行为有所不同。在以下代码片段中，禁止下沉收敛操作：

%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)
}