Program optimization via compile time execution

Patent metadata

Field	Value
Publication number	US-9690550-B2
Application number	US-201514704689-A
Country	US
Kind code	B2
Filing date	May 5, 2015
Priority date	Aug 23, 2012
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

When compiling high level, graphical code (e.g. LabVIEW™ code) representative of a design, parts of the code that do not depend on external input data may be executed during the compilation process. Specific variables and/or value traces of specific variables in the program, e.g. constant values and/or repeating patterns may be recorded then analyzed, and certain transformations may be applied in the compilation process according to the results of the analysis, thereby optimizing the design. In one approach, the graph may be dynamically stepped through one node at a time, and it may be determined whether all inputs to the stepped-through node are known. If those inputs are known, type conversion and the operation corresponding to the stepped-through node may be dynamically performed. In another approach, a subset of the graphical code not depending on external data may be compiled and executed, thereby obtaining the same results as described above.

First claim

We claim:

1. A non-transitory computer-accessible memory medium that stores program instructions executable by a computer system to:
receive an input program representative of a design comprising one or more functions;
compile the received input program to produce an output;
during the compile of the received input program, after the compile starts, and before the compile completes:
generate information about one or more elements of the design by executing portions of the received input program, wherein the portions are less than the entire input program, wherein at least one portion of the received input program are array indices in the input program, wherein the information comprises information about value traces of at least one of the one or more variables in the input program, and wherein said executing comprises:
determining and executing compiled executable instructions implementing each of the portions of the received program;
analyze the information; and
optimize the output by applying one or more transformations to the compile, including applying one or more transformations to arrays or array operations in the input program, responsive to analyzing the information.

2. The non-transitory computer-accessible memory medium of claim 1 , wherein the value traces of specific variables comprise one or more of:
a sequence of values;
a sequence of values in combination with loop iteration information;
a sequence of values in combination with multiple nested loop iteration information;
a sequence of values in combination with caller stack information;
a sequence of values across multiple variables; or
a compact expression that can generate values.

3. The non-transitory computer-accessible memory medium of claim 1 , wherein the portions of the received input program comprise one or more of:
a portion of the received input program that is data independent;
a portion of the received input program that is in a fan in cone of array indices; or
a few iterations of a loop in the received input program.

4. The non-transitory computer-accessible memory medium of claim 1 , wherein the program instructions executable to analyze the information comprise one or more of:
program instructions executable to determine loop iteration distances between array read operations;
program instructions executable to determine loop iteration distances between array write operations;
program instructions executable to determine loop iteration distances between array read and array write operations;
program instructions executable to collect statistics of value traces; or
program instructions executable to collect statistics of value traces across multiple variables.

5. The non-transitory computer-accessible memory medium of claim 4 , wherein the statistics comprise one or more of:
minimum value;
maximum value;
value ranges;
repetitive patterns;
number of bits required to represent values in specific data types;
count overflow value; or count underflow value.

6. The non-transitory computer-accessible memory medium of claim 1 , wherein the program instructions executable to apply transformations to the compile comprise one or more of:
program instructions executable to perform a new loop iteration before a current loop iteration finishes;
program instructions executable to generate pipelining hardware implementing an iterative behavior described by a loop;
program instructions executable to convert variables from one data type to another data type;
program instructions executable to determine a number of bits required to represent a variable;
program instructions executable to generate machine code implementing access to memories in anticipation of use;
program instructions executable to generate hardware implementing access to memories in anticipation of use;
program instructions executable to replace a variable with a constant;
program instructions executable to replace a variable with a look-up table of constants;
program instructions executable to replace an array variable with one or more of:
multiple array variables;
multiple non-array variables;

program instructions executable to replace multiple array variables with fewer array variables;
program instructions executable to replace one or more array variables with one or more other array variables with different arrangements of elements; or
program instructions executable to remove dead code.

7. The non-transitory computer-accessible memory medium of claim 1 , wherein the input program comprises one or more of:
a behavioral description of a piece of software in one or more of:
a programming language;
a machine language; or
a hardware description language; or

a behavioral description of a piece of hardware in one or more of:
a programming language;
a machine language; or
a hardware description language.

8. The non-transitory computer-accessible memory medium of claim 1 , wherein the program instructions executable to compile the input program comprise program instructions executable to:
translate the input program into another program that comprises a behavioral description of the design in one of:
a programming language;
a machine language; or
a hardware description language.

9. The non-transitory computer-accessible memory medium of claim 1 , wherein executing the portions of the received input program comprises one or more of:
interpreting the portions of the program in software executed on a computer;
executing, on the computer, code obtained from having compiled the portions of the program; or
emulating the portions of the program on hardware.

10. The non-transitory computer-accessible memory medium of claim 1 , wherein the program instructions are further executable to:
during the compile of the received input program, store the information in one or more of:
memory; or
storage disk.

11. The non-transitory computer-accessible memory medium of claim 10 , wherein the program instructions are further executable to:
use the stored information in a future compilation.

12. A computer-implemented method, comprising:
receiving an input program representative of a design comprising one or more functions;
compiling the received input program to produce an output representative of the design;
during said compiling of the received input program, after the compile starts, and before the compile completes:
generating information about one or more elements of the design by executing portions of the received input program, wherein the portions are less than the entire input program, wherein at least one portion of the received input program are array indices in the input program, wherein the information comprises information about value traces of at least one of the one or more variables in the input program, and wherein said executing comprises:
determining and executing compiled executable instructions implementing each of the portions of the received program;
analyzing the information; and
optimizing the output by applying transformations to one or more stages of said compiling, including applying one or more transformations to arrays or array operations in the input program, responsive to said analyzing the information.

13. The computer-implemented method of claim 12 , wherein the input program comprises graphical code, and the output is a program that comprises a hardware description language representation of the design.

14. The computer-implemented method of claim 12 , wherein the value traces of specific variables comprise one or more of:
a sequence of values;
a sequence of values in combinat

Assignees

• Nat Instr Corp

Inventors

• Kee Hojin
• Ly Tai A
• Petersen Newton G
• Washington Jeffrey D
• Yi Haoran
• Blasig Dustyn K

Classifications

• G06F8/48

  Incremental compilation (software reuse G06F8/36) · CPC title

• G06F8/447

  Target code generation · CPC title

• G06F8/34

  Graphical or visual programming · CPC title

• G06F8/49

  Partial evaluation · CPC title

• G06F8/41 Primary

  Compilation · CPC title