JPH03220669A - Multiple loop vectorization compilation method - 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 [Field of Industrial Application] The present invention relates to a multi-loop vectorization compilation method in a compiler for an electronic computer system.

[Conventional technology]

In vector processing processors that have vector instructions that perform operations on data arranged regularly in a storage area at once, it is useful to increase the proportion of the part of the target program that is executed by vector instructions. The more you do this, the faster the program execution time can be. This is because a single vector instruction can perform an operation that cannot be performed without repeating a normal instruction (scalar instruction) many times. Therefore, it is desirable for a compiler for such a hexagonal processor to convert a given source program into a target program in a form that can be executed in parallel using vector instructions as much as possible.

By the way, conventional compilers for vector I/L processors with vector instructions generally include a syntax analysis unit that reads a source program written in a high-level language and performs syntax analysis to generate a first intermediate text; A vectorization processing unit that detects a loop structure in a source program from text, recognizes a vectorizable part, and generates a second intermediate text containing text for Muk1-L processing; The main part consists of a code generation section that generates and outputs a program.

For example, when such a conventional compiler is given a source program including a DO loop written in the FORTRAN language as shown in FIG. Next, the vectorization processing unit transforms the first intermediate text to produce a second intermediate text (steps S11 to S34) having the structure as shown in FIG. 312), and the code generation unit reads the second intermediate text and generates a target program consisting of actual code.

Further, vectorization by unifying is possible not only in a single loop as described above but also in multiple loops as long as a predetermined condition is satisfied. For example, if a source program including multiple DO loops as shown in Fig. 13 is given,
As shown in Figure 14, one-dimensional arrays AA, BB, CC, and DD have the same number of elements as arrays A, B, C, and D.
Newly declare array A using the EQU I VALENCE statement.

By matching B, C, and D with the arrays AA, BB, CC, and DD, respectively, the multiple DO loop can be replaced with a single DO loop, and the same steps as in FIGS. 10 to 12 can be performed for this single DO loop. This method performs vectorization.

[Problem to be solved by the invention]

As mentioned above, under certain conditions, conventional compilers can vectorize not only a single loop but also multiple loops. This is very strict, and if the conditions are not met, the shortcoming is that the effect of reducing execution time through vectorization cannot be obtained.

In other words, the conditions for vectorization by unification of multiple loops are: ■ There is no data dependency in the loop that contradicts parallel execution. ■ Definition references of array elements in the loop are equidistant on the storage area. ■Definition quotation of array elements in a loop is unidirectional in the storage area. Note that ■ is a matter of course, and ■ and ■ are one-dimensional arrays (in the example in Figure 14, AA, BBCC, DD).
) is required by sequentially increasing and decreasing the elements of

Therefore, when a source program including multiple Do loops as shown in Figure 4 is given, the increment in the D○ variable is "
2", and the final value of the inner DO loop D○ variable is not the maximum value allowed for that array, so the above condition (■) is not satisfied. Therefore, this source program cannot be vectorized by unification, and the most Only the inner Do loop can be vectorized using the same method as shown in Figs. The subscript calculations had to be executed sequentially using scalar instructions.

The present invention has been proposed in view of the above-mentioned points, and its purpose is that if the conditions ``■'' and ``2'' are satisfied, even if the condition ``■'' is not satisfied, The object of the present invention is to provide a multi-loop vectorization compilation method that can perform vectorization by converting and achieve further reduction in execution time.

[Means to solve the problem]

In order to achieve the above object, the present invention includes a syntax analysis unit that reads a source program written in a high-level language and performs syntax analysis to generate a first intermediate text, and a syntax analysis unit that generates a first intermediate text from the first intermediate text. a vectorization processing unit that detects and recognizes vectorizable portions and generates a second intermediate text including text for vector processing;
a code generation unit that generates and outputs a target program from a second intermediate text, and generates and outputs a target program from a given source program to a vector processing processor, the vectorization process A structure analysis means for analyzing the flow of control in a loop of the source program from the first intermediate text; and a data dependency relationship determination means for determining whether there is a data dependency relationship inconsistent with parallel execution in the loop. , a multiple loop-overlapping analysis means for analyzing and determining whether or not multiple loops can be overlapped normally or by using a mask for parts that are determined to be consistent with parallel execution; Vector text generation means is provided for generating a second intermediate text by unifying and/or vectorizing the determined portion and other portions determined to be compatible with parallel execution.

[Effect]

In the multiple loop vectorization compilation method of the present invention, the structure analysis means of the vectorization processing section analyzes the control flow in the loop of the source program with respect to the first intermediate text generated by the syntax analysis section, and The dependency determination means determines whether or not there is a data dependency that contradicts parallel execution in the loop, and the multiple loop-duplication analysis means determines whether or not there is a data dependency that is inconsistent with parallel execution in the loop. Analyze and determine whether it is possible to combine multiple loops, and - vector text generation means unify and/or Vectorized and second
An intermediate text is generated, and then a code generation section generates and outputs a target program from this second intermediate text.

〔Example〕

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of a compiler to which the multiple loop vectorization compilation method of the present invention is applied.

In FIG. 1, the compiler 2 basically includes a syntax analysis unit 21 that reads a source program 1 written in a high-level language and performs syntax analysis to generate a first intermediate text 24; a vectorization processing unit 22 that detects loop structures in the source program 1 from the source program 1 and recognizes vectorizable portions to generate a second intermediate text 25 that includes text for vector processing; 3 and a code generation section 23 that generates and outputs the code.

Further, as a characteristic part of the present invention, the vectorization processing unit 22
a structure analysis means 221 for analyzing the control flow in the loop of the source program 1 from the first intermediate text 24;
A data dependency relationship determining means 222 determines whether there is a data dependency relationship inconsistent with parallel execution in the loop, and normal or mask use is performed for the portion determined by the data dependency relationship determining means 222 to be consistent with parallel execution. A multiple loop-duplication analysis means 223 that analyzes and determines whether or not multiple loops can be unified by the multiple loop-duplication analysis means 223, and portions and data dependence relationships determined by the multiple loop-duplication analysis means 223 to be unified. Vector text generation means 224 is provided which generates a second intermediate text by unifying and/or vectorizing other portions determined by means 222 to be compatible with parallel execution.

FIG. 2 shows the multiplex D used in the structural analysis means 221 to express analysis information that is the result of structural analysis of multiple loops.
○ This shows the logical configuration of the loop information table 4, and a pointer 41 to the next multiple Do small loop information table.
, a D○ loop nest chain 42, a pointer to the D○ loop-duplication table 43, a pointer to the array table 44, a pointer to the vector text 45, and D
Pointer 4G to the symbol table of the O variable, triat 47 of the D○ loop initial value, and 1- of the Do small loop value.
It consists of a triat 48 and a triat 49 for DO loop values.

FIG. 3 shows the logical configuration of the Do-loop-multiplexing method 1-Blu 5 used to express the analysis information of the result of analyzing multiple loops that can be combined in the multiple-loop-multiplexing analysis means 223. A pointer 51 to the innermost multiple D○ loop information table, a pointer 52 to the mask array table, and
It is composed of a triat 53 of the loop initial value, - a triat 54 of the DO loop final value after duplication, - a triat 55 of the DO loop value after duplication, and - a Do small loop repetition number 56 after duplication. ing.

The operation will be described below by taking as an example the case where the source program shown in FIG. 4 is given, which conventionally could not be vectorized by unifying multiple loops.

Prior to specific operations, a method of multiplexing multiple loops according to the present invention will be conceptually explained.

That is, in the present invention, the source program shown in FIG.
Contain two multiple DO loops as shown in the figure, and the first multiple DO small loop
The O loop uses the same Do variable, and at its innermost position there is an instruction that simply assigns the value "1" to the mask array W, and the next multiple DO loop sets all the increments of the D○ variable to "1", and , 2 Let P of the inner D○ variable, (Ii! be the maximum value allowed in the array, and only if the element of the mask array W at the innermost part of the loop is "1", for example, in the original source program Make the same definition citation as in .

In other words, the reason why the multiple DO loops in the source program in Figure 4 could not be unified is because the Do variation @K is incremented by ``2''.
This was because it did not meet the duplication condition that ``the definition references of array elements in the loop must be at equal intervals in the storage area'', so the increment was forced to the D○ variable. In addition to setting it to "1", the inner Do small loop Do
The final value of the variable is set to the maximum value allowed in the array. However, if left as is, D○ variable part "2""
4", etc. and Do variables I and J are larger than IT and JJ, definitions will also be quoted for array elements that are not intended by the program creator. To prevent this, leave multiple DO loops with the same D○ variables as in the original source program, write information indicating that the operation should actually be performed in the multiple loops to the masking array W, and mask it in the subsequent multiple DO loops. The element of the data array W is referenced, and definition citation is performed only when the value is "1".

Then, among those modified as shown in FIG. 5, the second multiplex DO loop is unified using the same method as explained in FIGS. 13 and 14. This state is shown in FIG. Then, this -duplicated D○ loop is shown in Figures 10 to 1.
Vectorization is performed using the same method as explained in Figure 2. Further, the first multiple DO loop can also be vectorized using the same method as that described for the innermost Do small loop with reference to FIGS. 10 to 12. In addition, in actual operation, the corresponding multiple D○ loop parts are unified and vectorized based on the analysis results of the source program shown in Figure 4, so the result is as shown in Figures 5 and 6. There is no transformed state.

Next, the operation of each means of the embodiment shown in FIG. 1 will be explained with respect to the above example.

First, when the source program 1 is given and the compiler 2 is activated, the syntax analysis unit 21 reads the source program 1, performs syntax analysis, and generates the intermediate text 24.The source program 1 shown in FIG. The first intermediate text 24 (step 2) having the structure shown in FIG.
401 to 2412) are generated.

Next, the structure analysis means 221 of the vectorization processing unit 22 reads the first intermediate text 24, recognizes loops, and analyzes the flow of control. Specifically, the following processing is performed.

(2) Divide the first intermediate text 24 into blocks with branches as units. Here, the branch corresponds to the exit or population of the loop. In the case of the first intermediate text 24 in FIG. 7, it is divided in steps 2402, 2404, and 2406.

■Divide the loop part into sentence units.

■Analyze the control flow of the entire program and find the relationship between each block.

■5 Collect information on the number of people going to the block for the arrays and variables whose definitions are cited in each block.

The above analysis results are multiplexed as shown in Figure 2.

It is expressed using loop information table 4. For example, each DO loop information of the first intermediate text 24 in FIG.
As shown in the figure, the multiple DO loop report table 4.4 starts from pointer 6 to the multiple DO loop report table. a, 4b
,4. It is expressed as a chain of c and its contents.

However, at this point, the DO loop overlapping table 5a in FIG. 8 has not been added.

Next, in FIG. 1, the data dependency relationship determining means 22
Step 2 uses analysis information to determine whether there is a data dependency in the loop that is inconsistent with parallel execution. From the analysis information shown in FIG. 8 created for the source program I shown in FIG. 4, it is determined that there is no contradiction in parallel execution.

Next, the multiple loop/duplication analysis means 223 analyzes and determines whether or not it is possible to unify multiple loops for the portion determined by the data dependency relationship determination means 222 to be compatible with parallel execution. For example 6, perform the following processing.

■D○ For arrays and variables whose definitions are cited in the loop, those whose definition citation relationships are consistent are extracted as candidates.

■ From the D○ variable information 47.48゜49 of the multiple DO loop information table 4 corresponding to the multiple Do small loop, whether or not the array/variable definition quotation has one directionality in the storage area through the multiple D○ loop. Find out. From the analysis information shown in FIG. 8 created for the source program 1 shown in FIG. 4, it is determined that it has one directionality.

(2) If there is one directionality, it is determined that the multiple DO loops can be unified, and a DO loop duplication table 5 is created. In the present example, the Do small loop overlap table 5a is created and chained in FIG.

■ After the DO loop-duplication table 5a is created, when the value of the Do small loop D○ variable outside the multiple Do loop changes, the magnitude of the increase/decrease in the storage location of the definition quotation of the array element is Check whether it is constant. That is, it is checked whether the definition references of array elements in the loop are evenly spaced in the storage area. From the analysis information in Figure 8, the outermost D
Since the increment of the O-loop Do variable is "2", it is determined that the magnitude of the increase/decrease is not constant.

■If it is determined that the magnitude of increase/decrease is not constant, secure a mask array area, use that information as a mask array table (not shown), and check the D○ loop unification table 5. Two sogs. In the analysis information in Figure 8, DO
A mask array table is checked into the loop overlapping table 5a.

■If the mask array table is chained, -
Information such as the number of repetitions of the D○ variable after duplication is set in the Do small loop duplication table 5. In the analysis information in Figure 8, −
The number of repetitions of the DO loop after overlapping is r1. OO*
50 * Becomes KKJ. That is, the number of repetitions is the sum of the maximum value of each inner D○ variable multiplied by the final value of the final D○ variable.

Next, in FIG. 1, vector text generation means 2
24 is a multiple loop - a portion determined to be possible to be unified by the duplication analysis means 223 and the data dependency relationship determination means 2
The second intermediate text 25 is generated by unifying and/or vectorizing the portion determined by 22 to be consistent with parallel execution using the analysis information. Specifically, the following processing is performed.

■Generate text for vector length settings required for vector processing of parts that can be executed in parallel. For example, from the analysis information in Figure 8, there is no part that can be executed in parallel, but multiple DOs that can be unified by using a mask array.
Since it turns out that there is one set of loops, the text for setting the vector length required for unifying the multiple DO loops is as follows:
Text as shown in step 2505 and step 251o in FIG. 9 is generated. Note that step 250
5 is necessary when converting the innermost DO loop for mask setting into a DO loop vector, and the vector length is rl l which is the final value of the Do variable ■.
becomes. Step 2510 is necessary when converting the unified DO loop into a vector, and the vector length is rloO*, which is the number of DO loop repetitions after unification.
It becomes 50*KKj.

■Generate text for vector processing for normal parallel executable parts. From the analysis information in FIG. 8, it is clear that there is no part that can be executed in parallel, so this process is not performed.

(2) - Generate text for processing of the multiplexable DO loop. When there are multiple DO loops that can be combined by using a masking array, this process is performed as follows.

(Al Generates the text of the part by the scalar instruction outside the multiple DO loop for setting the mask, and also generates the text for assigning a predetermined value to the mask array. In the present example, as the outer scalar instruction, the 9th Step 25 in the diagram
The text shown in steps 010 to 2504, 2507, and 2508 is generated, and the text shown in step 2509 is generated to guarantee the final value of the vectorized innermost D○ variable. Further, the text shown in step 2506 is generated as the text for substituting a predetermined value into the masking array.

Generates text for setting mask information indicating how many fbl mask array elements the mask should be turned on. In the current example, step 25 in Figure 9
1) Generate the text shown in ■.

(When the Cl mask is on, a text is generated that quotes the predetermined definition. In this example, step 2 in Figure 9 is used.
The texts shown in 512-2514 are generated.

(2) Next, the text generation means 224 generates text for post-processing, which is necessary for performing vector processing on the part that can be executed in parallel. In the case of the current example, there is no corresponding item, so this process is not performed.

Next, the code generation unit 23 reads the second intermediate text 25 generated as described above, and generates the object program 3 using the corresponding machine language code.

〔Effect of the invention〕

As explained above, in the multiple loop vectorization compilation method of the present invention, there is no data dependency in the loop that contradicts parallel execution, and definition citation of array elements in the loop is unidirectional on the storage area. If the above is satisfied, even if the definition references of array elements in the loop are not evenly spaced in the storage area, the part of the array definition reference can be taken out of the loop and vectorized, so the entire multiple loop can be vectorized. Although it is not equivalent to vectorizing only the innermost loop, a significant reduction in execution time can be expected compared to vectorizing only the innermost loop.

[Brief explanation of drawings]

1 is a block diagram showing an embodiment of a compiler to which the multiple loop vectorization compilation method of the present invention is applied; FIG. 2 is a logical block diagram of a multiple DO loop information table used to express DO loop analysis information; Figure 3 is a logical configuration diagram of the Do loop-duplication table used to express DO small loop analysis information, Figure 4 is a diagram showing an example of a source program that includes multiple DO loops, and Figure 5 is the source program of Figure 4. Figure 6 is a conceptual diagram showing the state of the source program in Figure 5 after being unified in the form of a source program. The figure is a conceptual diagram (flow chart) of the structure of the first intermediate text generated by parsing the source program in Figure 4. Figure 8 is an example of the representation of analysis information of the Do loop in the source program in Figure 4. Figure 9 is a conceptual diagram of the structure of the second intermediate text generated by vectorizing the first intermediate text in Figure 7, and Figure 10 is a
Figure 11 is a conceptual diagram of the structure of the first intermediate text generated by parsing the source program in Figure 10. Figure 12 is the first intermediate text in Figure 11. A conceptual diagram of the structure of the second intermediate text generated by vectorizing the intermediate text, Figure 13 is a diagram showing an example of a source program including multiple DO loops, and Figure 14 is an example of the source program in Figure 13 after being unified. It is a diagram showing the state in the form of a source program. In the figure, 1... Source program 2... Compiler 21... Syntax analysis section 22... Vectorization processing section 221...・Structure analysis means 222...Data dependency determination means 223...Multiple loop-overlapping analysis means 224...Vector text generation means 4 23...Code raw bottom part 24... First intermediate text 25...Second intermediate text 3...Object program 4...Multiple DO loop information table 5...
......D○ loop unification table 6...
...pointer

Claims (2)

[Claims] (1) A syntactic analysis unit that reads a source program written in a high-level language and performs syntax analysis to generate a first intermediate text, and a syntax analysis unit that detects loop structures in the source program from the first intermediate text and converts them into vectorizable parts. It has a vectorization processing unit that performs recognition and generates a second intermediate text including text for vector processing, and a code generation unit that generates and outputs a target program from the second intermediate text, and has a vectorization processing unit that generates a target program from the second intermediate text and outputs it. , in a compilation method that generates and outputs a target program from a given source program, the vectorization processing unit includes a structure analyzer that analyzes the control flow in a loop of the source program from a first intermediate text, and a structure analyzer that analyzes a flow of control in a loop of the source program from a first intermediate text; A data dependency relationship determining means for determining whether there is a data dependency relationship that is inconsistent with parallel execution, and whether or not it is possible to combine multiple loops normally or by using a mask for the portion determined not to be inconsistent with parallel execution. a multiple loop unification analysis means that analyzes and determines whether unification is possible, and unification and/or vectorization of portions determined to be unification possible and other portions determined to be consistent with parallel execution to generate a second intermediate text. A multi-loop vectorization compilation method characterized by comprising a vector text generation means. (2) The multiple loop vectorization compilation method according to claim 1, wherein the DO loop analysis information is expressed using a multiple DO loop information table and a DO loop unification table.