Lines Matching refs:cycle
84 Described in :ref:`cycle-terminology`.
87 Described in :ref:`cycle-closed-path`.
223 The maximal converged-with relation is defined in terms of cycle
225 "iteration" of the cycle. Informally, two threads execute the same iteration of
226 a cycle if they both previously executed the cycle header the same number of
227 times after they entered that cycle. In general, this needs to account for the
236 - ``X`` is not contained in any cycle, or,
237 - For every cycle ``C`` with header ``H`` that contains ``X``:
248 cycle hierarchy for the same CFG results in a different maximal
253 relation for the given cycle hierarchy".
280 .. _convergence-cycle-headers:
286 nodes that are inside some cycle. The dynamic instances of such nodes
292 Such a path must pass through the header of at least one cycle --- the
293 smallest cycle that includes the entire closed path. In a given
295 execution of at least one cycle header, or ``X`` itself is a cycle
299 equivalent to the start of a new iteration of the cycle. But this
302 work<convergence-note-convergence>`. Instead, cycle headers should be
307 that ``C1`` is the outermost cycle and ``Ck`` is the innermost cycle,
309 enters the cycle ``Ck``, any of the following is possible:
311 1. The thread directly entered cycle ``Ck`` without having executed
320 1. When two threads enter a top-level cycle ``C1``, they execute
322 <cycle-parent-block>` of ``C1``.
324 2. When two threads enter a nested cycle ``Ck``, they execute
330 Note that when a thread exits a nested cycle ``Ck``, it must follow
332 the header of some outer cycle, as described earlier.
335 and ``T2`` for a node ``X`` that is a child of nested cycle ``Ck``.
386 Informally, ``T1`` and ``T2`` execute the inner cycle a different
387 number of times, without executing the header of the outer cycle. All
388 threads converge in the outer cycle when they first execute the header
389 of the outer cycle.
426 When a divergent branch occurs inside a cycle, it is possible that a
427 diverged path continues to an exit of the cycle. This is called a
428 divergent cycle exit. If the cycle is irreducible, the diverged path
429 may re-enter and eventually reach a join within the cycle. Such a join
433 Nodes along the diverged path that lie outside the cycle experience
435 the cycle produce uniform values, but exit the cycle along the same
437 (informally, on different iterations of the cycle). For a node ``N``
438 inside the cycle the outputs may be uniform for the two threads, but
439 any use ``U`` outside the cycle receives a value from non-converged
448 Irreducible control flow results in different cycle hierarchies
452 those static instances whose convergence is independent of the cycle
461 the same in every cycle hierarchy that can be constructed for that CFG.
466 m-converged static instance ``X`` are converged in some cycle
468 cycle hierarchy for the same CFG.
472 cycle hierarchy".
476 only if every cycle that contains ``X`` satisfies the following necessary
479 1. Every divergent branch inside the cycle satisfies the
482 cycle<convergence-diverged-outside>` from a divergent branch
487 A reducible cycle :ref:`trivially satisfies
488 <convergence-reducible-cycle>` the above conditions. In particular,
500 maximal converged-with relation for any cycle hierarchy. In
502 m-converged for a given cycle hierarchy ``T``, even if that fact is
503 not detected when examining some other cycle hierarchy ``T'``.
507 cycle analysis. When two transforms use different instances of the
526 dynamic instances within the cyclic region depends on the cycle
529 1. In an implementation that detects a single cycle ``C`` with header
530 ``P``, convergence inside the cycle is determined by ``P``.
543 on the cycle hierarchy.
557 path<cycle-closed-path>`. ``Q`` is a divergent branch and ``S`` is a
561 - If a diverged entry ``R`` exists, then in some cycle hierarchy,
562 ``R`` is the header of the smallest cycle ``C`` containing the
563 closed path and a :ref:`child cycle<cycle-definition>` ``C'``
566 inside cycle ``C'``, while the complement ``N`` exits ``C'`` and
570 reconverge in the same iteration of the outer cycle ``C``, but they
571 may have executed the inner cycle ``C'`` differently.
589 header of ``C``, then no such child cycle ``C'`` is detected.
591 ``S`` since they do not encounter the cycle header on any path from
610 In general, the cycle ``C`` in the above statements is not
611 expected to be the same cycle for different headers. Cycles and
613 same outermost cycle, the child cycles detected may be different.
615 closed path, there is a cycle ``C`` that contains the path and
621 cycle<cycle-closed-path-header>`, this amounts to checking every cycle
626 an outer cycle that contains ``C``.
632 cycle ``C`` that contains both ``B`` and ``J`` are m-converged only
637 - Recursively, there is cycle ``C'`` inside ``C`` that satisfies the
651 The figure shows two cycle hierarchies with a divergent branch in
688 cycle from outside the cycle, the static analysis conservatively
689 reports every node in the cycle as not m-converged.
691 .. _convergence-reducible-cycle:
696 If ``C`` is a reducible cycle with header ``H``, then in any DFS,
697 ``H`` :ref:`must be the header of some cycle<cycle-reducible-headers>`
707 Clearly, this can be determined only in a cycle hierarchy ``T`` where
708 ``C`` is detected as a reducible cycle. No such conclusion can be made
709 in a different cycle hierarchy ``T'`` where ``C`` is part of a larger
710 cycle ``C'`` with the same header, but this does not contradict the