収束演算のセマンティクス¶

概要 ¶

いくつかの並列実行環境では、スレッドをグループで実行し、収束演算と呼ばれる特殊なプリミティブを使用してグループ内での効率的な通信を可能にします。収束演算の結果は、それを「一緒に」、つまり収束的に実行するスレッドのセットに依存します。制御フローが分岐する、つまり同じグループのスレッドが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も同様です。

if文の上でsubgroupAddをホイスティングしてマージした場合、すべてのスレッド間で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:
  ...
}

@example_kernelがOpenCLカーネルであると仮定すると（「サブグループ」という用語から推測されるように）、entryイントリンシックは前の例のように動作します。「サブグループ」内のすべてのスレッド間で通信すると予想されます。これは通常、GPUハードウェアのSIMDベクトルにマップされます。

@subgroupAddへの呼び出しは、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で再収束するため、制御バリアを実行するすべてのスレッド（サブグループ/ウェーブ内）が同時に実行されます。2番目のバージョンでは、異なるパスを介して制御バリアに到達するスレッドは別々に同期します。最初の（そして唯一の）ポストドミネーターは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、Uへのconvergencectrlオペランドとして使用されるトークン値を定義する収束演算をDとします。2つのスレッドがUの収束した動的インスタンスを実行するのは、両方のスレッドのトークン値がDの収束した動的インスタンスによって返された場合のみです。

注記

このテキストでは、収束トークン値は動的インスタンスを表すと定義されています。しかし、収束した動的インスタンスが同じトークン値を生成すると仮定した場合、トークン値をスレッドの集合、具体的には定義命令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内の呼び出し元から呼び出された場合、2つのスレッドがこの組込み関数の収束した動的インスタンスを実行するのは、両方のスレッドが呼び出し元の収束した動的インスタンスを実行することで関数に入った場合のみです。

この組込み関数は、関数内で最大1回、関数のエントリーブロックでのみ発生します。この組込み関数が基本ブロックに存在する場合、同じ基本ブロック内の他の収束演算の前に置く必要があります。

この組込み関数が非収束関数に表示されるのはエラーです。

この組込み関数の呼び出し時に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、Uへのconvergencectrlオペランドとして使用されるトークン値を定義する収束演算をDとします。2つのスレッドがUの収束した動的インスタンスを実行するのは、以下の場合のみです。

両方のスレッドのトークン値がDの収束した動的インスタンスによって返され、
整数*n*が存在し、両方のスレッドがそのトークン値を使用して*n*回目にUを実行します。

この組込み関数の呼び出しでconvergencectrlオペランドバンドルを省略するのはエラーです。

この組込み関数が基本ブロックに存在する場合、同じ基本ブロック内の他の収束演算の前に置く必要があります。

サイクルの中心

サイクルCに、そのトークンオペランドがCの外で定義されているこの組込み関数の出現Hが含まれる場合、HはCの中心と呼ばれます。

注記

サイクルの静的規則は、中心が自然ループのヘッダーにのみ出現できることを意味します。これにより、中心はループ反復の直感的な概念を正確に表すことができます。この制約を緩和すると、還元不能なサイクルに対しても「サイクル反復」という新しい概念が得られます。しかし、これにより自然ループの中心がヘッダー以外のノードに存在することが可能になり、収束の観点からループ反復の意味に影響を与えます。現時点では、その実用的な応用が非常に少ないため、この状況は許可していません。

`llvm.experimental.convergence.anchor`¶

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

この組込み関数は、あらゆる「外部スコープ」とは独立した初期収束トークンを生成します。この組込み関数の収束した動的インスタンスを実行するスレッドの集合は、実装によって定義されます。

この組込み関数の呼び出し時にconvergencectrlオペランドバンドルを渡すのはエラーです。

注記

期待されるのは、「同時にアクティブになっている」グループ内のすべてのスレッドが収束した動的インスタンスを実行することで、プログラムがプログラムのあるローカル領域内で効率的に通信できるスレッドの最大集合を検出できるようにすることです。

制御されていない収束演算 ¶

明示的なconvergencectrlオペランドバンドルを持つ収束演算は、*制御された収束演算*と呼ばれます。その他のすべての収束演算は、*制御されていない*と言われます。

制御されていない収束演算は、convergent属性のみによって決定される*暗黙の収束制御*を持っていると言われます。LLVMで実装されているconvergent属性のセマンティクスは、文書化されているセマンティクスとは異なります。実装は、収束演算に関する一般的な直感を追跡しようとしますが、それは未規定のままです。そのため、暗黙の収束制御を明示的な収束制御トークンに完全に変換することは不可能であり、これらの2つのモードを同じ関数で混在させることはできません。

関数が制御された収束演算を含む場合、その関数内のすべての収束演算は、制御された演算または収束制御組込み関数の呼び出しのいずれかである必要があります。

トークンの推論 ¶

(このセクションは参考情報です)

場合によっては、明示的な収束制御トークンの観点から暗黙の収束制御を再解釈する必要がある場合があります。たとえば、関数呼び出しがインライン化され、呼び出し元または呼び出し先のいずれかに制御されていない収束演算が含まれている場合に発生する可能性があります。

制御されていない収束演算のいくつかの使用法では、次のプロパティを満たす必要がある場合があります。

環境によって定義されたスレッドグループ（OpenCLワークグループやサブグループなど）では、グループ内の1つのスレッドが収束演算を実行する場合、グループ内のすべてのスレッドがそのスレッドと収束して実行します。

明示的な収束制御の観点から見ると、これは各収束演算Xのconvergencectrlオペランドは最終的にllvm.experimental.convergence.entry組込み関数の呼び出しに由来する必要があることを意味します。これにより、Xに到達して収束するスレッドグループが、最初に収束してプログラムの実行を開始したグループと同じである可能性が維持されます。これに対して、llvm.experimental.convergence.anchor組込み関数は実装によって定義されたスレッドグループを取得しますが、これは上記の特性をサポートするには不十分です。

明示的な収束制御トークンの観点から暗黙の収束制御を近似する1つの方法は、上記の特性を維持する次の手順です。

すべての既約サイクルを可約サイクルに変換します。
関数のエントリブロックの先頭に、llvm.experimental.convergence.entryへの呼び出しを挿入します。
すべてのループヘッダの先頭に、llvm.experimental.convergence.loopへの呼び出しを挿入します。このループが最外部ループの場合、convergencectrlオペランドは、関数のエントリブロック内のllvm.experimental.convergence.entryへの呼び出しです。それ以外の場合は、convergencectrlオペランドは、親ループのヘッダ内のllvm.experimental.convergence.loopへの呼び出しです。
制御されていない収束演算Xごとに、この演算の兄弟である定義Dによって定義されたトークンを使用してconvergencectrlオペランドバンドルを追加します。Dは常にXを支配します。つまり、Xがどのサイクルにも含まれていない場合、Dはllvm.experimental.convergence.entryへの呼び出しです。それ以外の場合は、DはXの親サイクルの中心です。

静的ルール ¶

LLVM IRの整形式プログラムは、サイクルと収束領域に関する以下の静的ルールを満たしている必要があります。

閉路 ¶

CFGにおける閉路とは、CFG内のノードとエッジの連結されたシーケンスであり、始点と終点が同じです。

llvm.experimental.convergence.loopによる使用を除く、収束トークンTの使用を含むCFG内のすべての閉路には、Tの定義も含まれている必要があります。
CFG内の、収束トークンTの2つの異なる使用を含むすべての閉路には、Tの定義も含まれている必要があります。
CFG内の、2つの異なる収束トークンT1とT2の使用を含むすべての閉路には、少なくとも一方の定義が含まれている必要があります。

これらのルールをまとめると、すべての閉路Cに対して、Cで使用されるがCの外側で定義される収束トークンTは高々1つであり、TはC内で一度だけ使用され、llvm.experimental.convergence.loopによってのみ使用されることが分かります。

トークンTの使用Uを含んでいるがTの定義を含んでいないすべての閉路において、Uは閉路内のすべてのノードを支配している必要があります。

これは、llvm.experimental.convergence.loopが中心として出現できるのは、自然ループのヘッダ内だけであることを意味します。

十分条件: サイクルの特性から、閉路ではなくサイクルについて上記の特性を証明することが十分です。簡単に言うと、上記の静的ルールの1つ以上を違反する閉路は、同じルールを違反するサイクルに含まれています。

収束領域 ¶

収束トークンTの収束領域とは、Tがライブであり使用されている最小の領域、つまり、Tの使用に到達できるTの定義Dによって支配されるプログラムポイントの集合です。

有効なプログラムは、収束領域に関する以下の静的ルールを満たしている必要があります。

トークンT1の収束領域Rが収束トークンT2の使用を含む場合、RはT2の定義も含む必要があります。(言い換えれば、収束領域は合理的にネストされている必要があります。)

注記

簡潔にするため、このドキュメントでは「トークン定義Dの収束領域」という用語を、実際にはDによって定義されたトークンTの収束領域を指すために使用します。

非収束の推論 ¶

ターゲットまたは環境が、スレッドが収束演算を使用して通信しないこと、またはスレッドが分岐しないことを保証する場合、プログラム内の動的インスタンスは関連がなく、最適化プログラムは呼び出しサイトまたは関数上のconvergent属性、および呼び出しサイトでの明示的なconvergencectrlオペランドバンドルのいずれかの出現を削除できます。

最適化プログラムは、この呼び出しサイトの実行が常に非収束関数への呼び出しになることを証明できる場合、呼び出しサイトからconvergent属性と明示的なconvergencectrlオペランドバンドルを削除できます。

最適化プログラムは、関数がllvm.experimental.convergence.entryへの呼び出し、または制御されていない収束演算を含んでいないことを証明できる場合、関数上のconvergent属性を削除できます。

メモリモデルの非相互作用 ¶

演算が収束するという事実は、メモリモデルの観点からどのように処理されるかには影響しません。特に、convergentおよびreadnoneである演算は、メモリモデルに関して追加の順序制約を導入しません。メモリバリアの意味でも、スレッドの実行を同期させる制御バリアの意味でも、暗黙のバリアはありません。

参考情報: 収束した動的インスタンスを実行するスレッドは、必ずしも同時に実行するとは限りません。

その他の相互作用 ¶

関数はconvergentとspeculatableの両方である可能性があり、関数が未定義の動作を持たず、結果の計算以外の影響がないことを示していますが、それでも関数を実行するスレッドの集合の影響を受けます。これは通常、convergentによって課せられた制約が他の手段によってさらに緩和されない限り、関数への呼び出しの投機を妨げます。

制御された最大収束 ¶

制御された収束演算の各動的インスタンスに対するconverged-with関係は、収束トークンのセマンティクスによって完全に定義されます。しかし、llvm.experimental.convergence.anchorへの呼び出しにおける実装定義の収束は、既約サイクル内で発生する場合、選択されたサイクル階層にも依存します。

収束演算Dによって定義されたトークンが別の収束演算Uで使用されている場合、実装は、Uで収束するスレッドがすべて、Dで収束した後にUに到達したスレッドであることを保証する必要があります。ほとんどの実装では、DからUまでの任意のパス上の到達するノードでは、これらのスレッドだけが収束すると仮定するのが妥当です。言い換えれば、Dでのconverged-with関係は、各グループ内でのみ収束できるスレッドのグループを生成し、Dの収束領域内ではそうします。

これらはすべて、動的インスタンスに対する最大converged-with関係、ひいてはDの収束領域内の静的インスタンスのm-convergedプロパティに影響を与えます。

制御された最大converged-with関係

収束演算の動的インスタンスは、収束制御トークンのセマンティクスに従って、制御された最大converged-with関係に関連付けられます。

同じ非収束演算Xに対して異なるスレッドによって生成された動的インスタンスX1とX2は、以下の場合にのみ、制御された最大converged-with関係に関連付けられます。

XがDの収束領域にあるようなすべてのトークン定義Dの収束した動的インスタンスを両方のスレッドが実行し、

Xがどのサイクルにも含まれていないか、またはXを含むヘッダHを持つすべてのサイクルCに対して

それぞれのスレッドでX1に先行するHの動的インスタンスH1はすべてX2の前に収束しており、

それぞれのスレッドにおいて、X2より前に出現するHの全ての動的インスタンスH2は、X1に先行収束する。

X1がX2と収束しているという仮定は置かない。

制御されたm-収束静的インスタンス

与えられたCFG内のノードXは、以下の場合に限りm-収束していると報告される。

XがDの収束領域内にあるようなトークン定義Dについて、D自身もm-収束しており、

Xを含む全てのサイクルは以下の必要条件を満たす。

サイクル内の全ての分岐ノードは分岐ノード進入基準を満たし、

サイクル外部の分岐ノードからサイクルに到達する分岐パスは存在しない。

サイクル出口における時間的分岐 ¶

サイクルに発散出口がある場合、最大収束は全てのスレッドが出口ブロックで収束すると仮定する。しかし、サイクル外部の制御された収束演算がサイクル内部の演算Dによって定義されたトークンを使用する場合、Dの収束領域はサイクル外部に拡張される。2つのスレッドがサイクルを出る前に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) ]
  ...
}

このコードは、サイクルに関する最初の静的ルールによって禁止されています。

これを行う必要がある理由の最初の正式な議論は、2つのスレッドが@convergent.opの収束した動的インスタンスを実行するかどうかを決定するための動的ルールがこのコードで論理的矛盾を引き起こすことです。2つのスレッドがアンカーに続いてループの2回の反復を実行する収束した動的インスタンスを実行すると仮定します。スレッド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) ]
  ...
}

アンカーの収束した動的インスタンスを実行し、その後ループの2回の反復を実行するという同じシナリオでは、ループハート固有関数に関する動的ルールは、両方のスレッドがそれぞれの最初の反復で、そしてその後ループのそれぞれの2回目の反復で、ループハート固有関数の収束した動的インスタンスを実行することを意味します。

これは、それらが最初の反復で@convergent.opの収束した動的インスタンスI1 == J1を実行し、その後2回目の反復でI2 == J2を実行することを意味します。このルールは「もし、そしてその場合のみ」のルールであるため、ループ固有関数の非収束した動的インスタンスに由来する%loopのトークン値を参照する実行であるため、I1 != J2およびI2 != J1も意味します。

サイクルに関する静的ルールを追加する代わりに、動的ルールを変更できるかどうかを尋ねるかもしれません。それは、より深い困難のために実際的ではありません。再び正しくない収束制御を持つ次のループを考えてみましょう。

; 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)

2つのスレッドがアンカーの収束した動的インスタンスを実行し、その後この基本ブロックのシーケンスを実行すると仮定します。

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

つまり、両方のスレッドはループの2回の反復を実行しますが、異なる反復で異なる収束演算を実行します。スレッド間でループ反復間の関係を形成せずに、どの収束演算の動的インスタンスがスレッド間で同じであるべきかを定義する妥当な方法はありません。

繰り返しますが、これはループハート固有関数を追加することで対処できます。最も自然な方法は次のとおりです。

; (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の実行の動的インスタンスとします。すると、次が得られます。

ループハート固有関数に関する動的ルールのため、j = 1, 2について%loop(1;j) == %loop(2;j)。
同じスレッドによる異なる実行は異なる動的インスタンスで発生するという基本ルールのため、i = 1, 2について%loop(i;1) != %loop(i;2)。
@op.1(1)は%loop(1;1)を参照する%loopのトークン値を使用し、@op.1(2)は%loop(2;2) == %loop(1;2)を参照するそれを使用するため、@op.1(1) != @op.1(2)。
同様に、@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によるループハート固有関数の実行の動的インスタンス（各スレッドは1回だけ実行する）とし、@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) ]
    }
  }
}

%anchorを使用するループハートイントリンシクの両方を通るサイクル（CFG内の閉じたウォーク）がありますが、%anchorの定義は通らないため、このコードは無効です。

プログラム変換の正当性の例 ¶

（このセクションは参考情報です。）

前のセクションの規則が示唆するように、プログラム変換は、収束演算のセマンティクスを保持または改良する場合、収束演算に関して正しいです。これは、変換されたプログラムにおける通信スレッドの集合は、元のプログラムで可能であったものでなければならないことを意味します。

単一スレッドに焦点を当てたプログラム変換は、分岐をまたいで収束演算をシンクまたはホイストしない場合、一般的に保守的に正しくなります。これは、制御フローグラフを変更するプログラム変換にも当てはまります。

たとえば、収束演算を含まないループをアンロールしても、ループ外の収束演算に必要な保証を破ることはありません。

ループアンローリングの例 ¶

ここでは、3種類のループアンローリングについて考えます。

既知の繰り返し回数がない部分アンローリング。そのため、「テール」が必要になります。
繰り返し回数が倍数の部分アンローリング。そのため、「テール」は必要ありません。
ループを削除する完全アンローリング。

@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回のループ反復を実行する2つのスレッドについて考えてみましょう。

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

ループハートイントリンシクに関する動的規則により、これらのスレッドは最初の3回の反復で収束動的インスタンスを実行し、その後、スレッド2は別の動的インスタンスを単独で実行します。

一般的な収束演算に関する動的規則により、スレッドは最初の3回の反復で@convergent.operationの収束動的インスタンスを実行します（つまり、反復*n*でスレッド1によって実行される動的インスタンスは、反復*n*でスレッド2によって実行される動的インスタンスと同じです。*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

上記の議論と同様に、これらは最初のアンロールされたループの反復（元のループの最初の2回の反復に対応）で%innerイントリンシクと@convergent.operationの収束動的インスタンスを実行します。

ただし、元のループの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への呼び出しをホイスティングした後、通信しているスレッドの集合は元のプログラムの2つのスレッドの集合の和集合であるため、%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の値に関する保証はありません。%idが通信しているスレッドの集合の外にある場合に@subgroupShuffleがUBとして定義されている場合、@subgroupShuffleを投機的にホイスティングすると、UBが発生する可能性があります。

一方、%idが「範囲外」の場合に@subgroupShuffleが単に未定義の値またはポイズンを結果として生成するように定義されている場合、投機は問題ありません。

llvm.experimental.convergence.anchorはconvergentとしてマークされていますが、場合によってはシンキングできます。たとえば、擬似コードでは：

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

%tokが条件ブロック内でのみ使用されていると仮定すると、アンカーは沈めることができます。その理由は2つあります。まず、アンカーは実装定義の動作を持ち、その沈め込みは実装の一部です。第二に、元のプログラムですでに、@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`¶

制御されていない収束演算 ¶

トークンの推論 ¶

静的ルール ¶

閉路 ¶

収束領域 ¶

非収束の推論 ¶

メモリモデルの非相互作用 ¶

その他の相互作用 ¶

制御された最大収束 ¶

サイクル出口における時間的分岐 ¶

サイクルに関する静的ルールの理由 ¶

プログラム変換の正当性の例 ¶

ループアンローリングの例 ¶

ホイスティングとシンキング ¶