Browse Prior Art Database

Dynamic Determinacy Analysis

IP.com Disclosure Number: IPCOM000224582D
Publication Date: 2013-Jan-02

Publishing Venue

The IP.com Prior Art Database

Abstract

We present an analysis for identifying determinate variables and expressions that always have the same value at a given program point. This information can be exploited by client analyses and tools to, e.g., identify dead code or specialize uses of dynamic language constructs such as eval, replacing them with equivalent static constructs. Our analysis is completely dynamic and only needs to observe a single execution of the program, yet the determinacy facts it infers hold for any execution. We present a formal soundness proof of the analysis for a simple imperative language, and a prototype implementation that handles full JavaScript. Finally, we report on two case studies that explored how static analysis for JavaScript could leverage the information gathered by dynamic determinacy analysis. We found that in some cases scalability of static pointer analysis was improved dramatically, and that many uses of runtime code generation could be eliminated.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 01 of 19

Dynamic Determinacy Analysis

Reflective language constructs (reflection in Java, eval in JavaScript) cause many difficulties for static analysis. Hence, a solution is needed to help a static analysis characterize the possible behaviors of such reflective code. Existing approaches for helping to analyze reflection often work by observing the dynamic behavior of such code, but they cannot give any guarantees regarding all the possible behaviors of the code.

We present an analysis for identifying \emph{determinate} variables and expressions that always have the same value at a given program point.

This information can be exploited by client analyses and tools to, e.g., identify dead code or specialize uses of dynamic language constructs such as \code{eval}, replacing them with equivalent static constructs.

Our analysis is completely dynamic and only needs to observe a single execution of the program, yet the determinacy facts it infers hold for any execution.

We present a formal soundness proof of the analysis for a simple imperative language, and a prototype implementation that handles full JavaScript.

Finally, we report on two case studies that explored how static analysis for JavaScript could leverage the information
gathered by dynamic determinacy analysis. We found that in some cases scalability of static pointer analysis
was improved dramatically, and that many uses of runtime code generation could be eliminated.

PLDI submission:

Dynamic Determinacy Analysis

Abstract

We present an analysis for identifying determinate variables and expressions that always have the same value at a given program
point. This information can be exploited by client analyses and
tools to, e.g., identify dead code or specialize uses of dynamic language constructs such as eval, replacing them with equivalent static constructs. Our analysis is completely dynamic and only
needs to observe a single execution of the program, yet the determinacy facts it infers hold for any execution. We present a formal
soundness proof of the analysis for a simple imperative language,
and a prototype implementation that handles full JavaScript. Finally, we report on two case studies that explored how static analysis
for JavaScript could leverage the information gathered by dynamic determinacy analysis. We found that in some cases scalability
of static pointer analysis was improved dramatically, and that
many uses of runtime code generation could be eliminated.


1. Introduction

Most modern programming languages offer support for reflective
programming. For instance, Java programs can inspect an object's
class at runtime to discover or access its fields and methods, and
they can dynamically load classes by name, or even create new
classes from scratch. Modern dynamic languages such as Ruby or
JavaScript are even more liberal and permit almost arbitrary reflective changes to a running program's state. JavaScript, for example,
provides for-in loops to discover an object's properties, and dyna...