[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 [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.

Pratik Bhatu

Bachelors of Technology, 3rd Year
Computer Science and Engineering
IIT Hyderabad
+91 961 905 6833

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

Just FYI:
It has never been contributed to GCC.
Versions were written *for GCC*, but they were *not* efficient.