LLVM Cycle Terminology#

Cycles#

Cycles are a generalization of LLVM loops, defined recursively as follows [HavlakCycles]:

  1. In a directed graph G that is a function CFG or a subgraph of it, a cycle is a maximal strongly connected region with at least one internal edge. (Informational note — The requirement for at least one internal edge ensures that a single basic block is a cycle only if there is an edge that goes back to the same basic block.)

  2. A basic block in a cycle that can be reached from the entry of the function along a path that does not visit any other basic block in the cycle is called an entry of the cycle. A cycle can have multiple entries.

  3. For a given depth-first search starting from the entry of the function, the first node of a cycle to be visited is called the header of this cycle with respect to this particular DFS. The header is always an entry node.

  4. In any depth-first search starting from the entry, the set of cycles found in the CFG is the same. These are the top-level cycles that do not themselves have a parent.

  5. The child cycles (or simply cycles) nested inside a cycle C with header H are the cycles in the subgraph induced on the set of nodes (C - H). C is said to be the