From b2b242f8ba7fde98c070803c808d32c9e4e0f2de Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Wed, 31 Jul 2019 16:24:20 +0000 Subject: [PATCH] [docs] Reword documentation in terms of SCCs not cycles Given the example: header: br i1 %c, label %next, label %header next: br i1 %c2, label %exit, label %header We end up with a loop containing both header and next. Given that, the describing the loop in terms of cycles is confusing since we have multiple distinct cycles within a single Loop. Standardize on the SCC to clarify. Differential Revision: https://reviews.llvm.org/D65299 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@367440 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LoopTerminology.rst | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/docs/LoopTerminology.rst b/docs/LoopTerminology.rst index 1e741e673ff..9229a24820e 100644 --- a/docs/LoopTerminology.rst +++ b/docs/LoopTerminology.rst @@ -12,18 +12,25 @@ Loops are a core concept in any optimizer. This page spells out some of the common terminology used within LLVM code to describe loop structures. -First, let's start with the basics. In LLVM, a Loop is a cycle within -the control flow graph (CFG) where there exists one block (the loop -header block) which dominates all other blocks within the cycle. +First, let's start with the basics. In LLVM, a Loop is a set of basic +blocks that form a strongly connected component (SCC) in the Control +Flow Graph (CFG) where there exists a dedicated entry/header block that +dominates all other blocks within the loop. Thus, without leaving the +loop, one can reach every block in the loop from the header block and +the header block from every block in the loop. Note that there are some important implications of this definition: -* Not all cycles are loops. There exist cycles that do not meet the +* Not all SCCs are loops. There exist SCCs that do not meet the dominance requirement and such are not considered loops. -* Loops can contain non-loop cycles and non-loop cycles may contain +* Loops can contain non-loop SCCs and non-loop SCCs may contain loops. Loops may also contain sub-loops. +* A header block is uniquely associated with one loop. There can be + multiple SCC within that loop, but the strongly connected component + (SCC) formed from their union must always be unique. + * Given the use of dominance in the definition, all loops are statically reachable from the entry of the function. @@ -51,9 +58,9 @@ of the other. Exiting Block - A basic block contained within a given loop which has at least one successor outside of the loop and one successor inside the -loop. (The latter is required for the block to be contained within the -cycle which makes up the loop.) That is, it has a successor which is -an Exit Block. +loop. (The latter is a consequence of the block being contained within +an SCC which is part of the loop.) That is, it has a successor which +is an Exit Block. Exit Block - A basic block outside of the associated loop which has a predecessor inside the loop. That is, it has a predecessor which is -- 2.49.0