Loop vectorization methods and apparatus

Patent metadata

Field	Value
Publication number	US-9244677-B2
Application number	US-201213630147-A
Country	US
Kind code	B2
Filing date	Sep 28, 2012
Priority date	Sep 28, 2012
Publication date	Jan 26, 2016
Grant date	Jan 26, 2016

Abstract

Loop vectorization methods and apparatus are disclosed. An example method includes setting a dynamic adjustment value of a vectorization loop; executing the vectorization loop to vectorize a loop by grouping iterations of the loop into one or more vectors; identifying a dependency between iterations of the loop as; and setting the dynamic adjustment value based on the identified dependency.

First claim

What is claimed is:

1. A method, comprising:
prior to executing an original loop having iterations:
analyzing, via a processor, the iterations of the original loop;
identifying, via the processor, a dependency between a first one of the iterations of the original loop and a second one of the iterations of the original loop;
after identifying the dependency, vectorizing, via the processor, a first group of the iterations of the original loop based on the identified dependency to form a vectorization loop;
generating a first mask for a first iteration of the vectorization loop to enable, for the first iteration of the vectorization loop, vectorization of independent ones of the iterations of the original loop and to disable vectorization of dependent ones of the iterations of the original loop; and
setting, via the processor, a dynamic adjustment value of the vectorization loop based on the identified dependency at least by identifying a first occurring unprocessed iteration of the original loop from a start of the first mask.

2. A method as defined in claim 1 , wherein the setting of the dynamic adjustment value further includes increasing or decreasing a parameter of a definition of the vectorization loop.

3. A method as defined in claim 1 , wherein the first group includes the first one of the iterations of the original loop, and further including vectorizing a second group of the iterations of the original loop, wherein the second group includes the second one of the iterations of the original loop.

4. A method as defined in claim 1 , further including adjusting a parameter of a definition of the vectorization loop according to the dynamic adjustment value such that a subsequent iteration of the vectorization loop begins after the identified dependency.

5. A method as defined in claim 1 , wherein the vectorizing of the first group of the iterations includes grouping iterations of the original loop that are enabled by the first mask.

6. A method as defined in claim 1 , further including generating a second mask for a second iteration of the vectorization loop subsequent to the first iteration of the vectorization loop, wherein the first mask and the second mask have a length corresponding to a vector length associated with the vectorization loop.

7. A non-transitory tangible computer readable storage medium comprising instructions that, when executed, cause a machine to at least:
prior to executing an original loop having iterations:
analyze the iterations of the original loop;
identify a dependency between a first one of the iterations of the original loop and a second one of the iterations of the original loop;
after identifying the dependency, vectorize a first group of the iterations of the original loop based on the identified dependency to form a vectorization loop;
generate a first mask for a first iteration of the vectorization loop to enable, for the first iteration of the vectorization loop, vectorization of independent ones of the iterations of the original loop and to disable vectorization of dependent ones of the iterations of the original loop; and
set a dynamic adjustment value of the vectorization loop based on the identified dependency at least by determining a first occurring unprocessed iteration of the original loop from a start of the first mask.

8. A storage medium as defined in claim 7 , wherein the instructions, when executed, cause the machine to adjust the dynamic adjustment value by increasing or decreasing a parameter of a definition of the vectorization loop.

9. A storage medium as defined in claim 7 , wherein the first group includes the first one of the iterations of the original loop, and the instructions, when executed, cause the machine to vectorize a second group of the iterations of the original loop, wherein the second group includes the second one of the iterations of the original loop.

10. A storage medium as defined in claim 7 , wherein the instructions, when executed, cause the machine to adjust a parameter of a definition of the vectorization loop according to the dynamic adjustment value such that a subsequent iteration of the vectorization loop begins after the identified dependency.

11. A storage medium as defined in claim 7 , wherein the instructions, when executed, cause the machine to vectorize the first group of the iterations by grouping iterations of the original loop that are enabled by the first mask.

12. A storage medium as defined in claim 7 , wherein the instructions, when executed, cause the machine to generate a second mask for a second iteration of the vectorization loop subsequent to the first iteration of the vectorization loop, wherein the first mask and the second mask have a length corresponding to a vector length associated with the vectorization loop.

13. An apparatus to convert code, comprising:
a loop vectorizer to vectorize iterations of an original loop, the loop vectorizer including:
a definer to, prior to executing the original loop, analyze the iterations of the original loop;
an identifier to, prior to the executing of the original loop, identify a dependency between a first one of the iterations of the original loop and a second one of the iterations of the original loop;
a grouper to, prior to the executing of the original loop and after identifying the dependency, vectorize a first group of the iterations of the original loop based on the identified dependency to form a vectorization loop;
a mask generator to generate a first mask for a first iteration of the vectorization loop to enable, for the first iteration of the vectorization loop, vectorization of independent iterations of the original loop and to disable vectorization of dependent iterations of the original loop; and
a dynamic adjustment setter to, prior to the executing of the first one of the iterations of the original loop, set a dynamic adjustment value of the vectorization loop based on the identified dependency at least by determining a first occurring unprocessed iteration of the original loop from a start of the first mask, at least one of the definer, the identifier, the grouper, or the dynamic adjustment setter implemented by a processor and stored in a memory of the apparatus.

14. An apparatus as defined in claim 13 , wherein the grouper is to group the first one of the first iterations of the original loop into the first group, and to group the second one of the iterations of the original loop into a second group.

15. A method as defined in claim 1 , wherein all of the iterations of the original loop are processed via the vectorization loop before the executing of the original loop.

Assignees

• Intel Corp

Inventors

• Vasudevan Nalini
• Bharadwaj Jayashankar
• Hughes Christopher J
• Girkar Milind B
• Charney Mark J
• Valentine Robert
• Lee Victor W
• Kim Daehyun
• Hartono Albert
• Baghsorkhi Sara S

Classifications

• G06F8/443 Primary

  Optimisation · CPC title

• G06F8/452 Primary

  Loops · CPC title

• G06F9/3836

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/70 Primary

  Software maintenance or management · CPC title