JPH0527986A - Compiler optimization method and optimization apparatus - Google Patents

Abstract

(57) [Summary] [Object] To provide an optimizing method and an optimizing device of a compiler that can delete an unnecessary comparison instruction and generate a target program with high execution efficiency. [Construction] A loop-invariant variable determination unit 1 detects the presence of a comparison instruction for comparing a loop-invariant variable with a constant or another loop-invariant variable and a conditional branch instruction associated with this comparison instruction in a loop. Register setting instruction generator 2
Generates an instruction sequence for storing the branch destination address in a register in accordance with the loop invariant variable detected by the loop invariant variable determination unit 1 immediately before the loop. Comparison / branch instruction replacement unit 3
Replaces the comparison instruction and the conditional branch instruction detected by the loop invariant variable determination unit 1 with an unconditional branch instruction for the address in the register set by the instruction sequence generated by the register setting instruction generation unit 2.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a compiler optimizing method and an optimizing device for improving the execution efficiency of a target program.

[0002]

2. Description of the Related Art In recent years, with the development of a RISC type microprocessor, a compiler having a high degree of optimization function has been developed in order to bring out its performance. In such an optimizing compiler, reducing the number of instructions in the loop greatly contributes to the improvement of the execution efficiency of the target program.

A conventional compiler generates a target program as shown in FIG. 4, for example. In this target program, instructions are sequentially executed one by one by the processor. In the comparison instruction 31, the content of the variable VAR1 is compared with the constant 0. Next, the conditional branch instruction 32 determines whether to branch to the label 33 or to execute the next instruction of the conditional branch instruction 32 without branching according to the result of the comparison instruction 31, and control to either address. Transfer. After that, the subsequent instructions are sequentially executed, and each instruction of the loop 34 is repeatedly executed until the loop end condition is satisfied.

[0004]

However, in the above object program, when the variable VAR1 is invariant in the loop 34, the branch destination by the conditional branch instruction 32 is also invariant, but the loop 34 is executed every time. However, there is a problem in that an unnecessary comparison instruction 31 is executed every time the execution of the.

The present invention has been made in view of the above circumstances, and it is an object of the present invention to provide an optimization method and an optimization device for a compiler that can delete unnecessary comparison instructions and generate a target program with high execution efficiency. To aim.

[0006]

The invention according to claim 1 is an optimization method adopted in a compiler for generating a target program by using a source program written in a high-level programming language as an input, which is loop-invariant in a loop. A loop invariant variable detecting step for detecting the presence of a comparison instruction for comparing a variable with a constant or another loop invariant variable and a conditional branch instruction related to this comparison instruction, and the loop detected in this loop invariant variable detecting step The register setting instruction generation step of generating an instruction sequence for storing a branch destination address in a register according to an invariant variable immediately before the loop, the comparison instruction detected in the loop invariant variable detection step, and the conditional branch instruction The address in the register set by the instruction sequence generated in the register setting instruction generation step It is characterized by performing the comparison-branch instructions replacing step of replacing the unconditional branch instruction to scan.

A second aspect of the present invention is an optimizing device that is used in a compiler that generates an object program by using a source program written in a high-level programming language as an input. A loop invariant variable detection unit that detects the presence of a comparison instruction that compares with a loop invariant variable and a conditional branch instruction related to this comparison instruction, and a loop invariant variable that is detected by this loop invariant variable detection unit A register setting instruction generation unit that generates an instruction sequence for storing a branch destination address in a register immediately before the loop, a register setting instruction generation unit that generates the comparison instruction and the conditional branch instruction detected by the loop invariant variable detection unit. Comparing with an unconditional branch instruction for the address in the register set by the instruction sequence generated in the section It is characterized in that a branch instruction substitution unit.

[0008]

According to the first aspect of the present invention, the loop invariant detecting the presence of a comparison instruction for comparing a loop invariant variable with a constant or another loop invariant variable and a conditional branch instruction related to the comparison instruction in the loop. In the variable detection step, the register setting instruction generation step that generates the instruction string that stores the branch destination address in the register according to the loop invariant variable detection step immediately before the loop, and the loop invariant variable detection step A comparison / branch instruction replacement step of replacing the detected comparison instruction and conditional branch instruction with an unconditional branch instruction for the address in the register set by the instruction set generated in the register setting instruction generation step is executed.

In the second aspect of the present invention, the loop invariant variable detection unit has a comparison instruction for comparing the loop invariant variable with a constant or another loop invariant variable and a conditional branch instruction related to the comparison instruction in the loop. Detect that. The register setting instruction generation unit generates an instruction sequence for storing the branch destination address in the register according to the loop invariant variable detected by the loop invariant variable detection unit immediately before the loop.
The comparison / branch instruction replacement unit converts the comparison instruction and the conditional branch instruction detected by the loop invariant variable detection unit into an unconditional branch instruction for the address in the register set by the instruction sequence generated by the register setting instruction generation unit. Replace.

[0010]

Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 1 is a block diagram of an optimizing device for a compiler according to an embodiment of the present invention. This optimizing device includes a loop invariant variable determining section 1, a register setting instruction generating section 2,
It is composed of a comparison / branch instruction replacement unit 3. The loop invariable variable determination unit 1 detects that there is a comparison instruction for comparing the loop invariant variable with a constant or another loop invariant variable and a conditional branch instruction related to this comparison instruction in the loop. In this specification, a loop invariant variable means a variable that is invariant in the loop. The register setting instruction generation unit 2 generates an instruction sequence for storing the branch destination address in the register according to the loop invariant variable detected by the loop invariant variable determination unit 1 immediately before the loop. The comparison / branch instruction replacement unit 3 unconditionally compares the comparison instruction detected by the loop invariant variable determination unit 1 and the conditional branch instruction with the address in the register set by the instruction sequence generated by the register setting instruction generation unit 2. Replace with a branch instruction.

FIG. 2 is a block diagram of the target program of FIG.
FIG. 6 is an explanatory diagram of a target program optimized by a compiler that employs the optimization device of FIG. Next, the operation of the optimizing device in FIG. 1 will be described. First, the loop invariant variable determination unit 1
The comparison instruction 31 and the conditional branch instruction 32 that compare the loop invariant variable and the constant in the loop 34 before optimization are detected. Since the content of the loop invariant variable detected by the loop invariant variable determination unit 1 has already been determined before entering the loop 34, the branch destination of the conditional branch instruction 32 is determined before entering the loop 34. be able to. Next, the register setting instruction generator 2 generates a register setting instruction sequence 11 and inserts it just before the loop 12. The register setting instruction sequence 11 generated here is the address of the instruction executed next to the conditional branch instruction 32 according to the result of the comparison instruction 31 (the address of label 13 or the address of label 14).
Is an instruction sequence for setting a particular register (not shown). A flowchart of this register setting instruction sequence 11 is shown in FIG. The label 13 is a label attached to an address to be executed next when the branch is not performed in the conditional branch instruction 32, and the label 14 is the conditional branch instruction 32.
It is a label attached to the branch destination address (the same address as the label 33) in the case of branching at. Then compare
The branch instruction replacement unit 3 includes a comparison instruction 31 and a conditional branch instruction 32.
And are replaced by the unconditional branch instruction 15. Thus, FIG.
The target program of FIG. 2 equivalent to the target program of FIG.

In this way, a comparison instruction for comparing a loop invariant variable in a loop with a constant or another loop invariant variable and a conditional branch instruction associated with this comparison instruction are detected,
Since this is replaced with a single unconditional branch instruction, the number of instructions in the loop can be reduced, and unnecessary comparison instructions need not be executed at the time of loop execution, so a target program with high execution efficiency is generated. be able to.

In the above embodiment, the case where the comparison instruction 31 for comparing the loop invariant variable and the constant exists in the loop 34 has been described. However, the comparison instruction for comparing the loop invariant variable with another loop invariant variable has been described. If it exists, it can be treated similarly. Further, in the above embodiment, the optimization method of the present invention is applied to the target program generated by the conventional compiler, but the target program directly optimized by applying the optimization method of the present invention in the intermediate language stage. May be generated.

[0014]

As described above, according to the present invention, a comparison / conditional branch instruction for a loop invariant variable in a loop is detected and replaced with a single unconditional branch instruction. It has an excellent effect that it can be reduced and the execution efficiency can be favorably improved.

[Brief description of drawings]

FIG. 1 is a block diagram of an optimization device according to an embodiment of the present invention.

FIG. 2 is an explanatory diagram of a target program generated by a compiler that employs an optimization device according to an embodiment of the present invention.

FIG. 3 is a flowchart of a register setting instruction sequence in a target program generated by a compiler that employs an optimizing device according to an exemplary embodiment of the present invention.

FIG. 4 is an explanatory diagram of a target program generated by a conventional compiler.

[Explanation of symbols]

1 Loop invariant variable judgment part 2 Register setting instruction generator 3 Comparison / branch instruction replacement unit

Claims (2)

[Claims] 1. An optimization method used in a compiler that generates an object program using a source program written in a high-level programming language as an input, wherein a loop invariant variable and a constant or another loop invariant variable are included in a loop. A loop invariant variable detection step that detects the presence of a comparison instruction to be compared and a conditional branch instruction related to this comparison instruction, and a branch destination address in a register according to the loop invariant variable detected in this loop invariant variable detection step A register setting instruction generating step for generating an instruction string to be stored immediately before the loop, the comparison instruction and the conditional branch instruction detected in the loop invariant variable detecting step, and the instruction string generated in the register setting instruction generating step. Replace with the unconditional branch instruction for the address in the register set by And a comparison / branch instruction replacement step. 2. An optimizing device used in a compiler for generating a target program by inputting a source program written in a high-level programming language, wherein a loop invariant variable and a constant or another loop invariant variable are included in a loop. A loop invariant variable detection unit that detects the presence of a comparison instruction to be compared and a conditional branch instruction related to this comparison instruction, and a branch destination address is registered according to the loop invariant variable detected by this loop invariant variable detection unit. A register setting instruction generating unit that generates an instruction sequence to be stored in the loop immediately before the loop, the comparison instruction and the conditional branch instruction detected by the loop invariant variable detecting unit are generated by the register setting instruction generating unit. A comparison / branch instruction replacement unit that replaces an unconditional branch instruction for an address in the register set by the instruction sequence, A compiler optimizing device characterized by comprising: