Page MenuHomePhabricator

Introduce CfgTraits abstraction
AbandonedPublic

Authored by nhaehnle on Jul 2 2020, 2:08 PM.

Details

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

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
arsenm added inline comments.Jul 3 2020, 7:56 AM
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 updated this revision to Diff 275811.Jul 6 2020, 1:02 PM
nhaehnle marked 4 inline comments as done.
  • fix MachineCfgTraits::blockdef_iterator and allow it to iterate over the instructions in a bundle
  • use MachineBasicBlock::printName
nhaehnle added inline comments.Jul 6 2020, 1:05 PM
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
arsenm added inline comments.Jul 6 2020, 1:51 PM
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 marked an inline comment as done.Jul 10 2020, 9:01 AM
nhaehnle added inline comments.
llvm/include/llvm/CodeGen/MachineCfgTraits.h
137–139

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

arsenm added inline comments.Jul 17 2020, 10:43 AM
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 marked 3 inline comments as done.Jul 24 2020, 8:40 AM
nhaehnle added inline comments.
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 updated this revision to Diff 280481.Jul 24 2020, 9:12 AM
nhaehnle marked an inline comment as done.
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 added inline comments.Jul 28 2020, 8:02 AM
clang/include/clang/Analysis/Analyses/Dominators.h
50

Missing space nullpointers, missing s succesors

51

s/it's/its/

nhaehnle updated this revision to Diff 284195.Aug 9 2020, 7:13 AM
nhaehnle marked 2 inline comments as done.
v7:
- std::forward fix in wrapping_iterator
- fix typos

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)

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.

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?

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.

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

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.

RKSimon resigned from this revision.Aug 16 2020, 11:02 AM

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.

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.

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.

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 added a comment.Aug 19 2020, 2:21 PM

Hi Nicoali,

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

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.

(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?)

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.

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 updated this revision to Diff 287441.Aug 24 2020, 10:29 AM
  • cleanup operators on CfgOpaqueType
  • address other review comments
nhaehnle added inline comments.Sep 7 2020, 7:38 AM
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.

arsenm accepted this revision.Oct 16 2020, 7:24 AM
This revision is now accepted and ready to land.Oct 16 2020, 7:24 AM
This revision was landed with ongoing or failed builds.Oct 20 2020, 4:51 AM
This revision was automatically updated to reflect the committed changes.
rriddle added inline comments.Oct 20 2020, 9:56 AM
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;
dblaikie reopened this revision.Oct 20 2020, 1:58 PM

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

This revision is now accepted and ready to land.Oct 20 2020, 1:58 PM

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!

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?

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

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 added a comment.EditedOct 23 2020, 8:16 AM

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.

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

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

I replied on llvm-dev.

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.

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

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