llvm dev - Jul 2013 - [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM backend code generation

Yes, the purpose is similar, we started this job from last year;
But it Shuxin's solution is module based (correct me if I am wrong), we
tried this solution and failed for many reasons, it is described in my design
document
https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgjY-vhyfySg/edit?usp=sharing

we need discuss two solution and compare them, then adopt one solution

The biggest difference of module based parallelism and function based
parallelism are
1. how to partition module into different pieces which consume similar time, it
is a difficult question
2. How to make sure the generated binary is same each time
3. if 2 can't be achieved, it is difficult to validate the correctness of
parallelism

Thanks
Wan Xiaofei

-----Original Message-----
From: Evan Cheng [mailto:evan.cheng at apple.com] 
Sent: Tuesday, July 16, 2013 8:28 PM
To: Wan, Xiaofei
Cc: LLVM Developers Mailing List (llvmdev at cs.uiuc.edu); Shuxin Yang
Subject: Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM
backend code generation

Please see Shuxin's proposal on "parallelizing post-IPO stage". It
seems the two projects are related.

Evan

On Jul 16, 2013, at 3:33 AM, "Wan, Xiaofei" <xiaofei.wan at
intel.com> wrote:
> 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/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgj
> Y-vhyfySg/edit?usp=sharing
> 
> 
> Background
> 1. 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.
> 2. Backend code generation is a time-consuming activity happened on target
device which makes it an important user experience.
> 3. 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
> 1. Generate totally same binary as what single thread output 2. No 
> impacts on single thread performance & conformance 3. Little impacts 
> on LLVM code infrastructure
> 
> Current status and test result
> 1. Parallel llc can generate same code as single thread by "objdump 
> -d", it could pass 10 hours stress test for all performance benchmark 
> 2. Parallel llc can introduce ~2.9X performance gain on XEON sever for 
> 4 threads
> 
> 
> Thanks
> Wan Xiaofei
> <Parallel.CG.7z>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 7/16/13 7:23 AM, Wan, Xiaofei wrote:
> Yes, the purpose is similar, we started this job from last year;
> But it Shuxin's solution is module based (correct me if I am wrong), we
tried this solution and failed for many reasons, it is described in my design
document
>
https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgjY-vhyfySg/edit?usp=sharing
>
> we need discuss two solution and compare them, then adopt one solution
>
> The biggest difference of module based parallelism and function based
parallelism are
> 1. how to partition module into different pieces which consume similar
time, it is a difficult question
Why difficult?
> 2. How to make sure the generated binary is same each time
It depends on what is the same.  In the merged version, constant may 
keep one copy, while
in the partition version,  constant may be duplicated as the post-IPO 
passes may generated
some constant, and they cannot share with the same constant generated in 
other partitions.

All these issues don't sound to be a problem in practice.
> 3. if 2 can't be achieved, it is difficult to validate the correctness
of parallelism
It is nothing about the correctness.

-----Original Message-----
From: Shuxin Yang [mailto:shuxin.llvm at gmail.com] 
Sent: Wednesday, July 17, 2013 1:50 AM
To: Wan, Xiaofei
Cc: Evan Cheng; Shuxin Yang; LLVM Developers Mailing List (llvmdev at
cs.uiuc.edu)
Subject: Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM
backend code generation


On 7/16/13 7:23 AM, Wan, Xiaofei wrote:
> Yes, the purpose is similar, we started this job from last year; But 
> it Shuxin's solution is module based (correct me if I am wrong), we 
> tried this solution and failed for many reasons, it is described in my 
> design document 
> https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgj
> Y-vhyfySg/edit?usp=sharing
>
> we need discuss two solution and compare them, then adopt one solution
>
> The biggest difference of module based parallelism and function based 
> parallelism are 1. how to partition module into different pieces which 
> consume similar time, it is a difficult question
Why difficult?
> 2. How to make sure the generated binary is same each time
It depends on what is the same.  In the merged version, constant may keep one
copy, while in the partition version,  constant may be duplicated as the
post-IPO passes may generated some constant, and they cannot share with the same
constant generated in other partitions.

All these issues don't sound to be a problem in practice.
> 3. if 2 can't be achieved, it is difficult to validate the correctness 
> of parallelism
It is nothing about the correctness.

[Xiaofei] why? I don't understand it very well here, you mean it can
generate totally identical binaries as the original llc, including the function
order (function order may not affect code quality, but we should make sure the
output is same in each run)?