Browse Prior Art Database

Type Specialization for Dynamic Weakly Typed Languages

IP.com Disclosure Number: IPCOM000240673D
Publication Date: 2015-Feb-17
Document File: 3 page(s) / 149K

Publishing Venue

The IP.com Prior Art Database

Abstract

The invention allows dynamic types from dynamic weakly typed languages to be specialized to a native type such as an int or a double, which allows a compiler to generate more efficient code. A factor of ten speedup on a simple but uneliminable loop, where the induction variable could thus be deduced may be expected.

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

Page 01 of 3

Type Specialization for Dynamic Weakly Typed Languages

Interpreted dynamic weakly typed languages such as PHP, Ruby and Python are often accelerated by dynamically compiling into bytecode, thus allowing a just-in-time (JIT) compiler to compile the bytecode into native code.

    One drawback with this approach is that the JIT compiler does not understand the source language's dynamic types, and hence many optimizations, such as loop invariance and induction variable analysis, and arithmetic optimizations are blocked. But in many cases, such variables are not actually dynamic, and their type may have been determined.

    This invention is a method for carrying out type specialization, so that the dynamic type of a variable may, in some cases, be specialized to say an int or a double allowing the generated bytecode to be consumable to the JIT compiler.

    A factor of ten speedup on a simple but uneliminable loop may be expected, where the induction variable could thus be deduced by the JIT compiler.

    The key step is to recognize that type specialization is equivalent to constant propagation where the constants are not the values of expressions but their types. With this step, it is then simply possible to use constant propagation algorithms but working on the types of expressions instead.

    The detailed description demonstrates how this is carried out for the algorithm called "Sparse Conditional Constant Propagation" [1] which uses SSA (Static Single Assignment) form [2, 3] and works on conditional branches which includes loops. This description explains the changes made to this algorithm to implement the type specialization algorithm and also explains the salient points about why this algorithm was chosen.

    As we want the algorithm to aid the JIT compiler to carry out loop invariance and induction variable analysis, we require that the type specialization algorithm must be able to deal with branches. Therefore we require a constant propagation algorithm that works on branches. A survey of the literature showed that [1] was the best candidate for this.

    First I describe the prior art on which our invention is based. Algorithm [1] is a data flow analysis technique that works on the value of expressions in an representation of the program. Data-flow analysis algorithms "propagate" data-flow information (in this case the constantness of the value of an expression) iteratively until the values converge. The converged values (which are guaranteed to converge in finite time) give the constant values.

    The concept of a lattice is important here, because the converged values are member of a lattice which may be: value of the constant, or cannot be constant (bottom, symbol: an upside down T). Initially values of expressions in the algorithm take the value of top (T, meaning "unassigned") and as the algorithm progresses they converge to either a constant value (shown as false ... -2, -1, 0, 1, 2, ... true) or bottom. In a valid program, when converged there w...