In object-oriented languages, the traditional CFL-reachability formulation for $k$-callsite-sensitive pointer analysis ($k$CFA) focuses on modeling field accesses and calling contexts, but it relies on a separate algorithm for call graph construction. This division can result in a loss of precision in ($k$CFA), a problem that persists even when using the most precise call graphs, whether pre-constructed or generated on the fly. Moreover, pre-analyses based on this framework aiming to improve the efficiency of ($k$CFA) may inadvertently reduce its precision, due to the framework’s lack of native call graph construction, essential for precise analysis.

Addressing this gap, this paper introduces a novel CFL-reachability formulation of ($k$CFA) for Java, uniquely integrating on-the-fly call graph construction. This advancement not only addresses the precision loss inherent in the traditional CFL-reachability-based approach but also enhances its overall applicability. In a significant secondary contribution, we present the first precision-preserving pre-analysis to accelerate ($k$CFA). This pre-analysis leverages selective context sensitivity to improve the efficiency of ($k$CFA) without sacrificing its precision. Collectively, these contributions represent a substantial step forward in pointer analysis, offering both theoretical and practical advancements that could benefit future developments in the field.