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

Is there large value from deferring the block ordering to link time? That
is, does the block layout algorithm need to consider global layout issues
when deciding which blocks to put together and which to relegate to the
far-away part of the code?

Or, could the propellor-optimized compile step instead split each function
into only 2 pieces -- one containing an "optimally-ordered" set of hot
blocks from the function, and another containing the cold blocks? The
linker would have less flexibility in placement, but maybe it doesn't
actually need that flexibility?

Apologies if this is obvious for those who actually know what they're
talking about here. :)

On Wed, Oct 2, 2019 at 6:18 PM Rafael Auler <rafaelauler at fb.com> wrote:
> You’re correct, except that, in Propeller, CFI duplication happens for
> every basic block as it operates with the conservative assumption that a
> block can be put anywhere by the linker. That’s a significant bloat that is
> not cleaned up later. So, during link time, if N blocks from the same
> function are contiguous in the final layout, as it should happen most of
> the time for any sane BB order, we would have several FDEs for a region
> that only needs one. The bloat goes to the final binary (a lot more FDEs,
> specifically, one FDE per basic block).
>
> BOLT will only split a function in two parts, and only if it has profile.
> Most of the time, a function is not split. It also has an option not to
> split at all. For internally reordered basic blocks of a given function, it
> has CFI deduplication logic (it will interpret and build the CFI states for
> each block and rewrite the CFIs in a way that uses the minimum number of
> instructions to encode the states for each block).
>
>
>
> *From: *llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
James Y
> Knight via llvm-dev <llvm-dev at lists.llvm.org>
> *Reply-To: *James Y Knight <jyknight at google.com>
> *Date: *Wednesday, October 2, 2019 at 1:59 PM
> *To: *Maksim Panchenko <maks at fb.com>
> *Cc: *"llvm-dev at lists.llvm.org" <llvm-dev at
lists.llvm.org>
> *Subject: *Re: [llvm-dev] [RFC] Propeller: A frame work for Post Link
> Optimizations
>
>
>
> I'm a bit confused by this subthread -- doesn't BOLT have the exact
same
> CFI bloat issue? From my cursory reading of the propellor doc, the CFI
> duplication is _necessary_ to represent discontiguous functions, not
> anything particular to the way Propellor happens to generate those
> discontiguous functions.
>
>
>
> And emitting discontiguous functions is a fundamental goal of this, right?
>
>
>
> On Wed, Oct 2, 2019 at 4:25 PM Maksim Panchenko via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Thanks for clarifying. This means once you move to the next basic block
> (or any other basic
>
> block in the function) you have to execute an entirely new set of CFI
> instructions
>
> except for the common CIE part. While indeed this is not as bad, on
> average, the overall
>
> active memory footprint will increase.
>
>
>
> Creating one FDE per basic block means that .eh_frame_hdr, an allocatable
> section,
>
> will be bloated too. This will increase the FDE lookup time. I don’t see
> .eh_frame_hdr
>
> being mentioned in the proposal.
>
>
>
> Maksim
>
>
>
> On 10/2/19, 12:20 PM, "Krzysztof Pszeniczny" <kpszeniczny at
google.com>
> wrote:
>
>
>
>
>
>
>
> On Wed, Oct 2, 2019 at 8:41 PM Maksim Panchenko via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> *Pessimization/overhead for stack unwinding used by system-wide profilers
> and
> for exception handling*
>
> Larger CFI programs put an extra burden on unwinding at runtime as more CFI
> (and thus native) instructions have to be executed. This will cause more
> overhead for any profiler that records stack traces, and, as you correctly
> note
> in the proposal, for any program that heavily uses exceptions.
>
>
>
> The number of CFI instructions that have to be executed when unwinding any
> given stack stays the same. The CFI instructions for a function have to be
> duplicated in every basic block section, but when performing unwinding only
> one such a set is executed -- the copy for the current basic block.
> However, this copy contains precisely the same CFI instructions as the ones
> that would have to be executed if there were no basic block sections.
>
>
>
> --
>
> Krzysztof Pszeniczny
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
<https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kx31RNFp5lAJejEYwuEQ4Zc5A6GakBit07EY08bIAvc&m=-AXqQmc2_r5LuTxyQRxmJESWGU7DLqvYjOlvwJnas_Q&s=h1mfecKZOhD5a1QaEabyI_nHKF81KAXoYRAgR0lNPvM&e=>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191011/7054158a/attachment.html>

On Fri, Oct 11, 2019 at 10:46 AM James Y Knight via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Is there large value from deferring the block ordering to link time? That
> is, does the block layout algorithm need to consider global layout issues
> when deciding which blocks to put together and which to relegate to the
> far-away part of the code?
>
> Or, could the propellor-optimized compile step instead split each function
> into only 2 pieces -- one containing an "optimally-ordered" set
of hot
> blocks from the function, and another containing the cold blocks? The
> linker would have less flexibility in placement, but maybe it doesn't
> actually need that flexibility?
>
> Apologies if this is obvious for those who actually know what they're
> talking about here. :)
>
It is a fair question.

We believe the flexibility to do fine grained layout in whole program
context is important. PostLinkOptimization is aimed at getting as much
performance improvement as possible (usually applied on top of
ThinLTO+PGO), so the framework is designed to enable it.

In particular, it allows the linker to stitch hot bb traces from different
functions to be stitched together. It also allows hot trace duplication
across procedure boundaries (kind of interprocedural tailDup). Besides,
code alignment decisions to minimize branch mispredictions  may require
global context (e.g, too conflicting branches residing in two different
functions).  Other micro-arch specific optimizations to improve processor
front-end throughput may also require global context.

It is conceivable to have an option to control the level of granularity at
the possible cost of performance.

thanks,

David


>
> On Wed, Oct 2, 2019 at 6:18 PM Rafael Auler <rafaelauler at fb.com>
wrote:
>
>> You’re correct, except that, in Propeller, CFI duplication happens for
>> every basic block as it operates with the conservative assumption that
a
>> block can be put anywhere by the linker. That’s a significant bloat
that is
>> not cleaned up later. So, during link time, if N blocks from the same
>> function are contiguous in the final layout, as it should happen most
of
>> the time for any sane BB order, we would have several FDEs for a region
>> that only needs one. The bloat goes to the final binary (a lot more
FDEs,
>> specifically, one FDE per basic block).
>>
>> BOLT will only split a function in two parts, and only if it has
profile.
>> Most of the time, a function is not split. It also has an option not to
>> split at all. For internally reordered basic blocks of a given
function, it
>> has CFI deduplication logic (it will interpret and build the CFI states
for
>> each block and rewrite the CFIs in a way that uses the minimum number
of
>> instructions to encode the states for each block).
>>
>>
>>
>> *From: *llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf
of James Y
>> Knight via llvm-dev <llvm-dev at lists.llvm.org>
>> *Reply-To: *James Y Knight <jyknight at google.com>
>> *Date: *Wednesday, October 2, 2019 at 1:59 PM
>> *To: *Maksim Panchenko <maks at fb.com>
>> *Cc: *"llvm-dev at lists.llvm.org" <llvm-dev at
lists.llvm.org>
>> *Subject: *Re: [llvm-dev] [RFC] Propeller: A frame work for Post Link
>> Optimizations
>>
>>
>>
>> I'm a bit confused by this subthread -- doesn't BOLT have the
exact same
>> CFI bloat issue? From my cursory reading of the propellor doc, the CFI
>> duplication is _necessary_ to represent discontiguous functions, not
>> anything particular to the way Propellor happens to generate those
>> discontiguous functions.
>>
>>
>>
>> And emitting discontiguous functions is a fundamental goal of this,
right?
>>
>>
>>
>> On Wed, Oct 2, 2019 at 4:25 PM Maksim Panchenko via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> Thanks for clarifying. This means once you move to the next basic block
>> (or any other basic
>>
>> block in the function) you have to execute an entirely new set of CFI
>> instructions
>>
>> except for the common CIE part. While indeed this is not as bad, on
>> average, the overall
>>
>> active memory footprint will increase.
>>
>>
>>
>> Creating one FDE per basic block means that .eh_frame_hdr, an
allocatable
>> section,
>>
>> will be bloated too. This will increase the FDE lookup time. I don’t
see
>> .eh_frame_hdr
>>
>> being mentioned in the proposal.
>>
>>
>>
>> Maksim
>>
>>
>>
>> On 10/2/19, 12:20 PM, "Krzysztof Pszeniczny" <kpszeniczny
at google.com>
>> wrote:
>>
>>
>>
>>
>>
>>
>>
>> On Wed, Oct 2, 2019 at 8:41 PM Maksim Panchenko via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> *Pessimization/overhead for stack unwinding used by system-wide
profilers
>> and
>> for exception handling*
>>
>> Larger CFI programs put an extra burden on unwinding at runtime as more
>> CFI
>> (and thus native) instructions have to be executed. This will cause
more
>> overhead for any profiler that records stack traces, and, as you
>> correctly note
>> in the proposal, for any program that heavily uses exceptions.
>>
>>
>>
>> The number of CFI instructions that have to be executed when unwinding
>> any given stack stays the same. The CFI instructions for a function
have to
>> be duplicated in every basic block section, but when performing
unwinding
>> only one such a set is executed -- the copy for the current basic
block.
>> However, this copy contains precisely the same CFI instructions as the
ones
>> that would have to be executed if there were no basic block sections.
>>
>>
>>
>> --
>>
>> Krzysztof Pszeniczny
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
<https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kx31RNFp5lAJejEYwuEQ4Zc5A6GakBit07EY08bIAvc&m=-AXqQmc2_r5LuTxyQRxmJESWGU7DLqvYjOlvwJnas_Q&s=h1mfecKZOhD5a1QaEabyI_nHKF81KAXoYRAgR0lNPvM&e=>
>>
>> _______________________________________________
> 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/20191011/510d69dd/attachment.html>

Hello,

I wanted to consolidate all the discussions and our final thoughts on the
concerns raised.  I have attached a document consolidating it.

BOLT’s performance gains inspired this work and we believe BOLT
is a great piece of engineering.  However, there are build environments
where
scalability is critical and memory limits per process are tight :

* Debug Fission,  https://gcc.gnu.org/wiki/DebugFission was primarily
invented to achieve scalability and better incremental build times while
building large binaries with debug information.

* ThinLTO,
http://blog.llvm.org/2016/06/thinlto-scalable-and-incremental-lto.html was
primarily invented to make LLVM’s full LTO scalable and keep the memory and
time overheads low.  ThinLTO has enabled much broader adoption of whole
program optimization, by making it non-monolithic.

* For Chromium builds,
https://chromium-review.googlesource.com/c/chromium/src/+/695714/3/build/toolcha
in/concurrent_links.gni, the linker process memory is set to 10GB with
ThinLTO.
It was 26GB with Full LTO before that and individual processes will run of
out
of memory beyond that.

* Here,
https://gotocon.com/dl/goto-chicago-2016/slides/AysyluGreenberg_BuildingADistrib
utedBuildSystemAtGoogleScale.pdf, a distributed build system at Google
scale
is shown where 5 million binary and test builds are performed every day on
several thousands of machines, each  with a limitation of 12G of memory per
process and 15 minute time-out on tests. Memory overheads of 35G (clang)
are
well above these thresholds.

We have developed Propeller like ThinLTO that can be used to obtain similar
performance gains like BOLT in such environments.

Thanks
Sri


On Fri, Oct 11, 2019 at 11:25 AM Xinliang David Li via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> On Fri, Oct 11, 2019 at 10:46 AM James Y Knight via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Is there large value from deferring the block ordering to link time?
That
>> is, does the block layout algorithm need to consider global layout
issues
>> when deciding which blocks to put together and which to relegate to the
>> far-away part of the code?
>>
>> Or, could the propellor-optimized compile step instead split each
>> function into only 2 pieces -- one containing an
"optimally-ordered" set of
>> hot blocks from the function, and another containing the cold blocks?
The
>> linker would have less flexibility in placement, but maybe it
doesn't
>> actually need that flexibility?
>>
>> Apologies if this is obvious for those who actually know what
they're
>> talking about here. :)
>>
>
> It is a fair question.
>
> We believe the flexibility to do fine grained layout in whole program
> context is important. PostLinkOptimization is aimed at getting as much
> performance improvement as possible (usually applied on top of
> ThinLTO+PGO), so the framework is designed to enable it.
>
> In particular, it allows the linker to stitch hot bb traces from different
> functions to be stitched together. It also allows hot trace duplication
> across procedure boundaries (kind of interprocedural tailDup). Besides,
> code alignment decisions to minimize branch mispredictions  may require
> global context (e.g, too conflicting branches residing in two different
> functions).  Other micro-arch specific optimizations to improve processor
> front-end throughput may also require global context.
>
> It is conceivable to have an option to control the level of granularity at
> the possible cost of performance.
>
> thanks,
>
> David
>
>
>
>>
>> On Wed, Oct 2, 2019 at 6:18 PM Rafael Auler <rafaelauler at
fb.com> wrote:
>>
>>> You’re correct, except that, in Propeller, CFI duplication happens
for
>>> every basic block as it operates with the conservative assumption
that a
>>> block can be put anywhere by the linker. That’s a significant bloat
that is
>>> not cleaned up later. So, during link time, if N blocks from the
same
>>> function are contiguous in the final layout, as it should happen
most of
>>> the time for any sane BB order, we would have several FDEs for a
region
>>> that only needs one. The bloat goes to the final binary (a lot more
FDEs,
>>> specifically, one FDE per basic block).
>>>
>>> BOLT will only split a function in two parts, and only if it has
>>> profile. Most of the time, a function is not split. It also has an
option
>>> not to split at all. For internally reordered basic blocks of a
given
>>> function, it has CFI deduplication logic (it will interpret and
build the
>>> CFI states for each block and rewrite the CFIs in a way that uses
the
>>> minimum number of instructions to encode the states for each
block).
>>>
>>>
>>>
>>> *From: *llvm-dev <llvm-dev-bounces at lists.llvm.org> on
behalf of James Y
>>> Knight via llvm-dev <llvm-dev at lists.llvm.org>
>>> *Reply-To: *James Y Knight <jyknight at google.com>
>>> *Date: *Wednesday, October 2, 2019 at 1:59 PM
>>> *To: *Maksim Panchenko <maks at fb.com>
>>> *Cc: *"llvm-dev at lists.llvm.org" <llvm-dev at
lists.llvm.org>
>>> *Subject: *Re: [llvm-dev] [RFC] Propeller: A frame work for Post
Link
>>> Optimizations
>>>
>>>
>>>
>>> I'm a bit confused by this subthread -- doesn't BOLT have
the exact same
>>> CFI bloat issue? From my cursory reading of the propellor doc, the
CFI
>>> duplication is _necessary_ to represent discontiguous functions,
not
>>> anything particular to the way Propellor happens to generate those
>>> discontiguous functions.
>>>
>>>
>>>
>>> And emitting discontiguous functions is a fundamental goal of this,
>>> right?
>>>
>>>
>>>
>>> On Wed, Oct 2, 2019 at 4:25 PM Maksim Panchenko via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>> Thanks for clarifying. This means once you move to the next basic
block
>>> (or any other basic
>>>
>>> block in the function) you have to execute an entirely new set of
CFI
>>> instructions
>>>
>>> except for the common CIE part. While indeed this is not as bad, on
>>> average, the overall
>>>
>>> active memory footprint will increase.
>>>
>>>
>>>
>>> Creating one FDE per basic block means that .eh_frame_hdr, an
>>> allocatable section,
>>>
>>> will be bloated too. This will increase the FDE lookup time. I
don’t see
>>> .eh_frame_hdr
>>>
>>> being mentioned in the proposal.
>>>
>>>
>>>
>>> Maksim
>>>
>>>
>>>
>>> On 10/2/19, 12:20 PM, "Krzysztof Pszeniczny"
<kpszeniczny at google.com>
>>> wrote:
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Wed, Oct 2, 2019 at 8:41 PM Maksim Panchenko via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>> *Pessimization/overhead for stack unwinding used by system-wide
>>> profilers and
>>> for exception handling*
>>>
>>> Larger CFI programs put an extra burden on unwinding at runtime as
more
>>> CFI
>>> (and thus native) instructions have to be executed. This will cause
more
>>> overhead for any profiler that records stack traces, and, as you
>>> correctly note
>>> in the proposal, for any program that heavily uses exceptions.
>>>
>>>
>>>
>>> The number of CFI instructions that have to be executed when
unwinding
>>> any given stack stays the same. The CFI instructions for a function
have to
>>> be duplicated in every basic block section, but when performing
unwinding
>>> only one such a set is executed -- the copy for the current basic
block.
>>> However, this copy contains precisely the same CFI instructions as
the ones
>>> that would have to be executed if there were no basic block
sections.
>>>
>>>
>>>
>>> --
>>>
>>> Krzysztof Pszeniczny
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
<https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kx31RNFp5lAJejEYwuEQ4Zc5A6GakBit07EY08bIAvc&m=-AXqQmc2_r5LuTxyQRxmJESWGU7DLqvYjOlvwJnas_Q&s=h1mfecKZOhD5a1QaEabyI_nHKF81KAXoYRAgR0lNPvM&e=>
>>>
>>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
> _______________________________________________
> 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/20191014/ccb6d0c1/attachment-0001.html>
-------------- next part --------------
In summary, BOLT’s performance gains inspired this work and we believe BOLT is a
great piece of engineering.  However, there are build environments where
scalability is critical and memory limits per process are tight :

* Debug Fission,  https://gcc.gnu.org/wiki/DebugFission was primarily  invented
to achieve scalability and better incremental build times while building large
binaries with debug information.

* ThinLTO,
http://blog.llvm.org/2016/06/thinlto-scalable-and-incremental-lto.html was
primarily invented to make LLVM’s full LTO scalable and keep the memory and time
overheads low.  ThinLTO has enabled much broader adoption of whole program
optimization, by making it non-monolithic.

* For Chromium builds,
https://chromium-review.googlesource.com/c/chromium/src/+/695714/3/build/toolchain/concurrent_links.gni,
the linker process memory is set to 10GB with ThinLTO. It was 26GB with Full LTO
before that and individual processes will run of out of memory beyond that.

* Here,
https://gotocon.com/dl/goto-chicago-2016/slides/AysyluGreenberg_BuildingADistributedBuildSystemAtGoogleScale.pdf, a
distributed build system at Google scale is shown where 5 million binary and
test builds are performed every day on several thousands of machines, each  with
a limitation of 12G of memory per process and 15 minute time-out on tests.
Memory overheads of 35G (clang) are well above these thresholds.

We have developed Propeller like ThinLTO that can be used to obtain similar
performance gains like BOLT in such environments.

+ Evaluation with the most recent BOLT

For the results, we based our customized bolt on upstream revision 7e80b300
which is committed on 8/28/2018.

Evaluating with the most recent version of BOLT (Oct 4th 2019) on clang binary
with ~50M of text requires ~35G of RAM, similar to the older version of
BOLT. Memory consumption increases rapidly with binary sizes and on a large
binary with 350M of text consumes ~70G of RAM (older BOLT version).  Even when
running several times changing the thread count from 1 to 70, the running time
and memory overhead respectively remain over 198 seconds and 34GB
(Multithreading reduces BOLT’s time overhead by at most 15% but also increases
memory overhead by 10% to upto 38 GB).


+ Overheads of CFI

TLDR; clang is pathological and the actual CFI bloat will go down from 7x to 2x.

Let us present the CFI Bloats for each benchmark with the default option, which
is creating basic block sections only for functions with samples.   For clang,
it is 7x and *not 17x* (the 17 x number is for all sections), and for the large
benchmarks it is less than 30% or 1.3x. For large benchmarks, Storage is the
highest, going from 18M to 23M, ~30%. Clang is almost pathological here. This is
because 10% of all functions in clang have samples (touched by the profile
information), and all of these functions get full basic block sections. Whereas,
for the large benchmarks, only 0.5% of functions have samples.  Now, for clang,
10% of functions that have samples also happen to contain 35% of all basic
blocks. This means, we are creating sections for 35% of all basic blocks and the
CFI bloats are clearly showing.

Now, the data for clang also shows that only 7% of the basic blocks have
samples. We are working on restricting basic block sections to only those basic
blocks that have samples. The rest of the basic blocks (cold) in that function
would share the same section.  With this, we would reduce the bloat of CFI from
7x to 2x. This is not hard to do and we will follow up with this patch.

Also for object size bloats with regards to eh_frame, the reasoning is similar. 
Restricting the section creation to only basic blocks that have profiles will
reduce this a lot more.

Importantly,  if CFI support were available for discontiguous ranges we
wouldn't have to duplicate CFI FDEs and the bloats would be near minimal.

BOLT parses CFI and DWARF and generates compact information by rewriting it.
Whereas, Propeller uses lld which uses relocations and sections to fixup but
does not rewrite it.  This is by design and that lld is not DWARF and CFI aware.
We designed basic block sections just like function sections.  The compiler
produces a bunch of sections and relocations. The linker patches the relocations
and the debug info and CFI are right, that's it.  For CFI, since there is no
support for discontiguous ranges we have to duplicate and dedup FDEs only for
blocks with sections. We are asking that CFI support discontiguous ranges and
this would look even simpler.  Alternately, if lld were made DWARF and CFI aware
we could rewrite it compactly like BOLT. These would help with object size
bloats and binary size bloats.

We would also like to clarify on the misconceptions around CFI Instructions:

There are two things that need to be clarified here:

1) Extra CFI FDE entries for basic blocks does not mean more dynamic
instructions are executed. In fact, they do not increase at all.  Krys talked
about this earlier.
2) We do deduplication of common static CFI instructions in the FDE and move it
to the CIE .  Hence, moving to a new basic block does not mean a completely new
set of CFI instructions is executed.

+ C++ Exceptions and basic block sections for these:

TLDR;  This can be implemented in propeller easily. It was considered low
priority because exception handling code is assumed in general not performance
critical .

Currently, we do not create basic block sections for any block that is involved
in exception handling.   There is nothing fundamentally difficult about
exception handling basic blocks. The exception table uses address offsets which
currently does not use relocations, and we must modify it to use relocations in
order to enable sections for exception handling basic blocks.

We will re-prioritize and send out a patch to handle exception basic blocks.

+ Relaxation Pass Efficiency

TLDR; Our relaxation pass is similar to what LLVM’s MCAssembler does but with a
caveat for efficiency.  Our experimental results show it is efficient and
convergence is guaranteed.

Our relaxation pass is very similar to what MCAssembler does as it needs to
solve the same problem, which is laying out basic blocks and optimizing branch
instruction sizes based on jump offset.  The optimal algorithm to do this is
quadratic and it involves computating of section offsets multiple times. Our
relaxation pass has a caveat for efficiency. Our relaxation pass recomputes
section offsets only after all the sections have been processed. This is
repeated  until convergence, whereas, the MCAssembler re-computes section
offsets every time a section is modified. Our pass works well in the linker as
it minimizes the section offset recomputation, which is more expensive to do in
the linker (whole program) than doing it in the assembler(per function).

We shrink jump instructions aggressively and then fix the wrongly shrunk
branches by running a pass that grows them back.  We guarantee convergence
because we always shrink in the first round and always grow in the second.

Data shows that our relaxation is efficient. For example, for clang, the
aggressive shrinking affects ~995000 branches in 6 iterations and only 4
branches had to be grown back.

+ On inconsistencies in performance data

TLDR;  We have provided a Makefile in the git repo, under llvm-propeller/splo,
to compare BOLT and Propeller performance.  “make check-performance” with
pointers to the BOLT binaries should do the comparisons.

In terms of performance optimization for code layout, fundamentally, BOLT and
Propeller are similar.  In fact, in one experiment, we extracted the basic block
order from BOLT and just used basic block sections and linker symbol ordering to
perform the same order during linking.  The performance was identical and the
ordering was exactly as expected.

Some recent changes in Propeller has caused it to regress by a small amount and
is sometimes getting hidden by the small noise.  We are debugging the
performance issue and it looks like an alignment issue or a second order effect.
Currently, because of this bug, BOLT is faster than Propeller by about 0.5% to
1% on Clang benchmark.

+ Debug Info Overhead

Large  binaries are built using  debug fission to as it significantly improves
the scalability of debug builds, https://gcc.gnu.org/wiki/DebugFission. Quoting
from the page which again reiterates the importance of scalability and
incremental builds, Fission was invented to mitigate the following issues for
debug builds of large applications:

* Out of memory errors
* Slow link times
* Slow gdb startup times

Debug Fission essentially splits the dwarf info into a separate object file and
the link action memory overheads are smaller as the input object files and the
resulting binary are smaller.

Propeller supports both fission and non-fission builds.  Even with fission, the
dwarf objects are not relocatable, so the extra relocations needed by Propeller
would still go into the main object file that contains code.   Also, Propeller
uses extra relocations for location lists too.

We looked at BOLT and it does not seem to have any support for binaries built
with fission, something we missed mentioning in the original RFC.  Fission
supports a mode which allows the individual dwarf objects, dwo files,  to be
linked into a single dwp file and BOLT would have to also rewrite the fission
object file and likely in the same process.

Another concern raised was regarding debugging overhead.  The specific concern
here is that having more debug ranges with basic block sections might increase
overheads of debugging tools.  We have not evaluated this, any benchmarks that
could measure these overheads? Also, this can be mitigated by just exposing
debug_ranges to lld.  The various ranges created for each basic block are
contiguous as most basic blocks end up together and these ranges can be
collapsed by the linker into a larger range.

+ Plan for adding future optimizations

TLDR: The model being proposed in this RFC is a first and necessary step for
enabling future optimizations in a scalable way.

Propeller is designed to be like ThinLTO.  ThinLTO breaks down whole-program
optimizations into two steps, a thin-link step generates summaries which are
used to guide the distributed/parallel backend actions step on how to transform
the individual modules.  Similarly, Propeller would use a thin-link like
analysis step to determine how to modify individual IR objects and guide
distributed/parallel back-end actions on transformations.  The goal is to keep
the whole-program step light-weight and avoid expensive code analysis and
transformations which would bloat memory.

New optimizations are being developed on Propeller and there will be more
scrutiny and discussions on how they are implemented to keep it scalable which
is a good thing.

+ Overhead of backend code generation

We have collected data for backend actions for the clang binary. Running in
parallel (standalone machine) increases the link time overhead by 40% from
38secs to 54secs and the memory overheads by ~50% from 3GB to 4.5GB, still way
smaller than monolithic approaches. Distributing these backend actions in a
distributed build system would not increase memory overheads, each action is a
separate process. We will include the data in the camera ready version.