[LoopInfo] Clarify header-loop relationship

[baziotis]

Summary

I'm not sure if I have phrased it correctly or if I have understood completely analyze() but it seems to me that: Two loops can't have the same header (even if one is a sub-loop of another, which btw is not clear what it means in this context).

Example: https://godbolt.org/z/bqo8KP

[Meinersbur]

There are different definitions of loops. In the literature, such as a Dragon Book, a loop is identified by a backedge, but LLVM does it with its header. But only natural loops have a header: that is, not all cyclic control flow is represented by LoopInfo. Cyclic control flow that is is not form a natural loop is called irreducible control flow.

Anyway, using SCCs to stand for loops is bad as well since it ignores subloops. It should be a induced subgraph, not component. I think I raised this in the first review, but it was committed anyway. I'd be grateful if this could be cleaned up.

Would you be ok if I made another patch trying to fix all these things?

[baziotis]

In D88183#2293384, @Meinersbur wrote:

There are different definitions of loops. In the literature, such as a Dragon Book, a loop is identified by a backedge, but LLVM does it with its header. But only natural loops have a header: that is, not all cyclic control flow is represented by LoopInfo. Cyclic control flow that is is not form a natural loop is called irreducible control flow.

Anyway, using SCCs to stand for loops is bad as well since it ignores subloops. It should be a induced subgraph, not component. I think I raised this in the first review, but it was committed anyway. I'd be grateful if this could be cleaned up.

I agree in all that. Actually, this patch started when I was reading Muchnick's book. It has a great paragraph on reducibility and this is where my example came from. Muchnick defines
a natural loop by a backedge, but it depends on how we define that: It's when the head of an edge dominates its tail. With this definition (AFAIU), a natural loop is always reducible (only one way to enter),
but multiple natural loops can have the same header. And then the book says "if that happens, it's a matter of convention then and our convention is to consider all of them one big loop".

So, then I was curious what LLVM does: LLVM's definition of a natural loop makes it clear that in such a scenario, the loops should be considered as one big natural loop since the header dominates all the latches (and intermediate blocks).
That's also what seems to happen in the code and when I ran a couple of examples in godbolt (like the one above). But the doc at this part did not agree with this.

Would you be ok if I made another patch trying to fix all these things?

Yes of course. TBH though, although I thank you for this comment, I didn't understand if I was wrong / correct, the doc was wrong / correct or any combination of those :) It would help if you clarified, as I'm trying to understand more about loops.

[Meinersbur]

With D88408 have been committed, can this be abandoned?

[baziotis]

In D88183#2311945, @Meinersbur wrote:

With D88408 have been committed, can this be abandoned?

Yep.

[Meinersbur]

Thank you

llvm/docs/LoopTerminology.rst

 Note that there are some important implications of this definition:
 
 * 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 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.
+* A header block is uniquely associated with one loop (and vice versa).
+  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.
 

 is branched to).  They may have multiple predecessors, phis, etc...
 
 Key Terminology
 ===============
 
 **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.
+two natural loops at the same time.  However, in such cases, LoopInfo
+considers them as part of one "big" loop (in order to enforce the
+guarantee that a header block is associated with exactly one loop
+and any loop has exactly one header).
 
 **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 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