JP3327640B2 - Instruction code selection device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an instruction code selecting device used in a compiler for translating a high-level programming language into a machine language for a specific target machine.

[0002]

2. Description of the Related Art A compiler is a device that inputs a source program written in a programming language and creates a target program written in a machine language or an assembly language. FIG. 2 is a block diagram conceptually showing a general configuration of the compiler. The compiler 1 includes a syntax analysis device 2, an optimization device 3, and a code generation device 4. The syntax analyzer 2 reads the source program,
After performing vocabulary analysis and recognizing each word, it is checked for consistency with the grammar and rules of the programming language and converted to an intermediate language. The optimization device 3 edits and optimizes the intermediate language generated by the syntax analysis device 2 in order to improve the memory efficiency and execution efficiency of the target program. The code generation device 4 generates a target program such as a machine language by generating an instruction code of a target machine from the optimized intermediate language. In the code generation device 4, an instruction code selection device 10 is provided to generate an instruction code.

Here, the operation of generating an instruction code by the conventional instruction code selection device 10 will be described. First, prior to the generation of the instruction code, as a result of the syntax analysis in the syntax analysis device 2, a pattern of an expression tree showing the instructions of the source program in a tree structure is obtained. FIG. 3 shows an example of a source program written in C language and a pattern of an expression tree corresponding to an execution instruction of each line of the program obtained by the processing of the syntax analysis device 2.

[0004] The instruction code selecting device 10 receives the pattern of the expression tree, and searches for a template using the pattern as a search key. The template is a pattern of Shiki tree,
The instruction generation rule corresponding to this is described in advance by the compiler creator. FIG. 9 conceptually shows an example of a conventional template. A column (1) shows an expression tree pattern of a procedure call instruction corresponding to an instruction for calling a certain function, and an instruction generation rule 51 corresponding to this. Are stored in the columns of (2) and (3), the expression tree pattern of the operation execution instruction corresponding to the addition instruction and the subtraction instruction of the two floating point type variables, and the instruction generation rule 52 corresponding to these. 5
3, 54 and 55 are stored. Two types of instruction generation rules are described for the expression tree patterns (2) and (3) of the operation execution instructions. This is because the target machine, when performing a floating-point operation, generates an instruction for executing the floating-point operation and a method for generating a procedure call instruction for executing the floating-point operation. This is because the fact that an instruction code can be generated by one of the two methods is considered.

[0005] At the time of compilation, when the operator performs a floating-point operation, by specifying whether to use an operation execution instruction or a procedure call instruction, the instruction generation rule corresponding to the pattern of the expression tree is specified. Only one is selected and an instruction code is generated. For example, FIG.
For the expression tree pattern of the addition instruction shown in (1), if the operator specifies generation of an operation execution instruction, the instruction generation rule 52 in FIG. 9 is selected, and an instruction code is generated.

[0006]

However, as shown in FIG. 9, in the conventional instruction code selection apparatus, a plurality of patterns are set for one expression tree in consideration of the type of the instruction generation method of the target machine. Instruction generation rules must be described in a template in advance. Moreover, some instruction generation rules for generating a procedure call instruction are already described in a template as instruction generation rules corresponding to the pattern of an expression tree representing a function call. For example, FIG.
In the expression tree pattern (2), two types of instruction generation rules, that is, an instruction generation rule 52 of a floating-point type operation execution instruction and an instruction generation rule 53 of a procedure call instruction are described. Among them, the same instruction generation rule 53 is described in the template 50 in the instruction generation rule 51 corresponding to the expression tree pattern (1) indicating a function call. Therefore, when performing the floating-point operation represented by the expression tree pattern (2), the function call pattern (1)
It is possible to execute a desired operation even if the instruction generation rule 51 described in (1) is selected. However, since the instruction generation rule 51 is searched only by the expression tree pattern (1) of the function call, an instruction generation rule 53 is further described for the expression tree pattern (2) in addition to the instruction generation rule 52. Need to be kept.

As described above, the conventional instruction code generation device must describe, for each pattern of the expression tree, an instruction generation rule for executing a plurality of floating-point operations corresponding to the instruction generation method of the target machine. Therefore, the effort of the compiler creator to create a template increases, and the storage area of the template also increases. Furthermore, when a compiler for one target machine is rewritten to a compiler for another target machine, all instruction generation rules must be rewritten, which requires a great deal of man-hours, and also requires maintainability and reusability of the compiler. There was a problem that it reduced.

The present invention has been made in view of the above problems, and has as its object to provide an instruction code selecting apparatus provided with a template which can omit redundant instruction generation rules for the same contents.

[0009]

According to a first aspect of the present invention, there is provided an instruction code selecting apparatus for selecting an instruction code corresponding to a pattern of an input expression tree.
Expression tree pattern selecting means for selecting an expression tree having a specific pattern from the input expression tree, and converting the expression tree pattern selected by the expression tree pattern selection means into a predetermined expression tree pattern and wherein wood pattern converting means for, the pattern of the various formula trees, and store unit that stores instruction generating rules corresponding thereto, before using the formula tree pattern converted by the equation tree pattern converting means Symbol select instruction generating rules from store means
Instruction code selecting means for generating an instruction code by
The storage unit generates an instruction corresponding to the predetermined pattern.
As a rule, an instruction generation rule corresponding to the specific pattern
Where the instruction generation rule that stores
Each of the expression trees having the pattern of
The pattern of the expression tree is a command that calls the procedure that performs the operation.
You may comprise so that it may respond to an order.

An instruction code selecting apparatus according to a third aspect of the present invention.
, Each of the expression trees having the specific pattern
The storage means stores a specific pattern and a corresponding
An instruction generation rule for generating a corresponding operation execution instruction;
Performs a given expression tree pattern and the corresponding operation
One instruction generation rule for generating an instruction that calls a procedure;
Storing the further instruction if the operator <br/> desired generation of execution instruction, and outputs the input expression tree Shikiki pattern selection means, if not desired, the input expression tree Conversion control means for outputting to the code selection means is provided.

[0011]

According to the first aspect of the present invention, a pattern of an expression tree is input to the instruction code selecting device. The expression tree pattern selecting means selects an expression tree having a specific pattern from the input expression trees. In the embodiment of the present invention, for example, a pattern of a floating-point type operation execution instruction is selected. The expression tree pattern converts the expression tree pattern selected by the expression tree pattern selection means into a predetermined expression tree pattern. The storage means is various expression trees
Patterns and the corresponding instruction generation rules, especially
As the instruction generation rule corresponding to a certain pattern,
Instruction generation rules that share the same instruction generation rules for patterns
Stores rules. Then, the instruction code selection means uses the expression tree pattern converted by the expression tree pattern conversion means to store the instruction generation rule corresponding to the expression tree pattern from the instruction code storage means.
Select a rule to generate an instruction code .

Further, in the invention according to claim 2, the conversion control means, when the operator desires to generate a procedure call instruction for executing a floating point type operation, converts the input expression tree to the expression tree pattern selection means. When it is desired to generate an instruction for executing a floating-point type operation, the input expression tree is output to the instruction code selecting means.

[0013]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram illustrating a configuration of an instruction code selection device according to an embodiment of the present invention. This instruction code selection device 10 is included in the code generation device 4 of the compiler 1 shown in FIG.

Referring to FIG. 1, an instruction code selection device 10 according to the present embodiment includes a conversion control unit 11, an expression tree pattern selection unit 12, an expression tree pattern conversion unit 13, an instruction code selection unit 14, And a template 15. Conversion control unit 11
Receives an expression tree pattern of a source program described in a high-level programming language and selection information specified by an operator, and selects one of the expression tree pattern selection unit 12 and the instruction code selection unit 14 according to the type of the selection information. Outputs the received expression tree pattern.

The formula tree pattern selection unit 12 is configured to select a specific pattern,
For example, an expression tree having a pattern of an operation execution instruction is selected. The expression tree pattern conversion unit 13 performs a predetermined operation on the expression tree pattern selected by the expression tree pattern selection unit 12 to convert the expression tree pattern. The instruction code selector 14 includes a conversion controller 11,
An instruction code corresponding to the pattern of the expression tree given from each of the expression tree pattern selection unit 12 and the expression tree pattern conversion unit 13 is selected from the template 15.

The template 15 stores combination data of an expression tree pattern and an instruction generation rule corresponding to the pattern. FIG. 4 shows an example of the contents of the template.
In this embodiment, the template describes one instruction generation rule for one expression tree pattern. Next, the operation of the instruction code selection device of the present embodiment configured as described above will be described below. FIG. 5 is a flowchart illustrating the operation of the instruction code selection device, and FIG. 6 is a flowchart illustrating the operation of the expression tree pattern conversion step shown in FIG. Here, as a target machine using a compiler, a method for generating an instruction for executing a floating-point type operation and a procedure call instruction for executing a floating-point type operation are generated in order to execute a floating-point type operation. Target machines to which the two methods are applied.

First, the operator inputs selection information for selecting one of these two methods when starting up the compiler. Then invoke the compiler,
A pattern of the expression tree is generated through the syntax analysis device 2 and the optimization device 3. The instruction code selection device 10 activates the conversion control unit 11 and receives the pattern of the expression tree and the selection information of the previously executed operation execution instruction. Then, the conversion control unit 11
Determines whether to pass the expression tree to the expression tree pattern selection unit 12 or the instruction code selection unit 14 according to the specification at the time of starting the compiler (steps S100 and S102).

If the content of the selection information is to generate an instruction for executing a floating-point type operation, an expression tree pattern is output to the instruction code selector 14 (step S11).
6) In the case of generating a procedure instruction for executing a floating-point type operation, the instruction code selection device 10
The formula tree pattern selection unit 12 is activated, and outputs the formula tree pattern to the formula tree pattern selection unit 12 (step S104).

The expression tree pattern selection unit 12 includes a conversion control unit 11
The pattern of the expression tree passed is analyzed (step S10).
6). If the expression tree has a pattern representing a floating-point operation, the pattern of the expression tree is converted to the expression tree pattern conversion unit 1.
3 (step S108). Otherwise, the expression tree is passed to the instruction code selector 14 (step S108,
S112).

Subsequently, the instruction code selecting device 10
The expression tree pattern conversion unit 13 is started. Then, the expression tree pattern conversion unit 13 converts the expression tree pattern having the pattern representing the floating-point operation selected by the expression tree pattern selection unit 12 into:
The pattern is converted into a pattern corresponding to a procedure call instruction for executing a floating-point type operation (step S110). This expression tree pattern conversion operation will be described later.

Further, the instruction code selection device 10 activates the instruction code selection section 14. Instruction code selector 14
Searches the template 15 using the expression tree pattern passed from the conversion control unit 11, the expression tree pattern selection unit 12, or the expression tree pattern conversion unit 13, selects an instruction generation rule corresponding to the expression tree pattern. (Step S11)
4).

Here, the conversion operation of the expression tree pattern in step S110 will be described with reference to FIG. When an expression tree pattern is input to the expression tree pattern conversion unit 13 (step S200), a conversion table 20 as shown in FIG. 7, for example, is searched using the operators and data types included in the expression tree pattern as search keys. (Step S210).

If there is no search key in the conversion table 20 (steps S220, S23)
0), it is determined that the expression tree is not a conversion target, and step S2
The process shifts to step 90 to output the pattern of the given expression tree to the instruction code selector 14. If the corresponding operator and type exist in the conversion table 20 (steps S220 and S220).
230), and extracts the corresponding procedure name from the conversion table 20 (step S240).

Then, a procedure call node is created (step S250), a node of the extracted procedure name is created (step S260), and the original expression tree argument is set (step S270). Is generated. After that, the procedure tree pattern of the procedure call generated by the above operation is output to the instruction code selection unit 14 (step S280).

Next, the operation of the instruction code selection device 10 of the present embodiment will be described using a specific example. As a specific example, as described in the section of the prior art, FIG.
An example in which an instruction code is generated using the template 15 shown in FIG. 4 for the source program shown in FIG. Here, FIG. 3 is a diagram showing an example of a source program described in the C language.
The first line of the executable statement is a real (floating point) type variable a,
b and c are defined, line (1) defines some function (func) with b and c as arguments, line (2) indicates an instruction to add b and c, and line (3) Indicates a subtraction instruction for subtracting c from b.

First, the operator inputs a selection specification for converting an expression tree pattern of a floating-point type operation execution instruction into an expression tree pattern of a procedure call instruction for executing a floating-point type operation, and activates the compiler. Then, in the source program shown on the left side of FIG. 3, a pattern of the expression tree shown on the right side of the drawing is generated for each line, and is input to the conversion control unit 11. For example, the expression tree pattern 30 of the generated operation execution instruction is generated for the instruction in the row (2), and is input to the conversion control unit 11.

The conversion control unit 11 determines whether or not to convert the expression tree according to the operator's selection designation. In the case of this example, since the pattern conversion is specified by the operator, the expression tree pattern 30 is
Is output to Then, the expression tree pattern selection unit 12 analyzes that the addition instruction of the real type variable is defined in the expression tree pattern 30, and outputs the expression tree pattern to the expression tree pattern conversion unit 13.

The expression tree pattern conversion unit 13 converts the expression tree pattern 30 of the execution instruction into the expression tree pattern of the procedure call instruction. This conversion processing will be described below. First, the operator "+" and the type "real number (float)" are obtained from the expression tree pattern 30.
Is retrieved as a search key, and the conversion table 20 shown in FIG. 7 is searched. As a result of the search, the first data in the conversion table 20 corresponds to the search key. Therefore, the first procedure name (_fadd) is extracted from the conversion table 20. Then, referring to FIG. 8, first, a procedure call node 40a is created.
Next, the node 40b of the extracted procedure name is connected to the left side of the node 40a of the procedure call. Further, a variable on the left side of the expression tree pattern 30 is extracted and used as the first argument 40c of the procedure call node 40a.
Take out the variable on the right side of 0, and call node 4 of the procedure call
The second argument 40d is 0a. As a result, the expression tree pattern 40 of the procedure call instruction is generated.

The converted expression tree pattern 40 is output to the instruction code selector 14. The instruction code selection unit 14 searches the template 15 shown in FIG. 4 using the converted expression tree pattern 40 as a search key. As a result of the search, the expression tree pattern of (1) matches the search key, and the instruction generation rule 15a is extracted by this search. As described above, the present invention has been described based on the embodiments. However, the present invention is not limited to the above embodiments, and various modifications as described below are possible. (1) In the above embodiment, a target machine in which two types of instruction codes can be selected for a floating-point type operation is assumed. Without providing the control unit 11, it is possible to adopt a configuration that can always convert the pattern of the expression tree. (2) In the above specific example, an example has been described in which the expression tree pattern of the operation execution instruction is converted into the expression tree pattern of the procedure call instruction. Conversely, the expression tree pattern of the procedure call instruction is converted to the expression tree pattern of the operation execution instruction. It is also possible to change to (3) In the above embodiment, the expression tree pattern selection unit 12 selects an expression tree having a pattern representing a floating-point operation, but the target machine does not have a double-integer operation instruction. Can be configured such that the expression tree pattern selection unit 12 selects an expression tree having a pattern representing a long integer operation. (4) Further, in the above embodiment, the expression tree pattern conversion unit 13
However, it is configured to convert to a pattern corresponding to a procedure call instruction that executes a desired operation, but in the case of a pattern representing an operation in which the assignment operation is not completed by one assignment instruction such as assignment of a structure, The formula tree pattern conversion unit may be configured to convert the pattern into a pattern representing a plurality of assignment instructions according to the size of the structure.

[0030]

As described above, the instruction code selection device according to the present invention converts the expression tree pattern by the expression tree pattern conversion means when different expression tree patterns exist for the same instruction generation rule. By converting, the desired instruction generation rule described in the template is selected by using the pattern of the expression tree converted by the instruction code selecting means, so that duplication of the instruction generation rule described in the template is avoided. Thus, the template can be made compact, and the number of man-hours required for rewriting a compiler for one target machine to another target machine can be reduced.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of an instruction code selection device according to an embodiment of the present invention.

FIG. 2 is a conceptual diagram conceptually showing a general configuration of a compiler.

FIG. 3 is an explanatory diagram showing an example of a C language program including floating-point type addition and subtraction and an expression tree pattern corresponding to the instruction.

FIG. 4 is an explanatory diagram showing an example of the contents of a template according to the embodiment of the present invention.

FIG. 5 is a flowchart showing an operation of the instruction code selection device of the embodiment shown in FIG. 1;

FIG. 6 is a flowchart showing a conversion operation of an expression tree pattern conversion unit of the instruction code selection device of the present invention.

FIG. 7 is an explanatory diagram showing an example of a conversion table of an expression tree used in the expression tree pattern conversion unit 13;

FIG. 8 is a schematic diagram showing states before and after conversion of a pattern of an expression tree converted by an expression tree pattern conversion unit 13;

FIG. 9 is an explanatory diagram showing an example of a template of a conventional instruction code selection device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 10 Instruction code selection apparatus 11 Conversion control part 12 Expression tree pattern selection part 13 Expression tree pattern conversion part 14 Instruction code selection part 15 Template

Continuation of front page (56) References JP-A-3-144829 (JP, A) JP-A-3-259343 (JP, A) JP-A-5-53821 (JP, A) JP-A-3-5827 (JP) , A) Proceedings of the IPSJ 26th (Early 1983) National Convention, p. 433-434 (58) Field surveyed (Int. Cl. ⁷ , DB name) G06F 9/45

Claims (3)

(57) [Claims] An instruction code selecting device for selecting an instruction code corresponding to a pattern of an input expression tree, wherein the expression tree pattern selects an expression tree having a specific pattern from the input expression tree. Selection means, expression tree pattern conversion means for converting the expression tree pattern selected by the expression tree pattern selection means into a predetermined expression tree pattern , various expression tree patterns, and instruction generation corresponding thereto a store unit that stores rules, the formula by selecting the instruction generating rule from the previous SL price paid means using the equation tree pattern converted by the tree pattern converting means instruction
Instruction code selecting means for generating a code , wherein the storing means includes an instruction generating means corresponding to the predetermined pattern.
As a rule, an instruction generation rule corresponding to the specific pattern
An instruction code selection device, characterized by storing an instruction generation rule that makes the instruction code common . 2. Each of the expression trees having the specific pattern
Represents operation pattern of said predetermined equation tree, call a procedure to perform the calculation
2. The method according to claim 1, wherein the instruction corresponds to an instruction to be issued.
Instruction code selection device. 3. An expression tree having the specific pattern
Represents an operation, and the storage means generates a specific expression tree pattern and an operation execution instruction corresponding thereto.
Instruction generation rules for generating, a predetermined expression tree pattern, and an operation corresponding thereto
One instruction generation rule for generating an instruction that calls a procedure;
And when the operator desires to generate an operation execution instruction, outputs the input expression tree to the expression tree pattern selecting means,
2. The instruction code selection device according to claim 1, further comprising a conversion control unit that outputs the input expression tree to the instruction code selection unit when generation of an operation execution instruction is not desired.