JPH04295960A - Vectorize processing system for compiler - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention relates to a computer system (hereinafter referred to as a vector computer) capable of performing vector operations.
This paper relates to a vectorization processing method for a compiler that generates a vectorized target program from a source program written in a high-level language.

0002

2. Description of the Related Art In vector computers, vector operations can be executed much faster than scalar operations. In order to maximize the capabilities of such a vector computer, it is important for a compiler for a vector computer to increase the proportion (vectorization rate) of the portion of the target program that is executed by vector operations. For this purpose, compiler vectorization processing methods exist.

Conventionally, in the vectorization processing method of this type of compiler, the number of variables defined/quoted in a loop is one
If the variable is definitely defined during the loop, it can be vectorized by making it into an array, but there is a conditional branch in the loop and it is difficult to determine whether the variable is defined or not. If the loop depends on the success or failure (satisfaction/non-satisfaction) of each condition, it is not possible to vectorize the loop.

0004

[Problem to be Solved by the Invention] In the conventional compiler vectorization processing method described above, there is a conditional branch in the loop, and whether or not a variable is defined depends on the success or failure of the condition at each iteration. In this case, the loop cannot be vectorized, so the vectorization rate of the target program for the vector computer is low.

An object of the present invention is to take into account the fact that a conditional branch exists in a loop and whether or not a variable is defined depends on the success or failure of a condition in each iteration. By removing the fact that variables are defined only under specific conditions (hereinafter referred to as variable definition condition dependency fact) from factors that make vectorization impossible, the vectorization rate of the target program for vector computers can be increased, and the execution time of the target program can be reduced. The object of the present invention is to provide a compiler vectorization processing method that reduces the time required.

[0006]

[Means for Solving the Problems] The compiler vectorization processing method of the present invention is a compiler that generates a vectorized object program from a source program written in a high-level language for a vector computer. A dependency relationship analysis unit that detects variable definition condition dependency facts in a loop in the generated intermediate text program, and a primary coefficient that reflects the success or failure of the condition related to the variable definition condition dependency fact detected by this dependency relationship analysis unit. a constant term processing unit that generates a constant term that reflects the success or failure of a condition related to the variable definition condition dependency fact detected by the dependency analysis unit; and a variable detected by the dependency analysis unit. a working array generation unit that generates a working array corresponding to a variable related to a definition condition dependent fact; a primary coefficient generated by the coefficient processing unit; a constant term generated by the constant term processing unit; and the working array generation unit. Generates a linear recurrence formula with a working array generated by a variable substitution unit that replaces access to a variable related to a variable definition condition dependent fact in a loop related to a variable definition condition dependent fact with an access to an element of a work array generated by the work array generation unit; Then, generates intermediate text that assigns the value of the variable related to the variable definition condition dependent fact immediately before the execution of the loop related to the variable definition condition dependent fact to the first element of the work array generated by the work array generation unit, and An initial value assignment generation unit that inserts the intermediate text immediately before, and an intermediate text that assigns the value of the last defined element of the work array generated by the work array generation unit to the variable related to the variable definition condition dependency fact. The present invention includes a final value guarantee generation unit that inserts the intermediate text immediately after the loop related to the generated variable definition condition dependent fact, and a vector text generation unit that performs vectorization processing on the intermediate text to generate vector intermediate text.

[0007]

[Operation] In the vectorization processing method of the compiler of the present invention, the dependency analysis section detects the variable definition condition dependence fact in the loop in the intermediate text program generated by the syntax analysis section, and the coefficient processing section detects the dependency fact in the intermediate text program generated by the syntax analysis section. The constant term processing unit generates a linear coefficient that reflects the success or failure of the condition related to the variable definition condition dependence fact detected by the dependency relationship analysis unit. The constant term is generated, the work array generation unit generates a work array corresponding to the variable related to the variable definition condition dependence fact detected by the dependency relationship analysis unit, and the recurrence expression generation unit generates the 1 generated by the coefficient processing unit. Variable definition conditions when a linear recurrence formula having an order coefficient, a constant term generated by the constant term processing unit, and a work array generated by the work array generation unit is generated, and the condition related to the variable definition condition dependence fact is satisfied. The definition of the variable related to the dependent fact is replaced by the linear recurrence formula, and the variable replacement unit generates access to the variable related to the variable definition condition dependent fact in the loop related to the variable definition condition dependent fact by the work array generation unit. The initial value assignment generation unit replaces the first element of the work array generated by the work array generation unit with the variable definition condition dependence fact immediately before the execution of the loop related to the variable definition condition dependence fact. Generates an intermediate text that assigns the value of the variable related to the loop, inserts the intermediate text immediately before the loop, and the final value guarantee generation unit assigns the value of the work array generated by the work array generation unit to the variable related to the variable definition condition dependency fact. Generates an intermediate text that assigns the value of the last defined element, inserts the intermediate text immediately after the loop related to the variable definition condition dependency fact, and the vector text generation unit performs vectorization processing on the intermediate text to create a vector intermediate text. generate.

[0008]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of a compiler vectorization processing method according to the present invention. The compiler vectorization processing method of this embodiment includes a compiler 1, a source program 15, and a target program 16.

The compiler 1 includes a control section 2, a syntax analysis section 3, a vectorization section 4, a target program generation section 5,
Dependency analysis section 6, coefficient processing section 7, and constant term processing section 8
, a work array generation section 9, a recurrence formula generation section 10, a variable substitution section 11, an initial value substitution generation section 12, a final price guarantee generation section 13, and a vector text generation section 14. There is.

FIG. 2 is a diagram showing an example of a loop existing in the source program 15. Note that I and N in the figure are positive integers.

FIG. 3 is a diagram showing an intermediate text string generated by the parser 3 based on the loop in the source program 15 shown in FIG. Note that i and n in the figure are positive integers (the same applies to FIGS. 4 and 5).

FIG. 4 is a diagram showing a vectorizable intermediate text string generated under the control of the vectorizer 4 based on the intermediate text string shown in FIG.

FIG. 5 is a diagram showing a vector intermediate text string (vectorized intermediate text string) generated under the control of the vectorizer 4 based on the intermediate text string shown in FIG.

Next, the operation of the vectorization processing method of the compiler of this embodiment configured as described above will be explained. Here, the operation when the source program 15 including the loop shown in FIG. 2 is compiled will be described.

The control section 2 in the compiler 1 performs overall control in a series of processes in the compiler 1 described below (the control section 2 will not be mentioned in the following explanation).

The syntactic analysis unit 3 performs syntactic analysis of the source program 15 to generate an intermediate text program including an intermediate text string (loop) shown in FIG.

The vectorization unit 4 to which control is transferred from the syntax analysis unit 3 detects loops in the intermediate text program generated by the syntax analysis unit 3, and sequentially vectorizes each detected loop. In the following explanation, vectorization for the loop shown in FIG. 3 will be described.

The vectorization section 4 first calls the dependency analysis section 6 when vectorizing the loop.

The dependency analysis unit 6 analyzes the definition/citation status of variables and arrays in the loop, and examines the possibility of vectorization of the loop. In the analysis, it is determined whether a variable definition condition dependent fact exists in the loop. In this loop, there is a variable definition condition dependent fact that "variable x is defined only under a specific condition 'y(i)>0'", so the dependency analysis unit 6
detects a fact that depends on the variable definition condition.

Since the dependency relationship analysis unit 6 has detected the variable definition condition dependency fact, the vectorization unit 4 uses the coefficient processing unit 7
, constant term processing unit 8, work array generation unit 9, recurrence expression generation unit 1
0, the variable replacement section 11, the initial value assignment generation section 12, and the final value guarantee generation section 13 are sequentially called to transform the loop into an intermediate text string shown in FIG. 4 that can be vectorized. In this process, each part performs the following processing.

[0022] The coefficient processing unit 7 generates a linear coefficient "1-s(i)" which becomes 0 when the condition "y(i)>0" is satisfied and becomes 1 when it does not hold (therefore, s(i
).

The constant term processing unit 8 satisfies the condition "y(i)>0"
Generates a constant term "t(i)" which is the value that should be assigned to the variable x if it holds true and becomes 0 if it does not hold (to do this, the intermediate text 18 that defines the array element t(i) is generated. generate).

In this embodiment, it is assumed that all elements of the arrays t and s are initialized to 0 before execution of the target program 16 in the processing by the coefficient processing section 7 and the constant term processing section 8. are doing.

The work array generation unit 9 generates a work array xx corresponding to the variable x.

The recurrence formula generation unit 10 generates a linear recurrence formula "xx(i+1)= (1-s(
Intermediate text 1 indicating “i))*xx(i)+t(i)”
9 is generated, and the intermediate text indicating the definition of the variable x in the loop is replaced with the intermediate text 19.

The variable substitution unit 11 replaces the variable x in the loop.
Intermediate text 20 indicating access to an element of working array xx is replaced with intermediate text 20 indicating access to an element of working array xx.

The initial value assignment generation unit 12 generates an intermediate text 21 that assigns the value of the variable x immediately before execution of the loop to the first element xx(1) of the work array xx. Insert.

The closing price guarantee generation unit 13 generates intermediate text 22 (intermediate text for closing price guarantee) that assigns the value of the last defined element xx(n+1) of the work array xx to the variable x, and Immediately after that intermediate text 22
Insert.

Transformation processing of the intermediate text string as described above (
After the process of transforming the intermediate text string shown in FIG. 3 into the intermediate text string shown in FIG. 4), the vectorization unit 4 calls the vector text generation unit 14.

The vector text generation unit 14 performs vectorization processing on the intermediate text string shown in FIG.
Generate the vector intermediate text string shown in In the vector intermediate text string shown in FIG. 5, the intermediate text 19 indicating the linear recurrence formula in FIG. 4 is replaced with the vector intermediate text 23 indicating the vector recurrence formula command.

The vectorization unit 4 vectorizes each loop in the intermediate text program as much as possible, including the vectorization of the loops shown in FIG. 3 as described above, and passes control to the target program generation unit 5.

The target program generating section 5 generates a vectorized target program 16 from an intermediate text program including the vector intermediate text string shown in FIG.

[0034]

[Effects of the Invention] As explained above, the present invention has a dependency analysis section, a coefficient processing section, a constant term processing section, a work array generation section,
By providing a recurrence formula generation section, a variable substitution section, an initial value assignment generation section, a final value guarantee generation section, and a vector text generation section, it is possible to vectorize loops that could not be vectorized using the vectorization processing method of conventional compilers. This has the effect of increasing the vectorization rate of the target program for the vector computer and shortening the execution time of the target program.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a diagram showing an example of a loop existing in the source program in FIG. 1;

FIG. 3 is a diagram showing an intermediate text string generated by the parser in FIG. 1 based on the loop shown in FIG. 2;

4 is a diagram showing a vectorizable intermediate text string generated under control of the vectorization unit in FIG. 1 based on the intermediate text string shown in FIG. 3; FIG.

FIG. 5 is a diagram showing a vector intermediate text string generated under control of the vectorization unit in FIG. 1 based on the intermediate text string shown in FIG. 4;

[Explanation of symbols]

1 Compiler 2 Control section 3 Syntax analysis section 4 Vectorization section 5 Target program generation section 6 Dependency analysis section 7 Coefficient processing section 8 Constant term processing section 9 Work array generation section 10 Recurrence formula generation unit 11 Variable replacement part 12 Initial value assignment generation section 13 Closing price guarantee generation section 14 Vector text generation section 15 Primitive program 16 Purpose program 17-22 Intermediate text 23 Vector intermediate text

Claims (1)

[Claims] Claim 1: In a compiler that generates a vectorized target program from a source program written in a high-level language for a vector computer, a variable definition condition dependency fact is detected in a loop in an intermediate text program generated by a syntax analysis unit. a dependency analysis unit that detects
a coefficient processing unit that generates a first-order coefficient that reflects the success or failure of a condition related to the variable definition condition dependency fact detected by the dependency relationship analysis unit; and a condition related to the variable definition condition dependency fact detected by the dependency relationship analysis unit a constant term processing unit that generates a constant term reflecting the success or failure of the process; a work array generation unit that generates a work array corresponding to a variable related to the variable definition condition dependence fact detected by the dependency relationship analysis unit; and the coefficient processing unit. A linear recurrence formula having a linear coefficient generated by the constant term processing unit, a constant term generated by the constant term processing unit, and a work array generated by the work array generation unit is generated, and a condition related to a variable definition condition dependence fact is generated. A recurrence expression generation unit that replaces the definition of a variable related to a variable definition condition dependent fact with the corresponding linear recurrence formula when , and a variable related to a variable definition condition dependent fact in a loop related to the variable definition condition dependent fact. a variable replacement unit that replaces access to with an access to an element of the work array generated by the work array generation unit; and a variable definition condition dependent fact related to the first element of the work array generated by the work array generation unit. An initial value assignment generation unit that generates an intermediate text to which a value of a variable related to a variable definition condition dependent fact immediately before execution of a loop is inserted and inserts the intermediate text immediately before the loop; a final value guarantee generation unit that generates intermediate text to which the value of the element defined at the end of the work array generated by the work array generation unit is assigned, and inserts the intermediate text immediately after the loop related to the variable definition condition dependence fact; A vectorization processing method for a compiler, comprising: a vector text generation unit that performs vectorization processing on intermediate text to generate vector intermediate text.