JPH0546404A - Branch instruction deletion optimization method - Google Patents

Abstract

(57) [Summary] [Object] The present invention relates to a branch instruction deletion optimization method that deletes and optimizes a branch instruction at the time of translation, and at the time of translation, deletes a branch instruction whose branch destination has already been determined, The purpose is to improve execution performance. [Composition] A comparison / branch deletion processing 2 for deleting a branch instruction is provided when the operand of the judgment statement of the source program (intermediate language) is a constant or the variables are the same, and this comparison / branch deletion processing 2 is the source during translation. When all the operands of the judgment sentence of the program (intermediate language) are constants or when the variables of the operands are the same, the judgment sentence and the instruction that is not the branch destination are deleted and optimized.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a branch instruction deletion optimizing method for optimizing a branch instruction by deleting it during translation.

[0002]

2. Description of the Related Art When a judgment statement is written in a source program, a machine instruction becomes a branch instruction. Conventional compilers generate a machine instruction by directly converting a branch instruction without deleting the branch instruction, even if the branch instruction is fixed at the time of translation. For example, the if statement of the C language source program (intermediate language) shown in FIG. With respect to the above, when the optimization is performed, the values are replaced in the operands a and b of the if statement, as shown in FIG.

[0003]

[0004]

As described above, the conventional i
Even if the branch destination is determined by the f statement or the like, the value (constant) is replaced with the operand of the if statement or the like as shown in (b) of FIG. Since it was translated to, the execution time was increased by the amount of branch instructions in the machine language, the execution performance deteriorates, there are parts that are not executed, extra machine language remains, load module size There was a problem of increasing. Therefore, it is desired to optimize and delete the portions that are not executed.

An object of the present invention is to improve the execution performance by deleting a branch instruction whose branch destination of the branch instruction is already determined at the time of translation.

[0006]

[Means for Solving the Problems] Means for solving the problems will be described with reference to FIG. In FIG. 1, the comparison / branch deletion processing 2 is to compare whether the operands of the judgment statement of the source program (intermediate language) 4 are constants or variables are the same, or delete the branch instruction.

The source program (intermediate language) 4 is an intermediate language obtained by converting the source program to be optimized.

[0008]

According to the present invention, as shown in FIG. 1, when the comparison / branch deletion processing 2 sequentially takes in the source program (intermediate language) 4 at the time of translation and all the operands of the judgment statement are constants, or the variables of the operands. If all are the same, the decision statement of the source program (intermediate language) 4 and the instruction that is not the branch destination are deleted and optimization is performed.

Therefore, at the time of translation, it becomes possible to improve the execution performance by deleting the judgment statement of the branch instruction in which the branch destination of the branch instruction has already been determined and the instruction that is not the branch destination.

[0010]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, the construction and operation of an embodiment of the present invention will be described in detail with reference to FIGS.

In FIG. 1, a compiler 1 reads a source program, converts it into an intermediate language, optimizes this intermediate language, translates the optimized intermediate language into a machine language, and so on. Therefore, here, the comparison / branch deletion processing 2 of the present invention is included.

The comparison / branch deletion processing 2 is to compare whether the operands of the judgment statement of the source program (intermediate language) 4 are constants or variables are the same, or delete the branch instruction. For example if sentence Of if (a == b) of operands a and b are constants. When this is found to be if (10 == 8) as shown in (a) of FIG. 3, the operand a,
Both b are constants, and it is determined that they are to be deleted.

The memory 3 is a memory for storing a source program (intermediate language) 4 and the like. The source program (intermediate language) 4 is an intermediate language obtained by converting the source program, which is a target for deleting the determination statement of the present embodiment. The flow on the right shows the processing of the source program (intermediate language) on the left as an image diagram. Where in
t a, b, x; / variables a, b, x are integers a = 10; / the value of variable a is 10 b = 8; / the value of variable b is 8 Next, according to the order shown in the flowchart of FIG.
The process of generating the post-optimization state of FIG. 3B from the pre-optimization state of FIG. 3A will be described in detail.

In FIG. 2, S1 determines whether or not there are any remaining commands. This is because the instructions are sequentially fetched from the beginning in the pre-optimization state (pre-optimization state of the present invention of the intermediate language obtained by converting the source program) of FIG. Determine whether. If NO, the process ends. In the case of YES, one next instruction (intermediate language instruction) is read in S2, and the process proceeds to S3.

In step S3, it is determined whether the instruction is a branch instruction. In the case of YES, the branch instruction is the optimization target of the present invention, so the process proceeds to S4. In the case of NO, since the branch instruction is not the optimization target of the present invention, S1 is repeated.

In step S4, it is determined whether all the operands of the branch instruction are constants. This means that if the if sentence is if (a =
= B), it is determined whether or not the operands a and b are both constants. In the case of YES, since the operands of the branch instruction are all constants and the branch destination has been determined, it was found that the branch instruction can be deleted. Therefore, the process proceeds to S6, and whether the operand and the branch condition are true or false. If YES, the branch instruction and the false instruction are deleted in S7 when true, and the branch instruction and the true instruction are deleted in S8 when false.
On the other hand, in the case of NO in S4, since all the operands are not constants, the process proceeds to S5.

In step S5, it is determined whether or not the operand variables of the branch instruction are the same. If YES, go to S6
Whether it is true or false is determined from the operand and the branch condition. When it is true, the branch instruction and the false instruction are deleted in S7, and when it is false, the branch instruction and the true instruction are deleted in S8.

More specifically, it is an if statement in FIG. 3A. Since it has been found that the operands 10 and 8 of if (10 == 8) among them are constants (YES in S4 of FIG. 2),
From the operand and the branch condition, it is determined to be false here (false in S6 of FIG. 2), the branch instruction if (10 == 8) and the true instruction x = 18 are deleted, and the above series of if statements is converted to x. = 2; As a result, the intermediate language in the pre-optimization state of FIG. 3A is optimized to the post-optimization intermediate language of FIG. 3B.

As described above, when the instructions of the intermediate language in the state before optimization are read one by one and the instructions are branch instructions, when the operands of the branch instructions are all constants or they are all the same. If it is a variable, the branch destination is determined, and thus the branch instruction and the instruction other than the branch destination may be deleted. As a result, it is possible to optimize by deleting meaningless branch instructions whose branch destinations are fixed during translation.

FIG. 3 shows a specific example explanatory view. This is c
This is a case of optimizing the if sentence of the language. FIG. 3A shows a state before optimization of the intermediate language obtained by converting the source program. The left side shows an intermediate language if sentence, and the right side shows an image diagram showing the flow of processing at that time.

Here, if (10 == 8) which is an if sentence
Since both operands 10 and 8 are constant and false (YES in S1 of FIG. 2, S2, YES in S3, Y in S4).
Since ES and S5 are false), the branch instruction if (10 == 8) in S8 of FIG. 2 and the true instruction x = 18; and the else etc. attached to the if statement are deleted. Then, as shown in FIG.

FIG. 3B shows an intermediate language after optimization of the intermediate language in the state before optimization shown in FIG.
Here, in (a) of FIG. Of the if statement and the true instruction are deleted and optimized to x = 2 ;.

FIG. 4 shows another embodiment of the present invention. This is the case of optimizing a switch statement in the c language. FIG. 4A shows a state before optimization of the intermediate language obtained by converting the source program. The left side shows an intermediate language switch statement, and the right side shows an image diagram showing the flow of processing at that time.

Here, switchc which is a switch statement
Since the operand c of h (c) is the constant 2, (S in FIG.
YES of 1, S2, YES of S3, YES of S4, S5
2), a branch instruction switch (c) in S7 of FIG. 2 and a false instruction case 1: x = a + b; break case 3: x = a / b; break default: x = a * B: Delete break etc., and make it as shown in (b) of FIG.

FIG. 4B shows an intermediate language after optimization of the intermediate language in the state before optimization shown in FIG.
Here, in (a) of FIG. Delete the switch statement and fake command from Has been optimized for.

[0026]

As described above, according to the present invention,
At the time of translation, since the decision statement of the branch instruction in which the branch destination of the branch instruction has already been determined and the instruction that is not the branch destination are deleted for optimization, the translation performance is improved and The execution speed can be improved by eliminating the execution of the branch instruction when executing the machine language.

[Brief description of drawings]

FIG. 1 is a configuration diagram of an embodiment of the present invention.

FIG. 2 is a flowchart for explaining the operation of the present invention.

FIG. 3 is a diagram illustrating a specific example of the present invention.

FIG. 4 is an explanatory diagram of another specific example of the present invention.

FIG. 5 is an explanatory diagram of a conventional technique.

[Explanation of symbols]

 1: Compiler 2: Comparison / branch deletion processing 3: Memory 4: Source program (intermediate language)

Claims (1)

[Claims] 1. In a branch instruction deletion optimizing method for optimizing a branch instruction by deleting it at the time of translation, the branch instruction is deleted when the operands of the judgment statement of the source program (intermediate language) are constants or variables are the same. The comparison / branch deletion processing (2) is provided, and when the comparison / branch deletion processing (2) has all the operands of the determination statement of the source program (intermediate language) are constants or the variables of the operands are the same at the time of translation, A branch instruction deletion optimizing method characterized in that a judgment statement and an instruction which is not a branch destination are deleted and optimized.