Vectorization in an optimizing compiler

Patent metadata

Field	Value
Publication number	US-9047077-B2
Application number	US-201313791929-A
Country	US
Kind code	B2
Filing date	Mar 9, 2013
Priority date	Feb 21, 2013
Publication date	Jun 2, 2015
Grant date	Jun 2, 2015

Abstract

An optimizing compiler includes a vectorization mechanism that optimizes a computer program by substituting code that includes one or more vector instructions (vectorized code) for one or more scalar instructions. The cost of the vectorized code is compared to the cost of the code with only scalar instructions. When the cost of the vectorized code is less than the cost of the code with only scalar instructions, the vectorization mechanism determines whether the vectorized code will likely result in processor stalls. If not, the vectorization mechanism substitutes the vectorized code for the code with only scalar instructions. When the vectorized code will likely result in processor stalls, the vectorization mechanism does not substitute the vectorized code, and the code with only scalar instructions remains in the computer program.

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 in an instruction set that includes a plurality of vector instructions that operate on data in a plurality of vector registers; and
an optimizing compiler residing in the memory and executed by the at least one processor, the optimizing compiler including a vectorization mechanism that analyzes a portion of the computer program, generates from a first set of instructions in the computer program that does not include any of the plurality of vector instructions a second set of instructions that includes at least one of the plurality of vector instructions, determines when a second cost of processing the second set of instructions is less than a first cost of processing the first set of instructions, and when the second cost is less than the first cost, determining when the second set of instructions is likely to cause a processor running the computer program to stall when executing the second set of instructions by determining a ratio of vector instructions in the second set of instructions to total instructions in the second set of instructions, and when the second set of instructions is not likely to cause the processor running the computer program to stall when executing the second set of instructions, the vectorization mechanism substitutes the second set of instructions for the first set of instructions in the computer program, and when the second cost is not less than the first cost or when the second set of instructions is likely to cause the processor running the computer program to stall when executing the second set of instructions, the vectorization mechanism does not substitute the second set of instructions for the first set of instructions in the computer program.

2. The apparatus of claim 1 wherein the vectorization mechanism determines when the second set of instructions is likely to cause the processor running the computer program to stall by determining when the ratio is less than a predetermined threshold value, the second set of instructions is not likely to cause the processor running the computer program to stall, and by determining when the ratio is greater than or equal to the predetermined threshold, the second set of instructions is likely to cause the processor running the computer program to stall.

3. The apparatus of claim 2 wherein the vectorization mechanism increases the second cost by a predetermined multiplier factor when the second cost exceeds the predetermined threshold.

4. The apparatus of claim 1 wherein the vectorization mechanism determines when the second set of instructions is likely to cause a processor running the computer program to stall when executing the second set of instructions only when a number of instructions in the second set of instructions exceeds a predetermined threshold.

5. The apparatus of claim 1 wherein the vectorization mechanism determines when the second set of instructions is likely to cause the processor running the computer program to stall by determining a ratio of cost of vector instructions in the second set of instructions to total cost of all instructions in the second set of instructions, and when the ratio is less than a predetermined threshold value, the second set of instructions is not likely to cause the processor running the computer program to stall, and when the ratio is greater than or equal to the predetermined threshold, the second set of instructions is likely to cause the processor running the computer program to stall.

6. An article of manufacture comprising software stored on a non-transitory computer readable storage medium, the software comprising:
an optimizing compiler including a vectorization mechanism that analyzes a portion of a computer program that includes a plurality of instructions for execution on at least one processor that includes a vector processing unit that processes a plurality of vector instructions that operate on data in a plurality of vector registers, generates from a first set of instructions in the computer program that does not include any of the plurality of vector instructions a second set of instructions that includes at least one of the plurality of vector instructions, determines when a second cost of processing the second set of instructions is less than a first cost of processing the first set of instructions, and when the second cost is less than the first cost, determining when the second set of instructions is likely to cause a processor running the computer program to stall when executing the second set of instructions by determining a ratio of vector instructions in the second set of instructions to total instructions in the second set of instructions, and when the second set of instructions is not likely to cause the processor running the computer program to stall when executing the second set of instructions, the vectorization mechanism substitutes the second set of instructions for the first set of instructions in the computer program, and when the second cost is not less than the first cost or when the second set of instructions is likely to cause the at least one processor to stall when executing the second set of instructions, the vectorization mechanism does not substitute the second set of instructions for the first set of instructions in the computer program.

7. The article of manufacture of claim 6 wherein the vectorization mechanism determines when the second set of instructions is likely to cause the processor running the computer program to stall by determining when the ratio is less than a predetermined threshold value, the second set of instructions is not likely to cause the processor running the computer program to stall, and by determining when the ratio is greater than or equal to the predetermined threshold, the second set of instructions is likely to cause the processor running the computer program to stall.

8. The article of manufacture of claim 7 wherein the vectorization mechanism increases the second cost by a predetermined multiplier factor when the second cost exceeds the predetermined threshold.

9. The article of manufacture of claim 6 wherein the vectorization mechanism determines when the second set of instructions is likely to cause a processor running the computer program to stall when executing the second set of instructions only when a number of instructions in the second set of instructions exceeds a predetermined threshold.

10. The article of manufacture of claim 6 wherein the vectorization mechanism determines when the second set of instructions is likely to cause the processor running the computer program to stall by determining a ratio of cost of vector instructions in the second set of instructions to total cost of all instructions in the second set of instructions, and when the ratio is less than a predetermined threshold value, the second set of instructions is not likely to cause the processor running the computer program to stall, and when the ratio is greater than or equal to the predetermined threshold, the second set of instructions is likely to cause the processor running the computer program to stall.

11. 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 in an instruction set that includes a plurality of vector instructions that operate on data in a plurality of vector registers; and
an optimizing compiler residing in the memory and executed by the at least o

Assignees

• IBM

Inventors

• Schmidt William J

Classifications

• G06F8/443 Primary

  Optimisation · CPC title

• G06F9/3001 Primary

  Arithmetic instructions · CPC title

• G06F8/41

  Compilation · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• G06F11/36

  Prevention of errors by analysis, debugging or testing of software · CPC title