[llvm-dev] [RFC] Propeller: A frame work for Post Link Optimizations

Teresa Johnson via llvm-dev llvm-dev at lists.llvm.org
Mon Sep 30 15:10:25 PDT 2019 

On Mon, Sep 30, 2019 at 3:07 PM James Y Knight <jyknight at google.com> wrote:

> One could imagine using MIR as an "object-file" format from the compiler
> to the linker -- and then within the linker, doing block layout on the MIR
> and lowering to actual instructions.
>

Sure, but this moves some of the currently parallel compilation (in ThinLTO
at least) into a monolithic phase (the linker), which is what Propeller is
trying to avoid to achieve scalability. Teresa


>
> I don't know that I'd say that's simpler than what you've described,
> however.
>

> On Mon, Sep 30, 2019 at 4:50 PM Xinliang David Li via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> I guess Eric means full program optimization/cross module optimization
>> using MIR.   This is in theory workable in full LTO style, but not in
>> ThinLTO style which works on summary data.  As we have discussed,
>> eliminating monolithic style optimization is the key design goal.
>>
>> This was also briefly discussed in one of the previous replies I sent.
>> There are other benefits of doing this in linker such as handling prebuilt
>> libraries such as libc.
>>
>> David
>>
>>
>> On Mon, Sep 30, 2019 at 1:39 PM Teresa Johnson <tejohnson at google.com>
>> wrote:
>>
>>>
>>>
>>> On Mon, Sep 30, 2019 at 1:34 PM Sriraman Tallam <tmsriram at google.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Mon, Sep 30, 2019 at 1:27 PM Eric Christopher <echristo at gmail.com>
>>>> wrote:
>>>>
>>>>> On Mon, Sep 30, 2019 at 12:31 PM Sriraman Tallam <tmsriram at google.com>
>>>>> wrote:
>>>>> >
>>>>> >
>>>>> >
>>>>> > On Mon, Sep 30, 2019 at 12:26 PM Eric Christopher <
>>>>> echristo at gmail.com> wrote:
>>>>> >>
>>>>> >> On Sat, Sep 28, 2019 at 8:25 AM Sriraman Tallam <
>>>>> tmsriram at google.com> wrote:
>>>>> >> >
>>>>> >> >
>>>>> >> >
>>>>> >> > On Fri, Sep 27, 2019 at 10:36 PM Eric Christopher <
>>>>> echristo at gmail.com> wrote:
>>>>> >> >>
>>>>> >> >> On Fri, Sep 27, 2019 at 2:08 PM Sriraman Tallam via llvm-dev
>>>>> >> >> <llvm-dev at lists.llvm.org> wrote:
>>>>> >> >> >
>>>>> >> >> > On Fri, Sep 27, 2019 at 1:16 PM Eli Friedman <
>>>>> efriedma at quicinc.com> wrote:
>>>>> >> >> > >
>>>>> >> >> > > > -----Original Message-----
>>>>> >> >> > > > From: Sriraman Tallam <tmsriram at google.com>
>>>>> >> >> > > > Sent: Friday, September 27, 2019 9:43 AM
>>>>> >> >> > > > To: Eli Friedman <efriedma at quicinc.com>
>>>>> >> >> > > > Cc: Xinliang David Li <xinliangli at gmail.com>; llvm-dev <
>>>>> llvm-dev at lists.llvm.org>
>>>>> >> >> > > > Subject: [EXT] Re: [llvm-dev] [RFC] Propeller: A frame
>>>>> work for Post Link
>>>>> >> >> > > > Optimizations
>>>>> >> >> > > >
>>>>> >> >> > > > >
>>>>> >> >> > > > > > > Why are you proposing to add a bunch of options to
>>>>> clang to manipulate
>>>>> >> >> > > > LLVM
>>>>> >> >> > > > > > code generation, given none of those options are
>>>>> actually used for Propeller
>>>>> >> >> > > > > > workflows?
>>>>> >> >> > > > > >
>>>>> >> >> > > > > > Where do you suggest labelling and section options
>>>>> should exist?  We
>>>>> >> >> > > > > > looked at  basic block sections to be similar to
>>>>> function sections in
>>>>> >> >> > > > > > terms of option handling?
>>>>> >> >> > > > >
>>>>> >> >> > > > > Generating bitcode with/without propeller doesn't
>>>>> actually affect the
>>>>> >> >> > > > generated bitcode, right?  So you could say that Propeller
>>>>> is enabled with "-Wl,--
>>>>> >> >> > > > enable-propeller", and not change clang at all.  I'm not a
>>>>> fan of adding options
>>>>> >> >> > > > just because we can.  If basic block sections are only
>>>>> used as a sort of secret
>>>>> >> >> > > > handshake between the propeller compiler and the propeller
>>>>> linker, we can
>>>>> >> >> > > > change that interface later, if we want; if we expose it
>>>>> as a clang option, we're
>>>>> >> >> > > > committing to making basic block sections continue to work
>>>>> the same way until
>>>>> >> >> > > > the end of time.
>>>>> >> >> > > >
>>>>> >> >> > > > The generated MIR code is slightly different as the later
>>>>> passes have
>>>>> >> >> > > > more CFI instructions, basic block labels and extra direct
>>>>> jumps which
>>>>> >> >> > > > would have been fall throughs otherwise.  So, some llvm
>>>>> option is
>>>>> >> >> > > > needed.
>>>>> >> >> > >
>>>>> >> >> > > At link (LTO codegen) time, yes.  But clang's bitcode
>>>>> generation doesn't change; only LTO code generation in lld changes.
>>>>> >> >> >
>>>>> >> >> > I see what you mean here.
>>>>> >> >> >
>>>>> >> >> > >
>>>>> >> >> > > > I envisioned that basic block sections could also be
>>>>> useful on its own
>>>>> >> >> > > > outside of propeller.   Hence, we made it like
>>>>> function-sections with
>>>>> >> >> > > > a separate option -fbasicblock-sections.  The propeller
>>>>> option is an
>>>>> >> >> > > > umbrella option to make it easy to invoke Propeller.
>>>>> >> >> > >
>>>>> >> >> > > I don't think this is really true.  Basic block labels means
>>>>> "insert labels that are useful for propeller profiling", and basic block
>>>>> sections means "split the function into multiple chunks that are convenient
>>>>> for propeller optimization".  So it's really only useful for propeller-like
>>>>> workflows.  And I'd be concerned that future changes to propeller could
>>>>> affect the behavior of these options in the future, if the behavior isn't
>>>>> specified in some rigorous way.
>>>>> >> >> >
>>>>> >> >> > The idea of basic block sections was seeded by Rui Ueyama.
>>>>> When basic
>>>>> >> >> > block sections was originally looked at, Propeller was not
>>>>> designed.
>>>>> >> >> > We looked at basic block sections as finer granularity than
>>>>> function
>>>>> >> >> > sections.  Section prefix based code layout where you just
>>>>> create
>>>>> >> >> > smaller code sections and let the linker do what it does today
>>>>> would
>>>>> >> >> > have much better results with basic block sections.  Symbol
>>>>> ordering
>>>>> >> >> > file with basic block sections to do random orderings can be
>>>>> done
>>>>> >> >> > without invoking Propeller.  Function sections has found uses
>>>>> after it
>>>>> >> >> > was invented like Identical Code Folding.
>>>>> >> >> >
>>>>> >> >>
>>>>> >> >> I'm not sure that function sections are entirely an apt
>>>>> comparison
>>>>> >> >> here for a few reasons:
>>>>> >> >>
>>>>> >> >>  - function sections mostly gave an easy way to do ICF - using
>>>>> MIR or
>>>>> >> >> LLVM IR are also fairly effective means as is just using the
>>>>> linker to
>>>>> >> >
>>>>> >> >
>>>>> >> > I did not mean to suggest we should do folding with basic block
>>>>> sections and I am aware of the issues, though I am not ruling out the
>>>>> possibility.  We had briefly brainstormed this.
>>>>> >> >
>>>>> >> > AFAICT, Function Sections was not invented to do ICF.  Function
>>>>> sections was used for linker garbage collection and global code layout and
>>>>> when we first worked on ICF for gold much later, we found function sections
>>>>> to be useful without which it would have been much  harder.
>>>>> >> >
>>>>> >>
>>>>> >> They're both in the same arena.
>>>>> >>
>>>>> >> >
>>>>> >> >>
>>>>> >> >> compare bytes. Using function sections can still run into
>>>>> language
>>>>> >> >> specific problems as well, hence why icf=safe vs icf=all. Though
>>>>> pcc's
>>>>> >> >
>>>>> >> >
>>>>> >> > Agreed, and I would like to humbly suggest that I added those
>>>>> options to gold originally and am aware of that.
>>>>> >>
>>>>> >> Of course, but context is helpful for discussion and for others in
>>>>> the
>>>>> >> future understanding the discussion.
>>>>> >>
>>>>> >> >
>>>>> >> >>
>>>>> >> >> recent work helps out a little bit via significant address
>>>>> >> >> determination in the front end
>>>>> >> >>  - order files and other similar mechanisms work based on
>>>>> externally
>>>>> >> >> visible symbols and are fairly straightforward to use in an ABI
>>>>> safe
>>>>> >> >> way (no function -> function fallthrough for example)
>>>>> >> >>  - basic block sections can run into the multiple entry point
>>>>> problems
>>>>> >> >> depending on how they're laid out as well as other ABI and
>>>>> visibility
>>>>> >> >> issues
>>>>> >> >>
>>>>> >> >>
>>>>> >> >> This can likely be done safely, but there are definitely some
>>>>> concerns
>>>>> >> >> here with how you want to enable the use of basic block
>>>>> >> >> labels/sections.
>>>>> >> >
>>>>> >> >
>>>>> >> > I would like to expose basic block sections independently and let
>>>>> me talk more about one more effort we are trying to do.  Independent of
>>>>> Propeller, we are looking at a machine learning based approach to do code
>>>>> layout at link time.  I won't go into the details of the features but
>>>>> having basic block sections allows us to naturally feed the native object
>>>>> files into a black box that would try several different reorderings of the
>>>>> sections and learn a model.  We looked at basic block sections as the
>>>>> building block on top of which Propeller was built.  I don't think it would
>>>>> be the only application, just my opinion.
>>>>> >> >
>>>>> >>
>>>>> >> Again a question of "why at the object level rather than a low level
>>>>> >> IR" seems like something we should really explore the tradeoffs for
>>>>> at
>>>>> >> more length.
>>>>> >
>>>>> >
>>>>> > This is so that we can do inter-procedural basic block ordering.
>>>>> Doing this at link time with all the basic blocks exposes a lot more
>>>>> inter-procedural ordering opportunities.  At a low-level IR, we are still
>>>>> limited to intra-module basic block reordering.
>>>>> >
>>>>>
>>>>> Seems like you could spend just as much work and reliability on making
>>>>> MIR/late stage LTO compilation handle this for you?
>>>>>
>>>>
>>>> Full LTO yes, Thin LTO ... no.  We want this to be scalable and ThinLTO
>>>> is what we are more interested in.
>>>>
>>>
>>> As Sri said, we need to be able to use this for ThinLTO, and I'm not
>>> sure how you would do whole program BB layout in ThinLTO which does the
>>> whole program analysis much much earlier than MIR. Eric - did you have
>>> something else in mind or were you talking about Full LTO?
>>>
>>> Teresa
>>>
>>>
>>>> Thanks
>>>> Sri
>>>>
>>>>
>>>>>
>>>>> -eric
>>>>>
>>>>> > Thanks
>>>>> > Sri
>>>>> >
>>>>> >
>>>>> >>
>>>>> >>
>>>>> >> -eric
>>>>> >>
>>>>> >> > Thanks
>>>>> >> > Sri
>>>>> >> >
>>>>> >> >
>>>>> >> >
>>>>> >> >
>>>>> >> >>
>>>>> >> >>
>>>>> >> >> -eric
>>>>> >> >>
>>>>> >> >>
>>>>> >> >> > >
>>>>> >> >> > > In any case, if we're adding flags to clang other than
>>>>> "enable propeller", I think we should have a separate thread on cfe-dev to
>>>>> discuss them. We don't expose every possible LLVM optimization and code
>>>>> generation option through clang. Users have a strong expectation of
>>>>> stability for clang options, and that means we need to evaluate each new
>>>>> option carefully, to decide whether it's something we really want to
>>>>> support indefinitely.
>>>>> >> >> >
>>>>> >> >> > Understood.
>>>>> >> >> >
>>>>> >> >> > Thanks
>>>>> >> >> > Sri
>>>>> >> >> >
>>>>> >> >> > >
>>>>> >> >> > > -Eli
>>>>> >> >> > _______________________________________________
>>>>> >> >> > LLVM Developers mailing list
>>>>> >> >> > llvm-dev at lists.llvm.org
>>>>> >> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>
>>>>
>>>
>>> --
>>> Teresa Johnson |  Software Engineer |  tejohnson at google.com |
>>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>

-- 
Teresa Johnson |  Software Engineer |  tejohnson at google.com |
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190930/db93f711/attachment.html>

More information about the llvm-dev mailing list