JPS58161045A - Register management method in compiler - Google Patents

Abstract

PURPOSE:To obtain easily use information of registers without a register information table, by adding a register use information bit to a code and moving the code with the register use information bit added as it is when the code is subjected to the movement processing. CONSTITUTION:A code generating part 1 generates an object code from a source program and adds the register use bit to the object code and stores it in an instruction memory 4. When judging that two codes stored in the memory 4 should be compounded, a compound instruction conversion processing part 2 sets addresses of these codes to registers 8 and 9 and the register use information bit to an information selecting register 10 and indicates this judgment to a register managing part 3. The managing part 3 manages the register use state of codes stored in the memory 4 and checks use information in a ragne designated by the processing part 2 and sends register use information in the designated range to the processing part 2 through a register 11. The processing part 2 compounds codes in two addresses to generate a compound instruction and stores this instruction in the memory 4 through an input/output register 5.

Description

Detailed Description of the Invention (1) Technical Field of the Invention The present invention relates to a register management system KIIL in a compiler.
, ``I'' relates to a raster management method that allows register usage information to be easily obtained when performing processing related to registers of a machine (for example, register allocation, optimization).

(2) Technical background A technology that generates object code from a source program written in a high-level language.

Register management is performed when processing related to the registers of the machine (for example, register allocation, optimization).

In order to perform register 0IIIjII accurately, register usage information in each code generated by Konnokuira is required. Therefore, the compiler uses some method to obtain register usage information for each code, and stores this obtained information in some form. Konno Kuirasha refers to this information and performs register-related processing such as register allocation and optimization.

For example, this will be explained in the case where the machine has the following characteristics (1) to (2).

■It has two registers, A and H.

■Transfer command from memory to human register and from memory to B
Has a transfer instruction to a register.

■i! There are four instructions (hereinafter referred to as compound instructions) that can execute the two instructions marked #■ at the same time.

As an optimization for a compiler that generates code for a machine with such characteristics, it finds the two transfer instructions in item II (ii) from the code generated by the compiler, and converts them into the compound instructions in item (iii) above. can be given. Making such complex instructions improves the machine's interleaving efficiency and memory usage efficiency, and the point of compiler performance evaluation is to do this effectively.

The contents of the compound instruction conversion performed by this compiler are as follows.

■' Transfer command from memory to A register (MOWNA
memory) and a transfer instruction from memory to B register (MO
VER memory).

■'Check whether this pair can be converted into one instruction as a compound instruction.

dIf there is a pair that can be made into a compound instruction, the two codes are changed into one code.

That is, as shown in FIG. 1(a), the code 1 in FIG.
You can see a pair of code 2 and code 2.

Next, use the code between Jin's code 1 and code 2 to check the usage status of the M register and B register.

In the code between code 1 and code 2.

Unless both the A register and the B register are used (i.e., the process in a), as shown in FIG. 1 (b),
A single instruction is converted into a compound instruction having the function of a transfer instruction from the memory to the register and the B register respectively (processing jl of 1111 ■').

In this way, if the A register is not used between code 1 and code 2, the compound instruction is executed as described above, but as shown in FIG. and B registers are used (for example, A
When there is an ADD instruction that adds a register and a B register), code 1 and code 2 are converted into a compound instruction as shown in FIG. 2 (b).

When converted into a single code, the execution result of the resulting code will be different from the original code.

This is incorrect. In other words, A in Figure 2 (b) K
Since the A register used in the DD instruction does not contain the contents transferred from memory written in the human register at code 1, it is different from the 7 execution result of the original code shown in Figure 2 (a). Becomes the property of

Therefore in the code generated by the compiler.

The compiler generates register information indicating which code is using the contents of the two registers A and B (hereinafter referred to as "use") or whether data is being written in the two registers B (hereinafter referred to as "d@f"). However, it is not possible to obtain the correct result unless it is made into a compound instruction.

(3) Prior art and interlayer points As mentioned above, in order to optimize the code generated by the compiler by converting it into complex instructions, the compiler needs to have accurate register information for each code it generates.

Generally, register-related processing that involves code movement (e.g. register allocation optimization) is performed before making this complex instruction, and of course such register-related lI &
Weir also requires complex instructions and register usage information for the same machine.

After this register-related processing that involves code movement, rounding to correctly convert the code into a compound instruction requires performing register processing while paying attention to changes in register characteristics.

Using the traditional register management method, the compiler generates 9 codes and checks the operands and operands of each code.
Two register usage information vse used in this code
and def, i.e. Are you using registers (US
e)・I am creating an information table for register management employment in order to find out whether it is on the register (def).

For example, as shown in FIG. 5(a), when nine codes generated by the compiler are written in the instruction memory MRM (
In addition, the numbers on the left side in Figure 5 (a) indicate the code name)
From this, an information table T for managing registers shown in FIG. 5(b) is created. Here aυ, (7) is the fifth
Figure ((shows the numbers on the left in IK).

This shows that data is written from the memory in the A register by the code of order fiυ, and data is written from the memory in the hood of the B register company order 4.

At this time, for optimization of register assignment.

For example, the code shown in the order αυ in Figure 3 (a) is
When the order is moved to a9 as shown in Figure (A) K, the contents of the information table T for register management are changed accordingly, as shown in Figure 4 (B) K. Otherwise, it is not possible to correctly execute compound instruction conversion performed by referring to the print information table T.

In other words, in order to correctly perform compound instructions using the conventional register management method, it is essential to modify the register management information table, which requires a lot of effort. If you don't do corrective geography, before you do compound imperatives.

It is necessary to again check the operands and operands of the code generated by the compiler and create a new information table for register management.

It requires more work.

4) Purpose of the invention To perform the easy implementation of the present invention, register '1131.

The present invention provides a register management system in the computer 7 that does not use such an information table that requires rewriting every time a code is moved.

(5) Structure of the Invention The ninth feature of the present invention to achieve this purpose is to use a source code written in a high-level language.
In a compiler that creates object code from a program, code generation means adds register usage information of registers used by the object code; code memory means writes code to which the register usage information is added; The present invention has an instruction means for instructing an investigation range of the code memory means, and a register usage information extraction means for extracting the register usage information, and checks register usage information packets added to codes within the range to be managed. A feature of this system is that the register management is performed automatically.

(61 Embodiment of the Invention Before describing in detail one embodiment of the present invention, its outline will be explained based on FIGS. 5 to 8.

In the present invention, when generating a code No. 7 (an object) from a source program, use information bits b of four registers of the machine are added to the generated code, as shown in FIG. For example, when adding an area indicating the use and def f of the #i register and the B register to the code, take a 4-bit area from b1 to b4 in the column and code, and write "A register, B register" as shown in Figure 6. rOJ and rIJ are determined according to the states of the registers uae and daf. Each bit for this register information is set as a color when the code is generated.

-” set. All register management in register-related processing is performed by checking the register usage information bit b added to the code, eliminating the need for an information table for register management.

For example, as shown in FIG. 7(a), the instruction memo jJ MBM
When writing the code generated by code 7 (Ira) shown in σ above, write the register usage information in that code. In other words, in the code **U in Figure 7 (a), the code from memory is stored in the mu register. “1” is written in bit b1 indicating rounding Kd@f to transfer data, and 11
In the code number (to), data is transferred from memory to the B register, so "1" is written in ba for the same ant.

Therefore, if there is a shift of the code to the position shown in FIG. 7(b) K in register-related processing for the code in order I, it is sufficient to simply move the code.

When converting into compound instructions, a part of the code generated by Con7 (Ira) is in the state shown in FIG. 8 (A).

**aS and code (2) are candidates for this compound instruction.

This coat is used to combine these go-dos.

It is necessary to check whether the bear can be converted into a compound instruction or not. At this time, the usage status of the A register and B register in job numbers a to lI is checked. In this case, each code has register usage information bits bI-b4
You can easily get information on their usage by checking . As a result of these checks, if all the us@ information bits of the A register from kabanka to alt are "0", the code in the order α$ and (to) can be converted into a compound instruction. As a result, as shown in Figure 18 (b), <, J[I(+49 and (
The code in 2) can be converted into one compound instruction.

Next, the configuration of an embodiment of the present invention will be described based on an IS9 diagram.

In the figure, 1 is a code generation section, 2 is a composite instruction processing section, 5 is a register management section, 4-line instruction memory, 5 is a Hiro input/output register, 6 is an output register, 7 is an instruction address register, 8
is the first address register.

9 is a second address register, 10 is an information selection register, 11 is a usage information register, 12 is a fifth address register, 15 is a fourth address register, 14 is a fifth address register, 15 is a first information register. register, 16 is the second
Information register 17 is an information accumulation register, 18 is a third information register.

1? 20 is an address/count-up section, 21 is an AND operation section, 22 is an OR operation section, and 25 is a controller 4-2.

The code generation unit 1 generates object code from a source program, and the generated code is held in the instruction memory 4.

If there is a code that can be compounded among the nine codes generated by the code generating section 1, it detects it and creates a compound instruction.

The register management unit 3 manages the usage status of registers in the code stored in the instruction memory 4. The register management unit 3 manages the usage status of registers in the code stored in the instruction memory 4. This is a check.

The instruction memo 4 stores the food generated by the compiler by the code generation unit 1, and corresponds to the instruction memo IJMEMK shown in FIGS. 7 and 8. Inside this instruction memory 4, a code in a format as shown in FIG. 5 is written, that is, an instruction code and register usage information bits b1 to b4.
The definition of b4 is as shown in FIG.

The input/output register 5 receives a code from the code generation section 1t or the complex instruction processing section 2 and inputs it to the instruction memory 4, or is set with a code output from the instruction memory 4.

The output register 6 is configured to output nine codes from the instruction memory 4 and to output the register usage information (P) to b4 to the outside.

Instruction address register 7 This is an address register in which an address for accessing the instruction memory 4 is set.

The first address φ register 8 is set with an address indicating from which code in the instruction memory 4 register management is to be performed.This address is received from the compound instruction processing unit 2 and transmitted to the register management unit 3. It is something to do.

The second address register 9 stores an address indicating which code trench in the instruction memory 4 is used for register management. It is something that is communicated.

The information selection register 10 instructs which bit of the register usage information bits b1 to b4 added to the code is to be extracted.
12 and is transmitted to the register management section 15. If you want to retrieve the A register's def state and the B register's def state, register usage information bit b
, and b4 only need to be taken out. At this time, company information selection register 100 bit b.

Selection instruction information is written in which the other bits bl and b4 are respectively "1" and "0".

Usage information register 11 Register usage information sent from the welfare register management section 5 is set therein.

The g15 address register 12 is a register in which the address of a code that extracts register usage information from the instruction memory 4 is set.

The fourth address register 13 is set with an address issued from an address determination section 19, which will be described later.

The fifth address register 14 is outputted from an address Q count up section 2o, which will be described later. The address next to the address set in the fourth address register 13 is set.

In the first information register 15, the register usage information bits b, to b4 added to the instruction memory 4 and the bladder release code are set.

The second information register 16 is used to set register use information output from the AND operation section 21, which will be described later.

Register use information read from the instruction memory 4 is accumulated.

The fifth information register 18 is set with register usage information output from the OR operation unit 22 described in 41.

Address judgment 1119Fi, 2nd address register?
and the address set in 5th address register 1
It is set to 2 and determines whether or not the 9th address matches or not, and when there is a match, this is reported to the controller 25, which will be described later.

Address fist count up part 20a, Ii4at VX・
The address set in the register 15 is incremented by one and this is output to the fifth address register 14.

The AND operation unit 21 selects the selection instruction information set on the information selection register 1o (the bit to be extracted is "1" and the others are "0") and each bit bI to b of the first information register 15.
This is an AND operation corresponding to every 4 bits.

The OR operation unit 22 performs an OR operation on each bit of the register use information set in the second information register 16 and the information accumulation register 17, respectively.

The controller 25 collectively controls the register management s5, and when it receives a start signal from the compound instruction processing unit 2, it composes the signal that started the register management unit 5 and the signal that register management has finished. Instruction processing unit 2
The address judgment unit 19, address count up unit 20, and operation unit 21. It performs various controls such as instructing the OR operation section 22 to start up, and outputting register usage information from the digital management section 3 in response to an end signal from the artless determination Wh19.

Next, the operation shown in FIG. 9 will be explained.

■ Now, the code in the state shown in Figure 5 is created by the code generator 1, and this is stored in the instruction memory 4 in the state shown in Figure 8 (a) K. i
t is the book corresponding to the address of the instruction memory 4. Then, when the compound instruction conversion processing section 2 monitors the code creation status of the code generation section 1 and determines that the code stored at address "15" and address "20" of the instruction memory 4 should be converted into compound instructions. , from address "16" to address r
It must be checked that the code existing between lWJ does not use the A and B registers in the del state. Therefore, the compound instruction processing unit 2 sets the address "16" in the first address register 8, sets the address "19" in the second address e register 9, and sets the bit corresponding to k)l+b4 in the information selection register 10. Enter "1" in "o i OIJ", each = -
Instructs to select information for the code, b4. Then, the compound instruction processing section 2 sends out a register management section SK activation signal.

■ When the control unit 23 receives the activation signal from the complex instruction processing unit 2, the address determination unit 1? , address count-up section 20. AND operation section 21. The OR operation section 22 is activated.

■ Atrace "16" set in the first address register 8 is set in the fifth address register 12. The address “16” set in the third address register 12 of the address determination unit 19 is the second address.
Since the address "19" set in register 9 is not reached, the address set in third address register 12 is output to fourth address register 13, and this is K.
The address "16" is set in the instruction address register 7, the address in the instruction memory 4 is read out, and its code and register usage information are outputted to the output register 6. This register use information is then set in the first information register 15, and the AND operation unit 21 calculates the logical AND of the bits corresponding to b1 to b4[0101J designated by the information selection register 10. Therefore, when the code written at address "16" of the instruction memory 4 does not use the A register and the B register, [0OOOJ is set in the first information register 15.

The AND operation section 21 outputs [0OOOJ.

This is set in the second information register 14.

(2) The nine data set in the second information register 16 are transmitted to the third information register 18 via the OR operation section 22, and then set in the information accumulation register 17.

■ On the other hand, the 'J4 address register 13 is incremented by p+1 by the seventh step section 20 and becomes "17", which is then sent to the third address register 12 via the $5 address register 14.
is set to And this address j17J is the address rl? set in the second address register 9? A determination is made as to whether JK has been reached, and then this address "17" is stored in the fourth address register 1.
3, and the instruction memory 4 is accessed in the same way. Then, the register use information of the code at address "17" is set in the first information register 15, and the AND operation section 21 performs the same AND operation as described above.

0 When these steps are performed in sequence and the address [19J is set in the third address register 12, the address determination unit 19 informs the controller 25 that this address is the value set in the second address register 9. Report that it matches.

This address "19J" is output to the fourth address register 15. The controller 25 thereby stops the operation of the address count-up section 200.

In the instruction memory 4, the fourth address register 15
An access is made to the address "1? As in the case, an AND operation is performed and this is set in the second information register 16, and this and the address set in the information accumulation register 17 are
The register usage information from addresses "16" to "19" is ORed in correspondence with the bits and passed through the gJ5 information register 18, and then the register usage information from addresses "16" to "19" is stored in the information accumulation register 17. Set. Then, the output command from the controller 23 is transmitted to the OR operation unit 22, so the OR operation unit 22 transfers the register usage information accumulated in the information accumulation register 17 via the third information register 18 to the usage information register 11. Output to.

■ If the code written in addresses ``16'' to ``19'' of instruction message 4 does not use register A or register B (in the manner related to bs g ha), ``0000J'' is written in usage information register 11Ka. It turns out.

Finally, the complex instruction processing unit 2 uses the usage information register II.
From the data written in K, it is g* determined that neither the M register nor the B register is used for the code within the address area. As a result, a compound instruction is created by compounding the address "15" and the j20Je:I- code as shown in FIG. 8(b).

Set this in the input/output register 5. Then, the address necessary for setting the controller 4-223 is sent to the instruction address conflict register. Figure 8 (
As shown in b), when a compound command is written in the command message field 4, the result is as follows.

■ However, the addresses "16" and "1" of instruction memory 4
9J 0II4, for example, "ADD A, BJ like K.

If there is a code that adds the data of the person register and the data of the B register and sets this to the mu register, the register usage information is written as "1110", and as a result, the usage information register 11 is written as "1110". is “010
0J (because bs+bs is rQJ with information 1 selected and register 10) is output from the register tube 1uls. The joining instruction processing unit 2 thereby determines that the code for rewriting the A register exists at addresses "16" to "19", and
In such a case, the collaborating command processing is not performed.

In the above description, an example has been described in which two registers, the M register and the B register, are used, but of course the number of registers to be managed is not limited to only two, and can be increased as appropriate. The usage bits will also increase accordingly.

(7) Effects of the Invention According to the present invention, a register usage information bit is added to the code, and when the code is moved, 11 moves with this register usage information bit added are performed, so all register management layer lines in register related processing are This can be done by checking the register usage information bit added to the code. Therefore, there is no need to create a register information table that needs to be rewritten as the code is moved, unlike in the past.

As described above, according to the present invention, not only can register information be checked against harmful birds, but also there is no need to modify the register information table as the code is moved. It has depth.

t 5uite Brief Explanation 1st is an explanatory diagram of the Kakakugokai ordering process, Figure 2 is an explanatory diagram of the case where the payment inspection ordering process is not possible, and Figure 3 is an explanatory diagram of the case where the payment inspection ordering process is not possible.

4Ill is an explanatory diagram of conventional register management and interlayer points, 1L FIG. 6 is a generated code in the present invention and its explanatory diagram, FIGS. 7 and 8 are explanatory diagrams of the operation of the present invention,
The following is a diagram showing the configuration of an embodiment of the present invention.

In the figure, 1 is a code generation section, 2 is a capital instruction processing section, 3 is a register management section, 4 is a basic instruction memory, 5 is an input/output register, 6 is an output register, 7 is an instruction address register, a
is the first address fist register.

9 second address register, 10 information selection register, 11 usage information register, 12 fifth address register, 13 jl14 address register/, 14til
15 address register; 15 is first information register; 1
6 companies 2nd information register x evening sty is information accumulation register, 18
is the fifth information register.

Reference numeral 19 designates an address determination section, 20 an address e-power unloading section, 21 an AND operation section, 22 an OR operation section, and 25 a controller.

Patent applicant Fujitsu Ltd. Representative Patent Attorney Akira Yamatani 21 O1I121T)
(b) f4PjJ (b)
(q) Age 5 code ゛ bhbb househi θm, a)

Claims (1)

[Claims] (1) In a compiler that creates object code from a source program written in a high-level language, code generation means adds register usage information of registers used by the object code. a code memory means for writing a code to which the register usage information is added; an instruction means for instructing a survey range of the code memory means; and a register usage information extraction means for extracting the register usage information; 1. A register management method in a compiler, characterized in that register management is performed by checking register usage information added to code within a target range.