一句话：提出饱和度机制，使基于类型的上下文不敏感指向分析在保持大部分精度的同时达到 RTA 的可扩展性。
整程序静态分析必须在精度与可扩展性之间权衡。上下文不敏感的指向分析常被视为较好折中，但其非线性复杂度使大型应用分析难以扩展；RTA 虽可扩展却精度不足。本文在基于类型的上下文不敏感指向分析中引入饱和度：分析只传播较小的指向集，当某变量可能拥有的值超过给定阈值时，将该变量及其所有使用视为饱和并停止继续分析。作者在 GraalVM Native Image 的指向分析中实现该技术。结果表明，饱和度使 Native Image 能在不到两分钟内分析包含数十万个方法的大型 Java 应用，同时保留指向分析的大部分精度。
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{paperbot2511,
title = {Scaling Type-Based Points-to Analysis with Saturation},
author = {Christian Wimmer and Codrut Stancu and David Kozak and Thomas Würthinger},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656417}
}