Try to clarify loop definition around confusing sub-loop case

[reames]

Summary

As pointed out by reviewers, my own mental model here was wrong. So, let's try revising the definition to make that more clear.

[jdoerfert]

docs/LoopTerminology.rst

17 ↗

(On Diff #211817)

a loop is a set of basic blocks (= nodes in the control flow graph (CFG)) that form a strongly connected component (SCC). In addition, each loop has 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.

(It's not a single cycle.)

31 ↗

(On Diff #211817)

A sub-loop is sth. different. A loop can be made up of multiple cycles without having sub-loops.
There is no need for a "largest" cycle. Take

h: if (...) goto a; else goto b;
a: if (...) goto h; else goto end;
b: if (...) goto h; else goto end;

two cycles: h -> a -> h and h -> b -> h, neither containing the other one.

[reames]

I think I've reformulated this to incorporate the review comments, let me know what you think.

[jdoerfert]

minor comments and corrections, LGTM otherwise. Thx.

docs/LoopTerminology.rst

17 ↗

(On Diff #211817)

My bad, I missed the "maximal" part:

In LLVM, a Loop is a maximal set of basic blocks that form a strongly connected component (SCC)

32 ↗

(On Diff #212398)

Nit: "but the strongly connected component formed"

63 ↗

(On Diff #212398)

Nit: "(The latter is a consequence of the block being contained within an
SCC which is part of the loop.)"

llvm/trunk/docs/LoopTerminology.rst

 ===========================================
 LLVM Loop Terminology (and Canonical Forms)
 ===========================================
 
 .. contents::
    :local:
 
 Introduction
 ============
 
 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.  
 
 * Every loop must have a header block, and some set of predecessors
   outside the loop.  A loop is allowed to be statically infinite, so
   there need not be any exiting edges.
 
 * Any two loops are either fully disjoint (no intersecting blocks), or

 Header Block - The basic block which dominates all other blocks
 contained within the loop.  As such, it is the first one executed if
 the loop executes at all.  Note that a block can be the header of
 two separate loops at the same time, but only if one is a sub-loop
 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
 an Exiting Block.
 
 Latch Block - A basic block within the loop whose successors include
 the header block of the loop.  Thus, a latch is a source of backedge.
 A loop may have multiple latch blocks.  A latch block may be either