Lines Matching refs:cycle

18 1. In a directed graph G that is a function CFG or a subgraph of it, a *cycle*
21    ensures that a single basic block is a cycle only if there is an edge
23 2. A basic block in a cycle that can be reached from the entry of
25    in the cycle is called an *entry* of the cycle.
26    A cycle can have multiple entries.
28    first node of a cycle to be visited is called the *header* of this cycle
33 5. The *child cycles* (or simply cycles) nested inside a cycle C with
37 Thus, cycles form an implementation-defined forest where each cycle C is
40 a reducible cycle (an LLVM loop) L dominates all its other nodes, and
41 is always chosen as the header of some cycle C regardless of the DFS
42 tree used. This cycle C is a superset of the loop L. For an
43 irreducible cycle, no one entry dominates the nodes of the cycle. One
44 of the entries is chosen as header of the cycle, in an
49 A cycle is *irreducible* if it has multiple entries and it is
54 A cycle C is said to be the *parent* of a basic block B if B occurs in
55 C but not in any child cycle of C. Then B is also said to be a *child*
56 of cycle C.
61 any cycle.
65 A basic block or cycle X is a *sibling* of another basic block or
66 cycle Y if they both have no parent or both have the same parent.
70 - Non-header entry blocks of a cycle can be contained in child cycles.
72   every cycle has exactly one entry block.
74 - The entry blocks of a cycle are siblings in the dominator tree.
85 Irreducible cycle enclosing natural loops
109 .. image:: cycle-1.png
114     cycle: {A, B, C} entries: {A, B} header: A
115     - cycle: {B, C}  entries: {B, C} header: C
116       - cycle: {B}   entries: {B}    header: B
149 .. image:: cycle-2.png
154     cycle: {A, B, C, D} entries: {A, B} header: A
155     - cycle: {B, D}     entries: {B}    header: B
157 Irreducible cycle without natural loops
186 .. image:: cycle-3.png
192     cycle: {A, B, C, D} entries: {A, B} header: A
193     - cycle: {B, D}     entries: {B, D} header: D
216    does not contain D, then there exists a cycle C that contains P but
221    DFS, consider the smallest cycle C which contains P. For the sake
223    cannot be in P, since the header of a cycle cannot be dominated by
224    any other node in the cycle. Thus, P is in the set (C-H), and there
225    must be a smaller cycle C' in C which also contains P, but that
229    dominators D1 and D2 respectively, then there exists a cycle C that
233    dominate every node in P. There exists a cycle C1 (respectively,
235    are the same cycle, or one of them is nested inside the other.
236    Hence there is always a cycle that contains U1 and U2 but neither
241 4. In any cycle hierarchy, the header ``H`` of the smallest cycle
244    **Proof:** If ``H`` is not in ``P``, then there is a smaller cycle
246    the claim that ``C`` is the smallest such cycle.
253 Although the cycle hierarchy depends on the DFS chosen, reducible
256   If a reducible cycle ``C`` with header ``H`` is discovered in any
257   DFS, then there exists a cycle ``C'`` in every DFS with header
261 every cycle hierarchy has a smallest cycle ``C'`` containing ``P`` and