Insertion of Operation-and-Indicate Instructions for Optimized SIMD Code

• US 20110047359A1
• Filed: 08/19/2009
• Published: 02/24/2011
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gara, Alan, Gschwind, Michael K., Eichenberger, Alexandre E.
• Granted Patent: US 8,458,684 B2
• Time in Patent Office: Days
• US Class Current: 712/222
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083
• CPC Class Codes: G06F 9/30007 to perform operations on data operands
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30038 using a mask
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3865 using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel

Abstract

Mechanisms are provided for inserting indicated instructions for tracking and indicating exceptions in the execution of vectorized code. A portion of first code is received for compilation. The portion of first code is analyzed to identify non-speculative instructions performing designated non-speculative operations in the first code that are candidates for replacement by replacement operation-and-indicate instructions that perform the designated non-speculative operations and further perform an indication operation for indicating any exception conditions corresponding to special exception values present in vector register inputs to the replacement operation-and-indicate instructions. The replacement is performed and second code is generated based on the replacement of the at least one non-speculative instruction. The data processing system executing the compiled code is configured to store special exception values in vector output registers, in response to a speculative instruction generating an exception condition, without initiating exception handling.

Claims

1. A method, in a data processing system, for inserting instructions into code for checking for in-data path special exception values indicative of deferred exception conditions, comprising:

analyzing, by a compiler executing on a processor of the data processing system, a portion of first code to identify at least one non-speculative instruction performing a designated non-speculative operation in the first code that is a candidate for replacement by an operation-and-indicate instruction that performs the designated non-speculative operation and further performs an indication operation for indicating any exception conditions corresponding to in-data path special exception values present in vector slots of vector register inputs to the operation-and-indicate instruction;

replacing, by the compiler executing on the processor, the at least one non-speculative instruction performing a designated non-speculative operation in the first code with the operation-and-indicate instruction; and

generating, by the compiler executing on the processor, second code based on the replacement of the at least one non-speculative instruction in the first code.

2. The method of claim 1, wherein the operation-and-indicate instruction is one of a store-and-indicate instruction, which performs a store operation to memory and indicates an exception condition corresponding to an in-data path special exception value if any, a move-and-indicate instruction, which moves a vector input from one vector register to another vector register and indicates an exception condition corresponding to an in-data path special exception value if any, or a computation-and-indicate instruction, which performs a computation operation on input vectors, generates a vector output, and indicates an exception condition corresponding to an in-data path special exception value if any.

3. The method of claim 1, wherein the first code includes single instruction multiple data (SIMD) code.

4. The method of claim 1, wherein analyzing the portion of first code comprises analyzing a dependence graph of the portion of the first code to identify a node within the dependence graph where an operation-and-indicate instruction may be inserted as a replacement for an instruction corresponding to the node.

5. The method of claim 4, wherein analyzing the portion of first code further comprises determining if a vector output register of the instruction corresponding to the node is checkable or uncheckable, wherein:

a vector output register is checkable if each value stored in each slot of the vector output register is checkable,

a value is checkable if it is a floating point value that is live and was actually computed or if the value is guaranteed to not cause an exception condition, and

a value is live if the value impacts a storage image of a memory of the data processing system or a decision process of the first code, or a successive computation that uses the value impacts the storage image or decision process.

6. The method of claim 5, wherein replacing the at least one non-speculative instruction with the operation-and-indicate instruction comprises inserting the operation-and-indicate instruction at a node in the dependence graph of the portion of the first code where live floating point values of the vector output registers of the portion of the first code are checked for the in-data path special exception value.

7. The method of claim 5, wherein replacing the at least one non-speculative instruction with the operation-and-indicate instruction comprises inserting the operation-and-indicate instruction at each node in the dependence graph of the portion of the first code where a computation is performed.

8. The method of claim 5, wherein analyzing the portion of first code further comprises:

determining if there is at least one node in the dependence graph that is associated with an instruction whose output vector register is checkable;

in response to determining that there is not at least one node in the dependence graph that is associated with an instruction whose output vector register is checkable, determining if at least one node in the dependence graph is a transformable node that is associated with an instruction whose output vector register is transformable into a checkable output vector register; and

transforming the instruction associated with the at least one transformable node such that the output vector register of the instruction associated with the at least one transformable node is checkable.

9. The method of claim 8, wherein transforming the instruction associated with the at least one transformable node comprises masking non-checkable values in the output vector register.

10. The method of claim 8, wherein transforming the instruction associated with the at least one transformable node comprises performing loop peeling such that the output vector register stores only checkable values.

11. The method of claim 8, further comprising:

determining if a cost associated with the transforming of the instruction associated with the at least one transformable node is above a threshold; and

in response to the cost being above the threshold, not performing the transforming of the instruction associated with the at least one transformable node.

12. The method of claim 11, wherein if the cost is above the threshold, vectorization of the second code is reverted at least in part.

13. The method of claim 1, wherein the data processing system is configured to store the in-data path special exception values in vector output registers, in response to a speculative instruction generating an exception condition, without initiating exception handling.

14. The method of claim 1, wherein replacing the at least one non-speculative instruction with the operation-and-indicate instruction comprises inserting the operation-and-indicate instruction at a node in the dependence graph of the portion of the first code where a comparison operation is performed.

15. The method of claim 1, wherein the in-data path special exception values are at least one of a Not-a-Number (NaN) value, a positive infinity value, or a negative infinity value.

16. The method of claim 15, wherein the in-data path special exception values that are identified by the operation-and-indicate instruction are controlled by a configuration setting of a computing device upon which the second code is executed, wherein the configuration setting specifies one or more of the NaN value, positive infinity value, or negative infinity value as being enabled for identification by the operation-and-indicate instruction.

17. The method of claim 1, wherein generating the second code comprises generating speculative instructions in the second code that defer exceptions by inserting an in-data path special exception value into a vector element of a corresponding vector register that is later checked by the operation-and-indicate instruction.

18. The method of claim 5, further comprising:

providing an interrupt handler that detects whether an interrupt is due to a checkable value or a non-checkable value in a vector output register, wherein the interrupt handler performs operations to handle the interrupt in response to the interrupt being due to a checkable value, and wherein the interrupt handler ignores the interrupt in response to the interrupt being due to a non-checkable value.

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

analyze a portion of first code to identify at least one non-speculative instruction performing a designated non-speculative operation in the first code that is a candidate for replacement by an operation-and-indicate instruction that performs the designated non-speculative operation and further performs an indication operation for indicating any exception conditions corresponding to in-data path special exception values present in vector slots of vector register inputs to the operation-and-indicate instruction;

replace the at least one non-speculative instruction performing a designated non-speculative operation in the code with the operation-and-indicate instruction; and

generate second code based on the replacement of the at least one non-speculative instruction.

20. A method, in a data processing system, for inserting instructions into code for checking for special values indicative of deferred exception conditions, comprising:

analyzing, by a processor of the data processing system, first code to identify at least one non-speculative instruction performing a designated non-speculative operation in the first code that is a candidate for replacement by an operation-and-indicate instruction that performs the designated non-speculative operation and further performs an indication operation for indicating any exception conditions corresponding to in-data path special exception values present in vector slots of vector register inputs to the operation-and-indicate instruction;

replacing, by the processor, the at least one non-speculative instruction performing a designated non-speculative operation in the code with the operation-and-indicate instruction;

generating, by the processor, second code based on the replacement of the at least one non-speculative instruction;

executing the second code in the processor or another processor of the data processing system, or in another computing device;

tracking exception conditions during execution of speculative instructions in the second code using special values indicative of the exception conditions, without invoking an exception handler; and

executing the operation-and-indicate instruction in the second code to detect the special values and perform the operation and indication operation, wherein the indication operation causes the exception handler to be invoked.