1.. _cycle-terminology: 2 3====================== 4LLVM Cycle Terminology 5====================== 6 7.. contents:: 8 :local: 9 10.. _cycle-definition: 11 12Cycles 13====== 14 15Cycles are a generalization of LLVM :ref:`loops <loop-terminology>`, 16defined recursively as follows [HavlakCycles]_: 17 181. In a directed graph G that is a function CFG or a subgraph of it, a *cycle* 19 is a maximal strongly connected region with at least one internal edge. 20 (Informational note --- The requirement for at least one internal edge 21 ensures that a single basic block is a cycle only if there is an edge 22 that goes back to the same basic block.) 232. A basic block in a cycle that can be reached from the entry of 24 the function along a path that does not visit any other basic block 25 in the cycle is called an *entry* of the cycle. 26 A cycle can have multiple entries. 273. For a given depth-first search starting from the entry of the function, the 28 first node of a cycle to be visited is called the *header* of this cycle 29 with respect to this particular DFS. The header is always an entry node. 304. In any depth-first search starting from the entry, the set of cycles 31 found in the CFG is the same. These are the *top-level cycles* 32 that do not themselves have a parent. 335. The *child cycles* (or simply cycles) nested inside a cycle C with 34 header H are the cycles in the subgraph induced on the set of nodes (C - H). 35 C is said to be the *parent* of these cycles. 36 37Thus, cycles form an implementation-defined forest where each cycle C is 38the parent of any child 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-toplevel-block: 59 60A block B is said to be a *top-level block* if it is not the child of 61any cycle. 62 63.. _cycle-sibling: 64 65A basic block or cycle X is a *sibling* of another basic block or 66cycle Y if they both have no parent or both have the same parent. 67 68Informational notes: 69 70- Non-header entry blocks of a cycle can be contained in child cycles. 71- If the CFG is reducible, the cycles are exactly the natural loops and 72 every cycle has exactly one entry block. 73- Cycles are well-nested (by definition). 74- The entry blocks of a cycle are siblings in the dominator tree. 75 76.. [HavlakCycles] Paul Havlak, "Nesting of reducible and irreducible 77 loops." ACM Transactions on Programming Languages 78 and Systems (TOPLAS) 19.4 (1997): 557-567. 79 80.. _cycle-examples: 81 82Examples of Cycles 83================== 84 85Irreducible cycle enclosing natural loops 86----------------------------------------- 87 88.. Graphviz source; the indented blocks below form a comment. 89 90 /// | | 91 /// />A] [B<\ 92 /// | \ / | 93 /// ^---C---^ 94 /// | 95 96 strict digraph { 97 { rank=same; A B} 98 Entry -> A 99 Entry -> B 100 A -> A 101 A -> C 102 B -> B 103 B -> C 104 C -> A 105 C -> B 106 C -> Exit 107 } 108 109.. image:: cycle-1.png 110 111The self-loops of ``A`` and ``B`` give rise to two single-block 112natural loops. A possible hierarchy of cycles is:: 113 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 117 118This hierarchy arises when DFS visits the blocks in the order ``A``, 119``C``, ``B`` (in preorder). 120 121Irreducible union of two natural loops 122-------------------------------------- 123 124.. Graphviz source; the indented blocks below form a comment. 125 126 /// | | 127 /// A<->B 128 /// ^ ^ 129 /// | | 130 /// v v 131 /// C D 132 /// | | 133 134 strict digraph { 135 { rank=same; A B} 136 { rank=same; C D} 137 Entry -> A 138 Entry -> B 139 A -> B 140 B -> A 141 A -> C 142 C -> A 143 B -> D 144 D -> B 145 C -> Exit 146 D -> Exit 147 } 148 149.. image:: cycle-2.png 150 151There are two natural loops: ``{A, C}`` and ``{B, D}``. A possible 152hierarchy of cycles is:: 153 154 cycle: {A, B, C, D} entries: {A, B} header: A 155 - cycle: {B, D} entries: {B} header: B 156 157Irreducible cycle without natural loops 158--------------------------------------- 159 160.. Graphviz source; the indented blocks below form a comment. 161 162 /// | | 163 /// />A B<\ 164 /// | |\ /| | 165 /// | | x | | 166 /// | |/ \| | 167 /// ^-C D-^ 168 /// | | 169 /// 170 171 strict digraph { 172 { rank=same; A B} 173 { rank=same; C D} 174 Entry -> A 175 Entry -> B 176 A -> C 177 A -> D 178 B -> C 179 B -> D 180 C -> A 181 D -> B 182 C -> Exit 183 D -> Exit 184 } 185 186.. image:: cycle-3.png 187 188This graph does not contain any natural loops --- the nodes ``A``, 189``B``, ``C`` and ``D`` are siblings in the dominator tree. A possible 190hierarchy of cycles is:: 191 192 cycle: {A, B, C, D} entries: {A, B} header: A 193 - cycle: {B, D} entries: {B, D} header: D 194 195.. _cycle-closed-path: 196 197Closed Paths and Cycles 198======================= 199 200A *closed path* in a CFG is a connected sequence of nodes and edges in 201the CFG whose start and end nodes are the same, and whose remaining 202(inner) nodes are distinct. 203 204An *entry* to a closed path ``P`` is a node on ``P`` that is reachable 205from the function entry without passing through any other node on ``P``. 206 2071. If a node D dominates one or more nodes in a closed path P and P 208 does not contain D, then D dominates every node in P. 209 210 **Proof:** Let U be a node in P that is dominated by D. If there 211 was a node V in P not dominated by D, then U would be reachable 212 from the function entry node via V without passing through D, which 213 contradicts the fact that D dominates U. 214 2152. If a node D dominates one or more nodes in a closed path P and P 216 does not contain D, then there exists a cycle C that contains P but 217 not D. 218 219 **Proof:** From the above property, D dominates all the nodes in P. 220 For any nesting of cycles discovered by the implementation-defined 221 DFS, consider the smallest cycle C which contains P. For the sake 222 of contradiction, assume that D is in C. Then the header H of C 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 226 contradicts how we chose C. 227 2283. If a closed path P contains nodes U1 and U2 but not their 229 dominators D1 and D2 respectively, then there exists a cycle C that 230 contains U1 and U2 but neither of D1 and D2. 231 232 **Proof:** From the above properties, each D1 and D2 separately 233 dominate every node in P. There exists a cycle C1 (respectively, 234 C2) that contains P but not D1 (respectively, D2). Either C1 and C2 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 237 of D1 and D2. 238 239.. _cycle-closed-path-header: 240 2414. In any cycle hierarchy, the header ``H`` of the smallest cycle 242 ``C`` containing a closed path ``P`` itself lies on ``P``. 243 244 **Proof:** If ``H`` is not in ``P``, then there is a smaller cycle 245 ``C'`` in the set ``C - H`` containing ``P``, thus contradicting 246 the claim that ``C`` is the smallest such cycle. 247 248.. _cycle-reducible-headers: 249 250Reducible Cycle Headers 251======================= 252 253Although the cycle hierarchy depends on the DFS chosen, reducible 254cycles satisfy the following invariant: 255 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 258 ``H``, that contains ``C``. 259 260**Proof:** For a closed path ``P`` in ``C`` that passes through ``H``, 261every cycle hierarchy has a smallest cycle ``C'`` containing ``P`` and 262whose header is in ``P``. Since ``H`` is the only entry to ``P``, 263``H`` must be the header of ``C'``. Since headers uniquely define 264cycles, ``C'`` contains every such closed path ``P``, and hence ``C'`` 265contains ``C``. 266
