[Docs] Improve cycle and closed path definitions

[jsilvanus]

Summary

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.

[jsilvanus]

Improve definition highlighting.

[sameerds]

I agree, this is cleaner than the original. But please do wait for comments from the other reviewers!

[nhaehnle]

The summary/commit message has a "later later". LGTM apart from that.

[jsilvanus]

Thanks!

[foad]

llvm/docs/CycleTerminology.rst

28

Would it make sense to swap 3 and 4, so you can define the "top-level cycles" without even mentioning DFS?

[jsilvanus]

llvm/docs/CycleTerminology.rst

28

You mean one could define "top-level cycles" without mentioning a particular DFS choice?

The current order has the advantage that entries and headers are adjacent, resembling their close relationship.
But I do not have a strong opinion here.

[foad]

llvm/docs/CycleTerminology.rst

28

You mean one could define "top-level cycles" without mentioning a particular DFS choice?

Yes. The sentence "In any depth-first search starting from the entry, the set of cycles found in the CFG is the same" is really strange. Why would you even mention DFS here??? It should be clear from (1) that cycles have nothing to do with any DFS ordering. It's like saying "the set of cycles found in the CFG is the same regardless of whether Denmark and Canada share a land border" :)

I guess the only reason that (4) mentions a DFS is that (3) has already mentioned DFS. That's why I suggested reordering them. But perhaps we could keep the order the same and still remove DFS from (4)?

[jsilvanus]

llvm/docs/CycleTerminology.rst

28

Ah, now I understand, and I think you are right.

The current wording probably originates from something like "The set of top-level cycles (i.e. cycles in the original graph) can be found by DFS. In particular, the set of cycles found this way does not depend on the DFS choice."

What about moving 4 to before 2 (to keep 2 and 3 together), and rephrasing to:

The set of cycles in the function CFG itself (and not a nontrivial subgraph of it) are called *top-level cycles*.
The top-level cycles can be found using a DFS from the entry node.

[sameerds]

llvm/docs/CycleTerminology.rst

28

We could make it simpler by not focusing so much on "any DFS". What if that part is moved to section titled "Effect of DFS on Cycle Hierarchy"? Under that, we can now say that the top-level cycles are always the same, but the choice of header results in different hierarchies inside the top-level cycles.

This effect on DFS is not necessary to define how cycles are found. So this enumerated definition can just say DFS and "first node encountered is the header". The choice of header is important for its effect on the users of the cycles found. Having it in a separate section with its own anchor will make it very convenient to add refs in other places like the uniformity info document.

llvm/docs/CycleTerminology.rst

 .. _cycle-terminology:
 
 ======================
 LLVM Cycle Terminology
 ======================
 
 .. contents::
    :local:
 
 Cycles
 ======
 
 Cycles are a generalization of LLVM :ref:`loops <loop-terminology>`,
 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
 tree used. This cycle C is a superset of the loop L. For an
 irreducible cycle, no one entry dominates the nodes of the cycle. One
 of the entries is chosen as header of the cycle, in an
 implementation-defined way.
 
hierarchy of cycles is::
     - cycle: {B, D}     entries: {B, D} header: D
 
 .. _cycle-closed-path:
 
 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.
 
    **Proof:** Let U be a node in P that is dominated by D. If there
    was a node V in P not dominated by D, then U would be reachable
    from the function entry node via V without passing through D, which
    contradicts the fact that D dominates U.

llvm/include/llvm/ADT/GenericCycleInfo.h

public:
   template <typename> friend class GenericCycleInfoCompute;
 
 private:
   ContextT Context;
 
   /// Map basic blocks to their inner-most containing loop.
   DenseMap<BlockT *, CycleT *> 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.
   std::vector<std::unique_ptr<CycleT>> TopLevelCycles;
 
 public:
   GenericCycleInfo() = default;
   GenericCycleInfo(GenericCycleInfo &&) = default;