Diff Graphs for a fast Incremental Pointer Analysis
Krainz J, Philippsen M (2017)
Publication Language: English
Publication Status: Accepted
Publication Type: Conference contribution, Original article
Future Publication Type: Conference contribution
Publication year: 2017
Publisher: ACM DL
Edited Volumes: Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS 2017)
Conference Proceedings Title: Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'17)
Event location: Barcelona
ISBN: 978-1-4503-5088-4
Abstract
A wide range of optimizations and program analyses, including bug finding by means of escape or race analyses, need accurate pointer information. Since accuracy takes time, there is a need for a fast incremental pointer analysis that re-uses prior results and only re-analyzes program changes and their effects instead of the whole program.
We present such an incremental pointer analysis that employs novel diff graphs to represent how a method accesses and/or modifies memory. Regardless of the number of call sites, we only need to analyze a method once; the resulting diff-graph is then used at every call site. If a method changes, we re-generate its diff-graph, and (unless its diff-graph stays the same) its callers' diff graphs, and so on.
Our algorithm is flow sensitive and context insensitive, does not leak information between call sites, can perform strong updates (even for method calls), and is fast (14 000 LOC with 25 000 bytecode instructions in 3 minutes). When used incrementally for each of the commits of an open-source software repository our incremental approach derives more precise pointer information than established (full) analyses like Spark -- albeit in about the same time.
Authors with CRIS profile
Jakob Krainz
Lehrstuhl für Informatik 2 (Programmiersysteme)
Michael Philippsen
Lehrstuhl für Informatik 2 (Programmiersysteme)
How to cite
APA:
Krainz, J., & Philippsen, M. (2017). Diff Graphs for a fast Incremental Pointer Analysis. In ACM (Eds.), Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'17). Barcelona, ES: ACM DL.
MLA:
Krainz, Jakob, and Michael Philippsen. "Diff Graphs for a fast Incremental Pointer Analysis." Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS 2017), Barcelona Ed. ACM, ACM DL, 2017.
BibTeX: Download