Compiler optimizations for vector operations that are reformatting-resistant

Patent metadata

Field	Value
Publication number	US-9886252-B2
Application number	US-201514840695-A
Country	US
Kind code	B2
Filing date	Aug 31, 2015
Priority date	Aug 17, 2015
Publication date	Feb 6, 2018
Grant date	Feb 6, 2018

Abstract

An optimizing compiler includes a vector optimization mechanism that optimizes vector operations that are reformatting-resistant, such as source instructions that do not have a corresponding reformatting operation, sink instructions that do not have a corresponding reformatting operation, a source instruction that is a scalar value, a sink instruction that may produce a scalar value, and an internal operation that depends on lanes being in a specified order. The ability to optimize vector instructions that are reformatting-resistant reduces the number of operations to improve the run-time performance of the code.

First claim

The invention claimed is:

1. An apparatus comprising:
at least one processor;
a memory coupled to the at least one processor;
a computer program residing in the memory, the computer program including a plurality of instructions that includes at least one vector operation and that includes a plurality of reformatting-resistant vector operations, wherein the plurality of formatting-resistant vector operations includes a source instruction without a corresponding reformatting operation; and
a compiler residing in the memory and executed by the at least one processor, the compiler including a vector instruction optimization mechanism that optimizes at least one of the plurality of reformatting-resistant vector operations in the computer program to enhance run-time performance of the computer program.

2. The apparatus of claim 1 wherein the plurality of reformatting-resistant vector operations comprises a sink instruction without a corresponding reformatting operation.

3. The apparatus of claim 1 wherein the plurality of reformatting-resistant vector operations comprises a source instruction that operates on a scalar value.

4. The apparatus of claim 1 wherein the plurality of reformatting-resistant vector operations comprises a sink instruction that can produce a scalar value.

5. The apparatus of claim 1 wherein the plurality of reformatting-resistant vector operations comprises an internal operation that depends on lanes being in a specified order.

6. The apparatus of claim 1 wherein the vector instruction optimization mechanism analyzes an existing code portion in the computer program, determines a proposed change to the existing code portion in the computer program, and when the proposed change to the existing code portion has a cost less than a cost of the existing code portion, the vector instruction optimization mechanism modifies the existing code portion with the proposed change.

7. The apparatus of claim 1 wherein the vector instruction optimization mechanism optimizes the at least one reformatting-resistant operation in the computer program by performing the steps of:
(a) finding all data flow subgraphs in the computer program;
(b) identifying source instructions, sink instructions, and internal instructions that are reformatting-resistant;
(c) selecting a data flow subgraph;
(d) determining a preferred vector element order;
(e) determining a savings of removing reformatting instructions from source instructions and sink instructions that have the reformatting instructions;
(f) determining a cost of inserting reformatting and other adjustment instructions at sources, sinks and internal instructions that are reformatting-resistant;
(g) when the savings minus the cost is not negative, removing the reformatting instructions from source instructions and sink instructions that have the reformatting instructions, and inserting the reformatting and other adjustment instructions; and
(h) when there are more data flow subgraphs to process, return to step (c) and continue processing until there are no more data flow subgraphs to process.

8. The apparatus of claim 1 wherein the at least one reformatting-resistant instruction is selected from the group comprising:
a source instruction without a corresponding reformatting operation;
a sink instruction without a corresponding reformatting operation;
a source instruction that operates on a scalar value;
a sink instruction that can produce a scalar value; and
an internal operation that depends on lanes being in a specified order.

9. An article of manufacture comprising software stored on a computer readable storage medium, the software comprising:
a compiler that compiles a computer program that includes a plurality of instructions that includes at least one vector operation and that includes a plurality of reformatting-resistant vector operations, wherein the plurality of formatting-resistant vector operations includes a source instruction without a corresponding reformatting operation, the compiler comprising a vector instruction optimization mechanism that optimizes at least one of the plurality of reformatting-resistant vector operations in the computer program to enhance run-time performance of the computer program.

10. The article of manufacture of claim 9 wherein the plurality of reformatting-resistant vector operations comprises a sink instruction without a corresponding reformatting operation.

11. The article of manufacture of claim 9 wherein the plurality of reformatting-resistant vector operations comprises a source instruction that operates on a scalar value.

12. The article of manufacture of claim 9 wherein the plurality of reformatting-resistant vector operations comprises a sink instruction that can produce a scalar value.

13. The article of manufacture of claim 9 wherein the plurality of reformatting-resistant vector operations comprises an internal operation that depends on lanes being in a specified order.

14. The article of manufacture of claim 9 wherein the vector instruction optimization mechanism analyzes an existing code portion in the computer program, determines a proposed change to the existing code portion in the computer program, and when the proposed change to the existing code portion has a cost less than a cost of the existing code portion, the vector instruction optimization mechanism modifies the existing code portion with the proposed change.

15. The article of manufacture of claim 9 wherein the vector instruction optimization mechanism optimizes the at least one reformatting-resistant operation in the computer program by performing the steps of:
(a) finding all data flow subgraphs in the computer program;
(b) identifying source instructions, sink instructions, and internal instructions that are reformatting-resistant;
(c) selecting a data flow subgraph;
(d) determining a preferred vector element order;
(e) determining a savings of removing reformatting instructions from source instructions and sink instructions that have the reformatting instructions;
(f) determining a cost of inserting reformatting and other adjustment instructions at sources, sinks and internal instructions that are reformatting-resistant;
(g) when the savings minus the cost is not negative, removing the reformatting instructions from source instructions and sink instructions that have the reformatting instructions, and inserting the reformatting and other adjustment instructions; and
(h) when there are more data flow subgraphs to process, return to step (c) and continue processing until there are no more data flow subgraphs to process.

16. The article of manufacture of claim 9 wherein the at least one reformatting-resistant instruction is selected from the group comprising:
a source instruction without a corresponding reformatting operation;
a sink instruction without a corresponding reformatting operation;
a source instruction that operates on a scalar value;
a sink instruction that can produce a scalar value; and
an internal operation that depends on lanes being in a specified order.

Assignees

• IBM

Inventors

• Gschwind Michael Karl
• Schmidt William J

Classifications

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title