Auto-vectorization in just-in-time compilers for dynamically typed programming languages

Abstract

A computing device with an optimizing compiler is disclosed that is configured to generate optimized machine code including a vector operation corresponding to multiple scalar operations where the vector operation is a single operation on multiple pairs of operands. The optimizing compiler includes a vector guard condition generator configured to generate a vector guard condition for one or more vector operations, a mapping module to generate a mapping between elements of the vector guard condition and positions of the relevant scalar operations in the non-optimized machine code or intermediate representation of the source code, and a guard condition handler configured to initiate execution from a particular scalar operation in the non-optimized machine code or intermediate representation if the vector guard condition is triggered. The computing device may include a non-optimizing compiler and/or an interpreter to perform execution of the scalar operations if the vector guard condition is triggered.

What is claimed is: 
     
         1 . A computing device for compiling source code, the device including:
 a non-optimizing compiler configured to generate non-optimized machine code that includes multiple scalar operations, each scalar operation includes a single pair of operands;   an optimizing compiler configured to generate optimized machine code including a vector operation corresponding to the multiple scalar operations, the vector operation is single operation on multiple pairs of operands, the optimizing compiler including:
 a vector guard condition generator configured to generate a vector guard condition for, at least, the vector operation; 
 a mapping module to generate a mapping between elements of the vector guard condition and positions in the non-optimized machine code; and 
 a guard condition handler configured to initiate execution of a particular scalar operation of the non-optimized machine code if the vector guard condition is triggered. 
   
     
     
         2 . The computing device of  claim 1 , wherein the source code is a type selected from the group consisting of JavaScript, LISP, SELF, Python, Perl, and ActionScript. 
     
     
         3 . The computing device of  claim 1 , wherein the vector guard condition generator is configured to generate a reference vector and the guard condition handler is configured to compare the reference vector with an output of the vector operation to determine if the vector guard condition is triggered. 
     
     
         4 . A method for compiling source code, the method comprising:
 receiving source code of a dynamically-typed language wherein types of operations are not defined in the source code;   generating an intermediate representation from the source code;   performing interpreted execution of the intermediate representation;   gathering profile information to determine if optimized machine code should be created or not;   transforming multiple scalar operations in the intermediate representation from a scalar form to a vector operation, wherein each scalar operation includes a single pair of operands, and the vector operation is single operation on multiple pairs of operands;   creating a vector guard condition for, at least, a vector operation;   creating optimized machine code that includes the vector operation and the vector guard condition;   executing the optimized machine code containing the vector operation;   mapping an element of the vector guard condition in the optimized machine code to a particular scalar operation of the intermediate representation if the vector guard condition is triggered during execution of the vector operation in the optimized machine code; and   switching back to start interpretation of the intermediate representation from the particular scalar operation when the guard condition is triggered.   
     
     
         5 . The method of  claim 4 , including:
 generating a reference vector; and   comparing the reference vector with an output of the vector operation to determine if the vector guard condition is triggered.   
     
     
         6 . The method of  claim 4 , including switching to execute the optimized machine code after starting the interpretation. 
     
     
         7 . The method of  claim 4 , including:
 generating a mapping table that maps, for the vector guard condition, each of a plurality of element positions of the vector operation to a node in the intermediate representation of the source code.   
     
     
         8 . A computing device for compiling source code, the computing device including:
 an interpreter configured to interpret an intermediate representation of the source code that includes multiple scalar operations, each scalar operation includes a single pair of operands;   an optimizing compiler configured to generate optimized machine code including a vector operation corresponding to the multiple scalar operations, the vector operation is single operation on multiple pairs of operands, the optimizing compiler including:
 a vector guard condition generator configured to generate a vector guard condition for one or more vector operations; 
 a mapping module to generate a mapping between elements of the vector guard condition and positions in the intermediate representation of the source code; and 
 a guard condition handler configured to initiate interpretation of a particular scalar operation of the intermediate representation of the source code if the vector guard condition is triggered. 
   
     
     
         9 . The computing device of  claim 8 , wherein the source code is a type selected from the group consisting of JavaScript, LISP, SELF, Python, Perl, and ActionScript. 
     
     
         10 . The computing device of  claim 8 , wherein the vector guard generator is configured to generate a reference vector, and wherein the guard condition handler is configured to compare the reference vector with an output of the vector operation to determine if the vector guard condition is triggered. 
     
     
         11 . The computing device of  claim 8 , wherein the optimizing compiler is configured to switch back to execute the optimized machine code after interpreting the particular scalar operation of the intermediate representation of the source code. 
     
     
         12 . The computing device of  claim 8 , wherein the mapping module is configured to map, for the vector guard condition, each of a plurality of element positions of the vector operation to a node in the intermediate representation of the source code.