US 10,871,950 B2 · Persistent annotation of syntax graphs for code optimization

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.

Claims20

Dependent claims

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.

1 more element

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.

2 more elements

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 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 specifying an extent of functional purity of the piece of code;
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;
and
producing an optimization of the program based at least in part on the annotated syntax graph.

3 more elements

Dependencies are inferred from the claim text.

Persistent annotation of syntax graphs for code optimization

Life of this patent

Persistent annotation of syntax graphs for code optimization

Life of this patent

Abstract

Claims20