<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
        {font-family:宋体;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:宋体;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
        {font-family:"\@宋体";
        panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:宋体;}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
        {mso-style-priority:34;
        margin:0cm;
        margin-bottom:.0001pt;
        text-indent:21.0pt;
        font-size:12.0pt;
        font-family:宋体;}
span.hoenzb
        {mso-style-name:hoenzb;}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-family:"Calibri","sans-serif";}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="ZH-CN" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">Thanks for your comments, see my reply below, thanks.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">Thanks<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">Wan Xiaofei<o:p></o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Chandler Carruth [mailto:chandlerc@google.com]
<br>
<b>Sent:</b> Tuesday, July 16, 2013 6:47 PM<br>
<b>To:</b> Wan, Xiaofei<br>
<b>Cc:</b> LLVM Developers Mailing List (llvmdev@cs.uiuc.edu)<br>
<b>Subject:</b> Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM backend code generation<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US">While I think the end goal you're describing is close to the correct one, I see the high-level strategy for getting there somewhat differently:<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">1) The code generators are only one collection of function passes that might be parallelized. Many others might also be parallelized profitably. The design for parallelism within LLVM's pass management infrastructure
 should be sufficiently generic to express all of these use cases.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">[xiaofei], yes, only passes in function pass manager are parallelized, it is enough to meet our requirement since 95% of time in llc are in function passes.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">2) The idea of having multiple pass managers necessitates (unless I misunderstand) duplicating a fair amount of state. For example, the caches in immutable analysis passes would no longer be shared, etc. I think that
 is really unfortunate, and would prefer instead to use parallelizing pass managers that are in fact responsible for the scheduling of passes.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">[ Xiaofei ] For
</span><span lang="EN-US">immutable passes, they are not parallelized, actually, only passes in function pass manager are parallelized<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">The reason why I start multiple pass manager is, make original code infrastructure stable, each thread has its own PM, then consume functions independently.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">3) It doesn't provide a strategy for parallelizing the leaves of a CGSCC pass manager which is where a significant portion of the potential parallelism is available within the middle end.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">4) It doesn't deal with the (numerous) parts of LLVM that are not actually thread safe today. They may happen to work with the code generators you're happening to test, but there is no guarantee. Notable things to think
 about here are computing new types, the use-def lists of globals, commandline flags, and static state variables. While our intent has been to avoid problems with the last two that could preclude parallelism, it seems unlikely that we have succeeded without
 thorough testing to this point. Instead, I fear we have leaned heavily on the crutch of one-thread-per-LLVMContext.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">[Xiaofei] we consider all the aspects you are listing, otherwise, it can’t pass any test cases, now we could pass all benchmarks and almost all unit test cases especial cases.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">5) It adds more complexity onto the poorly designed pass manager infrastructure. Personally, I think that cleanups to the design and architecture of the pass manager should be prioritized above adding new functionality
 like parallelism. However, so far no one has really had time to do this (including myself). While I would like to have time in the future to do this, as with everything else in OSS, it won't be real until the patches start flowing.<o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-US" style="color:#1F497D">[xiaofei] this feature doesn’t rely on PM too much; it doesn’t need to change PM infrastructure</span><span lang="EN-US"><o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US">On Tue, Jul 16, 2013 at 3:33 AM, Wan, Xiaofei <<a href="mailto:xiaofei.wan@intel.com" target="_blank">xiaofei.wan@intel.com</a>> wrote:<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-US">Hi, community:<br>
<br>
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!<br>
1. Is this idea the proper solution for my requirement<br>
2. This new feature will be enabled by llc -thd=N and has no impact on original llc when -thd=1<br>
3. Can this new feature of llc be accepted by community and merged into LLVM code tree<br>
<br>
Patches<br>
The patch is divided into four separated parts, the all-in-one patch could be found here:<br>
<a href="http://llvm-reviews.chandlerc.com/D1152" target="_blank">http://llvm-reviews.chandlerc.com/D1152</a><br>
<br>
Design<br>
<a href="https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgjY-vhyfySg/edit?usp=sharing" target="_blank">https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgjY-vhyfySg/edit?usp=sharing</a><br>
<br>
<br>
Background<br>
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.<br>
2. Backend code generation is a time-consuming activity happened on target device which makes it an important user experience.<br>
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.<br>
<br>
Overall design strategy and goal<br>
1. Generate totally same binary as what single thread output<br>
2. No impacts on single thread performance & conformance<br>
3. Little impacts on LLVM code infrastructure<br>
<br>
Current status and test result<br>
1. Parallel llc can generate same code as single thread by "objdump -d", it could pass 10 hours stress test for all performance benchmark<br>
2. Parallel llc can introduce ~2.9X performance gain on XEON sever for 4 threads<br>
<br>
<br>
Thanks<br>
<span class="hoenzb"><span style="color:#888888">Wan Xiaofei</span></span><span style="color:#888888"><br>
</span><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><o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
</div>
</body>
</html>