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

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

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

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)

29

Nit: "but the strongly connected component formed"

61

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

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.
+header block) which dominates all other blocks within that cycle.  
 
 Note that there are some important implications of this definition:
 
 * Not all cycles are loops.  There exist cycles 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.  Loops may also contain sub-loops.
 
+* A header block is uniquely associated with one loop.  There can be
+  multiple cycles within that loop (e.g. sub-loops), but the *largest*
+  cycle must always be the union of all the cycles which contain the
+  header.
+
 * 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

 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.  
 
 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