AUTOMATIC LOOP VECTORIZATION USING HARDWARE TRANSACTIONAL MEMORY

• US 20150268940A1
• Filed: 03/21/2014
• Published: 09/24/2015
• Est. Priority Date: 03/21/2014
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Baghsorkhi, Sara S., Hartono, Albert, Wu, Youfeng, Vasudevan, Nalini, Wang, Cheng
• Granted Patent: US 9,720,667 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/452 Loops

Abstract

Technologies for automatic loop vectorization include a computing device with an optimizing compiler. During an optimization pass, the compiler identifies a loop and generates a transactional code segment including a vectorized implementation of the loop body including one or more vector memory read instructions capable of generating an exception. The compiler also generates a non-transactional fallback code segment including a scalar implementation of the loop body that is executed in response to an exception generated within the transactional code segment. The compiler may detect whether the loop contains a memory read dependent on a condition that may be updated in a previous iteration or whether the loop contains a potential data dependence between two iterations. The compiler may generate a dynamic check for an actual data dependence and an explicit transactional abort instruction to be executed when an actual data dependence exists. Other embodiments are described and claimed.

Claims

1. A computing device for loop vectorization, the computing device comprising:

an analysis module to detect a loop of a source program, the loop to define one or more scalar iterations and have a loop body for execution during each scalar iteration; and

a vectorization module to;

generate a transactional code segment, wherein to generate the transactional code segment comprises to generate a vectorized implementation of the loop body within the transactional code segment as a function of the loop of the source program, the vectorized implementation to define one or more vector iterations and to include a vector memory read instruction capable of generation of an exception; and

generate a non-transactional fallback code segment associated with the transactional code segment, the non-transactional fallback code to be executed in response to generation of an exception within the transactional code segment and comprising a scalar implementation of the loop body.

2. The computing device of claim 1, wherein:

to detect the loop of the source program comprises to detect a loop that includes a memory read dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration; and

to generate the transactional code segment comprises to generate the transactional code segment in response to detection of the loop that includes the memory read.

3. The computing device of claim 1, wherein the vectorization module is further to:

detect a potential data dependence between two scalar iterations included in the same vector iteration;

generate a dynamic check within the vectorized implementation of the loop body to determine whether an actual data dependence based on the potential data dependence exists; and

generate an explicit transactional abort instruction within the vectorized implementation of loop body, the explicit transactional abort instruction to be executed in response to a determination that the actual data dependence exists.

4. The computing device of claim 3, wherein to detect the loop of the source program comprises to detect a loop that has a memory load dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration.

5. The computing device of claim 1, wherein:

to generate the vectorized implementation comprises to generate a partially vectorized implementation that includes one or more vector instructions, each vector instruction to define a vector length; and

wherein each vector iteration corresponds to up to the vector length number of scalar iterations of the loop body.

6. The computing device of claim 5, wherein to generate the partially vectorized implementation comprises to generate a partially vectorized implementation that includes a hardware partial vectorization support instruction, wherein the hardware partial vectorization support instruction comprises a set up to and including first true in mask instruction, a set up to but not including first true in mask instruction, or a masked broadcast of last set element instruction.

7. The computing device of claim 1, wherein to generate the vectorized implementation comprises to generate a vectorized implementation of the loop body that includes a vector load instruction that is capable of generation of an exception or a vector gather instruction that is capable of generation of an exception.

8. The computing device of claim 1, wherein to generate the transactional code segment comprises to include a plurality of vector iterations of the vectorized implementation of the loop body per transactional code segment.

9. A method for loop vectorization, the method comprising:

detecting, by a computing device, a loop of a source program, the loop defining one or more scalar iterations and having a loop body for execution during each scalar iteration;

generating, by the computing device, a transactional code segment, wherein generating the transactional code segment comprises generating a vectorized implementation of the loop body within the transactional code segment as a function of the loop of the source program, the vectorized implementation defining one or more vector iterations and including a vector memory read instruction that is capable of generating an exception; and

generating, by the computing device, a non-transactional fallback code segment associated with the transactional code segment, the non-transactional fallback code to be executed in response to generation of an exception within the transactional code segment and comprising a scalar implementation of the loop body.

10. The method of claim 9, wherein:

detecting the loop of the source program comprises detecting a loop including a memory read dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration; and

generating the transactional code segment comprises generating the transactional code segment in response to detecting the loop including the memory read.

11. The method of claim 9, further comprising:

detecting, by the computing device, a potential data dependence between two scalar iterations included in the same vector iteration;

generating, by the computing device, a dynamic check within the vectorized implementation of the loop body to determine whether an actual data dependence based on the potential data dependence exists; and

generating an explicit transactional abort instruction within the vectorized implementation of loop body, the explicit transactional abort instruction to be executed in response to determining that the actual data dependence exists.

12. The method of claim 11, wherein detecting the loop of the source program comprises detecting a loop having a memory load dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration.

13. The method of claim 9, wherein:

generating the vectorized implementation comprises generating a partially vectorized implementation including one or more vector instructions, each vector instruction defining a vector length; and

wherein each vector iteration corresponds to up to the vector length number of scalar iterations of the loop body.

14. The method of claim 9, wherein generating the transactional code segment comprises including a plurality of vector iterations of the vectorized implementation of the loop body per transactional code segment.

15. One or more computer-readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to:

detect a loop of a source program, the loop defining one or more scalar iterations and having a loop body for execution during each scalar iteration;

generate a transactional code segment, wherein to generate the transactional code segment comprises to generate a vectorized implementation of the loop body within the transactional code segment as a function of the loop of the source program, the vectorized implementation to define one or more vector iterations and including a vector memory read instruction that is capable of generating an exception; and

generate a non-transactional fallback code segment associated with the transactional code segment, the non-transactional fallback code to be executed in response to generation of an exception within the transactional code segment and comprising a scalar implementation of the loop body.

16. The one or more computer-readable storage media of claim 15, wherein:

to detect the loop of the source program comprises to detect a loop including a memory read dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration; and

to generate the transactional code segment comprises to generate the transactional code segment in response to detecting the loop including the memory read.

17. The one or more computer-readable storage media of claim 15, further comprising a plurality of instructions that in response to being executed cause the computing device to:

detect a potential data dependence between two scalar iterations included in the same vector iteration;

generate a dynamic check within the vectorized implementation of the loop body to determine whether an actual data dependence based on the potential data dependence exists; and

generate an explicit transactional abort instruction within the vectorized implementation of loop body, the explicit transactional abort instruction to be executed in response to determining that the actual data dependence exists.

18. The one or more computer-readable storage media of claim 17, wherein to detect the loop of the source program comprises to detect a loop having a memory load dependent on a condition that may be updated in a previous scalar iteration included in the same vector iteration.

19. The one or more computer-readable storage media of claim 15, wherein:

to generate the vectorized implementation comprises to generate a partially vectorized implementation including one or more vector instructions, each vector instruction defining a vector length; and

wherein each vector iteration corresponds to up to the vector length number of scalar iterations of the loop body.

20. The one or more computer-readable storage media of claim 15, wherein to generate the transactional code segment comprises to include a plurality of vector iterations of the vectorized implementation of the loop body per transactional code segment.