Dynamic Optimistic Interprocedural Analysis: A Framework and an Application

Authors:  Igor Pechtchanski, Vivek Sarkar

Conference:  2001 ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Tampa, FL, October 14-18, 2001.

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 interprocedural analysis. The framework is designed to be used in the context of dynamic class loading and dynamic compilation, and includes 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 Jalapeņo 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.7x-4.6x and 1.6x-2.4x 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 of polymorphic 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.5x-5.4x faster than the Jalapeņo baseline compiler).

Download:  postscript file (354K), PDF file (721K)

BibTeX Entry: 
@INPROCEEDINGS(pechtchanski-sarkar-01,
  Author      = "Igor Pechtchanski and Vivek Sarkar",
  Title       = "Dynamic Optimistic Interprocedural Analysis: A Framework and
                an Application",
  Booktitle   = "ACM Conference on Object-Oriented Programming, Systems,
                Languages, and Applications",
  Pages       = "195--210",
  Year        = 2001,
  Month       = oct,
  Day         = "14--18",
  Location    = "Tampa, Florida, USA",
  Publisher   = "ACM Press",
  ISBN        = "1-58113-441-X",
)
[Home]


Last modified on
Igor Peshansky
pechtcha@cs.nyu.edu