llvm dev - Mar 2015 - [LLVMdev] [GSoc] Liveness Based Flow Sensitive Pointer Analysis for GSoc 2015

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 [http://www.cse.iitb.ac.in/grc/software/livepta.pdf] [1] and has
already been implemented in the GCC compiler
[http://www.cse.iitb.ac.in/grc/index.php?page=l-fcpa].

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150310/5ec76d16/attachment.html>

This landed in my spam folder so resending it to the list!
On Mar 10, 2015 2:12 PM, "Pratik Bhatu" <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         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150310/7e0054c5/attachment.html>

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>

On Tue, Mar 10, 2015 at 4:25 AM, Rahul Jain <1989.rahuljain at gmail.com>
wrote:
> This landed in my spam folder so resending it to the list!
> On Mar 10, 2015 2:12 PM, "Pratik Bhatu" <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.
>>
>
Just FYI:
It has never been contributed to GCC.
Versions were written *for GCC*, but they were *not* efficient.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150310/47c1fd50/attachment.html>