Скачать или смотреть [PLDI24] Scaling Type-Based Points-to Analysis with Saturation

Scaling Type-Based Points-to Analysis with Saturation (Video, PLDI 2024)
Christian Wimmer, Codrut Stancu, David Kozak, and Thomas Würthinger
(Oracle Labs, USA; Oracle Labs, Switzerland; Brno University of Technology, Czechia / Oracle Labs, Czechia; Oracle Labs, Switzerland)

Abstract: Designing a whole-program static analysis requires trade-offs between precision and scalability. While a context-insensitive points-to analysis is often considered a good compromise, it still has non-linear complexity that leads to scalability problems when analyzing large applications. On the other hand, rapid type analysis scales well but lacks precision. We use saturation in a context-insensitive type-based points-to analysis to make it as scalable as a rapid type analysis, while preserving most of the precision of the points-to analysis. With saturation, the points-to analysis only propagates small points-to sets for variables. If a variable can have more values than a certain threshold, the variable and all its usages are considered saturated and no longer analyzed. Our implementation in the points-to analysis of GraalVM Native Image, a closed-world approach to build standalone binaries for Java applications, shows that saturation allows GraalVM Native Image to analyze large Java applications with hundreds of thousands of methods in less than two ‍minutes.

Article: https://doi.org/10.1145/3656417

Supplementary archive: https://doi.org/10.5281/zenodo.10961908 (Badges: Artifacts Available, Artifacts Evaluated — Reusable)

ORCID: https://orcid.org/0009-0003-3213-9306, https://orcid.org/0009-0007-3646-3663, https://orcid.org/0000-0002-8846-922X, https://orcid.org/0009-0007-0441-5173

Video Tags: points-to analysis, static analysis, pointer analysis, Java, GraalVM, pldi24main-p251-p, doi:10.1145/3656417, doi:10.5281/zenodo.10961908, orcid:0009-0003-3213-9306, orcid:0009-0007-3646-3663, orcid:0000-0002-8846-922X, orcid:0009-0007-0441-5173, Artifacts Available, Artifacts Evaluated — Reusable

Presentation at the PLDI 2024 conference, June 24–28, 2024, https://pldi24.sigplan.org/
Sponsored by ACM SIGPLAN,