Cut-Shortcut Whole-Program Pointer Analysis: Re-imagining Context-Sensitivity without Contexts

Over the past decades, context sensitivity has been considered key to improving the precision of whole-program pointer analysis for object-oriented languages such as Java. By analyzing a method under distinct contexts, it separates the static representations of different dynamic instantiations of variables and heap objects, thereby reducing spurious object flows. However, despite its precision benefits, context sensitivity incurs substantial efficiency costs because each method is analyzed multiple times under different contexts. To mitigate this issue, numerous selective context-sensitive approaches have been proposed that apply context sensitivity only to selected methods. However, these approaches do not fully eliminate the efficiency bottleneck because they still rely on the fundamental idea of context sensitivity—analyzing a method multiple times based on calling contexts—which limits scalability on large programs. In this work, we propose Cut-Shortcut , a fundamentally different approach for fast yet precise Java pointer analysis. The core insight is that the primary benefit of context sensitivity is to filter spurious object flows merged within callee methods; from the perspective of a pointer flow graph, this effect can be obtained without explicit contexts by suppressing the addition of imprecise flow edges ( Cut ) and adding Shortcut edges that directly connect source pointers to target pointers across method boundaries. This insight is distilled into a general principle and instantiated via three well-characterized program patterns under which suppressing imprecise flows and adding precise shortcut flows are provably safe. We formalize Cut-Shortcut via inference rules and prove soundness. A CFL-reachability formulation is further provided to relate Cut-Shortcut to well-understood formal models of pointer analysis and to show that Cut-Shortcut has the same worst-case asymptotic complexity as context-insensitive analysis. To address new sources of imprecision introduced in modern Java, we further propose Cut-Shortcut S , extending one of the patterns to handle Streams and their interaction with Lambda Expressions by distinguishing flows across different stream pipelines. Implemented in the state-of-the-art pointer analysis framework Tai-e , Cut-Shortcut is evaluated on 10 large, complex Java programs from recent literature, and Cut-Shortcut S is evaluated on three new stream-heavy benchmark suites that we created (with 20 programs in total). Results show that Cut-Shortcut achieves precision close to (selective) context-sensitive analysis (where applicable), while being faster than context-insensitive analysis on 9 of the 10 programs and matching it on the remaining one. Moreover, Cut-Shortcut S yields substantial precision improvement while preserving scalability and efficiency for programs with heavy stream usage. To the best of our knowledge, this work is the first to achieve such a good efficiency-precision trade-off for hard-to-analyze Java programs, including large-scale and feature-rich applications.