CycleInfo: Introduce cycles as a generalization of loops

[sameerds]

Summary

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization loops,
along with a CycleInfo analysis that discover a nested
hierarchy of such cycles. This is based on Havlak (1997), Nesting of
Reducible and Irreducible Loops.

The cycle analysis is implemented as a generic template and then
instatiated for LLVM IR and Machine IR. The template relies on a new
GenericSsaContext template which must be specialized when used for
each IR.

This review is a restart of an older review request:
https://reviews.llvm.org/D83094

Original implementation by Nicolai Hähnle <[e-mail]>,
with recent refactoring by Sameer Sahasrabuddhe <[e-mail]>

[foad]

Typos in summary: "introduces", "discovers", "instantiated".

[foad]

llvm/docs/CycleTerminology.rst

86

I think this needs to say "D properly dominates", with the usual convention that a block dominates itself but does not properly dominate itself. (We don't seem to have a domination terminology doc.)

99

"proper dominators"?

llvm/docs/UserGuides.rst

30

Judging by the raw diff, you have introduced some Windows-style line endings into this file.

[tschuett]

How much boilerplate would you need to support MLIR as well?

[foad]

llvm/include/llvm/ADT/GenericCycleImpl.h

21

Not sure what this comment is for. There aren't any uses of LLVM_DEBUG in this file. And if there were, and you forgot to define DEBUG_TYPE first, you'd get a compiler error wouldn't you?

llvm/include/llvm/ADT/GenericCycleInfo.h

24

Typo "block"

26

Maybe move or copy this note to the comment on the Blocks field below?

55

I vaguely remember that trailing backslashes in comments cause problems, but I can't remember what. Maybe some compilers warn about them?

140

Doxygen comment for this class template?

200

Does this make sense as part of the public API? How could a cycle be empty?

207

What is uint??? Should be unsigned.

226

Needs whitespace inside braces (doesn't clang-format do this?).

299–300

"... and entries members are"

334

Needs a comment. None of the comments so far have mentioned "exit blocks".

llvm/include/llvm/ADT/GenericSsaContext.h

26 ↗

(On Diff #382956)

Should really have comments describing the intention of all the members that specializations are supposed to define.

llvm/include/llvm/IR/SsaContext.h

46 ↗

(On Diff #382956)

Aren't Printable functions normally named like print() or printFoo()?

llvm/lib/Analysis/CycleAnalysis.cpp

2

Wrong file name.

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

2

Wrong file name.

llvm/lib/IR/CMakeLists.txt

2

Spurious change?

llvm/lib/IR/SsaContext.cpp

11 ↗

(On Diff #382956)

It's a class template, not a template class :)

[sameerds]

In D112696#3092904, @tschuett wrote:

How much boilerplate would you need to support MLIR as well?

This change is a rehash of an earlier attempt, which involved a lot of discussion about moving towards a common abstraction for CFG + SSA. The issues are more involved than boilerplate in the implementation (hint: MLIR does not have PHI nodes). The following email would be a good starting point if you want to dive in:

[llvm-dev] [RFC] Abstracting over SSA form IRs to implement generic analyses
Nicolai Hähnle
https://lists.llvm.org/pipermail/llvm-dev/2020-December/147433.html

[mehdi_amini]

(The added test seems to fail the CI right now)

[sameerds]

Addressed review comments

[foad]

llvm/include/llvm/ADT/GenericCycleInfo.h

137

Typo "possibly"

[sameerds]

llvm/docs/UserGuides.rst

30

I thought so too, but this original source file is DOS formatted, and Emacs faithfully added the Windows-style new lines.

llvm/include/llvm/ADT/GenericCycleImpl.h

21

I am not sure what the objection is. This comment simply explains what to do if there is an LLVM_DEBUG occurrence. This file specifically does not define DEBUG_TYPE so that the messages can be enabled by the file that actually specializes these templates. It so happens that this particular file does not contain any LLVM_DEBUG messages, but I am using this as a standard header for more such files in the pipeline.

llvm/include/llvm/ADT/GenericCycleInfo.h

55

An internet search revealed that things get interesting when a single-line comment has a trailing backslash and useful code on the next line. The backslash eats up the new-line , and on some platforms, depending on the definition of new-line, the useful code is eaten up by the comment.

Clearly, no such issue here inside a block of single-line comments.

226

Those braces enclose an initializer list and not a block of statements. Hence no space inside them.

[foad]

llvm/include/llvm/ADT/GenericCycleImpl.h

21

No strong objection, it just seems like the kind of comment you could put in any header file in the whole project, which suggests to me that it's not adding much value.

llvm/include/llvm/ADT/GenericCycleInfo.h

226

Good point! I'm still not used to braced initializer lists.

[arsenm]

llvm/include/llvm/ADT/GenericCycleImpl.h

21

I thought you had to define LLVM_DEBUG after any includes to avoid some issue

[sameerds]

• added specific wording from paper to description of cycle tree
• added LLVM_DEBUG to implementation
• fixed typos

[sameerds]

llvm/docs/CycleTerminology.rst

86

I think this needs to say "D properly dominates", with the usual convention that a block dominates itself but does not properly dominate itself. (We don't seem to have a domination terminology doc.)

Fixed this by requiring that D is not contained in P. The statement is not true if D is in P!

llvm/include/llvm/ADT/GenericCycleImpl.h

21

Fixed all of this by defining DEBUG_TYPE in the template implementation itself. This is closer to how the macro is defined in other header files.

[sameerds]

"uint" broke the Windows build

[foad]

LGTM overall. I only skimmed through the algorithmic parts. Personally I would be happy to take it on trust that the analysis does what Havlak says and works as described, unless someone volunteers to do a much deeper review of the implementation.

llvm/include/llvm/ADT/GenericCycleInfo.h

297

Typoe "filed".

[ruiling]

llvm/docs/CycleTerminology.rst

30

Why do we need this root cycle? All the blocks of a function mostly do not even form a strongly connected region. And this is quite different from the way LoopInfo works.

[sameerds]

llvm/docs/CycleTerminology.rst

30

Why do we need this root cycle? All the blocks of a function mostly do not even form a strongly connected region. And this is quite different from the way LoopInfo works.

I should copy a comment from GenericCycleInfo class to this spec. Essentially, the "root" is a placeholder cycle that allows CycleInfo to be treated as a single tree. Then we can use GraphTraits as follows (see validateTree() in GenericCycleImpl.h):

for (const CycleT *cycle : depth_first(getRoot())) { ... }

[ruiling]

llvm/docs/CycleTerminology.rst

30

My point is that the root cycle is actually not a cycle based on the definition of cycle. And If we want to check whether a block is inside any loop, we just check whether getLoopFor(block) returns nullptr, but that is not true in CycleInfo. This may be confusing for people switching from LoopInfo to CycleInfo. Am I over-concerned? I am not familiar with GraphTraits. So if we follow the same idea as LoopInfo, code will be quite complex, right?

[ruiling]

llvm/include/llvm/ADT/GenericCycleImpl.h

72

The implementation here looks good to me. just a few comments on the naming.

84

I think we capitalize the term DFS when naming variables within LLVM? at least I found most occurrences of DFS are capitalized.

98

Cycle is too general here. What about NewCycle to indicate that this is the newly discovered cycle?

139

I think it may be better to rename C as OuterMostCycle or some other reasonable name indicating that this is the outermost cycle discovered so far for this block.

[critson]

llvm/lib/CodeGen/MachineSsaContext.cpp

43 ↗

(On Diff #384646)

This needs to be able to deal with physical registers.

[sameerds]

• Fixed some doxygen comments.
• Eliminated the "root" cycle.
• Cycle should not point to CycleInfo; it's hard to update that reference. Fixed the side-effects of eliminating that reference.
• Fixed names mentioned in review comments.
• Extracted two helper functions: getTopLevelParent() and moveToNewParent(). Both very helpful in improving readability.
• SsaContext now keeps a reference to the Function so that user analyses can retrieve it. Forward looking change, found to be useful in later analyses not introduced yet.

[sameerds]

llvm/docs/CycleTerminology.rst

30

I see now. Thanks for pointing out the parallel with LoopInfo, it might be useful in the future. I've now eliminated the root cycle. Luckily, it did not cause much side-effects in other places.

llvm/include/llvm/ADT/GenericCycleImpl.h

84

CamelCase for acronym seems to be pretty inconsistent in the LLVM codebase, and the coding standard does not say anything specific. For example, I found instances of both Cfg/CFG and Dag/DAG. I am happy to change the name it if there is a strong preference for "DFS" instead of "Dfs". But in support of my choice, CamelCase makes it easier to read "DfsInfo" compared to "DFSInfo". This is especially so when joining two acronyms, like "CfgSsa" compared to "CFGSSA".

I have this vague memory that once upon a time, the LLVM coding standard recommended that only the first letter be capitalized, but now I am not sure if I am just misremembering something else.

llvm/lib/CodeGen/MachineSsaContext.cpp

43 ↗

(On Diff #384646)

Does the new check look better? From the implementation, it seems that getUniqueVRegDef() will gracefully handle physical registers.

[tschuett]

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

[arsenm]

In D112696#3124156, @tschuett wrote:

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

I'm desperately awaiting this to serve as the basis for a replacement control flow lowering scheme for AMDGPU

[tschuett]

In D112696#3124371, @arsenm wrote:

In D112696#3124156, @tschuett wrote:

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

I'm desperately awaiting this to serve as the basis for a replacement control flow lowering scheme for AMDGPU

Thanks!

[sameerds]

rebase

[ruiling]

Thanks for this revision, the refactor make lots of sense to me. I have added some further comments. Other parts look pretty good to me.

llvm/docs/CycleTerminology.rst

34–35

It would be better we are not treating nullptr as the root-cycle unless we really have to. My understanding is that nullptr is just saying that this is the outermost cycle, it does not have any parent.

65

I am not good at English wording. But is it meaningful to say two basic blocks are siblings to each other if both of them are not in any cycle?

llvm/include/llvm/ADT/GenericCycleImpl.h

84

I think we have not explicitly require UPPERCASE for acronym in LLVM. But if you grep in LLVM source code, DFS/SSA/CFG/DAG vs Dfs/Ssa/Cfg/Dag. I think you will easily notice 90% are using the UPPERCASE. Yes, there are some occurrence of the latter version, which I don't think is a good idea. I don't like such kind of divergence situation. technically I don't have preference for one over another. But I really like most of the code could be in the same form regarding this.

278

typo, "contains \p B".

291

While it is reasonable to return nullptr when querying parent cycle of top level cycle. It does not sound reasonable that we say nullptr contains an ordinary cycle. Do you have any use case that can demonstrate we need to define the behavior of contains() to return true if input A is nullptr to get expected result? I don't know what the case you have shown contains(getCycle(F), getCycle(G) used for. IMO, null input value is just non-applicable here, we should just return false if either A or B is nullptr.

[sameerds]

llvm/docs/CycleTerminology.rst

34–35

Not everything can be measured with the metric of "unless we have to". Treating nullptr as the "vacuous root" (please note the term "vacuous") is worth the convenience it provides.

This is not a novelty, it happens often in formal definitions, including the paper by Havlak that this implementation is based on. Such vacuous objects are used to make life easy for inductive reasoning about formalisms. To look at it differently, think of it as 0! defined as 1 just to make it easy to write an inductive definition of the factorial function.

65

It's not about the language used. This section defines terms, and I am defining what a sibling is when neither of them are in a "real" cycle because they are both in a "vacuous" root cycle.

llvm/include/llvm/ADT/GenericCycleImpl.h

291

While the code does not contain an explicit call to contains(getCycle(F), getCycle(G), it does contain calls to contains() where one of the arguments became null just because the caller went up the hierarchy. It is much more consistent to handle this situation inside contains() than adding if (!cycle) { // then that means we are the toplevel } in multiple places.

Where it matters, I have used Optional<Cycle*> to differentiate between "no cycle" and "root cycle". I believe that my interpretation of nullptr is convenient enough that I am willing to go use the Optional<> type where it needs to be disambiguated. In fact, that is the very purpose for the existence of types like llvm::Optional<>, std::opt, and Haskell Maybe.

[ruiling]

llvm/docs/CycleTerminology.rst

34–35

I am sorry I still don't get the point why treating nullptr as the root cycle is necessary here. And I also don't understand why "vacuous root" would help the argument here. The reason I don't want a root cycle (either a null or non-null) is it is counter-intuitive. It just makes CycleInfo different from the way LoopInfo works without any real benefits.

llvm/include/llvm/ADT/GenericCycleImpl.h

291

Could you help show me when we will passing nullptr to the first argument of contains() and we really depends on the return value should be TRUE to make caller algorithm work correctly?
Do we have many places need to check against nullptr before passing to the first argument as if (CycleA && contains(CycleA, CycleB))? And explicitly checking against a real-existed cycle for the first argument before calling this function sounds a clear way to me. I would even like we put an assert here that the first argument is not null:-)

[sameerds]

llvm/docs/CycleTerminology.rst

34–35

Yeah, compatibility with LoopInfo definitely over-rules all my other arguments. I had been going over the interface, and I realised that CycleInfo::contains() and Loop::contains() are clearly in different places. If there is an occasion to unify them in a single interface, things will get pretty awkward.

In fact, this might be a good time to audit the entire interface and make sure it looks exactly like LoopInfo. Thanks for not letting go of this! :D

llvm/include/llvm/ADT/GenericCycleImpl.h

291

I am now working on a change that removes the special meaning of nullptr completely just because of LoopInfo. I did discover places that broke, where now I have to do if (!CycleA || contains(CycleA, CycleB). I might even be able to replace some of the !CycleA with a preceding assert instead. But none of these places are a strong justification for the current behaviour of contains().

[sameerds]

• rebase
• replace Dfg and Ssa with uppercase versions
• eliminate any interpretation of nullptr as root cycle
• move two functions from CycleInfo to Cycle, just like LoopInfo
• small cleanup to the cycle terminology, pointed out by @nhaehnle

[foad]

llvm/include/llvm/CodeGen/MachineSSAContext.h

2

Capitalize SSA

11

Capitalize SSA

[sameerds]

• rebase
• removed the "vacuous root" from the cycle description

[sameerds]

llvm/include/llvm/CodeGen/MachineSSAContext.h

2

I didn't notice this when I uploaded an update a few minutes ago. I feel very bad about another update triggering yet another build in the CI system. I have fixed the problem in both places, as well as one last place that I missed in the commit description. Thanks!

[ruiling]

LGTM. please wait a few days before committing in case others have further comments.

llvm/include/llvm/ADT/GenericCycleInfo.h

18–25

Can you update this part to match the document?

200–202

Can you update the comment?

llvm/include/llvm/InitializePasses.h

448

This belongs to a future change?

[nhaehnle]

Thank you for doing this. I'm happy with the big picture of the change obviously, though I noticed a few things inline.

llvm/include/llvm/ADT/GenericCycleImpl.h

35

Other code in this file uses the new style function definition syntax, so perhaps do so here as well to be consistent?

69

-machine, since this is generic code

llvm/include/llvm/ADT/GenericCycleInfo.h

15–16

How about moving everything of this file comment to the new CycleTerminology document (that isn't already there) and then just refer to that document here?

llvm/include/llvm/InitializePasses.h

122–123

These two don't belong here

llvm/lib/IR/SSAContext.cpp

2

Wrong filename

[sameerds]

• rebase
• addressed review comments

[sameerds]

llvm/include/llvm/ADT/GenericCycleImpl.h

35

I am not sure what you mean here ... this definition passes clang-format and clang-tidy. If you mean the lowercase ::contains, then that is valid camelBack where the first letter must be lowercase.

llvm/include/llvm/ADT/GenericCycleInfo.h

15–16

Added appropriate sections to CycleTerminology.rst.

[nhaehnle]

LGTM

llvm/include/llvm/ADT/GenericCycleImpl.h

35

I meant the auto foo(...) -> T syntax.

llvm/include/llvm/ADT/GenericCycleInfo.h

11

Maybe add a "See docs/CycleTerminology.rst for a high-level overview." comment?

[foad]

I said:

LGTM overall. I only skimmed through the algorithmic parts. Personally I would be happy to take it on trust that the analysis does what Havlak says and works as described, unless someone volunteers to do a much deeper review of the implementation.

Still LGTM. Thanks @ruiling for doing a much more detailed review!

[sameerds]

llvm/include/llvm/ADT/GenericCycleImpl.h

35

That's a trailing return type from C++11 ... I am using it in places where the name of the return type is in scope only within the class whose member is being defined. For example:

template <typename ContextT>
auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
    -> CycleT * { ... }

The trailing return type ensures DRY because CycleT is in scope after declaring the function name. Naming the return type first would require us to use the much more verbose GenericCycleInfo<ContextT>::CycleT instead.

[JDevlieghere]

I've reverted this in 02940d6d22022dbad45efa0c9a5cc772ba844da4 because it breaks the modules builds:

https://green.lab.llvm.org/green/job/clang-stage2-rthinlto/4858/
https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/39112/

[sameerds]

Reopening revision to help with pre-submit checks, before reapplying the reverted commit.

[sameerds]

• rebase
• The opaque member class Compute broke module builds.
• Moved compute to an extern template class in namespace llvm.
• Cleaned out a spurious class declaration that was not used anywhere.

[sameerds]

In D112696#3177463, @JDevlieghere wrote:

I've reverted this in 02940d6d22022dbad45efa0c9a5cc772ba844da4 because it breaks the modules builds:

https://green.lab.llvm.org/green/job/clang-stage2-rthinlto/4858/
https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/39112/

I managed to reproduce the breakage locally with -DLLVM_ENABLE_MODULES=On. With my latest revision, I can see that the error specifically mentioning my files has disappeared, but the build does not complete. @JDevlieghere do you have any advice on perfectly reproducing that build locally? Are there other things to be specified on the cmake line?

[sameerds]

In D112696#3181899, @sameerds wrote:

In D112696#3177463, @JDevlieghere wrote:

I've reverted this in 02940d6d22022dbad45efa0c9a5cc772ba844da4 because it breaks the modules builds:

https://green.lab.llvm.org/green/job/clang-stage2-rthinlto/4858/
https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/39112/

I managed to reproduce the breakage locally with -DLLVM_ENABLE_MODULES=On. With my latest revision, I can see that the error specifically mentioning my files has disappeared, but the build does not complete. @JDevlieghere do you have any advice on perfectly reproducing that build locally? Are there other things to be specified on the cmake line?

@JDevlieghere, I am still unable to produce a modules build locally, but spent some effort convincing myself that the latest revision of my patch no longer introduces the original problem. I've submitted my fixed version with that confidence, but will keep an eye on the builds it broke. Do give me a chance to upload a fix before reverting, say within 24 hours of any new breakage.

[foad]

llvm/docs/CycleTerminology.rst

35

Hi @sameerds, I have a question about this: why does #5 talk about "a cycle C with header H" (which depends on a particular DFS), instead of "a cycle C with entries E" (which would not)? It seems like this would make the cycle nesting structure depend on the choice of DFS. Is that intentional? It is unavoidable?

[sameerds]

llvm/docs/CycleTerminology.rst

35

This is more about maximizing how much hierarchy we can uncover in a given irreducible graph. The current technique picks one entry of a cycle C as the header H in a mostly arbitrary way, and then discovers more cycles in the subgraph C-H. We could instead choose to explore the subgraph C-E, but that just means that we are likely to discover fewer subcyles. The cost of choosing C-H is that we make everything implementation/DFS dependent, but I think it's worth it. I don't think this dependence is unavoidable; it just makes the hierarchy more useful.

[sameerds]

llvm/docs/CycleTerminology.rst

35

On second thought, excluding the header is indeed unavoidable. Without that, we cannot make statements like property 4: "In any cycle hierarchy, the header H of the smallest cycle C containing a closed path P itself lies on P." If we used C-E, then we break any closed paths that are included in C but do not pass through H. Such paths will not pass through the header of any cycle.

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
+   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.
+
+Thus, cycles form an implementation-defined forest where each cycle C is
+the parent of any outermost 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.
+
+.. _cycle-irreducible:
+
+A cycle is *irreducible* if it has multiple entries and it is
+*reducible* otherwise.
+
+.. _cycle-parent-block:
+
+A cycle C is said to be the *parent* of a basic block B if B occurs in
+C but not in any child cycle of C. Then B is also said to be a *child*
+of cycle C.
+
+.. _cycle-sibling:
+
+A basic block or cycle X is a *sibling* of another basic block or
+cycle Y if they both have no parent or both have the same parent.
+
+Informational notes:
+
+- Non-header entry blocks of a cycle can be contained in child cycles.
+- If the CFG is reducible, the cycles are exactly the natural loops and
+  every cycle has exactly one entry block.
+- Cycles are well-nested (by definition).
+- The entry blocks of a cycle are siblings in the dominator tree.
+
+.. [HavlakCycles] Paul Havlak, "Nesting of reducible and irreducible
+                  loops." ACM Transactions on Programming Languages
+                  and Systems (TOPLAS) 19.4 (1997): 557-567.
+
+.. _cycle-examples:
+
+Examples of Cycles
+==================
+
+Irreducible cycle enclosing natural loops
+-----------------------------------------
+
+.. Graphviz source; the indented blocks below form a comment.
+
+  ///     |   |
+  ///   />A] [B<\
+  ///   |  \ /  |
+  ///   ^---C---^
+  ///       |
+
+  strict digraph {
+    { rank=same; A B}
+    Entry -> A
+    Entry -> B
+    A -> A
+    A -> C
+    B -> B
+    B -> C
+    C -> A
+    C -> B
+    C -> Exit
+  }
+
+.. image:: cycle-1.png
+
+The self-loops of ``A`` and ``B`` give rise to two single-block
+natural loops. A possible hierarchy of cycles is::
+
+    cycle: {A, B, C} entries: {A, B} header: A
+    - cycle: {B, C}  entries: {B, C} header: C
+      - cycle: {B}   entries: {B}    header: B
+
+This hierarchy arises when DFS visits the blocks in the order ``A``,
+``C``, ``B`` (in preorder).
+
+Irreducible union of two natural loops
+--------------------------------------
+
+.. Graphviz source; the indented blocks below form a comment.
+
+  ///     |   |
+  ///     A<->B
+  ///     ^   ^
+  ///     |   |
+  ///     v   v
+  ///     C   D
+  ///     |   |
+
+  strict digraph {
+    { rank=same; A B}
+    { rank=same; C D}
+    Entry -> A
+    Entry -> B
+    A -> B
+    B -> A
+    A -> C
+    C -> A
+    B -> D
+    D -> B
+    C -> Exit
+    D -> Exit
+  }
+
+.. image:: cycle-2.png
+
+There are two natural loops: ``{A, C}`` and ``{B, D}``. A possible
+hierarchy of cycles is::
+
+    cycle: {A, B, C, D} entries: {A, B} header: A
+    - cycle: {B, D}     entries: {B}    header: B
+
+Irreducible cycle without natural loops
+---------------------------------------
+
+.. Graphviz source; the indented blocks below form a comment.
+
+  ///     |   |
+  ///   />A   B<\
+  ///   | |\ /| |
+  ///   | | x | |
+  ///   | |/ \| |
+  ///   ^-C   D-^
+  ///     |   |
+  ///
+
+  strict digraph {
+    { rank=same; A B}
+    { rank=same; C D}
+    Entry -> A
+    Entry -> B
+    A -> C
+    A -> D
+    B -> C
+    B -> D
+    C -> A
+    D -> B
+    C -> Exit
+    D -> Exit
+  }
+
+.. image:: cycle-3.png
+
+This graph does not contain any natural loops --- the nodes ``A``,
+``B``, ``C`` and ``D`` are siblings in the dominator tree. A possible
+hierarchy of cycles is::
+
+    cycle: {A, B, C, D} entries: {A, B} header: A
+    - 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.
+
+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.
+
+2. If a node D dominates one or more nodes in a closed path P and P
+   does not contain D, then there exists a cycle C that contains P but
+   not D.
+
+   **Proof:** From the above property, D dominates all the nodes in P.
+   For any nesting of cycles discovered by the implementation-defined
+   DFS, consider the smallest cycle C which contains P. For the sake
+   of contradiction, assume that D is in C. Then the header H of C
+   cannot be in P, since the header of a cycle cannot be dominated by
+   any other node in the cycle. Thus, P is in the set (C-H), and there
+   must be a smaller cycle C' in C which also contains P, but that
+   contradicts how we chose C.
+
+3. If a closed path P contains nodes U1 and U2 but not their
+   dominators D1 and D2 respectively, then there exists a cycle C that
+   contains U1 and U2 but neither of D1 and D2.
+
+   **Proof:** From the above properties, each D1 and D2 separately
+   dominate every node in P. There exists a cycle C1 (respectively,
+   C2) that contains P but not D1 (respectively, D2). Either C1 and C2
+   are the same cycle, or one of them is nested inside the other.
+   Hence there is always a cycle that contains U1 and U2 but neither
+   of D1 and D2.

llvm/docs/UserGuides.rst

.. toctree::
    CFIVerify
    CMake
    CMakePrimer
    CodeGenerator
    CodeOfConduct
    CommandLine
    CompileCudaWithLLVM
    CoverageMappingFormat
+   CycleTerminology
    DebuggingJITedCode
    Docker
    ExtendingLLVM
    GoldPlugin
    HowToBuildOnARM
    HowToBuildWithPGO
    HowToBuildWindowsItaniumPrograms
    HowToCrossCompileBuiltinsOnArm
:doc:`AliasAnalysis`
    use existing analyses.
 
 :doc:`MemorySSA`
    Information about the MemorySSA utility in LLVM, as well as how to use it.
 
 :doc:`LoopTerminology`
   A document describing Loops and associated terms as used in LLVM.
 
+:doc:`CycleTerminology`
+  A document describing cycles as a generalization of loops.
+
 :doc:`Vectorizers`
    This document describes the current status of vectorization in LLVM.
 
 :doc:`LinkTimeOptimization`
    This document describes the interface between LLVM intermodular optimizer
    and the linker and its design
 
 :doc:`GoldPlugin`

llvm/include/llvm/ADT/GenericCycleImpl.h

+//===- GenericCycleImpl.h -------------------------------------*- C++ -*---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This template implementation resides in a separate file so that it
+// does not get injected into every .cpp file that includes the
+// generic header.
+//
+// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
+//
+// This file should only be included by files that implement a
+// specialization of the relevant templates. Currently these are:
+// - CycleAnalysis.cpp
+// - MachineCycleAnalysis.cpp
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_GENERICCYCLEIMPL_H
+#define LLVM_ADT_GENERICCYCLEIMPL_H
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/GenericCycleInfo.h"
+
+#define DEBUG_TYPE "generic-cycle-impl"
+
+namespace llvm {
+
+template <typename ContextT>
+bool GenericCycle<ContextT>::contains(const GenericCycle *C) const {
+  if (!C)
+    return false;
+
+  if (Depth > C->Depth)
+    return false;
+  while (Depth < C->Depth)
+    C = C->ParentCycle;
+  return this == C;
+}
+
+template <typename ContextT>
+void GenericCycle<ContextT>::getExitBlocks(
+    SmallVectorImpl<BlockT *> &TmpStorage) const {
+  TmpStorage.clear();
+
+  size_t NumExitBlocks = 0;
+  for (BlockT *Block : blocks()) {
+    llvm::append_range(TmpStorage, successors(Block));
+
+    for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
+         ++Idx) {
+      BlockT *Succ = TmpStorage[Idx];
+      if (!contains(Succ)) {
+        auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
+        if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
+          TmpStorage[NumExitBlocks++] = Succ;
+      }
+    }
+
+    TmpStorage.resize(NumExitBlocks);
+  }
+}
+
+/// \brief Helper class for computing cycle information.
+template <typename ContextT> class GenericCycleInfoCompute {
+  using BlockT = typename ContextT::BlockT;
+  using CycleInfoT = GenericCycleInfo<ContextT>;
+  using CycleT = typename CycleInfoT::CycleT;
+
+  CycleInfoT &Info;
+
+  struct DFSInfo {
+    unsigned Start = 0; // DFS start; positive if block is found
+    unsigned End = 0;   // DFS end
+
+    DFSInfo() {}
+    explicit DFSInfo(unsigned Start) : Start(Start) {}
+
+    /// Whether this node is an ancestor (or equal to) the node \p Other
+    /// in the DFS tree.
+    bool isAncestorOf(const DFSInfo &Other) const {
+      return Start <= Other.Start && Other.End <= End;
+    }
+  };
+
+  DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
+  SmallVector<BlockT *, 8> BlockPreorder;
+
+  GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete;
+  GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
+
+public:
+  GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {}
+
+  void run(BlockT *EntryBlock);
+
+  static void updateDepth(CycleT *SubTree);
+
+private:
+  void dfs(BlockT *EntryBlock);
+};
+
+template <typename ContextT>
+auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(
+    const BlockT *Block) const -> CycleT * {
+  auto MapIt = BlockMap.find(Block);
+  if (MapIt == BlockMap.end())
+    return nullptr;
+
+  auto *C = MapIt->second;
+  while (C->ParentCycle)
+    C = C->ParentCycle;
+  return C;
+}
+
+template <typename ContextT>
+void GenericCycleInfo<ContextT>::moveToNewParent(CycleT *NewParent,
+                                                 CycleT *Child) {
+  auto &CurrentContainer =
+      Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
+  auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
+    return Child == Ptr.get();
+  });
+  assert(Pos != CurrentContainer.end());
+  NewParent->Children.push_back(std::move(*Pos));
+  *Pos = std::move(CurrentContainer.back());
+  CurrentContainer.pop_back();
+  Child->ParentCycle = NewParent;
+}
+
+/// \brief Main function of the cycle info computations.
+template <typename ContextT>
+void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) {
+  LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
+                    << "\n");
+  dfs(EntryBlock);
+
+  SmallVector<BlockT *, 8> Worklist;
+
+  for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
+    const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
+
+    for (BlockT *Pred : predecessors(HeaderCandidate)) {
+      const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
+      if (CandidateInfo.isAncestorOf(PredDFSInfo))
+        Worklist.push_back(Pred);
+    }
+    if (Worklist.empty()) {
+      continue;
+    }
+
+    // Found a cycle with the candidate as its header.
+    LLVM_DEBUG(errs() << "Found cycle for header: "
+                      << Info.Context.print(HeaderCandidate) << "\n");
+    std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
+    NewCycle->appendEntry(HeaderCandidate);
+    NewCycle->appendBlock(HeaderCandidate);
+    Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
+
+    // Helper function to process (non-back-edge) predecessors of a discovered
+    // block and either add them to the worklist or recognize that the given
+    // block is an additional cycle entry.
+    auto ProcessPredecessors = [&](BlockT *Block) {
+      LLVM_DEBUG(errs() << "  block " << Info.Context.print(Block) << ": ");
+
+      bool IsEntry = false;
+      for (BlockT *Pred : predecessors(Block)) {
+        const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
+        if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
+          Worklist.push_back(Pred);
+        } else {
+          IsEntry = true;
+        }
+      }
+      if (IsEntry) {
+        assert(!NewCycle->isEntry(Block));
+        LLVM_DEBUG(errs() << "append as entry\n");
+        NewCycle->appendEntry(Block);
+      } else {
+        LLVM_DEBUG(errs() << "append as child\n");
+      }
+    };
+
+    do {
+      BlockT *Block = Worklist.pop_back_val();
+      if (Block == HeaderCandidate)
+        continue;
+
+      // If the block has already been discovered by some cycle
+      // (possibly by ourself), then the outermost cycle containing it
+      // should become our child.
+      if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
+        LLVM_DEBUG(errs() << "  block " << Info.Context.print(Block) << ": ");
+
+        if (BlockParent != NewCycle.get()) {
+          LLVM_DEBUG(errs()
+                     << "discovered child cycle "
+                     << Info.Context.print(BlockParent->getHeader()) << "\n");
+          // Make BlockParent the child of NewCycle.
+          Info.moveToNewParent(NewCycle.get(), BlockParent);
+          NewCycle->Blocks.insert(NewCycle->Blocks.end(),
+                                  BlockParent->block_begin(),
+                                  BlockParent->block_end());
+
+          for (auto *ChildEntry : BlockParent->entries())
+            ProcessPredecessors(ChildEntry);
+        } else {
+          LLVM_DEBUG(errs()
+                     << "known child cycle "
+                     << Info.Context.print(BlockParent->getHeader()) << "\n");
+        }
+      } else {
+        Info.BlockMap.try_emplace(Block, NewCycle.get());
+        assert(!is_contained(NewCycle->Blocks, Block));
+        NewCycle->Blocks.push_back(Block);
+        ProcessPredecessors(Block);
+      }
+    } while (!Worklist.empty());
+
+    Info.TopLevelCycles.push_back(std::move(NewCycle));
+  }
+
+  // Fix top-level cycle links and compute cycle depths.
+  for (auto *TLC : Info.toplevel_cycles()) {
+    LLVM_DEBUG(errs() << "top-level cycle: "
+                      << Info.Context.print(TLC->getHeader()) << "\n");
+
+    TLC->ParentCycle = nullptr;
+    updateDepth(TLC);
+  }
+}
+
+/// \brief Recompute depth values of \p SubTree and all descendants.
+template <typename ContextT>
+void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) {
+  for (CycleT *Cycle : depth_first(SubTree))
+    Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
+}
+
+/// \brief Compute a DFS of basic blocks starting at the function entry.
+///
+/// Fills BlockDFSInfo with start/end counters and BlockPreorder.
+template <typename ContextT>
+void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
+  SmallVector<unsigned, 8> DFSTreeStack;
+  SmallVector<BlockT *, 8> TraverseStack;
+  unsigned Counter = 0;
+  TraverseStack.emplace_back(EntryBlock);
+
+  do {
+    BlockT *Block = TraverseStack.back();
+    LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
+                      << "\n");
+    if (!BlockDFSInfo.count(Block)) {
+      // We're visiting the block for the first time. Open its DFSInfo, add
+      // successors to the traversal stack, and remember the traversal stack
+      // depth at which the block was opened, so that we can correctly record
+      // its end time.
+      LLVM_DEBUG(errs() << "  first encountered at depth "
+                        << TraverseStack.size() << "\n");
+
+      DFSTreeStack.emplace_back(TraverseStack.size());
+      llvm::append_range(TraverseStack, successors(Block));
+
+      LLVM_ATTRIBUTE_UNUSED
+      bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
+      assert(Added);
+      BlockPreorder.push_back(Block);
+      LLVM_DEBUG(errs() << "  preorder number: " << Counter << "\n");
+    } else {
+      assert(!DFSTreeStack.empty());
+      if (DFSTreeStack.back() == TraverseStack.size()) {
+        LLVM_DEBUG(errs() << "  ended at " << Counter << "\n");
+        BlockDFSInfo.find(Block)->second.End = Counter;
+        DFSTreeStack.pop_back();
+      } else {
+        LLVM_DEBUG(errs() << "  already done\n");
+      }
+      TraverseStack.pop_back();
+    }
+  } while (!TraverseStack.empty());
+  assert(DFSTreeStack.empty());
+
+  LLVM_DEBUG(
+    errs() << "Preorder:\n";
+    for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
+      errs() << "  " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
+    }
+  );
+}
+
+/// \brief Reset the object to its initial state.
+template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
+  TopLevelCycles.clear();
+  BlockMap.clear();
+}
+
+/// \brief Compute the cycle info for a function.
+template <typename ContextT>
+void GenericCycleInfo<ContextT>::compute(FunctionT &F) {
+  GenericCycleInfoCompute<ContextT> Compute(*this);
+  Context.setFunction(F);
+
+  LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
+                    << "\n");
+  Compute.run(ContextT::getEntryBlock(F));
+
+  assert(validateTree());
+}
+
+/// \brief Find the innermost cycle containing a given block.
+///
+/// \returns the innermost cycle containing \p Block or nullptr if
+///          it is not contained in any cycle.
+template <typename ContextT>
+auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
+    -> CycleT * {
+  auto MapIt = BlockMap.find(Block);
+  if (MapIt != BlockMap.end())
+    return MapIt->second;
+  return nullptr;
+}
+
+/// \brief Validate the internal consistency of the cycle tree.
+///
+/// Note that this does \em not check that cycles are really cycles in the CFG,
+/// or that the right set of cycles in the CFG were found.
+template <typename ContextT>
+bool GenericCycleInfo<ContextT>::validateTree() const {
+  DenseSet<BlockT *> Blocks;
+  DenseSet<BlockT *> Entries;
+
+  auto reportError = [](const char *File, int Line, const char *Cond) {
+    errs() << File << ':' << Line
+           << ": GenericCycleInfo::validateTree: " << Cond << '\n';
+  };
+#define check(cond)                                                            \
+  do {                                                                         \
+    if (!(cond)) {                                                             \
+      reportError(__FILE__, __LINE__, #cond);                                  \
+      return false;                                                            \
+    }                                                                          \
+  } while (false)
+
+  for (const auto *TLC : toplevel_cycles()) {
+    for (const CycleT *Cycle : depth_first(TLC)) {
+      if (Cycle->ParentCycle)
+        check(is_contained(Cycle->ParentCycle->children(), Cycle));
+
+      for (BlockT *Block : Cycle->Blocks) {
+        auto MapIt = BlockMap.find(Block);
+        check(MapIt != BlockMap.end());
+        check(Cycle->contains(MapIt->second));
+        check(Blocks.insert(Block).second); // duplicates in block list?
+      }
+      Blocks.clear();
+
+      check(!Cycle->Entries.empty());
+      for (BlockT *Entry : Cycle->Entries) {
+        check(Entries.insert(Entry).second); // duplicate entry?
+        check(is_contained(Cycle->Blocks, Entry));
+      }
+      Entries.clear();
+
+      unsigned ChildDepth = 0;
+      for (const CycleT *Child : Cycle->children()) {
+        check(Child->Depth > Cycle->Depth);
+        if (!ChildDepth) {
+          ChildDepth = Child->Depth;
+        } else {
+          check(ChildDepth == Child->Depth);
+        }
+      }
+    }
+  }
+
+  for (const auto &Entry : BlockMap) {
+    BlockT *Block = Entry.first;
+    for (const CycleT *Cycle = Entry.second; Cycle;
+         Cycle = Cycle->ParentCycle) {
+      check(is_contained(Cycle->Blocks, Block));
+    }
+  }
+
+#undef check
+
+  return true;
+}
+
+/// \brief Print the cycle info.
+template <typename ContextT>
+void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const {
+  for (const auto *TLC : toplevel_cycles()) {
+    for (const CycleT *Cycle : depth_first(TLC)) {
+      for (unsigned I = 0; I < Cycle->Depth; ++I)
+        Out << "    ";
+
+      Out << Cycle->print(Context) << '\n';
+    }
+  }
+}
+
+} // namespace llvm
+
+#undef DEBUG_TYPE
+
+#endif // LLVM_ADT_GENERICCYCLEIMPL_H

llvm/include/llvm/ADT/GenericCycleInfo.h

+//===- GenericCycleInfo.h - Info for Cycles in any IR ------*- C++ -*------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// \brief Find all cycles in a control-flow graph, including irreducible loops.
+///
+/// See docs/CycleTerminology.rst for a formal definition of cycles.
+///
+/// Briefly:
+/// - A cycle is a generalization of a loop which can represent
+///   irreducible control flow.
+/// - Cycles identified in a program are implementation defined,
+///   depending on the DFS traversal chosen.
+/// - Cycles are well-nested, and form a forest with a parent-child
+///   relationship.
+/// - In any choice of DFS, every natural loop L is represented by a
+///   unique cycle C which is a superset of L.
+/// - In the absence of irreducible control flow, the cycles are
+///   exactly the natural loops in the program.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_GENERICCYCLEINFO_H
+#define LLVM_ADT_GENERICCYCLEINFO_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GenericSSAContext.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Printable.h"
+#include "llvm/Support/raw_ostream.h"
+#include <vector>
+
+namespace llvm {
+
+template <typename ContexT> class GenericCycleInfo;
+template <typename ContexT> class GenericCycleInfoCompute;
+
+/// A possibly irreducible generalization of a \ref Loop.
+template <typename ContextT> class GenericCycle {
+public:
+  using BlockT = typename ContextT::BlockT;
+  using FunctionT = typename ContextT::FunctionT;
+  template <typename> friend class GenericCycleInfo;
+  template <typename> friend class GenericCycleInfoCompute;
+
+private:
+  /// The parent cycle. Is null for the root "cycle". Top-level cycles point
+  /// at the root.
+  GenericCycle *ParentCycle = nullptr;
+
+  /// The entry block(s) of the cycle. The header is the only entry if
+  /// this is a loop. Is empty for the root "cycle", to avoid
+  /// unnecessary memory use.
+  SmallVector<BlockT *, 1> Entries;
+
+  /// Child cycles, if any.
+  std::vector<std::unique_ptr<GenericCycle>> Children;
+
+  /// Basic blocks that are contained in the cycle, including entry blocks,
+  /// and including blocks that are part of a child cycle.
+  std::vector<BlockT *> Blocks;
+
+  /// Depth of the cycle in the tree. The root "cycle" is at depth 0.
+  ///
+  /// \note Depths are not necessarily contiguous. However, child loops always
+  ///       have strictly greater depth than their parents, and sibling loops
+  ///       always have the same depth.
+  unsigned Depth = 0;
+
+  void clear() {
+    Entries.clear();
+    Children.clear();
+    Blocks.clear();
+    Depth = 0;
+    ParentCycle = nullptr;
+  }
+
+  void appendEntry(BlockT *Block) { Entries.push_back(Block); }
+  void appendBlock(BlockT *Block) { Blocks.push_back(Block); }
+
+  GenericCycle(const GenericCycle &) = delete;
+  GenericCycle &operator=(const GenericCycle &) = delete;
+  GenericCycle(GenericCycle &&Rhs) = delete;
+  GenericCycle &operator=(GenericCycle &&Rhs) = delete;
+
+public:
+  GenericCycle() = default;
+
+  /// \brief Whether the cycle is a natural loop.
+  bool isReducible() const { return Entries.size() == 1; }
+
+  BlockT *getHeader() const { return Entries[0]; }
+
+  /// \brief Return whether \p Block is an entry block of the cycle.
+  bool isEntry(BlockT *Block) const { return is_contained(Entries, Block); }
+
+  /// \brief Return whether \p Block is contained in the cycle.
+  bool contains(const BlockT *Block) const {
+    return is_contained(Blocks, Block);
+  }
+
+  /// \brief Returns true iff this cycle contains \p C.
+  ///
+  /// Note: Non-strict containment check, i.e. returns true if C is the
+  /// same cycle.
+  bool contains(const GenericCycle *C) const;
+
+  const GenericCycle *getParentCycle() const { return ParentCycle; }
+  GenericCycle *getParentCycle() { return ParentCycle; }
+  unsigned getDepth() const { return Depth; }
+
+  /// Return all of the successor blocks of this cycle.
+  ///
+  /// These are the blocks _outside of the current cycle_ which are
+  /// branched to.
+  void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
+
+  /// Iteration over child cycles.
+  //@{
+  using const_child_iterator_base =
+      typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
+  struct const_child_iterator
+      : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
+    using Base =
+        iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;
+
+    const_child_iterator() = default;
+    explicit const_child_iterator(const_child_iterator_base I) : Base(I) {}
+
+    const const_child_iterator_base &wrapped() { return Base::wrapped(); }
+    GenericCycle *operator*() const { return Base::I->get(); }
+  };
+
+  const_child_iterator child_begin() const {
+    return const_child_iterator{Children.begin()};
+  }
+  const_child_iterator child_end() const {
+    return const_child_iterator{Children.end()};
+  }
+  size_t getNumChildren() const { return Children.size(); }
+  iterator_range<const_child_iterator> children() const {
+    return llvm::make_range(const_child_iterator{Children.begin()},
+                            const_child_iterator{Children.end()});
+  }
+  //@}
+
+  /// Iteration over blocks in the cycle (including entry blocks).
+  //@{
+  using const_block_iterator = typename std::vector<BlockT *>::const_iterator;
+
+  const_block_iterator block_begin() const {
+    return const_block_iterator{Blocks.begin()};
+  }
+  const_block_iterator block_end() const {
+    return const_block_iterator{Blocks.end()};
+  }
+  size_t getNumBlocks() const { return Blocks.size(); }
+  iterator_range<const_block_iterator> blocks() const {
+    return llvm::make_range(block_begin(), block_end());
+  }
+  //@}
+
+  /// Iteration over entry blocks.
+  //@{
+  using const_entry_iterator =
+      typename SmallVectorImpl<BlockT *>::const_iterator;
+
+  size_t getNumEntries() const { return Entries.size(); }
+  iterator_range<const_entry_iterator> entries() const {
+    return llvm::make_range(Entries.begin(), Entries.end());
+  }
+
+  Printable printEntries(const ContextT &Ctx) const {
+    return Printable([this, &Ctx](raw_ostream &Out) {
+      bool First = true;
+      for (auto *Entry : Entries) {
+        if (!First)
+          Out << ' ';
+        First = false;
+        Out << Ctx.print(Entry);
+      }
+    });
+  }
+
+  Printable print(const ContextT &Ctx) const {
+    return Printable([this, &Ctx](raw_ostream &Out) {
+      Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';
+
+      for (auto *Block : Blocks) {
+        if (isEntry(Block))
+          continue;
+
+        Out << ' ' << Ctx.print(Block);
+      }
+    });
+  }
+};
+
+/// \brief Cycle information for a function.
+template <typename ContextT> class GenericCycleInfo {
+public:
+  using BlockT = typename ContextT::BlockT;
+  using CycleT = GenericCycle<ContextT>;
+  using FunctionT = typename ContextT::FunctionT;
+  template <typename> friend class GenericCycle;
+  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.
+  ///
+  /// 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;
+  GenericCycleInfo &operator=(GenericCycleInfo &&) = default;
+
+  void clear();
+  void compute(FunctionT &F);
+
+  FunctionT *getFunction() const { return Context.getFunction(); }
+  const ContextT &getSSAContext() const { return Context; }
+
+  CycleT *getCycle(const BlockT *Block) const;
+  CycleT *getTopLevelParentCycle(const BlockT *Block) const;
+
+  /// Move \p Child to \p NewParent by manipulating Children vectors.
+  ///
+  /// Note: This is an incomplete operation that does not update the
+  /// list of blocks in the new parent or the depth of the subtree.
+  void moveToNewParent(CycleT *NewParent, CycleT *Child);
+
+  /// Methods for debug and self-test.
+  //@{
+  bool validateTree() const;
+  void print(raw_ostream &Out) const;
+  void dump() const { print(dbgs()); }
+  //@}
+
+  /// Iteration over top-level cycles.
+  //@{
+  using const_toplevel_iterator_base =
+      typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
+  struct const_toplevel_iterator
+      : iterator_adaptor_base<const_toplevel_iterator,
+                              const_toplevel_iterator_base> {
+    using Base = iterator_adaptor_base<const_toplevel_iterator,
+                                       const_toplevel_iterator_base>;
+
+    const_toplevel_iterator() = default;
+    explicit const_toplevel_iterator(const_toplevel_iterator_base I)
+        : Base(I) {}
+
+    const const_toplevel_iterator_base &wrapped() { return Base::wrapped(); }
+    CycleT *operator*() const { return Base::I->get(); }
+  };
+
+  const_toplevel_iterator toplevel_begin() const {
+    return const_toplevel_iterator{TopLevelCycles.begin()};
+  }
+  const_toplevel_iterator toplevel_end() const {
+    return const_toplevel_iterator{TopLevelCycles.end()};
+  }
+
+  iterator_range<const_toplevel_iterator> toplevel_cycles() const {
+    return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},
+                            const_toplevel_iterator{TopLevelCycles.end()});
+  }
+  //@}
+};
+
+/// \brief GraphTraits for iterating over a sub-tree of the CycleT tree.
+template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {
+  using NodeRef = CycleRefT;
+
+  using nodes_iterator = ChildIteratorT;
+  using ChildIteratorType = nodes_iterator;
+
+  static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
+
+  static ChildIteratorType child_begin(NodeRef Ref) {
+    return Ref->child_begin();
+  }
+  static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); }
+
+  // Not implemented:
+  // static nodes_iterator nodes_begin(GraphType *G)
+  // static nodes_iterator nodes_end  (GraphType *G)
+  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+
+  // typedef EdgeRef           - Type of Edge token in the graph, which should
+  //                             be cheap to copy.
+  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
+  //                             graph, dereference to a EdgeRef.
+
+  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
+  // static ChildEdgeIteratorType child_edge_end(NodeRef)
+  //     Return iterators that point to the beginning and ending of the
+  //     edge list for the given callgraph node.
+  //
+  // static NodeRef edge_dest(EdgeRef)
+  //     Return the destination node of an edge.
+  // static unsigned       size       (GraphType *G)
+  //    Return total number of nodes in the graph
+};
+
+template <typename BlockT>
+struct GraphTraits<const GenericCycle<BlockT> *>
+    : CycleGraphTraits<const GenericCycle<BlockT> *,
+                       typename GenericCycle<BlockT>::const_child_iterator> {};
+template <typename BlockT>
+struct GraphTraits<GenericCycle<BlockT> *>
+    : CycleGraphTraits<GenericCycle<BlockT> *,
+                       typename GenericCycle<BlockT>::const_child_iterator> {};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_GENERICCYCLEINFO_H

llvm/include/llvm/ADT/GenericSSAContext.h

+//===- GenericSSAContext.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines the little GenericSSAContext<X> template class
+/// that can be used to implement IR analyses as templates.
+/// Specializing these templates allows the analyses to be used over
+/// both LLVM IR and Machine IR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_GENERICSSACONTEXT_H
+#define LLVM_ADT_GENERICSSACONTEXT_H
+
+#include "llvm/Support/Printable.h"
+
+namespace llvm {
+
+template <typename _FunctionT> class GenericSSAContext {
+public:
+  // Specializations should provide the following types that are similar to how
+  // LLVM IR is structured:
+
+  // The smallest unit of the IR is a ValueT. The SSA context uses a ValueRefT,
+  // which is a pointer to a ValueT, since Machine IR does not have the
+  // equivalent of a ValueT.
+  //
+  // using ValueRefT = ...
+
+  // An InstT is a subclass of ValueT that itself defines one or more ValueT
+  // objects.
+  //
+  // using InstT = ... must be a subclass of Value
+
+  // A BlockT is a sequence of InstT, and forms a node of the CFG. It
+  // has global methods predecessors() and successors() that return
+  // the list of incoming CFG edges and outgoing CFG edges
+  // respectively.
+  //
+  // using BlockT = ...
+
+  // A FunctionT represents a CFG along with arguments and return values. It is
+  // the smallest complete unit of code in a Module.
+  //
+  // The compiler produces an error here if this class is implicitly
+  // specialized due to an instantiation. An explicit specialization
+  // of this template needs to be added before the instantiation point
+  // indicated by the compiler.
+  using FunctionT = typename _FunctionT::invalidTemplateInstanceError;
+
+  // Every FunctionT has a unique BlockT marked as its entry.
+  //
+  // static BlockT* getEntryBlock(FunctionT &F);
+
+  // Initialize the SSA context with information about the FunctionT being
+  // processed.
+  //
+  // void setFunction(FunctionT &function);
+  // FunctionT* getFunction() const;
+
+  // Methods to print various objects.
+  //
+  // Printable print(BlockT *block) const;
+  // Printable print(InstructionT *inst) const;
+  // Printable print(ValueRefT value) const;
+};
+} // namespace llvm
+
+#endif // LLVM_ADT_GENERICSSACONTEXT_H

llvm/include/llvm/Analysis/CycleAnalysis.h

+//===- CycleAnalysis.h - Cycle Info for LLVM IR -----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file declares an analysis pass that computes CycleInfo for
+/// LLVM IR, specialized from GenericCycleInfo.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CYCLEANALYSIS_H
+#define LLVM_ANALYSIS_CYCLEANALYSIS_H
+
+#include "llvm/ADT/GenericCycleInfo.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/SSAContext.h"
+
+namespace llvm {
+extern template class GenericCycleInfo<SSAContext>;
+extern template class GenericCycle<SSAContext>;
+
+using CycleInfo = GenericCycleInfo<SSAContext>;
+using Cycle = CycleInfo::CycleT;
+
+/// Analysis pass which computes a \ref CycleInfo.
+class CycleAnalysis : public AnalysisInfoMixin<CycleAnalysis> {
+  friend AnalysisInfoMixin<CycleAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  /// Provide the result typedef for this analysis pass.
+  using Result = CycleInfo;
+
+  /// Run the analysis pass over a function and produce a dominator tree.
+  CycleInfo run(Function &F, FunctionAnalysisManager &);
+
+  // TODO: verify analysis?
+};
+
+/// Printer pass for the \c DominatorTree.
+class CycleInfoPrinterPass : public PassInfoMixin<CycleInfoPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit CycleInfoPrinterPass(raw_ostream &OS);
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Legacy analysis pass which computes a \ref CycleInfo.
+class CycleInfoWrapperPass : public FunctionPass {
+  Function *F = nullptr;
+  CycleInfo CI;
+
+public:
+  static char ID;
+
+  CycleInfoWrapperPass();
+
+  CycleInfo &getCycleInfo() { return CI; }
+  const CycleInfo &getCycleInfo() const { return CI; }
+
+  bool runOnFunction(Function &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+
+  // TODO: verify analysis?
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_CYCLEANALYSIS_H

llvm/include/llvm/CodeGen/MachineCycleAnalysis.h

+//===- MachineCycleAnalysis.h - Cycle Info for Machine IR -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the MachineCycleInfo class, which is a thin wrapper over
+// the Machine IR instance of GenericCycleInfo.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINECYCLEANALYSIS_H
+#define LLVM_CODEGEN_MACHINECYCLEANALYSIS_H
+
+#include "llvm/ADT/GenericCycleInfo.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineSSAContext.h"
+
+namespace llvm {
+
+extern template class GenericCycleInfo<MachineSSAContext>;
+extern template class GenericCycle<MachineSSAContext>;
+
+using MachineCycleInfo = GenericCycleInfo<MachineSSAContext>;
+using MachineCycle = MachineCycleInfo::CycleT;
+
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_MACHINECYCLEANALYSIS_H

llvm/include/llvm/CodeGen/MachinePassRegistry.def

 DUMMY_MACHINE_FUNCTION_PASS("ra-greedy", RAGreedyPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("ra-pbqp", RAPBQPPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("legalizer", LegalizerPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("irtranslator", IRTranslatorPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("regbankselect", RegBankSelectPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("instruction-select", InstructionSelectPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("reset-machine-function", ResetMachineFunctionPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("machineverifier", MachineVerifierPass, ())
+DUMMY_MACHINE_FUNCTION_PASS("machine-cycles", MachineCycleInfoWrapperPass, ())
+DUMMY_MACHINE_FUNCTION_PASS("print-machine-cycles", MachineCycleInfoPrinterPass, ())
 #undef DUMMY_MACHINE_FUNCTION_PASS

llvm/include/llvm/CodeGen/MachineSSAContext.h

+//===- MachineSSAContext.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file declares a specialization of the GenericSSAContext<X>
+/// template class for Machine IR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINESSACONTEXT_H
+#define LLVM_CODEGEN_MACHINESSACONTEXT_H
+
+#include "llvm/ADT/GenericSSAContext.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Printable.h"
+
+#include <memory>
+
+namespace llvm {
+class MachineInstr;
+class MachineBasicBlock;
+class MachineFunction;
+class Register;
+template <typename, bool> class DominatorTreeBase;
+
+inline auto successors(MachineBasicBlock *BB) { return BB->successors(); }
+inline auto predecessors(MachineBasicBlock *BB) { return BB->predecessors(); }
+
+template <> class GenericSSAContext<MachineFunction> {
+  const MachineRegisterInfo *RegInfo = nullptr;
+  MachineFunction *MF;
+
+public:
+  using BlockT = MachineBasicBlock;
+  using FunctionT = MachineFunction;
+  using InstructionT = MachineInstr;
+  using ValueRefT = Register;
+  using DominatorTreeT = DominatorTreeBase<BlockT, false>;
+
+  static MachineBasicBlock *getEntryBlock(MachineFunction &F);
+
+  void setFunction(MachineFunction &Fn);
+  MachineFunction *getFunction() const { return MF; }
+
+  Printable print(MachineBasicBlock *Block) const;
+  Printable print(MachineInstr *Inst) const;
+  Printable print(Register Value) const;
+};
+
+using MachineSSAContext = GenericSSAContext<MachineFunction>;
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_MACHINESSACONTEXT_H

llvm/include/llvm/IR/SSAContext.h

+//===- SSAContext.h ---------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file declares a specialization of the GenericSSAContext<X>
+/// class template for LLVM IR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_SSACONTEXT_H
+#define LLVM_IR_SSACONTEXT_H
+
+#include "llvm/ADT/GenericSSAContext.h"
+#include "llvm/IR/ModuleSlotTracker.h"
+#include "llvm/Support/Printable.h"
+
+#include <memory>
+
+namespace llvm {
+class BasicBlock;
+class Function;
+class Instruction;
+class Value;
+template <typename> class SmallVectorImpl;
+template <typename, bool> class DominatorTreeBase;
+
+template <> class GenericSSAContext<Function> {
+  Function *F;
+
+public:
+  using BlockT = BasicBlock;
+  using FunctionT = Function;
+  using InstructionT = Instruction;
+  using ValueRefT = Value *;
+  using DominatorTreeT = DominatorTreeBase<BlockT, false>;
+
+  static BasicBlock *getEntryBlock(Function &F);
+
+  void setFunction(Function &Fn);
+  Function *getFunction() const { return F; }
+
+  Printable print(BasicBlock *Block) const;
+  Printable print(Instruction *Inst) const;
+  Printable print(Value *Value) const;
+};
+
+using SSAContext = GenericSSAContext<Function>;
+
+} // namespace llvm
+
+#endif // LLVM_IR_SSACONTEXT_H

llvm/include/llvm/InitializePasses.h

 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCheckDebugMachineModulePass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstraintEliminationPass(PassRegistry &);
 void initializeControlHeightReductionLegacyPassPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
+void initializeCycleInfoWrapperPassPass(PassRegistry &);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDFAJumpThreadingLegacyPassPass(PassRegistry &);
 void initializeDSELegacyPassPass(PassRegistry&);
 void initializeDataFlowSanitizerLegacyPassPass(PassRegistry &);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDebugifyMachineModulePass(PassRegistry &);

 void initializeMIRPrintingPassPass(PassRegistry&);
 void initializeMachineBlockFrequencyInfoPass(PassRegistry&);
 void initializeMachineBlockPlacementPass(PassRegistry&);
 void initializeMachineBlockPlacementStatsPass(PassRegistry&);
 void initializeMachineBranchProbabilityInfoPass(PassRegistry&);
 void initializeMachineCSEPass(PassRegistry&);
 void initializeMachineCombinerPass(PassRegistry&);
 void initializeMachineCopyPropagationPass(PassRegistry&);
+void initializeMachineCycleInfoPrinterPassPass(PassRegistry &);
+void initializeMachineCycleInfoWrapperPassPass(PassRegistry &);
 void initializeMachineDominanceFrontierPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);
 void initializeMachineFunctionPrinterPassPass(PassRegistry&);
 void initializeMachineFunctionSplitterPass(PassRegistry &);
 void initializeMachineLICMPass(PassRegistry&);
 void initializeMachineLoopInfoPass(PassRegistry&);
 void initializeMachineModuleInfoWrapperPassPass(PassRegistry &);
 void initializeMachineOptimizationRemarkEmitterPassPass(PassRegistry&);

 void initializeTailDuplicatePass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerLegacyPassPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
 void initializeTypePromotionPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesLegacyPassPass(PassRegistry &);
 void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &);
 void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVectorCombineLegacyPassPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);
 void initializeVirtRegMapPass(PassRegistry&);
 void initializeVirtRegRewriterPass(PassRegistry&);

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerLegacyPassPass(Registry);
   initializeCFGPrinterLegacyPassPass(Registry);
   initializeCFGOnlyViewerLegacyPassPass(Registry);
   initializeCFGOnlyPrinterLegacyPassPass(Registry);
   initializeCFLAndersAAWrapperPassPass(Registry);
   initializeCFLSteensAAWrapperPassPass(Registry);
+  initializeCycleInfoWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  CycleAnalysis.cpp
   DDG.cpp
   DDGPrinter.cpp
   ConstraintSystem.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DependenceGraphBuilder.cpp
   DevelopmentModeInlineAdvisor.cpp

llvm/lib/Analysis/CycleAnalysis.cpp

+//===- CycleAnalysis.cpp - Compute CycleInfo for LLVM IR ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CycleAnalysis.h"
+#include "llvm/ADT/GenericCycleImpl.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/InitializePasses.h"
+
+using namespace llvm;
+
+template class llvm::GenericCycleInfo<SSAContext>;
+template class llvm::GenericCycle<SSAContext>;
+
+CycleInfo CycleAnalysis::run(Function &F, FunctionAnalysisManager &) {
+  CycleInfo CI;
+  CI.compute(F);
+  return CI;
+}
+
+AnalysisKey CycleAnalysis::Key;
+
+CycleInfoPrinterPass::CycleInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
+
+PreservedAnalyses CycleInfoPrinterPass::run(Function &F,
+                                            FunctionAnalysisManager &AM) {
+  OS << "CycleInfo for function: " << F.getName() << "\n";
+  AM.getResult<CycleAnalysis>(F).print(OS);
+
+  return PreservedAnalyses::all();
+}
+
+//===----------------------------------------------------------------------===//
+//  CycleInfoWrapperPass Implementation
+//===----------------------------------------------------------------------===//
+//
+// The implementation details of the wrapper pass that holds a CycleInfo
+// suitable for use with the legacy pass manager.
+//
+//===----------------------------------------------------------------------===//
+
+char CycleInfoWrapperPass::ID = 0;
+
+CycleInfoWrapperPass::CycleInfoWrapperPass() : FunctionPass(ID) {
+  initializeCycleInfoWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+INITIALIZE_PASS_BEGIN(CycleInfoWrapperPass, "cycles", "Cycle Info Analysis",
+                      true, true)
+INITIALIZE_PASS_END(CycleInfoWrapperPass, "cycles", "Cycle Info Analysis", true,
+                    true)
+
+void CycleInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+bool CycleInfoWrapperPass::runOnFunction(Function &Func) {
+  CI.clear();
+
+  F = &Func;
+  CI.compute(Func);
+  return false;
+}
+
+void CycleInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  OS << "CycleInfo for function: " << F->getName() << "\n";
+  CI.print(OS);
+}
+
+void CycleInfoWrapperPass::releaseMemory() {
+  CI.clear();
+  F = nullptr;
+}

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   MachineBasicBlock.cpp
   MachineBlockFrequencyInfo.cpp
   MachineBlockPlacement.cpp
   MachineBranchProbabilityInfo.cpp
   MachineCombiner.cpp
   MachineCopyPropagation.cpp
   MachineCSE.cpp
   MachineCheckDebugify.cpp
+  MachineCycleAnalysis.cpp
   MachineDebugify.cpp
   MachineDominanceFrontier.cpp
   MachineDominators.cpp
   MachineFrameInfo.cpp
   MachineFunction.cpp
   MachineFunctionPass.cpp
   MachineFunctionPrinterPass.cpp
   MachineFunctionSplitter.cpp
add_llvm_component_library(LLVMCodeGen
   MachinePassManager.cpp
   MachinePipeliner.cpp
   MachinePostDominators.cpp
   MachineRegionInfo.cpp
   MachineRegisterInfo.cpp
   MachineScheduler.cpp
   MachineSink.cpp
   MachineSizeOpts.cpp
+  MachineSSAContext.cpp
   MachineSSAUpdater.cpp
   MachineStripDebug.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
   MIRFSDiscriminator.cpp
   MIRSampleProfile.cpp
   MIRYamlMapping.cpp
   ModuloSchedule.cpp

llvm/lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeMIRNamerPass(Registry);
   initializeMIRProfileLoaderPassPass(Registry);
   initializeMachineBlockFrequencyInfoPass(Registry);
   initializeMachineBlockPlacementPass(Registry);
   initializeMachineBlockPlacementStatsPass(Registry);
   initializeMachineCSEPass(Registry);
   initializeMachineCombinerPass(Registry);
   initializeMachineCopyPropagationPass(Registry);
+  initializeMachineCycleInfoPrinterPassPass(Registry);
+  initializeMachineCycleInfoWrapperPassPass(Registry);
   initializeMachineDominatorTreePass(Registry);
   initializeMachineFunctionPrinterPassPass(Registry);
   initializeMachineLICMPass(Registry);
   initializeMachineLoopInfoPass(Registry);
   initializeMachineModuleInfoWrapperPassPass(Registry);
   initializeMachineOptimizationRemarkEmitterPassPass(Registry);
   initializeMachineOutlinerPass(Registry);
   initializeMachinePipelinerPass(Registry);

llvm/lib/CodeGen/MachineCycleAnalysis.cpp

+//===- MachineCycleAnalysis.cpp - Compute CycleInfo for Machine IR --------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineCycleAnalysis.h"
+#include "llvm/ADT/GenericCycleImpl.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineSSAContext.h"
+#include "llvm/InitializePasses.h"
+
+using namespace llvm;
+
+template class llvm::GenericCycleInfo<llvm::MachineSSAContext>;
+template class llvm::GenericCycle<llvm::MachineSSAContext>;
+
+namespace {
+
+/// Legacy analysis pass which computes a \ref MachineCycleInfo.
+class MachineCycleInfoWrapperPass : public MachineFunctionPass {
+  MachineFunction *F = nullptr;
+  MachineCycleInfo CI;
+
+public:
+  static char ID;
+
+  MachineCycleInfoWrapperPass();
+
+  MachineCycleInfo &getCycleInfo() { return CI; }
+  const MachineCycleInfo &getCycleInfo() const { return CI; }
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+
+  // TODO: verify analysis
+};
+
+class MachineCycleInfoPrinterPass : public MachineFunctionPass {
+public:
+  static char ID;
+
+  MachineCycleInfoPrinterPass();
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+} // namespace
+
+char MachineCycleInfoWrapperPass::ID = 0;
+
+MachineCycleInfoWrapperPass::MachineCycleInfoWrapperPass()
+    : MachineFunctionPass(ID) {
+  initializeMachineCycleInfoWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+INITIALIZE_PASS_BEGIN(MachineCycleInfoWrapperPass, "machine-cycles",
+                      "Machine Cycle Info Analysis", true, true)
+INITIALIZE_PASS_END(MachineCycleInfoWrapperPass, "machine-cycles",
+                    "Machine Cycle Info Analysis", true, true)
+
+void MachineCycleInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool MachineCycleInfoWrapperPass::runOnMachineFunction(MachineFunction &Func) {
+  CI.clear();
+
+  F = &Func;
+  CI.compute(Func);
+  return false;
+}
+
+void MachineCycleInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  OS << "MachineCycleInfo for function: " << F->getName() << "\n";
+  CI.print(OS);
+}
+
+void MachineCycleInfoWrapperPass::releaseMemory() {
+  CI.clear();
+  F = nullptr;
+}
+
+char MachineCycleInfoPrinterPass::ID = 0;
+
+MachineCycleInfoPrinterPass::MachineCycleInfoPrinterPass()
+    : MachineFunctionPass(ID) {
+  initializeMachineCycleInfoPrinterPassPass(*PassRegistry::getPassRegistry());
+}
+
+INITIALIZE_PASS_BEGIN(MachineCycleInfoPrinterPass, "print-machine-cycles",
+                      "Print Machine Cycle Info Analysis", true, true)
+INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
+INITIALIZE_PASS_END(MachineCycleInfoPrinterPass, "print-machine-cycles",
+                    "Print Machine Cycle Info Analysis", true, true)
+
+void MachineCycleInfoPrinterPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<MachineCycleInfoWrapperPass>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool MachineCycleInfoPrinterPass::runOnMachineFunction(MachineFunction &F) {
+  auto &CI = getAnalysis<MachineCycleInfoWrapperPass>();
+  CI.print(errs());
+  return false;
+}

llvm/lib/CodeGen/MachineSSAContext.cpp

+//===- MachineSSAContext.cpp ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines a specialization of the GenericSSAContext<X>
+/// template class for Machine IR.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineSSAContext.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+MachineBasicBlock *MachineSSAContext::getEntryBlock(MachineFunction &F) {
+  return &F.front();
+}
+
+void MachineSSAContext::setFunction(MachineFunction &Fn) {
+  MF = &Fn;
+  RegInfo = &MF->getRegInfo();
+}
+
+Printable MachineSSAContext::print(MachineBasicBlock *Block) const {
+  return Printable([Block](raw_ostream &Out) { Block->printName(Out); });
+}
+
+Printable MachineSSAContext::print(MachineInstr *I) const {
+  return Printable([I](raw_ostream &Out) { I->print(Out); });
+}
+
+Printable MachineSSAContext::print(Register Value) const {
+  auto *MRI = RegInfo;
+  return Printable([MRI, Value](raw_ostream &Out) {
+    Out << printReg(Value, MRI->getTargetRegisterInfo(), 0, MRI);
+
+    if (Value) {
+      // Try to print the definition.
+      if (auto *Instr = MRI->getUniqueVRegDef(Value)) {
+        Out << ": ";
+        Instr->print(Out);
+      }
+    }
+  });
+}

llvm/lib/IR/CMakeLists.txt

 add_llvm_component_library(LLVMCore
   AbstractCallSite.cpp
   AsmWriter.cpp
   Assumptions.cpp
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
   BuiltinGCs.cpp
   Comdat.cpp
   ConstantFold.cpp
add_llvm_component_library(LLVMCore
   Dominators.cpp
   FPEnv.cpp
   Function.cpp
   GCStrategy.cpp
   GVMaterializer.cpp
   Globals.cpp
   IRBuilder.cpp
   IRPrintingPasses.cpp
+  SSAContext.cpp
   InlineAsm.cpp
   Instruction.cpp
   Instructions.cpp
   IntrinsicInst.cpp
   LLVMContext.cpp
   LLVMContextImpl.cpp
   LLVMRemarkStreamer.cpp
   LegacyPassManager.cpp

llvm/lib/IR/SSAContext.cpp

+//===- SSAContext.cpp -------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines a specialization of the GenericSSAContext<X>
+/// template class for LLVM IR.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/SSAContext.h"
+#include "llvm/IR/Argument.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+BasicBlock *SSAContext::getEntryBlock(Function &F) {
+  return &F.getEntryBlock();
+}
+
+void SSAContext::setFunction(Function &Fn) { F = &Fn; }
+
+Printable SSAContext::print(Value *V) const {
+  return Printable([V](raw_ostream &Out) { V->print(Out); });
+}
+
+Printable SSAContext::print(Instruction *Inst) const {
+  return print(cast<Value>(Inst));
+}
+
+Printable SSAContext::print(BasicBlock *BB) const {
+  if (BB->hasName())
+    return Printable([BB](raw_ostream &Out) { Out << BB->getName(); });
+
+  return Printable([BB](raw_ostream &Out) {
+    ModuleSlotTracker MST{BB->getParent()->getParent(), false};
+    MST.incorporateFunction(*BB->getParent());
+    Out << MST.getLocalSlot(BB);
+  });
+}

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CostModel.h"
+#include "llvm/Analysis/CycleAnalysis.h"
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/DDGPrinter.h"
 #include "llvm/Analysis/Delinearization.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DivergenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"

llvm/lib/Passes/PassRegistry.def

 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis())
 FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
+FUNCTION_ANALYSIS("cycles", CycleAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("func-properties", FunctionPropertiesAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())

 FUNCTION_PASS("objc-arc-contract", ObjCARCContractPass())
 FUNCTION_PASS("objc-arc-expand", ObjCARCExpandPass())
 FUNCTION_PASS("pgo-memop-opt", PGOMemOPSizeOpt())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<cost-model>", CostModelPrinterPass(dbgs()))
+FUNCTION_PASS("print<cycles>", CycleInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<da>", DependenceAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<divergence>", DivergenceAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<delinearization>", DelinearizationPrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<func-properties>", FunctionPropertiesPrinterPass(dbgs()))

llvm/test/Analysis/CycleInfo/basic.ll

+; RUN: opt < %s -cycles -analyze -enable-new-pm=0 | FileCheck %s -check-prefix=CHECK
+; RUN: opt < %s -disable-output -passes='print<cycles>' 2>&1 | FileCheck %s -check-prefix=CHECK
+
+define void @empty() {
+; CHECK-LABEL: CycleInfo for function: empty
+; CHECK-NOT:       depth
+
+  ret void
+}
+
+define void @simple() {
+; CHECK-LABEL: CycleInfo for function: simple
+; CHECK:           depth=1: entries(loop)
+entry:
+  br label %loop
+
+loop:
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @two_latches() {
+; CHECK-LABEL: CycleInfo for function: two_latches
+; CHECK:           depth=1: entries(loop) loop_next
+entry:
+  br label %loop
+
+loop:
+  br i1 undef, label %loop, label %loop_next
+
+loop_next:
+  br i1 undef, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @nested_simple() {
+; CHECK-LABEL: CycleInfo for function: nested_simple
+; CHECK:           depth=1: entries(outer_header) outer_latch inner
+; CHECK:               depth=2: entries(inner)
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %inner
+
+inner:
+  br i1 undef, label %inner, label %outer_latch
+
+outer_latch:
+  br i1 undef, label %outer_header, label %exit
+
+exit:
+  ret void
+}
+
+define void @nested_outer_latch_in_inner_loop() {
+; CHECK-LABEL: CycleInfo for function: nested_outer_latch_in_inner_loop
+; CHECK:           depth=1: entries(outer_header) inner_header inner_latch
+; CHECK:               depth=2: entries(inner_header) inner_latch
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %inner_header
+
+inner_header:
+  br i1 undef, label %inner_latch, label %outer_header
+
+inner_latch:
+  br i1 undef, label %exit, label %inner_header
+
+exit:
+  ret void
+}
+
+define void @sibling_loops() {
+; CHECK-LABEL: CycleInfo for function: sibling_loops
+; CHECK-DAG:       depth=1: entries(left)
+; CHECK-DAG:       depth=1: entries(right)
+entry:
+  br i1 undef, label %left, label %right
+
+left:
+  br i1 undef, label %left, label %exit
+
+right:
+  br i1 undef, label %right, label %exit
+
+exit:
+  ret void
+}
+
+define void @serial_loops() {
+; CHECK-LABEL: CycleInfo for function: serial_loops
+; CHECK-DAG:       depth=1: entries(second)
+; CHECK-DAG:       depth=1: entries(first)
+entry:
+  br label %first
+
+first:
+  br i1 undef, label %first, label %second
+
+second:
+  br i1 undef, label %second, label %exit
+
+exit:
+  ret void
+}
+
+define void @nested_sibling_loops() {
+; CHECK-LABEL: CycleInfo for function: nested_sibling_loops
+; CHECK:           depth=1: entries(outer_header) left right
+; CHECK-DAG:           depth=2: entries(right)
+; CHECK-DAG:           depth=2: entries(left)
+entry:
+  br label %outer_header
+
+outer_header:
+  br i1 undef, label %left, label %right
+
+left:
+  switch i32 undef, label %exit [ i32 0, label %left
+                                  i32 1, label %outer_header ]
+
+right:
+  switch i32 undef, label %outer_header [ i32 0, label %exit
+                                          i32 1, label %right ]
+
+exit:
+  ret void
+}
+
+define void @deeper_nest() {
+; CHECK-LABEL: CycleInfo for function: deeper_nest
+; CHECK:           depth=1: entries(outer_header) outer_latch middle_header inner_header inner_latch
+; CHECK:               depth=2: entries(middle_header) inner_header inner_latch
+; CHECK:                   depth=3: entries(inner_header) inner_latch
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %middle_header
+
+middle_header:
+  br label %inner_header
+
+inner_header:
+  br i1 undef, label %middle_header, label %inner_latch
+
+inner_latch:
+  br i1 undef, label %inner_header, label %outer_latch
+
+outer_latch:
+  br i1 undef, label %outer_header, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_basic() {
+; CHECK-LABEL: CycleInfo for function: irreducible_basic
+; CHECK:           depth=1: entries(right left)
+entry:
+  br i1 undef, label %left, label %right
+
+left:
+  br i1 undef, label %right, label %exit
+
+right:
+  br i1 undef, label %left, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_mess() {
+; CHECK-LABEL: CycleInfo for function: irreducible_mess
+; CHECK:           depth=1: entries(B A) D C
+; CHECK:               depth=2: entries(D C A)
+; CHECK:                   depth=3: entries(C A)
+entry:
+  br i1 undef, label %A, label %B
+
+A:
+  br i1 undef, label %C, label %D
+
+B:
+  br i1 undef, label %C, label %D
+
+C:
+  switch i32 undef, label %A [ i32 0, label %D
+                               i32 1, label %exit ]
+
+D:
+  switch i32 undef, label %B [ i32 0, label %C
+                               i32 1, label %exit ]
+
+exit:
+  ret void
+}
+
+define void @irreducible_into_simple_cycle() {
+; CHECK-LABEL: CycleInfo for function: irreducible_into_simple_cycle
+; CHECK:           depth=1: entries(F C A) E D B
+entry:
+  switch i32 undef, label %A [ i32 0, label %C
+                               i32 1, label %F ]
+
+A:
+  br label %B
+
+B:
+  br label %C
+
+C:
+  br label %D
+
+D:
+  br i1 undef, label %E, label %exit
+
+E:
+  br label %F
+
+F:
+  br i1 undef, label %A, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_mountain_bug() {
+; CHECK-LABEL: CycleInfo for function: irreducible_mountain_bug
+; CHECK:           depth=1: entries(while.cond)
+; CHECK:               depth=2: entries(cond.end61 cond.true49) while.body63 while.cond47
+; CHECK:                   depth=3: entries(while.body63 cond.true49) while.cond47
+entry:
+  br i1 undef, label %if.end, label %if.then
+
+if.end:
+  br i1 undef, label %if.then7, label %if.else
+
+if.then7:
+  br label %if.end16
+
+if.else:
+  br label %if.end16
+
+if.end16:
+  br i1 undef, label %while.cond.preheader, label %if.then39
+
+while.cond.preheader:
+  br label %while.cond
+
+while.cond:
+  br i1 undef, label %cond.true49, label %lor.rhs
+
+cond.true49:
+  br i1 undef, label %if.then69, label %while.body63
+
+while.body63:
+  br i1 undef, label %exit, label %while.cond47
+
+while.cond47:
+  br i1 undef, label %cond.true49, label %cond.end61
+
+cond.end61:
+  br i1 undef, label %while.body63, label %while.cond
+
+if.then69:
+  br i1 undef, label %exit, label %while.cond
+
+lor.rhs:
+  br i1 undef, label %cond.end61, label %while.end76
+
+while.end76:
+  br label %exit
+
+if.then39:
+  br i1 undef, label %exit, label %if.end.i145
+
+if.end.i145:
+  br i1 undef, label %exit, label %if.end8.i149
+
+if.end8.i149:
+  br label %exit
+
+if.then:
+  br i1 undef, label %exit, label %if.end.i
+
+if.end.i:
+  br i1 undef, label %exit, label %if.end8.i
+
+if.end8.i:
+  br label %exit
+
+exit:
+  ret void
+}

llvm/test/CodeGen/X86/cycle-info.mir

+# RUN: llc -mtriple=x86_64-unknown-linux-gnu -run-pass=print-machine-cycles -o - %s 2>&1 | FileCheck %s
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: empty
+name:            empty
+alignment:       16
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: simple
+# CHECK:           depth=1: entries(bb.1)
+name:            simple
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.2:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: two_latches
+# CHECK:           depth=1: entries(bb.1) bb.2
+name:            two_latches
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.2:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.3:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: nested_simple
+# CHECK:           depth=1: entries(bb.1) bb.3 bb.2
+# CHECK:               depth=2: entries(bb.2)
+name:            nested_simple
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    JMP_1 %bb.2
+
+  bb.2:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.4:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: nested_outer_latch_in_inner_loop
+# CHECK:           depth=1: entries(bb.1) bb.2 bb.3
+# CHECK:               depth=2: entries(bb.2) bb.3
+name:            nested_outer_latch_in_inner_loop
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    JMP_1 %bb.2
+
+  bb.2:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.3:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.4, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.4:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: sibling_loops
+# CHECK:           depth=1: entries(bb.1)
+# CHECK:           depth=1: entries(bb.2)
+name:            sibling_loops
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.1:
+    %2:gr8 = IMPLICIT_DEF
+    TEST8ri %2, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.2:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: serial_loops
+# CHECK:           depth=1: entries(bb.2)
+# CHECK:           depth=1: entries(bb.1)
+name:            serial_loops
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.2:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: nested_sibling_loops
+# CHECK:           depth=1: entries(bb.1) bb.4 bb.5 bb.3 bb.2
+# CHECK:               depth=2: entries(bb.4) bb.5
+# CHECK:               depth=2: entries(bb.2)
+name:            nested_sibling_loops
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr8 }
+  - { id: 3, class: gr32 }
+  - { id: 4, class: gr8 }
+  - { id: 5, class: gr32 }
+  - { id: 6, class: gr8 }
+  - { id: 7, class: gr32 }
+  - { id: 8, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.2:
+    %5:gr32 = MOV32r0 implicit-def dead $eflags
+    %6:gr8 = COPY %5.sub_8bit
+    TEST8rr %6, %6, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.6
+
+  bb.6:
+    %7:gr32 = MOV32r0 implicit-def dead $eflags
+    %8:gr8 = COPY %7.sub_8bit
+    TEST8rr %8, %8, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.3:
+    %1:gr32 = MOV32r0 implicit-def dead $eflags
+    %2:gr8 = COPY %1.sub_8bit
+    TEST8rr %2, %2, implicit-def $eflags
+    JCC_1 %bb.4, 5, implicit $eflags
+    JMP_1 %bb.5
+
+  bb.5:
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    %4:gr8 = COPY %3.sub_8bit
+    TEST8rr %4, %4, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.4:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: deeper_nest
+# CHECK:           depth=1: entries(bb.1) bb.5 bb.2 bb.3 bb.4
+# CHECK:               depth=2: entries(bb.2) bb.3 bb.4
+# CHECK:                   depth=3: entries(bb.3) bb.4
+name:            deeper_nest
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    JMP_1 %bb.2
+
+  bb.2:
+    JMP_1 %bb.3
+
+  bb.3:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.4:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.5
+
+  bb.5:
+    %2:gr8 = IMPLICIT_DEF
+    TEST8ri %2, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.6
+
+  bb.6:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: irreducible_basic
+# CHECK:           depth=1: entries(bb.2 bb.1)
+name:            irreducible_basic
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.1:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.2:
+    %2:gr8 = IMPLICIT_DEF
+    TEST8ri %2, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: irreducible_mess
+# CHECK:           depth=1: entries(bb.2 bb.1) bb.6 bb.5 bb.3 bb.4
+# CHECK:               depth=2: entries(bb.5 bb.3 bb.1) bb.4
+# CHECK:                   depth=3: entries(bb.3 bb.1) bb.4
+name:            irreducible_mess
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr8 }
+  - { id: 4, class: gr32 }
+  - { id: 5, class: gr8 }
+  - { id: 6, class: gr32 }
+  - { id: 7, class: gr8 }
+  - { id: 8, class: gr32 }
+  - { id: 9, class: gr8 }
+  - { id: 10, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.1:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.2:
+    %10:gr8 = IMPLICIT_DEF
+    TEST8ri %10, 1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.3:
+    %2:gr32 = MOV32r0 implicit-def dead $eflags
+    %3:gr8 = COPY %2.sub_8bit
+    TEST8rr %3, %3, implicit-def $eflags
+    JCC_1 %bb.4, 5, implicit $eflags
+    JMP_1 %bb.6
+
+  bb.6:
+    %4:gr32 = MOV32r0 implicit-def dead $eflags
+    %5:gr8 = COPY %4.sub_8bit
+    TEST8rr %5, %5, implicit-def $eflags
+    JCC_1 %bb.5, 5, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.4:
+    %6:gr32 = MOV32r0 implicit-def dead $eflags
+    %7:gr8 = COPY %6.sub_8bit
+    TEST8rr %7, %7, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.7
+
+  bb.7:
+    successors: %bb.5, %bb.2
+
+    %8:gr32 = MOV32r0 implicit-def dead $eflags
+    %9:gr8 = COPY %8.sub_8bit
+    TEST8rr %9, %9, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.5
+
+  bb.5:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: irreducible_into_simple_cycle
+# CHECK:           depth=1: entries(bb.2 bb.7 bb.4) bb.6 bb.5 bb.3
+name:            irreducible_into_simple_cycle
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr8 }
+  - { id: 4, class: gr8 }
+  - { id: 5, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    %0:gr32 = MOV32r0 implicit-def dead $eflags
+    %1:gr8 = COPY %0.sub_8bit
+    TEST8rr %1, %1, implicit-def $eflags
+    JCC_1 %bb.3, 5, implicit $eflags
+    JMP_1 %bb.8
+
+  bb.8:
+    %2:gr32 = MOV32r0 implicit-def dead $eflags
+    %3:gr8 = COPY %2.sub_8bit
+    TEST8rr %3, %3, implicit-def $eflags
+    JCC_1 %bb.6, 5, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.1:
+    JMP_1 %bb.2
+
+  bb.2:
+    JMP_1 %bb.3
+
+  bb.3:
+    JMP_1 %bb.4
+
+  bb.4:
+    %4:gr8 = IMPLICIT_DEF
+    TEST8ri %4, 1, implicit-def $eflags
+    JCC_1 %bb.5, 5, implicit $eflags
+    JMP_1 %bb.7
+
+  bb.5:
+    JMP_1 %bb.6
+
+  bb.6:
+    %5:gr8 = IMPLICIT_DEF
+    TEST8ri %5, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.7
+
+  bb.7:
+    RET64
+
+...
+---
+# CHECK-LABEL: MachineCycleInfo for function: irreducible_mountain_bug
+# CHECK:           depth=1: entries(bb.6) bb.11 bb.10 bb.8 bb.7 bb.9 bb.12
+# CHECK:               depth=2: entries(bb.10 bb.7) bb.8 bb.9
+# CHECK:                   depth=3: entries(bb.8 bb.7) bb.9
+name:            irreducible_mountain_bug
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr8 }
+  - { id: 2, class: gr8 }
+  - { id: 3, class: gr8 }
+  - { id: 4, class: gr8 }
+  - { id: 5, class: gr8 }
+  - { id: 6, class: gr8 }
+  - { id: 7, class: gr8 }
+  - { id: 8, class: gr8 }
+  - { id: 9, class: gr8 }
+  - { id: 10, class: gr8 }
+  - { id: 11, class: gr8 }
+  - { id: 12, class: gr8 }
+  - { id: 13, class: gr8 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    %0:gr8 = IMPLICIT_DEF
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.17
+
+  bb.1:
+    %3:gr8 = IMPLICIT_DEF
+    TEST8ri %3, 1, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit $eflags
+    JMP_1 %bb.3
+
+  bb.2:
+    JMP_1 %bb.4
+
+  bb.3:
+    JMP_1 %bb.4
+
+  bb.4:
+    %4:gr8 = IMPLICIT_DEF
+    TEST8ri %4, 1, implicit-def $eflags
+    JCC_1 %bb.5, 5, implicit $eflags
+    JMP_1 %bb.14
+
+  bb.5:
+    JMP_1 %bb.6
+
+  bb.6:
+    %7:gr8 = IMPLICIT_DEF
+    TEST8ri %7, 1, implicit-def $eflags
+    JCC_1 %bb.7, 5, implicit $eflags
+    JMP_1 %bb.12
+
+  bb.7:
+    %9:gr8 = IMPLICIT_DEF
+    TEST8ri %9, 1, implicit-def $eflags
+    JCC_1 %bb.11, 5, implicit $eflags
+    JMP_1 %bb.8
+
+  bb.8:
+    %10:gr8 = IMPLICIT_DEF
+    TEST8ri %10, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.9
+
+  bb.9:
+    %11:gr8 = IMPLICIT_DEF
+    TEST8ri %11, 1, implicit-def $eflags
+    JCC_1 %bb.7, 5, implicit $eflags
+    JMP_1 %bb.10
+
+  bb.10:
+    %12:gr8 = IMPLICIT_DEF
+    TEST8ri %12, 1, implicit-def $eflags
+    JCC_1 %bb.8, 5, implicit $eflags
+    JMP_1 %bb.6
+
+  bb.11:
+    %13:gr8 = IMPLICIT_DEF
+    TEST8ri %13, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.6
+
+  bb.12:
+    %8:gr8 = IMPLICIT_DEF
+    TEST8ri %8, 1, implicit-def $eflags
+    JCC_1 %bb.10, 5, implicit $eflags
+    JMP_1 %bb.13
+
+  bb.13:
+    JMP_1 %bb.20
+
+  bb.14:
+    %5:gr8 = IMPLICIT_DEF
+    TEST8ri %5, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.15
+
+  bb.15:
+    %6:gr8 = IMPLICIT_DEF
+    TEST8ri %6, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.16
+
+  bb.16:
+    JMP_1 %bb.20
+
+  bb.17:
+    %1:gr8 = IMPLICIT_DEF
+    TEST8ri %1, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.18
+
+  bb.18:
+    %2:gr8 = IMPLICIT_DEF
+    TEST8ri %2, 1, implicit-def $eflags
+    JCC_1 %bb.20, 5, implicit $eflags
+    JMP_1 %bb.19
+
+  bb.19:
+    JMP_1 %bb.20
+
+  bb.20:
+    RET64
+
+...