Context-free type recording for virtual machines of dynamic programming languages

A computing device for running dynamically-typed programming languages, comprising;

• a compilation engine for compiling source code of a dynamically-typed program;
• a context-free type-state recorder in a memory, configured to record a first data type of one or more values associated with a particular named memory location within the source code during runtime, and further configured to record all possible data types that may be assigned to the particular named memory location across multiple runs of the dynamically-typed program;
• an optimized code generation component configured to generate optimized code based on the first data type of the value being a matching data types for global values associated with the particular named memory location;
• and
• a run-time type-checking component for type-checking one or more global values associated with the particular named memory location to determine whether the global values have matching data types to the first data type,
• wherein the context-free type-state recorder is further configured to record, during runtime, if one or more of the global values associated with the particular named memory location is a different data type than the first data type, one or more different data types associated with the particular named memory location;
• and
• wherein the optimized code generation component is further configured to generate optimized code based on the first data type and the one or more different data types of the values associated with the particular named memory location being matching data types for global values associated with the particular named memory location.

A non-transitory, tangible computer readable storage medium, encoded with processor readable instructions to perform a method for reducing deoptimization in a virtual machine, the method comprising:

• compiling, at a compilation engine, source code of a dynamically-typed program;
• recording, during runtime, at a context-free type state recorder in a memory, a first data type of a value associated with a particular named memory location within the source code, wherein the context-free type-state recorder is configured to record all possible data types that may be assigned to the particular named memory location across multiple runs of the dynamically-typed program;
• generating optimized code based on the first data type of the value being a matching data type for global values associated with the particular named memory location;
• type-checking that one or more global values associated with the particular named memory location is of the same type as the first data type;
• recording, during runtime, at the context-free type-state recorder, if one or more of the global values associated with the particular named memory location is a different data type than the first data type, one or more different data types associated with the particular named memory location;
• and
• generating optimized code based on the first data type and the one or more different data types of the values associated with the particular named memory location being matching data types for global values associated with the particular named memory location.