Framework for generating mixed-mode operations in loop-level simdization

• US 20050273769A1
• Filed: 08/16/2004
• Published: 12/08/2005
• Est. Priority Date: 06/07/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eichenberger, Alexandre E., Wu, Peng, Wang, Kai-Ting Amy
• Granted Patent: US 8,549,501 B2
• Time in Patent Office: Days
• US Class Current: 717/136
• CPC Class Codes: G06F 8/4452 Software pipelining

Abstract

A method, computer program product, and information handling system for generating mixed-mode operations in the compilation of program code for processors having vector or SIMD processing units is disclosed. In a preferred embodiment of the present invention, program instructions making up the body of a loop are abstracted into virtual vector instructions. These virtual vector instructions are treated, for initial code optimization purposes, as vector instructions (i.e., instructions written for the vector unit). The virtual vector instructions are eventually expanded into native code for the target processor, at which time a determination is made for each virtual vector instruction as to whether to expand the virtual vector instruction into native vector instructions, into native scalar instructions, into calls to pre-defined library functions, or into a combination of these. A cost model is used to determine the optimal choice of expansion based on hardware/software constraints, performance costs/benefits, and other criteria.

Claims

1. A computer-implemented method comprising:

identifying a loop containing instructions that operate over an array of values;

transforming the instructions into a set of virtual vector operations;

choosing, for each operation in the set of virtual vector operations, an expansion to apply to that operation, wherein the expansion is chosen from a plurality of possible expansions; and

expanding each operation in the set of virtual vector operations into a native code implementation of that operation in accordance with that operation'"'"'s corresponding chosen expansion.

2. The method of claim 1, wherein the plurality of possible expansions includes expanding an operation into vector instructions.

3. The method of claim 2, wherein the vector instructions are single-instruction multiple-datapath (SIMD) instructions.

4. The method of claim 2, wherein the plurality of possible expansions includes expanding an operation into scalar instructions.

5. The method of claim 4, wherein the plurality of possible expansions includes at least one of inserting a call to a pre-defined library function and expanding an operation into a combination of vector and scalar operations.

6. The method of claim 1, wherein the expansion for each operation in the set of vector operations is chosen according to a cost model.

7. The method of claim 6, wherein the cost model is computed based on at least one of hardware resource availability, data dependencies, and existence of pre-defined library functions for particular operations.

8. A computer program product in a computer-readable medium, comprising:

identifying means for identifying a loop containing instructions that operate over an array of values;

transforming means for transforming the instructions into a set of virtual vector operations;

choosing means for choosing, for each operation in the set of virtual vector operations, an expansion to apply to that operation, wherein the expansion is chosen from a plurality of possible expansions; and

expanding means for expanding each operation in the set of virtual vector operations into a native code implementation of that operation in accordance with that operation'"'"'s corresponding chosen expansion.

9. The computer program product of claim 8, wherein the plurality of possible expansions includes expanding an operation into vector instructions.

10. The computer program product of claim 9, wherein the vector instructions are single-instruction multiple-datapath (SIMD) instructions.

11. The computer program product of claim 9, wherein the plurality of possible expansions includes expanding an operation into scalar instructions.

12. The computer program product of claim 11, wherein the plurality of possible expansions includes at least one of inserting a call to a pre-defined library function and expanding an operation into a combination of vector and scalar operations.

13. The computer program product of claim 8, wherein the expansion for each operation in the set of vector operations is chosen according to a cost model.

14. The computer program product of claim 13, wherein the cost model is computed based on at least one of hardware resource availability, data dependencies, and existence of pre-defined library functions for particular operations.

15. An information-handling system comprising:

at least one processor;

one or more data storage units accessible by the at least one processor; and

functional descriptive material contained within the data storage units that, when executed by the at least one processor, directs the at least one processor to perform actions of;

identifying a loop containing instructions that operate over an array of values;

transforming the instructions into a set of virtual vector operations;

choosing, for each operation in the set of virtual vector operations, an expansion to apply to that operation, wherein the expansion is chosen from a plurality of possible expansions; and

expanding each operation in the set of virtual vector operations into a native code implementation of that operation in accordance with that operation'"'"'s corresponding chosen expansion.

16. The information-handling system of claim 15, wherein the plurality of possible expansions includes expanding an operation into vector instructions.

17. The information-handling system of claim 16, wherein the plurality of possible expansions includes expanding an operation into scalar instructions.

18. The information-handling system of claim 17, wherein the plurality of possible expansions includes at least one of inserting a call to a pre-defined library function and expanding an operation into a combination of vector and scalar operations.

19. The information-handling system of claim 15, wherein the expansion for each operation in the set of vector operations is chosen according to a cost model.

20. The information-handling system of claim 19, wherein the cost model is computed based on at least one of hardware resource availability, data dependencies, and existence of pre-defined library functions for particular operations.