[llvm-dev] RFC: Introducing CfgTraits and type-erased CfgInterface / CfgBlockRef / CfgValueRef

Thu Jul 9 11:23:09 PDT 2020

Hi,

The overall idea to provide a cleaner and unified infrastructure is great.
The only caveat already mentioned is keeping an eye on the impact on
compile-time.

Just to reiterate what Kuba said, I think what D77341
<https://reviews.llvm.org/D77341> is looking to cleanup is somewhat
orthogonal to this RFC. There are aspects that we played with there that
may help, in particular potential solutions for avoiding the added
compile-time. Vice-versa, it's possible CfgTraits could be used in
GraphDiff  - I don't have a good picture here yet.
So while the end goals are different, it seems like the scopes of the work
can benefit each other :-).

Deep-diving into some of the compile-time regression: I did an analysis on
where the added time was spent with the changes in D77341, and the main
cause is merging the runtime check for a nullptr BUI into a single path
that doesn't add new children, but still added a concat iterator. This is
the context in which we're considering having GraphDiff return a
type-erased iterator.
An option discussed was through virtual calls due to the runtime nullptr
check, to avoid concating the empty iterator; another option was
re-designing GraphTraits to provide storage and *not* return a
light-weight/copyable range. Another option Dave looked into is improving
the concat_iterator for the common case of having 1-2 iterators
concatenated. We also looked into re-nesting iterators (the wrapped
iterator with the concat/filter iterators) and found incompatibilities with
existing by-value iterator implementations.
It looks like the compile-time issue is not as straight-forward for the DT
full-cleanup, but we're actively looking into it.

Alina

On Wed, Jul 8, 2020 at 1:04 PM Jakub (Kuba) Kuderski via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Interesting! I'm not sure what those polymorphic iterators would look like.
>
>
> I don't have anything concrete yet, but I thought of creating type-erased
> range and iterator types over base types, i.e., the types you get by
> dereferencing iterators with operator*. This way you (1) don't have to
> worry about begin and end returning different types and (2) can implement
> different graph traversal logics without having to introduce funny tag
> types. IIRC the main observation Alina made was that iterators derived from
> ranges cannot outlive these range objects, so generic ranges would have to
> provide storage for concrete range objects and generic iterators would have
> to carry references to their parent ranges. Here, the motivation is purely
> to work around the current template madness in GraphDiff and the updaters,
> but it's unclear to me what the performance impact of the virtual calls and
> small/dynamic storage would be.
>
> Next, we could implement range adapters (like concat, filter, etc.) to
> eagerly materialize or cache underlying rangest storing them in some
> user-provided external storage. For example, for some data structures
> (e.g., IntervalMap) it may be costly to just advance iterators and we may
> save some time by caching the underlying references until the underlying
> data gets modified.
>
> All of this is just a bunch of ideas as of today, and I'd consider it
> completely orthogonal to this RFC.
>
> Jakub
>
> On Tue, Jul 7, 2020 at 9:01 AM Nicolai Hähnle <nhaehnle at gmail.com> wrote:
>
>> 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.
>>
>
>
> --
> Jakub Kuderski
> _______________________________________________
> 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/20200709/3b0d9816/attachment.html>