Persistent annotation of syntax graphs for code optimization

Patent metadata

Field	Value
Publication number	US-10871950-B2
Application number	US-201916414526-A
Country	US
Kind code	B2
Filing date	May 16, 2019
Priority date	May 16, 2019
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

Abstract

Optimization opportunities are located and documented to enhance code translation by compilers or interpreters. An enhanced translator scans a program syntax graph, recognizes subgraph structures, and annotates nodes of the graph to document optimization characteristics of program code entities associated with the nodes. Subgraph structures and corresponding annotations may be maintained in an optimization catalog, distinct from any particular optimizable program. Optimizers improve program code translation based on the annotated syntax graph. Optimization characteristics may specify code purity in terms of execution value ranges and execution behaviors, e.g., side-effects, local or global variable usage, I/O, by-reference parameters, and which exceptions are possible. Subgraph structures may be identified using routine names, hash values, and templates with holes any constant will fill. Parent node characteristics may be inferred from characteristics of child nodes. Optimization candidates may be prioritized using weight functions. Optimizer callbacks may be inserted to evaluate optimization characteristics incrementally.

First claim

What is claimed is:

1. A code translation optimization system, comprising:
a memory;
a processor in operable communication with the memory, the processor configured to perform steps which include (a) traversing at least a portion of a syntax graph of a program, (b) recognizing a predetermined subgraph structure in the syntax graph, (c) annotating the recognized syntax subgraph structure with an optimization characteristic annotation, the optimization characteristic annotation indicating a presence or an absence of functional purity of a piece of code that corresponds to the recognized subgraph structure, and (d) performing an optimization of a code translation of the program based at least in part on a result of the annotating step; and
wherein the memory comprises a catalog having an entry, the entry including an identification of the subgraph structure and the optimization characteristic annotation which is associated with the identified subgraph structure, the catalog entry in existence prior to the code translation of the program and also in existence after the optimization of the code translation of the program is performed.

2. The system of claim 1 , wherein the identification of the subgraph structure includes or is indexed by at least one of the following keys:
a name of a routine of a library which is utilized by the program;
a name of a user-defined routine which is part of the program and is specific to the program;
a hash value of a routine;
a hash value of the subgraph structure; or
a hash value of a syntax subgraph structure template.

3. The system of claim 1 , wherein the optimization characteristic annotation indicates at least one of the following:
whether the piece of code that corresponds to the recognized subgraph structure accesses any non-local variable during an execution of the piece of code;
whether the piece of code that corresponds to the recognized subgraph structure has any local static variable;
whether the piece of code that corresponds to the recognized subgraph structure has any parameter which is passed by reference to support an execution of the piece of code;
whether the piece of code that corresponds to the recognized subgraph structure accesses any I/O device or I/O stream during an execution of the piece of code;
whether the piece of code fails to terminate after an execution of the piece of code has begun; or
whether the piece of code that corresponds to the recognized subgraph structure may throw an exception during an execution of the piece of code.

4. The system of claim 1 , comprising a pluggable optimizer which the system is configured to invoke to perform the optimization, wherein an optimizer is deemed pluggable when the optimizer can be enabled or disabled or both without recompiling code which invokes the optimizer.

5. The system of claim 1 , wherein the optimization characteristic annotation indicates whether the piece of code that corresponds to the recognized subgraph structure has no side-effect during an execution of the piece of code.

6. A method for finding optimization opportunities during code translation, the method comprising:
scanning at least part of a syntax graph of a program, the syntax graph having nodes, the syntax graph representing at least syntactic structure aspects of the program;
ascertaining that a piece of code of the program which is associated with a node of the syntax graph has an optimization characteristic;
annotating the syntax graph with an optimization characteristic annotation according to the ascertained optimization characteristic, the optimization characteristic annotation including an execution value of the piece of code which is discernable prior to execution of the piece of code or specifying an extent of functional purity of the piece of code, or both; and
consulting a catalog which associates the optimization characteristic with an identification of the corresponding portion of the syntax graph of the program, the catalog being distinct from the program and being in existence prior to the scanning of the program syntax graph and also being in existence after the code translation of the program is performed.

7. The method of claim 6 , wherein ascertaining that the piece of code of the program which is associated with the node of the syntax graph has the optimization characteristic comprises at least one of the following:
matching the piece of code to an entry in the catalog which describes the optimization characteristic;
matching a syntax subgraph containing the node to an entry in the catalog which describes the optimization characteristic.

8. The method of claim 6 , wherein ascertaining that the piece of code of the program which is associated with a first node of the syntax graph has a first optimization characteristic comprises making an inference from a second optimization characteristic that is associated with a second node of the syntax graph, the first and second nodes having different respective locations in the syntax graph, the first and second optimization characteristics having the same or different respective values.

9. The method of claim 6 , further comprising providing an optimizer access to the annotated syntax graph, and the optimizer producing at least one of the following:
an optimization which reduces a processor cycle count for an execution of the piece of code of the program;
an optimization which reduces a memory requirement for an execution of the piece of code of the program;
an optimization which reduces an I/O requirement for an execution of the piece of code of the program;
an optimization which at compile time replaces a part of the program by a constant value;
an optimization which memoizes data or instructions or both in the piece of code of the program; or
an optimization which removes a call or jump to an exception handler in the piece of code of the program.

10. The method of claim 6 , further comprising an optimizer producing an optimization based on the annotated syntax graph, wherein the optimization includes a rewrite of at least a portion of the syntax graph.

11. The method of claim 6 , further comprising:
an optimizer producing multiple optimization candidates which are based on the annotated syntax graph;
assigning respective weights to at least two of the optimization candidates; and
prioritizing optimization candidates based at least in part on their respective assigned weights.

12. The method of claim 6 , further comprising inserting a callback which upon execution triggers a partial evaluation which produces an optimization based at least in part on the annotated syntax graph.

13. The method of claim 6 , wherein the ascertaining does not rely on use of a programming language keyword in a source code of the program specifically to denote the optimization characteristic.

14. The method of claim 6 , further comprising updating the catalog to include an additional piece of code or an additional syntax subgraph structure, and updating the catalog to include a corresponding optimization characteristic which matches an additional annotation of the syntax graph.

15. The method of claim 6 , further comprising updating the catalog by at least one of the following: modifying an entry in the catalog, deleting an entry from the catalog, or changing the order of entries in the catalog.

16. A computer-readable storage medium configured with data and instructions which upon execution by a processor perform a method for finding optimization opportunities during code translation, the method comprising:
scanning at least part of a syntax graph o

Assignees

• Microsoft Technology Licensing Llc

Inventors

• De Smet Bart J F

Classifications

• G06F8/443 Primary

  Optimisation · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F8/427

  Parsing · CPC title