JPH0522936B2 - - Google Patents

Description

[Detailed description of the invention]

[Industrial Application Field] The present invention relates to a register tracing method for eliminating redundant load instructions for registers during optimization processing for eliminating redundant instructions in an assembler source program. [Constitution of Conventional Example and its Problems] Conventionally, register tracing has been performed as a method of optimizing an assembler source program. FIGS. 1A and 1B are flowcharts in assembler language for explaining the register tracing method, respectively. 1, 4, 7, 1', 4', 7'
is a load instruction that assigns the contents of variable A to register R, 2, 5, 2', and 5' are a group of instructions that do not include branch instructions that do not change the contents of register R, and 3 and 3' are conditional branch instructions. Among these, load command 4,
7, 4', and 7' are redundant and can be deleted.
This is because branch instructions generally do not change the contents of registers, so the contents of variable A assigned to register R by load instructions 1 and 1' are preserved. In the conventional register tracing method, load instructions 4 and 4' can be deleted, but load instructions 7 and 4' can be deleted.
7' cannot be recognized as being redundant and cannot be deleted. The reason for this is that only one set of register trace memory is used to store the contents currently stored in the registers in the CPU, so when the program flow is divided into two by a branch, there is a register trace memory for each path. This is because conventionally, register tracing was performed for only one of the two paths and the other path was ignored. Therefore, the contents currently stored in the registers in the CPU for the route whose register trace was ignored cannot be determined, so after the confluence of the two routes, the previous register trace must be cleared and a new register trace must be started. It was impossible. [Object of the Invention] An object of the present invention is to provide a register tracing method that can recognize and delete more redundant load instructions. [Structure of the Invention] The register tracing method of the present invention includes a plurality of register trace memories that store source operands of load instructions to registers for each register in an assembler source program, and one register trace memory of the plurality of register trace memories. A register trace memory specifying means is used to select a register trace memory specifying means, and in a single pass of the assembler source program, register tracing is performed using the first register trace memory selected by the register trace memory specifying means. The assembler source program is output by deleting redundant load instructions for the registers in the assembler source program, and at a branch point of the assembler source program, the first register trace memory is transferred to the second register trace memory selected by the register trace memory specifying means. The source operand of the load instruction stored in the register trace memory is copied, and the first and second branch paths branched at the branch point perform register trace using the first and second register trace memories, respectively. By doing this, redundant load instructions for registers in the assembler source program are deleted and the assembler source program is output, and at the confluence of the first and second branch paths, the first
and compares the source operands of the load instruction stored in the second register trace memory, and if there is a register in which the source operand of the load instruction differs, the source operand of the load instruction differs in the register in the first register trace memory. The memory of the source operand of the load instruction is deleted, the second register trace memory becomes unused, and the first register trace memory is used to perform register tracing on the confluence route extending from the confluence point. This is a method of outputting the assembler source program by deleting redundant load instructions for registers in the source program. By using this method, even when the program path is split into two due to a branch, for example, register tracing can be continued on each path, and even after the confluence of the two paths, information on the previous register trace can be retained. Recognize and remove more redundant load instructions by making more efficient use of . [Description of Embodiment] An embodiment of the present invention will be described based on FIGS. 2 to 4. FIG. 2 is a block diagram showing the configuration of a register tracing device for carrying out the register tracing method, in which numeral 10 is an input assembler source program, and numerals 11A to 11N are source operands of load instructions to registers in the assembler source program. A plurality of register trace memories are stored for each register, 12 is a register trace memory specifying means for specifying one of the plurality of register trace memories 11A to 11N, and 13 is a register trace memory specifying means 12
through register trace memories 11A to 11N
A register trace unit stores source operands of load instructions to registers for each register in an assembler source program, and uses the contents to recognize and delete redundant load instructions.
4 is an output assembler source program from which redundant load instructions have been removed in the register trace section 13. Next, the operation of the register trace section 13 will be explained in detail with reference to the flowchart shown in FIG. In the figure, the symbol RT[R] indicates the contents of register R in the register trace memory specified by the register trace memory specifying means 12. In step 30, one instruction is read from the input assembler source program 10. In step 39, it is determined whether the one instruction read in step 30 is a store instruction. This determination is made because when the instruction is a store instruction, the contents of the memory are changed, and the contents of the register R having the same source operand contents are also changed. In step 31, the determination result of step 39 is
If the answer is NO, it is determined whether the instruction read in step 30 is an instruction that changes the contents of step R. In step 32, the determination result of step 31 is
If YES, the register name whose contents are to be changed is stored in register R. In step 33, it is determined whether the instruction read in step 30 is a load instruction to register R. In step 34, the determination result of step 33 is
In case of YES, the source operand loaded into register R is stored in memory MEM.
The source operand of the load instruction is the address to the memory area where the data stored in register R is held. Although the data changes during execution, the address is statically determined. By managing the contents of the registers using this address, it is possible to determine whether the contents of the registers match/mismatch by static inspection. In step 35, the contents of the memory MEM and RT
It is determined whether or not [R] matches. RT
[R] remembers the source operand previously loaded into register R, so when the contents of memory MEM match RT[R] (YES), the contents of the same source operand will be loaded. Therefore, the load instruction read in step 30 is redundant. This redundant load instruction is not output. In step 36, the determination result of step 35 is
In the case of NO, let RT[R] be the contents of the memory MEM. This shows the contents of memory MEM and RT
This is because if [R] does not match, new contents are loaded into register R. In step 40, the determination result of step 39 is
In the case of YES, a register R having the source operand of the store instruction (source operand=RT[R]) is searched in the register trace memory. In step 37, if the above register R exists in step 40, the content RT[R] of the corresponding register trace memory is set to 0. The same applies if the judgment result in step 33 is NO (for register change instructions other than load instructions,
RT[R] is set to 0, and register R stores nothing.) In step 38, the determination result of step 31 is
If NO, or if step 37 or step 36 is executed, that is, if it is determined that the read instruction is not redundant, the read instruction is output as is. Redundant load instructions can be deleted by repeating steps 30 to 40 for all instructions in the input assembler source program. FIG. 4 shows a flow of a program including branches, and in the figure, 20 is a single route, 21 is a branch point of the single route 20, 22 and 23 are branch routes branching from the branch point 21, and 24 is a branch route. 2
The confluence point 2 and 23 and 25 will be referred to as a confluence route extending from the confluence point. When this diagram is made to correspond to an assembler source program, there is a conditional branch instruction at the branch point 21, and a jump destination label of the conditional branch instruction existing at the branch point 21 is at the confluence point 24. With reference to FIG. 4, the processing contents of the register trace unit 13 in a program including a branch will be explained. (a) Single path 20 Multiple register trace memories 11A to 11
One of N, for example 11A, is used to perform the conventional register trace. (b) Branch point 21 (a) A register trace memory other than the register trace memory 11A used in the path 20, for example 11B, is selected by the register trace memory specifying means 12. (a) Copy the contents of the register trace memory 11A used in the path 20 to the register trace 11B. (c) On the branch route 22, the register trace memory 11A used on the route 20 is used, and on the branch route 23, the register trace memory 11B obtained in (a) and (b) is used to create the conventional register. Perform a trace. (c) Junction point 24 (a) Compare the contents of each register in the register trace memory 11B used in the branch route 23 and the register trace memory 11A used in the branch route 22. (a) If a register with the same contents exists, the contents of that register can be used for register tracing after the confluence point 24, so the contents corresponding to this register in the register trace memory 11A are saved as they are. (c) If there is a register with different contents, it means that the register has different contents in the two branch paths 22 and 23 after the branch point 21, and cannot be used for register tracing after the confluence point 24. Therefore, the contents of the register trace memory 11A corresponding to this register are cleared to indicate that no data is stored in the register. Then, the register trace memory 11B is made unused. (d) Merging route 25 Register trace memory 11A obtained in (c)
Perform traditional register trace memory using . In this way, multiple register trace memories 1
By performing the above processing using 1A to 11N, register tracing can be continued for all paths of the program including branches, which could not be performed with conventional register tracing. This makes it possible to recognize and delete more redundant load instructions, thereby further reducing the size of the program. Note that even if the branch paths 22 and 23 include a branch, register tracing can be performed in the same manner by using a newer register trace memory at the branch point. [Effects of the Invention] According to the register tracing method of the present invention, more redundant load instructions can be recognized and deleted, and the program can be made smaller. Further, since the configuration is such that the source operand of a load instruction to a register in an assembler source program is stored for each register using a plurality of register trace memories, more detailed management can be performed in register trace. Further, since the configuration has register usage information only regarding the registers that the machine has, the register usage information is constant regardless of the amount of source programs to be compiled, and only a small amount is required, so that the size of the compiler can be reduced. Furthermore, since the configuration is such that the entire program path is traced, that is, the trace is performed taking branching and merging into account, the optimization effect is high. In addition, the entire path of the program can be inspected simply by storing the source operands of register load instructions for each register in the register trace memory and comparing them, which simplifies the compiler configuration. Compilation time is also reduced.

[Brief explanation of the drawing]

1A and 1B are assembler language flowcharts for explaining each conventional register trace, FIG. 2 is a block diagram of an embodiment of the present invention, and FIG. 3 is a flowchart showing the operation of the register trace section. Chart FIG. 4 is an explanatory diagram of the flow of a program with branches. 10... Input assembler source program, 11
A to 11N...Register trace memory, 12...Register trace memory specifying means, 13...Register trace unit, 14...Output assembler source program.

Claims (1)

[Scope of Claims] 1. A plurality of register trace memories that store source operands of load instructions to registers for each register in an assembler source program, and a register trace memory that selects one of the plurality of register trace memories. By using a specifying means, in a single pass of the assembler source program, register tracing is performed using the first register trace memory selected by the register trace memory specifying means, so that redundant registers for registers in the assembler source program can be traced. The load instruction is deleted and the assembler source program is output, and at a branch point of the assembler source program, the second register trace memory selected by the register trace memory specifying means is stored in the first register trace memory. The assembler source is copied by copying the source operand of the load instruction that has been executed, and performing register tracing using the first and second register trace memories, respectively, in the first and second branch paths branched at the branch point. The assembler source program is output by deleting redundant load instructions for registers in the program, and at the confluence of the first and second branch paths, the first
and compares the source operands of the load instruction stored in the second register trace memory, and if there is a register in which the source operand of the load instruction differs, a register in which the source operand of the load instruction differs in the first register trace memory. The memory of the source operand of the load instruction for is deleted, the second register trace memory is left unused, and the first register trace memory is used to perform register tracing on the confluence path extending from the confluence point. A register tracing method that deletes redundant load instructions for registers in a source program and outputs the assembler source program.