SkipFlow: Improving the Precision of Points-to Analysis Using
Primitive Values and Predicate Edges

D 2025

SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges

KOZÁK, David; Codrut STANCU; Tomáš VOJNAR a Christian WIMMER

Základní údaje

Originální název

SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges

Autoři

KOZÁK, David; Codrut STANCU; Tomáš VOJNAR a Christian WIMMER

Vydání

Las Vegas, Proc. of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization – CGO'25, od s. 347-361, 15 s. 2025

Nakladatel

ACM/IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

Publisher's version, Associated technical report

Organizační jednotka

Fakulta informatiky

ISBN

979-8-4007-1275-3

DOI

https://doi.org/10.1145/3696443.3708932

EID Scopus

2-s2.0-105001152841

Klíčová slova anglicky

points-to analysis;static analysis;pointer analysis;compiler;optimization;

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 14. 8. 2025 18:05, prof. Ing. Tomáš Vojnar, Ph.D.

Anotace

V originále

A typical points-to analysis such as Andersen’s or Steensgaard’s may lose precision because it ignores the branching structure of the analyzed program. Moreover, points-to analysis typically focuses on objects only, not considering instructions manipulating primitive values. We argue that such an approach leads to an unnecessary precision loss, for example, when primitive constants true and false flow out of method calls. We propose a novel lightweight points-to analysis called SkipFlow that interprocedurally tracks the flow of both primitives and objects, and explicitly captures the branching structure of the code using predicate edges. At the same time, however, SkipFlow is as lightweight and scalable as possible, unlike a traditional flow-sensitive analysis. We apply SkipFlow to GraalVM Native Image, a closed-world solution to building standalone binaries for Java applications. We evaluate the implementation using a set of microservice applications as well as well-known benchmark suites. We show that SkipFlow reduces the size of the application in terms of reachable methods by 9% on average without significantly increasing the analysis time.

Návaznosti

GA23-06506S, projekt VaV

Název: Pokročilá analýza a verifikace pro pokročilý software

Investor: Grantová agentura ČR, Pokročilá analýza a verifikace pro pokročilý software

Citovat

KOZÁK, David; Codrut STANCU; Tomáš VOJNAR a Christian WIMMER. SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges. Online. In Proc. of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization – CGO'25. Las Vegas: ACM/IEEE, 2025, s. 347-361. ISBN 979-8-4007-1275-3. Dostupné z: https://doi.org/10.1145/3696443.3708932.

@inproceedings{2512083,
   author = {Kozák, David and Stancu, Codrut and Vojnar, Tomáš and Wimmer, Christian},
   address = {Las Vegas},
   booktitle = {Proc. of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization – CGO'25},
   doi = {https://doi.org/10.1145/3696443.3708932},
   keywords = {points-to analysis;static analysis;pointer analysis;compiler;optimization;},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Las Vegas},
   isbn = {979-8-4007-1275-3},
   pages = {347-361},
   publisher = {ACM/IEEE},
   title = {SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges},
   url = {https://dl.acm.org/doi/10.1145/3696443.3708932},
   year = {2025}
}

TY  - CONF
ID  - 2512083
AU  - Kozák, David - Stancu, Codrut - Vojnar, Tomáš - Wimmer, Christian
PY  - 2025
TI  - SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges
PB  - ACM/IEEE
CY  - Las Vegas
SN  - 9798400712753
KW  - points-to analysis;static analysis;pointer analysis;compiler;optimization;
UR  - https://dl.acm.org/doi/10.1145/3696443.3708932
N2  - A typical points-to analysis such as Andersen’s or Steensgaard’s may lose precision because it ignores the branching structure of the analyzed program. Moreover, points-to analysis typically focuses on objects only, not considering instructions manipulating primitive values. We argue that such an approach leads to an unnecessary precision loss, for example, when primitive constants true and false flow out of method calls. We propose a novel lightweight points-to analysis called SkipFlow that interprocedurally tracks the flow of both primitives and objects, and explicitly captures the branching structure of the code using predicate edges. At the same time, however, SkipFlow is as lightweight and scalable as possible, unlike a traditional flow-sensitive analysis. We apply SkipFlow to GraalVM Native Image, a closed-world solution to building standalone binaries for Java applications. We evaluate the implementation using a set of microservice applications as well as well-known benchmark suites. We show that SkipFlow reduces the size of the application in terms of reachable methods by 9% on average without significantly increasing the analysis time.
ER  -

KOZÁK, David; Codrut STANCU; Tomáš VOJNAR a Christian WIMMER. SkipFlow: Improving the Precision of Points-to Analysis Using Primitive Values and Predicate Edges. Online. In \textit{Proc. of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization – CGO'25}. Las Vegas: ACM/IEEE, 2025, s.~347-361. ISBN~979-8-4007-1275-3. Dostupné z: https://doi.org/10.1145/3696443.3708932.

Přehled o publikaci