[llvm-dev] RFC: CfgTraits/CfgInterface design discussion

[Nicolai Hähnle via llvm-dev]

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.