Practical virtual method call resolution for Java

This paper addresses the problem of resolving virtual method and interface calls in Java bytecode. The main focus is on a new practical technique that can be used to analyze large applications. Our fundamental design goal was to develop a technique that can be solved with only one iteration, and thu s scales linearly with the size of the program, while at the same time prov iding more accurate results than two popular existing linear techniques, cl ass hierarchy analysis and rapid type analysis. We present two variations of our new technique, variable-type analysis and a coarser-grain version called declared-type analysis. Both of these analys es are inexpensive, easy to implement, and our experimental results show th at they scale linearly in the size of the program. We have implemented our new analyses using the Soot framework, and we repor t on empirical results for seven benchmarks. We have used our techniques to build accurate call graphs for complete applications (including libraries) and we show that compared to a conservative call graph built using class h ierarchy analysis, our new variable-type analysis can remove a significant number of nodes (methods) and call edges. Further, our results show that we can improve upon the compression obtained using rapid type analysis. We also provide dynamic measurements of monomorphic call sites, focusing on the benchmark code excluding libraries. We demonstrate that when consideri ng only the benchmark code, both rapid type analysis and our new declared-t ype analysis do not add much precision over class hierarchy analysis. Howev er, our finer-grained variable-type analysis does resolve significantly mor e call sites, particularly for programs with more complex uses of objects.