llvm dev - Apr 2012 - [LLVMdev] GSoC 2012 Ideas - Alias Analysis

Hi guys,

I'm an undergraduate computer science student and I've been working
with pointer analysis this semester under the orientation of professor
Calvin Lin, at The University of Texas at Austin. I'm interested on
helping to develop LLVM's alias analysis infrastructure. I have two
ideas for a possible proposal and I'd like to know if you have
interest on any of them.

My first idea is to improve LLVM's existing alias analysis
infrastructure. I saw on the open projects page that there are a
couple of things that need to be done on LLVM's Pointer and Alias
Analysis[1]. However, some things seem to be solved
(http://llvm.org/PR1604 and http://llvm.org/PR452) and it made me a
little confused because I don't know exactly what should be addressed
by a possible proposal.

My second idea is to implement a pointer analysis algorithm in LLVM
using Value Flow Graph, as described by the paper "Boosting the
Performance of Flow-sensitive Points-to Analysis using Value Flow"[2].

Thus, I'd like to know whether or not you think improving LLVM's alias
analysis infrastructure using one of those two suggestions would be a
reasonable thing to do as a GSoC.

[1] http://llvm.org/OpenProjects.html#pointeranalysis
[2] http://labs.oracle.com/docs/2011/150-299/2011-0189/esec053-li.pdf

Best,

Douglas

On 3/30/12 7:07 PM, Douglas do Couto Teixeira wrote:
> Hi guys,
>
> I'm an undergraduate computer science student and I've been working
> with pointer analysis this semester under the orientation of professor
> Calvin Lin, at The University of Texas at Austin. I'm interested on
> helping to develop LLVM's alias analysis infrastructure. I have two
> ideas for a possible proposal and I'd like to know if you have
> interest on any of them.
>
> My first idea is to improve LLVM's existing alias analysis
> infrastructure. I saw on the open projects page that there are a
> couple of things that need to be done on LLVM's Pointer and Alias
> Analysis[1]. However, some things seem to be solved
> (http://llvm.org/PR1604 and http://llvm.org/PR452) and it made me a
> little confused because I don't know exactly what should be addressed
> by a possible proposal.
>
> My second idea is to implement a pointer analysis algorithm in LLVM
> using Value Flow Graph, as described by the paper "Boosting the
> Performance of Flow-sensitive Points-to Analysis using Value Flow"[2].
>
> Thus, I'd like to know whether or not you think improving LLVM's
alias
> analysis infrastructure using one of those two suggestions would be a
> reasonable thing to do as a GSoC.
If you want to work on points-to analysis, then you need to have some 
feature which will benefit from using that points-to analysis.  Example 
applications of points-to analysis would be optimization and static 
backwards slicing.

If you write a proposal to work on points-to analysis, then I recommend 
that your proposal also include work on code that will use that 
points-to analysis.  For example, you could implement a points-to 
analysis and then add an AliasAnalysis interface to it so that LLVM 
optimizations can use it without modification.  Alternatively, you could 
implement some new optimization that uses the points-to results from 
your analysis directly.

If you can provide evidence in your proposal that LLVM is missing 
optimization opportunities because of a lack of good points-to analysis, 
that would make your proposal even stronger.

-- John T.
>
> [1] http://llvm.org/OpenProjects.html#pointeranalysis
> [2] http://labs.oracle.com/docs/2011/150-299/2011-0189/esec053-li.pdf
>
> Best,
>
> Douglas
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi John, thanks for your feedback. I'll try to answer your comments bellow.

On Mon, Apr 2, 2012 at 10:59 AM, John Criswell <criswell at illinois.edu>
wrote:
> On 3/30/12 7:07 PM, Douglas do Couto Teixeira wrote:
>>
>> Hi guys,
>>
>> I'm an undergraduate computer science student and I've been
working
>> with pointer analysis this semester under the orientation of professor
>> Calvin Lin, at The University of Texas at Austin. I'm interested on
>> helping to develop LLVM's alias analysis infrastructure. I have two
>> ideas for a possible proposal and I'd like to know if you have
>> interest on any of them.
>>
>> My first idea is to improve LLVM's existing alias analysis
>> infrastructure. I saw on the open projects page that there are a
>> couple of things that need to be done on LLVM's Pointer and Alias
>> Analysis[1]. However, some things seem to be solved
>> (http://llvm.org/PR1604 and http://llvm.org/PR452) and it made me a
>> little confused because I don't know exactly what should be
addressed
>> by a possible proposal.
>>
>> My second idea is to implement a pointer analysis algorithm in LLVM
>> using Value Flow Graph, as described by the paper "Boosting the
>> Performance of Flow-sensitive Points-to Analysis using Value
Flow"[2].
>>
>> Thus, I'd like to know whether or not you think improving
LLVM's alias
>> analysis infrastructure using one of those two suggestions would be a
>> reasonable thing to do as a GSoC.
>
>
> If you want to work on points-to analysis, then you need to have some
> feature which will benefit from using that points-to analysis.  Example
> applications of points-to analysis would be optimization and static
> backwards slicing.
>
I think implementing a program slicer would be doable. We have a
prototype implemented; extending it and porting it to the newer
version of LLVM shouldn't be hard.

As for the optimizations, is there any optimization (maybe a client of
pointer information, maybe not) that you would like to see implemented
in LLVM that is not implemented yet?

I'd like to point out that, although it'd be easier for me working
with pointer analysis, if there is anything that you think has more
priority or is more appealing for the LLVM community, I'd be happy to
give it a try.
> If you write a proposal to work on points-to analysis, then I recommend
that
> your proposal also include work on code that will use that points-to
> analysis.  For example, you could implement a points-to analysis and then
> add an AliasAnalysis interface to it so that LLVM optimizations can use it
> without modification.
Yes, that would be part of the proposal.
>  Alternatively, you could implement some new
> optimization that uses the points-to results from your analysis directly.
>
> If you can provide evidence in your proposal that LLVM is missing
> optimization opportunities because of a lack of good points-to analysis,
> that would make your proposal even stronger.
>
Well, off the top of my head, I can't think of any missing
optimizations related to points-to analysis. However, I'm developing a
study right now to investigate which clients would benefit from a
stronger pointer analysis. There is a famous paper about this "Which
Pointer Analysis Should I Use?" where they conclude that most of the
clients do not need a really strong pointer analysis. However, it has
been 12 years since they developed that study, they only analyzed very
small benchmarks, and they experimented just a few clients. So,
hopefully, we'll be able to find potencial clients that benefit from a
strong pointer analysis.

Douglas
> -- John T.
>
>>
>> [1] http://llvm.org/OpenProjects.html#pointeranalysis
>> [2] http://labs.oracle.com/docs/2011/150-299/2011-0189/esec053-li.pdf
>>
>> Best,
>>
>> Douglas
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>