Selective code generation optimization for an advanced dual-representation polyhedral loop transformation framework

• US 8,087,010 B2
• Filed: 09/26/2007
• Issued: 12/27/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: Eichenberger, Alexandre E., O'Brien, John K. P., O'Brien, Kathryn M., Vasilache, Nicolas T.
• Primary Examiner(s): Das, Chameli
• Application Number:
  US11/861,493
• Publication Number:
  US 20090083702A1
• Time in Patent Office: 1,553 Days
• Field of Search: None
• US Class Current: 717/150
• CPC Class Codes: G06F 8/4452 Software pipelining

Abstract

Mechanisms for selective code generation optimization 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.

Claims

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

receiving, by the processor, source code for a program in a compiler;

transforming, by the processor, the source code into a program statement view of the source code;

transforming, by the processor, the program statement view of the source code into a program loop view of the source code, wherein the program loop view is an abstract syntax tree (AST) representation of the source code generated by applying a loop transformation on the program statement view, and wherein the AST of the program loop view comprises a plurality of nodes with each node representing a loop in the source code;

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

outputting, by the processor, the optimized code to a compiler for use in generating executable code for execution on a computing device, wherein the one or more code generation optimizations transform the program loop view of the source code into the optimized code while maintaining both program and schedule equivalence between the optimized code and the program statement view of the source code, wherein each code generation optimization of the one or more code generation optimizations visits a list of nodes of the AST in the program loop view for which the code generation optimization is to be applied and a propagation mode indicator that identifies a manner by which the list of nodes is to be processed by the code generation optimization.

2. The method of claim 1, wherein the list of nodes is a list of prefix vectors for nodes in the program loop view of the source code, wherein a prefix vector is a vector of numbers which indicates a corresponding node'"'"'s path from a root node to the corresponding node in the program loop view of the source code.

3. The method of claim 2, wherein the propagation mode indicator identifies whether the code generation optimization is to be applied to all nodes in the program loop view, only child nodes of an identified node, or only specified nodes.

4. The method of claim 3, wherein applying one or more code generation optimizations to the program loop view of the source code to generate optimized code comprises:

performing a first pass on the program loop view of the source code, based on the list of nodes and the propagation mode indicator to flag nodes in the program loop view of the source code to which the one or more code generation optimizations are to be applied; and

executing a code generation optimization algorithm corresponding to the one or more code generation optimizations on each flagged node in the program loop view of the source code.

5. The method of claim 4, wherein executing a code generation optimization algorithm on each flagged node comprises:

instantiating a visitor to perform an outermost scan of the nodes of the program loop view of the source code to identify one or more flagged nodes;

applying a core function of the code generation optimization algorithm to the one or more flagged nodes;

determining if domains associated with the one or more flagged nodes are modified by the core function; and

returning a list of new domains to replace previous domains associated with the one or more flagged nodes.

6. The method of claim 5, wherein applying the core function of the code generation optimization comprises:

generating a new node and a corresponding subtree for each new domain; and

applying a propagation function to each path to every new leaf node in the subtrees for each new domain.

7. The method of claim 1, wherein the one or more code generation optimizations comprises at least one of simplify, simplify-unstretch, simplify-trivial-modulo-remapping, extract-kernel, if-hoist/if-hoist-gentle, if-hoist-brutal, substitute-modulo, or loop-unroll.

8. The method of claim 1, further comprising:

identifying parallel loops in the program loop view; and

setting a parallel bit in association with the identified parallel loops in the optimized code.

9. The method of claim 1, further comprising:

transforming the program loop view of the source code back into a second program statement view following application of the one or more code generation optimizations;

performing one or more loop optimizations on the second program statement view to generate loop optimized code;

transforming the loop optimized code into a program loop view of the loop optimized code; and

applying the one or more code generation optimizations to the program loop view of the loop optimized code to generate the optimized code.

10. The method of claim 1, wherein the loop transformation is a polyhedral loop transformation and wherein each node in the AST of the program loop view is associated with a separate polyhedron representing a corresponding loop in the source code.

11. A computer program product comprising a computer useable 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 program statement view of the source code;

transform the program statement view of the source code into a program loop view of the source code, wherein the program loop view is an abstract syntax tree (AST) representation of the source code generated by applying a loop transformation on the program statement view, and wherein the AST of the program loop view comprises a plurality of nodes with each node representing a loop in the source code;

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

output the optimized code to a compiler for use in generating executable code for execution on a computing device, wherein the one or more code generation optimizations transform the program loop view of the source code into the optimized code while maintaining both program and schedule equivalence between the optimized code and the program statement view of the source code, wherein each code generation optimization of the one or more code generation optimizations visits a list of nodes of the AST in the program loop view for which the code generation optimization is to be applied and a propagation mode indicator that identifies a manner by which the list of nodes is to be processed by the code generation optimization.

12. The computer program product of claim 11, wherein the list of nodes is a list of prefix vectors for nodes in the program loop view of the source code, wherein a prefix vector is a vector of numbers which indicates a corresponding node'"'"'s path from a root node to the corresponding node in the program loop view of the source code.

13. The computer program product of claim 12, wherein the propagation mode indicator identifies whether the code generation optimization is to be applied to all nodes in the program loop view, only child nodes of an identified node, or only specified nodes.

14. The computer program product of claim 13, wherein the computer readable program causes the computing device to apply one or more code generation optimizations to the program loop view of the source code to generate optimized code by:

performing a first pass on the program loop view of the source code, based on the list of nodes and the propagation mode indicator to flag nodes in the program loop view of the source code to which the one or more code generation optimizations are to be applied; and

executing a code generation optimization algorithm corresponding to the one or more code generation optimizations on each flagged node in the program loop view of the source code.

15. The computer program product of claim 14, wherein the computer readable program causes the computing device to execute a code generation optimization algorithm on each flagged node by:

instantiating a visitor to perform an outermost scan of the nodes of the program loop view of the source code to identify one or more flagged nodes;

applying a core function of the code generation optimization algorithm to the one or more flagged nodes;

determining if domains associated with the one or more flagged nodes are modified by the core function; and

returning a list of new domains to replace previous domains associated with the one or more flagged nodes.

16. The computer program product of claim 15, wherein the computer readable program causes the computing device to apply the core function of the code generation optimization by:

generating a new node and a corresponding subtree for each new domain; and

applying a propagation function to each path to every new leaf node in the subtrees for each new domain.

17. The computer program product of claim 11, wherein the one or more code generation optimizations comprises at least one of simplify, simplify-unstretch, simplify-trivial-modulo-remapping, extract-kernel, if-hoist/if-hoist-gentle, if-hoist-brutal, substitute-modulo, or loop-unroll.

18. The computer program product of claim 11, wherein the computer readable program further causes the computing device to;

identify parallel loops in the program loop view; and

set a parallel bit in association with the identified parallel loops in the optimized code.

19. The computer program product of claim 11, wherein the loop transformation is a polyhedral loop transformation and wherein each node in the AST of the program loop view is associated with a separate polyhedron representing a corresponding loop in the source code.

20. 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 program statement view of the source code;

transform the program statement view of the source code into a program loop view of the source code, wherein the program loop view is an abstract syntax tree (AST) representation of the source code generated by applying a loop transformation on the program statement view, and wherein the AST of the program loop view comprises a plurality of nodes with each node representing a loop in the source code;

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

output the optimized code to a compiler for use in generating executable code for execution on a computing device, wherein the one or more code generation optimizations transform the program loop view of the source code into the optimized code while maintaining both program and schedule equivalence between the optimized code and the program statement view of the source code, wherein each code generation optimization of the one or more code generation optimizations visits a list of nodes of the AST in the program loop view for which the code generation optimization is to be applied and a propagation mode indicator that identifies a manner by which the list of nodes is to be processed by the code generation optimization.