llvm/docs/CycleTerminology.rst

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