From d0bfebda5b789621dd97b5dca0bd2082a82e82d9 Mon Sep 17 00:00:00 2001 From: Jannik Silvanus Date: Mon, 1 Aug 2022 11:46:02 +0200 Subject: [PATCH] [Docs] Improve cycle and closed path definitions Improve the cycle definition, by avoiding usage of not yet defined or only vaguely defined terminology inside definitions. More precisely, the existing definition defined "outermost cycles", and then proceeded to use the term "cycles" for further definitions, which in turn were used to actually define "cycles". Now, instead only define "cycles". This does not change the meaning of a cycle, which depends on the chosen surrounding (subgraph) of a CFG. Also mention the function CFG in the first definition, because later later definitions require it anyways. Also slightly improve the definition of a closed path, by explicitly requiring the inner nodes to be distinct. Differential Revision: https://reviews.llvm.org/D130891 --- llvm/docs/CycleTerminology.rst | 41 ++++++++++++++++---------------- llvm/include/llvm/ADT/GenericCycleInfo.h | 2 +- 2 files changed, 21 insertions(+), 22 deletions(-) diff --git a/llvm/docs/CycleTerminology.rst b/llvm/docs/CycleTerminology.rst index 3d7c397..1c11107 100644 --- a/llvm/docs/CycleTerminology.rst +++ b/llvm/docs/CycleTerminology.rst @@ -13,29 +13,27 @@ Cycles Cycles are a generalization of LLVM :ref:`loops `, defined recursively as follows [HavlakCycles]_: -1. In a directed graph G, an *outermost 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 the cycle that can be reached from the entry of +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. In any depth-first search starting from the entry of the function, - the first node of a cycle to be visited will be one of the entries. - This entry is called the *header* of the cycle. (Informational note - --- Thus, the header of the cycle is implementation-defined.) -4. In any depth-first search starting from the entry, set of outermost - cycles found in the CFG is the same. These are the *top-level - cycles* that do not themselves have a parent. -5. The cycles nested inside a cycle C with header H are the outermost - cycles in the subgraph induced on the set of nodes (C - H). C is - said to be the *parent* of these cycles, and each of these cycles - is a *child* of C. + 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 *parent* of these cycles. Thus, cycles form an implementation-defined forest where each cycle C is -the parent of any outermost cycles nested inside C. The tree closely +the parent of any child cycles nested inside C. The tree closely follows the nesting of loops in the same function. The unique entry of a reducible cycle (an LLVM loop) L dominates all its other nodes, and is always chosen as the header of some cycle C regardless of the DFS @@ -193,7 +191,8 @@ Closed Paths and Cycles ======================= A *closed path* in a CFG is a connected sequence of nodes and edges in -the CFG whose start and end points are the same. +the CFG whose start and end nodes are the same, and whose remaining +(inner) nodes are distinct. 1. If a node D dominates one or more nodes in a closed path P and P does not contain D, then D dominates every node in P. diff --git a/llvm/include/llvm/ADT/GenericCycleInfo.h b/llvm/include/llvm/ADT/GenericCycleInfo.h index 970664b..9fbcb55 100644 --- a/llvm/include/llvm/ADT/GenericCycleInfo.h +++ b/llvm/include/llvm/ADT/GenericCycleInfo.h @@ -235,7 +235,7 @@ private: /// Map basic blocks to their inner-most containing loop. DenseMap BlockMap; - /// Outermost cycles discovered by any DFS. + /// Top-level cycles discovered by any DFS. /// /// Note: The implementation treats the nullptr as the parent of /// every top-level cycle. See \ref contains for an example. -- 2.7.4