llvm dev - Feb 2021 - [RFC] Abstracting over SSA form IRs to implement generic analyses

Hi LLVM community,

Earlier this year I first proposed a new way of writing analyses that can
be applied to multiple IRs, for example, applying the same analysis to both
LLVM IR and MachineIR.

LLVM already has some analyses like that; for example, dominator tree
construction and loop info. However, they're all limited to looking at the
control flow graph: basic blocks and lists of predecessors and successors.
We want to push the envelope with a divergence analysis that is also aware
of instructions and values, and ran into severe limitations in what we
could do with the techniques that are commonly used in LLVM today. Some
limitations are around which concepts are exposed generically at all,
though the bulk of limitations revolves around readability and
maintainability of the resulting generic code.

After more evolution of the ideas and many discussions over the last few
months, I want to raise this proposal once more -- this time with an
extensive document:
https://docs.google.com/document/d/1sbeGw5uNGFV0ZPVk6h8Q5_dRhk4qFnKHa-uZ-O3c4UY/edit?usp=sharing

Feel free to comment on the document, though high-level discussion is
probably best kept in this email thread.

The concrete proposal is to enable 4 tools for use by generic analyses:

- type erasure
- an SsaContext context class concept with a fairly small surface area
- dynamic polymorphism via per-analysis adapters
- dynamic polymorphism via an LLVM-wide adapter of SsaContext

The document goes to some length to explain what precisely is meant by each
of those bullets, including code examples, as well as describing a few
other options that we _don't_ propose, based on their relative merits.

There are concrete patches that go along with the proposal and you can
refer to for additional context. In logical sequence, they are:
- https://reviews.llvm.org/D92924: Introduce opaque handles for type erasure
- https://reviews.llvm.org/D83089: Based on the handle infrastructure,
refactor the dominator tree with type-erased base classes that can be used
by generic algorithms
- https://reviews.llvm.org/D92925: Introduce an SsaContext context class
concept for static polymorphism
- https://reviews.llvm.org/D92926: Introduce an ISsaContext “global”
interface class for dynamic polymorphism built on top of SsaContext and
opaque handles
- https://reviews.llvm.org/D83094: A new analysis (cycle info) written
generically as non-template code using opaque handles, ISsaContext, and
analysis-specific dynamic polymorphism via the ICycleInfoSsaContext
interface added in the patch

I would like us to get to general agreement on this thread that this is a
direction we want to go in and that we can proceed with the proposed code
changes.

Thanks,
Nicolai
-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201217/90daf3d3/attachment.html>

Hi Nicolai,

I’m quite sympathetic with the idea of abstracting away details of IRs and
having a single implementation of analysis and optimizations over these
abstractions. IMHO, that’s the main feature missing in MLIR.
That said, the analyses you consider in the document seem a bit limited. The
first two, at least, related with dominators are just a few lines of codes.
Which makes me wonder if the trouble, extra complexity, etc, of going this
generic way is worth it. Isn’t it simple to just duplicate them in MLIR?

I would be very supportive of a generic alias analysis, for example. That’s a
serious amount of work and potentially complicated algorithms that could be
reused across LLVM and various MLIR dialects. Plus LLVM could use a new alias
analysis algorithm. But that requires going a bit further than your proposal.
One needs an abstraction that can cover several IRs and provide enough
information to the AA algorithm in an efficient way. Also, it likely needs to
know about undefined behavior. But MLIR has been avoiding that issue for now,
AFAICT. So anything on that front would likely be wrong, as there hasn’t been
much thought about UB in MLIR. (AFAIK; I don’t follow MLIR closely)
MLIR’s ODS doesn’t seem sufficient either, as it only allows (at least now) to
attach shallow semantics attributes to instructions, similar to LLVM ones. Maybe
that could be extended somehow?

TL;DR: While I’d love to see LLVM/MLIR go into the direction you are proposing,
I’m not sure the set of considered analyses is sufficiently complicated to award
the investment in complicated infrastructure.

Nuno

______________________________________________________
From: Nicolai Hähnle
Sent: 17 December 2020 19:17
To: llvm-dev
Subject: [llvm-dev] [RFC] Abstracting over SSA form IRs to implement generic
analyses

Hi LLVM community,

Earlier this year I first proposed a new way of writing analyses that can be
applied to multiple IRs, for example, applying the same analysis to both LLVM IR
and MachineIR.

LLVM already has some analyses like that; for example, dominator tree
construction and loop info. However, they're all limited to looking at the
control flow graph: basic blocks and lists of predecessors and successors. We
want to push the envelope with a divergence analysis that is also aware of
instructions and values, and ran into severe limitations in what we could do
with the techniques that are commonly used in LLVM today. Some limitations are
around which concepts are exposed generically at all, though the bulk of
limitations revolves around readability and maintainability of the resulting
generic code.

After more evolution of the ideas and many discussions over the last few months,
I want to raise this proposal once more -- this time with an extensive document:
https://docs.google.com/document/d/1sbeGw5uNGFV0ZPVk6h8Q5_dRhk4qFnKHa-uZ-O3c4UY/edit?usp=sharing

Feel free to comment on the document, though high-level discussion is probably
best kept in this email thread.

The concrete proposal is to enable 4 tools for use by generic analyses:

- type erasure
- an SsaContext context class concept with a fairly small surface area
- dynamic polymorphism via per-analysis adapters
- dynamic polymorphism via an LLVM-wide adapter of SsaContext

The document goes to some length to explain what precisely is meant by each of
those bullets, including code examples, as well as describing a few other
options that we _don't_ propose, based on their relative merits.

There are concrete patches that go along with the proposal and you can refer to
for additional context. In logical sequence, they are:
- https://reviews.llvm.org/D92924: Introduce opaque handles for type erasure
- https://reviews.llvm.org/D83089: Based on the handle infrastructure, refactor
the dominator tree with type-erased base classes that can be used by generic
algorithms
- https://reviews.llvm.org/D92925: Introduce an SsaContext context class concept
for static polymorphism
- https://reviews.llvm.org/D92926: Introduce an ISsaContext “global” interface
class for dynamic polymorphism built on top of SsaContext and opaque handles
- https://reviews.llvm.org/D83094: A new analysis (cycle info) written
generically as non-template code using opaque handles, ISsaContext, and
analysis-specific dynamic polymorphism via the ICycleInfoSsaContext interface
added in the patch

I would like us to get to general agreement on this thread that this is a
direction we want to go in and that we can proceed with the proposed code
changes.

Thanks,
Nicolai

Thanks for sending this out!

+Mehdi - if you have a chance to look, I'd appreciate your thoughts on
this, partly as a general LLVM contributor, but also with an eye to
abstractions over multiple IRs given your work on MLIR
+Lang - you mentioned maybe some colleagues of yours might be able to take
a look at the design here?

I'd like to try writing up maybe alternatives to a couple of the patches in
the series to see how they compare, but haven't done that as yet.

My brief take is that I think the opaque handles make a fair bit of
sense/seem high-value/low-cost (if it turned out the handle for one of
these IR types needed to become a bit heavier, I don't think it'd be
super
difficult to revisit this code - make the generic handle large enough to
accommodate whatever the largest concrete handle happens to be, etc).
Though I'm still a bit less certain about the full runtime polymorphic
abstractions.

On Thu, Dec 17, 2020 at 11:17 AM Nicolai Hähnle via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi LLVM community,
>
> Earlier this year I first proposed a new way of writing analyses that can
> be applied to multiple IRs, for example, applying the same analysis to both
> LLVM IR and MachineIR.
>
> LLVM already has some analyses like that; for example, dominator tree
> construction and loop info. However, they're all limited to looking at
the
> control flow graph: basic blocks and lists of predecessors and successors.
> We want to push the envelope with a divergence analysis that is also aware
> of instructions and values, and ran into severe limitations in what we
> could do with the techniques that are commonly used in LLVM today. Some
> limitations are around which concepts are exposed generically at all,
> though the bulk of limitations revolves around readability and
> maintainability of the resulting generic code.
>
> After more evolution of the ideas and many discussions over the last few
> months, I want to raise this proposal once more -- this time with an
> extensive document:
>
https://docs.google.com/document/d/1sbeGw5uNGFV0ZPVk6h8Q5_dRhk4qFnKHa-uZ-O3c4UY/edit?usp=sharing
>
> Feel free to comment on the document, though high-level discussion is
> probably best kept in this email thread.
>
> The concrete proposal is to enable 4 tools for use by generic analyses:
>
> - type erasure
> - an SsaContext context class concept with a fairly small surface area
> - dynamic polymorphism via per-analysis adapters
> - dynamic polymorphism via an LLVM-wide adapter of SsaContext
>
> The document goes to some length to explain what precisely is meant by
> each of those bullets, including code examples, as well as describing a few
> other options that we _don't_ propose, based on their relative merits.
>
> There are concrete patches that go along with the proposal and you can
> refer to for additional context. In logical sequence, they are:
> - https://reviews.llvm.org/D92924: Introduce opaque handles for type
> erasure
> - https://reviews.llvm.org/D83089: Based on the handle infrastructure,
> refactor the dominator tree with type-erased base classes that can be used
> by generic algorithms
> - https://reviews.llvm.org/D92925: Introduce an SsaContext context class
> concept for static polymorphism
> - https://reviews.llvm.org/D92926: Introduce an ISsaContext “global”
> interface class for dynamic polymorphism built on top of SsaContext and
> opaque handles
> - https://reviews.llvm.org/D83094: A new analysis (cycle info) written
> generically as non-template code using opaque handles, ISsaContext, and
> analysis-specific dynamic polymorphism via the ICycleInfoSsaContext
> interface added in the patch
>
> I would like us to get to general agreement on this thread that this is a
> direction we want to go in and that we can proceed with the proposed code
> changes.
>
> Thanks,
> Nicolai
> --
> 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/20210201/b260caa5/attachment.html>