716 lines · plain
1.. _convergence-and-uniformity:2 3==========================4Convergence And Uniformity5==========================6 7.. contents::8 :local:9 10Introduction11============12 13In some environments, groups of threads execute the same program in parallel,14where efficient communication within a group is established using special15primitives called :ref:`convergent operations<convergent_operations>`. The16outcome of a convergent operation is sensitive to the set of threads that17participate in it.18 19The intuitive picture of *convergence* is built around threads executing in20"lock step" --- a set of threads is thought of as *converged* if they are all21executing "the same sequence of instructions together". Such threads may22*diverge* at a *divergent branch*, and they may later *reconverge* at some23common program point.24 25In this intuitive picture, when converged threads execute an instruction, the26resulting value is said to be *uniform* if it is the same in those threads, and27*divergent* otherwise. Correspondingly, a branch is said to be a uniform branch28if its condition is uniform, and it is a divergent branch otherwise.29 30But the assumption of lock-step execution is not necessary for describing31communication at convergent operations. It also constrains the implementation32(compiler as well as hardware) by overspecifying how threads execute in such a33parallel environment. To eliminate this assumption:34 35- We define convergence as a relation between the execution of each instruction36 by different threads and not as a relation between the threads themselves.37 This definition is reasonable for known targets and is compatible with the38 semantics of :ref:`convergent operations<convergent_operations>` in LLVM IR.39- We also define uniformity in terms of this convergence. The output of an40 instruction can be examined for uniformity across multiple threads only if the41 corresponding executions of that instruction are converged.42 43This document describes a static analysis for determining convergence at each44instruction in a function. The analysis extends previous work on divergence45analysis [DivergenceSPMD]_ to cover irreducible control-flow. The described46analysis is used in LLVM to implement a UniformityAnalysis that determines the47uniformity of value(s) computed at each instruction in an LLVM IR or MIR48function.49 50.. [DivergenceSPMD] Julian Rosemann, Simon Moll, and Sebastian51 Hack. 2021. An Abstract Interpretation for SPMD Divergence on52 Reducible Control Flow Graphs. Proc. ACM Program. Lang. 5, POPL,53 Article 31 (January 2021), 35 pages.54 https://doi.org/10.1145/343431255 56Motivation57==========58 59Divergent branches constrain60program transforms such as changing the CFG or moving a convergent61operation to a different point of the CFG. Performing these62transformations across a divergent branch can change the sets of63threads that execute convergent operations convergently. While these64constraints are out of scope for this document,65uniformity analysis allows these transformations to identify66uniform branches where these constraints do not hold.67 68Uniformity is also useful by itself on targets that execute threads in69groups with shared execution resources (e.g. waves, warps, or70subgroups):71 72- Uniform outputs can potentially be computed or stored on shared73 resources.74- These targets must "linearize" a divergent branch to ensure that75 each side of the branch is followed by the corresponding threads in76 the same group. But linearization is unnecessary at uniform77 branches, since the whole group of threads follows either one side78 of the branch or the other.79 80Terminology81===========82 83Cycles84 Described in :ref:`cycle-terminology`.85 86Closed path87 Described in :ref:`cycle-closed-path`.88 89Disjoint paths90 Two paths in a CFG are said to be disjoint if the only nodes common91 to both are the start node or the end node, or both.92 93Join node94 A join node of a branch is a node reachable along disjoint paths95 starting from that branch.96 97Diverged path98 A diverged path is a path that starts from a divergent branch and99 either reaches a join node of the branch or reaches the end of the100 function without passing through any join node of the branch.101 102.. _convergence-dynamic-instances:103 104Threads and Dynamic Instances105=============================106 107Each occurrence of an instruction in the program source is called a108*static instance*. When a thread executes a program, each execution of109a static instance produces a distinct *dynamic instance* of that110instruction.111 112Each thread produces a unique sequence of dynamic instances:113 114- The sequence is generated along branch decisions and loop115 traversals.116- Starts with a dynamic instance of a "first" instruction.117- Continues with dynamic instances of successive "next"118 instructions.119 120Threads are independent; some targets may choose to execute them in121groups in order to share resources when possible.122 123.. figure:: convergence-natural-loop.png124 :name: convergence-natural-loop125 126.. table::127 :name: convergence-thread-example128 :align: left129 130 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+131 | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |132 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+133 | Thread 1 | Entry1 | H1 | B1 | L1 | H3 | | L3 | | | | Exit |134 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+135 | Thread 2 | Entry1 | H2 | | L2 | H4 | B2 | L4 | H5 | B3 | L5 | Exit |136 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+137 138In the above table, each row is a different thread, listing the139dynamic instances produced by that thread from left to right. Each140thread executes the same program that starts with an ``Entry`` node141and ends with an ``Exit`` node, but different threads may take142different paths through the control flow of the program. The columns143are numbered merely for convenience, and empty cells have no special144meaning. Dynamic instances listed in the same column are converged.145 146.. _convergence-definition:147 148Convergence149===========150 151*Convergence-before* is a strict partial order over dynamic instances152that is defined as the transitive closure of:153 1541. If dynamic instance ``P`` is executed strictly before ``Q`` in the155 same thread, then ``P`` is *convergence-before* ``Q``.1562. If dynamic instance ``P`` is executed strictly before ``Q1`` in the157 same thread, and ``Q1`` is *converged-with* ``Q2``, then ``P`` is158 *convergence-before* ``Q2``.1593. If dynamic instance ``P1`` is *converged-with* ``P2``, and ``P2``160 is executed strictly before ``Q`` in the same thread, then ``P1``161 is *convergence-before* ``Q``.162 163.. table::164 :name: convergence-order-example165 :align: left166 167 +----------+-------+-----+-----+-----+-----+-----+-----+-----+------+168 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |169 +----------+-------+-----+-----+-----+-----+-----+-----+-----+------+170 | Thread 1 | Entry | ... | | | | S2 | T | ... | Exit |171 +----------+-------+-----+-----+-----+-----+-----+-----+-----+------+172 | Thread 2 | Entry | ... | | Q2 | R | S1 | | ... | Exit |173 +----------+-------+-----+-----+-----+-----+-----+-----+-----+------+174 | Thread 3 | Entry | ... | P | Q1 | | | | ... | |175 +----------+-------+-----+-----+-----+-----+-----+-----+-----+------+176 177The above table shows partial sequences of dynamic instances from178different threads. Dynamic instances in the same column are assumed179to be converged (i.e., related to each other in the converged-with180relation). The resulting convergence order includes the edges ``P ->181Q2``, ``Q1 -> R``, ``P -> R``, ``P -> T``, etc.182 183*Converged-with* is a transitive symmetric relation over dynamic instances184produced by *different threads* for the *same static instance*.185 186It is impractical to provide any one definition for the *converged-with*187relation, since different environments may wish to relate dynamic instances in188different ways. The fact that *convergence-before* is a strict partial order is189a constraint on the *converged-with* relation. It is trivially satisfied if190different dynamic instances are never converged. Below, we provide a relation191called :ref:`maximal converged-with<convergence-maximal>`, which satisifies192*convergence-before* and is suitable for known targets.193 194.. _convergence-note-convergence:195 196.. note::197 198 1. The convergence-before relation is not199 directly observable. Program transforms are in general free to200 change the order of instructions, even though that obviously201 changes the convergence-before relation.202 203 2. Converged dynamic instances need not be executed at the same204 time or even on the same resource. Converged dynamic instances205 of a convergent operation may appear to do so but that is an206 implementation detail.207 208 3. The fact that ``P`` is convergence-before209 ``Q`` does not automatically imply that ``P`` happens-before210 ``Q`` in a memory model sense.211 212.. _convergence-maximal:213 214Maximal Convergence215-------------------216 217This section defines a constraint that may be used to218produce a *maximal converged-with* relation without violating the219strict *convergence-before* order. This maximal converged-with220relation is reasonable for real targets and is compatible with221convergent operations.222 223The maximal converged-with relation is defined in terms of cycle224headers, with the assumption that threads converge at the header on every225"iteration" of the cycle. Informally, two threads execute the same iteration of226a cycle if they both previously executed the cycle header the same number of227times after they entered that cycle. In general, this needs to account for the228iterations of parent cycles as well.229 230 **Maximal converged-with:**231 232 Dynamic instances ``X1`` and ``X2`` produced by different threads233 for the same static instance ``X`` are converged in the maximal234 converged-with relation if and only if:235 236 - ``X`` is not contained in any cycle, or,237 - For every cycle ``C`` with header ``H`` that contains ``X``:238 239 - every dynamic instance ``H1`` of ``H`` that precedes ``X1`` in240 the respective thread is convergence-before ``X2``, and,241 - every dynamic instance ``H2`` of ``H`` that precedes ``X2`` in242 the respective thread is convergence-before ``X1``,243 - without assuming that ``X1`` is converged with ``X2``.244 245.. note::246 247 Cycle headers may not be unique to a given CFG if it is irreducible. Each248 cycle hierarchy for the same CFG results in a different maximal249 converged-with relation.250 251 For brevity, the rest of the document restricts the term252 *converged* to mean "related under the maximal converged-with253 relation for the given cycle hierarchy".254 255Maximal convergence can now be demonstrated in the earlier example as follows:256 257.. table::258 :align: left259 260 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+261 | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |262 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+263 | Thread 1 | Entry1 | H1 | B1 | L1 | H3 | | L3 | | | | Exit |264 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+265 | Thread 2 | Entry2 | H2 | | L2 | H4 | B2 | L4 | H5 | B3 | L5 | Exit |266 +----------+--------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+267 268- ``Entry1`` and ``Entry2`` are converged.269- ``H1`` and ``H2`` are converged.270- ``B1`` and ``B2`` are not converged due to ``H4`` which is not271 convergence-before ``B1``.272- ``H3`` and ``H4`` are converged.273- ``H3`` is not converged with ``H5`` due to ``H4`` which is not274 convergence-before ``H3``.275- ``L1`` and ``L2`` are converged.276- ``L3`` and ``L4`` are converged.277- ``L3`` is not converged with ``L5`` due to ``H5`` which is not278 convergence-before ``L3``.279 280.. _convergence-cycle-headers:281 282Dependence on Cycles Headers283----------------------------284 285Contradictions in *convergence-before* are possible only between two286nodes that are inside some cycle. The dynamic instances of such nodes287may be interleaved in the same thread, and this interleaving may be288different for different threads. Cycle headers serve as implicit289*points of convergence* in the maximal converged-with relation.290When a thread executes a node ``X`` once and then executes it again,291it must have followed a closed path in the CFG that includes ``X``.292Such a path must pass through the header of at least one cycle --- the293smallest cycle that includes the entire closed path. In a given294thread, two dynamic instances of ``X`` are either separated by the295execution of at least one cycle header, or ``X`` itself is a cycle296header.297 298Consider a sequence of nested cycles ``C1``, ``C2``, ..., ``Ck`` such299that ``C1`` is the outermost cycle and ``Ck`` is the innermost cycle,300with headers ``H1``, ``H2``, ..., ``Hk`` respectively. When a thread301enters the cycle ``Ck``, any of the following is possible:302 3031. The thread directly entered cycle ``Ck`` without having executed304 any of the headers ``H1`` to ``Hk``.305 3062. The thread executed some or all of the nested headers one or more307 times.308 309The maximal converged-with relation captures the following intuition310about cycles:311 3121. When two threads enter a top-level cycle ``C1``, they execute313 converged dynamic instances of every node that is a :ref:`child314 <cycle-parent-block>` of ``C1``.315 3162. When two threads enter a nested cycle ``Ck``, they execute317 converged dynamic instances of every node that is a child of318 ``Ck``, until either thread exits ``Ck``, if and only if they319 executed converged dynamic instances of the last nested header that320 either thread encountered.321 322 Note that when a thread exits a nested cycle ``Ck``, it must follow323 a closed path outside ``Ck`` to reenter it. This requires executing324 the header of some outer cycle, as described earlier.325 326Consider two dynamic instances ``X1`` and ``X2`` produced by threads ``T1``327and ``T2`` for a node ``X`` that is a child of nested cycle ``Ck``.328Maximal convergence relates ``X1`` and ``X2`` as follows:329 3301. If neither thread executed any header from ``H1`` to ``Hk``, then331 ``X1`` and ``X2`` are converged.332 3332. Otherwise, if there are no converged dynamic instances ``Q1`` and334 ``Q2`` of any header ``Q`` from ``H1`` to ``Hk`` (where ``Q`` is335 possibly the same as ``X``), such that ``Q1`` precedes ``X1`` and336 ``Q2`` precedes ``X2`` in the respective threads, then ``X1`` and337 ``X2`` are not converged.338 3393. Otherwise, consider the pair ``Q1`` and ``Q2`` of converged dynamic340 instances of a header ``Q`` from ``H1`` to ``Hk`` that occur most341 recently before ``X1`` and ``X2`` in the respective threads. Then342 ``X1`` and ``X2`` are converged if and only if there is no dynamic343 instance of any header from ``H1`` to ``Hk`` that occurs between344 ``Q1`` and ``X1`` in thread ``T1``, or between ``Q2`` and ``X2`` in345 thread ``T2``. In other words, ``Q1`` and ``Q2`` represent the last346 point of convergence, with no other header being executed before347 executing ``X``.348 349**Example:**350 351.. figure:: convergence-both-diverged-nested.png352 :name: convergence-both-diverged-nested353 354The above figure shows two nested irreducible cycles with headers355``R`` and ``S``. The nodes ``Entry`` and ``Q`` have divergent356branches. The table below shows the convergence between three threads357taking different paths through the CFG. Dynamic instances listed in358the same column are converged.359 360 .. table::361 :align: left362 363 +---------+-------+-----+-----+-----+-----+-----+-----+-----+------+364 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |365 +---------+-------+-----+-----+-----+-----+-----+-----+-----+------+366 | Thread1 | Entry | P1 | Q1 | S1 | P3 | Q3 | R1 | S2 | Exit |367 +---------+-------+-----+-----+-----+-----+-----+-----+-----+------+368 | Thread2 | Entry | P2 | Q2 | | | | R2 | S3 | Exit |369 +---------+-------+-----+-----+-----+-----+-----+-----+-----+------+370 | Thread3 | Entry | | | | | | R3 | S4 | Exit |371 +---------+-------+-----+-----+-----+-----+-----+-----+-----+------+372 373- ``P2`` and ``P3`` are not converged due to ``S1``374- ``Q2`` and ``Q3`` are not converged due to ``S1``375- ``S1`` and ``S3`` are not converged due to ``R2``376- ``S1`` and ``S4`` are not converged due to ``R3``377 378Informally, ``T1`` and ``T2`` execute the inner cycle a different379number of times, without executing the header of the outer cycle. All380threads converge in the outer cycle when they first execute the header381of the outer cycle.382 383.. _convergence-uniformity:384 385Uniformity386==========387 3881. The output of two converged dynamic instances is uniform if and389 only if it compares equal for those two dynamic instances.3902. The output of a static instance ``X`` is uniform *for a given set391 of threads* if and only if it is uniform for every pair of392 converged dynamic instances of ``X`` produced by those threads.393 394A non-uniform value is said to be *divergent*.395 396For a set ``S`` of threads, the uniformity of each output of a static397instance is determined as follows:398 3991. The semantics of the instruction may specify the output to be400 uniform.4012. Otherwise, the output is divergent if the static instance is not402 :ref:`m-converged <convergence-m-converged>`.4033. Otherwise, if the static instance is m-converged:404 405 1. If it is a PHI node, its output is uniform if and only406 if for every pair of converged dynamic instances produced by all407 threads in ``S``:408 409 a. Both instances choose the same output from converged410 dynamic instances, and,411 b. That output is uniform for all threads in ``S``.412 2. Otherwise, the output is uniform if and only if the input413 operands are uniform for all threads in ``S``.414 415Divergent Cycle Exits416---------------------417 418When a divergent branch occurs inside a cycle, it is possible that a419diverged path continues to an exit of the cycle. This is called a420divergent cycle exit. If the cycle is irreducible, the diverged path421may re-enter and eventually reach a join within the cycle. Such a join422should be examined for the :ref:`diverged entry423<convergence-diverged-entry>` criterion.424 425Nodes along the diverged path that lie outside the cycle experience426*temporal divergence*, when two threads executing convergently inside427the cycle produce uniform values, but exit the cycle along the same428divergent path after executing the header a different number of times429(informally, on different iterations of the cycle). For a node ``N``430inside the cycle the outputs may be uniform for the two threads, but431any use ``U`` outside the cycle receives a value from non-converged432dynamic instances of ``N``. An output of ``U`` may be divergent,433depending on the semantics of the instruction.434 435.. _uniformity-analysis:436 437Static Uniformity Analysis438==========================439 440Irreducible control flow results in different cycle hierarchies441depending on the choice of headers during depth-first traversal. As a442result, a static analysis cannot always determine the convergence of443nodes in irreducible cycles, and any uniformity analysis is limited to444those static instances whose convergence is independent of the cycle445hierarchy:446 447.. _convergence-m-converged:448 449 **m-converged static instances:**450 451 A static instance ``X`` is *m-converged* for a given CFG if and only452 if the maximal converged-with relation for its dynamic instances is453 the same in every cycle hierarchy that can be constructed for that CFG.454 455 .. note::456 457 In other words, two dynamic instances ``X1`` and ``X2`` of an458 m-converged static instance ``X`` are converged in some cycle459 hierarchy if and only if they are also converged in every other460 cycle hierarchy for the same CFG.461 462 As noted earlier, for brevity, we restrict the term *converged* to463 mean "related under the maximal converged-with relation for a given464 cycle hierarchy".465 466 467Each node ``X`` in a given CFG is reported to be m-converged if and468only if every cycle that contains ``X`` satisfies the following necessary469conditions:470 471 1. Every divergent branch inside the cycle satisfies the472 :ref:`diverged entry criterion<convergence-diverged-entry>`, and,473 2. There are no :ref:`diverged paths reaching the474 cycle<convergence-diverged-outside>` from a divergent branch475 outside it.476 477.. note::478 479 A reducible cycle :ref:`trivially satisfies480 <convergence-reducible-cycle>` the above conditions. In particular,481 if the whole CFG is reducible, then all nodes in the CFG are482 m-converged.483 484The uniformity of each output of a static instance485is determined using the criteria486:ref:`described earlier <convergence-uniformity>`. The discovery of487divergent outputs may cause their uses (including branches) to also488become divergent. The analysis propagates this divergence until a489fixed point is reached.490 491The convergence inferred using these criteria is a safe subset of the492maximal converged-with relation for any cycle hierarchy. In493particular, it is sufficient to determine if a static instance is494m-converged for a given cycle hierarchy ``T``, even if that fact is495not detected when examining some other cycle hierarchy ``T'``.496 497This property allows compiler transforms to use the uniformity498analysis without being affected by DFS choices made in the underlying499cycle analysis. When two transforms use different instances of the500uniformity analysis for the same CFG, a "divergent value" result in501one analysis instance cannot contradict a "uniform value" result in502the other.503 504Generic transforms such as SimplifyCFG, CSE, and loop transforms505commonly change the program in ways that change the maximal506converged-with relations. This also means that a value that was507previously uniform can become divergent after such a transform.508Uniformity has to be recomputed after such transforms.509 510Divergent Branch inside a Cycle511-------------------------------512 513.. figure:: convergence-divergent-inside.png514 :name: convergence-divergent-inside515 516The above figure shows a divergent branch ``Q`` inside an irreducible517cyclic region. When two threads diverge at ``Q``, the convergence of518dynamic instances within the cyclic region depends on the cycle519hierarchy chosen:520 5211. In an implementation that detects a single cycle ``C`` with header522 ``P``, convergence inside the cycle is determined by ``P``.523 5242. In an implementation that detects two nested cycles with headers525 ``R`` and ``S``, convergence inside those cycles is determined by526 their respective headers.527 528.. _convergence-diverged-entry:529 530A conservative approach would be to simply report all nodes inside531irreducible cycles as having divergent outputs. But it is desirable to532recognize m-converged nodes in the CFG in order to maximize533uniformity. This section describes one such pattern of nodes derived534from *closed paths*, which are a property of the CFG and do not depend535on the cycle hierarchy.536 537 **Diverged Entry Criterion:**538 539 The dynamic instances of all the nodes in a closed path ``P`` are540 m-converged only if for every divergent branch ``B`` and its541 join node ``J`` that lie on ``P``, there is no entry to ``P`` which542 lies on a diverged path from ``B`` to ``J``.543 544.. figure:: convergence-closed-path.png545 :name: convergence-closed-path546 547Consider the closed path ``P -> Q -> R -> S`` in the above figure.548``P`` and ``R`` are :ref:`entries to the closed549path<cycle-closed-path>`. ``Q`` is a divergent branch and ``S`` is a550join for that branch, with diverged paths ``Q -> R -> S`` and ``Q ->551S``.552 553- If a diverged entry ``R`` exists, then in some cycle hierarchy,554 ``R`` is the header of the smallest cycle ``C`` containing the555 closed path and a :ref:`child cycle<cycle-definition>` ``C'``556 exists in the set ``C - R``, containing both branch ``Q`` and join557 ``S``. When threads diverge at ``Q``, one subset ``M`` continues558 inside cycle ``C'``, while the complement ``N`` exits ``C'`` and559 reaches ``R``. Dynamic instances of ``S`` executed by threads in set560 ``M`` are not converged with those executed in set ``N`` due to the561 presence of ``R``. Informally, threads that diverge at ``Q``562 reconverge in the same iteration of the outer cycle ``C``, but they563 may have executed the inner cycle ``C'`` differently.564 565 .. table::566 :align: left567 568 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+569 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |570 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+571 | Thread1 | Entry | P1 | Q1 | | | | R1 | S1 | P3 | ... | Exit |572 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+573 | Thread2 | Entry | P2 | Q2 | S2 | P4 | Q4 | R2 | S4 | | | Exit |574 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+575 576 In the table above, ``S2`` is not converged with ``S1`` due to ``R1``.577 578|579 580- If ``R`` does not exist, or if any node other than ``R`` is the581 header of ``C``, then no such child cycle ``C'`` is detected.582 Threads that diverge at ``Q`` execute converged dynamic instances of583 ``S`` since they do not encounter the cycle header on any path from584 ``Q`` to ``S``. Informally, threads that diverge at ``Q``585 reconverge at ``S`` in the same iteration of ``C``.586 587 .. table::588 :align: left589 590 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+------+591 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |592 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+------+593 | Thread1 | Entry | P1 | Q1 | R1 | S1 | P3 | Q3 | R3 | S3 | Exit |594 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+------+595 | Thread2 | Entry | P2 | Q2 | | S2 | P4 | Q4 | R2 | S4 | Exit |596 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+------+597 598|599 600 .. note::601 602 In general, the cycle ``C`` in the above statements is not603 expected to be the same cycle for different headers. Cycles and604 their headers are tightly coupled; for different headers in the605 same outermost cycle, the child cycles detected may be different.606 The property relevant to the above examples is that for every607 closed path, there is a cycle ``C`` that contains the path and608 whose header is on that path.609 610The diverged entry criterion must be checked for every closed path611passing through a divergent branch ``B`` and its join ``J``. Since612:ref:`every closed path passes through the header of some613cycle<cycle-closed-path-header>`, this amounts to checking every cycle614``C`` that contains ``B`` and ``J``. When the header of ``C``615dominates the join ``J``, there can be no entry to any path from the616header to ``J``, which includes any diverged path from ``B`` to ``J``.617This is also true for any closed paths passing through the header of618an outer cycle that contains ``C``.619 620Thus, the diverged entry criterion can be conservatively simplified621as follows:622 623 For a divergent branch ``B`` and its join node ``J``, the nodes in a624 cycle ``C`` that contains both ``B`` and ``J`` are m-converged only625 if:626 627 - ``B`` strictly dominates ``J``, or,628 - The header ``H`` of ``C`` strictly dominates ``J``, or,629 - Recursively, there is cycle ``C'`` inside ``C`` that satisfies the630 same condition.631 632When ``J`` is the same as ``H`` or ``B``, the trivial dominance is633insufficient to make any statement about entries to diverged paths.634 635.. _convergence-diverged-outside:636 637Diverged Paths reaching a Cycle638-------------------------------639 640.. figure:: convergence-divergent-outside.png641 :name: convergence-divergent-outside642 643The figure shows two cycle hierarchies with a divergent branch in644``Entry`` instead of ``Q``. For two threads that enter the closed path645``P -> Q -> R -> S`` at ``P`` and ``R`` respectively, the convergence646of dynamic instances generated along the path depends on whether ``P``647or ``R`` is the header.648 649- Convergence when ``P`` is the header.650 651 .. table::652 :align: left653 654 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+655 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |656 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+657 | Thread1 | Entry | | | | P1 | Q1 | R1 | S1 | P3 | Q3 | | S3 | Exit |658 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+659 | Thread2 | Entry | | R2 | S2 | P2 | Q2 | | S2 | P4 | Q4 | R3 | S4 | Exit |660 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+661 662 |663 664- Convergence when ``R`` is the header.665 666 .. table::667 :align: left668 669 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+670 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |671 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+672 | Thread1 | Entry | | P1 | Q1 | R1 | S1 | P3 | Q3 | S3 | | | Exit |673 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+674 | Thread2 | Entry | | | | R2 | S2 | P2 | Q2 | S2 | P4 | ... | Exit |675 +---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+------+676 677 |678 679Thus, when diverged paths reach different entries of an irreducible680cycle from outside the cycle, the static analysis conservatively681reports every node in the cycle as not m-converged.682 683.. _convergence-reducible-cycle:684 685Reducible Cycle686---------------687 688If ``C`` is a reducible cycle with header ``H``, then in any DFS,689``H`` :ref:`must be the header of some cycle<cycle-reducible-headers>`690``C'`` that contains ``C``. Independent of the DFS, there is no entry691to the subgraph ``C`` other than ``H`` itself. Thus, we have the692following:693 6941. The diverged entry criterion is trivially satisfied for a divergent695 branch and its join, where both are inside subgraph ``C``.6962. When diverged paths reach the subgraph ``C`` from outside, their697 convergence is always determined by the same header ``H``.698 699Clearly, this can be determined only in a cycle hierarchy ``T`` where700``C`` is detected as a reducible cycle. No such conclusion can be made701in a different cycle hierarchy ``T'`` where ``C`` is part of a larger702cycle ``C'`` with the same header, but this does not contradict the703conclusion in ``T``.704 705Controlled Convergence706======================707 708:ref:`Convergence control tokens <dynamic_instances_and_convergence_tokens>`709provide an explicit semantics for determining which threads are converged at a710given point in the program. The impact of this is incorporated in a711:ref:`controlled maximal converged-with <controlled_maximal_converged_with>`712relation over dynamic instances and a :ref:`controlled m-converged713<controlled_m_converged>` property of static instances. The :ref:`uniformity714analysis <uniformity-analysis>` implemented in LLVM includes this for targets715that support convergence control tokens.716