Pratik Bhatu
2015-Mar-10 08:40 UTC
[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>
Rahul Jain
2015-Mar-10 11:25 UTC
[LLVMdev] [GSoc] Liveness Based Flow Sensitive Pointer Analysis for GSoc 2015
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>
John Criswell
2015-Mar-10 14:07 UTC
[LLVMdev] [GSoc] Liveness Based Flow Sensitive Pointer Analysis for GSoc 2015
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>
Daniel Berlin
2015-Mar-10 16:16 UTC
[LLVMdev] [GSoc] Liveness Based Flow Sensitive Pointer Analysis for GSoc 2015
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>