llvm/docs/CycleTerminology.rst

   1 .. _cycle-terminology:
   2
   3 ======================
   4 LLVM Cycle Terminology
   5 ======================
   6
   7 .. contents::
   8    :local:
   9
  10 .. _cycle-definition:
  11
  12 Cycles
  13 ======
  14
  15 Cycles are a generalization of LLVM :ref:`loops <loop-terminology>`,
  16 defined recursively as follows [HavlakCycles]_:
  17
  18 1. 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.)
  23 2. 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.
  27 3. 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.
  30 4. 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.
  33 5. 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
  37 Thus, cycles form an implementation-defined forest where each cycle C is
  38 the parent of any child cycles nested inside C. The tree closely
  39 follows the nesting of loops in the same function. The unique entry of
  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
  45 implementation-defined way.
  46
  47 .. _cycle-irreducible:
  48
  49 A cycle is *irreducible* if it has multiple entries and it is
  50 *reducible* otherwise.
  51
  52 .. _cycle-parent-block:
  53
  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.
  57
  58 .. _cycle-toplevel-block:
  59
  60 A block B is said to be a *top-level block* if it is not the child of
  61 any cycle.
  62
  63 .. _cycle-sibling:
  64
  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.
  67
  68 Informational 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
  82 Examples of Cycles
  83 ==================
  84
  85 Irreducible 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
 111 The self-loops of ``A`` and ``B`` give rise to two single-block
 112 natural 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
 118 This hierarchy arises when DFS visits the blocks in the order ``A``,
 119 ``C``, ``B`` (in preorder).
 120
 121 Irreducible 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
 151 There are two natural loops: ``{A, C}`` and ``{B, D}``. A possible
 152 hierarchy of cycles is::
 153
 154     cycle: {A, B, C, D} entries: {A, B} header: A
 155     - cycle: {B, D}     entries: {B}    header: B
 156
 157 Irreducible 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
 188 This graph does not contain any natural loops --- the nodes ``A``,
 189 ``B``, ``C`` and ``D`` are siblings in the dominator tree. A possible
 190 hierarchy 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
 197 Closed Paths and Cycles
 198 =======================
 199
 200 A *closed path* in a CFG is a connected sequence of nodes and edges in
 201 the CFG whose start and end nodes are the same, and whose remaining
 202 (inner) nodes are distinct.
 203
 204 An *entry* to a closed path ``P`` is a node on ``P`` that is reachable
 205 from the function entry without passing through any other node on ``P``.
 206
 207 1. 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
 215 2. 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
 228 3. 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
 241 4. 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
 250 Reducible Cycle Headers
 251 =======================
 252
 253 Although the cycle hierarchy depends on the DFS chosen, reducible
 254 cycles 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``,
 261 every cycle hierarchy has a smallest cycle ``C'`` containing ``P`` and
 262 whose header is in ``P``. Since ``H`` is the only entry to ``P``,
 263 ``H`` must be the header of ``C'``. Since headers uniquely define
 264 cycles, ``C'`` contains every such closed path ``P``, and hence ``C'``
 265 contains ``C``.