Method, apparatus, and computer program for generating SIMD instruction sequence

• US 20040098709A1
• Filed: 11/12/2003
• Published: 05/20/2004
• Est. Priority Date: 11/12/2002
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kyo, Shorin
• Granted Patent: US 7,509,634 B2
• Time in Patent Office: Days
• US Class Current: 717/140
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

A translator receives a source code that is described using a process designation (such as a line-by-line process designation, a line data extraction designation, and a broadcast designation) to be performed on line data of an image on a line by line basis, parses and optimizes the source code, and then generates an SIMD macro code that is an intermediate form taking into consideration the use of an SIMD instruction set. A simplifier generates, from the SIMD macro code, a simplified SIMD macro code, namely, a composite macro code into which a series of codes having the relationship between the definition and the reference of the same virtual SIMD register is organized. A machine code generator generates, from the simplified SIMD macro code, a machine code that efficiently uses an SIMD instruction.

Claims

1. An SIMD (Single Instruction Multi Data) instruction sequence generation method comprising generating automatically an SIMD instruction sequence from a source code that is described using a process designation that is to be performed on line data of an image on a line by line basis.

4. An SIMD instruction sequence generation method according to one of claims 1, 2, and 3, comprising generating an instruction sequence for performing an operation as designated in response to a scalar process designation contained in a line-by-line operation designation, and generating, in response to a line-by-line process designation, an SIMD instruction sequence for designating a loop operation, wherein the loop operation is repeated by P/(S×

M) cycles, and comprises, in the body thereof, M SIMD load instructions for loading, in M SIMD registers, S×

M data elements (S is a value smaller than P and is the number of data elements that are simultaneously processed in response to a single SIMD instruction and M is an integer equal to or larger than 1 and equal to or smaller than the number of SIMD registers held by a target machine) from among P data elements of the line date to be processed (P is the number of pixels horizontally across an image to be processed) present in consecutive addresses in a memory with a head address aligned to the powers of 2, SIMD operation instructions of the number required for the M SIMD registers, and M SIMD write instructions for writing, in a memory area having consecutive addresses with the head address thereof aligned to the powers of 2, the content of the M SIMD registers having data obtained as a result of the SIMD operation instructions.

2. An SIMD instruction sequence generation method comprising generating automatically an SIMD instruction sequence from a source code that is described using a line-by-line process designation, wherein the line-by-line process designation is a combination of a line-by-line calculation designation and a line-by-line adjacent element reference designation, the line-by-line calculation designation designating one of the same unary operation to be performed to all data elements of the line data, and the same binary operation to be performed to all corresponding data element pairs of line data of two lines, and the line-by-line adjacent element reference designation designating an operation for referencing a data element which is separated to the right or to the left by a designated number of elements from each of all data elements of the line data.

3. An SIMD instruction sequence generation method comprising generating automatically an SIMD instruction sequence from a source code that is described using a line-by-line operation designation, wherein the line-by-line operation designation is a combination of a line-by-line process designation, a line data extraction designation for referencing a particular data element of the line data, a broadcast designation for substituting scalar data as particular single data for all data elements of the line data, and a scalar process designation for designating a process to scalar data.

5. An SIMD instruction sequence generation method comprising:

a translation step for inputting a source code to a first storage device, parsing and optimizing the source code, generating an SIMD macro code that is an intermediate form taking into consideration the use of an SIMD instruction set, and outputting the SIMD macro code to a second storage device, wherein the source code is described using a line-by-line process designation, and a line-by-line operation designation, the line-by-line process designation being a combination of a line-by-line calculation designation and a line-by-line adjacent element reference designation, the line-by-line calculation designation designating one of the same unary operation to be performed to all data elements of the line data, and the same binary operation to be performed to all corresponding data element pairs of line data of two lines, the line-by-line adjacent element reference designation designating an operation for referencing a data element which is separated to the right or to the left by a designated number of elements from each of all data elements of the line data, and the line-by-line operation designation being a combination of a line data extraction designation for referencing a particular data element of the line data, a broadcast designation for substituting scalar data as particular single data for all data elements of the line data, and a scalar process designation for designating a process to scalar data;

a simplification step for generating a simplified SIMD macro code and outputting the simplified SIMD macro code to a third storage device, wherein the simplified SIMD macro code is generated by receiving the SIMD macro code from the second storage device, analyzing the relationship between a definition and a reference of a virtual SIMD register for an entire code having the virtual SIMD register in an operand, and converting the SIMD macro code into a composite macro code having a series of codes having the relationship between the definition and the reference to the same virtual SIMD register based on the analysis result; and

a machine code generation step for receiving the simplified SIMD macro code from the third storage device, for generating an instruction sequence for performing an operation as designated in response to the scalar process designation contained in the line-by-line operation designation, and for generating, in response to the line-by-line process designation, an SIMD instruction sequence for designating a loop operation, wherein the loop operation is repeated by P/(S×

M) cycles, and comprises, in the body thereof, M SIMD load instructions for loading, in M SIMD registers, S×

M-data elements (S is a value smaller than P and is the number of data elements that are simultaneously processed in response to a single SIMD instruction and M is an integer equal to or larger than 1 and equal to or smaller than the number of SIMD registers held by a target machine) from among P data elements of the line date to be processed (P is the number of pixels horizontally across an image to be processed) present in consecutive addresses in a memory with a head address aligned to the powers of 2, SIMD operation instructions of the number required for the M SIMD registers, and M SIMD write instructions for writing, in a memory area having consecutive addresses with the head address thereof aligned to the powers of 2, the content of the M SIMD registers having data obtained as a result of the SIMD operation instructions.

6. An SIMD instruction sequence generator comprising:

a first storage device for storing a source code, wherein the source code is described using a line-by-line process designation, and a line-by-line operation designation, the line-by-line process designation being a combination of a line-by-line calculation designation and a line-by-line adjacent element reference designation, the line-by-line calculation designation designating one of the same unary operation to be performed to all data elements of the line data, and the same binary operation to be performed to all corresponding data element pairs of line data of two lines, the line-by-line adjacent element reference designation designating an operation for referencing a data element which is separated to the right or to the left by a designated number of elements from each of all data elements of the line data, and the line-by-line operation designation being a combination of a line data extraction designation for referencing a particular data element of the line data, a broadcast designation for substituting scalar data as particular single data for all data elements of the line data, and a scalar process designation for designating a process to scalar data;

translation means for receiving the source code from a first storage device, parsing and then optimizing the source code, and generating an SIMD macro code that is an intermediate form taking into consideration the use of an SIMD instruction set;

a second storage device for storing the SIMD macro code generated by the translation means;

simplifying means for generating a simplified SIMD macro code, wherein the simplified SIMD macro code is generated by receiving the SIMD macro code from the second storage device, analyzing the relationship between a definition and a reference of a virtual SIMD register for an entire code having the virtual SIMD register in an operand, and converting the SIMD macro code into a composite macro code having a series of codes having the relationship between the definition and the reference to the same virtual SIMD register based on the analysis result;

a third storage device for storing the simplified SIMD macro code generated by the simplifying means;

machine code generating means for receiving the simplified SIMD macro code from the third storage device, for generating an instruction sequence for performing an operation as designated in response to the scalar process designation contained in the line-by-line calculation designation, and for generating, in response to the line-by-line process designation, an SIMD instruction sequence for designating a loop operation, wherein the loop operation is repeated by P/(S×

M) cycles, and comprises, in the body thereof, M SIMD load instructions for loading, in M SIMD registers, S×

M data elements (S is a value smaller than P and is the number of data elements that are simultaneously processed in response to a single SIMD instruction and M is an integer equal to or larger than 1 and equal to or smaller than the number of SIMD registers held by a target machine) from among P data elements of the line date to be processed (P is the number of pixels horizontally across an image to be processed) present in consecutive addresses in a memory with a head address aligned to the powers of 2, SIMD operation instructions of the number required for the M SIMD registers, and M SIMD write instructions for writing, in a memory area having consecutive addresses with the head address there of aligned to the powers of 2, the content of the M SIMD registers having data obtained as a result of the SIMD operation instructions; and

a fourth storage device for storing a machine code which is an instruction sequence generated by the machine code generating means.

7. A computer program for causing a computer to function as an SIMD instruction sequence generator comprising:

translation means for inputting a source code from a first storage device, parsing and then optimizing the source code, generating an SIMD macro code that is an intermediate form taking into consideration the use of an SIMD instruction set, and outputting the SIMD macro code to a second storage device, wherein the source code is described using a line-by-line process designation, and a line-by-line operation designation, the line-by-line process designation being a combination of a line-by-line calculation designation and a line-by-line adjacent element reference designation, the line-by-line calculation designation designating one of the same unary operation to be performed to all data elements of the line data, and the same binary operation to be performed to all corresponding data element pairs of line data of two lines, the line-by-line adjacent element reference designation designating an operation for referencing a data element which is separated to the right or to the left by a designated number of elements from each of all data elements of the line data, and the line-by-line operation designation being a combination of a line data extraction designation for referencing a particular data element of the line data, a broadcast designation for substituting scalar data as particular single data for all data elements of the line data, and a scalar process designation for designating a process to scalar data;

simplifying means for generating a simplified SIMD macro code, wherein the simplified SIMD macro code is generated by receiving the SIMD macro code from the second storage device, analyzing the relationship between a definition and a reference of a virtual SIMD register for an entire code having the virtual SIMD register in an operand, converting the SIMD macro code into a composite macro code having a series of codes having the relationship between the definition and the reference to the same virtual SIMD register based on the analysis result, and outputting the simplified SIMD macro code to a third storage device; and

machine code generating means for receiving the simplified SIMD macro code from the third storage device, for generating an instruction sequence for performing an operation as designated in response to the scalar process designation contained in the line-by-line calculation designation, and for generating, in response to the line-by-line process designation, an SIMD instruction sequence for designating a loop operation, wherein the loop operation is repeated by P/(S×

M) cycles, and comprises, in the body thereof, M SIMD load instructions for loading, in M SIMD registers, S×

M data elements (S is a value smaller than P and is the number of data elements that are simultaneously processed in response to a single SIMD instruction and M is an integer equal to or larger than 1 and equal to or smaller than the number of SIMD registers held by a target machine) from among P data elements of the line date to be processed (P is the number of pixels horizontally across an image to be processed) present in consecutive addresses in a memory with a head address aligned to the powers of 2, SIMD operation instructions of the number required for the M SIMD registers, and M SIMD write instructions for writing, in a memory area having consecutive addresses with the head address there of aligned to the powers of 2, the content of the M SIMD registers having data obtained as a result of the SIMD operation instructions.