<div dir="ltr">On 12 July 2013 15:49, Shuxin Yang <span dir="ltr"><<a href="mailto:shuxin.llvm@gmail.com" target="_blank">shuxin.llvm@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi, There:<br>
<br>
This is the proposal for parallelizing post-ipo stage. See the following for details.<br>
<br>
I also attach a toy-grade rudimentary implementation. This implementation can be<br>
used to illustrate some concepts here. This patch is not going to be committed.<br>
<br>
Unfortunately, this weekend I will be too busy to read emails. Please do not construe<br>
delayed response as being rude :-).<br>
<br>
Thanks a lot in advance for your time insightful comments!<br>
<br>
Shuxin<br>
<br>
<br>
The proposal<br>
------------<br>
It is organized as following:<br>
1) background info, if you heard "/usr/bin/ls", please skip it<br>
2) the motivation of parallelize post-IPO stage<br>
3) how to parallelize post-IPO<br>
4) the linker problems.<br>
5) the toy-grade rudimentary implementation<br>
6) misc<br>
<br>
1.Some background<br>
------------------<br>
<br>
The Interprocedural-optimization compilation, aka IPO or IPA, typically<br>
consists of three stages:<br>
<br>
S1) pre-IPO<br>
Each function goes through some analysis and not-very-aggressive optimizations.<br>
Some information is collected during this stage, this info will be to IPO stages.<br>
This info is usually called summary info.<br>
<br>
The result of this stage is "fake-objects" which is binary files using<br>
some known object format to encapsulate IR as well as summary info along with<br>
other stuff.<br>
<br>
S2) IPO:<br>
Compiler works with linker to resolve and merge symbols in the "fake-objects"<br>
<br>
Then Interprocedural analyses (IPA) are invoked to perform interprocedural<br>
analysis either based on the summary-info, or directly on the IR.<br>
<br>
Interprocedural optimizations (IPO) are called based on the IPA result.<br>
<br>
In some compilers, IPA and IPO are separated. One reason is that many IPAs can<br>
be directly conduct on the concise summary info, while many IPOs need to load<br>
IRs and bulky annotation/metadata into memory.<br>
<br>
S3) post-IPO:<br>
Typically consist of Loop-Nest-Opt, Scalar Opt, Code-Gen etc etc. While they<br>
are intra-procedural analyses/optimizers, they may directly benefit from<br>
the info collected in the IPO stages and pass down the road.<br>
<br>
LLVM collectively call S2 and S3 as "LTO CodeGen", which is very confusing.<br>
<br>
2. Why parallelize post-IPO stage<br>
==============================<br>
<br>
R1) To improve the scalarbility<br>
It is quite obvious that we are not able to put everything about a monster<br>
program in memory at once.<br>
<br>
Even if you can afford a expensive computer, the address space of a<br>
single compiler process cannot accommodate a monster program.<br>
<br>
R2) to take advantage of ample HW resource to shorten compile time.<br>
R3) make debugging lot easier.<br>
One can triage problems in a much smaller partition rather than<br>
the huge monster program.<br>
<br>
This proposal is not able to shoot the goal R1 at this moment, because during<br>
the IPO stage, currently the compiler brings everything into memory at once.<br>
<br>
3. How to parallelize post-IPO stage<br>
==============================<u></u>======<br>
<br>
From 5k' high, the concept is very simple, just to<br>
step 1).divide the merged IR into small pieces,<br>
step 2).and compile each of this pieces independendly.<br>
step 3) the objects of each piece are fed back to linker to are linked<br>
into an executable, or a dynamic lib.<br>
<br>
Section 3.1 through 3.3 describe these three steps respectively.<br></blockquote><div><br></div><div>Yes, this is one approach. I think others at Google have looked into this sort of partitioning with GCC and found that the one thing which really helps you pick the partitions, is to profile the program and make the partitions based on the actual paths of functions seen by the profile. I don't think they saw much improvement without that. See <a href="http://research.google.com/pubs/pub36355.html">http://research.google.com/pubs/pub36355.html</a> .</div>
<div><br></div><div>I do want to mention some other things we can do to parallelize. You may already know of these and have considered them and rejected them before deciding on the design you emailed out here, but I want to list them since there's already another thread with a different approach on the mailing list.</div>
<div><br></div><div>* Use what we have. LTO partitions at a time, directories for instance, on the premise that LTO'ing them will produce something smaller than the sum of its inputs. Then when you do the final whole-program step, it will be receiving smaller inputs than it otherwise would. The change to LLVM here is to fix the inliner (or other optimizations?) to reduce the chance that LTO produces an output larger than its input.<br>
</div><div><br></div><div>* Parallelize the per-function code generator within a single LLVMContext. CodeGen presently operates on a per-function basis, and is structured as an analysis over llvm IR. There shouldn't be any global state, and there shouldn't be any need for locking accesses to the IR since nothing will be mutating it. This will even speed up clang -O0, and is a solid first step that gets a thread-creation API into LLVM.</div>
<div> - What happened to "one LLVMContext per thread"? Okay, that rule is a little white lie. Always was. LLVMContext allows two libraries to use llvm under the hood without interfering with each other (even to the point of separate maps of types to avoid one library from causing slow type lookups in the other). LLVM also doesn't have locking around accesses to the IR, and few guarantees how many things a single mutating operation will need to look at or change, but with those caveats in mind it is possible to share a context across threads. Because CodeGen is structured as an analysis over the IR without mutating the IR, it should work. There's probably still global state in the code generator somewhere, but it's not a structural problem.</div>
<div><br></div><div>* Parallelize the function passes, and SCCs that are siblings in the call tree (again within a single LLVMContext). The gnarly part of this is that globals have shared use-lists which are updated as we modify each function individually. Those globals either need to have locks on their use-lists, replaced with a lockless list, or removed entirely. Probably both, as GlobalVariable's have use-lists we actually use in the optimizers, but we don't actually need the use-list for "i32 0".</div>
<div><br></div><div>* Parallelize ModulePasses by splitting them into an analysis phase and an optimization phase. Make each per-TU build emit the .bc as usual plus an analysis-file (for instance, call graph, or "which functions reads/modify which globals"). Merge all the analysis-files and farm them back out to be used as input to the programs optimizing each .bc individually -- but now they have total knowledge of the whole-program call graph and other AA information, etc.</div>
<div> - You can combine this with an RPC layer to give each worker the ability to ask for the definition of a function from another worker. LLVM already supports "unmaterialized" functions where the definition is loaded lazily. The analysis part should arrange to give us enough information to determine whether we want to do the inlining, then if we decide to materialize the function we get its body from another worker.</div>
<div><br></div><div>* Parallelize by splitting into different LLVMContexts. This spares us the difficulty of adding locks or otherwise changing the internals of LLVM, gets us the ability to spread the load across multiple machines, and if combined with the RPC idea above you can also get good inlining without necessarily loading the whole program into memory on a single machine.<br>
</div><div><br></div><div>I'm not planning to do the work any time soon so count my vote with that in mind, but if you ask me I think the first step should be to parallelize the backend within a single LLVMContext first, then to parallelize the function passes and CGSCC passes (across siblings only of course) second. Removing the use-list from simple constants is a very interesting thing to do to decrease lock contention, but we may want to do something smarter than just remove it -- consider emitting a large constant that is only used by an inline function. It is possible to emit a table of constants in the same COMDAT group as the function, then if the inline function is discarded by the linker the constants are discarded with it. I don't have a concrete proposal for that.</div>
<div><br></div><div>Nick</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">3.1. Partitioning<br>
-----------------<br>
Partitioning is to cut a resonabely-sized chunk from the big merged IRs.<br>
It roughly consists of two steps, 1) determine the partition scheme, which<br>
is relatively easy step, and 2) physically scoop the partition out of<br>
the merged IR, which is much more involved.<br>
<br>
3.1.1 Figure out Partition scheme<br>
------------------------------<u></u>----<br>
we randomly pick up some function and put them in a partition.<br>
It would be nice to perform some optimization at this moment. One opt<br>
in my mind is to reorder functions in order to reduce working-set and<br>
improve locality.<br>
<br>
Unfortunately, this opt seems to be bit blind at this time, because<br>
- CallGraph is not annotated with estimated or profiled frequency.<br>
- some linkers don't respect the order. It seems they just<br>
remembers the function order of the pristine input obj/fake-obj,<br>
and enforce this order at final link (link-exec/shared-lib) stage.<br>
<br>
Anyway, I try to ignore all these problems, and try to perform partition<br>
via following steps. Maybe we have some luck on some platforms:<br>
<br>
o. DFS the call-graph, ignoring the self-resursive edges, if freq is<br>
available, prioritizing the edges (i.e. corresponding to call-sites)<br>
such that frequent edges are visited first.<br>
<br>
o. Cut the DFS spanning tree obtained from the previous step bottom-up,<br>
Each cut/partition contains reasonable # of functions, and the aggregate<br>
size of the functions of the partition should not exceeds predefined<br>
threshold.<br>
<br>
o. repeat the previous step until the Call-graph's DFS spanning tree<br>
is empty.<br>
<br>
3.1.2 Partition transformation<br>
------------------------------<br>
<br>
This is bit involved. There are bunch of problems we have to tackle.<br>
1) When the use/def of a symbol are separated in different modules,<br>
its attribute, like linkage, visibility, need to be changed<br>
as well.<br>
<br>
[Example 1], if a symbol is flagged as "internal" to the module where<br>
the it is defined, the linkage need to be changed into "internal"<br>
to the executable/lib being compiled.<br>
<br>
[Example 2], For compile-time constants, their initialized value<br>
needs to to cloned to the partitions where it is referenced,<br>
The rationale is to make the post-ipo passes to take advantage<br>
of the initlized value to squeeeze some performance.<br>
<br>
In order to not bloat the code size, the cloned constant should<br>
mark "don't emit". [end of eg2]<br>
<br>
Being able to precisely update symbols' attribute is not only<br>
vital to correctness, it has significant impact to the the<br>
performance as well.<br>
<br>
I have not yet taken a thorough investigation of this issue. My<br>
rudimentary implementation is simply flag symbol "external" when its<br>
use/def are separated in different module. I believe this is one<br>
of the most difficult part of this work. I guess it is going to<br>
take long time to become stable.<br>
<br>
2) In order to compile each partition in each separate thread (see<br>
Section 3.2), we have to put partitions in distinct LLVMContext.<br>
<br>
I could be wrong, but I don't find the code which is able to<br>
perform function cloning across LLVMContext.<br>
<br>
My workaround in the patch is to perform function cloning in<br>
one LLVMContext (but in different Module, of course), then<br>
save the module to disk file, and load it to memory using a<br>
new LLVMContext.<br>
<br>
It is bit circuitous and expensive.<br>
<br>
One random observation:<br>
Currently, function-scoped static variables are considered<br>
as "global variables". When cloning a function with static variable,<br>
compiler has no idea if the static variables are used only by<br>
the function being cloned, and hence separate the function<br>
and the variables.<br>
<br>
I guess it would be nice if we organized symbols by its scope<br>
instead of its live-time. it would be convenient for this situation.<br>
<br>
3.2 Compile partitions independently<br>
------------------------------<u></u>--------<br>
<br>
There are two camps: one camp advocate compiling partitions via multi-process,<br>
the other one favor multi-thread.<br>
<br>
Inside Apple compiler teams, I'm the only one belong to the 1st comp. I think<br>
while multi-proc sounds bit red-neck, it has its advantage for this purpose, and<br>
while multi-thread is certainly more eye-popping, it has its advantage<br>
as well.<br>
<br>
The advantage of multi-proc are:<br>
1) easier to implement, the process run in its own address space.<br>
We don't need to worry about they can interfere with each other.<br>
<br>
2)huge, or not unlimited, address space.<br>
<br>
The disadvantage is that it's expensive. But I guess the cost is<br>
almost negligible compared to the overall IPO compilation.<br>
<br>
The advantage of multi-threads I can imagine are:<br>
1) sound fancy<br>
2) it is light-weight<br>
3) inter-thread communication is easier than IPC.<br>
<br>
Its disadvantage are:<br>
1). Oftentime we will come across race-condition, and it took<br>
awful long time to figure it out. While the code is supposed<br>
to be mult-thread safe, we might miss some tricky case.<br>
Trouble-shooting race condition is a nightmare.<br>
<br>
2) Small address space. This is big problem if we the compiler<br>
is built 32-bit . In that case, the compiler is not able to bring<br>
lots of stuff in memory even if the HW dose<br>
provide ample mem.<br>
<br>
3) The thread-safe run-time lib is more expensive.<br>
I once linked a compiler using -lpthread (I dose not have to) on a<br>
UNIX platform, and saw the compiler slow down by about 1/3.<br>
<br>
I'm not able to convince the folks in other camp, neither are they<br>
able to convince me. I decide to implement both. Fortunately, this<br>
part is not difficult, it seems to be rather easy to crank out one within short<br>
period of time. It would be interesting to compare them side-by-side,<br>
and see which camp lose:-). On the other hand, if we run into race-condition<br>
problem, we choose multi-proc version as a fall-back.<br>
<br>
Regardless which tech is going to use to compile partition<br>
independently, in order to judiciously and adaptively choose appropriate<br>
parallel-factor, the compiler certainly need a lib which is able to<br>
figure out the load the entire system is in. I don't know if there are<br>
such magic lib or not.<br>
<br>
4. the tale of two kinds of linker<br>
------------------------------<u></u>----<br>
<br>
As far as I can tell, llvm suports two kind linker for its IPO compilation,<br>
and the supports are embodied by two set of APIs/interfaces.<br>
<br>
o. Interface 1, those stuff named lto_xxxx().<br>
o. GNU gold interface,<br>
The compiler interact with GNU gold via the adapter implemented<br>
in tools/gold/gold-plugin.cpp.<br>
<br>
This adpater calls the interface-1 to control the IPO process.<br>
It dose not have to call the interface APIs, I think it is definitely<br>
ok it call internal functions.<br>
<br>
The compiler used to generate a single object file from the merged<br>
IR, now it will generate multiple of them, one for each partition.<br>
<br>
So, the interface 1 is *NOT* sufficient any more.<br>
<br>
For gold linker users, it is easy to make them happy just by<br>
hacking the adapter, informing the linker new input object<br>
files. This is done transparently, the users don't need to install new ld.<br>
<br>
For those system which invoke ld interacting with the libLTO.{so,dylib},<br>
it has to accept the new APIs I added to the interface-1 in order to<br>
enable the new functionality. Or maybe we can invoke '/the/path/to/ld -r *.o -o merged.o'<br>
and feed the merged.o the linker (this will keep the interface<br>
interact)? Unfortunately, it dose not work at all, how can I know the path<br>
the ld? the libLTO.{so,dydlib} is invoked as plugin; it cannot see the argv.<br>
How about hack them by adding a nasty flag pointing to the right ld?<br>
Well, it works. However, I don't believe many people like to do it this way,<br>
that means I loose huge number of "QA" who are working hard for this compiler.<br>
<br>
What's wrong with the interface-1? The ld side is more active than<br>
the compiler side, however, in concept the IPO is driven by the compiler side.<br>
This mean this interface is changing over time.<br>
<br>
In contrast, the gold interface (as I rever-engineer from the adpator<br>
code) is more symbol-centric, taking little IPO-thing into account.<br>
That interface is simple and stable.<br>
<br>
5. the rudimentary implementation<br>
------------------------------<u></u>---<br>
<br>
I make it works for bzip2@cpu2kint yesterday. bzip2 is "tiny"<br>
program, I intentionally lower the partition size to get 3 partitions.<br>
There is no comment in the code, and it definitely need rewrite. I<br>
just check the correctness (with ref input), and I don't measure how much<br>
it degrade the performance. (due to the problem I have not got chance<br>
to tackle, see section 3.1.2, the symbol attribute stuff).<br>
<br>
The control flow basically is:<br>
1. add a module pass to the IPO pass-manager, and figure<br>
out the partition scheme.<br>
<br>
2) physically partition the merged partition.<br>
the IR and the obj of partition are placed in a new dir. "llvmipo" by default<br>
<br>
--<br>
ls llvmipo/<br>
Makefile merged part1.bc part1.o part2.bc part2.o part3.bc part3.o<br>
--<br>
<br>
3) For demo purpose, I drive the post-IPO stage via a makefile, which encapsulate<br>
hack and other nasty stuff.<br>
<br>
NOTE that the post-ipo pass in my hack contains only CodeGen pass, we need to<br>
reorganize the PassManagerBuilder::<u></u>populateLTOPassManager(), which intermingle<br>
IPO pass along with intra-proc scalar pass, we need to separate them and the intra-proc<br>
scalar pass to post-IPO stage.<br>
<br>
<br>
1 .PHONY = all<br>
2<br>
3<br>
4 BC = part1.bc part2.bc part3.bc<br>
5 OBJ = ${BC:.bc=.o}<br>
6<br>
7 all : merged<br>
8 %.o : %.bc<br>
9 $(HOME)/tmp/lto.llc -filetype=obj $+ -o $@<br>
10<br>
11 merged : $(OBJ)<br>
12 /usr/bin/ld $+ -r -o $@<br>
13<br>
<br>
4. as the Makefile sugguest, the *.o of the partions are linked into a single obj "merged"<br>
and feed back to link.<br>
<br>
<br>
6) Miscellaneous<br>
===========<br>
Will partitioning degrade performance in theory. I think it depends on the definition of<br>
performance. If performance means execution-time, I guess it dose not.<br>
However, if performance includes code-size, I think it may have some negative impact.<br>
Following is few scenario:<br>
<br>
- constants generated by the post-IPO passes are not shared across partitions<br>
- dead func may be detected during the post-IPO stage, and they may not be deleted.<br>
<br>
<br>
<br>
<br>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>