Stable transitions in the presence of conditionals for an advanced dual-representation polyhedral loop transformation framework

• US 8,056,065 B2
• Filed: 09/26/2007
• Issued: 11/08/2011
• Est. Priority Date: 09/26/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: O'Brien, Kathryn M., Eichenberger, Alexandre E., O'Brien, John K. P., Vasilache, Nicolas T.
• Primary Examiner(s): DAO, THUY CHAN
• Application Number:
  US11/861,512
• Publication Number:
  US 20090083722A1
• Time in Patent Office: 1,504 Days
• Field of Search: None
• US Class Current: 717/151
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

Mechanisms for stable transitions in the presence of conditionals for an advanced dual-representation polyhedral loop transformation framework are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization. In addition, mechanisms are provided for ensuring code stabilization in the presence of conditions such that code bloat is not encountered during re-entrance.

Claims

1. A method, in a data processing system, for optimizing program code, comprising:

receiving source code for a program in a compiler executed by at least one processor of the data processing system;

transforming, by the at least one processor, the source code into a first program statement view of the source code;

transforming, by the at least one processor, the first program statement view of the source code into a program loop view of the source code;

applying, by the at least one processor, one or more code generation optimizations to the program loop view of the source code to generate first optimized code;

generating, by a polyhedral rescan module of a re-entrance path executed by the at least one processor, a second program statement view of the source code based on the first optimized code and information maintained for each statement in the first program statement view, describing how the source code was transformed into the first program statement view;

generating, by the at least one processor, second optimized code based on the second program statement view of the source code; and

outputting, by the at least one processor, optimized code, based on the second optimized code, to the compiler for use in generating executable code for execution on a computing device, wherein generating the second program statement view via the re-entrance path comprises recombining instances of statements in the program loop view prior to a polyhedral rescan operation of the re-entrance path being performed on the program loop view of the source code.

2. The method of claim 1, wherein the program loop view of the source code is a hierarchical ordered graph of the source code where each inner node of the graph corresponds to an iteration domain at a given depth in a loop nest structure, and wherein each leaf node of the graph has a list of statements that are enclosed by a loop nest corresponding to the leaf node.

3. The method of claim 2, wherein each node in the graph is associated with a domain, and wherein each domain is a polyhedral representation of a domain associated with statements enclosed by the node and projected to reflect a depth of the node within the graph.

4. The method of claim 1, wherein, each statement in the first program statement view has an associated schedule data structure, and wherein the schedule data structure is maintained and stored in association with corresponding statements in the program loop view of the source code.

5. The method of claim 1, further comprising:

detecting, in the program loop view of the source code, nodes containing hoistable conditional statements;

marking a parent node as a boundary node for a re-entrance operation;

identifying for each marked boundary node of a given depth in the program loop view of the source code, all instances of a given statement; and

generating, in the first optimized code, a single compound statement representing all of the instances of the given statement at the given depth in the program loop view of the source code.

6. The method of claim 5, further comprising:

setting a new domain for the compound statement as a union of domains over all instances of the given statement.

7. The method of claim 1, wherein the first program statement view of the source code is a representation of the source code in which each statement in the source code is associated with a polyhedron describing a domain of the statement identifying a number of times the statement iterates in each loop dimension, and a schedule of the statement identifying when the statement is executed relative to the other statements in the source code, wherein the schedule is specified as a structured matrix, and wherein the program loop view organizes statements in the first program statement view into groups of statements according to iterations of loops with which the statements correspond such that at least one instance of a statement in the first program statement view is separated into a plurality of instances of the statement, one for each group of statements corresponding to iterations of loops.

8. The method of claim 1, wherein each instance of a same statement in the program loop view has a separate sub-domain of a domain associated with a corresponding statement in the first program statement view, and separate schedule, and wherein as part of processing according to the re-entrance path, each of the instances of a same statement in the program loop view is operated on separately with regard to optimizations applied to the statements.

9. A computer program product comprising a computer readable storage medium having a computer readable program stored thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive source code for a program in a compiler;

transform the source code into a first program statement view of the source code;

transform the first program statement view of the source code into a program loop view of the source code;

apply one or more code generation optimizations to the program loop view of the source code to generate first optimized code;

generate, by a polyhedral rescan module of a re-entrance path, a second program statement view of the source code based on the first optimized code and information maintained for each statement in the first program statement view, describing how the source code was transformed into the first program statement view;

generate second optimized code based on the second program statement view of the source code; and

output optimized code, based on the second optimized code, to the compiler for use in generating executable code for execution on a computing device, wherein generating the second program statement view via the re-entrance path comprises recombining instances of statements in the program loop view prior to a polyhedral rescan operation of the re-entrance path being performed on the program loop view of the source code.

10. The computer program product of claim 9, wherein the program loop view of the source code is a hierarchical ordered graph of the source code where each inner node of the graph corresponds to an iteration domain at a given depth in a loop nest structure, and wherein each leaf node of the graph has a list of statements that are enclosed by a loop nest corresponding to the leaf node.

11. The computer program product of claim 10, wherein each node in the graph is associated with a domain, and wherein each domain is a polyhedral representation of a domain associated with statements enclosed by the node and projected to reflect a depth of the node within the graph.

12. The computer program product of claim 9, wherein, each statement in the first program statement view has an associated schedule data structure, and wherein the schedule data structure is maintained and stored in association with corresponding statements in the program loop view of the source code.

13. The computer program product of claim 9, wherein the computer readable program further causes the computing device to:

detect, in the program loop view of the source code, nodes containing hoistable conditional statements;

mark a parent node as a boundary node for a re-entrance operation;

identify for each marked boundary node of a given depth in the program loop view of the source code, all instances of a given statement; and

generate, in the first optimized code, a single compound statement representing all of the instances of the given statement at the given depth in the program loop view of the source code.

14. The computer program product of claim 13, wherein the computer readable program further causes the computing device to:

set a new domain for the compound statement as a union of domains over all instances of the given statement.

15. A system, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive source code for a program in a compiler;

transform the source code into a first program statement view of the source code;

transform the first program statement view of the source code into a program loop view of the source code;

apply one or more code generation optimizations to the program loop view of the source code to generate first optimized code;

generate, by a polyhedral rescan module of a re-entrance path, a second program statement view of the source code based on the first optimized code and information maintained for each statement in the first program statement view, describing how the source code was transformed into the first program statement view;

generate second optimized code based on the second program statement view of the source code; and

output optimized code, based on the second optimized code, to the compiler for use in generating executable code for execution on a computing device, wherein generating the second program statement view via the re-entrance path comprises recombining instances of statements in the program loop view prior to a polyhedral rescan operation of the re-entrance path being performed on the program loop view of the source code.

16. The system of claim 15, wherein the program loop view of the source code is a hierarchical ordered graph of the source code where each inner node of the graph corresponds to an iteration domain at a given depth in a loop nest structure, and wherein each leaf node of the graph has a list of statements that are enclosed by a loop nest corresponding to the leaf node.

17. The system of claim 16, wherein each node in the graph is associated with a domain, and wherein each domain is a polyhedral representation of a domain associated with statements enclosed by the node and projected to reflect a depth of the node within the graph.

18. The system of claim 15, wherein, each statement in the first program statement view has an associated schedule data structure, and wherein the schedule data structure is maintained and stored in association with corresponding statements in the program loop view of the source code.

19. The system of claim 15, wherein the instructions further cause the processor to:

detect, in the program loop view of the source code, nodes containing hoistable conditional statements;

mark a parent node as a boundary node for a re-entrance operation;

identify for each marked boundary node of a given depth in the program loop view of the source code, all instances of a given statement; and

generate, in the first optimized code, a single compound statement representing all of the instances of the given statement at the given depth in the program loop view of the source code.

20. The system of claim 19, wherein the instructions further cause the processor to:

set a new domain for the compound statement as a union of domains over all instances of the given statement.