<div dir="ltr"><div>I've recently implemented profile guided section layout in llvm + lld using the <span style="background-color:rgb(248,249,250);color:rgb(0,0,0);font-family:sans-serif;font-size:14px">Call-Chain Clustering (</span>C<span style="background-color:rgb(248,249,250);color:rgb(0,0,0);font-family:sans-serif;font-size:14px">³</span><span style="background-color:rgb(248,249,250);color:rgb(0,0,0);font-family:sans-serif;font-size:14px">)</span> heuristic from <a href="https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf">https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf</a> . In the programs I've tested it on I've gotten from 0% to 5% performance improvement over standard PGO with zero cases of slowdowns and up to 15% reduction in ITLB misses.</div><div><br></div><div><br></div><div>There are three parts to this implementation.</div><div><br></div><div>The first is a new llvm pass which uses branch frequency info to get counts for each call instruction and then adds a module flags metatdata table of function -> function edges along with their counts.</div><div><br></div><div>The second takes the module flags metadata and writes it into a .note.llvm.callgraph section in the object file. This currently just dumps it as text, but could save space by reusing the string table.</div><div><br></div><div>The last part is in lld. It reads the .note.llvm.callgraph data from each object file and merges them into a single table. It then builds a call graph based on the profile data then iteratively merges the hottest call edges using the C<span style="background-color:rgb(248,249,250);color:rgb(0,0,0);font-family:sans-serif;font-size:14px">³</span> heuristic as long as it would not create a cluster larger than the page size. All clusters are then sorted by a density metric to further improve locality.</div><div><br></div><div><br></div><div>There are a couple issues with the current implementation that shouldn't be too hard to fix.</div><div><br></div><div>The .note.llvm.callgraph sections add about 10% to the size of each object file. This can be fixed by reusing the symbol string table instead of duplicating all the strings.</div><div><br></div><div>The ordering algorithm is n^2 in the number of call graph edges. This is because it's using a trivial algorithm and can be fixed by doing something more intelligent.</div><div><br></div><div>It doesn't currently work for LTO as the llvm pass needs to be run after all inlining decisions have been made and LTO codegen has to be done with -ffunction-sections.</div><div><br></div><div>It's only implemented for ELF.</div><div><br></div><div><br></div><div>I've attached the llvm and lld patches and would appreciate feedback on the overall design, the method of threading the profile data to the linker, and an improved ordering algorithm. No need for a detailed code review as I'll be making changes, adding tests, and posting proper patches for review.</div><br clear="all"><div><div class="gmail_signature">- Michael Spencer</div></div>
</div>