High-level loop fusion

• US 5,822,593 A
• Filed: 12/06/1996
• Issued: 10/13/1998
• Est. Priority Date: 12/06/1996
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mendhekar, Anurag D., Lamping, John O., Kiczales, Gregor J.
• Primary Examiner(s): Voel, Emanuel Todd
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/764,101
• Time in Patent Office: 676 Days
• Field of Search: 395/709, 395/705, 395/500, 395/704, 395/710, 395/588, 395/676
• US Class Current: 717/161
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs

Abstract

A processor is provided with a software program specifying an overall computation that includes operations. Each operation implies a set of subcomputations, without explicitly specifying a control structure for carrying out the subcomputations according to a particular sequencing. The operations include a first and a second operation, and the provided software program further specifies how the first and second operations are combined in the overall computation. For example, the first and second operations can each imply, respectively, a first and a second computational loop, the first loop including the subcomputations of the first operation, the second loop including the subcomputations of the second operation. A description of possible sequencings of subcomputations of the first and second operations is provided, to be used in implementing the specified combination of the first and second operations, the description including a set of constraints on the sequencing of subcomputations of the first and second operations. A software program is automatically generated that includes a combined operation implementing the specified combination of the first and second operations. The combined operation has a control structure for carrying out the subcomputations of the first and second operations in accordance with the constraints. This control structure can be, for example, a computational loop. If the first and second operations imply, respectively, first and second computational loops, the control structure of the combined operation can be, for example, a computational loop including a fusion of the first and second loops.

Claims

1. A method comprising the steps of:

(a) providing a processor with a software program specifying a computation (hereinafter, "the overall computation") including a plurality of operations,

each of the operations implying a set of subcomputations without explicitly specifying a control structure for carrying out the subcomputations of said set according to a particular sequencing,

the plurality of operations including a first operation and a second operation, the software program further specifying how the first and second operations are combined in the overall computation;

(b) providing a processor with a description of possible sequencings of subcomputations of the first and second operations, to be used in implementing the specified combination of the first and second operations, the description comprising predetermined set of fusibility constraints on the sequencing of subcomputations of the first and second operations; and

(c) generating automatically with a processor a software program including a combined operation, the combined operation implementing the specified combination of the first and second operations, the combined operation having a control structure for carrying out the subcomputations of the first and second operations in accordance with the predetermined set of fusibility constraints.

2. The method of claim 1 wherein the control structure of the combined operation comprises a computational loop.

3. The method of claim 1 wherein the first and second operations each imply, respectively, a first and a second computational loop, the first loop including the subcomputations of the first operation, the second loop including the subcomputations of the second operation, neither the first nor the second operation explicitly specifying a control structure for carrying out the subcomputations of, respectively, the first and second loops according to a particular sequencing.

4. The method of claim 3 wherein the control structure of the combined operation comprises a computational loop including a fusion of the first and second loops.

5. The method of claim 1 wherein:

the provided software program of step (a) is a first program comprising a source code program;

the generated software program of step (c) is a second program; and

the step (c) is performed by executing with the processor of step (c) at least a portion of a language processing program distinct from said first and second programs, the language processing program being a software program for processing a source code program expressed in a programming language, the language processing program accepting the first program as an input and producing the second program as an output.

6. The method of claim 5 wherein the language processing program is selected from the group a compiler, an interpreter, a precompiler, or a preprocessor.

7. The method of claim 1 wherein the description provided in step (b) comprises a set of annotations added by a human user to the provided software program of step (a).

10. The method of claim 1 wherein the predetermined set of fusibility constraints includes at least one constraint selected from the group

a data access order constraint,

a loop organization constraint,

a demand constraint, and

a timing constraint.

11. The method of claim 1 wherein the predetermined set of fusibility constraints includes at least one mandatory constraint and at least one optional constraint.

12. The method of claim 1 wherein step (c) comprises automatically generating a constraint analysis by analyzing the predetermined set of fusibility constraints with the processor to determine if the first and second operations can be combined consistently with the predetermined set of fusibility constraints.

13. The method of claim 1 wherein step (c) comprises the constituent steps of:

generating a first graph representing the overall computation, the first graph having a plurality of nodes, each node of the first graph representing one of the operations of the overall computation, the nodes of the first graph including a first node representing the first operation and a second node representing the second operation;

annotating the first graph to reflect the predetermined set of fusibility constraints;

solving the predetermined set of fusibility constraints to determine a constraint solution representing how the first graph can be transformed, consistently with the predetermined set of fusibility constraints, into a second graph, the second graph having a plurality of nodes including a single node representing a fusion of the first and second operations; and

producing the generated software program of step (c) from the constraint solution thus determined.

14. The method of claim 13 wherein:

the step of generating the first graph comprises generating a set of computational objects each representing a node in the first graph, the set of computational objects including a first object representing the first node and a second object representing the second node; and

the steps of solving the predetermined set of fusibility constraints does not involve generating a computational object representing said single node representing the fusion of the first and second operations.

15. The method of claim 13 wherein:

the generated first graph further comprises a plurality of links representing data flows between operations, the plurality of links including a link between the first and second nodes; and

the step of solving the predetermined set of fusibility constraints comprises determining a set of fusible links from among the plurality of links.

16. The method of claim 13 wherein the step of solving the predetermined set of fusibility constraints comprises performing a unification of constraints of the set.

17. The method of claim 1 wherein:

the first operation has a large-scale operand comprising a plurality of elements, each implied subcomputation of the first operation pertaining to one element of the first operation'"'"'s operand; and

the second operation has a large-scale operand comprising a plurality of elements, each implied subcomputation of the second operation pertaining to one element of the second operation'"'"'s operand.

18. The method of claim 1 wherein the provided software program of step (a) is a program expressed in an image-processing language.

19. The method of claim 1 wherein the generated software program of step (c) is selected from the group a source code program or an executable program.

20. The method of claim 1 wherein:

the provided software program of step (a) is a source code program expressed in a programmning language, the language comprising a base language and an extension to the language, the extension comprising an operation not defined in the base language (hereinafter, "the new operation"); and

at least one of the first and second operations is the new operation.

21. A method comprising the step of transmitting information including a software program, the software program being generated according to the method of claim 1 and being identified with the generated software program of step (c) therein.

22. An article of manufacture comprising an information storage medium wherein is stored information including a software program, the software program being generated according to the method as recited in claim 1 and being identified with the generated software program of step (c) therein.

8. The method of claim I wherein the description of step (b) is provided as a general set of instructions, the instructions being applicable to various software programs, including but not limited to the software program provided in step (a).

9. The method of claim 8 wherein the step (c) is performed by executing a language processing program with the processor of step (c), the language processing program incorporating the general set of instructions.

23. An article of manufacture comprising an information storage medium wherein is stored information comprising a third software program for facilitating automatic generation by a processor of a second software program from a first software program and a sequencing description,

the first software program specifying a computation (hereinafter, "the overall computation") including a plurality of operations,

each of the operations implying a set of subcomputations without explicitly specifying a control structure for carrying out the subcomputations of said set according to a particular sequencing,

the plurality of operations including a first operation and a second operation, the software program further specifying how the first and second operations are combined in the overall computation,

the sequencing description being a description of possible sequencings of subcomputations of the first and second operations, to be used in implementing the specified combination of the first and second operations, the description comprising a predetermined set of fusibility constraints on the sequencing of subcomputations of the first and second operations,

the second software program being generated automatically by the processor under control of the third software program, the second software program including a combined operation, the combined operation implementing the specified combination of the first and second operations, the combined operation having a control structure for carrying out the subcomputations of the first and second operations in accordance with the predetermined set of fusibility constraints.

24. The article of manufacture as recited in claim 23 wherein the third software program comprises a language processing program for processing a source code program expressed in a programming language, the first software program comprising such a source code program, the language processing program accepting the first software program as an input and producing the second software program as an output.

25. The article of manufacture as recited in claim 24 wherein the language processing program is selected from the group a compiler, an interpreter, a precompiler, or a preprocessor.

26. The article of manufacture as recited in claim 24 wherein:

the first software program is a source code program expressed in a programming language, the language comprising a base language and an extension to the language, the extension comprising an operation not defined in the base language (hereinafter, "the new operation"); and

at least one of the first and second operations is the new operation.

27. Apparatus comprising:

a processor;

an instruction store, coupled to the processor, comprising an article of manufacture as recited in claim 23; and

a data store, coupled to the processor, wherein the first and second software programs and the sequencing description can be stored.

28. A method comprising the steps of:

(a) providing a processor with a description of a source code programming language, the language including a plurality of operations, each operation implying a set of subcomputations without explicitly specifying a control structure for carrying out the subcomputations of said set according to a particular sequencing;

(b) providing a processor with a description of possible sequencings of the subcomputations of each of the operations of the plurality, to be used in implementing combinations of these operations, the description of this step (b) comprising a predetermined set of fusibility constraints on the sequencing of subcomputations of each of the operations of the plurality;

(c) extending the language by providing a processor with a description of an extension to the source code language, the extension comprising an operation not included in the plurality of operations (hereinafter, "the new operation"), the new operation implying a set of subcomputations without explicitly specifying a control structure for carrying out the subcomputations of the new operation according to a particular sequencing;

(d) providing a processor with a description of possible sequencings of subcomputations of the new operation of the language, to be used in implementing combinations of the new operation with operations of the plurality, the description not explicitly relating the possible sequencings of subcomputations of the new operation to the possible sequencings of subcomputations of the operations of the plurality, the description of this step (d) comprising the predetermined set of fusibility constraints on the sequencing of subcomputations of the new operation;

(e) providing a processor with a software program expressed in the language as extended, the program specifying a computation (hereinafter, "the overall computation") including first and second operations, the first operation being an operation of the plurality of operations, the second operation being the new operation, the software program further specifying how the first and second operations are combined in the overall computation; and

(f) from the software program and the descriptions thus provided in the above-recited steps, generating automatically with a processor a software program including a combined operation, the combined operation implementing the specified combination of the first and second operations, the combined operation having a control structure for carrying out the subcomputations of the first and second operations in accordance with the constraints.