<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Feb 27, 2020 at 6:34 PM Fangrui Song via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">I met with the Propeller team today (we work for the same company but it<br>
was my first time meeting two members on the team:) ).<br>
One thing I have been reassured:<br>
<br>
* There is no general disassembly work. General<br>
disassembly work would assuredly frighten off developers. (Inherently<br>
unreliable, memory usage heavy and difficult to deal with CFI, debug<br>
information, etc)<br>
<br>
Minimal amount of plumbing work (<a href="https://reviews.llvm.org/D68065" rel="noreferrer" target="_blank">https://reviews.llvm.org/D68065</a>) is<br>
acceptable: locating the jump relocation, detecting the jump type,<br>
inverting the direction of a jump, and deleting trailing bytes of an<br>
input section</blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">. The existing linker relaxation schemes already do similar<br>
things. Deleting a trailing jump is similar to RISC-V where sections can<br>
shrink (not implemented in lld; R_RISCV_ALIGN and R_RISCV_RELAX are in<br>
my mind)) (binutils supports deleting bytes for a few other<br>
architectures, e.g. msp430, sh, mips, ft32, rl78). With just minimal<br>
amount of disassembly work, conceptually the framework should not be too<br>
hard to be ported to another target.<br>
<br>
One thing I was not aware of (perhaps the description did not make it clear) is that<br>
Propeller intends to **reorder basic block sections across translation units**.<br>
This is something that full LTO can do while ThinLTO cannot.<br>
Our internal systems cannot afford doing a full LTO (**Can we fix the bottleneck of full LTO** [1]?)<br>
for large executables and I believe some other users are in the same camp.<br></blockquote><div><br></div><div>Right, beyond distributed build system, even on a single machine and for "small" projects like clang: building on a laptop with FullLTO can be challenging in terms of memory consumption, and the iterative development is just not practical.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
Now, with ThinLTO, the post link optimization scheme will inevitably require<br>
help from the linker/compiler. It seems we have two routes:<br>
<br>
## Route 1: Current Propeller framework<br>
<br>
lld does whole-program reordering of basic block sections. We can extend it in<br>
the future to overalign some sections and pad gaps with NOPs. What else can we<br>
do? Source code/IR/MCInst is lost at this stage. Without general assembly<br>
work, it may be difficult to do more optimization.<br>
<br>
This makes me concerned of another thing: Intel's Jump Condition Code Erratum.<br>
<a href="https://www.intel.com/content/dam/support/us/en/documents/processors/mitigations-jump-conditional-code-erratum.pdf" rel="noreferrer" target="_blank">https://www.intel.com/content/dam/support/us/en/documents/processors/mitigations-jump-conditional-code-erratum.pdf</a><br>
<br>
Put it in the simplest way, a Jcc instruction whose address ≡ 30 or 31<br>
(mod 32) should be avoided. There are assembler level (MC) mitigations<br>
(function sections are overaligned to 32), but because we use basic<br>
block sections (sh_addralign<32) and need reordering, we have to redo<br>
some work at the linking stage.<br>
<br>
After losing the representation of MCInst, it is not clear to me how we can<br>
insert NOPs/segment override prefixes without doing disassembly work in the linker.<br>
<br>
Route 2 does heavy lifting work in the compiler, which can naturally reuse the assembler level mitigation,<br>
CFI and debug information generating, and probably other stuff.<br>
(How will debug information be bloated?)<br>
<br>
## Route 2: Add another link stage, similar to a Thin Link as used by ThinLTO.<br>
<br>
Regular ThinLTO with minimized bitcode files:<br>
<br>
all: compile thin_link thinlto_backend final_link<br>
<br>
compile a.o b.o a.indexing.o b.indexing.o: a.c b.c<br>
$(clang) -O2 -c -flto=thin -fthin-link-bitcode=a.indexing.o a.c<br>
$(clang) -O2 -c -flto=thin -fthin-link-bitcode=b.indexing.o b.c<br>
<br>
thin_link lto/a.o.thinlto.bc lto/b.o.thinlto.bc a.rsp: a.indexing.o b.indexing.o<br>
$(clang) -fuse-ld=lld -Wl,--thinlto-index-only=a.rsp -Wl,--thinlto-prefix-replace=';lto' -Wl,--thinlto-object-suffix-replace='.indexing.o;.o' a.indexing.o b.indexing.o<br>
<br>
thinlto_backend lto/a.o lto/b.o: a.o b.o lto/a.o.thinlto.bc lto/b.o.thinlto.bc<br>
$(clang) -O2 -c -fthinlto-index=lto/a.o.thinlto.bc a.o -o lto/a.o<br>
$(clang) -O2 -c -fthinlto-index=lto/b.o.thinlto.bc b.o -o lto/b.o<br>
<br>
final_link exe: lto/a.o lto/b.o a.rsp<br>
# Propeller does basic block section reordering here.<br>
$(clang) -fuse-ld=lld @a.rsp -o exe<br>
<br>
We need to replace the two stages thinlto_backend and final_link with<br>
three.<br>
<br>
Propelled ThinLTO with minimized bitcode files:<br>
<br>
propelled_thinlto_backend lto/a.mir lto/b.mir: a.o b.o lto/a.o.thinlto.bc lto/b.o.thinlto.bc<br>
# Propeller emits something similar to a Machine IR file.<br>
# a.o and b.o are all IR files.<br>
$(clang) -O2 -c -fthinlto-index=lto/a.o.thinlto.bc -fpropeller a.o -o lto/a.mir<br>
$(clang) -O2 -c -fthinlto-index=lto/b.o.thinlto.bc -fpropeller b.o -o lto/b.mir<br>
<br>
propeller_link propeller/a.o propeller/b.o: lto/a.mir lto/b.mir<br>
# Propeller collects input Machine IR files,<br>
# spawn threads to generate object files parallelly.<br>
$(clang) -fpropeller-backend -fpropeller-prefix-replace='lto;propeller' lto/a.mir lto/b.mir<br>
<br>
final_link exe: propeller/a.o propeller/b.o<br>
# GNU ld/gold/lld links object files.<br>
$(clang) $^ -o exe<br></blockquote><div><br></div><div>There was an interesting talk last week at the LLVM performance workshop: <a href="https://llvm.org/devmtg/2020-02-23/#kl" target="_blank">Global Machine Outliner for ThinLTO</a> which introduced a similar stage in ThinLTO (for another purpose though). I believe they avoid the serialization of MIR by running the CodeGen twice instead (once to collect the cross-module informations, and the second time using these informations).</div><div>CC the author in case the slides are already available online.<br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
A .mir may be much large than an object file. So lto/a.mir may be<br>
actually an object file annotated with some information, or some lower<br>
level representation than a Machine IR (there should be a guarantee that<br>
the produced object file will keep the basic block structure unchanged<br>
=> otherwise basic block profiling information will not be too useful).<br>
<br>
<br>
<br>
[1]: **Can we fix the bottleneck of full LTO** [1]?<br>
<br>
I wonder whether we have reached a "local maximum" of ThinLTO.<br>
If full LTO were nearly as fast as ThinLTO, how would we design a post-link optimization framework?<br>
Apparently, if full LTO did not have the scalability problem, we would<br>
not do so much work in the linker?<br></blockquote><div></div><div><br></div><div>At lot of work went into ThinLTO because the scalability issue of LTO was considered inherent to the design. It isn't clear what you're suggesting here though?</div><div><br></div><div>-- </div><div>Mehdi</div><div><br></div><div> </div></div></div></div></div>