Nicolai Hähnle via llvm-dev
2020-Oct-21 19:57 UTC
[llvm-dev] RFC: CfgTraits/CfgInterface design discussion
Hi all, I'm moving a discussion from https://reviews.llvm.org/D83088 here, where it's arguably more appropriate. For context, I proposed in early July a mechanism that allows writing program analyses that are generic over the type of IR using dynamic dispatch (virtual methods). The first mail of the llvm-dev thread is here: http://lists.llvm.org/pipermail/llvm-dev/2020-July/143039.html The change was more than three months in review, including some very long stretches of radio silence. The change was accepted on Friday and, after waiting a few more days, I pushed it yesterday. Now some concerns are being raised on the review. I don't necessarily want to discuss the dysfunctions of our review process here. I also don't want to steamroll those concerns because I don't want us to follow a misguided notion of "progress at all cost", but I do think progress is important. So I propose that we discuss perceived shortcomings of the design here. If folks here can provide a sense of changes to the design they'd actually be happy with, then I'm happy to spin up the required patches to improve the design.[0] With that in mind, let me "import" the last comment on the Phabricator review:> > > 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.I assume you're not talking about runtime overhead here? If we're talking about that, I'd expect that variant to often be slower, although I obviously don't have numbers. If it's the code style you're concerned about, yeah, I'm happy to prepare a patch that extends the interface with forEachSuccessor / forEachPredecessor methods like `void forEachSuccessor(CfgBlockRef, std::function<void (CfgBlockRef)>)`.> > [discussion on printBlockName and similar methods] > 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?It's mostly a matter of debuggability of the algorithms that are being written. Pragmatism is the key. Example: The current in-tree DivergenceAnalysis leaves debug messages like: LLVM_DEBUG(dbgs() << "propBranchDiv " << Term.getParent()->getName() << "\n"); In the new CfgTraits-based divergence analysis I'm working on, a similar point in the algorithm has: LLVM_DEBUG(dbgs() << "DIVERGENT TERMINATOR: " << printer().printableBlockName(divergentBlock) << '\n'); At this point, divergentBlock is a CfgBlockRef, which is simply an opaque wrapper around a type-erased pointer. So the only other thing we could do here is print out the pointer value, which makes for an awful debugging experience. I'll point out again that existing template-based generic algorithms have leaky interfaces: some parts of the dominator tree machinery call the node type's `printAsOperand`.> > [broader discussion] > 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).I agree that the first form is nicer. I'd raise two points. First, the first form works nicely if the concept of container is sufficiently well understood and all relevant containers really are sufficiently similar. Neither is the case here. We're trying to cover different pre-existing IRs, and even though all of them are SSA IRs, the differences are substantial. Currently, we only really care about LLVM IR and MachineIR in SSA form; their main differences is that the concept of "value" is a C++ object in LLVM IR, while in MIR-SSA it's a plain unsigned int (now wrapped in a Register). MLIR would add yet another way of thinking about values. The fact that we have to work with those pre-existing IRs means we have to compromise. Second, none of this applies to dynamic polymorphism, which is really the main goal here at least for me. Not sure where that leaves us. We need something like CfgTraits to cover the substantial differences between the IRs, but perhaps we can work over time to reduce those differences? Over time, instead of relying on CfgTraits for _everything_ in CfgInterfaceImpl, we could instead use unified functionalities directly? Some of that could probably already be done today. For example, we could probably just use llvm::successors directly in CfgInterfaceImpl::appendSuccessors (and your proposed forEachSuccessor) instead of going via CfgTraits.> 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 << '}'; > }Yes, though it wouldn't quite work like that with the IRs we have in LLVM. Most of them go to great length to avoid embedding virtual methods in the IR classes themselves. That's why you'd more likely see something like the following: void print(const CfgInterface& iface, CfgBlockRef block, raw_ostream& out) { out << "Successors of " << iface.printableName(block) << ':'; iface.forEachSuccessor(block, [&](CfgBlockRef succ) { if (first) out << ' '; else out << ", "; first = false; iface.printName(succ, out); }); out << '\n'; } The CfgBlockRef / CfgValueRef / etc. appear in the design to avoid having an abstract base class for the different IRs, and also to cover the difference between LLVM IR `Value *` and MIR-SSA `Register`.> 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).I don't really care that much about what the static side of things looks like. CfgTraits is the way it is on purpose because I felt it would be useful to have a homogenous view of what generic aspects of IR will ultimately be exposed by the CfgInterface. In the absence of compiler-enforced concepts, that feels helpful to me. If you put yourself in the shoes of an author of an algorithm that is supposed to be generic over IRs, you'll realize that it's great to have some easy way of discovering which things really _are_ generic over IRs. The comparison with containers is slightly lacking because the potential surface area is so much larger. But perhaps we can iterate on the design and find a better way. This is kind of a restatement of what I wrote above: If we can get general agreement in the community that there is a desire that the different IRs in LLVM follow common concepts "directly", then we can iterate towards that over time. I'm personally convinced that unifying the various IRs is a worthy goal (the introduction of MLIR really was an unfortunate step backwards as far as that is concerned), it just feels like it'd be a thankless project because it would go through _many_ reviews that feel like the one that triggered this thread. Even without a dysfunctional review process it'd be a long refactoring, and some sort of trait class is unavoidable at least for now. At a minimum, something is needed to abstract over the large differences between SSA value representations. Cheers, Nicolai [0] What I'm _not_ going to do is write patches based on vague guesses of what other people might want. I don't want even more changes hanging in Phabricator limbo for months. Be explicit about what it is that you want, and we can make progress. -- Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.
David Blaikie via llvm-dev
2020-Oct-21 20:35 UTC
[llvm-dev] RFC: CfgTraits/CfgInterface design discussion
Hey Nicolai, On Wed, Oct 21, 2020 at 12:57 PM Nicolai Hähnle via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi all, > > I'm moving a discussion from https://reviews.llvm.org/D83088 here, > where it's arguably more appropriate. > > For context, I proposed in early July a mechanism that allows writing > program analyses that are generic over the type of IR using dynamic > dispatch (virtual methods). The first mail of the llvm-dev thread is > here: http://lists.llvm.org/pipermail/llvm-dev/2020-July/143039.html > > The change was more than three months in review, including some very > long stretches of radio silence. The change was accepted on Friday > and, after waiting a few more days, I pushed it yesterday. Now some > concerns are being raised on the review. > > I don't necessarily want to discuss the dysfunctions of our review > process here. I also don't want to steamroll those concerns because I > don't want us to follow a misguided notion of "progress at all cost", > but I do think progress is important. >Sure enough - and apologies for the delays.> So I propose that we discuss perceived shortcomings of the design > here. If folks here can provide a sense of changes to the design > they'd actually be happy with, then I'm happy to spin up the required > patches to improve the design.I'm still fairly concerned this isn't a matter of fixing it in-tree & not especially happy with the inversion that's occurred here (now it's "this goes ahead unless I can justify why it shouldn't", whereas previously it was "this doesn't go ahead unless you can justify why it should" - that's a pretty significant change) which is why I'd like to revert the patch first, and discuss second. This is generally the bar for LLVM reviews - if there are outstanding concerns, patches don't move forward. This doesn't mean arbitrary hold-up, and there's admittedly some problems with how to resolve irreconcilable differences, usually by escalating to other, more senior community members to make a determination. Ultimately, given the fairly large surface area/intended use of this abstraction, I think it might rise to the level of using the proposed "contentious decision" process discussed here: https://github.com/llvm/llvm-www/blob/master/proposals/LP0001-LLVMDecisionMaking.md Other folks weighing in would be great & certainly there's a line at which my opinion isn't the gatekeeper here if other folks are in favor.> [0] With that in mind, let me "import" > the last comment on the Phabricator review: > > > > > > 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. > > I assume you're not talking about runtime overhead here? If we're > talking about that, I'd expect that variant to often be slower, > although I obviously don't have numbers. >I think I was referring to runtime overhead - you mentioned the increase in indirect calls. A callback-like API can reduce the number of such calls. (rather than one virtual call per increment, inequality test, and dereference - there would be only one polmorphic call per iteration)> If it's the code style you're concerned about, yeah, I'm happy to > prepare a patch that extends the interface with forEachSuccessor / > forEachPredecessor methods like `void forEachSuccessor(CfgBlockRef, > std::function<void (CfgBlockRef)>)`. > > > > > [discussion on printBlockName and similar methods] > > 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? > > It's mostly a matter of debuggability of the algorithms that are being > written. Pragmatism is the key. > > Example: The current in-tree DivergenceAnalysis leaves debug messages like: > > LLVM_DEBUG(dbgs() << "propBranchDiv " << Term.getParent()->getName() << > "\n"); > > In the new CfgTraits-based divergence analysis I'm working on, a > similar point in the algorithm has: > > LLVM_DEBUG(dbgs() << "DIVERGENT TERMINATOR: " > << printer().printableBlockName(divergentBlock) << > '\n'); > > At this point, divergentBlock is a CfgBlockRef, which is simply an > opaque wrapper around a type-erased pointer. So the only other thing > we could do here is print out the pointer value, which makes for an > awful debugging experience. > > I'll point out again that existing template-based generic algorithms > have leaky interfaces: some parts of the dominator tree machinery call > the node type's `printAsOperand`. >That isn't a necessary feature of template-based generic algorithms, and I agree that the traits-based API probably isn't the best one for something as complicated as a graph, especially as we've added more features to them. Something more like a container abstraction seems more suitable (especially since it would allow carrying more payload in a Graph object itself when writing a decorator - which currently can't be done so such a payload ends up being carried around in heavyweight node pointers/iterators which is awkward)> > > > > [broader discussion] > > 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). > > I agree that the first form is nicer. I'd raise two points. > > First, the first form works nicely if the concept of container is > sufficiently well understood and all relevant containers really are > sufficiently similar.I'm not sure how a dynamic interface is likely to be significantly different/better in this regard.> Neither is the case here. We're trying to cover > different pre-existing IRs, and even though all of them are SSA IRs, > the differences are substantial.I guess that's another thing that might benefit from further clarity: Currently we have generic graph traits, notionally that's for any graph (collection of nodes and edges). The proposed abstraction is for CFG graphs, but due to the added layers of abstraction complexity, dynamic and static APIs, etc, it's not been especially clear to me what makes this abstraction specific to/only for CFG graphs[1] (& then how that relates to IR I'm not sure either - control flow seems like it would be fairly independent of the values within that graph).> Currently, we only really care about > LLVM IR and MachineIR in SSA form; their main differences is that the > concept of "value" is a C++ object in LLVM IR, while in MIR-SSA it's a > plain unsigned int (now wrapped in a Register). MLIR would add yet > another way of thinking about values. The fact that we have to work > with those pre-existing IRs means we have to compromise. >Not sure I follow what compromises you're referring to - if we have a container abstraction, some containers are over ints, some over objects, etc - the container can specify via typedefs, for instance, what type its elements are.> Second, none of this applies to dynamic polymorphism, which is really > the main goal here at least for me. >And one I'm trying to push back on - my hope is that a common set of abstractions (much like the container concepts in the STL) would be suitable here. To potentially subsume the existing GraphTraits (could have a "GraphTraits adapter" that gives a Graph-concept-implementing-container given GraphTraits) and potentially has layers to add on more expressive/narrower abstractions (whatever extra features are relevant to CFG graphs that aren't relevant to all graphs in general([1] above - not super sure what those are)) - much like generic C++ containers, to sequential containers, random access containers, etc - various refinements of the general concept of a container. What I'm especially interested in is not having two distinct concepts of graphs and graph algorithms with no plan to merge/manage these together, since as you say, the algorithms are complicated enough already - having two distinct and potentially competing abstractions in LLVM seems harmful to the codebase.> Not sure where that leaves us. We need something like CfgTraits to > cover the substantial differences between the IRs, but perhaps we can > work over time to reduce those differences? Over time, instead of > relying on CfgTraits for _everything_ in CfgInterfaceImpl, we could > instead use unified functionalities directly? > > Some of that could probably already be done today. For example, we > could probably just use llvm::successorsBy way of example, I /think/ the future we'd probably all want for llvm::successors would be to move towards entities having their own successors() function rather than the non-member/ADL-based lookup. (the same way that it's far more common/readable/expected to use x.begin() rather than "using std::begin; begin(x);" construct, or wrapping that in some std::adl_begin(x) function)> directly in > CfgInterfaceImpl::appendSuccessors (and your proposed > forEachSuccessor) instead of going via CfgTraits. > > > > 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 << '}'; > > } > > Yes, though it wouldn't quite work like that with the IRs we have in > LLVM. Most of them go to great length to avoid embedding virtual > methods in the IR classes themselves. That's why you'd more likely see > something like the following: > > void print(const CfgInterface& iface, CfgBlockRef block, raw_ostream& out) > { > out << "Successors of " << iface.printableName(block) << ':'; > iface.forEachSuccessor(block, [&](CfgBlockRef succ) { > if (first) > out << ' '; > else > out << ", "; > first = false; > iface.printName(succ, out); > }); > out << '\n'; > } > > The CfgBlockRef / CfgValueRef / etc. appear in the design to avoid > having an abstract base class for the different IRs, and also to cover > the difference between LLVM IR `Value *` and MIR-SSA `Register`. >If a dynamically polymorphic API is needed/ends up being chosen, I'd /probably/ be inclined to try to add an abstract base class for blocks too (unclear about values) - but not wedded to it. In general I'm more pushing back on the dynamically polymorphic API in general than what it might look like if it exists. In part because of the complexities of having opaque handle objects that are passed out and back into APIs to model things, rather than being able to model them more directly. The APIs become a bit unwieldy because of that, in my opinion. (again, looking at GraphTraits awkwardness of load-bearing node pointers - though having the graph as a parameter ('this' parameter or otherwise) to the edge/successor/etc queries (rather than having the queries only based on the node) would go a long way to addressing that particular shortcoming if such a token/ref-passing API were needed)> > 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). > > I don't really care that much about what the static side of things > looks like. CfgTraits is the way it is on purpose because I felt it > would be useful to have a homogenous view of what generic aspects of > IR will ultimately be exposed by the CfgInterface. In the absence of > compiler-enforced concepts, that feels helpful to me. If you put > yourself in the shoes of an author of an algorithm that is supposed to > be generic over IRs,Perhaps that's part of my confusion - generic over IRs sounds like a far richer/more complicated API than generic over CFGs.> you'll realize that it's great to have some easy > way of discovering which things really _are_ generic over IRs.Writing out the concept would be a good start, I think, same as the C++ standard does for containers. (not to the kind of C++ language-lawyerly level of detail, but the basic summary of the conceptual API - independent of any of the implementation choices so far considered - this is why I'd really like to see especially trivial/mock use cases, yeah, they won't be representative of the full complexity of the API in use, but give a sense of what the semantics of the API are so we can consider different syntactic/implementation choices)> The > comparison with containers is slightly lacking because the potential > surface area is so much larger. But perhaps we can iterate on the > design and find a better way. >Larger surface area somewhat concerns me and why I'd like to see more sort of example usage to get a better sense of what this is expected to abstract over now and in the future.> This is kind of a restatement of what I wrote above: If we can get > general agreement in the community that there is a desire that the > different IRs in LLVM follow common concepts "directly", then we can > iterate towards that over time. I'm personally convinced that unifying > the various IRs is a worthy goal (the introduction of MLIR really was > an unfortunate step backwards as far as that is concerned), it just > feels like it'd be a thankless project because it would go through > _many_ reviews that feel like the one that triggered this thread.Perhaps - though getting design review/directional buy-in first can go a long way to making incremental reviews much less contentious/easier to commit. And a design that can be implemented via incremental improvement can also mean smaller patches that are easier to review/commit.> Even > without a dysfunctional review process it'd be a long refactoring, and > some sort of trait class is unavoidable at least for now. At a > minimum, something is needed to abstract over the large differences > between SSA value representations. > > Cheers, > Nicolai > > [0] What I'm _not_ going to do is write patches based on vague guesses > of what other people might want. I don't want even more changes > hanging in Phabricator limbo for months. Be explicit about what it is > that you want, and we can make progress. > > -- > Lerne, wie die Welt wirklich ist, > aber vergiss niemals, wie sie sein sollte. > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201021/a09bf4fe/attachment-0001.html>
Nicolai Hähnle via llvm-dev
2020-Oct-22 11:32 UTC
[llvm-dev] RFC: CfgTraits/CfgInterface design discussion
Hi David, On Wed, Oct 21, 2020 at 10:35 PM David Blaikie <dblaikie at gmail.com> wrote:> On Wed, Oct 21, 2020 at 12:57 PM Nicolai Hähnle via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> So I propose that we discuss perceived shortcomings of the design >> here. If folks here can provide a sense of changes to the design >> they'd actually be happy with, then I'm happy to spin up the required >> patches to improve the design. > > > I'm still fairly concerned this isn't a matter of fixing it in-tree & not especially happy with the inversion that's occurred here (now it's "this goes ahead unless I can justify why it shouldn't", whereas previously it was "this doesn't go ahead unless you can justify why it should" - that's a pretty significant change) which is why I'd like to revert the patch first, and discuss second. > > This is generally the bar for LLVM reviews - if there are outstanding concerns, patches don't move forward. This doesn't mean arbitrary hold-up, and there's admittedly some problems with how to resolve irreconcilable differences, usually by escalating to other, more senior community members to make a determination. Ultimately, given the fairly large surface area/intended use of this abstraction, I think it might rise to the level of using the proposed "contentious decision" process discussed here: https://github.com/llvm/llvm-www/blob/master/proposals/LP0001-LLVMDecisionMaking.mdYes, which is part of why I thought we should move this to llvm-dev. One issue I'm having with this discussion if I'm being honest is that despite all the back and forth I _still_ barely know what your opinion is, or whether you even have one. This puts me in a difficult situation. I have no indication of whether there is _any_ version of this that you would accept, and if so, what it would look like, so there is no way forward for me. In the meantime, there is a substantial (and increasing) amount of work that builds on what we're talking about here.> Other folks weighing in would be great & certainly there's a line at which my opinion isn't the gatekeeper here if other folks are in favor.Agreed. Part of the dysfunction here is that it's difficult to get people to pay attention in the first place. The few folks who replied to my llvm-dev thread in July did have questions but seemed to be generally okay with the direction.>> [0] With that in mind, let me "import" >> the last comment on the Phabricator review: >> >> >> > > > 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. >> >> I assume you're not talking about runtime overhead here? If we're >> talking about that, I'd expect that variant to often be slower, >> although I obviously don't have numbers. > > > I think I was referring to runtime overhead - you mentioned the increase in indirect calls. A callback-like API can reduce the number of such calls. (rather than one virtual call per increment, inequality test, and dereference - there would be only one polmorphic call per iteration)CfgInterface::appendSuccessors requires only a single indirect call for the entire loop, which is why I chose to do that over some getSuccessorByIndex-type interface. A CfgInterface::forEachSuccessor method is a trade-off: it's an interface that is more in line with patterns you see elsewhere (std::for_each), at the cost of more indirect calls. [snip[>> > 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). >> >> I agree that the first form is nicer. I'd raise two points. >> >> First, the first form works nicely if the concept of container is >> sufficiently well understood and all relevant containers really are >> sufficiently similar. > > > I'm not sure how a dynamic interface is likely to be significantly different/better in this regard.It's mostly orthogonal. Though dynamic polymorphism does end up having better compiler support for _enforcing_ concepts. This is a common theme in this discussion: the tooling support for dynamic polymorphism is far better. That matters.>> Neither is the case here. We're trying to cover >> different pre-existing IRs, and even though all of them are SSA IRs, >> the differences are substantial. > > > I guess that's another thing that might benefit from further clarity: Currently we have generic graph traits, notionally that's for any graph (collection of nodes and edges). The proposed abstraction is for CFG graphs, but due to the added layers of abstraction complexity, dynamic and static APIs, etc, it's not been especially clear to me what makes this abstraction specific to/only for CFG graphs[1] (& then how that relates to IR I'm not sure either - control flow seems like it would be fairly independent of the values within that graph).Maybe it would help if CfgTraits was renamed to SsaTraits? Or SsaCfgTraits? Being able to do some limited inspection of the SSA values (and instructions, really) is key to what we're trying to do here -- there's an example below. If this was only about nodes and edges, I would have added dynamic polymorphism on top of the existing GraphTraits.>> Currently, we only really care about >> LLVM IR and MachineIR in SSA form; their main differences is that the >> concept of "value" is a C++ object in LLVM IR, while in MIR-SSA it's a >> plain unsigned int (now wrapped in a Register). MLIR would add yet >> another way of thinking about values. The fact that we have to work >> with those pre-existing IRs means we have to compromise. > > > Not sure I follow what compromises you're referring to - if we have a container abstraction, some containers are over ints, some over objects, etc - the container can specify via typedefs, for instance, what type its elements are.Simple example: Let's say we have an SSA value and need to find the basic block in which it is defined. In LLVM IR, that's `value->getParent()`, where value is an `llvm::Value*`. In SSA-form MachineIR, that's `m_machineRegInfo->getVRegDef(value)->getParent()`, where value is an `llvm::Register`. In MLIR, that's `value.getParentBlock()`, where value is an `mlir::Value`. This kind of operation is needed for a complete divergence analysis, and so it needs to be abstracted somehow.>> Second, none of this applies to dynamic polymorphism, which is really >> the main goal here at least for me. > > > And one I'm trying to push back on - my hope is that a common set of abstractions (much like the container concepts in the STL) would be suitable here. To potentially subsume the existing GraphTraits (could have a "GraphTraits adapter" that gives a Graph-concept-implementing-container given GraphTraits) and potentially has layers to add on more expressive/narrower abstractions (whatever extra features are relevant to CFG graphs that aren't relevant to all graphs in general([1] above - not super sure what those are)) - much like generic C++ containers, to sequential containers, random access containers, etc - various refinements of the general concept of a container. > > What I'm especially interested in is not having two distinct concepts of graphs and graph algorithms with no plan to merge/manage these together, since as you say, the algorithms are complicated enough already - having two distinct and potentially competing abstractions in LLVM seems harmful to the codebase.It seems to me that there are two orthogonal issues here. One is whether dynamic polymorphism can be used or not. If you're in fundamental opposition to that, then we have a serious problem (a bit on that further down). Dynamic polymorphism doesn't contradict the goal of a common set of abstractions. The other is how _exactly_ the abstractions are factored. For example, on the dynamic polymorphism side we could have: - a `GraphInterface` class which provides methods for iterating predecessors and successors of `CfgBlockRef` (presumably we'd rename that to something like NodeRef?), and - an `SsaCfgInterface` class which provides additional methods for instructions and values. The question is whether you'd be willing to support something like that eventually, once we've hashed it out.>> Not sure where that leaves us. We need something like CfgTraits to >> cover the substantial differences between the IRs, but perhaps we can >> work over time to reduce those differences? Over time, instead of >> relying on CfgTraits for _everything_ in CfgInterfaceImpl, we could >> instead use unified functionalities directly? >> >> Some of that could probably already be done today. For example, we >> could probably just use llvm::successors > > > By way of example, I /think/ the future we'd probably all want for llvm::successors would be to move towards entities having their own successors() function rather than the non-member/ADL-based lookup. (the same way that it's far more common/readable/expected to use x.begin() rather than "using std::begin; begin(x);" construct, or wrapping that in some std::adl_begin(x) function)Makes sense, though it doesn't really respond to what I was writing here. My point was about how the bridge between the world of dynamic polymorphism and that of static polymorphism works.>> directly in >> CfgInterfaceImpl::appendSuccessors (and your proposed >> forEachSuccessor) instead of going via CfgTraits. >> >> >> > 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 << '}'; >> > } >> >> Yes, though it wouldn't quite work like that with the IRs we have in >> LLVM. Most of them go to great length to avoid embedding virtual >> methods in the IR classes themselves. That's why you'd more likely see >> something like the following: >> >> void print(const CfgInterface& iface, CfgBlockRef block, raw_ostream& out) { >> out << "Successors of " << iface.printableName(block) << ':'; >> iface.forEachSuccessor(block, [&](CfgBlockRef succ) { >> if (first) >> out << ' '; >> else >> out << ", "; >> first = false; >> iface.printName(succ, out); >> }); >> out << '\n'; >> } >> >> The CfgBlockRef / CfgValueRef / etc. appear in the design to avoid >> having an abstract base class for the different IRs, and also to cover >> the difference between LLVM IR `Value *` and MIR-SSA `Register`. > > > If a dynamically polymorphic API is needed/ends up being chosen, I'd /probably/ be inclined to try to add an abstract base class for blocks too (unclear about values) - but not wedded to it. In general I'm more pushing back on the dynamically polymorphic API in general than what it might look like if it exists. In part because of the complexities of having opaque handle objects that are passed out and back into APIs to model things, rather than being able to model them more directly. The APIs become a bit unwieldy because of that, in my opinion. (again, looking at GraphTraits awkwardness of load-bearing node pointers - though having the graph as a parameter ('this' parameter or otherwise) to the edge/successor/etc queries (rather than having the queries only based on the node) would go a long way to addressing that particular shortcoming if such a token/ref-passing API were needed)In the end, it boils down to a tooling issue, which in turn is a C++ language issue. When you're writing template code, you're basically throwing the type system out of the window. Sure, it comes back in once you _instantiate_ the template, but that doesn't help if all the complexity is in the template code. The kinds of algorithms we're trying to write have enough inherent complexity as it is. Asking us to simultaneously fight the accidental complexity caused by how C++ templates work is unreasonable. The sentiment that C++ templates hurt here has been shared in this discussion by people with experience working on the dominator tree implementation (which is arguably a simpler problem than what we're trying to solve). Keep in mind that it's not just a question of current development but also of maintainability going forward. It would help to understand _which_ APIs you think are becoming unwieldy, because you may be imagining something misleading. For example, consider the updated generic dominator tree. It has a `GenericDominatorTreeBase` class which is type-erased and provides all the usual query functions in terms of opaque handles. Then there is a derived `DominatorTreeBase<NodeT>` class. If you're writing a non-generic algorithm, or a template-generic algorithm, you never interact with GenericDominatorTreeBase directly. Instead, you interact with `DominatorTreeBase<NodeT>`, which has all the usual methods where you pass in `NodeT*` instead of opaque handles. You only interact with GenericDominatorTreeBase directly if you're writing a dynamically-generic algorithm, where you consciously chose to enter the world of opaque handles. There ends up being some boilerplate for wrapping/unwrapping opaque handles in `DominatorTreeBase<NodeT>`, but it's pretty straightforward and hidden from users of the class. (FWIW, the updated dominator tree analysis itself is still implemented as a template. I converted it to dynamic polymorphism as an experiment, and there was one outlier test case with 1-2% compile time performance loss. I haven't pursued this further, and I don't want to convert this particular algorithm just for the sake of it. The update to dominator trees is only intended to allow other, more complex algorithms to be built on top of it using dynamic polymorphism.) If you're looking for an example of an algorithm that is written using dynamic polymorphism, you could take a look here: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp>> > 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). >> >> I don't really care that much about what the static side of things >> looks like. CfgTraits is the way it is on purpose because I felt it >> would be useful to have a homogenous view of what generic aspects of >> IR will ultimately be exposed by the CfgInterface. In the absence of >> compiler-enforced concepts, that feels helpful to me. If you put >> yourself in the shoes of an author of an algorithm that is supposed to >> be generic over IRs, > > > Perhaps that's part of my confusion - generic over IRs sounds like a far richer/more complicated API than generic over CFGs.Yes, indeed :)>> you'll realize that it's great to have some easy >> way of discovering which things really _are_ generic over IRs. > > > Writing out the concept would be a good start, I think, same as the C++ standard does for containers. (not to the kind of C++ language-lawyerly level of detail, but the basic summary of the conceptual API - independent of any of the implementation choices so far considered - this is why I'd really like to see especially trivial/mock use cases, yeah, they won't be representative of the full complexity of the API in use, but give a sense of what the semantics of the API are so we can consider different syntactic/implementation choices)The complete set of operations we seem to need is in CfgInterface and CfgPrinter. I do have some further development on it, where they look as follows: 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 bool comesBefore(CfgInstructionRef lhs, CfgInstructionRef rhs) 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; }; 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; virtual void printInstruction(raw_ostream &out, CfgInstructionRef instruction) 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); }); } Printable printableInstruction(CfgInstructionRef instruction) const { return Printable([this, instruction](raw_ostream &out) { printInstruction(out, instruction); }); } }; Iterating over this design in-tree seems perfectly viable to me.>> The >> comparison with containers is slightly lacking because the potential >> surface area is so much larger. But perhaps we can iterate on the >> design and find a better way. > > > Larger surface area somewhat concerns me and why I'd like to see more sort of example usage to get a better sense of what this is expected to abstract over now and in the future.See the example GenericUniformAnalysis I linked to above.>> This is kind of a restatement of what I wrote above: If we can get >> general agreement in the community that there is a desire that the >> different IRs in LLVM follow common concepts "directly", then we can >> iterate towards that over time. I'm personally convinced that unifying >> the various IRs is a worthy goal (the introduction of MLIR really was >> an unfortunate step backwards as far as that is concerned), it just >> feels like it'd be a thankless project because it would go through >> _many_ reviews that feel like the one that triggered this thread. > > > Perhaps - though getting design review/directional buy-in first can go a long way to making incremental reviews much less contentious/easier to commit. And a design that can be implemented via incremental improvement can also mean smaller patches that are easier to review/commit.If people were paying attention, sure :) Unfortunately, that's not how things seem to work in practice... I'm all for smaller patches as well, which is part of why I think in-tree iteration is better. Cheers, Nicolai> >> >> Even >> without a dysfunctional review process it'd be a long refactoring, and >> some sort of trait class is unavoidable at least for now. At a >> minimum, something is needed to abstract over the large differences >> between SSA value representations. >> >> Cheers, >> Nicolai >> >> [0] What I'm _not_ going to do is write patches based on vague guesses >> of what other people might want. I don't want even more changes >> hanging in Phabricator limbo for months. Be explicit about what it is >> that you want, and we can make progress. >> >> -- >> Lerne, wie die Welt wirklich ist, >> aber vergiss niemals, wie sie sein sollte. >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.