Texture sampling in a pixel shader¶

The following stylized pixel shader samples a texture at a given set ofcoordinates, using the builtin functiontextureSample. Texture samplingrequires screen-space derivatives of the coordinates to determine the level ofdetail (mipmap level) of the sample. They are commonly approximated by takingthe difference between neighboring pixels, which are computed by differentthreads in the same group:

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

From a purely single-threaded perspective, sinking thetextureSample intothe if-statement appears legal. However, if the condition is false for someneighboring pixels, then their corresponding threads will not execute togetherin the group, making it impossible to take the difference of coordinates as anapproximation of the screen-space derivative. In practice, the outcome will bean undefined value.

That is, thetextureSample operation fits our definition of a convergentoperation:

1. It communicates with a set of threads that implicitly depends on controlflow.

2. Correctness depends on this set of threads.

The compiler frontend can emit IR that expresses the convergence constraints asfollows:

definevoid@example_shader()convergent{%entry=calltoken@llvm.experimental.convergence.entry()...%color=callT@textureSample(U%texture,V%coordinates)["convergencectrl"(token%entry)]bri1%condition,label%then,label%endthen:callvoid@use(T%color)brlabel%endend:retvoid}

Thellvm.experimental.convergence.entryintrinsic is itselfconvergent, and we expect it to communicate at leastamong all threads of the same “quad” – a group of 2x2 pixels that areevaluated together for the purpose of approximating screen-space derivatives.This fact is not part of the generic LLVM IR semantics; it would have to bedefined somewhere else, for example as part of target-specific ABI definitionsand/or in reference to some relevant API specs.

Since the@textureSample call then uses the token produced by the entryintrinsic in itsconvergencectrl bundle, and has no additional controldependencies, it must communicate among the same set of threads. This indicatesto generic program transforms that sinking the@textureSample call isforbidden. (A program transform can still sink the call if it can prove somehow,e.g. by leaning on target-specific callbacks that can analyze the program withadditional knowledge, that%condition is always uniform across the threadsreferenced by theconvergence token%entry.)

Reductions inside divergent control flow¶

The following example shows that merging common code of branches can beincorrect in the face of convergent operations:

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

ThesubgroupAdd computing thetotal_gains will be executed by thesubset of threads with positivedelta in a subgroup (wave), and so will sumup all thedelta values of those threads; and similarly for thesubgroupAdd that computes thetotal_losses.

If we were to hoist and merge thesubgroupAdd above the if-statement, itwould sum up thedelta acrossall threads instead.

The compiler frontend can emit IR that expresses the convergence constraintsas follows:

definevoid@example_kernel()convergent{%entry=calltoken@llvm.experimental.convergence.entry()%delta=...%cc=icmpsgti32%delta,0bri1%cc,label%then,label%elsethen:%total_gains=calli32@subgroupAdd(i32%delta)["convergencectrl"(token%entry)]...brlabel%endelse:%total_losses=calli32@subgroupAdd(i32%delta)["convergencectrl"(token%entry)]...brlabel%endend:...}

The entry intrinsic behaves like in the previous example: assuming that@example_kernel is an OpenCL kernel (as hinted at by the “subgroup”terminology), we expect it to communicate among all threads within the“subgroup”. This typically maps to a SIMD vector on GPU hardware.

The calls to@subgroupAdd use the token produced by the entry intrinsic,but they also have an additional control dependency. According to the rulesdefined in this document, they only communicate among the subset of threadsthat actually end up executing the respective (static) call site.

Hoisting them would remove the control dependency and cause them to communicateamong the full set of threads that the entry intrinsic communicated with.Again, hoisting is allowed if it can be proven that%cc is always uniformamong the relevant set of threads: in that case, the@subgroupAdd alreadycommunicates among the full set of threads in the original program.

Unstructured control flow¶

Consider an example of how jump threading removes structure in a way that canmake semantics non-obvious without the convergence intrinsics described in thisdocument:

voidexample_original(){entry:...bri1%cond1,label%then1,label%midthen1:...%cond2=...brlabel%midmid:%flag=phii1[true,%entry],[%cond2,%then1]bri1%flag,label%then2,label%endthen2:...callvoid@subgroupControlBarrier()...brlabel%endend:}voidexample_jumpthreaded(){entry:...bri1%cond1,label%then1,label%then2then1:...%cond2=...bri1%cond2,label%then2,label%endthen2:...callvoid@subgroupControlBarrier()...brlabel%endend:}

Is the control barrier guaranteed to synchronize among the same set of threadsin both cases? Different implementations in the literature may give differentanswers to this question:

• In an implementation that reconverges at post-dominators, threads reconvergeatmid in the first version, so that all threads (within a subgroup/wave)that execute the control barrier do so together. In the second version,threads that reach the control barrier via different paths synchronizeseparately: the first (and only) post-dominator isend, so threads do notreconverge before then.

• An implementation that sorts basic blocks topologically and ensures maximalreconvergence for each basic block would behave the same way in bothversions.

We generally take the stance that reconvergence in acyclic control flow mustbe maximal. The compiler frontend could augment the original code as follows:

definevoid@example_original()convergent{entry:%entry=calltoken@llvm.experimental.convergence.entry()...bri1%cond1,label%then1,label%midthen1:...%cond2=...brlabel%midmid:%flag=phii1[true,%entry],[%cond2,%then1]bri1%flag,label%then2,label%endthen2:...callvoid@subgroupControlBarrier()["convergencectrl"(token%entry)]...brlabel%endend:}

If S is the set of threads that the entry intrinsic communicated with, thenthe@subgroupControlBarrier call communicates with the subset of S thatactually reaches the call site. This set of threads doesn’t change afterjump-threading, so the answer to the question posed above remains the same.

Opportunistic convergent operations¶

Some programs have local regions of code that contain a sequence of convergentoperations where the code does not care about the exact set of threads withwhich it is executed, but only that the set of threads is the same for all theoperations within the sequence. (If a subset of the convergent operations in thesequence have additional, non-uniform control dependencies, then this is notpossible. However, the code may still require that the sets of threads arelogically consistent with the conditions of those control dependencies.) In thiscase,llvm.experimental.convergence.anchor can be used to express the desiredsemantics.

The following example function could be part of a hypothetical “append buffer”implementation, where threads conditionally write fixed-sized recordscontiguously into a global buffer. The function@reserveSpaceInBufferreturns the index into the buffer at which the calling thread should store itsdata.

This could be achieved by using a simple atomic operation in every thread tobump an allocation counter.

However, the following implementation can be more performant on some hardware,because it uses only a single atomic operation for an entire group of threads.To do this, it first determines the total size of the group, which will be theoperand to the atomic operation, and then later broadcasts the result of theatomic operation to all threads of the group, so that each thread can computeits individual position in the buffer:

definei32@reserveSpaceInBuffer(){; NOTE: _not_ a convergent function!entry:%anchor=calltoken@llvm.experimental.convergence.anchor()%ballot=calli64@subgroupBallot(i1true)["convergencectrl"(token%anchor)]%numThreads.p=calli64@llvm.ctpop.i64(i64%ballot)%numThreads=trunci64%numThreads.ptoi32%absoluteThreadIdx=calli32@getSubgroupLocalInvocationId()%absoluteThreadIdx.ext=zexti32%absoluteThreadIdxtoi64%mask.p=shli641,%absoluteThreadIdx.ext%mask=subi64%mask.p,1%maskedBallot=andi64%ballot,%mask%relativeThreadIdx.p=calli64@llvm.ctpop.i64(i64%maskedBallot)%relativeThreadIdx=trunci64%relativeThreadIdx.ptoi32%isFirstThread=icmpeqi32%relativeThreadIdx,0bri1%isFirstThread,label%then,label%endthen:%baseOffset.1=atomicrmwaddptr@bufferAllocationCount,i32%numThreadsmonotonicbrlabel%endend:%baseOffset.2=phii32[undef,%entry],[%baseOffset.1,%then]%baseOffset=calli32@subgroupBroadcastFirst(i32%baseOffset.2)["convergencectrl"(token%anchor)]%offset=addi32%baseOffset,%relativeThreadIdxreti32%offset}

The key here is that the function really doesn’t care which set of threads itis being called with. It takes whatever set of threads it can get. What theimplementation of the function cares about is that the initial@subgroupBallot – which is used to retrieve the bitmask of threads thatexecuted the anchor together – executes with the same set of threads as thefinal@subgroupBroadcastFirst. Nothing else is required for correctness asfar as convergence is concerned.

The function@reserveSpaceInBuffer itself is _not_convergent: callersare free to move call sites of the function as they see fit. This can changethe behavior in practice, by changing the sets of threads that are groupedtogether for the atomic operation. This can be visible in the output of theprogram, since the order in which outputs appear in the buffer is changed.However, this does not break the overall contract that@reserveSpaceInBufferhas with its caller – which makes sense: the order of outputs isnon-deterministic anyway because of the atomic operation that is involved.

If the function is inlined, the use of the anchor intrinsic similarly indicatesthat certain transforms which are usually forbidden by the presence ofconvergent operations are in fact allowed, as long as they don’t break up theregion of code that is controlled by the anchor.

Extended Cycles: Divergent Exit from a Loop¶

High-level languages typically provide abreak statement that transferscontrol out of a loop statement. In most cases, the loop is structured and hencethere is no ambiguity about convergence inside the loop. But an ambiguity ariseswhen abreak is control dependent on a divergent condition inside the loop.Consider the following example:

voidexample(){// A...for(...){// Bif(condition){// divergent condition// Cconvergent_op();break;}// D...}// E}

In this program, the call to convergent_op() is lexically “inside” theforloop. But when translated to LLVM IR, the basic block B is an exiting blockending in a divergent branch, and the basic block C is an exit of the loop.Thus, the call to convergent_op() is outside the loop. This causes a mismatchbetween the programmer’s expectation and the compiled program. The call shouldbe executed convergently on every iteration of the loop, by threads thattogether take the branch to exit the loop. But when compiled, all threads thattake the divergent exit on different iterations first converge at the beginningof basic block C and then together execute the call to convergent_op().

In this case,llvm.experimental.convergence.loop can be used to express the desiredsemantics. A call to this intrinsic is placed in the loop header, which trackseach iteration of the loop. The token produced by this is used as aconvergencectrl operand to the convergent call. The semantics of theloop intrinsic ensures that the convergent call is performed convergentlyonly by those threads that convergently exited the loop in a given iteration.

definevoid@example()convergent{%entry=calltoken@llvm.experimental.convergence.entry()brlabel%forfor:%inner=calltoken@llvm.experimental.convergence.loop()["convergencectrl"(token%entry)]%for.cond=i1...bri1%for.cond,label%B,label%EB:...%condition=i1...bri1%condition,label%C,label%DC:callvoid@convergent_op()["convergencectrl"(token%inner)]brlabel%ED:...brlabel%forE:...retvoid}

The LLVM IR version of the same program shows a cycle consisting of the basicblocks%for,%B and%D, while%C is an exit reached by thedivergent branch at the end of the exiting block%B. But the use ofconvergence control tokens makes it clear that block%C must be executedconvergently only by those threads that convergently take the exit edge from %Bto%C. In other words, the convergent execution of%C is governed by thecall to thellvm.experimental.convergence.loop intrinsic inside the cycle. The cycle iseffectively extended to include all uses of this token that lie outside thecycle.

llvm.experimental.convergence.entry¶

token@llvm.experimental.convergence.entry()convergentreadnone

This intrinsic is used to tie the dynamic instances inside of a function tothose in the caller.

1. If the function is called from outside the scope of LLVM, the convergence ofdynamic instances of this intrinsic are environment-defined. For example:

   1. In an OpenCLkernel launch, the maximal set of threads thatcan communicate outside the memory model is aworkgroup.Hence, a suitable choice is to specify that all the threads froma single workgroup in OpenCL execute converged dynamic instancesof this intrinsic.

   2. In a C/C++ program, threads are launched independently and they cancommunicate only through the memory model. Hence the dynamic instances ofthis intrinsic in a C/C++ program are never converged.

2. If the function is called from a call-site in LLVM IR, then twothreads execute converged dynamic instances of this intrinsic if andonly if both threads entered the function by executing convergeddynamic instances of the call-site.

This intrinsic can occur at most once in a function, and only in the entryblock of the function. If this intrinsic occurs in a basic block, then it mustprecede any other convergent operation in the same basic block.

It is an error if this intrinsic appears in a non-convergent function.

It is an error to specify aconvergencectrl operand bundle at acall to this intrinsic.

Function inlining substitutes this intrinsic with the token from the operandbundle. For example:

// Before inlining:voidcallee()convergent{%tok=calltoken@llvm.experimental.convergence.entry()convergent_operation(...)["convergencectrl"(token%tok)]}voidmain(){%outer=calltoken@llvm.experimental.convergence.anchor()for(...){%inner=calltoken@llvm.experimental.convergence.loop()["convergencectrl"(token%outer)]callee()["convergencectrl"(token%inner)]}}// After inlining:voidmain(){%outer=calltoken@llvm.experimental.convergence.anchor()for(...){%inner=calltoken@llvm.experimental.convergence.loop()["convergencectrl"(token%outer)]convergent_operation(...)["convergencectrl"(token%inner)]}}

llvm.experimental.convergence.loop¶

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

This intrinsic represents the place where an imaginary counter is incrementedfor determining convergence inside a control flow cycle.

LetU be a call to this intrinsic andD be the convergent operation thatdefines the token value used as theconvergencectrl operand toU. Twothreads execute converged dynamic instances ofU if and only if:

1. The token value in both threads was returned by converged dynamicinstances ofD, and,

2. There is an integern such that both threads executeU for then’th timewith that token value.

It is an error to omit theconvergencectrl operand bundle on acall to this intrinsic.

If this intrinsic occurs in a basic block, then it must precede any otherconvergent operation in the same basic block.

Heart of a Cycle:

If acycleC contains an occurrenceH ofthis intrinsic whose token operand is defined outsideC, thenH iscalled the heart ofC.

Note

The static rules for cycles imply that a heart can occur only in the headerof a natural loop. This ensures that the heart closely represents theintuitive notion of a loop iteration. If this restriction is relaxed, theresulting semantics provides a new notion of “cycle iteration” even forirreducible cycles. But this allows a natural loop to have a heart in anode other than its header, which has interesting consequences on themeaning of a loop iteration in terms of convergence. For now, we disallowthis situation since its practical application is very rare.

llvm.experimental.convergence.anchor¶

token@llvm.experimental.convergence.anchor()convergentreadnone

This intrinsic produces an initial convergence token that is independent fromany “outer scope”. The set of threads executing converged dynamic instances ofthis intrinsic is implementation-defined.

It is an error to pass aconvergencectrl operand bundle at acall to this intrinsic.

Inferring Tokens¶

(This section is informational)

Sometimes, it may be necessary to reinterpret the implicit convergence controlin terms of explicit convergence control tokens. For example, this may happenwhen a function call is inlined, and either the caller or the callee containsuncontrolled convergent operations.

Some uses of uncontrolled convergent operations may need to satisfy thefollowing property:

For an environment-defined group of threads (such as an OpenCL workgroup orsubgroup), if one thread in the group executes a convergent operation, thenall threads in the group do so convergently with that thread.

In terms of explicit convergence control, this means that theconvergencectrl operand on each convergent operationX must ultimatelyoriginate from a call to thellvm.experimental.convergence.entry intrinsic. This preserves the possibilitythat the group of threads that converge on reachingX is the same group thatoriginally started executing the program in convergence. In comparison, thellvm.experimental.convergence.anchor intrinsic captures animplementation-defined group of threads, which is insufficient to support theabove property.

One way to approximate implicit convergence control in terms of explicitconvergence control tokens is the following procedure, which preserves the abovementioned property:

1. Convert every irreducible cycle into a reducible cycle.

2. Insert a call tollvm.experimental.convergence.entry at the start of the entry block of thefunction.

3. Insert a call tollvm.experimental.convergence.loop at the start of every loop header. Ifthis loop is an outermost loop, theconvergencectrl operand is the calltollvm.experimental.convergence.entry in the entry block of the function.Otherwise, theconvergencectrl operand is the call tollvm.experimental.convergence.loop in the parent loop’s header.

4. For each uncontrolled convergent operationX, add aconvergencectrloperand bundle using the token defined by a definitionD that is asibling to this operation.D always dominatesX — ifX is not in any cycle, thenD is a call tollvm.experimental.convergence.entry; otherwiseD is the heart of theparent cycle ofX.

Closed Paths¶

Aclosed path in a CFG is a connected sequence ofnodes and edges in the CFG whose start and end points are the same.

1. Every closed path in the CFG that contains a use of a convergence token T otherthan a use byllvm.experimental.convergence.loopmust also contain the definition of T.

2. Every closed path in the CFG that contains two different uses of a convergencetoken T must also contain the definition of T.

3. Every closed path in the CFG that contains uses of two different convergence tokensT1 and T2 must also contain the definition of at least one of them.

Taken together, these rules imply that for every closed path C, there can be at mostone convergence token T which is used in C but defined outside of it, and thatT can be used only once in C, and only byllvm.experimental.convergence.loop.

4. In every closed path that contains a use U of a token T but not thedefinition of T, U must dominate all nodes in the closed path.

This implies thatllvm.experimental.convergence.loop can appear as a heartonly in the header of a natural loop.

Sufficient Conditions: From theproperties of cycles, it is sufficient to prove the above propertiesfor cycles instead of closed paths. Briefly, any closed path that violatesone or more of the above static rules is contained in a cycle that alsoviolates the same rule(s).

Convergence Regions¶

Theconvergence region of a convergence token T is the minimal region inwhich T is live and used, i.e., the set of program points dominated by thedefinition D of T from which a use of T can be reached.

The following static rule about convergence regions must be satisfied byvalid programs:

If a convergence region R for a token T1 contains a use of a convergencetoken T2, then R must also contain the definition of T2. (In other words,convergence regions must be reasonably nested.)

Temporal Divergence at Cycle Exit¶

When a cycle has a divergent exit, maximal convergence assumes that all threadsconverge at the exit block. But if a controlled convergent operation outside thecycle uses a token defined by an operationD inside the cycle, theconvergence region ofD now extends outside the cycle. If two threadsexecuted converged dynamic instances ofD before exiting the cycle, thenthey continue to execute converged dynamic instances of nodes in the convergenceregion ofD outside the cycle. Thus, for a valueV defined inside thecycle, any useU ofV within the convergence region ofT uses theoutput of converged dynamic instances ofV. IfV is uniform, then itsuse at such aU is also uniform. In other words, temporal divergence appliesonly to a use ofV that is outside the convergence region ofD.

Loop unrolling examples¶

We consider three kinds of loop unrolling here:

• Partial unrolling with no known trip multiple, so a “tail” is required tocollect the remaining elements.

• Partial unrolling by a trip multiple, so no “tail” is required.

• Full unrolling, which eliminates the loop.

The first kind is forbidden when@llvm.experimental.convergence.loop isused. We illustrate the reasoning with some examples.

First, an arbitrary loop that contains convergent operationscan be unrolledin all of these ways, even with “tail”, if all convergent operations refer backto an anchor inside the loop. For example (in pseudo-code):

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

This can be unrolled to:

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

This is likely to change the behavior of the convergent operation if thereare threads whose initial counter value is not a multiple of 2. In particular,all threads with an odd trip count are now likely to execute the convergentoperation in their respective final iterations together because theunderlying implementation is likely to try to group as many threads togetheras possible for the execution of the “tail”.

This change is allowed because the anchor intrinsic has implementation-definedconvergence behavior and the loop unrolling transform is considered to be partof the implementation. Another way of reasoning is that while thelikelybehavior of the code has changed, theguarantees about its behavior haveremained the same.

If the loop contains uncontrolled convergent operations, this kind of unrollingis forbidden.

Unrolling a loop with convergent operations that refer to tokens producedoutside the loop is forbidden when a “tail” or “remainder” would have tobe introduced. Consider:

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

To understand why unrolling is forbidden, consider two threads that executeconverged dynamic instances of the anchor and then proceed with 3 and 4 loopiterations, respectively:

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

By the dynamic rule on loop heart intrinsics, these threads execute convergeddynamic instances of the loop intrinsic for the first 3 iterations, and thenthread 2 executes another dynamic instance by itself.

By the dynamic rule on general convergent operations, the threads executeconverged dynamic instances of the@convergent.operation in the first 3iterations (that is, the dynamic instance executed by thread 1 in iterationn is the same as that executed by thread 2 in iterationn, forn = 1,2,3;the dynamic instance executed in iteration 1 is different from that initeration 2, etc.).

Now assume that the loop is unrolled by a factor of 2, which requires aremainder as follows:

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

First of all, note some interesting problems surrounding the loop intrinsic:

1. It isnot duplicated inside the unrolled loop. This is to comply withtheStatic Rules.

2. It is unclear whether the loop intrinsic ought to be duplicated in theremainder, or whether the final@convergent.operation in D should justrefer to either%inner (which is possible in SSA form) or directly to%outer. The decision made here is arbitrary and doesn’t change theargument that follows. Ultimately, it simply doesn’t matter because thetransform is incorrect either way.

The threads now execute the following sequences of blocks:

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

Analogous to the argument above, they execute converged dynamic instances of the%inner intrinsic and the@convergent.operation in the first iterationof the unrolled loop, which corresponds to the first 2 iterations of theoriginal loop.

However, they execute different static calls to@convergent.operation forthe 3rd iteration of the original loop. In thread 1, that iteration correspondsto the call in the remainder, while in thread 2 it corresponds to the firstcall to@convergent.operation in the unrolled loop. Therefore, they executenon-converged dynamic instances, which means that the set of communicating threadsfor the 3rd iteration of the original loop is different. This is why theunrolling is incorrect.

On the other hand, unrolling without “tail” is allowed. For example, assumingthat the trip counter is known to be a multiple of 2, we can unroll the loopas follows:

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

Note again that the loop intrinsic is not duplicated.

Thellvm.experimental.convergence.loopintrinsic is typically expected to appear in the header of a natural loop.However, it can also appear in non-header blocks of a loop. In that case, theloop can generally not be unrolled.

Hoisting and sinking¶

In general, hoisting and sinking of convergent operations is forbidden. This isbecause moving the operation to a different point in control flow generallychanges the set of threads that reach the operation and therefore, the set ofthreads that execute converged dynamic instances of the operation. Bydefinition, this changes the set of threads that participate in thecommunication of the convergent operation, which will typically change itsresult.

There are a number of exceptions, though most of them require additionalknowledge.

For example, hoisting and sinking acrossuniform conditional branches – i.e.,conditional branches where within every possible relevant set of threads, allthreads will always take the same direction – is generally allowed. See the endof theexample of reductions inside control flow for a brief discussion.

Some convergent operations can be hoisted but not sunk, or vice versa. A simpleexample is thesubgroupShuffle(data,id) operation. It returns thedataoperand of the thread identified byid, where thread IDs are fixed andassigned to each thread at launch. The result is undefined (or perhaps there isUB, depending on the language and environment) if threadid is not in thecommunicating set of threads. So hoisting is allowed in the followingpseudo-code example:

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

After hoisting the calls to@subgroupShuffle, the communicating set ofthreads is the union of the two sets of threads in the original program, so%id can only go “out of range” after hoisting if it did so in the originalprogram.

However, speculative execution of@subgroupShuffle in the following programmay be forbidden:

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

There is no guarantee about the value of%id in the threads wherecondition is false. If@subgroupShuffle is defined to have UB when%id is outside of the set of communicating threads, then speculating andhoisting@subgroupShuffle might introduce UB.

On the other hand, if@subgroupShuffle is defined such that it merelyproduces an undefined value or poison as result when%id is “out of range”,then speculating is okay.

Even thoughllvm.experimental.convergence.anchoris marked asconvergent, it can be sunk in some cases. For example, inpseudo-code:

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

Assuming that%tok is only used inside the conditional block, the anchor canbe sunk. The rationale is two-fold. First, the anchor has implementation-definedbehavior, and the sinking is part of the implementation. Second, already in theoriginal program, the set of threads that communicates in the@convergent.operation is automatically subset to the threads for whichcondition is true.

Anchors can be hoisted in acyclic control flow. For example:

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

The anchors can be hoisted, resulting in:

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

The behavior is unchanged, since each of the static convergent operations onlyever communicates with threads that have the samecondition value.By contrast, hoisting the convergent operations themselves is forbidden.

Hoisting and sinking anchors out of and into loops is forbidden. For example:

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

Hoisting the anchor would make the program invalid according to the staticvalidity rules. Conversely:

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

The program would stay valid if the anchor was sunk into the loop, but itsbehavior could end up being different. If the anchor is inside the loop, theneach loop iteration has a new dynamic instance of the anchor, and the set ofthreads participating in those dynamic instances of the anchor could bedifferent in arbitrary implementation-defined ways. Via the dynamic rules aboutdynamic instances of convergent operations, this then implies that the set ofthreads executing@convergent.operation could be different in each loopiteration in arbitrary implementation-defined ways.

Convergent operations can be sunk together with their anchor. Again inpseudo-code:

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

Assuming that%tok,%a, and%b are only used inside the conditionalblock, all can be sunk together:

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

The rationale is that the anchor intrinsic has implementation-defined behavior,and the sinking transform is considered to be part of the implementation:the sinking will restrict the set of communicating threads to those for whichcondition is true, but that could have happened in the original programanyway for some arbitrary other reason.

However, sinkingonly the convergent operation producing%b would beincorrect. That would allow threads for whichcondition is false tocommunicate at%a, but not at%b, which the original program doesn’tallow.

Note that the entry intrinsic behaves differently. Sinking the convergentoperations is forbidden in the following snippet:

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