JPH046020B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (A) Technical Field of the Invention The present invention provides a data register allocation processing device;
In particular, for example, in a compiler that generates and supplies an object program from a given source program to a vector processing processor equipped with multiple pipeline calculation units, it is necessary to use a compiler that generates and supplies an object program from a given source program to a vector processing processor equipped with multiple pipeline calculation units. Extract variables that were not executed, perform register allocation so that values defined at a certain rotation can be propagated by registers to the reference point at the next rotation, and perform optimized compilation processing. The present invention relates to a data register allocation processing device.

(B) Technical background and problems For example, as shown in Figure 1A, if the elements a ₁ , a ₂ , ... belonging to vector A and the elements b ₁ , b ₂ , ... belonging to vector B are There are vector processing processors that execute vector instructions that add together to produce a vector C with elements C ₁ , C ₂ , . Figure 1A
In the illustrated case, the mask elements m ₁ , m ₂ ,...
The process is generalized as shown in FIG. 1B.

A data processing system having a vector processing processor that performs the above processing has a system configuration as shown in FIG. 2 as an embodiment.
In the figure, reference numeral 1 is a main storage device, 2 is a memory control device, 3 is a vector processing processor, 4 is a channel processor, 5 is a large storage device, 6 is a scalar processing circuit section, 7 is a vector processing circuit section, 8- 0,8
-1,... are floating point data registers, 9
-0, 9-1, ... are vector registers that can each store multiple pieces of data (element data), and 10-0, 10-1, ... are vector registers that can each store multiple pieces of mask data (mask element data). ); 11 is a vector length register in which information on the number of elements to be stored in each vector register is set; 1;
Reference numerals 2-0 and 12-1 represent memory access pipelines, 13 an addition/subtraction pipeline, 14 a multiplication processing pipeline, 15 a division processing pipeline, and 16 a mask processing pipeline.

When a vector processing processor as described above executes a process, a given source program is compiled into a form suitable for execution by the processor to generate a target program. The configuration of the compiler that performs this compilation will be described later with reference to FIG. Then, the data registers to be used are allocated.

Conventionally, a global register method has been adopted in which variables are allocated on a one-to-one basis, but for some sequentially referenced array elements and variables, processing like the global register method described above has been adopted. In order to refer to the value defined in a certain rotation at the next rotation, the vector processing processor repeats the store processing and load processing as follows: store processing -> load processing -> store processing ->... It had become commonplace.

(C) Object and structure of the invention The present invention aims to solve the above points, and () extracts the existence of the above-mentioned sequential reference array element, etc., and () uses the defined value at the next rotation. It is characterized in that it is compiled so that it is propagated through registers until it is referenced.
This will be explained below with reference to the drawings.

(D) Embodiment of the Invention Figure 3 shows the configuration of an embodiment of the compiler used in the present invention, Figure 4 is an explanatory diagram illustrating the manner in which a source program is transferred to intermediate code in the present invention, and Figure 5 is Explanatory diagrams explaining how to vectorize a source program, Figures 6 to 8
The figure is an explanatory diagram explaining the concept of processing according to the present invention,
9 and 10 respectively show the configuration of an embodiment of the present invention, and FIG. 11 shows an example of processing for sequential reference variables.

In FIG. 3, 17 is a source program stored in a large storage device, 18 is a compiler,
19 is an object program which is compiled and stored on a large storage device; 20 is a source interpretation section; 21 is a storage allocation section; 22 is a vectorization section; 23 is an intermediate code optimization section; 24 is a register use determination section;
25 represents a target program output section.

A compiler 18 takes in a source program 17 from a large storage device and generates a desired target program 19. At this time, each of the illustrated parts performs the following processing.

That is, the source interpreter 20 takes in the source program 17 from the large storage device, performs sentence interpretation, and develops it into intermediate code (text). For example, if the source program is as shown on the left side of FIG. 4, it is developed into intermediate code as shown on the right side of the figure. The storage area allocation unit 21 allocates addresses within the storage area corresponding to various data appearing within the program. The vectorizer 22 detects loop structures in the program, recognizes parallel executable portions, and changes intermediate code as shown in FIG. Intermediate code optimization section 2
3 performs optimization at the intermediate code level to effectively utilize a vector processing processor as shown in FIG. The register use determining unit 24 allocates resources (registers) on the vector processing processor to data appearing in the intermediate code. Then, the target program output unit 25 outputs the machine instruction words to the large storage device and performs optimization at the instruction word level.

The compiler for operating the vector processing processor has the configuration shown in Figure 3.
The register use determining unit 24 allocates data registers on the vector processing processor to be used when processing is performed by the processor. However, the following problem arises.

Now, when a source program as shown in FIG. 6A is given, a target program as shown in FIG. 7A is generally generated. That is, "() Load data A(I) into register "0", ()
Store the contents of register "0" as data B, () add data C to the contents of register "0", () store the contents of register "0" as data A (I
The target program is generated so as to repeat the process of ``store as +1)''. However, in the above example, when the value of I is k, the contents of register "0" stored at ST 0, A(I+1) are:
This is the same content that will be loaded into register "0" at L 0,A(I) in the next rotation, that is, when I=(k+1). Therefore, it is desirable to propagate the value of array element A defined when I=k by holding the contents of a register for reference when I=(k+1).

For this purpose, in one embodiment of the present invention, when a source program as shown in FIG. 6A is given, it is expressed in the same expression as in FIG. 6A and transformed into a form as shown in FIG. 6B. Then, the register usage determining unit 24 determines the register to be used. In this way, the process shown in FIG. 6B is as follows.
The target program becomes as shown in FIG. 7B, and it is sufficient to first load data A(I) once into register "2" outside the loop.

FIG. 8 shows the processing when the sequential reference variable V is not set in the global register. That is, in FIG. 8A, for example, when I=k, the value of variable V is I=(k+1), which is referred to when performing the process C=V*B.

In such a case, as conceptually shown in Figure 8B, the variable V is temporarily loaded into a certain register γ as a process outside the loop, and the contents of the register γ are used to calculate C=γ*B. Then, the value of variable V is set in the register in the form γ=V+D. By doing this, the contents of register γ (value of V) defined when I=k
is propagated by register propagation and becomes referenced when I=(k+1). That is, store→load→store→ etc. is not performed every time each rotation is performed.

FIG. 9 shows an embodiment for carrying out the process described with reference to FIGS. 6 and 7. Note that the illustrated processes 26 and 27 may be considered to be performed in the intermediate code optimization section 23 illustrated in FIG. In the figure, 26 is an array element detection unit, 27
28 is an array element replacement section, and 28 is a register allocation section, which is performed in the register use determination section 24 shown in FIG.

The illustrated detection unit 26 detects the existence of array elements A(I) and A(I+1) as shown in FIG. 6A based on array conditions, subscript conditions, and address conditions. That is, for example, conditions on the array include that it is defined and referenced within the () loop, and that control is always transferred to a block when the () loop is executed. In addition, conditions related to addresses are detected by (address of defined array element) - (address of referenced array element) = (intra-loop increment value of subscript). The array element replacement unit 27
() Set the initial value A() in the form of internal variable GN in the loop preparation block as shown in Figure 6B, and create an array such as B(I) = A(I) as shown in Figure 6A. Replace the reference to element A with the reference to the internal variable GN in the form B(I)=GN as shown in Figure 6B, and write ()
The definition such as A(I+1)=B(I)+C(I) shown in Figure 6A is internalized in the form GN=B(I)+C(I) A(I+1)=GN as shown in Figure 6B. Change the definition of variable GN to an interposed format. Needless to say, the register allocation section 28 shown in FIG. 9 sequentially allocates registers based on the input intermediate code (input in the form of an intermediate code). The result is as shown in FIG. 7B.

FIG. 10 shows an embodiment for executing the process described with reference to FIG. Note that the illustrated processing is performed on variables that have not been allocated to global registers, and is therefore performed after the use of the global registers has been determined in the register use determining unit 24 shown in FIG. In the figure, numeral 29 is a sequential reference variable detection unit that detects variables that have not been allocated to global registers and extracts variables to be processed. 30 is a register propagation range detection unit that determines in which range register propagation is performed. For example, if multiple definitions are performed within one loop,
The last defined point becomes the propagation starting point. Furthermore, when reference is made multiple times within one loop, the first reference point becomes the propagation end point.

Furthermore, 31 is a register propagation processing section. The processing section 31 performs the following processing. That is, (1) First, extract a register (referred to as Rt) that will be a propagation medium. In other words, register Rt is either a register (referred to as Rd) used when the variable is defined, or another register (rf) to which the contents of register Rd are transferred up to the variable reference point.
) or an unused register within the propagation range (referred to as Ru), and in reality, register Rt is determined after global register allocation is completed.

(2) If register Rt is not register Rd, add processing to transfer the contents of register Rd to register Rt during the process of storing the contents of register Rd.

(3) Once register Rt is determined, register Rt is allocated so that the contents of register Rt are referenced in response to reference to variable V.

(4) In the loop preparation block, generate an instruction to load the value of variable V into register Rt.

(5) If after the execution of the loop finishes,
When the variable V is referenced outside the loop, an instruction to store the contents of the register Rt is generated outside the loop.

FIG. 11 shows the source information as shown in FIG. 11A.
When the program is given, register Rt=Rd
(Figure 11B), when register Rt=Rf (Figure 11C), and when register Rt=Rd=Rf (Figure 11D), the obtained target programs are shown on the right side of the figure. In either case, a load (L) is executed outside the loop, and a store (ST) is executed outside the loop as necessary. It is taking shape.

(E) Effects of the Invention As explained above, according to the present invention, sequentially referenced data is propagated by registers during loop rotation, and undesired load/store operations are significantly reduced.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram conceptually explaining processing corresponding to vector instructions, FIG. 2 is an example of a processing system having a vector processing processor according to the present invention, and FIG. 3 is an example of a compiler used in the present invention. Embodiment configuration, FIG. 4 is an explanatory diagram illustrating the manner in which a source program is transferred to intermediate code, FIG. 5 is an explanatory diagram illustrating a manner in which a source program is vectorized, and FIGS. 6 to 8 9 is an explanatory diagram for explaining the concept of processing according to the present invention, FIGS. 9 and 10 each show an embodiment of the present invention, and FIG. 11 shows an example of processing for sequentially referenced variables. In the figure, 1 is a main storage device, 2 is a memory control device,
3 is a vector processing processor, 4 is a channel processor, 5 is a large storage device, 9 is a vector register, 10 is a mask register, 11 to 16
17 is a source program, 18 is a compiler, 19 is an objective program, 20 is a source interpreter, 21 is a storage allocation unit, 22 is a vectorization unit, 23 is an intermediate code optimization unit, 24 25 represents a register use determining section, and 25 represents a target program output section.

Claims (1)

[Scope of Claims] 1. In a compiling device that generates and supplies a target program from a given source program, a source interpreter that interprets the sentences of the source program and develops it into intermediate code; Storage allocation means for allocating addresses within storage areas for various data; intermediate code optimization means for optimizing the processor to make effective use of the intermediate code; and register use for allocating actual resources to data appearing in intermediate code. and a target program output means; furthermore, the intermediate code optimization means detects the existence of a sequentially referenced array element based on at least a condition on the array, a condition on the subscript, and a condition on the address. The register use determining means comprises: a sequentially referenced array element detecting means; and an array element replacing means for replacing the sequentially referenced array element in a manner that defines an internal variable and uses the defined internal variable. A register allocation means is provided which allocates a register based on a given intermediate code and holds the contents of the register in which the sequentially referenced array element is defined in the register at least until the next rotation. A data register allocation processing device characterized in that the value of the sequential reference array element is propagated through the register during the next rotation. 2. In a compiling device that generates and supplies a target program from a given source program, a source interpreter that interprets the sentences of the source program and develops it into intermediate code, and addresses in the storage area of various data that appear in the program. A storage allocation means for allocating a memory area, an intermediate code optimization means for optimizing the effective use of a processor at the intermediate code level, a register use determination means for allocating actual resources to data appearing in the intermediate code, and a purpose. The register use determining means further includes register allocation means for sequentially allocating registers based on a given intermediate code, and at least sequential reference to which no global register allocation has been made. A sequential reference variable detection means for detecting variables; and a register propagation range for detecting the range in which register propagation is performed from the last definition point to the first reference point in the next rotation when registers are used within one loop. detection means, and the register of interest is a first type register used when a variable is defined and a second type register to which the contents of the first type register are transferred up to a variable reference point.
After checking whether it is a seed register or a third type register that is unused within the propagation range, it generates an instruction that allocates the sequential reference variable to the register that becomes the propagation medium and makes it consistent with the allocation. 1. A data register allocation processing device, comprising register propagation processing means, wherein the value of the sequential reference variable at the time of definition is propagated via the register at the next rotation.