266 lines · plain
1.. _cycle-terminology:2 3======================4LLVM Cycle Terminology5======================6 7.. contents::8 :local:9 10.. _cycle-definition:11 12Cycles13======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 edge21 ensures that a single basic block is a cycle only if there is an edge22 that goes back to the same basic block.)232. A basic block in a cycle that can be reached from the entry of24 the function along a path that does not visit any other basic block25 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, the28 first node of a cycle to be visited is called the *header* of this cycle29 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 cycles31 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 with34 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 is38the parent of any child cycles nested inside C. The tree closely39follows the nesting of loops in the same function. The unique entry of40a reducible cycle (an LLVM loop) L dominates all its other nodes, and41is always chosen as the header of some cycle C regardless of the DFS42tree used. This cycle C is a superset of the loop L. For an43irreducible cycle, no one entry dominates the nodes of the cycle. One44of the entries is chosen as header of the cycle, in an45implementation-defined way.46 47.. _cycle-irreducible:48 49A cycle is *irreducible* if it has multiple entries and it is50*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 in55C 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 of61any cycle.62 63.. _cycle-sibling:64 65A basic block or cycle X is a *sibling* of another basic block or66cycle 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 and72 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 irreducible77 loops." ACM Transactions on Programming Languages78 and Systems (TOPLAS) 19.4 (1997): 557-567.79 80.. _cycle-examples:81 82Examples of Cycles83==================84 85Irreducible cycle enclosing natural loops86-----------------------------------------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 -> A99 Entry -> B100 A -> A101 A -> C102 B -> B103 B -> C104 C -> A105 C -> B106 C -> Exit107 }108 109.. image:: cycle-1.png110 111The self-loops of ``A`` and ``B`` give rise to two single-block112natural loops. A possible hierarchy of cycles is::113 114 cycle: {A, B, C} entries: {A, B} header: A115 - cycle: {B, C} entries: {B, C} header: C116 - cycle: {B} entries: {B} header: B117 118This hierarchy arises when DFS visits the blocks in the order ``A``,119``C``, ``B`` (in preorder).120 121Irreducible union of two natural loops122--------------------------------------123 124.. Graphviz source; the indented blocks below form a comment.125 126 /// | |127 /// A<->B128 /// ^ ^129 /// | |130 /// v v131 /// C D132 /// | |133 134 strict digraph {135 { rank=same; A B}136 { rank=same; C D}137 Entry -> A138 Entry -> B139 A -> B140 B -> A141 A -> C142 C -> A143 B -> D144 D -> B145 C -> Exit146 D -> Exit147 }148 149.. image:: cycle-2.png150 151There are two natural loops: ``{A, C}`` and ``{B, D}``. A possible152hierarchy of cycles is::153 154 cycle: {A, B, C, D} entries: {A, B} header: A155 - cycle: {B, D} entries: {B} header: B156 157Irreducible cycle without natural loops158---------------------------------------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 -> A175 Entry -> B176 A -> C177 A -> D178 B -> C179 B -> D180 C -> A181 D -> B182 C -> Exit183 D -> Exit184 }185 186.. image:: cycle-3.png187 188This graph does not contain any natural loops --- the nodes ``A``,189``B``, ``C`` and ``D`` are siblings in the dominator tree. A possible190hierarchy of cycles is::191 192 cycle: {A, B, C, D} entries: {A, B} header: A193 - cycle: {B, D} entries: {B, D} header: D194 195.. _cycle-closed-path:196 197Closed Paths and Cycles198=======================199 200A *closed path* in a CFG is a connected sequence of nodes and edges in201the CFG whose start and end nodes are the same, and whose remaining202(inner) nodes are distinct.203 204An *entry* to a closed path ``P`` is a node on ``P`` that is reachable205from 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 P208 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 there211 was a node V in P not dominated by D, then U would be reachable212 from the function entry node via V without passing through D, which213 contradicts the fact that D dominates U.214 2152. If a node D dominates one or more nodes in a closed path P and P216 does not contain D, then there exists a cycle C that contains P but217 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-defined221 DFS, consider the smallest cycle C which contains P. For the sake222 of contradiction, assume that D is in C. Then the header H of C223 cannot be in P, since the header of a cycle cannot be dominated by224 any other node in the cycle. Thus, P is in the set (C-H), and there225 must be a smaller cycle C' in C which also contains P, but that226 contradicts how we chose C.227 2283. If a closed path P contains nodes U1 and U2 but not their229 dominators D1 and D2 respectively, then there exists a cycle C that230 contains U1 and U2 but neither of D1 and D2.231 232 **Proof:** From the above properties, each D1 and D2 separately233 dominate every node in P. There exists a cycle C1 (respectively,234 C2) that contains P but not D1 (respectively, D2). Either C1 and C2235 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 neither237 of D1 and D2.238 239.. _cycle-closed-path-header:240 2414. In any cycle hierarchy, the header ``H`` of the smallest cycle242 ``C`` containing a closed path ``P`` itself lies on ``P``.243 244 **Proof:** If ``H`` is not in ``P``, then there is a smaller cycle245 ``C'`` in the set ``C - H`` containing ``P``, thus contradicting246 the claim that ``C`` is the smallest such cycle.247 248.. _cycle-reducible-headers:249 250Reducible Cycle Headers251=======================252 253Although the cycle hierarchy depends on the DFS chosen, reducible254cycles satisfy the following invariant:255 256 If a reducible cycle ``C`` with header ``H`` is discovered in any257 DFS, then there exists a cycle ``C'`` in every DFS with header258 ``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`` and262whose header is in ``P``. Since ``H`` is the only entry to ``P``,263``H`` must be the header of ``C'``. Since headers uniquely define264cycles, ``C'`` contains every such closed path ``P``, and hence ``C'``265contains ``C``.266