[LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM backend code generation

[Wan, Xiaofei]

Hi, community:

For the sake of our business need, I want to enable "Function-based parallel code generation" to boost up the compilation of single module, please see the details of the design and provide your feedbacks on below aspects, thanks

1.       Is this idea the proper solution for my requirement

2.       This new feature will be enabled by llc -thd=N and has no impact on original llc when -thd=1

3.       Can this new feature of llc be accepted by community and merged into LLVM code tree

Patches
The patch is divided into four separated parts, the all-in-one patch could be found here:

http://llvm-reviews.chandlerc.com/D1152

Design
https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgjY-vhyfySg/edit?usp=sharing


Function-based parallel LLVM backend code generation
Wan Xiaofei (xiaofei.wan at intel.com)
Background
l  Our business need to compile C/C++ source files into LLVM IR and link them into a big BC file; the big BC file is then compiled into binary code on different arch/target devices.
l  Backend code generation is a time-consuming activity happened on target device which makes it an important user experience.
l  Make -j or file based parallelism can't help here since there is only one big BC file; function-based parallel LLVM backend code generation is a good solution to improve compilation time which will fully utilize multi-cores.
Overall design strategy and goal
l  Generate totally same binary as what single thread output
l  No impacts on single thread performance
l  Little impacts on LLVM code infrastructure
Why not choose module-based parallelism
l  Module partition
ü  How to partition one module into several modules which will consume similar time;
Compilation time is not decided by instructions number.
Compilation time depends on instruction categories + instruction number + CFG + others
ü  We tried this solution and stopped after below obstacles.
Global variables & functions may be used by other modules; each global variables & constants has a use list, use list has to be re-constructed during module partition.
Functions and variables must be cloned out since they can't belong to two modules; this may be a big effort and a waste of memory, especially for big BC files.
l  Binaries merge
ü  Linking different binaries is needed after all modules are finished, usually linking is a time consuming activity.
l  Validation strategy
ü  To simplify the validation, generating same binary is the best solution (including symbols and function order). It is not easy to generate totally identical binaries even though it is correct in module-based parallelism. Symbol & temp variable mangling are done in different modules; it is difficult to ensure the symbols are same.
ü  The function order after linking may not be same as what it should be in one-module.
l  Potential benefit
ü  What is the benefit from module-based parallelism, can it bring more benefit than function-based parallelism?
ü  Module partition & module linkage are two extra overheads.
ü  Global variables should be cloned for several times, it is a big memory penalty.
Design of function-based parallelism
[cid:image001.png at 01CE824E.0C5C7950]
Step 1: Make LLVM pass Reentrant
l  Function passes should be thread-safe since function-based parallelism is adopted.
l  UseList and ValueHandleList of 'Constant' class may be accessed by different functions; all operations on UseList and ValueHandleList should be locked.
l  LLVMContext will be shared by different functions; all accesses to LLVMContext should be locked.
l  For allocators which use default SlabAllocator (which is static), operation on these kinds of allocators should be locked.
l  Symbols in MCContext are accessed by different functions, it should be locked.
Step 2: Multiple pass manager
*      The role of PM in LLVM code generator
ü  PassManager is top level pass manager, it contains all module level passes which are necessary to generate the binary code; In all module-level passes, function pass manager is the biggest module pass.
ü  PassManager will control all steps during the code generation; a function should walk through all passes contained in function pass manager to emit final binary code.
ü  Pass can't be shared by different function/thread simultaneously since pass contain many immediate information.
*      Multiple pass managers
ü  Multiple pass managers are created to implement parallel compilation, each pass manager is owned by one thread.
ü  During all passes/pass managers, there is one parent pass/pass manager which will delegate some activities for other passes/pass managers
ü  AsmPrinter is the last pass for function passes, it is shared by all threads; in this pass, parent AsmPrinter will delegate the code emission for other threads.
Step 3: Share the last pass "AsmPrinter"
*      AsmPrinter is the last function pass which will emit the final binary code; it is shared by different functions/threads.
*      AsmPrinter is responsible for merging instructions generated by different threads.
*      AsmPrinter will provide mechanism to make sure the instructions sequences are same as what they are in single thread.
Validation methodology & test result
*      Parallel llc will generate totally same binary code as single thread, similar validation to single thread can be used
*      Long time stress tests are launched to guarantee the correctness and robustness.
Current status and test result
*      Parallel llc can generate same code as single thread by "objdump -d", it could pass 10 hours stress test for all performance benchmark
*      Parallel llc can introduce ~2.9X performance gain on XEON sever for 4 threads


Thanks
Wan Xiaofei
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 202279 bytes
Desc: image001.png
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Parallel.CG.Threading.patch
Type: application/octet-stream
Size: 5225 bytes
Desc: Parallel.CG.Threading.patch
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Parallel.CG.AsmPrinter.patch
Type: application/octet-stream
Size: 29239 bytes
Desc: Parallel.CG.AsmPrinter.patch
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Parallel.CG.MultiplePM.patch
Type: application/octet-stream
Size: 21920 bytes
Desc: Parallel.CG.MultiplePM.patch
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Parallel.CG.PassReentrant.patch
Type: application/octet-stream
Size: 56511 bytes
Desc: Parallel.CG.PassReentrant.patch
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130716/6461f125/attachment-0003.obj>