JP2001290652A - Device and method for converting program and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a program converter for reducing generation of transfer instruction. SOLUTION: This program converter is a program converter for converting a source program to an object program, stores the source program containing a described program part from a virtual register in place of a real register into a memory, detects a variable having a survival section over program parts (step c2), calculates the value of gains/losses in the case of assigning the real register to the detected variable for each real register (step c3) and assigns the real register with the minimum value of gains/losses to the virtual register (step c4).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a program language processing system for translating a source program written in a high-level programming language into a target program (object program) such as a machine language program or an assembler program. In order to execute the program part and the specific part of the program at high speed,
The present invention relates to a program conversion device, a program conversion method, and a recording medium for translating a source program including both portions described in an assembler language closer to a machine language.

[0002]

2. Description of the Related Art In recent years, the scale of programs (hereinafter referred to as "embedded programs") mounted on devices together with a processor for embedded devices has increased, and even though the programs are embedded programs, their programs are developed in a high-level language such as C language. It is common that In particular, in embedded programs installed in information devices that perform multimedia processing, such as communication, images, characters, and sound processing, which are rapidly developing in recent years, the program size has increased, and high-level language development has become indispensable. I have.

[0003] By the way, these multimedia processing,
Because high-speed processing of large amounts of data is required, program parts that are frequently executed and strongly required to be executed in a short time are written in an assembler language close to machine language without using a high-level language. Often described. This is because a program part using a high-level language description is converted into an assembler language closer to a machine language by a compiler, but the compiler performs a translation process assuming various types of programs described in the high-level language. Therefore, there is a case where the program is inevitably converted into a redundant assembler language program.

Therefore, as an extended function of a high-level language, there is provided a function of passing values between a high-level language description part and an assembler language description part, and an inline function that can embed an assembler language description part in the high-level language description part. There are many compilers having the "assembler function". Regarding the method of realizing the inline assembler function,
There are various methods, and among them, the method of Literature 3 (described later) which is more convenient is described below. Here, for simplicity of description, a description will be given of an example of division and remainder calculation in C language, which is also handled in the method description of Reference 3.

First, a microprocessor targeted by a compiler is a load / store system of a two-operand type (in operand addressing, an inter-memory operation instruction has only a transfer instruction), and a division instruction div
Has the following specifications. div rm, rn Here, the division instruction div divides the register rm by the register rn, stores the division result in rn, and stores the remainder result in the special register mdr.

As described above, the division instructions of many microprocessors can simultaneously calculate the division and the remainder with one instruction. It is also assumed that the transfer instruction mov described in FIG. 12 or the like indicates that the value of the first operand is transferred to the second operand. Therefore, as shown in FIG. 12A, an assembler routine is macro-defined by using an "asm sentence" using the "asm" keyword (more precisely, an "asm sentence block", which will be described later). Use at multiple locations as in b). The macro dm defined by the macro is expanded as shown in FIG. In the method of Reference 3, a variable whose value is stored during macro dm (macro dm
Are stored in the registers whose values are destroyed by the macro dm (registers r0 and r1 in this case).
Is guaranteed to be unallocated,
Macro dm can be described anywhere.
The degree of freedom in programming is improved.

The description example of the asm sentence in FIG. 12A is slightly different from the example of Reference 3, and is expressed by enclosing a set of a plurality of asm sentences with "@" and "@".
In this way, a set of a plurality of asm sentences will be referred to as an “asm block”. By treating one asm block in the same way as one asm statement,
It can be easily applied to sm blocks.

[0008]

[Problems to be Solved by the Invention] However, Document 3
In the method of (1), there is a problem that the compiler cannot always convert to efficient assembler code depending on where the macro dm is used. This point will be described with a specific example. FIG. 13 shows a result of internally converting the function f2 of FIG. 12C so that it can be further processed inside the compiler. In particular, before calling the function h as shown in (s1) of FIG. 13, the value of the variable m is stored in the temporary variable t generated by the compiler,
The variable t is used as an argument of the function h. This is introduced by the compiler to ensure that the value of the argument of the function is passed by the register, and it is assumed that the register r0 is allocated to the temporary variable t. (Passing an argument by register is a method widely used by compilers in order to perform high-speed function calls.) At this time, since the variable m in FIG. r0 and r1 cannot be assigned to the variable m. As a result, registers other than the registers r0 and r1 are allocated to the variable m, and (s1) in FIG.
, A transfer instruction is generated.

An object of the present invention is to provide a program conversion device (compiler device), a program conversion method, and a recording medium that reduce generation of transfer instructions.

[0010]

To achieve the above object, the present invention provides a program conversion device for converting a source program into an object program, using a virtual register indicating an arbitrary register instead of a real register. A storage unit that stores a source program including the described program part; a detection unit that detects a variable in the source program, the variable having a live range spanning the program part; An allocation unit that allocates a real register different from the real register to be allocated to the variable detected by the detection unit, and a generation unit that generates an object program from a source program according to the allocation result.

The detecting means may include a temporary variable generating unit for generating, for each virtual register, a temporary variable having the program portion as a live range, wherein the temporary variable is a variable in the source program and overlaps with a live range of the temporary variable. And a detection unit for detecting a variable having a live range. The allocating means calculates a value obtained by assigning a real register to the detected variable, and calculates a value obtained by calculating the value obtained by the detecting means. And an allocating unit for allocating a real register having a minimum value to the virtual register.

According to this configuration, since the real register having the minimum gain / loss value is assigned to the virtual register for the detected variable, the real register having the higher gain / loss value can be assigned to the detected variable. The higher the gain / loss value of a real register assigned to a variable, the higher the probability that the variable and another variable in a resource inheritance relationship will inherit the same real register, thereby reducing the occurrence of transfer instructions. .

[0013]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Prior to the description of the embodiments of the present invention, documents related to the present invention will be cited and terms used in the following will be explained. <Literature> 1. AVAho, R. Sethi, JDUllman: ”Compilers, Prin
ciple, Techniques, andTool ”, Addison Wesley Publi
shing Company Inc., 1986, Kenichi Harada: "Compiler I, II", Science, 1990. 2. Tanaka: “Computer readable recording medium on which resource allocation device and resource allocation program are recorded”, application number Japanese Patent Application No. Hei 10-344524. Tanaka: "Compiler device and computer-readable recording medium on which compiler program is recorded and compiling method", application number Japanese Patent Application No. 11-1957.
17 <Explanation of terms> Definition, reference and use of variables Setting the value of a variable is called "defining", and using the set value is called "referencing". Defining or referencing a variable in a program is referred to as "using" a variable. In the following, formal arguments are treated in the same manner as variables unless otherwise specified. -Temporary variables Variables that are generated by the compiler to temporarily store calculation results and variables that are generated to increase the efficiency of processing are called "temporary variables". In the following, unless otherwise specified, they are handled in the same way as variables described in ordinary source programs. -Intermediate instruction The compiler converts the code of the source program into intermediate code to facilitate processing, called "intermediate code", and one step of the intermediate code is called "intermediate instruction".
I will call it. There are quadruples and triads in the intermediate instructions, and these are converted to generate a final target program (object program). A source program converted into a sequence of intermediate instructions will be referred to as an "intermediate program". FIG. 6A shows an example of an intermediate program corresponding to the program of the function f2 in FIG. 5C, which is represented by an address code, which is one of a set of four.
In addition, those indicated by “i” and the accompanying numbers, such as i1 and i2 in FIG. 6A, mean the identifier of the intermediate instruction. Also, the asm block in FIG.
As shown in FIG. 5A, the instruction is converted into an intermediate instruction having the same format as that shown in FIG. 5C. In particular, the intermediate instruction of the asm block in FIG. 6A will be referred to as “asm block intermediate instruction”.

Incidentally, the intermediate instruction in the present invention is not limited to this format, and can be applied to other types of intermediate instructions. Also, in order to simplify the processing in the compiler device, intermediate instructions indicating the beginning and end of the intermediate program,
Intermediate instructions that represent a specific program range, such as intermediate instructions that indicate the beginning and end of a function, are also provided. FIG. 6A shows an intermediate instruction indicating the beginning and end of a function of a function expressed as intermediate instructions i50 and i51.・ Basic block Of the intermediate instruction sequence, jumping from inside the intermediate instruction sequence
If the execution order of the intermediate instruction sequence is a fixed order without jumping into the intermediate instruction sequence, the intermediate instruction sequence is called a basic block. The basic block is described in detail in Document 1. -Live range The live range is the range in which the value held in each variable is valid. To be precise, the range from the intermediate instruction that defines the value of the variable to the intermediate instruction that finally refers to the defined value is defined. A section on the program. The variable is said to be "alive" during the life span. A more detailed description of the survival interval is described in References 1, 2, and 3. FIG. 7B shows an example of the live range. FIG. 7 (b)
In, the live range is represented by a vertical solid line. The start point and end point of the live range are represented by white circles and black circles, respectively. Further, as shown in FIG. 7B, it is not necessary to obtain the live range for each asm statement in the asm block as to the live range for the asm block intermediate instruction, and it is sufficient that the live range represents the entire asm block. . -Resource allocation to variables Resource allocation to variables means allocating registers and memory to variables. Since it is impossible to store two or more values in the same section of a program in one register or memory, it is impossible to assign the same register or memory to a variable whose live range overlaps. And it is essential to allocate memory. For example, two live ranges of a variable m and a variable s2 (s2 will be described later) in FIG. 7 overlap, and it is necessary to allocate different registers and memories to each variable. Hereinafter, the register and the memory are collectively referred to as “resource”. -Resource inheritance relationship When the variable t and the start and end of the live range match, and there is a variable u that can reduce the occurrence of transfer instructions when allocated to the same resource, the variable t and the variable u are in a "resource inheritance relationship". I will say. For example, in FIG.
And the variable t1, the variable t1 and the variable m, and the variable m and the variable t2, respectively, have a resource inheritance relationship. Variable e and variable m
Are in an "indirect resource inheritance relationship".
Since the detailed description of the resource inheritance relationship is described in Reference 2, further description is omitted.・ Loss / Loss A gain / loss value is defined as a case where a resource element (register or memory) already allocated to a variable is allocated to a variable t to be allocated from the viewpoint of suppressing the occurrence of a transfer instruction of a target program. This is a value quantified by focusing on variables that have a resource inheritance relationship or an indirect resource inheritance relationship with the variable t, which contributes to the suppression of the occurrence of transfer instructions.
For example, in FIG. 7B, if the register r0 is assigned to the variable m, the intermediate instruction i11 can be deleted.
In this case, the profit / loss value of the register r0 increases, and it is determined that it is advantageous to assign the register r0 to the variable m from the calculation result of the profit / loss value. Since the detailed description of the gain / loss value is described in Reference 2, further description is omitted. <Description of Embodiment> In the compiler device of this embodiment,
In the description method of the register in the asm block, when “v_” is added before the register name, it means not a specific register but an arbitrary register, and the register with “v_” is referred to as a “virtual register”. ". Then, it is assumed that the effective range is within the asm block.

In the following, description will be made with reference to program examples shown in FIGS. In particular, FIG. 5A shows a case where the used part of the register r0 of FIG. 12A used in the description of the conventional technique is a virtual register v_r0. The register in the asm block is described by a virtual register by a program creator. FIG. 1 is a configuration diagram of a compiler device of the present embodiment. The compiler device 1 shown in FIG. 1 includes a general compiler device including a macro expansion unit 11, a syntax analysis unit 12, an optimization unit 13, a resource allocation unit 14, and a code generation unit 15, and a register argument replacement unit 16 , Asm block definition register detection unit 17,
It comprises a part related to the present invention, which comprises an asm block definition register holding unit 18 and an asm block live range generation unit 19.

Next, the operation and function of each section will be described with reference to examples. First, the compiler 1 activates the macro expansion unit 11. The macro expansion unit 11 replaces the macro identifier defined by the macro with its body. This processing part is the same as the processing of the macro processor of a general C language compiler, so that the detailed description will be omitted and an example of the processing result will be described.

For example, FIG. 5A shows a macro dm defined by a macro, FIG. 5B shows an example of use of the macro dm in a source program, and FIG. Is replaced by its body. Next, the compiler device 1 activates the syntax analysis unit 12. The syntax analysis unit 12 performs lexical analysis, syntax analysis, and semantic analysis of the macro-expanded program output from the macro expansion unit 11, and converts the program into an intermediate program that can be easily processed by a compiler.

For example, the function f2 in FIG.
It is converted to the intermediate program of (a). Since the details of the syntax analysis unit 12 are not the focus of the present invention, the description is omitted. Next, the compiler device 1 activates the optimizing unit 13.
The optimizing unit 13 first activates the register argument replacing unit 16 to be described later and finishes the processing, and then intermediately reduces the program size of the target program generated by the compiler apparatus 1 and the processing execution time. Perform program optimization. Since the details of the optimizing unit 13 are not the main subject of the present invention, a description thereof will be omitted, and only points relevant to the present invention will be described.

The optimizing unit 13 performs basic block analysis, control flow analysis, and data flow analysis in order to perform optimization. The basic block analysis is to divide an intermediate program to be processed into basic blocks. Control flow analysis is to analyze the flow of control between each basic block. Data flow analysis is to analyze where each variable is defined and referenced in each basic block. Further, from these analysis results, the later resource allocation unit 14 calculates a live range.

The register argument replacing unit 16 started by the optimizing unit 13 first inserts an intermediate instruction for temporarily storing the value of the dummy argument passed by the register in a temporary variable at the beginning of the function,
Furthermore, all the used parts of the dummy arguments of the intermediate program are replaced with temporary variables. Further, an intermediate instruction for temporarily storing the value of an actual argument to be transferred in a register in a temporary variable is generated, inserted before the generated function call, and a transfer register is allocated to the temporary variable.

For example, in FIG. 6B, an intermediate instruction i10 for temporarily storing the temporary argument e in the temporary variable t1 is inserted at the beginning of the function, and the place where the temporary argument e is used is replaced with the temporary variable t1. Further, in FIG. 6B, the intermediate instruction i11 temporarily stored in the temporary variable t2 for the actual argument m is inserted before calling the function h, and the function h is called with the temporary variable t2 as the actual argument. I have. Here, it is assumed that the register r0 is allocated to the temporary argument e and the temporary variable t2.

Next, the compiler device 1 activates the resource allocation unit 14. The resource allocating unit 14 first activates the asm block definition register detecting unit 17. The asm block definition register detection unit 17 extracts an intermediate instruction of the asm block from the intermediate program, detects a register defined by an asm statement existing in the extracted asm block, and stores the result in the asm block definition register holding unit 18. Store. FIG. 2 is a processing flowchart of the asm block definition register detection unit 17. In step a1, steps a2 to a3 are repeated for all the intermediate instructions i.
The process of the block definition register detection unit 17 ends.
In step a2, when the intermediate instruction i is an asm block intermediate instruction, step a3 is performed. If not, the process returns to step a1.

In step a3, if the register r is defined by the intermediate instruction i including the virtual register, the intermediate instruction i and the register r are stored in the asm block definition register holding unit 18, and the process returns to step a1. (End of Flowchart) For example, FIG. 8 shows the contents held by the asm block definition register holding unit 18 with respect to the example of the intermediate program shown in FIG. 6B. The register defined by the asm block intermediate instruction is held for each asm block intermediate instruction, and the asm block intermediate instruction i2 shown in FIG.
In, the value of the variable g is transferred to the virtual register v_r0, the value of the variable h is transferred to the real register r1, the virtual register v_r0 is updated by the div instruction, and the real register m
Since dr is also updated, v_r0, r1, and mdr are stored in the register column defined by the asm statement intermediate instruction i2 in FIG. (Step a3).

In the process of step a3, asm
The register defined by the block may simply be a register appearing in the asm block to reduce the processing load. This is because most of the registers described in the asm block are usually defined and then referred to in the asm block except in special cases.

Next, the resource allocation unit 14 uses the control flow information and the data flow information analyzed by the optimization unit 13 to
The live ranges of all variables including the temporary variables generated by the register argument replacing unit 16 are calculated. Since the method of calculating the live range is the same as that of the conventional method, the detailed description is omitted, and here, only the result of calculating the live range for the example of the intermediate program in FIG. 6B is shown. FIG. 7B shows FIG. 6B.
Is the result of calculating the live range for the intermediate program of FIG. The live range is expressed as a set of intermediate instructions as in Document 2 or the like, but here the range is indicated by a solid line for easy understanding intuitively. Further, (r0) described in the live range of the dummy argument e in FIG. 7B means that the register r0 is allocated to the dummy argument e. The same applies to the temporary variable t2. (However, variables s1, s
The live range 2 is generated by the asm block live range generating unit 19 described below. ) Resource allocation unit 1
4 starts the asm block live range generation unit 19,
A special temporary variable assigned to a register defined by an asm statement and its live range are generated. FIG. 3 is a processing flowchart of the asm block live range generation unit 19.

In step b1, the process is repeated from step d2 to step d5 for all the asm block intermediate instructions i, and when the processing is completed, the processing of the asm block live range generation unit 19 ends. In step b2, the asm block definition register holding unit 18 including the virtual register
To the register r defined by the asm block intermediate instruction i
Is present, steps d3 to d5 are performed for all the registers r, and if not, the procedure returns to step d1.

At step b3, a new temporary variable s is generated. In step b4, a live range in which the live range starts and ends with the asm block intermediate instruction i for the generated temporary variable s is generated. In step b5, a register r is assigned to the generated temporary variable s, and the process returns to step d1.

(End of flowchart) For example, FIG.
In (b), s1 and s2 are special temporary variables generated by the asm block live range generation unit 19, a live range exists only in the intermediate instruction i2, and a virtual variable is stored in the temporary variable s1. The real register r1 is allocated to the register v_r0 and the temporary variable s2. In the example of FIG. 7, the value of the register mdr is also updated in the div instruction of the intermediate instruction i2.
Since r itself is not used as a register allocated to a variable, a temporary variable allocated to the register mdr is not generated.

Next, the resource allocating unit 14 generates a temporary variable (temporary variable t1 in the example of FIG. 7) generated by the register argument replacing unit 16 and not generated by the register argument replacing unit 16 and a temporary variable t1 in the example of FIG. Resources are allocated to variables including the temporary variables (temporary variables s1 in the example of FIG. 7) allocated to the virtual registers among the temporary variables thus set.
In particular, the resource allocation unit 14 gives priority to allocation to temporary variables allocated to virtual registers. At the time of this allocation, the register is allocated in consideration of the register to be allocated to the variable whose live range overlaps with the temporary variable allocated to the virtual register. FIG. 4 is a processing flowchart of the resource allocation unit 14.

In step c1, all the variables s allocated to the virtual registers are repeated from step c2 to step c3. When the processing is completed for all variables s, the process proceeds to step c5. In step c2, the variable s
And a set R1 of registers assigned to variables whose live ranges overlap with that of R1.

In step c3, for all the variables t whose variables s and the live range overlap, the gain / loss value is calculated by focusing on the variables that have a resource inheritance relationship or an indirect resource inheritance relationship with the variable t. In step c4, the group does not belong to the set R1 and
The register with the smallest gain / loss value obtained in step c3 is the variable s
Assign to (Because it is more advantageous to assign a register with a large gain / loss value to the variable t, a register with a smaller gain / loss value is assigned to the variable s. The details of the gain / loss value are described in Reference 2. This is the same as the calculation of the profit / loss value for a variable in the “resource exclusion relationship” (the assignment target in Literature 2). Here, the register with the lowest profit / loss value is assigned to the variable s, but is not limited to the register with the lowest profit / loss value. For example, a register whose gain / loss value is not the maximum may be used.

In step c5, steps c6 to c9 are repeated for all the remaining variables v, and when the processing has been completed for all the variables v, the processing of the resource allocation unit 14 ends. In step c6, a set R2 of registers assigned to variables whose live ranges overlap with the variable v is obtained.

Step c7, if there is no register that does not belong to the set R2, a memory is allocated to the variable v and the process returns to step c5. In step c8, a gain / loss value is calculated for the variable v. In step c9, among the registers that do not belong to the set R2, the register having the largest value obtained in step c8 is assigned to the variable v, and the process returns to step c5.

(End of Flowchart) The resource allocation to the variable v in steps c5 to c9 may be performed more strictly as in document 2. In the example of FIG. 7B, in register allocation to the temporary variable s1, first, in step c2, a set R1 having elements of the register r1 allocated to the temporary variable s2 whose live range overlaps the temporary variable s1 is obtained. . Next, at step c3, the profit / loss value is obtained for the variable m whose live range overlaps the temporary variable s1, and in this case, the profit / loss value of the register r0 becomes the maximum. Next, in step c4,
The register r2 that does not belong to the set R1, that is, is not the register r1, and is not the register r0 based on the gain / loss value of the variable m, is selected as a register to be assigned to the temporary variable s1.

In allocating registers to the variable m, first, at step c6, the registers r allocated to the temporary variables s1 and s2 whose live ranges overlap the variable m.
A set R2 having 2, r1 as elements is obtained. Next, in step c8, the profit / loss value of the variable m is obtained, and in this example, the profit / loss value of the register r0 becomes the maximum. Next, in step c9, the register r which does not belong to the set R2 and has
0 is selected as the allocation register for the variable m. The variable t1 is similarly allocated to the register r0.

As a result, the intermediate program of FIG. 7A is converted as shown in FIG. 7C, the virtual register v_r0 in the asm block intermediate instruction is replaced by the real register r2, and the intermediate instructions i10 and i11 Is transferred to the same register, and can be deleted. Next, the compiler device 1 activates the code generation unit 15 and converts the intermediate instruction into a target program such as an assembler instruction or a machine language instruction of a machine targeted by the compiler. The code generation unit 15 itself is the same as the conventional method, and a detailed description is omitted.

As described above, the virtual register v_ described in the asm block intermediate instruction i2 in FIGS.
r0 is replaced by register r2, variable m can be assigned to register r0, and intermediate instruction i11 can be deleted. As described above, the virtual register described in the asm block is replaced with a more appropriate real register depending on the situation where the asm block is described or the macro defined in the asm block is described.
More efficient code generation can be performed.

Hereinafter, another program example different from the program examples of FIGS. 5 to 7 will be described with reference to FIGS. 9 to 11. FIG. 9A shows a macro dm defined by the same macro as FIG. 5A, in which the used part of the register r0 of FIG. 9A used in the description of the conventional technique is a virtual register v_r0. . The register in the asm block is described by a virtual register by a program creator.
FIG. 9B shows an example of the use of the macro dm in the source program, and FIG. 9C shows the result of replacing the macro dm by the macro expansion unit 11 with its body. FIG.
The function f2 in (c) is converted to the intermediate program in FIG. FIG. 10B shows that the intermediate instruction i10 for temporarily storing the temporary argument e in the temporary variable t1 is inserted into the intermediate program of FIG. An intermediate instruction i11 to be stored in the temporary variable t2 and an intermediate instruction i12 to be temporarily stored in the temporary variable t3 for the actual argument n are inserted before the function h is called. The used part of a dummy argument has been replaced with a temporary variable. FIG. 11B shows the result of calculating a live range for the intermediate program of FIG. 10B. Here, (r0) described in the formal parameter e means that the register r0 is allocated to the formal parameter e. Similarly, it means that registers r0 and r1 are allocated to the temporary variables t2 and t3, respectively.

When the flowchart shown in FIG. 4 is executed in the example of FIG. 11 (b), in allocating registers to the temporary variable s1, first, in step c2, the temporary variable s
A set R1 having a register r2 assigned as an element to a temporary variable s2 whose live range overlaps with 1 is obtained. Next, in step c3, the profit and loss values are obtained for the variables m and n whose live ranges overlap with the temporary variable s1, and in this example, the profit and loss value of the register r0 for the variable m and r1 for the variable n becomes the maximum. . Next, in step c4, a register r3 that does not belong to the set R1, that is, is not the register r1, and is not a register r0, r1, or r2 from the gain / loss values of the variables m and n, is selected as a register to be assigned to the temporary variable s1. You.

In allocating registers to the variable m, first, at step c6, the registers r allocated to the temporary variables s1 and s2 whose live range overlaps the variable m.
3. A set R2 having r2 as elements is obtained. Next, in step c8, the profit / loss value of the variable m is obtained, and in this example, the profit / loss value of the register r0 becomes the maximum. Next, in step c9, the register r which does not belong to the set R2 and has
0 is selected as the allocation register for the variable m. The variable n is similarly allocated to the register r1. Variable t
1 and e are similarly allocated to the register r1.

As a result, the intermediate program in FIG.
The conversion is performed as shown in FIG. 11C, the virtual register v_r0 in the asm block intermediate instruction is replaced with the real register r3, and the intermediate instructions i10 and i11 are transferred to the same register, so that they can be deleted. Although the program conversion device (compiler device) according to the present invention has been described based on the embodiments, the present invention is not limited to these embodiments, and may be as follows. (1) In the specific example of the present embodiment, a method has been described in which the compiler replaces only virtual registers in an asm block with more appropriate registers. However, without providing a virtual register description, all compilers in the asm block are provided. The register description can be treated as a virtual register, and the compiler can replace all registers in the asm block with appropriate registers. (2) A restriction may be placed on the register in which the virtual register is replaced. For example, a compiler generally saves a register value in a memory at the beginning of a function, and provides a guarantee register which needs to restore the register value at the end of the function, and a destruction register which does not require it. Therefore, if the replacement register of the virtual register can be any of the destruction registers, efficient code generation may be possible.

In this case, the compiler device 1 stores the set of destruction registers in advance, and in the process of step c4 in FIG. 4, belongs to the set of destruction registers, does not belong to the set R1, and has the minimum value obtained in step c3. May be assigned to the variable s. As described above, the present invention may be configured such that one real register of a set of real registers having a specific function such as a destruction register is allocated to a virtual register. Types of real registers having a specific function include address registers and data registers in addition to destruction registers. (3) When there are a plurality of sets of real registers having a specific function such as an address register and a data register, one real register of one of the plurality of sets is assigned to a virtual register. You may comprise. In this case, the types of the virtual registers are provided so as to correspond to the respective sets having a specific function, such as virtual registers v_Ari and v_Bri, and the programmer performs the description using the plurality of types of virtual registers properly. The compiler device 1 stores a virtual register type and a set having a specific function in association with each other, and belongs to a set having a specific function corresponding to the type of the virtual register in the source program. A real register that does not belong to a set of real registers assigned to a variable whose live range overlaps with the variable s assigned to the virtual register (that is, does not belong to R1) and has the smallest gain / loss value is assigned to the variable s.

More specifically, step c4 in the flowchart of the resource allocating unit 14 in FIG. 4 is referred to as “in step 4, a group belonging to a set having a specific function corresponding to the type of the virtual register allocated to the variable s. , A register that does not belong to the set R1 and has the smallest gain / loss value obtained in step 3 is assigned to the variable s. " (4) In the above embodiments, for simplicity of explanation, the description related to the division instruction has been described. However, the present invention can be applied not only to the division instruction but also to a multi-function such as a product-sum operation instruction. It goes without saying that it can also be applied to instructions. (5) A computer program for causing a general-purpose computer or a device having a program execution function to execute the operation procedure of each component of the compiler apparatus 1, in particular, the procedure shown in the flowcharts of FIGS. It can be recorded on a recording medium or distributed and distributed via various communication paths. Such recording media include an IC card, an optical disk, a flexible disk, a ROM, and the like.

[0044]

According to the present invention, there is provided a program conversion device for converting a source program into an object program, wherein the storage means stores a source program including a program portion described using a virtual register indicating an arbitrary register instead of a real register. A detecting means for detecting a variable in the source program, the variable having a live range spanning the program part; and, for the virtual register, a real register to be assigned to the variable detected by the detecting means. Comprises an allocating means for allocating different real registers, and a generating means for generating an object program from a source program according to the allocation result.

According to this configuration, the program conversion device
A program part included in a source program stores a source program described by a virtual register instead of a real register, and when allocating a register to this virtual register, what is a register to be assigned to a variable in a live range across a program part? Assign different registers.

As a result, there is a high possibility that the same register is allocated to a variable in a live range that crosses a program part and another variable that has a resource inheritance relationship with the variable. If the same register is allocated, the same register is allocated. Since a transfer instruction between a variable in an inheritance relationship and another variable can be deleted, the number of unnecessary transfer instructions can be reduced.

The detecting means includes: a temporary variable generating unit for generating, for each virtual register, a temporary variable having the program portion as a live range; and a variable in the source program,
A detection unit having a live range overlapping the live range of the temporary variable. The allocating means calculates a value obtained by assigning a real register to the detected variable, and calculates a value obtained by calculating the value obtained by the detecting means. And an allocating unit for allocating a real register having a minimum value to the virtual register.

According to this configuration, since the real register having the minimum gain / loss value is assigned to the virtual register for the detected variable, an actual register having a higher gain / loss value can be assigned to the detected variable. The higher the gain / loss value of a real register assigned to a variable, the higher the probability that the variable and another variable in a resource inheritance relationship will inherit the same real register, thereby reducing the occurrence of transfer instructions. .

The allocating means is configured to allocate the real registers preferentially to the virtual registers, and then perform the register allocation to the variables in the program. The allocating means is configured to allocate one real register of a real register group having a specific function among all real registers to a virtual register. According to this configuration, there is an effect that real registers assigned to virtual registers can be limited to real registers having a specific function.

As described above, it is possible to determine the replacement register of the virtual register described in the program portion (in the embodiment, the asm block) in consideration of the variables that live over the program portion. More efficient code generation becomes possible. Also defined using the program part containing the virtual register description,
Functions that are inlined (embedded) in the source program, such as C language macro functions and C ++ language “inline” specification functions, can be written anywhere in the source program, and according to the usage of the written places. Therefore, the virtual register is replaced with a more appropriate real register, so that the generated code efficiency of the compiler is further improved.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a compiler device 1 according to a first embodiment.

FIG. 2 is a processing flowchart of an asm block definition register detection unit 17;

FIG. 3 is a processing flowchart of an asm block live range generation unit 19;

FIG. 4 is a processing flowchart of a resource allocation unit 14;

FIG. 5 is a diagram showing an example of a macro defined by an asm block, an example of a program using the macro, and an example of a program for expanding the macro.

FIG. 6 is a diagram illustrating an example of an intermediate program including an asm block and an intermediate program after processing of a register argument replacing unit 16;

FIG. 7 is a diagram showing an intermediate program including an asm block, a live range of the intermediate program, and an allocated intermediate program.

FIG. 8 is a diagram of contents held by an asm block definition register holding unit 18;

FIG. 9 is a diagram illustrating an example of a macro defined by an asm block, an example of a program using the macro, and an example of a program for expanding the macro.

FIG. 10 is a diagram illustrating an example of an intermediate program including an asm block and an intermediate program after processing of a register argument replacement unit 16;

FIG. 11 is a diagram showing an intermediate program including an asm block, a live range of the intermediate program, and an intermediate program after allocation.

FIG. 12 shows an example of a macro defined by an asm block;
FIG. 3 is a diagram illustrating an example of a macro use program and an example of a macro expansion program.

FIG. 13 is an example of an intermediate program including an asm block.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Compiler 11 Macro expansion part 12 Syntax analysis part 13 Optimization part 14 Resource allocation part 15 Code generation part 16 Register argument substitution part 17 asm block definition register detection part 18 asm block definition register holding part 19 asm block live range generation part

Claims (7)

[Claims] 1. A program conversion device for converting a source program into an object program, comprising: storage means for storing a source program including a program portion described using a virtual register indicating an arbitrary register instead of a real register; Detecting means for detecting a variable in the source program, the variable having a live range spanning the program portion; and a real register to be assigned to the variable detected by the detecting means for the virtual register. A program conversion device comprising: an allocating unit for allocating a real register different from a real register; and a generating unit for generating an object program from a source program according to the allocation result. 2. The method according to claim 1, wherein the detecting unit includes: a temporary variable generation unit configured to generate, for each virtual register, a temporary variable having the program portion as a live range; The program conversion device according to claim 1, further comprising a detection unit that detects a variable having an overlapping live range. 3. The gain and loss value calculating section for calculating, for each real register, a profit and loss value indicating how advantageous the real register is when the real register is allocated to the detected variable; 2. The program conversion device according to claim 1, further comprising: an allocating unit that allocates a real register having a minimum value to the detected variable to the virtual register. 4. The program conversion device according to claim 1, wherein said assigning means assigns registers to variables in the source program after assigning the real registers to the virtual registers with priority. 5. The program conversion device according to claim 1, wherein said allocating means allocates one real register of a real register group having a specific function among all real registers to a virtual register. 6. A program conversion method for converting a source program into an object program, wherein the program is a source program stored in a memory, the program being described using a virtual register indicating an arbitrary register instead of a real register. Detecting, from a source program including a portion, a variable having a live range spanning the program portion; and a real register to be assigned to the variable detected by the detecting step for the virtual register. A program conversion method, comprising: an assignment step of assigning real registers; and a creation step of creating an object program from a source program according to the assignment result. 7. A computer-readable recording medium having recorded thereon a program for causing a computer to execute a process of converting a source program into an object program, wherein the program is a source program stored in a memory of a computer. Detecting, from a source program including a program part described using a virtual register indicating an arbitrary register instead of a real register, a variable having a live range that extends over the program part, And executing a allocating step of allocating a real register different from the real register to be allocated to the variable detected by the detecting step, and a generating step of generating an object program from a source program according to the allocation result. A recording medium recording a program characterized by the following.