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

[Nicolai Hähnle via llvm-dev]

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>