<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></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="">On Mar 18, 2015, at 10:12 AM, Xiang Gao <<a href="mailto:qasdfgtyuiop@gmail.com" class="">qasdfgtyuiop@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">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 <a href="http://www.eecs.umich.edu/eecs/about/articles/2015/p45-mahlke.pdf" class="">[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 class=""></div></div><div>Questions:</div><div><br class=""></div><div>* 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>* What architecture are you targeting? HB makes more sense for ISA with lots of predicated registers.</div><div><br class=""></div><div>Evan</div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">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 class="">if (<a>) {</div><div class=""> execute 1000 statements</div><div class="">} else {</div><div class=""> execute 1 statements</div><div class="">}</div><div class="">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 class=""><br class=""></div><div class="">There are studies on how to make a balance in whether to do if-conversion or not. There are both static policy <a href="http://impact.crhc.illinois.edu/shared/papers/micro-97-framework.pdf" class="">[David I. August et al 1997]</a> and dynamic policy <a href="http://www.cs.virginia.edu/kim/docs/pact00.pdf" class="">[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" class=""><div class=""><div class="gmail_signature">Xiang Gao</div></div>
<br class=""><div class="gmail_quote">2015-03-17 18:14 GMT-04:00 John Criswell <span dir="ltr" class=""><<a href="mailto:jtcriswel@gmail.com" target="_blank" class="">jtcriswel@gmail.com</a>></span>:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000" class="">
<div class="">Dear Xiang,<br class="">
<br class="">
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 class="">
<br class="">
Regards,<br class="">
<br class="">
John Criswell<div class=""><div class="h5"><br class="">
<br class="">
On 3/16/15 4:23 PM, Xiang Gao wrote:<br class="">
</div></div></div>
<blockquote type="cite" class=""><div class=""><div class="h5">
<div dir="ltr" class="">Hi,
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">Best,</div>
<div class=""><br class="">
<div class="">
<div class="">Xiang Gao</div>
</div>
</div>
</div>
<br class="">
<fieldset class=""></fieldset>
<br class="">
</div></div><pre class="">_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><span class="HOEnZb"><font color="#888888" class="">
</font></span></pre><span class="HOEnZb"><font color="#888888" class="">
</font></span></blockquote><span class="HOEnZb"><font color="#888888" class="">
<br class="">
<br class="">
<pre cols="72" class="">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank" class="">http://www.cs.rochester.edu/u/criswell</a></pre>
</font></span></div>
</blockquote></div><br class=""></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class=""></div></blockquote></div><br class=""></body></html>