llvm dev - Mar 2015 - [LLVMdev] Implementing if-conversion as a GSoC 2015 project?

Hi,

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?

Best,

Xiang Gao
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150316/9fddc0db/attachment.html>

Dear Xiang,

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.

Regards,

John Criswell

On 3/16/15 4:23 PM, Xiang Gao wrote:
> Hi,
>
> 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?
>
> Best,
>
> Xiang Gao
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150318/4ddef5e4/attachment.html>

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 [Scott
A. Mahlke et al 1992]
<http://www.eecs.umich.edu/eecs/about/articles/2015/p45-mahlke.pdf>, 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.

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:
if (<a>) {
   execute 1000 statements
} else {
   execute 1 statements
}
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.

There are studies on how to make a balance in whether to do if-conversion
or not. There are both static policy [David I. August et al 1997]
<http://impact.crhc.illinois.edu/shared/papers/micro-97-framework.pdf> and
dynamic policy [Kim M. Hazelwood and Thomas Conte 2000]
<http://www.cs.virginia.edu/kim/docs/pact00.pdf>. What I want to do for
GSoC is to implement these approaches into LLVM.

Xiang Gao

2015-03-17 18:14 GMT-04:00 John Criswell <jtcriswel at gmail.com>:
>  Dear Xiang,
>
> 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.
>
> Regards,
>
> John Criswell
>
>
> On 3/16/15 4:23 PM, Xiang Gao wrote:
>
> Hi,
>
>  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?
>
>  Best,
>
>  Xiang Gao
>
>
> _______________________________________________
> LLVM Developers mailing listLLVMdev at cs.uiuc.edu        
http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of
Rochesterhttp://www.cs.rochester.edu/u/criswell
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150318/fc51ee79/attachment.html>