<div dir="ltr"><div>Hello Maksim,</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Oct 16, 2019 at 3:52 PM Maksim Panchenko <<a href="mailto:maks@fb.com" target="_blank">maks@fb.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-US">
<div>
<p class="MsoNormal">Hi Sri,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I want to clarify one thing before sending a detailed reply: did you evaluate<u></u><u></u></p>
<p class="MsoNormal">BOLT on Clang built with basic block sections? </p></div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US"><div><p class="MsoNormal"> In the makefile you reference,<u></u><u></u></p>
<p class="MsoNormal">there are two versions: a “vanilla” and a default built with function sections.<u></u><u></u></p>
<p class="MsoNormal">High overheads you see with BOLT on Clang do not match our experience.</p></div></div></blockquote><div><br></div><div>Thanks for pointing that out in the Makefile. We double-checked and noticed a bug in our Makefile. For clang, we noticed that we are BOLTING with basic block symbols which seems to affect the memory consumption of BOLT. So, we have re-measured with recent bolt and for *full transparency* we have uploaded the binaries, BOLT's yaml files and perf.data files and the commands so that you can independently verify our results and check the binaries. We have gzipped all the files to keep it under 2G limit for git lfs, everything is here : <a href="https://github.com/google/llvm-propeller/tree/plo-dev/clang-bolt-experiment">https://github.com/google/llvm-propeller/tree/plo-dev/clang-bolt-experiment</a> We have run our experiments on a 192G machine with Intel 18 core.</div><div><br></div><div>We built llvm-bolt with most recent sources and is *pristine* with none of our patches and uploading the binary we used here, <a href="https://github.com/google/llvm-propeller/blob/plo-dev/clang-bolt-experiment/llvm-bolt">https://github.com/google/llvm-propeller/blob/plo-dev/clang-bolt-experiment/llvm-bolt</a> That's a very recent BOLT binary, git hash: 988a7e8819b882fd14e18d149f8d3f702b134680</div><div><br></div><div>The <a href="https://github.com/google/llvm-propeller/tree/plo-dev/clang-bolt-experiment">https://github.com/google/llvm-propeller/tree/plo-dev/clang-bolt-experiment</a>/{v1,v2} contains two sets of binaries. The first binary is pristine recent clang-10 built from 2 weeks ago with additionally only -Wl,-q. v2 is another clang binary also only additionally built with -q. There are no labels or sections or any other Propeller flags used to build these clang binaries. Here is the command we are using to optimize with BOLT, all the commands have been checked in too.</div><div><br></div><div>You should be able to run llvm-bolt now on these binaries as all the files are provided. We have also provided the raw perf data files in case you want to independently convert. </div><div><br></div><div>$ /usr/bin/time -v /llvm-bolt clang-10 -o pgo_relocs-bolt-compiler -b pgo_relocs-compiler.yaml -split-functions=3 -reorder-blocks=cache+ -reorder-functions=hfsort -relocs=1 --update-debug-sections </div><div><br></div><div></div><div>For version 2, this is the number:</div><div><br></div><div>Elapsed (wall clock) time (h:mm:ss or m:ss): 2:05.40<br></div><div>Maximum resident set size (kbytes): 18742688<br></div><div><br></div><div>That is 125 seconds and ~18G of RAM.<br></div><div><br></div><div>For version 1, this hangs and we stopped it after several minutes and the maximum RSS size crossing 50G. This is most likely just a bug and you should be able to reproduce this. The binary seems to be running and printing update messages.<br></div><div><br></div><div></div><div>We also measured without update-debug-sections too with the command :<br></div><div><br></div><div>$ /usr/bin/time -v /llvm-bolt clang-10 -o pgo_relocs-bolt-compiler -b pgo_relocs-compiler.yaml -split-functions=3 -reorder-blocks=cache+ -reorder-functions=hfsort -relocs=1</div><div><br></div><div>For version1 :</div><div>Elapsed (wall clock) time (h:mm:ss or m:ss): 1:33.74<br></div><div>Maximum resident set size (kbytes): 14824444<br></div><div><br></div><div>93 seconds and ~14G of RAM</div><div><br></div><div>version 2 : </div><div>Elapsed (wall clock) time (h:mm:ss or m:ss): 1:21.90<br></div><div>Maximum resident set size (kbytes): 14511912<br></div><div><br></div><div>similar 91 secs and ~14G</div><div><br></div><div>Now, coming back to the bug in the Makefile, we originally reported ~35G. That is *wrong* since the clang binary used to measure bolt overheads was built with basic block labels. Our *sincere apologies* for this, this showed BOLT as consuming more memory than is actual for clang. We double-checked BOLT numbers with the internal benchmark search2 for sanity and that is built *without any labels* and only with "-Wl,-q". We are checking the other large internal benchmarks too. We cannot disclose internal benchmarks. So, we will get more large open-source benchmarks like Chrome or gcc built with bolt and share the binaries and results so you can independently verify.<br></div><div><br></div><div>Thanks</div><div>Sri</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US"><div><p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Thanks,<u></u><u></u></p>
<p class="MsoNormal">Maksim<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On 10/14/19, 11:44 AM, "llvm-dev on behalf of Sriraman Tallam via llvm-dev" <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a> on behalf of
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Hello, <u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I wanted to consolidate all the discussions and our final thoughts on the concerns raised. I have attached a document consolidating it.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">BOLT’s performance gains inspired this work and we believe BOLT <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">is a great piece of engineering. However, there are build environments where
<br>
scalability is critical and memory limits per process are tight :<br>
<br>
* Debug Fission, <a href="https://gcc.gnu.org/wiki/DebugFission" target="_blank">https://gcc.gnu.org/wiki/DebugFission</a> was primarily
<br>
invented to achieve scalability and better incremental build times while <br>
building large binaries with debug information.<br>
<br>
* ThinLTO, <br>
<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__blog.llvm.org_2016_06_thinlto-2Dscalable-2Dand-2Dincremental-2Dlto.html&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=4c9jZ8ZwYXlxUZHyw4Wing&m=BOTyGbKXpK1kdAvdQF0QoVsl4A5BCIQJMEEXJRVW6To&s=rW9yHyu5DPla9M38HolcW_w_Md8TLqe53BTWIClBxO4&e=" target="_blank">http://blog.llvm.org/2016/06/thinlto-scalable-and-incremental-lto.html</a>
was <br>
primarily invented to make LLVM’s full LTO scalable and keep the memory and <br>
time overheads low. ThinLTO has enabled much broader adoption of whole <br>
program optimization, by making it non-monolithic.<br>
<br>
* For Chromium builds, <br>
<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__chromium-2Dreview.googlesource.com_c_chromium_src_-2B_695714_3_build_toolcha&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=4c9jZ8ZwYXlxUZHyw4Wing&m=BOTyGbKXpK1kdAvdQF0QoVsl4A5BCIQJMEEXJRVW6To&s=8EBzmSqxfeVJXXXFKkx4Mzkf5d6cucxPc9pXkF36v_o&e=" target="_blank">https://chromium-review.googlesource.com/c/chromium/src/+/695714/3/build/toolcha</a><br>
in/concurrent_links.gni, the linker process memory is set to 10GB with ThinLTO. <br>
It was 26GB with Full LTO before that and individual processes will run of out <br>
of memory beyond that.<br>
<br>
* Here, <br>
<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__gotocon.com_dl_goto-2Dchicago-2D2016_slides_AysyluGreenberg-5FBuildingADistrib&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=4c9jZ8ZwYXlxUZHyw4Wing&m=BOTyGbKXpK1kdAvdQF0QoVsl4A5BCIQJMEEXJRVW6To&s=lH-bp7s0QTtCyJkcSTOL8B_wOsRw-SLGrFsbZLmjaxQ&e=" target="_blank">https://gotocon.com/dl/goto-chicago-2016/slides/AysyluGreenberg_BuildingADistrib</a><br>
utedBuildSystemAtGoogleScale.pdf, a distributed build system at Google scale <br>
is shown where 5 million binary and test builds are performed every day on <br>
several thousands of machines, each with a limitation of 12G of memory per <br>
process and 15 minute time-out on tests. Memory overheads of 35G (clang) are <br>
well above these thresholds.<br>
<br>
We have developed Propeller like ThinLTO that can be used to obtain similar <br>
performance gains like BOLT in such environments.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Sri<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Oct 11, 2019 at 11:25 AM Xinliang David Li via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Oct 11, 2019 at 10:46 AM James Y Knight via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal">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? <u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Apologies if this is obvious for those who actually know what they're talking about here. :)<u></u><u></u></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">It is a fair question. <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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. <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">It is conceivable to have an option to control the level of granularity at the possible cost of performance.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">thanks,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">David<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Wed, Oct 2, 2019 at 6:18 PM Rafael Auler <<a href="mailto:rafaelauler@fb.com" target="_blank">rafaelauler@fb.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal">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).<br>
<br>
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).<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(181,196,223);padding:3pt 0in 0in">
<p class="MsoNormal"><b><span style="font-size:12pt;color:black">From:
</span></b><span style="font-size:12pt;color:black">llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>> on behalf of James Y Knight via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Reply-To: </b>James Y Knight <<a href="mailto:jyknight@google.com" target="_blank">jyknight@google.com</a>><br>
<b>Date: </b>Wednesday, October 2, 2019 at 1:59 PM<br>
<b>To: </b>Maksim Panchenko <<a href="mailto:maks@fb.com" target="_blank">maks@fb.com</a>><br>
<b>Cc: </b>"<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Subject: </b>Re: [llvm-dev] [RFC] Propeller: A frame work for Post Link Optimizations</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">And emitting discontiguous functions is a fundamental goal of this, right?<u></u><u></u></p>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Wed, Oct 2, 2019 at 4:25 PM Maksim Panchenko via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin:5pt 0in 5pt 4.8pt">
<div>
<div>
<p class="MsoNormal">Thanks for clarifying. This means once you move to the next basic block (or any other basic<u></u><u></u></p>
<p class="MsoNormal">block in the function) you have to execute an entirely new set of CFI instructions<u></u><u></u></p>
<p class="MsoNormal">except for the common CIE part. While indeed this is not as bad, on average, the overall<u></u><u></u></p>
<p class="MsoNormal">active memory footprint will increase.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Creating one FDE per basic block means that .eh_frame_hdr, an allocatable section,<u></u><u></u></p>
<p class="MsoNormal">will be bloated too. This will increase the FDE lookup time. I don’t see .eh_frame_hdr<u></u><u></u></p>
<p class="MsoNormal">being mentioned in the proposal.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Maksim<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On 10/2/19, 12:20 PM, "Krzysztof Pszeniczny" <<a href="mailto:kpszeniczny@google.com" target="_blank">kpszeniczny@google.com</a>> wrote:<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Wed, Oct 2, 2019 at 8:41 PM Maksim Panchenko via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin:5pt 0in 5pt 4.8pt">
<p class="MsoNormal">*Pessimization/overhead for stack unwinding used by system-wide profilers and<br>
for exception handling*<br>
<br>
Larger CFI programs put an extra burden on unwinding at runtime as more CFI<br>
(and thus native) instructions have to be executed. This will cause more<br>
overhead for any profiler that records stack traces, and, as you correctly note<br>
in the proposal, for any program that heavily uses exceptions.<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">--<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Krzysztof Pszeniczny<u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="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=" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=4c9jZ8ZwYXlxUZHyw4Wing&m=BOTyGbKXpK1kdAvdQF0QoVsl4A5BCIQJMEEXJRVW6To&s=nI5BAwXY8FSk9XDrnUJfuretr1UXOXiiqKNvmEDjDXo&e=" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><u></u><u></u></p>
</blockquote>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=4c9jZ8ZwYXlxUZHyw4Wing&m=BOTyGbKXpK1kdAvdQF0QoVsl4A5BCIQJMEEXJRVW6To&s=nI5BAwXY8FSk9XDrnUJfuretr1UXOXiiqKNvmEDjDXo&e=" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</blockquote></div></div>