A method and a computing device for reducing deoptimization in a virtual machine are provided. Source code of a dynamically-typed program is compiled. A context-free type-state recorder records a first data type of a value associated with a particular named memory location within the source code. Optimized code may be generated based on the first data type of the value being a matching data type for global values associated with the particular named memory location. One or more global values associated with the particular named memory location may be type-checked. The context-free type-state recorder may record, 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. New optimized code may then be generated.