Detail publikačního výsledku

Scaling Type-Based Points-to Analysis with Saturation

WIMMER, C.; STANCU, C.; KOZÁK, D.; WUERTHINGER, T.

Originální název

Scaling Type-Based Points-to Analysis with Saturation

Anglický název

Scaling Type-Based Points-to Analysis with Saturation

Druh

Článek WoS

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

points-to analysis, static analysis, pointer analysis, Java, GraalVM

Klíčová slova v angličtině

points-to analysis, static analysis, pointer analysis, Java, GraalVM

Autoři

WIMMER, C.; STANCU, C.; KOZÁK, D.; WUERTHINGER, T.

Rok RIV

2025

Vydáno

24.04.2024

Nakladatel

ACM

Místo

New York

Kniha

Proceedings of the ACM on Programming Languages

ISSN

2475-1421

Periodikum

Proceedings of the ACM on Programming Languages-PACMPL

Svazek

8

Číslo

PLDI

Stát

Spojené státy americké

Strany od

990

Strany do

1013

Strany počet

24

URL

https://dl.acm.org/doi/pdf/10.1145/3656417

Plný text v Digitální knihovně

http://hdl.handle.net/11012/252836

BibTex

@article{BUT189291,
  author="Christian {Wimmer} and Condrut {Stancu} and David {Kozák} and Thomas {Wuerthinger}",
  title="Scaling Type-Based Points-to Analysis with Saturation",
  journal="Proceedings of the ACM on Programming Languages-PACMPL",
  year="2024",
  volume="8",
  number="PLDI",
  pages="990--1013",
  doi="10.1145/3656417",
  url="https://dl.acm.org/doi/pdf/10.1145/3656417"
}

Dokumenty

3656417