JP2001101008A - Pair register allocation processing method, compilation processing device, and program recording medium for compiler - Google Patents

Abstract

(57) [Summary] In a translation process of a source program described in a high-level programming language, a pair register can be assigned to consecutive memory access instructions as much as possible, thereby improving execution performance. SOLUTION: In the case of a pair instruction, an instruction check means 20 sets pair information (first element / second element) in a pair register information area of the instruction, and stores an even register in a definition part of the first element. Set information (pair register information) to be assigned. The register allocating means 30 allocates an even-numbered register to the definition part of the first element, and unless there is an instruction to save the register contents, transfers the register in which the pair register information is set up to another instruction of the definition part of the second element. Do not assign it as an instruction register.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

TECHNICAL FIELD The present invention relates to FORTRAN,
The present invention relates to a pair register allocation processing method capable of generating an object program having a high execution performance in compiling a source program described in a high-level programming language such as C language or C ++ language.

[0002]

2. Description of the Related Art In conventional compiler processing, register numbers are regularly assigned in the order in which instructions are executed in register number assignment processing when a final object program is generated.

At the stage of optimization processing at the time of instruction assignment, even if a paired memory access instruction that accesses two data with one instruction is assigned, the register holding the two data is an even register (even number). If these registers are not consecutive registers in the order of numbered register) and even numbered register + 1 (this is called a paired register), the instruction cannot be executed as a paired memory access instruction due to the instruction specifications (hardware restrictions). At the time of register allocation for an access instruction, the pair memory access instruction has been decomposed into two single access instructions and expanded into an object program.

FIG. 6 shows an example of a translation result according to the prior art. In the multi instruction, the multiplication result is stored in the register r.
egX, the result of the multiplication is stored in a register regY in the multi instruction. The store1 instruction stores the value of the register regX in the memory, and the store2 instruction stores the value of the register regY in consecutive memory locations.

Here, if the register regX is an even-numbered register and the register regY is a register of a continuous pair of even-numbered register + 1, the store1 instruction and the store2 instruction shown in FIG. 6 are replaced with one pair memory access instruction. The number of instructions to be expanded in the object program can be reduced. However, register re
Register allocation is performed by an instruction between the definition part d1 of gX and the definition part d2 of the register regY. If the registers regX and regY are not continuous registers starting from even numbers, the instruction of the reference part r1 of the register regX is executed. And the instruction of the reference part r2 of the register regY are
As shown in FIG.
As shown in the figure, two single access instructions (stor
e1, store2).

[0006]

SUMMARY OF THE INVENTION An object of the present invention is to solve the above-mentioned problems and improve the execution performance of an object program as a translation result by allocating consecutive memory access instructions to a pair register. .

[0007]

In order to solve the above-mentioned problem, according to the present invention, it is determined whether a register allocated by a definition unit is a first element or a second element of a register of a pair memory access instruction of a reference unit. If the register is the first element, an even register is allocated, and if the register is the second element, an odd register is allocated.

At this time, information indicating that the register is to be assigned as a pair register is set in the register of the even-numbered register + 1 desired to be the register of the second element, and there is no instruction to save the contents of the register to the memory because the register is insufficient. As long as the second
Until the instruction in the definition part of the element, the register of the even register + 1 is not allocated to another instruction. As a result, the execution of the pair memory access instruction becomes possible.

Similarly, if an odd register is assigned to the second element prior to the assignment of the register to the first element, the odd register-1 to be the register of the first element is assigned as a pair register. Is set, and the register of the odd-numbered register-1 is allocated as little as possible between the instruction of the reference part of the first element and the instruction of the definition part of the first element.

A compiler program for realizing the above processing by a computer can be stored in an appropriate recording medium such as a computer-readable portable medium memory, a semiconductor memory, and a hard disk.

[0011]

Embodiments of the present invention will be described below. FIG. 1 shows a block configuration example of the present invention.
The processing device 1 is a device including a CPU, a memory, and the like. Source (primitive) program 2 is FORTRAN,
It is a program described in a high-level programming language such as C language or C ++ language. Object program 3
Is a program resulting from translating the source program 2 into a machine language instruction sequence.

The compiler 10 operates on the processing device 1,
This is a program that inputs a source program 2, translates (compiles) it, and generates an object program 3. The compiler 10 inputs the source program 2 and analyzes the syntax, converts the internal data (here, this internal data is referred to as an intermediate program) into a source program analysis unit 11 and an efficient intermediate program. An optimization unit 12 that performs processing for generating an instruction sequence, a register allocation unit 13 that allocates registers that can be used for the optimized instruction sequence, and an instruction sequence that results from allocating registers are used as necessary. The scheduling / code generation unit 14 generates the code of the object program 3 by rearranging and combining instructions.

The present invention particularly relates to the processing of the register allocating unit 13, and the processing of the other parts in the compiler 10 may be the same as the conventional one, so that the detailed description will be omitted.

In the present invention, in particular, the register allocating unit 13 includes an instruction checking means 20 having a pair information setting unit 21 and a pair instruction allocation information setting unit 22, a pair instruction definition unit detecting unit 31, and a pair register allocating unit 32. There is a register allocating means 30 having the following. Instruction check means 20
Inspects the intermediate program output by the optimization unit 12,
The register allocating means 30 determines whether or not the instruction is a pair memory access instruction before allocating the register. Is assigned.

The pair information setting section 2 of the instruction checking means 20
1 checks the intermediate program output from the optimizing unit 12 one instruction at a time, from the rear, to determine whether or not the instruction is a pair memory access instruction. "Pair information (first element / second element)" is set in the pair register information area provided on the memory. At the same time as this processing, the pair instruction assignment information setting unit 22 checks the intermediate program output from the optimizing unit 12 one instruction at a time from the rear, and defines the first element or the second element of the pair memory access instruction. Appears, information for assigning an even register is set in the definition part of the first element, and information for assigning an odd register of the even register + 1 is set in the definition part of the second element.

The pair instruction definition section detecting section 31 of the register allocating section 30 detects the definition section of the pair memory access instruction from the information set by the pair instruction allocation information setting section 22,
The pair register allocating unit 32 includes a pair instruction definition unit detecting unit 3
1 assigns an even-numbered register to the register of the first element of the paired memory access instruction and assigns an odd-numbered register to the register of the second element of the paired memory access instruction.

FIG. 2 shows the flow of processing of the instruction check means 20. In the instruction checking means 20, the pair information setting unit 21 examines the instructions sequentially from the back of the intermediate program, determines whether the focused instruction is a pair memory access instruction (step S1), and determines whether the instruction is a pair memory access instruction. If the pair information (first element,
The second element is set (step S2). The pair instruction assignment information setting unit 22 determines whether the focused instruction is a definition part of a pair memory access instruction (step S3).
Further, it is determined whether the element is the first element (step S
4) If the element is the first element, information for allocating an even register to the definition part of this instruction is set (step S).
5) If it is not the first element, information for assigning an odd register to the definition part of this instruction is set (step S).
6). The above processing is repeated for all instructions.

Next, FIG. 3 shows a flow of processing of the register allocating means 30. The processing of the register allocating means 30 is as follows.
It is performed in order from the first instruction of the intermediate program to the rear. When allocating available registers in order from the first instruction of the intermediate program, the pair instruction definition unit detecting unit 31 determines whether the instruction is a definition unit of a pair memory access instruction (step S11). Then, it is further determined whether the element is the first element (step S1).
2). In the case of the first element, it is determined whether a register has been allocated to the second element (step S1).
3) If the second element has been allocated, a register of the register (odd number) -1 of the second element is allocated to the first element (step S14). If the second element has not been allocated, an even register is allocated to the first element (step S1).
5) Reserve the register of the first element (even number) +1 for the second element (step S16). Reserved registers are not allocated to other than the second element, except in special cases such as a shortage of registers.

On the other hand, if the definition part of the pair memory access instruction is not the first element (step S12), it is determined whether the first element has been allocated (step S17).
If the first element has been allocated, the register of the register of the first element (even number) +1 is allocated to the second element (step S18). If the first element has not been assigned,
The register of the even register + 1 is assigned to the second element (step S19), and the even register is reserved for the first element (step S20).

Next, referring to FIGS. 4 and 5, specific examples of register allocation will be described in comparison with the case of the prior art and the case of the present embodiment. FIG.
FIG. 5 shows an example of a source program described in FORTRAN, and FIG. 5 shows an example in which registers are assigned to a part of the program shown in FIG. In particular, FIG.
5A shows an example of register allocation according to the prior art, FIG.
(B) shows an example of register allocation according to the embodiment of the present invention.

FIG. 5 is an example of a translation result of the following part which is a part of the program of FIG. 4, DO 20 J = 1,5 IB (J) = IA (J, J) +1 20 CONTINUE. In order to make the explanation easy to understand, it is expressed in assembler instruction format. Further, in the description of the source program, J is looped five times from 1 to 5, but here, optimization by loop unrolling is performed to speed up the processing.

In FIG. 5A, the meanings of the instructions on each line are as follows. grN represents a general-purpose register N. The target computer is assumed to have one word = 4 bytes.

(1) I in the address of gr4 + 0
The contents of A (1,1) are loaded into gr18.

(2) gr18 and the initial value 1 of J are added.

(3) The leading address of IB (J) contained in $ 000001 + 640 is entered in gr19. Note that the orn instruction is an instruction that takes a logical sum (or), and the value of gr0 is always calculated as 0, so
The address of 00001 + 640 will be in gr19.

(4) Load the contents of IA (2,2) contained in the address of gr4 + 44 into gr20.

(5) gr20 and the rotation value 2 of J are added.

(6) IA contained in gr18 (1, 1)
+1 is stored in IB (1) of gr19 + 0.

(7) IA contained in gr20 (2, 2)
+2 is stored in gr19 + 4 IB (2).

(8) The contents of IA (3,3) contained in the address of gr4 + 88 are loaded into gr21.

(9) gr21 and the rotation value 3 of J are added.

(10) The contents of IA (4, 4) contained in the address of gr4 + 132 are loaded into gr22.

(11) gr22 and the rotation value 4 of J are added.

(12) IA contained in gr21 (3,
3) Store +3 in IB (3) of gr19 + 8.

(13) IA contained in gr22 (4,
4) Store +4 in IB (4) of gr19 + 12.

(14) The contents of IA (5, 5) contained in the address of gr4 + 176 are loaded into gr23.

(15) gr23 and the rotation value 5 of J are added.

(16) IA contained in gr23 (5,
5) Store +5 in IB (5) of gr19 + 16.

As shown in FIG. 5A, in the conventional allocation, the register g in the definition part of IA (1,1) in row (1)
The register gr20 is allocated to r18 in the definition part of IA (2, 2) in the row (4). This is because the register gr19 is allocated to the instruction related to the start address of the IB (J) in line (3) between the two definition units. Therefore, the store instruction of IA (1,1) +1 in row (6) and the store instruction of IA (2,2) +2 in row (7) cannot be executed as a pair memory access instruction, and are executed by two single instructions. Instructions have been expanded to be

The register gr21 is allocated to the definition part of IA (3, 3) in row (8), and the register gr22 is allocated to the definition part of IA (4, 4) in row (10). Although these allocated registers are continuous,
Since the sequence starts with odd registers gr21 and gr22, a store instruction to IB (3) in line (12) and a line
(13) The store instruction to the IB (4) cannot be executed as a pair memory access instruction, and the instructions are expanded so that each is executed by a single instruction.

According to the present invention, the instruction check means 20 uses the instruction check means 20 to allocate the lines (6), (6) in FIG.
When a pair memory accessible instruction such as (7) or (12) or (13) is detected, the information of the pair is stored, and the pair instruction assignment information is set to the instruction of the definition part. Keep it. Therefore, by the register allocating means 30,
The register of the even element can be assigned to the definition part of the first element, and the register of the even register + 1 can be assigned to the definition part of the second element, and the registers can be assigned as shown in FIG.

That is, according to the present invention, as shown in FIG. 5B, the register gr is stored in the definition part 1 of IA (1, 1) in row (1) ′.
18 is allocated, and the register gr19 is reserved for the second element. Therefore, the register gr20 is allocated to the instruction in the row (3) ′ during this period, and the register gr19 is allocated to the definition part 2 of the IA (2, 2) in the row (4) ′. As a result, the store of IA (1, 1) in row (6) and the store of IA (2, 2) in row (7) in FIG. As described above, one pair memory access instruction (st.
1). Line (6) 's
t. The l instruction is IA (1,1) in gr18 +
1 is stored in IB (1) indicated by gr20, and IA (2, 2) +2 stored in gr19 is stored in IB (1).
This is an instruction to store in IB (2) following (1).

Also, the definition part 3 of the IA (3, 3) in line (8) '
Assigns the register gr22 to the definition part 4 of the IA (4, 4) in the row (10) '. This gives
The reference part 2 of the register gr22 and the register gr23 (row (1
2) '), IB (3) and IB of these pair registers
(4) can be executed by a pair memory access instruction (st.li9).

[0044]

As described above, according to the present invention,
Successive memory access instructions can always be assigned to a pair of registers, an even register and an odd register. As a result, by executing the pair instruction,
It becomes possible to improve the execution performance of the program resulting from the translation.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating an example of a block configuration according to the present invention.

FIG. 2 is a diagram showing a flow of processing of an instruction check unit.

FIG. 3 is a diagram showing a processing flow of a register allocating means.

FIG. 4 is a diagram illustrating an example of a source program.

FIG. 5 is a diagram showing an example of register allocation.

FIG. 6 is a diagram for explaining a conventional technique.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Processing apparatus 2 Source program 3 Object program 10 Compiler 11 Source program analysis part 12 Optimization part 13 Register allocation part 14 Scheduling / code generation part 20 Instruction check means 21 Pair information setting part 22 Pair instruction allocation information setting part 30 Register allocation means 31 Pair instruction definition part detection part 32 Pair register allocation part

 ──────────────────────────────────────────────────続 き Continued on the front page (72) Inventor Naofumi Sugimoto 4-15-33 Shibaura, Minato-ku, Tokyo Inside Fujitsu BSC Ltd. (72) Inventor Kiyofumi Suzuki Kamiodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture 4-1-1, Fujitsu Limited (72) Inventor Koji Takahara 4-1-1, Kamikodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture Fujitsu Limited (72) Inventor Judo Koizumi 18-1 Minamicho, Shizuoka City, Shizuoka Prefecture No. Fujitsu Shizuoka Engineering Co., Ltd. (72) Inventor Masato Morishima 18-1 Minamicho, Shizuoka City, Shizuoka Prefecture Inside Fujitsu Shizuoka Engineering Co., Ltd. (72) Kenichi Yamamoto 181-1 Minamicho, Shizuoka City, Shizuoka Prefecture Co., Ltd. Within Fujitsu Shizuoka Engineering (72) Inventor Yasunobu Tanimura 18-1 Minamicho, Shizuoka City, Shizuoka Prefecture Fujitsu Shizuoka Co., Ltd. Inside engineering (72) Inventor Akira Kusakabe 18-1, Minamicho, Shizuoka-shi, Shizuoka Prefecture Inside Fujitsu Shizuoka Engineering Co., Ltd. (72) Inventor Nobuka Yamaji 4-1-1 Uedanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Fujitsu Stock In-house F-term (reference) 5B081 CC25

Claims (3)

[Claims] 1. A register allocation processing method in a compile processing device for translating a source program described in a high-level programming language.
A pair memory access instruction that refers to a register is detected,
Setting the pair register information of the pair of the first element and the second element, and determining whether the register allocated by the definition unit is the first element or the second element of the register of the pair memory access instruction of the reference unit And assigning an even register when the register to be assigned by the definition unit is the register of the first element, and assigning an odd register following the even register when the register to be assigned is the register of the second element. Register allocation processing method. 2. A compiling apparatus for translating a source program described in a high-level programming language,
At the time of register allocation, a pair memory access instruction referring to the register is detected, pair register information of a pair of the first element and the second element is set, and the register allocated in the definition unit is the first register of the instruction of the reference unit. It is determined whether the element is a second element or not. If the element is the first element, information for allocating an even register to the definition part of this instruction is set. Instruction check means for setting information for assigning an odd register to the definition unit; and assigning an even register when the register to be assigned in the definition unit of the instruction is the register of the first element, and assigning an even register when the register of the instruction is the register of the second element. Register allocating means for allocating an odd register following the even register. 3. A program recording medium of a compiler for translating a source program described in a high-level programming language, wherein a pair memory access instruction that refers to a register is detected when a register is allocated, and a first element and a second element are read.
A process of setting pair register information of an element pair, a process of determining whether or not a register to be allocated by a definition unit is a first element or a second element of a register of a pair memory access instruction of a reference unit; Recording a program for causing a computer to perform an operation of allocating an even register when the register to be allocated by the section is the register of the first element, and allocating an odd register following the even register when the register to be allocated is the register of the second element. A program recording medium for a compiler, comprising: