<div dir="ltr"><p>When dealing with if-conversion, there are two problems: the first is how to do if-conversion, the second is how to use if-conversion to make the code generated faster. When talking about the first problem, we think nothing about how if-conversion is going to be used.</p><p><br></p><p>The way that LLVM deal with the first problem is to consider the case of triangle, diamond, etc. This approach is not complete, i.e. there are cases this approach can't deal with. A better way to do is the RK algorithm<a href="http://perso.ens-lyon.fr/christophe.alias/M2/HPL-91-58.pdf">[Park 1992]</a>, which can deal convert any control flow graph without loop into a single basic block and "minimize both the number of predicates in use and the of defining operations necessary". Figure 1 of Park paper is one example that LLVM's algorithm can't deal with but the RK algorithm can. Replacing the current algorithm with RK algorithm benefits everywhere when if-conversion is used, including vectorization.</p><p dir="ltr"><br></p><p dir="ltr">For the second problem, if-conversion might improve efficiency in the following ways:</p><p dir="ltr">First, if-conversion can merge several basic block into one large basic block, then global scheduling problem reduces to a local scheduling problem. Actually there are approaches that take advantage of this feature of if-conversion to do global scheduling <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2910" target="_blank">[NJ Water 1993]</a>. I have no idea about how much improvements implementing if-conversion into it will make.</p><p>Second, properly using if-conversion can avoid punishment of failing to predict the branching. As Gerolf says, the improvement of branch predictor and global scheduler might make it not as attractive as in literature.</p><p>Third, if-conversion makes it possible to vectorize loops with branching inside. The vectorization has already been implemented in LLVM, so the benefit will be the benefit of RK algorithm.</p><p>Unfortunately I don't have any specific example yet. Benchmark can't be done before it is implemented. If unluckily the benchmark shows almost no improvement, all the work done to implement this part then becomes useless. </p><p dir="ltr"><br></p><p>What I plan to do is:</p><p></p><ol><li>Replace the algorithm of if-conversion with RK algorithm.<br></li><li>Adopt the scheduler to handle hyperblock, as Evan says.</li></ol><p></p><p><br></p><p>Answer Evan's question </p><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"><span style="font-size:14px">* What architecture are you targeting? HB makes more sense for ISA with lots of predicated registers.</span></blockquote><p>Good question. The RK algorithm is architecture independent. And for the scheduler, I haven't decided yet. It depends on the time table. I don't know how much time it will take to do the coding, so it's hard to say now. Candidates with priority might be: the one with most predicated registers, the one with poorest branch predictor, and the one that is most widely used. </p><p dir="ltr"><br></p>
<p dir="ltr">Xiang Gao</p>
<div 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"><div style="word-wrap:break-word"><div><br></div><br><div><br></div><div>It would help most if you had key examples/benchmarks where if conversion will provide (additional) performance benefits. Literature is a limited guide. For example, in hindsight many early papers on Itanium oversold the potential benefits - which is not necessarily their fault: branch predictors got better over time, global scheduling techniques improved over time etc. In the specific example of the Mahlke paper if-conversion turned out to improve global scheduling in their compiler. With a better global scheduler the result is different.</div><div><br></div><div>When you scope the design it will be helpful when the pass can be invoked on demand for a region by loop transformations and in the codegen. Specific example where if conversion enables e.g. vectorization or can eliminate targeted data dependent branches (on top of what can be done today) is where I think the benefits will be. The more specific examples you have the less likely you’ll get lost in the morass of compiler changes that get triggered by the ‘advanced’ conversion schemes.</div><div><br></div><div>-Gerolf</div><div><blockquote type="cite"><div>On Mar 18, 2015, at 11:20 AM, Evan Cheng <<a href="mailto:evan.cheng@apple.com" target="_blank">evan.cheng@apple.com</a>> wrote:</div><br><div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><blockquote type="cite"><div><br>On Mar 18, 2015, at 10:12 AM, Xiang Gao <<a href="mailto:qasdfgtyuiop@gmail.com" target="_blank">qasdfgtyuiop@gmail.com</a>> wrote:</div><br><div><div dir="ltr">OK, Let me describe. There is nothing wrong with if-conversion in LLVM. The algorithm implemented in LLVM can handle the if(???){do something} and if(???){do something}else{do something else} case very well. But it can handle complicated case like when there are a lot of gotos in the program. The more systematic way to do if-conversion is based on Hyperblock<span> </span><a href="http://www.eecs.umich.edu/eecs/about/articles/2015/p45-mahlke.pdf" target="_blank">[Scott A. Mahlke et al 1992]</a>, which is set of basic blocks with one entrance and one or more exits. The algorithms now implemented in LLVM is very easy to understand, and very easy to implement. But it is not general, and it might not generate code with best efficient.</div></div></blockquote><div><br></div></div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">Questions:</div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">* You are not going to get good performance out of hyperblock without global scheduling. Are you planning to adopt the MI schedule to handle HB? Will it be predicate aware?</div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">* What architecture are you targeting? HB makes more sense for ISA with lots of predicated registers.</div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">Evan</div><div style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>As we know, if-conversion is a double-edged sword, it might increase the efficiency, it might also make it worse. For example, if the program to be compiled have a code like:</div><div>if (<a>) {</div><div> execute 1000 statements</div><div>} else {</div><div> execute 1 statements</div><div>}</div><div>In the case when <a> is almost always true, it is very efficient because it avoid branching with only executing one more statement as punishment. The improvements of performance from eliminating the branching is always larger than 1 cpu cycle. However, in the case when <a> is almost always false, doing if-conversion is a stupid decision because the improvements of eliminating the branch is very limited here, but the punish, that 1000 more statements have to be executed everytime, really hurt.</div><div><br></div><div>There are studies on how to make a balance in whether to do if-conversion or not. There are both static policy<span> </span><a href="http://impact.crhc.illinois.edu/shared/papers/micro-97-framework.pdf" target="_blank">[David I. August et al 1997]</a><span> </span>and dynamic policy<span> </span><a href="http://www.cs.virginia.edu/kim/docs/pact00.pdf" target="_blank">[Kim M. Hazelwood and Thomas Conte 2000]</a>. What I want to do for GSoC is to implement these approaches into LLVM.</div></div><div class="gmail_extra"><br clear="all"><div><div>Xiang Gao</div></div><br><div class="gmail_quote">2015-03-17 18:14 GMT-04:00 John Criswell<span> </span><span dir="ltr"><<a href="mailto:jtcriswel@gmail.com" target="_blank">jtcriswel@gmail.com</a>></span>:<br><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"><div bgcolor="#FFFFFF" text="#000000"><div>Dear Xiang,<br><br>Can you briefly describe the limitations with the current if-conversion in LLVM and how you plan to improve it? I haven't read your thesis, and I (and others) are unlikely to have time to do so.<br><br>Regards,<br><br>John Criswell<div><div><br><br>On 3/16/15 4:23 PM, Xiang Gao wrote:<br></div></div></div><blockquote type="cite"><div><div><div dir="ltr">Hi,<div><br></div><div>Are you guys interested in implementing if-conversion as a GSoC 2015 project? Last year, I did a literature review about approaches of if-conversion and the if-conversion in LLVM. This was the undergraduate thesis of my bachelor degree. It seems that, the if-conversion used in LLVM is a very simple approach instead of following the literature. So I want to implement the approaches in the literature in LLVM and get support from Google for this. Are you guys interested?</div><div><br></div><div>Best,</div><div><br><div><div>Xiang Gao</div></div></div></div><br><fieldset></fieldset><br></div></div><pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><span><font color="#888888">
</font></span></pre><span><font color="#888888"></font></span></blockquote><span><font color="#888888"><br><br><pre cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank">http://www.cs.rochester.edu/u/criswell</a></pre></font></span></div></blockquote></div><br></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a><span> </span> <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></div></blockquote></div><br style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">_______________________________________________</span><br style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">LLVM Developers mailing list</span><br style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="mailto:LLVMdev@cs.uiuc.edu" style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">LLVMdev@cs.uiuc.edu</a><span style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important"><span> </span> </span><a href="http://llvm.cs.uiuc.edu/" style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://llvm.cs.uiuc.edu</a><br style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family:Helvetica;font-size:18px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></div></blockquote></div><br></div></div>
</div>