Dynamic Optimistic lnterprocedurai Analysis: A framework and an application

Abstract

In this paper, we address the problem of dynamic optimistic interprocedural analysis. Our goal is to build on past work on static interprocedural analysis and dynamic optimization by combining their advantages. We present a framework for performing dynamic optimistic interprocedurai analysis. The framework is designed to be used in the context of dynamic class loading and dynamic compilation, and in-dudes mechanisms for event notification (on class loading and method compilation) and dependence tracking (to enable invalidation of optimistic assumptions). We illustrate the functionality of the framework by using it to implement a dynamic optimistic interprocedural type (DOIT) analysis algorithm. The DOIT algorithm uses a new global data structure called the Value Graph. The framework and DOIT analysis are implemented as part of the IBM Jalapefio Java Virtual Machine. Our experimental results for the SPECjvm benchmarks and two larger programs show promising benefits due to dynamic optimistic analysis. Compared to pessimistic analysis, the reduction in the number of methods and fields analyzed was in the 2.7×~4.6× and 1.6×-2.4× ranges respectively. The average fraction of polymorphic virtual calls decreased from 39.5% to 24.4% due to optimistic analysis, with a best-case decrease from 47.0% to 8.1%. The average fraction ofpolymorphic interface calls decreased from 96.4% to 36.2% due to optimistic analysis, with a best-case decrease from 100.0% to 0.0%. These benefits were obtained with a low dynamic analysis overhead in the range of 570-930 bytecode bytes/millisecond (about 2.5×-5.4× faster than the Jalapefio baseline compiler).