Introduce CfgTraits abstraction

[nhaehnle]

Summary

The CfgTraits abstraction simplfies writing algorithms that are
generic over the type of CFG, and enables writing such algorithms
as regular non-template code that operates on opaque references
to CFG blocks and values.

Implementations of CfgTraits provide operations on the concrete
CFG types, e.g. IrCfgTraits::BlockRef is BasicBlock *.

CfgInterface is an abstract base class which provides operations
on opaque types CfgBlockRef and CfgValueRef. Those opaque types
encapsulate a void *, but the meaning depends on the concrete
CFG type. For example, MachineCfgTraits -- for use with MachineIR
in SSA form -- encodes a Register inside CfgValueRef. Converting
between concrete references and opaque/generic ones is done by
CfgTraits::{fromGeneric,toGeneric}. Convenience methods
CfgTraits::{un}wrap{Iterator,Range} are available as well.

Writing algorithms in terms of CfgInterface adds some overhead
(virtual method calls, plus in same cases it removes the
opportunity to inline iterators), but can be much more convenient
since generic algorithms can be written as non-templates.

This patch adds implementations of CfgTraits for all CFGs on
which dominator trees are calculated, so that the dominator
tree can be ported to this machinery. Only IrCfgTraits (LLVM IR)
and MachineCfgTraits (Machine IR in SSA form) are complete, the
other implementations are limited to the absolute minimum
required to make the upcoming dominator tree changes work.

Change-Id: Ia75f4f268fded33fca11218a7d578c9aec1f3f4d

[arsenm]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

134

!= return early?

137–139

I've been thinking about more aggressively using bundles around call sites to handle waterfall looping around divergent calls with SGPR arguments

[arsenm]

llvm/lib/CodeGen/MachineCfgTraits.cpp

28–30

I think this should be added to MachineBasicBlock. The same logic is already repeated in MIRPrinter (and the MBB dump function uses a different prefix)

33

Single quotes around .

[nhaehnle]

• fix MachineCfgTraits::blockdef_iterator and allow it to iterate over the instructions in a bundle
• use MachineBasicBlock::printName

[nhaehnle]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

134

The logic is actually subtly broken in the presence of instructions without defs, I just didn't notice it because it currently affects only debug printing logic. Going to fix it.

137–139

Hmm, so what's the correct iteration behavior in the presence of bundles? Iterate over all instructions in the bundle (which is that MachineBasicBlock::instr_iterator does) and only iterate over explicit defs? I think that's what makes the most sense, and what I'm going with for now...

llvm/lib/CodeGen/MachineCfgTraits.cpp

28–30

D83253

[arsenm]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

137–139

I don't think this actually needs to specially consider bundles. The BUNDLE itself is supposed to have the uses/defs that cover all the uses/defs inside the bundle. You shouldn't need to worry about the individual instructions

[nhaehnle]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

137–139

This is what should be there with the last change :)

[arsenm]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

45

I feel like there should be a better way to do this; we should probably have an assert where virtual registers are created

102

I think regular getVRegDef is preferable for SSA MIR

[nhaehnle]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

45

The reason for doing it here is that this is the place where the reinterpret happens. If the check is elsewhere, it's easy to miss by a user of this.

102

Fixed locally.

[nhaehnle]

v6:
- implement predecessors/successors for all CfgTraits implementations
- fix error in unwrapRange
- rename toGeneric/fromGeneric into wrapRef/unwrapRef to have naming
  that is consistent with {wrap,unwrap}{Iterator,Range}
- use getVRegDef instead of getUniqueVRegDef

[arsenm]

clang/include/clang/Analysis/Analyses/Dominators.h

50

Missing space nullpointers, missing s succesors

51

s/it's/its/

[nhaehnle]

v7:
- std::forward fix in wrapping_iterator
- fix typos

[dblaikie]

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

[nhaehnle]

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

[dblaikie]

In D83088#2213797, @nhaehnle wrote:

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

Could it be implemented statically as a primary interface, with a dynamic wrapper? (eg: a base class, then a derived class template that takes the static CFG type to wrap into the dynamic type) keeping the two concepts more clearly separated?

[nhaehnle]

In D83088#2213802, @dblaikie wrote:

In D83088#2213797, @nhaehnle wrote:

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

Could it be implemented statically as a primary interface, with a dynamic wrapper? (eg: a base class, then a derived class template that takes the static CFG type to wrap into the dynamic type) keeping the two concepts more clearly separated?

That is how it is implemented. CfgTraits is the primary static interface, and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.

[dblaikie]

In D83088#2213864, @nhaehnle wrote:

In D83088#2213802, @dblaikie wrote:

In D83088#2213797, @nhaehnle wrote:

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

Could it be implemented statically as a primary interface, with a dynamic wrapper? (eg: a base class, then a derived class template that takes the static CFG type to wrap into the dynamic type) keeping the two concepts more clearly separated?

That is how it is implemented. CfgTraits is the primary static interface, and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.

Ah, fair enough. The inheritance details in the traits class confused me a bit/I had a hard time following, with all the features being in the one patch. Might be easier separately, but not sure.

Would it be possible for this not to use traits - I know @asbirlea and I had trouble with some things using GraphTraits owing to the traits API. An alternative would be to describe a CFGGraph concept (same as a standard container concept, for instance) - where there is a concrete graph object and that object is queried for things like nodes, edges, etc. (actually one of the significant things we tripped over was the API choice to navigate edges from a node itself without any extra state - which meant nodes/edge iteration had to carry state (potentially pointers back to the graph, etc) to be able to manifest their edges - trait or concept could both address this by, for traits, passing the graph as well as the node when querying the trait for edges, or for a concept passing the node back to the graph to query for edges).

[nhaehnle]

In D83088#2213886, @dblaikie wrote:

In D83088#2213864, @nhaehnle wrote:

In D83088#2213802, @dblaikie wrote:

In D83088#2213797, @nhaehnle wrote:

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

Could it be implemented statically as a primary interface, with a dynamic wrapper? (eg: a base class, then a derived class template that takes the static CFG type to wrap into the dynamic type) keeping the two concepts more clearly separated?

That is how it is implemented. CfgTraits is the primary static interface, and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.

Ah, fair enough. The inheritance details in the traits class confused me a bit/I had a hard time following, with all the features being in the one patch. Might be easier separately, but not sure.

Would it be possible for this not to use traits - I know @asbirlea and I had trouble with some things using GraphTraits owing to the traits API. An alternative would be to describe a CFGGraph concept (same as a standard container concept, for instance) - where there is a concrete graph object and that object is queried for things like nodes, edges, etc. (actually one of the significant things we tripped over was the API choice to navigate edges from a node itself without any extra state - which meant nodes/edge iteration had to carry state (potentially pointers back to the graph, etc) to be able to manifest their edges - trait or concept could both address this by, for traits, passing the graph as well as the node when querying the trait for edges, or for a concept passing the node back to the graph to query for edges).

So there is a bit of a part here where I may admittedly be a bit confused with the C++ lingo, since I don't actually like template programming that much :) (Which is part of the motivation for this to begin with... so that I can do the later changes in the stack here without *everything* being in templates.)

The way the CfgTraits is used is that you never use the CfgTraits class directly except to inherit from it using CRTP (curiously recurring template pattern). When writing algorithms that want to be generic over the type of CFG, those algorithms then have a derived class of CfgTraits as a template parameter. For example, D83094 adds a GenericCycleInfo<CfgTraitsT> template class, where the template parameter should be set to e.g. IrCfgTraits, if you want cycle info on LLVM IR, or to MachineCfgTraits, if you want cycle info on MachineIR. Both of these classes are derived from CfgTraits.

It is definitely different from how GraphTraits works, which you use it as GraphTraits<NodeType>, and then GraphTraits<BasicBlock *> etc. are specialized implementations. If GraphTraits worked the way that CfgTraits works, then we'd instead have classes like BasicBlockGraphTraits.

So to sum it up, all this sounds a bit to me like maybe calling CfgTraits "traits" is wrong? Is that what you're saying here? You can't just call it Cfg though, because it's *not* a CFG -- it's a kind of interface to a CFG which is designed for static polymorphism, unlike CfgInterface which is designed for dynamic polymorphism. Getting the names right is important, unfortunately I admit that I'm a bit lost there. "Traits" seemed like the closest thing to what I want, but I'm definitely open to suggestions.

[dblaikie]

In D83088#2218559, @nhaehnle wrote:

In D83088#2213886, @dblaikie wrote:

In D83088#2213864, @nhaehnle wrote:

In D83088#2213802, @dblaikie wrote:

In D83088#2213797, @nhaehnle wrote:

In D83088#2208611, @dblaikie wrote:

This seems like a strange hybrid between a static-polymorphism (with traits) and dynamic polymorphism (with base classes/virtual functions). Could this more readily be just one or the other? (sounds like you're leaning towards dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of functionality as much as possible in both static and dynamic polymorphism.

Could it be implemented statically as a primary interface, with a dynamic wrapper? (eg: a base class, then a derived class template that takes the static CFG type to wrap into the dynamic type) keeping the two concepts more clearly separated?

That is how it is implemented. CfgTraits is the primary static interface, and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.

Ah, fair enough. The inheritance details in the traits class confused me a bit/I had a hard time following, with all the features being in the one patch. Might be easier separately, but not sure.

Would it be possible for this not to use traits - I know @asbirlea and I had trouble with some things using GraphTraits owing to the traits API. An alternative would be to describe a CFGGraph concept (same as a standard container concept, for instance) - where there is a concrete graph object and that object is queried for things like nodes, edges, etc. (actually one of the significant things we tripped over was the API choice to navigate edges from a node itself without any extra state - which meant nodes/edge iteration had to carry state (potentially pointers back to the graph, etc) to be able to manifest their edges - trait or concept could both address this by, for traits, passing the graph as well as the node when querying the trait for edges, or for a concept passing the node back to the graph to query for edges).

So there is a bit of a part here where I may admittedly be a bit confused with the C++ lingo, since I don't actually like template programming that much :)

Not sure that's the best place to be designing this fairly integral and complicated piece of infrastructure from, but hoping we can find some good places/solutions/etc.

(Which is part of the motivation for this to begin with... so that I can do the later changes in the stack here without *everything* being in templates.)

That concerns me a bit as a motivation - Perhaps the existing GraphTraits template approach could be improved, rather than adding another/separate set of complexity with both dynamic and static dispatch. (eg: containers in the C++ standard library don't support runtime polymorphism (you can't dynamically dispatch over a std::vector versus a std::list, for instance)).

What does/will this Cfg abstraction provide that's separate from the current Graph (provided by GraphTraits) abstraction? Does it provide things other than the ability to write these algorithms as non-templates? (in which case is the non-dynamic portion of this functionally equivalent to GraphTraits (but more as a concept than a trait, by the sounds of it))

The way the CfgTraits is used is that you never use the CfgTraits class directly except to inherit from it using CRTP (curiously recurring template pattern).

side note: Using the same name in multiple namespaces makes this a bit harder to read than it might otherwise be (clang::CfgTraits deriving from llvm::CfgTraits, etc)
So currently you write a MyCfgTraitsBase, deriving from llvm::CfgTraitsBase

class MyCfgTraitsBase : public llvm::CfgTraitsBase { ...

then you write CfgTraits that derieves from that with both CRTP and the MyCfgTraitsBase

class MyCfgTraits : public llvm::CfgTraits<CfgTraitsBase, CfgTraits>

Could this be simplified by moving the MyCfgTraitsBase stuff into MyCfgTraits, and having llvm::CfgTraits with just one template parameter, the derived class?

When writing algorithms that want to be generic over the type of CFG, those algorithms then have a derived class of CfgTraits as a template parameter. For example, D83094 adds a GenericCycleInfo<CfgTraitsT> template class, where the template parameter should be set to e.g. IrCfgTraits, if you want cycle info on LLVM IR, or to MachineCfgTraits, if you want cycle info on MachineIR. Both of these classes are derived from CfgTraits.

Why is it necessary to pass the traits, rather than looking it up via a specialization (or allowing it to be passed explicitly if the user wants to)?

It is definitely different from how GraphTraits works, which you use it as GraphTraits<NodeType>, and then GraphTraits<BasicBlock *> etc. are specialized implementations. If GraphTraits worked the way that CfgTraits works, then we'd instead have classes like BasicBlockGraphTraits.

So to sum it up, all this sounds a bit to me like maybe calling CfgTraits "traits" is wrong? Is that what you're saying here?

Hmm, don't think so - as I look at it more. It's still seems like a traits class - it has all static members, a bunch of typedefs. And those members/types are used to interact with/probe some other object. The fact you can't look up the traits of a given type T certainly make this a bit quirky/outside the more usual model.

You can't just call it Cfg though, because it's *not* a CFG -- it's a kind of interface to a CFG which is designed for static polymorphism, unlike CfgInterface which is designed for dynamic polymorphism. Getting the names right is important, unfortunately I admit that I'm a bit lost there. "Traits" seemed like the closest thing to what I want, but I'm definitely open to suggestions.

Let's take a specific example then - Clang's CFG and LLVM's IR CFG. What if both those classes had a common API using exactly the same identifiers, typedefs, etc? That's what I mean by a non-traits-based solution. Much like std::vector and std::list have the same API (you can iterate over them using the same functions, etc - yes, only in other templates).

But I guess coming back to the original/broader design: What problems is this intended to solve? The inability to write non-template algorithms over graphs? What cost does that come with? Are there algorithms that are a bit too complicated/unwieldy when done as templates?
If it's specifically the static/dynamic dispatch issue - I'm not sure the type erasure and runtime overhead may be worth the tradeoff here, though if it is - it'd be good to keep the non-dynamic version common, rather than now having GraphTraits and CfgTraits done a bit differently, etc.

llvm/include/llvm/Support/CfgTraits.h

52

operator bool should be explicit

54–55

Preferably make any operator overload that can be a non-member, a non-member - this ensures equal conversion handling on both the left and right hand side of symmetric operators like these. (they can be friends if needed, but doesn't look like it in this case - non-friend, non-members that call get() should be fine here)

91

Not sure if this benefits from being inherited from, versus being freely accessible?

272–274

This probably shouldn't be defined if it's only needed for specialization, instead it can be declared:

template<typename CfgRelatedTypeT> struct CfgTraitsFor;

288

prefer = default where possible

338

generally capture everything by ref [&] if the lambda is only used locally/within the same expression or block

mlir/include/mlir/IR/Dominance.h

33–34

if something inherits publicly and declares all members public, I'd usually use "struct" and omit the "public"s.

[nhaehnle]

Not sure that's the best place to be designing this fairly integral and complicated piece of infrastructure from, but hoping we can find some good places/solutions/etc.

I sent an email to llvm-dev several weeks ago, but things seem to have moved here. Either way is fine with me.

But I guess coming back to the original/broader design: What problems is this intended to solve? The inability to write non-template algorithms over graphs? What cost does that come with? Are there algorithms that are a bit too complicated/unwieldy when done as templates?
If it's specifically the static/dynamic dispatch issue - I'm not sure the type erasure and runtime overhead may be worth the tradeoff here, though if it is - it'd be good to keep the non-dynamic version common, rather than now having GraphTraits and CfgTraits done a bit differently, etc.

It's not just over graphs, but taking SSA values into account as well -- that is the key distinction between GraphTraits and CfgTraits. The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

[dblaikie]

In D83088#2224297, @nhaehnle wrote:

Not sure that's the best place to be designing this fairly integral and complicated piece of infrastructure from, but hoping we can find some good places/solutions/etc.

I sent an email to llvm-dev several weeks ago, but things seem to have moved here. Either way is fine with me.

Yeah, sorry, I did see it - but didn't follow it in sufficient detail to understand the motivation/tradeoffs so well. (I do usually prefer to keep the design discussion on the design discussion threads, before worrying about the code specifics - but sometimes hard to understand it without code)

But I guess coming back to the original/broader design: What problems is this intended to solve? The inability to write non-template algorithms over graphs? What cost does that come with? Are there algorithms that are a bit too complicated/unwieldy when done as templates?
If it's specifically the static/dynamic dispatch issue - I'm not sure the type erasure and runtime overhead may be worth the tradeoff here, though if it is - it'd be good to keep the non-dynamic version common, rather than now having GraphTraits and CfgTraits done a bit differently, etc.

It's not just over graphs, but taking SSA values into account as well -- that is the key distinction between GraphTraits and CfgTraits.

Not sure I follow - could you give an example of a graph where the GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, perhaps more importantly - features of the graph/API surface area/properties you can expose through the CFG API/concept/thing but not through GraphTraits?

The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm thinking it's likely a concept (like containers in the C++ standard library) might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole algorithms - maybe something simple like generating a dot diagram for a graph) with these things given different APIs (traits, concepts, and runtime polymorphism) - and implementations of each kind too.

[nhaehnle]

In D83088#2225415, @dblaikie wrote:

But I guess coming back to the original/broader design: What problems is this intended to solve? The inability to write non-template algorithms over graphs? What cost does that come with? Are there algorithms that are a bit too complicated/unwieldy when done as templates?
If it's specifically the static/dynamic dispatch issue - I'm not sure the type erasure and runtime overhead may be worth the tradeoff here, though if it is - it'd be good to keep the non-dynamic version common, rather than now having GraphTraits and CfgTraits done a bit differently, etc.

It's not just over graphs, but taking SSA values into account as well -- that is the key distinction between GraphTraits and CfgTraits.

Not sure I follow - could you give an example of a graph where the GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, perhaps more importantly - features of the graph/API surface area/properties you can expose through the CFG API/concept/thing but not through GraphTraits?

See below.

The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm thinking it's likely a concept (like containers in the C++ standard library) might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole algorithms - maybe something simple like generating a dot diagram for a graph) with these things given different APIs (traits, concepts, and runtime polymorphism) - and implementations of each kind too.

Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form. A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template.

Thid motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are.

[kuhar]

Hi Nicoali,

In D83088#2227151, @nhaehnle wrote:

...
Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form. A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template.

Thid motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are.

Based on your description and the DomTree patches, if I understand correctly, the primary motivation is to facilitate writing CFG-representation-agnostic algorithms/analyses (e.g., dominators, divergence, convergence analyses), such that you can later lift the results back to the representation-aware types? If that's correct, I support the overall goal. Having spent probably ~weeks wrangling with domtree templates, this sounds like something that could simplify life a lot and potentially cut down on compilation times & sizes of llvm binaries.

[nhaehnle]

Based on your description and the DomTree patches, if I understand correctly, the primary motivation is to facilitate writing CFG-representation-agnostic algorithms/analyses (e.g., dominators, divergence, convergence analyses), such that you can later lift the results back to the representation-aware types? If that's correct, I support the overall goal. Having spent probably ~weeks wrangling with domtree templates, this sounds like something that could simplify life a lot and potentially cut down on compilation times & sizes of llvm binaries.

Yes, that is the motivation.

[dblaikie]

(side note: this code review is a bit hard to follow with all the linting messages about naming - might be a bit more readable if it conformed to the naming conventions?)

In D83088#2227151, @nhaehnle wrote:

In D83088#2225415, @dblaikie wrote:

But I guess coming back to the original/broader design: What problems is this intended to solve? The inability to write non-template algorithms over graphs? What cost does that come with? Are there algorithms that are a bit too complicated/unwieldy when done as templates?
If it's specifically the static/dynamic dispatch issue - I'm not sure the type erasure and runtime overhead may be worth the tradeoff here, though if it is - it'd be good to keep the non-dynamic version common, rather than now having GraphTraits and CfgTraits done a bit differently, etc.

It's not just over graphs, but taking SSA values into account as well -- that is the key distinction between GraphTraits and CfgTraits.

Not sure I follow - could you give an example of a graph where the GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, perhaps more importantly - features of the graph/API surface area/properties you can expose through the CFG API/concept/thing but not through GraphTraits?

See below.

The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm thinking it's likely a concept (like containers in the C++ standard library) might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole algorithms - maybe something simple like generating a dot diagram for a graph) with these things given different APIs (traits, concepts, and runtime polymorphism) - and implementations of each kind too.

Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form.

I'm having trouble following this example - I'm not sure what the CfgPrinter abstraction is/why it's first-class, and why this "print" function is calling what look like mutation operations like "appendBlocks". I guess perhaps the question is - what's it printing from and what's it printing to?

Ah, I see, the "append" functions are accessors, of a sort. Returning a container might be more clear than using an out parameter - alternatively, a functor parameter (ala std::for_each) that is called for each element, that can then be used to populate an existing container if desired, or to do immediate processing without the need for an intermediate container.

Though the printer abstraction still strikes me as a bit strange - especially since it doesn't seem to be printing itself. This function was passed a printer and a stream - the printer prints to the stream (perhaps it'd make more sense for the printer to take the stream on construction) and the function isn't passed the thing to print at all - that thing is accessed from the printer. That seems fairly awkward to me - I'd expect a printing operation to take a thing to be printed and a thing to print to.

Perhaps setting aside the complexities of printing things - could you provide an example of code, given a CfgGraph, that walks the graph - perhaps just numbering the nodes/edges/etc to produce a dot graph? Showing what the code would look like if it were passed a GraphTraits-implementing graph, a static polymorphic CfgGraph, and a dynamically polymorphic GfgGraph - and also showing what would be fandemantally possible with the CfgGraph that wouldn't be possible with GraphTraits, if any such things exist (it's still unclear to me whether CfgGraph has abstractions that don't exist in GraphTraits (eg: could you write a CfgGraph over GraphTraits? or would that be impossible because GraphTraits is missing concepts/CfgGraph doesn't apply to all GraphTraits-grahs? what subset of GraphTraits graphs does CfgGraph cover?).

A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template.

Thid motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are.

I hesitate to write code that's more idiomatic in a language that isn't C++. Agreed that long/complicated algorithms as templates aren't the best thing - but sometimes can be quite suitable/idiomatic C++ (see the C++ standard library).

That said, I'd like to help make things more usable, for sure - but I'm not sure/currently feeling like this might not be the best direction for achieving that goal & I think some clear comparisons - even for overly simplistic code, where the overhead of a more complex solution may not be felt as acutely (actually, small examples might show syntactic overhead more acutely - if it takes more code to do the same thing, when that code isn't washed out by a lot of code that would be the same regardless of implementation, it will hopefully be more obvious, rather than less), hopefully it'll be more a more clear/concrete basis on which to discuss relative design tradeoffs.

[nhaehnle]

The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm thinking it's likely a concept (like containers in the C++ standard library) might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole algorithms - maybe something simple like generating a dot diagram for a graph) with these things given different APIs (traits, concepts, and runtime polymorphism) - and implementations of each kind too.

Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form.

I'm having trouble following this example - I'm not sure what the CfgPrinter abstraction is/why it's first-class, and why this "print" function is calling what look like mutation operations like "appendBlocks". I guess perhaps the question is - what's it printing from and what's it printing to?

Ah, I see, the "append" functions are accessors, of a sort. Returning a container might be more clear than using an out parameter - alternatively, a functor parameter (ala std::for_each) that is called for each element, that can then be used to populate an existing container if desired, or to do immediate processing without the need for an intermediate container.

The code is trying to strike a balance here in terms of performance. Since dynamic polymorphism is used, a functor-based traversal can't be inlined and so the number of indirect function calls increases quite a bit. There are a number of use cases where you really do want to just append successors or predecessors to a vectors, like during a graph traversal. An example graph traversal is here: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L329

Though the printer abstraction still strikes me as a bit strange - especially since it doesn't seem to be printing itself. This function was passed a printer and a stream - the printer prints to the stream (perhaps it'd make more sense for the printer to take the stream on construction) and the function isn't passed the thing to print at all - that thing is accessed from the printer. That seems fairly awkward to me - I'd expect a printing operation to take a thing to be printed and a thing to print to.

Keep in mind that where those printBlockName / printValue methods are used, they will always be mixed in with printing of other things. So the alternative you're describing would result in code like:

dbgs() << " currently at: ";  // explicit stream
printer.printBlockName(block); // implicit stream
dbgs() << '\n'; // explicit stream

I would argue that that ends up being more awkward because it mixes implicit streams with explicitly given streams.

We could perhaps add versions of the methods that return a Printable object, so that we can write:

dbgs() << "currently at: " << printer.printableBlockName(block) << '\n';

By the way, the main motivation for making the CfgPrinter a separate object is that printing LLVM IR efficiently requires keeping a ModuleSlotTracker around. Splitting the CfgPrinter off from the CfgInterface allows the fast-path of code that doesn't want debug prints to not have to carry a reference to a ModuleSlotTracker around, even if it's just an empty std::unique_ptr. That's a comparatively small burden though, so I'd be fine with merging the CfgPrinter back into the CfgInterface.

Perhaps setting aside the complexities of printing things - could you provide an example of code, given a CfgGraph, that walks the graph - perhaps just numbering the nodes/edges/etc to produce a dot graph? Showing what the code would look like if it were passed a GraphTraits-implementing graph, a static polymorphic CfgGraph, and a dynamically polymorphic GfgGraph - and also showing what would be fandemantally possible with the CfgGraph that wouldn't be possible with GraphTraits, if any such things exist (it's still unclear to me whether CfgGraph has abstractions that don't exist in GraphTraits (eg: could you write a CfgGraph over GraphTraits? or would that be impossible because GraphTraits is missing concepts/CfgGraph doesn't apply to all GraphTraits-grahs? what subset of GraphTraits graphs does CfgGraph cover?).

Repeating myself, the main difference is that CfgGraph has a notion of SSA values in addition to nodes / basic blocks. There are some other differences, but they're comparatively minor and more cosmetic.

As far as an example is concerned, see the link above. That particular algorithm is still on the simpler side and doesn't need SSA values, so you could implement it based on GraphTraits as well, in which case you'd replace the various

iface.appendSuccessors(block, blockStack);

with something like:

blockStack.insert(blockStack.end(), std::begin(llvm::children(block)), std::end(llvm::children(block)));

Apart from that, the code would be the same.

A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template.

Third motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are.

I hesitate to write code that's more idiomatic in a language that isn't C++. Agreed that long/complicated algorithms as templates aren't the best thing - but sometimes can be quite suitable/idiomatic C++ (see the C++ standard library).

I think there's a misunderstanding here. The code I'm writing based on CfgTraits would not be more idiomatic in Rust or any other language that I'm aware of. The point is that writing the code in the way that it seems you want it to be written would be feasible in Rust, but isn't feasible in C++. It's about how type-checking of generics/templates works in those languages.

Comparing to the C++ STL, the STL is significantly simpler on the aspect that matters here. The templates in the STL have comparatively simple contracts with their template parameters. In most cases, they only care about a very small number of things, like copy-/move-ability and comparison operators. The "interface" of the CfgTraits is broader and deeper. Repeating myself again, this is in large part because it also has a notion of SSA values, but there are other reasons, e.g. caring about printability to make debugging less painful.

That said, I'd like to help make things more usable, for sure - but I'm not sure/currently feeling like this might not be the best direction for achieving that goal & I think some clear comparisons - even for overly simplistic code, where the overhead of a more complex solution may not be felt as acutely (actually, small examples might show syntactic overhead more acutely - if it takes more code to do the same thing, when that code isn't washed out by a lot of code that would be the same regardless of implementation, it will hopefully be more obvious, rather than less), hopefully it'll be more a more clear/concrete basis on which to discuss relative design tradeoffs.

It's not really about needing to write more or less source code -- see the example above. It's about the fact that C++ can't type-check templates in a useful way. Templates are effectively duck-typed and type-checking only happens at instantiation, which makes their maintenance a pain over time. A nice example of the negative effects that this can have in practice is you end up with stuff like (from mlir/include/mlir/IR/Block.h):

/// Print out the name of the block without printing its body.
/// NOTE: The printType argument is ignored.  We keep it for compatibility
/// with LLVM dominator machinery that expects it to exist.
void printAsOperand(raw_ostream &os, bool printType = true);

Why is this method called printAsOperand, which makes no sense for a generic interface of a graph? And why does it have a printType argument? Presumably this happened because dominator trees were first written for IR and then genericized from there without taking the time to properly think about and define what the interface between generic dominator trees and their template parameter should be. So then an implementation detail of llvm::BasicBlock ended up leaking all over the place.

When I started out writing the algorithms around CfgTraits, I didn't even know what the right interface should be, and I expect that there may well still be tweaks to the interface going forward. Writing the code in the way that I'm writing it helps keeps us honest and prevents weird escapes like printAsOperand. Perhaps even more importantly, as @kuhar also suggested, the quality-of-life when writing and maintaining code is much improved because you get more useful type-checking.

[nhaehnle]

• cleanup operators on CfgOpaqueType
• address other review comments

[nhaehnle]

llvm/include/llvm/Support/CfgTraits.h

52

Done.

54–55

Done.

91

The idea here is to enforce via the type system that people use CfgTraits::{wrap,unwrap}Ref instead of having makeOpaque calls freely in random code.

272–274

Interesting. So GraphTraits should arguably be changed similarly.

288

Done.

338

The lambda is returned via Printable.

[nhaehnle]

ping

[nhaehnle]

ping^2

[rriddle]

mlir/include/mlir/IR/Dominance.h

49

This seems to have broken the GCC5 build:
https://buildkite.com/mlir/mlir-core/builds/8739#7a957564-9850-487c-a814-c6818890bd14

/mlir/include/mlir/IR/Dominance.h:49:14: error: specialization of 'template<class CfgRelatedTypeT> struct llvm::CfgTraitsFor' in different namespace [-fpermissive]
 struct llvm::CfgTraitsFor<mlir::Block> {
              ^
In file included from mlir/include/mlir/IR/Dominance.h:13:0,
                 from mlir/lib/IR/Verifier.cpp:30:
llvm/include/llvm/Support/CfgTraits.h:294:44: error:   from definition of 'template<class CfgRelatedTypeT> struct llvm::CfgTraitsFor' [-fpermissive]
 template <typename CfgRelatedTypeT> struct CfgTraitsFor;

[antiagainst]

mlir/include/mlir/IR/Dominance.h

49

Pushed https://github.com/llvm/llvm-project/commit/f2a06875b604c00cbe96e54363f4f5d28935d610

[dblaikie]

Sorry about the delays in review - but please revert this patch until we can hash out a few more details. I really don't think this is the best direction forward for a core abstraction & I'll do my best to explain why & try to understand where you're coming from.

In D83088#2232893, @nhaehnle wrote:

The most immediate problem is divergence analysis, which is extremely complex and difficult to get right. If I had tried to fight the accidental complexity that comes with attempting to write such an algorithm as C++ templates in addition to the inherent complexity of the algorithm at the same time, I'm not sure I would have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because of this, though at least dominator trees are much more well studied in the academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm thinking it's likely a concept (like containers in the C++ standard library) might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole algorithms - maybe something simple like generating a dot diagram for a graph) with these things given different APIs (traits, concepts, and runtime polymorphism) - and implementations of each kind too.

Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form.

I'm having trouble following this example - I'm not sure what the CfgPrinter abstraction is/why it's first-class, and why this "print" function is calling what look like mutation operations like "appendBlocks". I guess perhaps the question is - what's it printing from and what's it printing to?

Ah, I see, the "append" functions are accessors, of a sort. Returning a container might be more clear than using an out parameter - alternatively, a functor parameter (ala std::for_each) that is called for each element, that can then be used to populate an existing container if desired, or to do immediate processing without the need for an intermediate container.

The code is trying to strike a balance here in terms of performance. Since dynamic polymorphism is used, a functor-based traversal can't be inlined and so the number of indirect function calls increases quite a bit. There are a number of use cases where you really do want to just append successors or predecessors to a vectors, like during a graph traversal. An example graph traversal is here: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L329

One way to simplify the dynamic polymorphism overhead of iteration would be to invert/limit the API - such as having a "node.forEachEdge([](const Edge& E) { ... });" or the like.

Though the printer abstraction still strikes me as a bit strange - especially since it doesn't seem to be printing itself. This function was passed a printer and a stream - the printer prints to the stream (perhaps it'd make more sense for the printer to take the stream on construction) and the function isn't passed the thing to print at all - that thing is accessed from the printer. That seems fairly awkward to me - I'd expect a printing operation to take a thing to be printed and a thing to print to.

Keep in mind that where those printBlockName / printValue methods are used, they will always be mixed in with printing of other things. So the alternative you're describing would result in code like:

dbgs() << " currently at: ";  // explicit stream
printer.printBlockName(block); // implicit stream
dbgs() << '\n'; // explicit stream

I would argue that that ends up being more awkward because it mixes implicit streams with explicitly given streams.

We could perhaps add versions of the methods that return a Printable object, so that we can write:

dbgs() << "currently at: " << printer.printableBlockName(block) << '\n';

By the way, the main motivation for making the CfgPrinter a separate object is that printing LLVM IR efficiently requires keeping a ModuleSlotTracker around. Splitting the CfgPrinter off from the CfgInterface allows the fast-path of code that doesn't want debug prints to not have to carry a reference to a ModuleSlotTracker around, even if it's just an empty std::unique_ptr. That's a comparatively small burden though, so I'd be fine with merging the CfgPrinter back into the CfgInterface.

I'm generally worried about the genericity of these abstractions - whether or not a generic abstraction over printing is required/pulling its weight. Are there common abstractions over printing you have in mind using this abstraction?

A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template.

Third motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are.

I hesitate to write code that's more idiomatic in a language that isn't C++. Agreed that long/complicated algorithms as templates aren't the best thing - but sometimes can be quite suitable/idiomatic C++ (see the C++ standard library).

I think there's a misunderstanding here. The code I'm writing based on CfgTraits would not be more idiomatic in Rust or any other language that I'm aware of. The point is that writing the code in the way that it seems you want it to be written would be feasible in Rust, but isn't feasible in C++. It's about how type-checking of generics/templates works in those languages.

Comparing to the C++ STL, the STL is significantly simpler on the aspect that matters here. The templates in the STL have comparatively simple contracts with their template parameters. In most cases, they only care about a very small number of things, like copy-/move-ability and comparison operators. The "interface" of the CfgTraits is broader and deeper. Repeating myself again, this is in large part because it also has a notion of SSA values, but there are other reasons, e.g. caring about printability to make debugging less painful.

Ah, sorry - I don't mean to treat CfgGraph to be thought of like the template parameter to, say, std::vector - I meant thinking of CfgGraph as something like std::vector itself. Rather than using traits to access containers in the C++ standard library, the general concept of a container is used to abstract over a list, a vector, etc.

eg, if you want to print the elements of any C++ container, the code looks like:

template<typename Container>
void print(const Container &C, std::ostream &out) {
  out << '{';
  bool first = true;
  for (const auto &E : C) {
    if (!first)
      out << ", ";
    first = false;
    out << E;
  }
  out << '}';
}

Which, yes, is much more legible than what one could imagine a GraphTraits-esque API over containers might be:

template<typename Container, typename Traits = ContainerTraits<Container>>
void print(const Container &C, std::ostream &out) {
  out << '{';
  bool first = true;
  for (const auto &E : Traits::children(C)) {
    if (!first)
      out << ", ";
    first = false;
    out << Traits::element(E);
  }
  out << '}';
}

Or something like that - and the features you'd gain from that would be the ability to sort of "decorate" your container without having to create an actual container decorator - instead implementing a custom trait type that, say, iterates container elements in reverse. But generally a thin decorator using the first non-traits API would be nicer (eg: llvm::reverse(container) which gives you a container decorator that reverses order).

If you had a runtime polymorphic API over containers in C++, then it might look something like this:

void print(const ContainerInterface& C, std::ostream& out) {
  out << '{';
  bool first = true;
  C.for_each([&](const auto &E) {
    if (!first)
      out << ", ";
    first = false;
    E.print(out);
  });
  out << '}';
}

(printing, as you've mentioned, might get a bit complicated - perhaps a "visitor" pattern would be suitable for printing, then:

void print(const ContainerInterface& C, std::ostream& out) {
  out << '{';
  bool first = true;
  C.for_each([&](const auto &E) {
    if (!first)
      out << ", ";
    first = false;
    E.print(out);
  });
  out << '}';
}

I'd really like to see examples like this ^ using the different abstractions under consideration here (classic GraphTraits, CfgTraits dynamic and static typed, perhaps what a static API would look like if it wasn't trying to be dynamic API compatible).

That said, I'd like to help make things more usable, for sure - but I'm not sure/currently feeling like this might not be the best direction for achieving that goal & I think some clear comparisons - even for overly simplistic code, where the overhead of a more complex solution may not be felt as acutely (actually, small examples might show syntactic overhead more acutely - if it takes more code to do the same thing, when that code isn't washed out by a lot of code that would be the same regardless of implementation, it will hopefully be more obvious, rather than less), hopefully it'll be more a more clear/concrete basis on which to discuss relative design tradeoffs.

It's not really about needing to write more or less source code -- see the example above. It's about the fact that C++ can't type-check templates in a useful way. Templates are effectively duck-typed and type-checking only happens at instantiation, which makes their maintenance a pain over time. A nice example of the negative effects that this can have in practice is you end up with stuff like (from mlir/include/mlir/IR/Block.h):

/// Print out the name of the block without printing its body.
/// NOTE: The printType argument is ignored.  We keep it for compatibility
/// with LLVM dominator machinery that expects it to exist.
void printAsOperand(raw_ostream &os, bool printType = true);

Why is this method called printAsOperand, which makes no sense for a generic interface of a graph? And why does it have a printType argument? Presumably this happened because dominator trees were first written for IR and then genericized from there without taking the time to properly think about and define what the interface between generic dominator trees and their template parameter should be. So then an implementation detail of llvm::BasicBlock ended up leaking all over the place.

When I started out writing the algorithms around CfgTraits, I didn't even know what the right interface should be, and I expect that there may well still be tweaks to the interface going forward. Writing the code in the way that I'm writing it helps keeps us honest and prevents weird escapes like printAsOperand. Perhaps even more importantly, as @kuhar also suggested, the quality-of-life when writing and maintaining code is much improved because you get more useful type-checking.

Indeed template code can get a bit weird - but I'm not sure it's quite enough to justify the change in/complications of mulitple (static and dynamic) abstractions here just yet. It might be that taking a more structured C++ idiomatic approach to template design (like C++ standard container concept abstractions) might lead to more usable code without /some/ complexities (though may trade others).

[nhaehnle]

David, I don't think this is appropriate here. Let's take the discussion to llvm-dev.

mlir/include/mlir/IR/Dominance.h

49

Apologies for the inconvenience, and thank you for taking care of it!

[mehdi_amini]

In D83088#2345540, @nhaehnle wrote:

David, I don't think this is appropriate here. Let's take the discussion to llvm-dev.

Seems like David asked to revert in the meantime?

[arsenm]

In D83088#2346322, @mehdi_amini wrote:

In D83088#2345540, @nhaehnle wrote:

David, I don't think this is appropriate here. Let's take the discussion to llvm-dev.

Seems like David asked to revert in the meantime?

-1 to reverting, which will just make the history messier with no tangible benefit

[mehdi_amini]

In D83088#2347111, @arsenm wrote:

In D83088#2346322, @mehdi_amini wrote:

In D83088#2345540, @nhaehnle wrote:

David, I don't think this is appropriate here. Let's take the discussion to llvm-dev.

Seems like David asked to revert in the meantime?

-1 to reverting, which will just make the history messier with no tangible benefit

This is the usual LLVM policy I believe: someone expressed a concern and ask to revert. We revert and discuss first.
So again: please revert.

The messier history is not an argument: we revert so many times for any random bot failures already, and our contribution guidelines still tell people to push a "fake commit" with a whitespace change to test their access.

I also see tangile benefits:

• we don't start building dependencies on newly introduced API making a revert more difficult later.
• the burden of convincing of the approach is on the patch author, reverting is forcing the discussion here.

[nhaehnle]

Hi Mehdi, this is not an appropriate place for this discussion. Yes, we have a general rule that patches can be reverted if they're obviously broken (e.g. build bot problems) or clearly violate some other standard. This is a good rule, but it doesn't apply here. If you think it does, please state your case in the email thread that I've started on llvm-dev for this very purpose. Just one thing:

• the burden of convincing of the approach is on the patch author, reverting is forcing the discussion here.

I was trying to have this conversation. I am more than happy to have it, and I would be happy for more people to participate! But what can I do if the only(!) person who voices concerns just goes into radio silence, and the total number of people who participate is small in any case, despite raising it on llvm-dev as well?

It is in fact the decision to not revert the change which is apparently required to force the discussion!

P.S.: It's easy to miss on Phabricator, but there is already a long stack of patches which build on this. In a way this is a good thing because it can inform the discussion, but I will hold off from pushing more for now even though many of them have already been accepted.

[arsenm]

In D83088#2348641, @mehdi_amini wrote:

In D83088#2347111, @arsenm wrote:

In D83088#2346322, @mehdi_amini wrote:

In D83088#2345540, @nhaehnle wrote:

David, I don't think this is appropriate here. Let's take the discussion to llvm-dev.

Seems like David asked to revert in the meantime?

-1 to reverting, which will just make the history messier with no tangible benefit

This is the usual LLVM policy I believe: someone expressed a concern and ask to revert. We revert and discuss first.
So again: please revert.

The messier history is not an argument: we revert so many times for any random bot failures already, and our contribution guidelines still tell people to push a "fake commit" with a whitespace change to test their access.

Unrelated, but I think the test commit process should be dropped

I also see tangile benefits:

• we don't start building dependencies on newly introduced API making a revert more difficult later.
• the burden of convincing of the approach is on the patch author, reverting is forcing the discussion here.

This patch has been up for review for almost 4 months, with a corresponding RFC on llvm-dev. The last review comments were over 2 months ago. Coming back to this so long after to ask for a revert is an unworkable level of review paralysis

[mehdi_amini]

In D83088#2350287, @nhaehnle wrote:

Hi Mehdi, this is not an appropriate place for this discussion. Yes, we have a general rule that patches can be reverted if they're obviously broken (e.g. build bot problems) or clearly violate some other standard. This is a good rule, but it doesn't apply here. If you think it does, please state your case in the email thread that I've started on llvm-dev for this very purpose. Just one thing:

I strongly disagree: the bar for post-review commit is not lower than pre-commit review.

Again: please revert when someone has a concern, including a *design* concern with you patch.

P.S.: It's easy to miss on Phabricator, but there is already a long stack of patches which build on this

(this is part of my previous point).

[nhaehnle]

I replied on llvm-dev.

[rengolin]

I have read all of the comments in this review and have looked at all the other pending reviews because of this and I still see strong disagreement on the design and implementation.

Unfortunately, I can't contribute with the technical discussion because there's a lot more context and content here than I can absorb in the time I have available, but overall I think David's critics are very pertinent. They don't mean the code is wrong or bad, just that they are important questions that need answers. Some of the questions were answered, others weren't. This patch should not have been committed before those things were sorted out, as is clearly stated in the (existing) review policy (https://llvm.org/docs/CodeReview.html#acknowledge-all-reviewer-feedback).

I do appreciate that the other patches are "waiting" for this one and that it has been months, but this patch fundamentally changes the algorithm with a motivation that still isn't clear for two reasons:

1. It was initially stated that the motivation is to reduce the number of templates because the author doesn't like them, which is not a good reason.
2. Despite recurrent requests to show concrete code examples comparing current and new design, showing why it would be "easier to use", none have materialised (other than David's own attempts).

All of the other patches were approved by the same set of people. This is definitely not uncommon, but is highly susceptible to unconscious bias. Once David questioned the approach with concrete questions, concrete answers should address all of the points.

This patch should have never been committed in the first place, even with one approval.

In D83088#2342760, @dblaikie wrote:

Sorry about the delays in review - but please revert this patch until we can hash out a few more details. I really don't think this is the best direction forward for a core abstraction & I'll do my best to explain why & try to understand where you're coming from.

The (current) review policy (https://llvm.org/docs/CodeReview.html#can-code-be-reviewed-after-it-is-committed) is already clear enough:

"There is a strong expectation that authors respond promptly to post-commit feedback and address it. Failure to do so is cause for the patch to be reverted."

It's pretty clear that the paragraph applies to David's post-commit review.

I'd really like to see examples like this ^ using the different abstractions under consideration here (classic GraphTraits, CfgTraits dynamic and static typed, perhaps what a static API would look like if it wasn't trying to be dynamic API compatible).

This is the main request that was left unaddressed and the one that has the highest impact on the design of the API as well as all the following patches. The fact that they have all been approved doesn't mean this one must, too.

Their own approval just means those changes look good with the current interpretation, not that they must land. It's entirely possible that they continue to be good after the API has changed (if it has), in which case the approvals can just be restated. But they may well disappear or change completely due to the change in API, and will need new reviews to avoid having an already approved review change substantially in content.

Indeed template code can get a bit weird - but I'm not sure it's quite enough to justify the change in/complications of mulitple (static and dynamic) abstractions here just yet. It might be that taking a more structured C++ idiomatic approach to template design (like C++ standard container concept abstractions) might lead to more usable code without /some/ complexities (though may trade others).

And this is the main critic to the overall design choice, which I also agree completely. I'm not a big fan of complex template code myself, but the idioms are well known and they do simplify usage in many cases.

LLVM has had its fair share of discussions on the topics and we have developed multiple APIs and containers tho overcome deficiencies in the standard library, some of those concepts made into the standard. Some of those I have learned to like when I tried to implement otherwise and failed.

Only with concrete comparison of usage and patterns that we can make an informed decision and this is required to change a core concept of the compiler more than any other place. A single example where your pattern fits isn't enough to demonstrate that it will be generic and usable for all the other patterns that it may be used.

I'm sorry this delays more your work, but this is what working on an open source very large project entails. In comparison, LLVM is very fast compared to other OSS projects out there.

Also, echoing other people in this thread, this is more a case for an RFC thread on the list than code review. If the original thread didn't catch the attention of a public wide enough, ping the thread, talk to people on IRC or any other tool that works for you. We need consensus and we clearly don't have it here.

As an LLVM developer, you're expected to read the policy documents and follow the expectations, but not necessarily to interpret them in the same way we did when we wrote them. If they're confusing or imprecise, remember we're not writers, nor we're all native English speakers, nor we all have the same culture. Trying to clarify what they mean (as Sean and Mehdi tried to do) is the only way forward.

Please, revert this commit and discuss the merits of your approach on the list.

Thank you,
--renato

[nhaehnle]

I'm going to follow up with another RFC about this on llvm-dev.

[nhaehnle]

Superseded by D92924, D92925, D92926

clang/include/clang/Analysis/Analyses/Dominators.h

 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
 #define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
 
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
-#include "llvm/Support/GenericIteratedDominanceFrontier.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
+#include "llvm/Support/GenericIteratedDominanceFrontier.h"
 #include "llvm/Support/raw_ostream.h"
 
+namespace clang {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = CFG;
+  using BlockRef = CFGBlock *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+    return makeOpaque<llvm::CfgBlockRefTag>(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+    return static_cast<BlockRef>(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits<CfgTraitsBase, CfgTraits> {
+public:
+  static ParentType *getBlockParent(CFGBlock *block) {
+    return block->getParent();
+  }
+
+  // Clang's CFG contains null pointers for unreachable successors, e.g. when an
+  // if statement's condition is always false, it's 'then' branch is represented
+  // with a nullptr. Account for this in the predecessors / successors
+  // iteration.
+  template <typename BaseIteratorT> struct skip_null_iterator;
+
+  template <typename BaseIteratorT>
+  using skip_null_iterator_base =
+      llvm::iterator_adaptor_base<skip_null_iterator<BaseIteratorT>,
+                                  BaseIteratorT,
+                                  std::bidirectional_iterator_tag>;
+
+  template <typename BaseIteratorT>
+  struct skip_null_iterator : skip_null_iterator_base<BaseIteratorT> {
+    using Base = skip_null_iterator_base<BaseIteratorT>;
+
+    skip_null_iterator() = default;
+    skip_null_iterator(BaseIteratorT it, BaseIteratorT end)
+        : Base(it), m_end(end) {
+      forward();
+    }
+
+    skip_null_iterator &operator++() {
+      ++this->I;
+      forward();
+      return *this;
+    }
+
+    skip_null_iterator &operator--() {
+      do {
+        --this->I;
+      } while (!*this->I);
+      return *this;
+    }
+
+  private:
+    BaseIteratorT m_end;
+
+    void forward() {
+      while (this->I != m_end && !*this->I)
+        ++this->I;
+    }
+  };
+
+  static auto predecessors(CFGBlock *block) {
+    auto range = llvm::inverse_children<CFGBlock *>(block);
+    using iterator = skip_null_iterator<decltype(range.begin())>;
+    return llvm::make_range(iterator(range.begin(), range.end()),
+                            iterator(range.end(), range.end()));
+  }
+
+  static auto successors(CFGBlock *block) {
+    auto range = llvm::children<CFGBlock *>(block);
+    using iterator = skip_null_iterator<decltype(range.begin())>;
+    return llvm::make_range(iterator(range.begin(), range.end()),
+                            iterator(range.end(), range.end()));
+  }
+};
+
+} // namespace clang
+
+template <> struct llvm::CfgTraitsFor<clang::CFGBlock> {
+  using CfgTraits = clang::CfgTraits;
+};
+
 // FIXME: There is no good reason for the domtree to require a print method
 // which accepts an LLVM Module, so remove this (and the method's argument that
 // needs it) when that is fixed.
 
 namespace llvm {
 
 class Module;
 

llvm/include/llvm/CodeGen/MachineCfgTraits.h

+//===- MachineCfgTraits.h - Traits for Machine IR CFGs ----------*- 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 MachineCfgTraits to allow generic CFG algorithms to
+/// operate on MachineIR in SSA form.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINECFGTRAITS_H
+#define LLVM_CODEGEN_MACHINECFGTRAITS_H
+
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/CfgTraits.h"
+
+namespace llvm {
+
+class MachineCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = MachineFunction;
+  using BlockRef = MachineBasicBlock *;
+  using ValueRef = Register;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+    return makeOpaque<CfgBlockRefTag>(block);
+  }
+  static CfgValueRef wrapRef(ValueRef value) {
+    // Physical registers are unsupported by design.
+    assert(!value.isValid() || value.isVirtual());
+    uintptr_t wrapped = value.id();
+    assert((wrapped != 0) == value.isValid());
+
+    // Guard against producing values reserved for DenseMap markers. This is de
+    // facto impossible, because it'd require 2^31 virtual registers to be in
+    // use on a 32-bit architecture.
+    assert(wrapped != (uintptr_t)-1 && wrapped != (uintptr_t)-2);
+
+    return makeOpaque<CfgValueRefTag>(reinterpret_cast<void *>(wrapped));
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+    return static_cast<BlockRef>(getOpaque(block));
+  }
+  static ValueRef unwrapRef(CfgValueRef value) {
+    uintptr_t wrapped = reinterpret_cast<uintptr_t>(getOpaque(value));
+    return Register(wrapped);
+  }
+};
+
+/// \brief CFG traits for Machine IR in SSA form.
+class MachineCfgTraits
+    : public CfgTraits<MachineCfgTraitsBase, MachineCfgTraits> {
+private:
+  MachineRegisterInfo *m_regInfo;
+
+public:
+  explicit MachineCfgTraits(MachineFunction *parent)
+      : m_regInfo(&parent->getRegInfo()) {}
+
+  static MachineFunction *getBlockParent(MachineBasicBlock *block) {
+    return block->getParent();
+  }
+
+  struct const_blockref_iterator
+      : iterator_adaptor_base<const_blockref_iterator,
+                              MachineFunction::iterator> {
+    using Base = iterator_adaptor_base<const_blockref_iterator,
+                                       MachineFunction::iterator>;
+
+    const_blockref_iterator() = default;
+
+    explicit const_blockref_iterator(MachineFunction::iterator i) : Base(i) {}
+
+    MachineBasicBlock *operator*() const { return &Base::operator*(); }
+  };
+
+  static iterator_range<const_blockref_iterator>
+  blocks(MachineFunction *function) {
+    return {const_blockref_iterator(function->begin()),
+            const_blockref_iterator(function->end())};
+  }
+
+  static auto predecessors(MachineBasicBlock *block) {
+    return block->predecessors();
+  }
+  static auto successors(MachineBasicBlock *block) {
+    return block->successors();
+  }
+
+  /// Get the defining block of a value.
+  MachineBasicBlock *getValueDefBlock(ValueRef value) const {
+    if (!value)
+      return nullptr;
+    return m_regInfo->getVRegDef(value)->getParent();
+  }
+
+  struct blockdef_iterator
+      : iterator_facade_base<blockdef_iterator, std::forward_iterator_tag,
+                             Register> {
+  private:
+    MachineBasicBlock::instr_iterator m_instr;
+    MachineInstr::mop_iterator m_def;
+
+  public:
+    blockdef_iterator() = default;
+
+    explicit blockdef_iterator(MachineBasicBlock &block)
+        : m_instr(block.instr_begin()) {
+      if (m_instr != block.end())
+        m_def = m_instr->defs().begin();
+    }
+    blockdef_iterator(MachineBasicBlock &block, bool)
+        : m_instr(block.instr_end()), m_def() {}
+
+    bool operator==(const blockdef_iterator &rhs) const {
+      return m_instr == rhs.m_instr && m_def == rhs.m_def;
+    }
+
+    Register operator*() const {
+      assert(m_def->isReg() && !m_def->getSubReg() && m_def->isDef());
+      return m_def->getReg();
+    }
+
+    blockdef_iterator &operator++() {
+      ++m_def;
+
+      while (m_def == m_instr->defs().end()) {
+        ++m_instr;
+        if (m_instr.isEnd()) {
+          m_def = {};
+          return *this;
+        }
+
+        m_def = m_instr->defs().begin();
+      }
+
+      return *this;
+    }
+  };
+
+  static auto blockdefs(MachineBasicBlock *block) {
+    return llvm::make_range(blockdef_iterator(*block),
+                            blockdef_iterator(*block, true));
+  }
+
+  struct Printer {
+    explicit Printer(const MachineCfgTraits &traits)
+        : m_regInfo(traits.m_regInfo) {}
+
+    void printBlockName(raw_ostream &out, MachineBasicBlock *block) const;
+    void printValue(raw_ostream &out, Register value) const;
+
+  private:
+    MachineRegisterInfo *m_regInfo;
+  };
+};
+
+template <> struct CfgTraitsFor<MachineBasicBlock> {
+  using CfgTraits = MachineCfgTraits;
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_MACHINECFGTRAITS_H

llvm/include/llvm/IR/CFG.h

 #define LLVM_IR_CFG_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/CfgTraits.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 
 namespace llvm {
 
 class BasicBlock;
 class Instruction;

 };
 template <> struct GraphTraits<Inverse<const Function*>> :
   public GraphTraits<Inverse<const BasicBlock*>> {
   static NodeRef getEntryNode(Inverse<const Function *> G) {
     return &G.Graph->getEntryBlock();
   }
 };
 
+//===----------------------------------------------------------------------===//
+// LLVM IR CfgTraits
+//===----------------------------------------------------------------------===//
+
+class IrCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = Function;
+  using BlockRef = BasicBlock *;
+  using ValueRef = Value *;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+    return makeOpaque<CfgBlockRefTag>(block);
+  }
+  static CfgValueRef wrapRef(ValueRef block) {
+    return makeOpaque<CfgValueRefTag>(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+    return static_cast<BlockRef>(getOpaque(block));
+  }
+  static ValueRef unwrapRef(CfgValueRef block) {
+    return static_cast<ValueRef>(getOpaque(block));
+  }
+};
+
+/// \brief CFG traits for LLVM IR.
+class IrCfgTraits : public CfgTraits<IrCfgTraitsBase, IrCfgTraits> {
+public:
+  explicit IrCfgTraits(Function * /*parent*/) {}
+
+  static Function *getBlockParent(BasicBlock *block) {
+    return block->getParent();
+  }
+
+  static auto predecessors(BasicBlock *block) {
+    return llvm::predecessors(block);
+  }
+  static auto successors(BasicBlock *block) { return llvm::successors(block); }
+
+  /// Get the defining block of a value if it is an instruction, or null
+  /// otherwise.
+  static BlockRef getValueDefBlock(ValueRef value) {
+    if (auto *instruction = dyn_cast<Instruction>(value))
+      return instruction->getParent();
+    return nullptr;
+  }
+
+  struct block_iterator
+      : iterator_adaptor_base<block_iterator, Function::iterator> {
+    using Base = iterator_adaptor_base<block_iterator, Function::iterator>;
+
+    block_iterator() = default;
+
+    explicit block_iterator(Function::iterator i) : Base(i) {}
+
+    BasicBlock *operator*() const { return &Base::operator*(); }
+  };
+
+  static iterator_range<block_iterator> blocks(Function *function) {
+    return {block_iterator(function->begin()), block_iterator(function->end())};
+  }
+
+  struct value_iterator
+      : iterator_adaptor_base<value_iterator, BasicBlock::iterator> {
+    using Base = iterator_adaptor_base<value_iterator, BasicBlock::iterator>;
+
+    value_iterator() = default;
+
+    explicit value_iterator(BasicBlock::iterator i) : Base(i) {}
+
+    ValueRef operator*() const { return &Base::operator*(); }
+  };
+
+  static iterator_range<value_iterator> blockdefs(BlockRef block) {
+    return {value_iterator(block->begin()), value_iterator(block->end())};
+  }
+
+  struct Printer {
+    explicit Printer(const IrCfgTraits &);
+    ~Printer();
+
+    void printBlockName(raw_ostream &out, BlockRef block) const;
+    void printValue(raw_ostream &out, ValueRef value) const;
+
+  private:
+    mutable std::unique_ptr<ModuleSlotTracker> m_moduleSlotTracker;
+
+    void ensureModuleSlotTracker(const Function &function) const;
+  };
+};
+
+template <> struct CfgTraitsFor<BasicBlock> { using CfgTraits = IrCfgTraits; };
+
 } // end namespace llvm
 
 #endif // LLVM_IR_CFG_H

llvm/include/llvm/Support/CfgTraits.h

+//===- CfgTraits.h - Traits for generically working on CFGs -----*- 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 traits template \ref CfgTraits as well as the
+/// \ref CfgInterface abstract interface and \ref CfgInterfaceImpl that help
+/// in writing algorithms that are generic over CFGs, e.g. operating on both
+/// LLVM IR and MachineIR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CFGTRAITS_H
+#define LLVM_SUPPORT_CFGTRAITS_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Printable.h"
+
+namespace llvm {
+
+template <typename Tag> class CfgOpaqueType;
+
+template <typename Tag>
+bool operator==(CfgOpaqueType<Tag> lhs, CfgOpaqueType<Tag> rhs);
+template <typename Tag>
+bool operator<(CfgOpaqueType<Tag> lhs, CfgOpaqueType<Tag> rhs);
+
+/// \brief Type-erased references to CFG objects (blocks, values).
+///
+/// Use CfgTraits::{wrapRef, unwrapRef} to wrap and unwrap concrete object
+/// references.
+///
+/// The most common use is to hold a pointer, but arbitrary uintptr_t values
+/// may be stored by CFGs. Note that 0, -1, and -2 have special interpretations:
+///  * 0 / nullptr: default-constructed value; evaluates to false in boolean
+///                 contexts.
+///  * -1: dense map empty marker
+///  * -2: dense map tombstone
+template <typename Tag> class CfgOpaqueType {
+  friend class CfgTraitsBase;
+  friend struct DenseMapInfo<CfgOpaqueType<Tag>>;
+  template <typename BaseTraits, typename FullTraits> friend class CfgTraits;
+  template <typename T>
+  friend bool operator==(CfgOpaqueType<T>, CfgOpaqueType<T>);
+  template <typename T>
+  friend bool operator<(CfgOpaqueType<T>, CfgOpaqueType<T>);
+
+  void *ptr = nullptr;
+
+  explicit CfgOpaqueType(void *ptr) : ptr(ptr) {}
+  void *get() const { return ptr; }
+
+public:
+  CfgOpaqueType() = default;
+
+  explicit operator bool() const { return ptr != nullptr; }
+};
+
+template <typename Tag>
+bool operator==(CfgOpaqueType<Tag> lhs, CfgOpaqueType<Tag> rhs) {
+  return lhs.get() == rhs.get();
+}
+
+template <typename Tag>
+bool operator!=(CfgOpaqueType<Tag> lhs, CfgOpaqueType<Tag> rhs) {
+  return !(lhs == rhs);
+}
+
+template <typename Tag>
+bool operator<(CfgOpaqueType<Tag> lhs, CfgOpaqueType<Tag> rhs) {
+  return lhs.get() < rhs.get();
+}
+
+template <typename Tag> struct DenseMapInfo<CfgOpaqueType<Tag>> {
+  using Type = CfgOpaqueType<Tag>;
+
+  static Type getEmptyKey() {
+    uintptr_t val = static_cast<uintptr_t>(-1);
+    return Type(reinterpret_cast<void *>(val));
+  }
+
+  static Type getTombstoneKey() {
+    uintptr_t val = static_cast<uintptr_t>(-2);
+    return Type(reinterpret_cast<void *>(val));
+  }
+
+  static unsigned getHashValue(Type val) {
+    return llvm::DenseMapInfo<void *>::getHashValue(val.get());
+  }
+  static bool isEqual(Type lhs, Type rhs) { return lhs == rhs; }
+};
+
+class CfgParentRefTag;
+using CfgParentRef = CfgOpaqueType<CfgParentRefTag>;
+
+class CfgBlockRefTag;
+using CfgBlockRef = CfgOpaqueType<CfgBlockRefTag>;
+
+class CfgValueRefTag;
+using CfgValueRef = CfgOpaqueType<CfgValueRefTag>;
+
+/// \brief Base class for CFG traits
+///
+/// Derive from this base class to define the mapping between opaque types and
+/// concrete CFG types. Then derive from \ref CfgTraits to implement
+/// operations such as traversal of the CFG.
+class CfgTraitsBase {
+protected:
+  template <typename Tag> static auto makeOpaque(void *ptr) {
+    CfgOpaqueType<Tag> ref;
+    ref.ptr = ptr;
+    return ref;
+  }
+
+  template <typename Tag> static void *getOpaque(CfgOpaqueType<Tag> opaque) {
+    return opaque.ptr;
+  }
+
+public:
+  // To be implemented by derived classes:
+  //
+  // - The type of the "parent" of the CFG, e.g. `llvm::Function`
+  //   using ParentType = ...;
+  //
+  // - The type of block references in the CFG, e.g. `llvm::BasicBlock *`
+  //   using BlockRef = ...;
+  //
+  // - The type of value references in the CFG, e.g. `llvm::Value *`
+  //   using ValueRef = ...;
+  //
+  // - Static methods for converting BlockRef and ValueRef to and from
+  //   static CfgBlockRef wrapRef(BlockRef);
+  //   static CfgValueRef wrapRef(ValueRef);
+  //   static BlockRef unwrapRef(CfgBlockRef);
+  //   static ValueRef unwrapRef(CfgValueRef);
+};
+
+/// \brief CFG traits
+///
+/// Implement CFG traits by:
+///  - Deriving from CfgTraitsBase to designate block and value types and
+///    implementing wrapRef / unwrapRef
+///  - Deriving from CfgTraits using CRTP and implement / override additional
+///    methods for CFG traversal, printing, etc.
+///
+/// This somewhat surprising two-step helps with the implementation of
+/// (un)wrapping_iterators.
+///
+template <typename BaseTraits, typename FullTraits>
+class CfgTraits : public BaseTraits {
+public:
+  using typename BaseTraits::BlockRef;
+  using typename BaseTraits::ParentType;
+  using typename BaseTraits::ValueRef;
+
+  /// Functionality to be provided by implementations:
+  ///@{
+
+  // Constructor: initialize from a pointer to the parent.
+  //   explicit CfgTraits(ParentType *parent);
+
+  // Find the parent for a given block.
+  //   static ParentType *getBlockParent(BlockRef block);
+
+  // Iterate over blocks in the CFG containing the given block in an arbitrary
+  // order (start with entry block, return a range of iterators dereferencing
+  // to BlockRef):
+  //   static auto blocks(ParentType *parent);
+
+  // Iterate over the predecessors / successors of a block (return a range
+  // of iterators dereferencing to BlockRef):
+  //   static auto predecessors(BlockRef block);
+  //   static auto successors(BlockRef block);
+
+  // Iterate over the values defined in a basic block in program order (return
+  // a range of iterators dereferencing to ValueRef):
+  //   static auto blockdefs(BlockRef block);
+
+  // Get the block in which a given value is defined. Returns a null-like
+  // BlockRef if the value is not defined in a block (e.g. it is a constant or
+  // function argument).
+  //   BlockRef getValueDefBlock(ValueRef value) const;
+
+  // struct Printer {
+  //   explicit Printer(const CfgTraits &traits);
+  //   void printBlockName(raw_ostream &out, BlockRef block) const;
+  //   void printValue(raw_ostream &out, ValueRef value) const;
+  // };
+
+  ///@}
+
+  static CfgParentRef wrapRef(ParentType *parent) {
+    return CfgParentRef{parent};
+  }
+
+  static ParentType *unwrapRef(CfgParentRef parent) {
+    return static_cast<ParentType *>(parent.get());
+  }
+
+  using BaseTraits::unwrapRef;
+  using BaseTraits::wrapRef;
+
+  template <typename BaseIteratorT> struct unwrapping_iterator;
+
+  template <typename BaseIteratorT>
+  using unwrapping_iterator_base = iterator_adaptor_base<
+      unwrapping_iterator<BaseIteratorT>, BaseIteratorT,
+      typename std::iterator_traits<BaseIteratorT>::iterator_category,
+      // value_type
+      decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>())),
+      typename std::iterator_traits<BaseIteratorT>::difference_type,
+      // pointer (not really usable, but we need to put something here)
+      decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>())) *,
+      // reference (not a true reference, because operator* doesn't return one)
+      decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>()))>;
+
+  template <typename BaseIteratorT>
+  struct unwrapping_iterator : unwrapping_iterator_base<BaseIteratorT> {
+    using Base = unwrapping_iterator_base<BaseIteratorT>;
+
+    unwrapping_iterator() = default;
+    explicit unwrapping_iterator(BaseIteratorT &&it)
+        : Base(std::forward<BaseIteratorT>(it)) {}
+
+    auto operator*() const { return BaseTraits::unwrapRef(*this->I); }
+  };
+
+  template <typename BaseIteratorT> struct wrapping_iterator;
+
+  template <typename BaseIteratorT>
+  using wrapping_iterator_base = iterator_adaptor_base<
+      wrapping_iterator<BaseIteratorT>, BaseIteratorT,
+      typename std::iterator_traits<BaseIteratorT>::iterator_category,
+      // value_type
+      decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>())),
+      typename std::iterator_traits<BaseIteratorT>::difference_type,
+      // pointer (not really usable, but we need to put something here)
+      decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>())) *,
+      // reference (not a true reference, because operator* doesn't return one)
+      decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>()))>;
+
+  template <typename BaseIteratorT>
+  struct wrapping_iterator : wrapping_iterator_base<BaseIteratorT> {
+    using Base = wrapping_iterator_base<BaseIteratorT>;
+
+    wrapping_iterator() = default;
+    explicit wrapping_iterator(BaseIteratorT &&it)
+        : Base(std::forward<BaseIteratorT>(it)) {}
+
+    auto operator*() const { return BaseTraits::wrapRef(*this->I); }
+  };
+
+  /// Convert an iterator of CfgBlockRef or CfgValueRef into an iterator of
+  /// BlockRef or ValueRef.
+  template <typename IteratorT> static auto unwrapIterator(IteratorT &&it) {
+    return unwrapping_iterator<IteratorT>(std::forward<IteratorT>(it));
+  }
+
+  /// Convert a range of CfgBlockRef or CfgValueRef into a range of
+  /// BlockRef or ValueRef.
+  template <typename RangeT> static auto unwrapRange(RangeT &&range) {
+    return llvm::make_range(
+        unwrapIterator(adl_begin(std::forward<RangeT>(range))),
+        unwrapIterator(adl_end(std::forward<RangeT>(range))));
+  }
+
+  /// Convert an iterator of BlockRef or ValueRef into an iterator of
+  /// CfgBlockRef or CfgValueRef.
+  template <typename IteratorT> static auto wrapIterator(IteratorT &&it) {
+    return wrapping_iterator<IteratorT>(std::forward<IteratorT>(it));
+  }
+
+  /// Convert a range of BlockRef or ValueRef into a range of CfgBlockRef or
+  /// CfgValueRef.
+  template <typename RangeT> static auto wrapRange(RangeT &&range) {
+    return llvm::make_range(
+        wrapIterator(adl_begin(std::forward<RangeT>(range))),
+        wrapIterator(adl_end(std::forward<RangeT>(range))));
+  }
+};
+
+/// \brief Obtain CfgTraits given the basic block type.
+///
+/// This template is provided to ease the transition to the use of CfgTraits.
+/// Existing templates e.g. over the basic block type can use this to derive
+/// the appropriate CfgTraits implementation via
+/// typename CfgTraitsFor<BlockT>::CfgTraits.
+template <typename CfgRelatedTypeT> struct CfgTraitsFor;
+// Specializations need to include:
+//   using CfgTraits = ...;
+
+class CfgPrinter;
+
+/// \brief Type-erased "CFG traits"
+///
+/// Non-template algorithms that operate generically over CFG types can use this
+/// interface to query for CFG-specific functionality.
+///
+/// Note: This interface should only be implemented by \ref CfgInterfaceImpl.
+class CfgInterface {
+  virtual void anchor();
+
+public:
+  virtual ~CfgInterface() = default;
+
+  /// Escape-hatch for obtaining a printer e.g. in debug code. Prefer to
+  /// explicitly pass a CfgPrinter where possible.
+  virtual std::unique_ptr<CfgPrinter> makePrinter() const = 0;
+
+  virtual CfgParentRef getBlockParent(CfgBlockRef block) const = 0;
+
+  virtual void appendBlocks(CfgParentRef parent,
+                            SmallVectorImpl<CfgBlockRef> &list) const = 0;
+
+  virtual void appendPredecessors(CfgBlockRef block,
+                                  SmallVectorImpl<CfgBlockRef> &list) const = 0;
+  virtual void appendSuccessors(CfgBlockRef block,
+                                SmallVectorImpl<CfgBlockRef> &list) const = 0;
+  virtual ArrayRef<CfgBlockRef>
+  getPredecessors(CfgBlockRef block,
+                  SmallVectorImpl<CfgBlockRef> &store) const = 0;
+  virtual ArrayRef<CfgBlockRef>
+  getSuccessors(CfgBlockRef block,
+                SmallVectorImpl<CfgBlockRef> &store) const = 0;
+
+  virtual void appendBlockDefs(CfgBlockRef block,
+                               SmallVectorImpl<CfgValueRef> &list) const = 0;
+  virtual CfgBlockRef getValueDefBlock(CfgValueRef value) const = 0;
+};
+
+/// \brief Type-erased "CFG printer"
+///
+/// Separate from CfgInterface because some CFG printing requires tracking
+/// expensive data structures, and we'd like to avoid the cost of
+/// (conditionally) tearing them down in the common case.
+class CfgPrinter {
+  virtual void anchor();
+
+protected:
+  const CfgInterface &m_iface;
+
+  CfgPrinter(const CfgInterface &iface) : m_iface(iface) {}
+
+public:
+  virtual ~CfgPrinter() {}
+
+  const CfgInterface &interface() const { return m_iface; }
+
+  virtual void printBlockName(raw_ostream &out, CfgBlockRef block) const = 0;
+  virtual void printValue(raw_ostream &out, CfgValueRef value) const = 0;
+
+  Printable printableBlockName(CfgBlockRef block) const {
+    return Printable(
+        [this, block](raw_ostream &out) { printBlockName(out, block); });
+  }
+  Printable printableValue(CfgValueRef value) const {
+    return Printable(
+        [this, value](raw_ostream &out) { printValue(out, value); });
+  }
+};
+
+template <typename CfgTraitsT> class CfgPrinterImpl;
+
+/// \brief Implementation of type-erased "CFG traits"
+///
+/// Note: Do not specialize this template; adjust the CfgTraits type instead
+/// where necessary.
+template <typename CfgTraitsT>
+class CfgInterfaceImpl final : public CfgInterface,
+                               private CfgTraitsT { // empty base optimization
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using ValueRef = typename CfgTraits::ValueRef;
+  using ParentType = typename CfgTraits::ParentType;
+
+  friend CfgPrinterImpl<CfgTraits>;
+
+public:
+  explicit CfgInterfaceImpl(ParentType *parent) : CfgTraits(parent) {}
+
+  std::unique_ptr<CfgPrinter> makePrinter() const final {
+    return std::make_unique<CfgPrinterImpl<CfgTraits>>(*this);
+  }
+
+  CfgParentRef getBlockParent(CfgBlockRef block) const final {
+    return CfgTraits::wrapRef(
+        CfgTraits::getBlockParent(CfgTraits::unwrapRef(block)));
+  }
+
+  void appendBlocks(CfgParentRef parent,
+                    SmallVectorImpl<CfgBlockRef> &list) const final {
+    auto range = CfgTraits::blocks(CfgTraits::unwrapRef(parent));
+    list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
+                CfgTraits::wrapIterator(std::end(range)));
+  }
+
+  void appendPredecessors(CfgBlockRef block,
+                          SmallVectorImpl<CfgBlockRef> &list) const final {
+    auto range = CfgTraits::predecessors(CfgTraits::unwrapRef(block));
+    list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
+                CfgTraits::wrapIterator(std::end(range)));
+  }
+  void appendSuccessors(CfgBlockRef block,
+                        SmallVectorImpl<CfgBlockRef> &list) const final {
+    auto range = CfgTraits::successors(CfgTraits::unwrapRef(block));
+    list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
+                CfgTraits::wrapIterator(std::end(range)));
+  }
+  ArrayRef<CfgBlockRef>
+  getPredecessors(CfgBlockRef block,
+                  SmallVectorImpl<CfgBlockRef> &store) const final {
+    // TODO: Can this be optimized for concrete CFGs that already have the
+    //       "right" in-memory representation of predecessors / successors?
+    store.clear();
+    appendPredecessors(block, store);
+    return store;
+  }
+  ArrayRef<CfgBlockRef>
+  getSuccessors(CfgBlockRef block,
+                SmallVectorImpl<CfgBlockRef> &store) const final {
+    // TODO: Can this be optimized for concrete CFGs that already have the
+    //       "right" in-memory representation of predecessors / successors?
+    store.clear();
+    appendSuccessors(block, store);
+    return store;
+  }
+
+  void appendBlockDefs(CfgBlockRef block,
+                       SmallVectorImpl<CfgValueRef> &list) const final {
+    auto range = CfgTraits::blockdefs(CfgTraits::unwrapRef(block));
+    list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
+                CfgTraits::wrapIterator(std::end(range)));
+  }
+
+  CfgBlockRef getValueDefBlock(CfgValueRef value) const final {
+    return CfgTraits::wrapRef(
+        CfgTraits::getValueDefBlock(CfgTraits::unwrapRef(value)));
+  }
+};
+
+/// \brief Implementation of type-erased "CFG traits"
+///
+/// Note: Do not specialize this template; adjust the CfgTraits type instead
+/// where necessary.
+template <typename CfgTraitsT>
+class CfgPrinterImpl : public CfgPrinter,
+                       private CfgTraitsT::Printer { // empty base optimization
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using ValueRef = typename CfgTraits::ValueRef;
+
+public:
+  explicit CfgPrinterImpl(const CfgInterfaceImpl<CfgTraits> &impl)
+      : CfgPrinter(impl), CfgTraitsT::Printer(impl) {}
+
+  void printBlockName(raw_ostream &out, CfgBlockRef block) const final {
+    CfgTraits::Printer::printBlockName(out, CfgTraits::unwrapRef(block));
+  }
+  void printValue(raw_ostream &out, CfgValueRef value) const final {
+    CfgTraits::Printer::printValue(out, CfgTraits::unwrapRef(value));
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_SUPPORT_CFGTRAITS_H

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   LocalStackSlotAllocation.cpp
   LoopTraversal.cpp
   LowLevelType.cpp
   LowerEmuTLS.cpp
   MachineBasicBlock.cpp
   MachineBlockFrequencyInfo.cpp
   MachineBlockPlacement.cpp
   MachineBranchProbabilityInfo.cpp
+  MachineCfgTraits.cpp
   MachineCombiner.cpp
   MachineCopyPropagation.cpp
   MachineCSE.cpp
   MachineDebugify.cpp
   MachineDominanceFrontier.cpp
   MachineDominators.cpp
   MachineFrameInfo.cpp
   MachineFunction.cpp

llvm/lib/CodeGen/MachineCfgTraits.cpp

+//===- MachineCycleInfo.cpp - 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineCfgTraits.h"
+
+#include "llvm/IR/BasicBlock.h"
+
+using namespace llvm;
+
+void MachineCfgTraits::Printer::printValue(raw_ostream &out,
+                                           Register value) const {
+  out << printReg(value, m_regInfo->getTargetRegisterInfo(), 0, m_regInfo);
+
+  if (value) {
+    out << ": ";
+
+    MachineInstr *instr = m_regInfo->getUniqueVRegDef(value);
+    instr->print(out);
+  }
+}
+
+void MachineCfgTraits::Printer::printBlockName(raw_ostream &out,
+                                               MachineBasicBlock *block) const {
+  block->printName(out);
+}

llvm/lib/IR/CFG.cpp

+//===- CFG.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/CFG.h"
+
+#include "llvm/IR/ModuleSlotTracker.h"
+
+using namespace llvm;
+
+IrCfgTraits::Printer::Printer(const IrCfgTraits &) {}
+IrCfgTraits::Printer::~Printer() {}
+
+void IrCfgTraits::Printer::printValue(raw_ostream &out, ValueRef value) const {
+  if (!m_moduleSlotTracker) {
+    const Function *function = nullptr;
+
+    if (auto *instruction = dyn_cast<Instruction>(value)) {
+      function = instruction->getParent()->getParent();
+    } else if (auto *argument = dyn_cast<Argument>(value)) {
+      function = argument->getParent();
+    }
+
+    if (function)
+      ensureModuleSlotTracker(*function);
+  }
+
+  if (m_moduleSlotTracker) {
+    value->print(out, *m_moduleSlotTracker, true);
+  } else {
+    value->print(out, true);
+  }
+}
+
+void IrCfgTraits::Printer::printBlockName(raw_ostream &out,
+                                          BlockRef block) const {
+  if (block->hasName()) {
+    out << block->getName();
+  } else {
+    ensureModuleSlotTracker(*block->getParent());
+    out << m_moduleSlotTracker->getLocalSlot(block);
+  }
+}
+
+void IrCfgTraits::Printer::ensureModuleSlotTracker(
+    const Function &function) const {
+  if (!m_moduleSlotTracker) {
+    m_moduleSlotTracker =
+        std::make_unique<ModuleSlotTracker>(function.getParent(), false);
+    m_moduleSlotTracker->incorporateFunction(function);
+  }
+}

llvm/lib/IR/CMakeLists.txt

 add_llvm_component_library(LLVMCore
   AbstractCallSite.cpp
   AsmWriter.cpp
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
   Constants.cpp
   Core.cpp
   DIBuilder.cpp
   DataLayout.cpp
   DebugInfo.cpp

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   BinaryStreamError.cpp
   BinaryStreamReader.cpp
   BinaryStreamRef.cpp
   BinaryStreamWriter.cpp
   BlockFrequency.cpp
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
   CodeGenCoverage.cpp
   CommandLine.cpp
   Compression.cpp
   CRC.cpp
   ConvertUTF.cpp

llvm/lib/Support/CfgTraits.cpp

+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}

llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
 
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+    return makeOpaque<CfgBlockRefTag>(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+    return static_cast<BlockRef>(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits<VPCfgTraitsBase, VPCfgTraits> {
+public:
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+    return block->getParent();
+  }
+
+  static auto predecessors(VPBlockBase *block) {
+    return llvm::inverse_children<VPBlockBase *>(block);
+  }
+
+  static auto successors(VPBlockBase *block) {
+    return llvm::children<VPBlockBase *>(block);
+  }
+};
+
+template <> struct CfgTraitsFor<VPBlockBase> { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase<VPBlockBase>;
 
 using VPDomTreeNode = DomTreeNodeBase<VPBlockBase>;
 
 /// Template specializations of GraphTraits for VPDomTreeNode.
 template <>

mlir/include/mlir/IR/Dominance.h

 //===- Dominance.h - Dominator analysis for CFGs ----------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_IR_DOMINANCE_H
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+    return makeOpaque<llvm::CfgBlockRefTag>(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+    return static_cast<BlockRef>(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits<CfgTraitsBase, CfgTraits> {
+public:
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+  static auto predecessors(Block *block) {
+    return llvm::inverse_children<Block *>(block);
+  }
+
+  static auto successors(Block *block) {
+    return llvm::children<Block *>(block);
+  }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor<mlir::Block> {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase<mlir::Block, false>;
 extern template class llvm::DominatorTreeBase<mlir::Block, true>;
 
 namespace mlir {
 using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
 class Operation;
 
 namespace detail {