llvm dev - Jul 2020 - RFC: Introducing CfgTraits and type-erased CfgInterface / CfgBlockRef / CfgValueRef

Hi all,

This is a request for comment on a series of patches which introduce a 
new way of writing algorithms that are generic over different types of CFG.


What is this?
============This series of patches introduces a set of classes and templates
for:

1. Working on basic blocks and values generically, in particular with 
the same algorithm implementation on both LLVM IR and MachineIR (in SSA 
form), and

2. Doing so using type erasure, i.e. the bulk of the algorithm you're 
writing doesn't have to be a template (at the cost of using some virtual 
methods).

The second point is achieved by

a) having algorithms refer to blocks and values using CfgBlockRef and 
CfgValueRef types which wrap a `void *` whose interpretation depends on 
the concrete CFG (for example, CfgValueRef wraps a `Value *` for LLVM IR 
but a `Register` for MachineIR), and

b) querying the CFG via virtual methods in a CfgInterface interface class.

Please take a look at the following Phabricator reviews and related 
changes you can navigate to via the "Stack" tab:

1. https://reviews.llvm.org/D83088: Introduces the classes and templates 
that enable this new way of writing analyses (CfgTraits, CfgInterface, 
CfgInterfaceImpl<CfgTraitsT>, ...).

2. https://reviews.llvm.org/D83089: Refactors the dominator tree 
implementation so that algorithms that operate on CfgBlockRef will be 
able to use a standard dominator tree as input. The calculation of 
dominator trees remains unchanged as a template.

3. https://reviews.llvm.org/D83094: Adds a GenericCycleInfo analysis as 
a first "full" user of the CfgInterface machinery. Unlike LoopInfo,
this
analysis computes a nesting of both reducible and irreducible loops 
(based on Havlak (1997)).


Why now?
=======The concrete need that prompted this development is a reworking of the 
control flow lowering in the AMDGPU backend. Part of this rework is a 
new divergence/uniformity analysis that can be used on both LLVM IR and 
MachineIR. This analysis has to be able to operate generically on both 
basic blocks and values.

If you're interested in this larger context, feel free to take a look 
here: https://github.com/nhaehnle/llvm-project/tree/controlflow-wip-v4. 
There are still some missing bits and pieces and more cleanup to be done 
for the parts which are not yet on Phabricator. I am going to tackle 
those over the next weeks.


Templates vs. interfaces
=======================At a high level, there are two parts to the proposed
framework:

- CfgTraits, which provide generic operations on concrete CFG types. For 
example, CfgTraits allow iterating over all values defined in a block. 
The implementations of CfgTraits are typically used as template parameters.

- CfgInterface, which provides generic operations on opaque, type-erased 
objects of type CfgBlockRef and CfgValueRef.

It is this second part which enables generic algorithms to be written 
using virtual method-based interfaces instead of as templates.

Both approaches for writing generic algorithms have their advantages and 
disadvantages. Templates don't have the (direct and indirect) runtime 
overhead of virtual methods. Code that uses abstract interfaces is 
easier to maintain and causes less binary bloat. It is not always clear 
what the right trade-off is.

Existing generic analyses are all written as templates. It's not clear 
to me how conscious that choice was, or whether the alternatives were 
ever fully explored, but in any case I am not proposing to change the 
already chosen trade-off there. Instead, I am proposing that we make the 
alternative _possible_, and I have a whole set of analyses that are 
implemented using this alternative waiting to be upstreamed.


What about MLIR / other CFGs?
============================While I personally only work in LLVM IR and
MachineIR and my changes
only provide the minimum required to ensure that dominator trees 
continue to work for everything else, the framework is designed with 
other CFGs in mind. In particular, since `mlir::Value` is pointer-sized, 
it shouldn't be too much effort to allow it to be wrapped in a 
CfgValueRef as well. This would enable analyses written on CfgTraits / 
CfgInterface (such as my upcoming divergence/uniformity analysis) to be 
used from MLIR as well.

Cheers,
Nicolai

-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.

Hi Nicolai,

Thanks for sharing the proposal and the patches. I looked at most of them
and think this is a good general direction.

There's a lot of heavily templated code in generic DomTee
construction/updater, MemSSA updater, and GraphDiff that has become really
hard to modify. For the context, Alina (cc'd) was recently looking into
making the domtree code work with 'CFG views'; the basic idea is to take
a
concrete CFG and a series of updates and create a view over this CFG, as if
the updates were applied, add more updates and repeat [1]. The initial
attempt was based on GraphDiff and GraphTraits over GraphDiff, but this
gets prohibitively verbose very quickly and caused difficult to fix
compilation time regressions related to nested fancy iterator types
(something like concat<filter<pair<vector<>::iterator,
T*>>, ...>) [2]. We
got to the idea of trying  polymorphic iterators, which I think is kind of
similar to this RFC, except that your proposal does type erasure at the
bottom, while polymorphic iterators from the top. Alina should know this
problem space best.

I think that generic DomTree construction/updater could be rewritten to
work on CfgTraits directly, while GraphDiff would provide CfgTraits
directly usable by the updaters. Same with the generic IDF calculator. The
biggest question for me here is how all of that would affect compilation
times. What are your thoughts on more refactoring like this? How do you
plan to evaluate compilation times impact of your changes?

Thanks,
Jakub

[1]
https://github.com/llvm/llvm-project/commit/a90374988e4eb8c50d91e11f4e61cdbd5debb235
[2]
http://llvm-compile-time-tracker.com/compare.php?from=37bcf2df01cfa47e4509a5d225a23e2ca95005e6&to=a90374988e4eb8c50d91e11f4e61cdbd5debb235&stat=instructions



On Thu, Jul 2, 2020 at 6:46 PM Nicolai Hähnle via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> This is a request for comment on a series of patches which introduce a
> new way of writing algorithms that are generic over different types of CFG.
>
>
> What is this?
> ============> This series of patches introduces a set of classes and
templates for:
>
> 1. Working on basic blocks and values generically, in particular with
> the same algorithm implementation on both LLVM IR and MachineIR (in SSA
> form), and
>
> 2. Doing so using type erasure, i.e. the bulk of the algorithm you're
> writing doesn't have to be a template (at the cost of using some
virtual
> methods).
>
> The second point is achieved by
>
> a) having algorithms refer to blocks and values using CfgBlockRef and
> CfgValueRef types which wrap a `void *` whose interpretation depends on
> the concrete CFG (for example, CfgValueRef wraps a `Value *` for LLVM IR
> but a `Register` for MachineIR), and
>
> b) querying the CFG via virtual methods in a CfgInterface interface class.
>
> Please take a look at the following Phabricator reviews and related
> changes you can navigate to via the "Stack" tab:
>
> 1. https://reviews.llvm.org/D83088: Introduces the classes and templates
> that enable this new way of writing analyses (CfgTraits, CfgInterface,
> CfgInterfaceImpl<CfgTraitsT>, ...).
>
> 2. https://reviews.llvm.org/D83089: Refactors the dominator tree
> implementation so that algorithms that operate on CfgBlockRef will be
> able to use a standard dominator tree as input. The calculation of
> dominator trees remains unchanged as a template.
>
> 3. https://reviews.llvm.org/D83094: Adds a GenericCycleInfo analysis as
> a first "full" user of the CfgInterface machinery. Unlike
LoopInfo, this
> analysis computes a nesting of both reducible and irreducible loops
> (based on Havlak (1997)).
>
>
> Why now?
> =======> The concrete need that prompted this development is a reworking
of the
> control flow lowering in the AMDGPU backend. Part of this rework is a
> new divergence/uniformity analysis that can be used on both LLVM IR and
> MachineIR. This analysis has to be able to operate generically on both
> basic blocks and values.
>
> If you're interested in this larger context, feel free to take a look
> here: https://github.com/nhaehnle/llvm-project/tree/controlflow-wip-v4.
> There are still some missing bits and pieces and more cleanup to be done
> for the parts which are not yet on Phabricator. I am going to tackle
> those over the next weeks.
>
>
> Templates vs. interfaces
> =======================> At a high level, there are two parts to the
proposed framework:
>
> - CfgTraits, which provide generic operations on concrete CFG types. For
> example, CfgTraits allow iterating over all values defined in a block.
> The implementations of CfgTraits are typically used as template parameters.
>
> - CfgInterface, which provides generic operations on opaque, type-erased
> objects of type CfgBlockRef and CfgValueRef.
>
> It is this second part which enables generic algorithms to be written
> using virtual method-based interfaces instead of as templates.
>
> Both approaches for writing generic algorithms have their advantages and
> disadvantages. Templates don't have the (direct and indirect) runtime
> overhead of virtual methods. Code that uses abstract interfaces is
> easier to maintain and causes less binary bloat. It is not always clear
> what the right trade-off is.
>
> Existing generic analyses are all written as templates. It's not clear
> to me how conscious that choice was, or whether the alternatives were
> ever fully explored, but in any case I am not proposing to change the
> already chosen trade-off there. Instead, I am proposing that we make the
> alternative _possible_, and I have a whole set of analyses that are
> implemented using this alternative waiting to be upstreamed.
>
>
> What about MLIR / other CFGs?
> ============================> While I personally only work in LLVM IR
and MachineIR and my changes
> only provide the minimum required to ensure that dominator trees
> continue to work for everything else, the framework is designed with
> other CFGs in mind. In particular, since `mlir::Value` is pointer-sized,
> it shouldn't be too much effort to allow it to be wrapped in a
> CfgValueRef as well. This would enable analyses written on CfgTraits /
> CfgInterface (such as my upcoming divergence/uniformity analysis) to be
> used from MLIR as well.
>
> Cheers,
> 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
>

-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200707/9cdb0126/attachment.html>

Hi Jakub,

On Tue, Jul 7, 2020 at 6:25 AM Jakub (Kuba) Kuderski
<kubakuderski at gmail.com> wrote:
> There's a lot of heavily templated code in generic DomTee
construction/updater, MemSSA updater, and GraphDiff that has become really hard
to modify. For the context, Alina (cc'd) was recently looking into making
the domtree code work with 'CFG views'; the basic idea is to take a
concrete CFG and a series of updates and create a view over this CFG, as if the
updates were applied, add more updates and repeat [1]. The initial attempt was
based on GraphDiff and GraphTraits over GraphDiff, but this gets prohibitively
verbose very quickly and caused difficult to fix compilation time regressions
related to nested fancy iterator types (something like
concat<filter<pair<vector<>::iterator, T*>>, ...>) [2].
We got to the idea of trying  polymorphic iterators, which I think is kind of
similar to this RFC, except that your proposal does type erasure at the bottom,
while polymorphic iterators from the top. Alina should know this problem space
best.
Interesting! I'm not sure what those polymorphic iterators would look like.

> I think that generic DomTree construction/updater could be rewritten to
work on CfgTraits directly, while GraphDiff would provide CfgTraits directly
usable by the updaters. Same with the generic IDF calculator. The biggest
question for me here is how all of that would affect compilation times. What are
your thoughts on more refactoring like this? How do you plan to evaluate
compilation times impact of your changes?
Yes, that would be possible. And the compile time question is a big
reason why I didn't touch DomTree construction, but it's probably
worth the experiment. The main issue is iteration of predecessors /
successors.

Is it possible to run the llvm-compile-time-tracker tests on a branch
somewhere? That would be the most convenient approach as far as I'm
concerned.

Cheers,
Nicolai


>
> Thanks,
> Jakub
>
> [1]
https://github.com/llvm/llvm-project/commit/a90374988e4eb8c50d91e11f4e61cdbd5debb235
> [2]
http://llvm-compile-time-tracker.com/compare.php?from=37bcf2df01cfa47e4509a5d225a23e2ca95005e6&to=a90374988e4eb8c50d91e11f4e61cdbd5debb235&stat=instructions
>
>
>
> On Thu, Jul 2, 2020 at 6:46 PM Nicolai Hähnle via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>>
>> Hi all,
>>
>> This is a request for comment on a series of patches which introduce a
>> new way of writing algorithms that are generic over different types of
CFG.
>>
>>
>> What is this?
>> ============>> This series of patches introduces a set of classes
and templates for:
>>
>> 1. Working on basic blocks and values generically, in particular with
>> the same algorithm implementation on both LLVM IR and MachineIR (in SSA
>> form), and
>>
>> 2. Doing so using type erasure, i.e. the bulk of the algorithm
you're
>> writing doesn't have to be a template (at the cost of using some
virtual
>> methods).
>>
>> The second point is achieved by
>>
>> a) having algorithms refer to blocks and values using CfgBlockRef and
>> CfgValueRef types which wrap a `void *` whose interpretation depends on
>> the concrete CFG (for example, CfgValueRef wraps a `Value *` for LLVM
IR
>> but a `Register` for MachineIR), and
>>
>> b) querying the CFG via virtual methods in a CfgInterface interface
class.
>>
>> Please take a look at the following Phabricator reviews and related
>> changes you can navigate to via the "Stack" tab:
>>
>> 1. https://reviews.llvm.org/D83088: Introduces the classes and
templates
>> that enable this new way of writing analyses (CfgTraits, CfgInterface,
>> CfgInterfaceImpl<CfgTraitsT>, ...).
>>
>> 2. https://reviews.llvm.org/D83089: Refactors the dominator tree
>> implementation so that algorithms that operate on CfgBlockRef will be
>> able to use a standard dominator tree as input. The calculation of
>> dominator trees remains unchanged as a template.
>>
>> 3. https://reviews.llvm.org/D83094: Adds a GenericCycleInfo analysis as
>> a first "full" user of the CfgInterface machinery. Unlike
LoopInfo, this
>> analysis computes a nesting of both reducible and irreducible loops
>> (based on Havlak (1997)).
>>
>>
>> Why now?
>> =======>> The concrete need that prompted this development is a
reworking of the
>> control flow lowering in the AMDGPU backend. Part of this rework is a
>> new divergence/uniformity analysis that can be used on both LLVM IR and
>> MachineIR. This analysis has to be able to operate generically on both
>> basic blocks and values.
>>
>> If you're interested in this larger context, feel free to take a
look
>> here: https://github.com/nhaehnle/llvm-project/tree/controlflow-wip-v4.
>> There are still some missing bits and pieces and more cleanup to be
done
>> for the parts which are not yet on Phabricator. I am going to tackle
>> those over the next weeks.
>>
>>
>> Templates vs. interfaces
>> =======================>> At a high level, there are two parts to
the proposed framework:
>>
>> - CfgTraits, which provide generic operations on concrete CFG types.
For
>> example, CfgTraits allow iterating over all values defined in a block.
>> The implementations of CfgTraits are typically used as template
parameters.
>>
>> - CfgInterface, which provides generic operations on opaque,
type-erased
>> objects of type CfgBlockRef and CfgValueRef.
>>
>> It is this second part which enables generic algorithms to be written
>> using virtual method-based interfaces instead of as templates.
>>
>> Both approaches for writing generic algorithms have their advantages
and
>> disadvantages. Templates don't have the (direct and indirect)
runtime
>> overhead of virtual methods. Code that uses abstract interfaces is
>> easier to maintain and causes less binary bloat. It is not always clear
>> what the right trade-off is.
>>
>> Existing generic analyses are all written as templates. It's not
clear
>> to me how conscious that choice was, or whether the alternatives were
>> ever fully explored, but in any case I am not proposing to change the
>> already chosen trade-off there. Instead, I am proposing that we make
the
>> alternative _possible_, and I have a whole set of analyses that are
>> implemented using this alternative waiting to be upstreamed.
>>
>>
>> What about MLIR / other CFGs?
>> ============================>> While I personally only work in
LLVM IR and MachineIR and my changes
>> only provide the minimum required to ensure that dominator trees
>> continue to work for everything else, the framework is designed with
>> other CFGs in mind. In particular, since `mlir::Value` is
pointer-sized,
>> it shouldn't be too much effort to allow it to be wrapped in a
>> CfgValueRef as well. This would enable analyses written on CfgTraits /
>> CfgInterface (such as my upcoming divergence/uniformity analysis) to be
>> used from MLIR as well.
>>
>> Cheers,
>> 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
>
>
>
> --
> Jakub Kuderski


-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.