Method and system for anticipatory optimization of computer programs

Claim 3

The method of claim 1 wherein the identifying of an optimization selects one of a plurality of optimizations that can be applied when translating a high-level computer program into a low-level computer program.

Claim 4

The method of claim 2 wherein the additional optimizations can be defined by a developer of the high-level computer program.

Claim 5

The method of claim 1 wherein the high-level computer program and the low-level computer program are represented by an abstract syntax tree.

Claim 6

The method of claim 1 wherein the identifying and indicating are performed by high-level computational construct transforms.

Claim 7

The method of claim 1 including generating code for the low-level computer program.

Claim 8

The method of claim 1 , wherein the high-level computational constructs are represented by matrices.

Claim 11

The method of claim 8 , wherein the high-level computational constructs are represented by matrices.

Claim 14

The method of claim 10 wherein the analyzing, storing, and translating are performed by transforms that implement the optimization techniques.

Claim 15

The method of claim 11 including defining a new high-level computational construct and providing a transform for that new high-level computational construct.

Claim 16

The method of claim 10 including defining a new high-level computational construct and providing a plurality of transforms that define all transformations of the new high-level computational construct.

Claim 17

The method of claim 13 wherein the transforms define all optimization behaviors of the new high-level computational construct.

Claim 18

The method of claim 13 wherein the transforms define multiple implementations of the new high-level computational construct.

Claim 19

The method of claim 13 wherein the transforms define various optimizations to apply to the new high-level computational construct in combination with other high-level computational constructs.

Claim 20

The method of claim 13 wherein the transforms define modifications to optimization tags to express interdependencies among the optimization tags.

Claim 21

The method of claim 13 wherein modifiers within optimization tags are invoked based on occurrences of named optimization events.

Claim 22

The method of claim 10 wherein the high-level computer program is represented in a tree data structure.

Claim 23

The method of claim 10 , wherein the high-level computational constructs are represented by matrices.

Claim 24

The method of claim 20 , wherein the high-level computational constructs are represented by matrices.

Claim 27

The method of claim 22 wherein the optimization tags express an implementation of the optimization in an abstract form.

Claim 28

The method of claim 23 whereby the abstract form indicates one of a plurality of low-level implementations of the high-level computational construct.

Claim 29

The method of claim 23 whereby further optimizations can be identified from the optimization tags.

Claim 30

The method of claim 22 wherein the optimization tags include modifiers that specify variations in the optimizations.

Claim 31

The method of claim 26 wherein one modifier takes precedence over a variation specified by another modifier.

Claim 32

The method of claim 26 wherein one modifier indicates that an expression should be moved outside a loop.

Claim 33

The method of claim 26 wherein one modifier indicates that an expression is a constant.

Claim 34

The method of claim 22 wherein modifiers within optimization tags are invoked based on occurrences of named optimization events.

Claim 35

The method of claim 22 wherein a transform expresses high-level structure of an implementation of optimizations indicated by the optimization tags.

Claim 36

The method of claim 22 wherein a transform expresses low-level structure of optimizations indicated by the optimization tags.

Claim 37

The method of claim 22 wherein the transforms are provided so that new transforms can be provided without modification to the applying of the transforms.

Claim 38

The method of claim 22 wherein the annotations are stored separately from the high-level implementation of the computer program so that the annotations can be manipulated separately from the computer program.

Claim 39

The method of claim 22 including generating a low-level implementation of the computer program in accordance with the indicated optimizations that are expressed at an implementation-independent level.

Claim 40

The method of claim 22 wherein a transform indicates that a low-level implementation of a computational construct can be moved outside of an iteration statement.

Claim 41

The method of claim 22 wherein a transform indicates that an iteration control statement should be unwrapped.

Claim 42

The method of claim 22 wherein an optimization tag indicates an optimization of the low-level implementation and thereby avoiding analysis of a low-level implementation to identify optimizations.

Claim 43

A computer system for optimizing a computer program when transforming a high-level representation of the computer program into a low-level representation of the computer program in accordance with an analysis of the high-level representation, comprising: a inline function component for determining whether any invocations of functions in the high-level representation should be transformed into inline execution of the functions; an eliminate barriers component for determining whether any computational constructs of the high-level representation can be transformed to permit identifying certain optimizations; an add optimization tag component for adding optimization tags to the high-level representation that indicate optimization that may be applied when generating the code; and a code generation component for generating a low-level representation that is optimized in accordance with the added optimization tags.

Claim 44

A computer system for optimizing a computer program when transforming a high-level representation of the computer program into a low-level representation of the computer program in accordance with an analysis of the high-level representation, comprising: a inline function component for determining whether any invocations of functions in the high-level representation should be transformed into inline execution of the functions; an eliminate barriers component for determining whether any computational constructs of the high-level representation can be transformed to permit identifying certain optimizations; an add optimization tag component for adding optimization tags to the high-level representation that indicate optimization that may be applied when generating the code; and a code generation component for generating a low-level representation that is optimized in accordance with the added optimization tags.

Claim 45

The computer system of claim 39 wherein the high-level representation is a tree data structure and each component visits nodes of the tree in one or more depth-first, left-to-right traversals of the tree data structure.

Claim 46

The computer system of claim 39 wherein each component invokes transform modules that are defined to be used by that component.

Claim 47

The computer system of claim 39 wherein the add optimization tag component identifies optimization tags that have already been added to the high-level representation that can be migrated to a higher level in the representation.

Claim 48

The computer system of claim 42 wherein the identified optimization tags are coalesced into a single optimization tag.

Claim 49

Computer-readable medium containing instructions for causing a computer system to optimize a high-level computer program using high-level computational constructs that is to be translated into a low-level computer program using low-level computational constructs, the high-level computational constructs including high-level operands that are composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, by: selecting a statement of the high-level computer program, the selected statement having a high-level operator and high-level operands, each high-level operand having implementing low-level computational constructs that implement the behavior of the high-level operand; identifying an optimization of the implementing low-level computational constructs that would result in an optimized translation of the selected statement into the low-level computational constructs; when an optimization has been identified, indicating that the identified optimization can be applied to the selected statement of the high-level computer program; and when translating the selected statement of the high-level computer program to the low-level computer program, applying the indicated optimization to the low-level computational constructs implementing the behavior of the selected statement wherein the optimizations are identified from the high-level computer program rather than on the low-level computer program.

Claim 50

Computer-readable medium containing instructions for causing a computer system to optimize a high-level computer program using high-level computational constructs that is to be translated into a low-level computer program using low-level computational constructs, the high-level computational constructs including high-level operands that are composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, by: selecting a statement of the high-level computer program, the selected statement having a high-level operator and high-level operands, each high-level operand having implementing low-level computational constructs that implement the behavior of the high-level operand; identifying an optimization of the implementing low-level computational constructs that would result in an optimized translation of the selected statement into the low-level computational constructs; when an optimization has been identified, indicating that the identified optimization can be applied to the selected statement of the high-level computer program; and when translating the selected statement of the high-level computer program to the low-level computer program, applying the indicated optimization to the low-level computational constructs implementing the behavior of the selected statement wherein the optimizations are identified from the high-level computer program rather than on the low-level computer program.

Claim 51

The computer-readable medium of claim 44 wherein the identifying of an optimization selects one of a plurality of optimizations that can be applied when translating a high-level computer program into a low-level computer program.

Claim 52

The computer-readable medium of claim 45 wherein the additional optimizations can be defined by a developer of the high-level computer program.

Claim 53

The computer-readable medium of claim 44 wherein the high-level computer program and the low-level computer program are represented by an abstract syntax tree.

Claim 54

The computer-readable medium of claim 44 wherein the identifying and indicating are performed by high-level computational construct transforms.

Claim 55

The computer-readable medium of claim 44 including generating code from the low-level computer program.

Claim 56

The computer-readable medium of claim 44 wherein a modifier of an optimization further indicates a variation in the optimization.

Claim 57

The computer-readable medium of claim 44 including mediating various modifiers of an optimization to resolve any inconsistencies among the modifiers.

Claim 58

The computer-readable medium of claim 44 including generating the low-level computer program with optimization without analyzing the low-level computational construct.

Claim 59

The computer-readable medium of claim 44 , wherein the high-level computational constructs are represented by matrices.