[LLVMdev] [GSoc] Liveness Based Flow Sensitive Pointer Analysis for GSoc 2015

[John Criswell]

On 3/10/15 7:25 AM, Rahul Jain wrote:
>
> This landed in my spam folder so resending it to the list!
>

My first question is, "What is to be gained from the extra precision?"  
Will this help some optimization that already exists within LLVM?  Will 
it help optimize memory safety checks by finding more type-safe memory 
objects (ala SAFECode)?  Will it enable outside projects to build better 
static analysis and debugging tools?

Different uses of points-to/alias analysis place different constraints 
on the precision/performance tradeoff.  The intended use also changes 
the interface (some interfaces just want alias pairs while others want a 
points-to/shape graph).

A strong proposal for an alias analysis project should communicate the 
intended use of the alias analysis, why that intended use is useful, and 
why the extra precision is needed.

Regards,

John Criswell


> On Mar 10, 2015 2:12 PM, "Pratik Bhatu" <cs12b1010 at iith.ac.in 
> <mailto:cs12b1010 at iith.ac.in>> wrote:
>
>     Hi all,
>
>     I'm a 3rd year CSE B.Tech student and have been studying LLVM
>     since the past year. I have written a pass for doing register
>     allocation as part of my course project and have also been
>     studying LLVM code sections related to SSA construction, dominance
>     frontiers,etc. I also made some contributions to the Polly project.
>
>     Currently I am interested in improving the existing alias analysis
>     infrastructure as part of my GSoC-15 project. The current pointer
>     analyses in LLVM (basicaa, cflaa etc.) compute imprecise
>     information as none of them are flow-sensitive. The aim of my
>     project is to implement a pass that computes more precise
>     points-to pairs that is both flow-sensitive as well as
>     context-sensitive. This method has been described in
>     Liveness-Based Pointer Analysis [1] and has already been
>     implemented in the GCC compiler.
>
>     Most of the information in traditional context-sensitive
>     algorithms is useless because it involves variables that are dead.
>     The paper however relies on liveness information at the
>     construction time of points-to-sets to prune the useless
>     information. This method makes it comparable to a
>     context-insensitive algorithm in cost.
>
>     This would be an inter-procedural pass and would be implemented in
>     the existing AliasAnalysis infrastructure by implementing  all the
>     methods of AliasAnalysis class similar to the existing alias
>     analysis passes in LLVM like basicaa and CFL-AA. I am looking for
>     feedback and on directions on how to proceed with this.
>
>     [1] Uday P. Khedker, Alan Mycroft, and Prashant Singh Rawat. 2012.
>     “Liveness-Based pointer analysis”. In Proceedings of the 19th
>     international conference on Static Analysis (SAS'12), Antoine Miné
>     and David Schmidt (Eds.). Springer-Verlag, Berlin, Heidelberg,
>     265-282.
>
>
>     Regards
>     Pratik Bhatu
>     Bachelors of Technology, 3rd Year
>     Computer Science and Engineering
>     IIT Hyderabad
>     +91 961 905 6833
>
>     _______________________________________________
>     LLVM Developers mailing list
>     LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>
>     http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> _______________________________________________
> 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/20150310/ea9b2cfa/attachment.html>