1.. _cycle-terminology:
2
3======================
4LLVM Cycle Terminology
5======================
6
7.. contents::
8   :local:
9
10Cycles
11======
12
13Cycles are a generalization of LLVM :ref:`loops <loop-terminology>`,
14defined recursively as follows [HavlakCycles]_:
15
161. In a directed graph G, an *outermost cycle* is a maximal strongly
17   connected region with at least one internal edge. (Informational
18   note --- The requirement for at least one internal edge ensures
19   that a single basic block is a cycle only if there is an edge that
20   goes back to the same basic block.)
212. A basic block in the cycle that can be reached from the entry of
22   the function along a path that does not visit any other basic block
23   in the cycle is called an *entry* of the cycle. A cycle can have
24   multiple entries.
253. In any depth-first search starting from the entry of the function,
26   the first node of a cycle to be visited will be one of the entries.
27   This entry is called the *header* of the cycle. (Informational note
28   --- Thus, the header of the cycle is implementation-defined.)
294. In any depth-first search starting from the entry, set of outermost
30   cycles found in the CFG is the same. These are the *top-level
31   cycles* that do not themselves have a parent.
325. The cycles nested inside a cycle C with header H are the outermost
33   cycles in the subgraph induced on the set of nodes (C - H). C is
34   said to be the *parent* of these cycles, and each of these cycles
35   is a *child* of C.
36
37Thus, cycles form an implementation-defined forest where each cycle C is
38the parent of any outermost cycles nested inside C. The tree closely
39follows the nesting of loops in the same function. The unique entry of
40a reducible cycle (an LLVM loop) L dominates all its other nodes, and
41is always chosen as the header of some cycle C regardless of the DFS
42tree used. This cycle C is a superset of the loop L. For an
43irreducible cycle, no one entry dominates the nodes of the cycle. One
44of the entries is chosen as header of the cycle, in an
45implementation-defined way.
46
47.. _cycle-irreducible:
48
49A cycle is *irreducible* if it has multiple entries and it is
50*reducible* otherwise.
51
52.. _cycle-parent-block:
53
54A cycle C is said to be the *parent* of a basic block B if B occurs in
55C but not in any child cycle of C. Then B is also said to be a *child*
56of cycle C.
57
58.. _cycle-sibling:
59
60A basic block or cycle X is a *sibling* of another basic block or
61cycle Y if they both have no parent or both have the same parent.
62
63Informational notes:
64
65- Non-header entry blocks of a cycle can be contained in child cycles.
66- If the CFG is reducible, the cycles are exactly the natural loops and
67  every cycle has exactly one entry block.
68- Cycles are well-nested (by definition).
69- The entry blocks of a cycle are siblings in the dominator tree.
70
71.. [HavlakCycles] Paul Havlak, "Nesting of reducible and irreducible
72                  loops." ACM Transactions on Programming Languages
73                  and Systems (TOPLAS) 19.4 (1997): 557-567.
74
75.. _cycle-examples:
76
77Examples of Cycles
78==================
79
80Irreducible cycle enclosing natural loops
81-----------------------------------------
82
83.. Graphviz source; the indented blocks below form a comment.
84
85  ///     |   |
86  ///   />A] [B<\
87  ///   |  \ /  |
88  ///   ^---C---^
89  ///       |
90
91  strict digraph {
92    { rank=same; A B}
93    Entry -> A
94    Entry -> B
95    A -> A
96    A -> C
97    B -> B
98    B -> C
99    C -> A
100    C -> B
101    C -> Exit
102  }
103
104.. image:: cycle-1.png
105
106The self-loops of ``A`` and ``B`` give rise to two single-block
107natural loops. A possible hierarchy of cycles is::
108
109    cycle: {A, B, C} entries: {A, B} header: A
110    - cycle: {B, C}  entries: {B, C} header: C
111      - cycle: {B}   entries: {B}    header: B
112
113This hierarchy arises when DFS visits the blocks in the order ``A``,
114``C``, ``B`` (in preorder).
115
116Irreducible union of two natural loops
117--------------------------------------
118
119.. Graphviz source; the indented blocks below form a comment.
120
121  ///     |   |
122  ///     A<->B
123  ///     ^   ^
124  ///     |   |
125  ///     v   v
126  ///     C   D
127  ///     |   |
128
129  strict digraph {
130    { rank=same; A B}
131    { rank=same; C D}
132    Entry -> A
133    Entry -> B
134    A -> B
135    B -> A
136    A -> C
137    C -> A
138    B -> D
139    D -> B
140    C -> Exit
141    D -> Exit
142  }
143
144.. image:: cycle-2.png
145
146There are two natural loops: ``{A, C}`` and ``{B, D}``. A possible
147hierarchy of cycles is::
148
149    cycle: {A, B, C, D} entries: {A, B} header: A
150    - cycle: {B, D}     entries: {B}    header: B
151
152Irreducible cycle without natural loops
153---------------------------------------
154
155.. Graphviz source; the indented blocks below form a comment.
156
157  ///     |   |
158  ///   />A   B<\
159  ///   | |\ /| |
160  ///   | | x | |
161  ///   | |/ \| |
162  ///   ^-C   D-^
163  ///     |   |
164  ///
165
166  strict digraph {
167    { rank=same; A B}
168    { rank=same; C D}
169    Entry -> A
170    Entry -> B
171    A -> C
172    A -> D
173    B -> C
174    B -> D
175    C -> A
176    D -> B
177    C -> Exit
178    D -> Exit
179  }
180
181.. image:: cycle-3.png
182
183This graph does not contain any natural loops --- the nodes ``A``,
184``B``, ``C`` and ``D`` are siblings in the dominator tree. A possible
185hierarchy of cycles is::
186
187    cycle: {A, B, C, D} entries: {A, B} header: A
188    - cycle: {B, D}     entries: {B, D} header: D
189
190.. _cycle-closed-path:
191
192Closed Paths and Cycles
193=======================
194
195A *closed path* in a CFG is a connected sequence of nodes and edges in
196the CFG whose start and end points are the same.
197
1981. If a node D dominates one or more nodes in a closed path P and P
199   does not contain D, then D dominates every node in P.
200
201   **Proof:** Let U be a node in P that is dominated by D. If there
202   was a node V in P not dominated by D, then U would be reachable
203   from the function entry node via V without passing through D, which
204   contradicts the fact that D dominates U.
205
2062. If a node D dominates one or more nodes in a closed path P and P
207   does not contain D, then there exists a cycle C that contains P but
208   not D.
209
210   **Proof:** From the above property, D dominates all the nodes in P.
211   For any nesting of cycles discovered by the implementation-defined
212   DFS, consider the smallest cycle C which contains P. For the sake
213   of contradiction, assume that D is in C. Then the header H of C
214   cannot be in P, since the header of a cycle cannot be dominated by
215   any other node in the cycle. Thus, P is in the set (C-H), and there
216   must be a smaller cycle C' in C which also contains P, but that
217   contradicts how we chose C.
218
2193. If a closed path P contains nodes U1 and U2 but not their
220   dominators D1 and D2 respectively, then there exists a cycle C that
221   contains U1 and U2 but neither of D1 and D2.
222
223   **Proof:** From the above properties, each D1 and D2 separately
224   dominate every node in P. There exists a cycle C1 (respectively,
225   C2) that contains P but not D1 (respectively, D2). Either C1 and C2
226   are the same cycle, or one of them is nested inside the other.
227   Hence there is always a cycle that contains U1 and U2 but neither
228   of D1 and D2.
229