Dynamic determinacy analysis
Authors:
Open Access
- 16 June 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 48 (6) , 165-174
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.Keywords
This publication has 22 references indexed in Scilit:
- Fast and precise hybrid type inference for JavaScript2012
- Type-directed automatic incrementalization2012
- Multiple facets for dynamic information flow2012
- Correlation Tracking for Points-To Analysis of JavaScript2012
- Implicit self-adjusting computation for purely functional programs2011
- Profile-guided static typing for dynamic scripting languages2009
- Coinductive big-step operational semanticsInformation and Computation, 2009
- Type Analysis for JavaScript2009
- Weighted pushdown systems and their application to interprocedural dataflow analysisScience of Computer Programming, 2005
- Symbolic execution and program testingCommunications of the ACM, 1976