<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" class="">mehdi.amini@apple.com</a>> 於 2016年11月30日 上午11:23 寫道：</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Nov 29, 2016, at 6:55 PM, Bekket McClane <<a href="mailto:bekket.mcclane@gmail.com" class="">bekket.mcclane@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" class="">mehdi.amini@apple.com</a>> 於 2016年11月30日 上午9:50 寫道：</div><br class="Apple-interchange-newline"><div class=""><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class="Apple-interchange-newline">On Nov 29, 2016, at 5:22 PM, Bekket McClane <<a href="mailto:bekket.mcclane@gmail.com" class="">bekket.mcclane@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br class=""><div class=""><blockquote type="cite" class=""><div class="">Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" class="">mehdi.amini@apple.com</a>> 於 2016年11月30日 上午5:14 寫道：</div><br class="Apple-interchange-newline"><div class=""><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class="Apple-interchange-newline">On Nov 29, 2016, at 4:02 AM, Bekket McClane via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hi,<div class="">Though there exists lots of researches on parallelizing or scheduling optimization passes, If you open up the time matrices of codegen(llc -time-passes), you'll find that the most time consuming task is actually instruction selection(40~50% of time) instead of optimization passes(10~0%). That's why we're trying to parallelize the (target-independent) instruction selection process in aid of JIT compilation speed.</div></div></div></blockquote><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">How much of this 40-50% is spent in the matcher table? I though most of the overhead was inherent to SelectionDAG?</div></div></blockquote><div class=""><br class=""></div><div class="">Do you mean DAG operations like adding SDNode to CSENodes? Could you talk a little bit more?</div></div></div></div></blockquote><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Yes: building the DAG and mutating the DAG (performing the combine/legalize stage, with continuous CSE).</div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">What does your profile show? Do you have some example IR out of your frontend that I could process with opt/llc and profile? </div></div></blockquote><div class=""><br class=""></div><div class="">The “large” one, to simulate the scenario that someone just want to speed up the building speed of a large project instead of JIT usages:</div><div class=""></div></div><span id="cid:F4C06642-0E91-446F-A588-7D475E4DDE6A@apple.com" class=""><Task.ll></span><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""></div><div class=""><br class=""></div><div class="">The normal one, from one of the test cases in LLVM, to simulate JIT compilation usage:</div></div><span id="cid:057183EF-ED96-47DA-93C1-4AD2B998B858@apple.com" class=""><zlib-longest-match.ll></span></div></blockquote><div class=""><br class=""></div><div class="">If I run: " clang -march=x86-64 zlib-longest-match.ll -mllvm -time-passes -c -O2” on this I get this top 5:</div><div class=""><br class=""></div><div class=""> Total Execution Time: 0.1896 seconds (0.2101 wall clock)<br class=""><br class=""> ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---<br class=""> 0.0024 ( 18.4%) 0.0450 ( 25.4%) 0.0473 ( 25.0%) 0.0536 ( 25.5%) X86 DAG->DAG Instruction Selection<br class=""> 0.0005 ( 4.1%) 0.0192 ( 10.8%) 0.0197 ( 10.4%) 0.0226 ( 10.8%) Combine redundant instructions<br class=""> 0.0010 ( 7.7%) 0.0128 ( 7.2%) 0.0138 ( 7.3%) 0.0144 ( 6.9%) Induction Variable Simplification<br class=""> 0.0011 ( 8.7%) 0.0101 ( 5.7%) 0.0112 ( 5.9%) 0.0116 ( 5.5%) Loop Strength Reduction<br class=""> 0.0002 ( 1.3%) 0.0083 ( 4.7%) 0.0085 ( 4.5%) 0.0101 ( 4.8%) Early CSE<br class=""><br class=""></div><div class="">And the DAG detail is:</div><div class=""><br class=""></div><div class=""> 0.0004 ( 22.6%) 0.0137 ( 39.4%) 0.0141 ( 38.6%) 0.0168 ( 40.3%) DAG Combining 1<br class=""> 0.0003 ( 18.8%) 0.0106 ( 30.6%) 0.0109 ( 30.0%) 0.0118 ( 28.1%) Instruction Selection<br class=""> 0.0002 ( 14.6%) 0.0022 ( 6.4%) 0.0025 ( 6.8%) 0.0034 ( 8.1%) Instruction Scheduling<br class=""> 0.0001 ( 8.2%) 0.0027 ( 7.9%) 0.0029 ( 7.9%) 0.0033 ( 7.9%) DAG Legalization<br class=""> 0.0001 ( 8.0%) 0.0026 ( 7.6%) 0.0028 ( 7.6%) 0.0032 ( 7.7%) Type Legalization<br class=""><br class=""></div><div class=""><br class=""></div><div class="">The -time-passes option is nice, but I like to look at the profiler better in general, so I ran a profiler (Instruments) on the backend only (without running the optimizer!) using: llc -march=x86-64 zlib-longest-match.ll -O2 -time-passes -disable-verify -time-compilations 100</div><div class="">(It will repeat the codegen 100 times which helps getting enough runtime to have a meaningful profile) </div><div class=""><br class=""></div><div class="">I get (focusing on the “Instruction Selection” part:</div><div class=""><br class=""></div><div class=""><div class="">Running Time<span class="Apple-tab-span" style="white-space:pre"> </span>Self (ms)<span class="Apple-tab-span" style="white-space:pre"> </span>Symbol Name</div><div class="">20.5ms 3.2%<span class="Apple-tab-span" style="white-space:pre"> </span>0.2<span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span> llvm::SelectionDAGISel::DoInstructionSelection()</div><div class="">18.9ms 3.0%<span class="Apple-tab-span" style="white-space:pre"> </span>0.5<span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span> (anonymous namespace)::X86DAGToDAGISel::Select(llvm::SDNode*)</div><div class="">17.7ms 2.8%<span class="Apple-tab-span" style="white-space:pre"> </span>6.9<span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span> llvm::SelectionDAGISel::SelectCodeCommon(llvm::SDNode*, unsigned char const*, unsigned int)</div><div class="">3.9ms 0.6%<span class="Apple-tab-span" style="white-space:pre"> </span>0.4<span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span> (anonymous namespace)::X86DAGToDAGISel::CheckComplexPattern(llvm::SDNode*, llvm::SDNode*, llvm::SDValue, unsigned int, llvm::SmallVectorImpl<std::__1::pair<llvm::SDValue, llvm::SDNode*> >&)</div><div class=""><br class=""></div></div><div class=""><br class=""></div><div class="">Note that the percentage if with respect to the total time, so it seems to me that you’re trying to parallelize a function that takes ~3% of the backend, which doesn’t play well with Amdahl.</div></div></div></div></blockquote><div><br class=""></div><div>Cheers! Thanks for the profiling</div><div>I even don’t know the -time-compilations options. </div><div>We’ll verify our assumption again.</div><div><br class=""></div>B.R.</div><div>McClane<br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Best,</div><div class=""><br class=""></div><div class="">— </div><div class="">Mehdi</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Also why having such a fine grain approach instead of trying to perform instruction selection in parallel across basic blocks or functions?</div></div></blockquote><div class=""><br class=""></div><div class="">JIT compilation tends to compile small amount of DAG nodes each time, and also, most of the JIT strategies tend to merge several instructions(e.g. all of the hot instructions) into single basic block or function, so I guess it wouldn’t get significant speedup on overall performance if we handle only one(or few) compilation unit each time.(correct me if I'm wrong)</div></div></div></div></blockquote><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">If you have one function and a very small IR as you seem to indicate here, I wouldn’t expect parallelizing the matcher table to be worthwhile (I’d like to see a profile…).</div></div></blockquote><div class=""><br class=""></div><div class="">The reason why we suspect MatcherTable to be the bottleneck is that there might be chances that though a program has few DAG nodes, each of those nodes' selection “path” in MatcherTable is long(i.e. Failed in many OPC_Scope). So the overall selection time won’t necessarily be linear to the amount of DAG nodes. But indeed, we haven’t do fine profiling to confirm our assumption. </div><div class=""><br class=""></div><div class="">Also, the builtin time profiler(llc -time-passes) has indicated that the "real instruction selector” part, where MatcherTable acts as the main role, is also the most time consuming part among other instruction selection procedures like DAG combiner and legalizer.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">I rather think that if the matcher table is high on the profile, a “PGO" approach as suggested by Nicolai is likely to help the most.</div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Also, you should really measure the difference on the generated code between fast-isel and SelectionDAG, as in practice it may not be that high for the kind of IR you have. Sometimes, we’ve seen fast-isel even gets better generated code by matching pattern across basic blocks.</div></div></blockquote><div class=""><br class=""></div><div class="">We haven’t performed a deep profiling on fast-isel. Thanks for the information.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="">— </div><div class="">Mehdi</div><div class=""><br class=""></div></div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><br class=""></div>B.R.</div><div class="">McClane<br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">I suspect you won’t gain much for too much added complexity with this approach.</div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">— </div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Mehdi</div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">The instruction selector of LLVM is an interpreter that interpret the MatcherTable which consists of bytecodes generated by TableGen. I'm surprised to find that the structure of MatcherTable and the interpreter seems to be suitable for parallelization. So we propose a prototype that parallelizes the interpreting of OPC_Scope children that are possibly time-consuming. Here is some quick overview:</div><div class=""><br class=""></div><div class="">We add two new opcodes: OPC_Fork and OPC_Merge. During DAG optimization process(utils/TableGen/<wbr class="">DAGISelMatcherOpt.cpp). OPC_Fork would be added to the front of scope(OPC_Scope) children which fulfill following conditions:</div><div class="">1. Amount of opcodes within the child exceed certain threshold(5 in current prototype).</div><div class="">2. The child is reside in a sequence of continuous scope children which length also exceed certain threshold(7 in current prototype).</div><div class="">For each valid sequence of scope children, an extra scope child, where OPC_Merge is the only opcode, would be appended to it(the sequence). </div><div class=""><br class=""></div><div class="">In the interpreter, when an OPC_Fork is encountered inside a scope child, the main thread would dispatch the scope child as a task to a central thread pool, then jump to the next child. At the end of a valid "parallel sequence(of scope children)" an OPC_Merge must exist and the main thread would stop there and wait other threads to finish. <br clear="all" class=""><div class=""><br class=""></div><div class="">About the synchronization, read-write lock is mainly used: In each checking-style opcode(e.g. OPC_CheckSame, OPC_CheckType, except OPC_CheckComplexPat) handlers, a read lock is used, otherwise, a write lock is used. </div><div class=""><br class=""></div><div class="">Finally, although the generated code is correct, total consuming time barely break even with the original one. Possible reasons may be:</div><div class="">1. The original interpreter is pretty fast actually. The thread pool dispatching time for each selection task may be too long in comparison with the original approach.</div><div class="">2. X86 is the only architecture which contains OPC_CheckComplexPat that would modify DAG. This constraint force us to add write lock on it which would block other threads at the same time. Unfortunately, OPC_CheckComplexPat is probably the most time-consuming opcodes in X86 and perhaps in other architectures, too.</div><div class="">3. Too many threads. We're now working on another approach that use larger region, consist of multiple scope children, for each parallel task for the sake of reducing thread amount. </div><div class="">4. Popular instructions, like add or sub, contain lots of scope children so one or several parallel regions exist. However, most of the common instruction variants(e.g. add %reg1, %reg2) is on "top" among scope children which would be encountered pretty early. So sometimes threads are fired, but the correct instruction is actually immediately selected after that. Thus lots of time is wasted on joining threads. </div><div class=""><br class=""></div><div class="">Here is our working repository and diff with 3.9 release: <a href="https://bitbucket.org/mshockwave/hydra-llvm/branches/compare/master%0D3.9-origin#diff" target="_blank" class="">https://bitbucket.<wbr class="">org/mshockwave/hydra-llvm/<wbr class="">branches/compare/master%0D3.9-<wbr class="">origin#diff </a></div><div class="">I don't think the current state is ready for code reviewing since there is no significant speedup. But it's very welcome for folks to discuss about this idea and also, whether current instruction selection approach had reached its upper bound of speed.(I ignore fast-isel by mean since it sacrifices too much on quality of generated code. One of our goals is to boost the compilation speed while keeping the code quality as much as possible)</div><div class=""><br class=""></div><div class="">Feel free to comment directly on the repo diff above.</div><div class=""><br class=""></div><div class="">About the "region approach" mentioned in the third item of possible reasons above. It's actually the "dev-region-parallel" branch, but it still has some bugs on correctness of generated code. I would put more detail about it if the feedback is sound.</div><div class=""><br class=""></div><div class="">NOTE: There seems to be some serious bugs in concurrent and synchronization library of old gcc/standard libraries. So it's strongly recommended to use the latest version of clang to build our work.</div><div class=""><br class=""></div><div class="">B.R</div>--<span class="Apple-converted-space"> </span><br class=""><div class="m_-289937573853035298gmail-m_-4541007648684868004gmail_signature"><div dir="ltr" class="">Bekket McClane<div class="">Department of Computer Science,</div><div class="">National Tsing Hua University</div></div></div></div></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div></blockquote></div></div></div></blockquote></div></blockquote></div></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""></body></html>