Optimized execution of dynamic languages

• US 10,025,571 B1
• Filed: 07/17/2014
• Issued: 07/17/2018
• Est. Priority Date: 07/17/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Boulos, Solomon, Sugerman, Jeremy
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): Soltanzadeh, Amir
• Application Number:
  US14/334,582
• Time in Patent Office: 1,461 Days
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/437 Type checking
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

In one aspect, a method includes receiving a code block including one or more variables, performing forward data flow analysis for the code block including generating a control flow graph of the code block and for each operation in the control flow graph determining if the operation provides an update regarding the type of one or more of the operations or variables of the code block, the update being based on one or more rules of type inference, updating a type set of each of the operations or variables where the operation provides an update regarding the type, determining if the operation provides an update regarding the location of the variables, the update being based on one or more rules of location inference and updating a location set of each of the variables where the operation provides an update regarding the location set.

Claims

1. A machine-implemented method comprising:

receiving a code block of dynamic language code, the code block including one or more variables;

generating a control flow graph of the code block, the control flow graph including one or more operations;

performing forward data flow analysis for the control flow graph of the code block, the forward data flow analysis for each operation of the one or more operations of the control flow graph comprising;

determining if the operation provides an update regarding a type of one or more of the one or more operations or one or more variables, the update being based on one or more rules of type inference, wherein the one or more rules of type inference comprise at least one of;

information including a signature of a builtin, a return type computed for a user function, an argument type from call-time function specialization, or a rule of language of the code block;

updating a type set of each of the one or more operations when the operation provides the update regarding the type of each of the one or more operations, wherein the update regarding the type of at least one of the one or more operations is determined independently of the one or more variables; and

updating a type set of each of the one or more variables when the operation provides the update regarding the type of each of the one or more variables; and

returning the type set for the one or more of the one or more operations or the one or more variables of the code block determined in response to the forward data flow analysis, wherein the type set of each of the one or more operations or the one or more variables defines possible types for each of the one or more operations or the one or more variables.

2. The method of claim 1, wherein performing the forward data flow analysis further comprises:

for each of the one or more operations of the control flow graph, determining if the operation provides an update regarding a scope of the one or more variables, the update being based on one or more rules of location inference; and

updating, prior to executing the code block, a location set of each of the one or more variables where the operation provides the update regarding the scope of the one or more variables, wherein the location set for each variable of the one or more variables is initially set to null and the location set comprises one or more possible locations for the variable.

3. The method of claim 2, further comprising:

returning the location set for each of the one or more variables of the code block determined in response to the forward data flow analysis once the forward data flow analysis converges.

4. The method of claim 2, wherein the rules of location inference include one or more of:

information regarding signatures of builtins, return locations computed for user functions, argument locations from call-time function specialization or rules of language of the code block.

5. The method of claim 2, wherein the location set for at least one of the one or more variables includes at least two possible locations.

6. The method of claim 2, wherein the location set for at least one variable of one or more variables includes location information regarding type of storage for the at least one variable.

7. The method of claim 6, wherein a type of storage for the at least one variable may include one of stack based, heap based, global heap or constant.

8. The method of claim 2, wherein the location set for at least one variable of one or more variables includes location information indicating type of access for the at least one variable at runtime.

9. The method of claim 8, wherein the type of access comprises at least one of:

statically resolving an address during compile-time, semi-statically resolving the address with occasional feedback to dynamic lookup, dynamically resolving with pre-computation, or fully dynamically resolve by name.

10. The method of claim 2, further comprising:

storing the type set for the one or more of the one or more operations or the one or more variables in association with the code block once the forward data flow analysis converges.

11. The method of claim 1, wherein the code block includes a function, and wherein the returning comprises returning type information regarding one or more argument variables or return variables of the function.

12. The method of claim 1, wherein the forward data flow analysis is performed until the forward data flow analysis converges.

13. The method of claim 1, wherein the code block is in a dynamic language.

14. A system comprising:

one or more processors; and

a machine-readable medium comprising instructions stored therein, which when executed by the processors, cause the processors to perform operations comprising;

generating a control flow graph of a code block, the control flow graph comprising one or more operations and one or more variables;

performing forward data flow analysis for the code block until the forward data flow analysis converges, the forward data flow analysis for each operation of the one or more operations of the control flow graph comprising;

determining if the operation provides an update regarding a type of one or more of the one or more operations or one or more variables, the update being based on one or more rules of type inference, wherein the one or more rules of type inference comprise at least one of;

information including a signature of a builtin, a return type computed for a user function, an argument type from call-time function specialization, or a rule of language of the code block;

updating a type set of each of the one or more of the one or more operations or one or more variables where the operation provides the update regarding the type;

determining if the operation provides an update regarding a scope of the one or more variables, the update being based on one or more rules of location inference; and

updating, prior to executing the code block, a location set of each of the one or more variables where the operation provides the update regarding the scope of the one or more variables; and

storing the type sets and location sets generated in response to the forward data flow analysis with respect to the code block.

15. The system of claim 14, wherein the forward data flow analysis converges when the location set and type set of the one or more operations or one or more variables is no longer updated.

16. The system of claim 14, wherein the location set for at least one variable of one or more variables includes one or more of:

location information indicating how optimally to represent a type of storage for the at least one variable, or location information indicating type of access for the at least one variable at runtime.

17. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

receiving a code block, the code block including one or more variables;

generating a control flow graph of the code block including one or more operations;

performing forward data flow analysis for the control flow graph of the code block, the forward data flow analysis for each operation of the one or more operations of the control flow graph comprising;

determining if the operation provides an update regarding a type of one or more of the one or more operations or one or more variables, the update being based on one or more rules of type inference, wherein the one or more rules of type inference comprise at least one of;

information including a signature of a builtin, a return type computed for a user function, an argument type from call-time function specialization, or a rule of language of the code block;

updating a type set of each of the one or more of the one or more operations or one or more variables where the operation provides the update regarding the type;

determining if the operation provides an update regarding a scope of the one or more variables, the update being based on one or more rules of location inference; and

updating, prior to executing the code block, a location set of each of the one or more variables where the operation provides the update regarding the scope of each of the one or more variables; and

returning the type set for each of the one or more of the one or more operations or the one or more variables of the code block determined in response to the forward data flow analysis, wherein the type set of each of the one or more operations or the one or more variables defines possible types for each of the one or more operations or the one or more variables.

18. The non-transitory machine-readable medium of claim 17, wherein performing the forward data flow analysis further comprises:

determining if the forward data flow analysis converges, wherein the forward data flow analysis converges when the location set and type set of the one or more operations or one or more variables is no longer updated;

performing the forward data flow analysis if the forward data flow analysis does not converge; and

storing the type sets and location sets generated in response to the forward data flow analysis with respect to the code block.