JP2000339171A - Compile device, its method and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To generate an object program for improving the using efficiency of a memory and for increasing the speed of execution. SOLUTION: The processing results of a word and phrase analyzing means 101, syntax analyzing means 102, and optimizing means 103 are outputted as an intermediate file. In a code generating means 1041, an eternal variable and register information output code generating means 10412 generates a code for ensuring the reference region of the external variables in a memory region on the basis of the intermediate file and a first code to be outputted to a file at the time of executing information concerning the number of times of reference of the external variables and the register-assignment to the variables, and an unused register external variable assigning means 10413 operates register- assignment to the external variables according to the execution result of the first code, and an unused register external variable assignment code generating means 10414 generates a code for non-ensuring the reference region of the external variables in the memory region on the basis of the intermediate file by referring to the result of the register-assignment to the external variables.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] The present invention relates to a compiling device,
The present invention relates to a method and a computer-readable recording medium recording a compiler program.

[0002]

2. Description of the Related Art A conventional compiler includes, for example, a lexical analyzer 101 and a syntax analyzer 10 as shown in FIG.
2, optimization means 103, code output means 10401
And code generation means 1041 having
In such a compiler, an object program (assembler or machine language) is passed through the lexical analysis, syntax analysis, and optimization phases in the code generation unit 1041.
Code is generated.

In such a compiler, when a variable is defined in a source program to be compiled, the generated object program includes a code for securing an area for the defined variable in a memory. Then, the CPU (Central Processing Unit) of the computer that executes the object program,
When a reference is made to the variable, an area in the memory secured by the above code is accessed.

However, since access to the memory must be performed via an external bus, it takes time. Therefore, it is effective from the viewpoint of the execution time of the program to allocate a register inside the CPU to a variable having a high frequency of reference and to access the register when the variable is referenced. Such optimization processing is generally called register allocation optimization.

[0005] Register allocation optimization in a conventional compiler generally involves allocating registers to variables that are frequently referenced in a source program. However, the number of times a variable reference instruction appears in a source program is different from the number of times a variable is referenced when a compiled object program is executed. For example,
When a conditional branch instruction is preceded by a variable reference instruction, the variable may or may not be referenced depending on the conditions at the time of program execution.

In some loop processing, the number of loops can be statically determined, but in other loop processing, it is only known at the time of execution. If there is a loop process whose number can only be determined at the time of execution, it is general to consider the number of loops with appropriate weighting and determine the number of times to refer to variables, but this naturally includes an error It will be. The number of loops varies considerably at the time of execution depending on a program, and this causes a large error in judging the number of times of reference to a variable, and in many cases, optimal register allocation is not performed.

Therefore, in the "object program generation method" described in Japanese Patent Application Laid-Open No. 61-82243, the compiler is provided with two output means to perform optimal register allocation. That is, the first means generates an object program including a code for generating a reference frequency storage area for recording the number of times of reference for each variable at the time of execution, and the second means outputs the object program by the first means. By referring to the information in the reference frequency storage area obtained by executing the object program, an object program that allocates registers to variables with high reference frequency is generated.

[0008]

However, in the above-mentioned Japanese Patent Application Laid-Open No. 61-82243, only the assignment of registers is performed in accordance with the reference frequency, but no description is given regarding the attributes of variables to be assigned to the registers. Further, there is no description about what registers are allocated to what variables. For this reason, for example, if the number of references to the external variable increases and a large number of registers are allocated to the external variable, it becomes impossible to secure the registers necessary for ensuring the consistency of the function.

[0009] However, the above publication does not disclose any method for coping with such a case. Therefore, when such a situation occurs, it is necessary to save / restore the registers after all, so that the code efficiency is deteriorated and the program execution speed is reduced. Was. In addition, it is necessary to prepare a save area for the register in the memory, and there is a problem that the use efficiency of the memory is deteriorated.

[0010] Other techniques related to register allocation optimization are disclosed in, for example, Japanese Patent Application Laid-Open Nos. 4-326432 and 6-214802.
However, even the techniques described in these publications cannot solve the problems pointed out in the technique described in JP-A-61-82243.

The present invention provides a compiling apparatus and method capable of generating an object program with high memory utilization efficiency and high execution speed, and a computer-readable recording medium on which such a compiler program is recorded. The purpose is to:

[0012]

In order to achieve the above object, a compiling apparatus according to a first aspect of the present invention provides a compiling apparatus which parses a plurality of source programs including external variables referred to each other into a plurality of intermediate files. A compiling device for generating an object program based on the
A first object program generating unit for generating a plurality of first object programs for securing an area for referring to the external variable in a memory based on the plurality of intermediate files; Register allocating means for allocating a register which is not used elsewhere in the order of external variables having a large number of references as a result of executing a program in an executable form in which a plurality of first object programs are combined, and allocating registers by the register allocating means A second object program generating means for generating, based on the plurality of intermediate files, a plurality of second object programs for referring to an external variable to which a register is assigned by using the assigned register; It is characterized by having.

In the above-mentioned compiling apparatus, since the external variable having a high frequency of reference can be referred to using the allocated register, the execution speed when the program combining the generated second object program is executed is increased. be able to. Further, in some cases, it is not necessary to allocate a memory for an external variable referred to by using a register, so that the use efficiency of the memory can be increased.

In the above-mentioned compiling device, the register which is not used except for assigning to the external variable by the register assigning means may be obtained as a result of executing the program in the executable form.

In this case, the first object program generating means includes a register included in an apparatus for executing an executable program obtained by combining the plurality of first and second object programs, and a register corresponding to each register. Means for generating a code for generating a register use management means for managing information on the use state when executing an executable program obtained by combining the plurality of first object programs; and 1
Means for executing a program in an executable form in which the object program is combined and generating a code for setting a use state in the register use management means corresponding to the used register when the register is used. Wherein the register allocating means allocates a register to an external variable by referring to the register use managing means obtained after executing an executable program obtained by combining the plurality of first object programs. It can be.

In the above-mentioned compiling apparatus, the register which is not used except for assigning to the external variable by the register allocating means may be a register other than the register used in the plurality of first object programs. Good.

In this case, the first object program generation means associates the plurality of first and second object programs with each register included in a device that executes an executable program that combines the plurality of first and second object programs. Means for generating register use management means for managing information on the use state, and using the use state in the register use management means corresponding to the used register when generating a code for using any of the registers Means for setting a state.

In the above-mentioned compiling apparatus, the first object program generating means may include a reference frequency storage means for storing the number of times of reference in association with each external variable, and an execution form program combining the plurality of first object programs. Means for generating a code for generating when the external variable is referred to, and when the external variable is referred to by executing an executable program in which the plurality of first object programs are combined, Means for generating a code for adding the number of references in the corresponding reference frequency storage means.

Further, the reference frequency storage means may further store an initial value in association with each of the external variables. In this case, the first object program generating means may store the initial value. It may include means for generating a code for setting an initial value of a variable in the reference frequency storage means.

Further, the reference frequency storage means may store information on registers assigned to each of the external variables. In this case, the register assignment means may store the plurality of first variables. Assigning registers according to the reference frequency of each external variable in the reference frequency storage means after executing the execution form program in which the object program is combined, and storing the information in the information field regarding the register of the corresponding external variable, The second
The object program generating means may generate the plurality of second object programs with reference to the reference frequency storage means.

In the above-mentioned compiling apparatus, the second object program generating means is for excluding a register allocated to the external variable by the register allocating means from registers to be saved and restored in interrupt processing. It may include means for generating code.

In the compiling apparatus, the plurality of intermediate files may be stored before the first object program generating means generates the plurality of first object programs and when the second object program generating means generates the plurality of first object programs. Before the plurality of second object programs are generated, they may be generated separately.

In order to achieve the above object, a compiling method according to a second aspect of the present invention is a method for compiling an object program based on a plurality of intermediate files obtained by parsing a plurality of source programs including external variables referred to each other. A compiling method for generating, wherein a first object program generating step of generating a plurality of first object programs for securing an area for referencing the external variable in a memory based on the plurality of intermediate files; A register allocating step of allocating registers that are not used elsewhere in order from an external variable having a large number of references, as a result of executing an executable form program in which the plurality of first object programs generated in the object program generating step are combined; In the register allocation step A second object program for generating a plurality of second object programs that refers to register allocation and references external variables to which registers are allocated using the allocated registers based on the plurality of intermediate files And a generating step.

In the above-mentioned compiling method, the register which is not used except for assigning to an external variable in the register assigning step may be obtained as a result of executing the program in the executable form.

In the above-mentioned compiling method, the register which is not used except for assigning to an external variable in the register allocating step may be a register other than the register used in the plurality of first object programs. Good.

In order to achieve the above object, a computer-readable recording medium according to a third aspect of the present invention comprises:
A computer-readable recording medium on which a compiler program for generating an object program is recorded based on a plurality of intermediate files obtained by parsing a plurality of source programs including external variables which are referred to each other, wherein A first object program generating step for generating a plurality of first object programs for securing an area for referring to the external variable in a memory based on a file; and a plurality of first object programs generated in the object program generating step. As a result of execution of the execution form program in which the object programs are combined with each other, a register allocating step of allocating a register that is not used by another in order from an external variable having a large number of references, and a register allocating in the register allocating step are referred to. And executing a second object program generating step of generating, based on the plurality of intermediate files, a plurality of second object programs for referring to an external variable to which a register is assigned by using the assigned register. The program is characterized by recording a program for causing the program to execute.

In the program recorded on the recording medium, the register which is not used except for assigning it to an external variable in the register allocating step may be obtained as a result of executing the program in the executable form. Good.

In the program recorded on the recording medium, the registers which are not used except for assigning to the external variables in the register allocating step are also registers other than the registers used in the plurality of first object programs. Register.

[0029]

Embodiments of the present invention will be described below with reference to the accompanying drawings.

[First Embodiment] FIG. 1 is a functional block diagram showing a compiler according to the first embodiment.
In this drawing, the functions are shown as functions realized by a processor that executes a compiler program stored in a memory. That is, the computer system on which the compiler program is executed operates as a compiling device.

As shown in FIG. 1, a compiler 10 according to this embodiment includes a lexical analysis unit 101, a syntax analysis unit 102, an optimization unit 103, and a code generation unit 1.
041. The code generation unit 1041 includes a code generation control unit 10411, an external variable and register information output code generation unit 10412, an unused register external variable allocation unit 10413, an unused register external variable allocation code generation unit 10414, and a code output unit. 10401.

The lexical analysis means 101 decomposes a source program described in a high-level language to be compiled into tokens. The parsing means 102 parses the decomposed lexical data according to the specification of the program language, and generates, for example, a parse tree as a result of the parsing.
The optimization unit 103 improves the execution efficiency of the compiled object program by reviewing redundant instructions and the like. The processing results of these units 101 to 103 are passed to the code generation unit 1041 as an intermediate file.

The code generation control means 10411 controls a translation process (process for generating assembler code from the above-mentioned intermediate file, which is performed in two processes). That is, the code generation unit 10411
Calls the external variable and register information output code generation means 10412 in the first translation processing, and uses the unused register external variable allocation means 1012 in the second translation processing.
413 and unused register external variable assignment code generation means 10414 are sequentially called.

An external variable and register information output code generating means 10412 generates a code for securing an area for an external variable in a memory from the intermediate file which is the output result of the optimizing means 103, as in the conventional case. ,
Generate code to output information about the number of references to external variables and registers to be assigned to variables.

Unused register external variable allocation means 10
Reference numeral 413 performs a process of allocating unused registers to the external variables based on information when the code generated by the external variable and the register information output code generation unit 10412 is executed in an executable form.

The unused register external variable allocation code generation means 10414 refers to the register allocation to the external variables by the unused register external variable allocation means 10413, and uses the intermediate file which is the output result of the optimizing means 103 to allocate the register. Generates a code that does not secure the area for the external variable for which the

The code output means 10401 is an assembler program code generated by the external variable and register information output code generation means 10412 or an unused register external variable allocation code generation means 10414.
Outputs the code of the assembler program generated by.

The operation of the system including the compiler 10 according to this embodiment until a load module in an executable format is generated from a source program described in a high-level language will be described below. FIG. 2 is a diagram showing the entire system including the compiler 10 for performing such an operation.

First, a plurality of source programs (A, B, C) 201 described in a high-level language are input to the compiler 10. The compiler 10 performs a first translation process on each of the input source programs 201.
In the first translation processing, first, the lexical analysis means 10
1. The parsing means 102 and the optimizing means 103 perform the same processing as before, and the result is stored in the intermediate file (A,
B, C) 202.

Next, in the compiler 10, the code generation means 1041 performs normal code generation using the intermediate file 202 as an input, and allocates the external variable and the register information output code generation means 10412 to the external variable reference count and variables. The first assembler program (A, B, C) 203 is generated by generating a code for outputting information about the register.

Next, the assembler 20 assembles the first assembler program 203, and the linker 30 further links the first assembler program 203.
5 is generated. Then, the program execution unit 40 executes the executable program 205 to generate the register use management area 301 and the reference frequency storage area 302.

Next, in the compiler 10, the code generation means 1041 performs the second translation processing by using the intermediate file 202 generated in the first translation processing, the register use management area 301 and the reference frequency storage area 302 as inputs. Do. In the second translation process, the unused register external variable allocating unit 10413 allocates the same register to the variable having a high number of references in all programs, and the used register external variable allocation code generating unit 10414.
Generates a second assembler program (A, B, C) 204 by generating a code that does not reserve an area for an external variable to which a register is assigned in a memory area.

Then, the assembler 20 assembles the second assembler program 204, respectively, and the linker 30 further links the assembler program 204 to generate an executable program 206 as a final output.

Hereinafter, code generation control means 10411, external variable and register information output code generation means 1041
2. Unused register external variable allocation means 10413 and unused register external variable allocation code generation means 10
Details of the operation of 414 will be described with reference to the flowcharts shown in FIGS.

FIG. 3 is a flowchart showing the processing of the code generation control means 10411. First, the code generation control unit 10411 determines whether or not it is the first translation process (step S101). If it is the first translation process, the code generation control unit 10411 calls the external variable and register information output code generation unit 10412 to execute the process described later (step S10).
2). When control is returned from the external variable and register information output code generation means 10412, the code generation control means 10
Step 411 ends the process of this flowchart.

On the other hand, if it is not the first translation processing, that is, if it is the second translation processing, the code generation control means 10411 calls the unused register external variable allocation means 10413 and executes the processing described later (step S103). When the control is returned from the external variable and register information output code generation unit 10412, the code generation control unit 10411 calls the unused register external variable allocation code generation unit 10414, and executes the process described later (step S104). When the control is returned from the unused register external variable assignment code generation unit 10414, the code generation unit 10411 ends the processing of this flowchart.

FIG. 4 is a flowchart showing the processing of the external variable and register information output code generation means 10412. The external variable and register information output code generation means 10412 firstly outputs the reference frequency storage area 30
It is determined whether a code for securing the area 2 and the register use management area 301 has not been generated yet (step S201). As a result of the determination, if such a code has been generated, the process proceeds to step S203; otherwise, the process proceeds to step S202.

In step S 202, the external variable and register information output code generation means 10412 stores the reference frequency storage area 3
01 and the register use management area 302 are secured in the memory, the names of all registers except special registers are registered in the register name field of the register use management area 302, and the use flag field of the register use management area 302 is used. To generate a code for performing a process for initializing to “0”. When the generation of this code is completed, step S2
Proceed to 03.

In step S203, the external variable and register information output code generating means 10412 determines whether or not all the intermediate files 202 as the processing results of the optimizing means 103 have been completed. The intermediate file 202 in this determination means all files to be compiled, and in the example of FIG. 2, all three of the intermediate files A, B, and C.

If it is determined that the intermediate file 202 has not been completed, the external variable and register information output code generating means 10412 reads one line from the intermediate file 202 which is the processing result of the optimizing means 103 (step S204). ). Further, the external variable and register information output code generation unit 10412 determines whether the read line is an external variable definition statement (step S2).
05).

When it is determined that the statement is an external variable definition statement,
External variable and register information output code generation means 104
12 registers the name of the external variable in the variable column of the reference frequency storage area 302 at the time of execution by the program execution unit 40, initializes the corresponding reference frequency column to “0”,
A code for setting an initial value of the external variable in a corresponding initial value column is generated (step S206). Then, the process returns to step S203.

On the other hand, if it is determined in step S205 that the statement is not an external variable definition statement, the external variable and register information output code generation means 10412 further determines whether the read line is an external variable reference statement (step S205). S207). If it is determined that the sentence is not an external variable reference statement, the process proceeds to step S209.

On the other hand, if it is determined in step S 207 that the sentence is an external variable reference sentence, the external variable and register information output code generating means 10412 sets the reference frequency column of the reference frequency storage area 302 for the external variable. “1”
Is generated (step S20).
8). Then, the process proceeds to step S209.

In step S209, the external variable and register information output code generation means 10412 determines whether or not the read out line generates a code that uses a register (including a case other than the reference to a variable). I do. If it is determined that the code using the register is not generated, the process returns to step S203, and
If it is determined that a code using a register is to be generated, the process proceeds to step S210.

In step S 210, the external variable and register information output code generation means 10412 generates a code for setting the use flag column corresponding to the register to be used in the register use management area 302 to “1”. Then, the process returns to step S203.

Steps S204 to S2 as described above
If the process of step 10 is repeated and it is finally determined in step S203 that the intermediate file 202 has ended, the process of this flowchart ends.

FIG. 5 is a flowchart showing the processing of the unused register external variable allocation means 10413. When the process starts, the unused register external variable allocating unit 10413 determines that there is an unused register in the register managed in the register use management area 301 based on the execution result of the executable program 205 obtained according to the first translation process. And it is determined whether or not it is assigned to an external variable (step S301).

If it is determined that there is an unused register and it is not assigned to an external variable, the unused register external variable allocating unit 10413 allocates the register in the reference frequency storage area 302 in order from the variable having the largest number of references. Registered in the column of the allocation register. At this time, the use flag of the register use management area 301 for the assigned register is set (step S3).
02). Then, the process of this flowchart ends.

On the other hand, when it is determined that there is no unused register and / or that the unused register is not assigned to an external variable, the processing of this flowchart is terminated.

FIG. 6 is a flowchart showing the processing of the unused register external variable assignment code generation means 10414. The unused register external variable allocation code generation unit 10414 determines whether or not all the intermediate files 202 as the processing results of the optimization unit 103 have been completed (step S401).

On the other hand, if it is determined that the intermediate file 202 has not been completed, the unused register external variable assignment code generation means 10414 reads one line from the intermediate file 202 which is the processing result of the optimization means 103 ( Step S402). Next, the unused register external variable assignment code generation unit 10414 determines whether or not the read out line generates the head code of the main function (step S403).

If it is determined that the code at the head of the main function is to be generated, the unused register external variable allocation code generation means 10414 refers to the reference frequency storage area 302 to determine the register to which the external variable has been allocated. Then, a code for loading an initial value is generated (step S404). Then, the process returns to step S401.

On the other hand, if it is determined in step S403 that the first code of the main function is not to be generated, the unused register external variable allocation code generation means 1
The step 0414 further determines whether or not the line read in the step S402 is for generating the head code of the interrupt function (step S405).

If it is determined that the code at the head of the interrupt function is to be generated, the unused register external variable allocation code generation means 10414 transfers the register allocated to the external variable from the save register group for interrupt processing. A code to be removed is generated (step S406).
Then, the process returns to step S401.

On the other hand, if it is determined in step S405 that the first code of the interrupt function is not to be generated, the unused register external variable allocation code generation means 1
In step S414, it is further determined whether or not the line read in step S402 is to generate a code at the end of the interrupt function (step S407).

If it is determined that the code at the end of the interrupt function is to be generated, the unused register external variable allocation code generation means 10414 saves the register allocated to the external variable when returning from interrupt processing. A code to be removed from the group is generated (step S408). Then, the process returns to step S401.

On the other hand, if it is determined in step S407 that the code at the end of the interrupt function is not to be generated, the unused register external variable allocation code generation means 1
In step S414, it is determined whether the row read in step S402 refers to an external variable to which a register is assigned (step S409). If it is determined that reference is not made to the external variable to which the register is assigned, the process returns to step S401.

On the other hand, if it is determined that the reference is made to the external variable to which the register is allocated, the unused register external variable allocation code generation means 10414 generates
With reference to the reference frequency storage area 302, a code for referring to an external variable using the register is generated (step S410). Then, the process returns to step S401.

Then, the processing of steps S402 to S410 is repeated, and when it is determined in step S401 that the intermediate file 202 is finally completed, the processing of this flowchart is completed.

Hereinafter, the operation of the compiler 10 according to this embodiment until the second assembler program 202 is generated from the source program 201 described in a high-level language will be described with reference to a specific example. here,
As the source program 201, a program described in C language shown in FIGS. 7 and 8 is taken as an example. Here, FIG.
FIG. 10 shows a first assembler program 201 (same as the prior art) obtained in the first translation process, and FIGS.
Indicates a second assembler program 202 obtained in the second translation process. FIGS. 11 and 12 show a register use management area 301 and a reference frequency storage area 302 when the first assembler program 203 obtained in the first translation process is assembled and linked and executed.
3 shows the state transition.

Source program a. Shown in FIG. When c is input to the compiler 10, the lexical analysis means 101, the syntax analysis means 102, and the optimization means 103 perform the same processing as in the prior art, and output the result as an intermediate file 201. Next, control is transferred to the code generation control unit 10411, the process of step S102 is performed based on the result of the determination process of S101 in FIG. 3, and control is transferred to the external variable and register information output code generation unit 10412.

In the processing of the external variable and register information output code generation means 10412, the processing of step S202 is performed according to the result of the determination processing of step S201 in FIG. 4, and the register use management area 301, the reference frequency storage area A code to secure and initialize 302 is generated.

In the first line of the source program in FIG. 7, a code for registering an initial value of a variable in the reference frequency storage area 302 is generated by the processing of steps S203, S204, S205, and S206. In lines 3, 5, 6, 7, 8, 10, and 11 of the source program in FIG. 7, steps S203, S204, S205, S207,
The process of S209 is performed.

In the source program shown in FIG.
In the fourth line, steps S203, S204, S
205, S207, S208, S209, and S210 are performed, and a code for adding the number of times of reference in the reference frequency storage area 302 and a code for setting the use flag of the register use management area 301 to "1" are generated. Is done.
In lines 15 and 16 of the source program in FIG. 7, steps S203, S204, S205, S207,
The process of S209 is performed. And finally, step S
In the processing of 203, the end of the intermediate file 202 is recognized and the processing is ended, and the code output means 10401 outputs the first assembler program 203 shown in FIG.

Next, the source program b. When c is input to the compiler 10, the lexical analysis means 1
01, the parsing means 102 and the optimizing means 103 perform the same processing as in the prior art, and
Output as 2. Next, code generation control means 1041
1 and the process of step S102 is performed based on the result of the determination process of S101 in FIG. 3, and the control is shifted to the external variable and register information output code generation unit 10412.

The external variable and register information output code generation means 10412 determines that the code for securing the register use management area 301 and the reference frequency storage area 302 has already been generated in the determination processing of step S201 in FIG. Then, the process directly proceeds to the processing after step S203.

The source programs 1, 3, 6, and 7 in FIG.
In the row, steps S203, S204, S2
05, S207, and S209 are performed. In lines 8 and 9 of the source program in FIG.
203, S204, S205, S207, S208, S
209 and S210 are performed, and the reference frequency storage area 3
A code for adding the reference number 02 and a code for setting the use flag of the register use management area 301 to “1” are generated.

The source program 10, 12, 1
In lines 3, 14, and 15, steps S203,
Steps S204, S205, S207, and S209 are performed. Finally, the process of step S203 recognizes the end of the intermediate file 202, ends the process, and outputs the first assembler program 203 shown in FIG. 10 from the code output unit 10401.

The first data shown in FIG.
Assembler program a. s and the first assembler program b. By executing the executable program 205 obtained by assembling and linking s with the s, the register use management area 301 and the reference frequency storage area 302 in FIG. 3 are generated. Next, the state transition of each generation area when the executable program 205 is executed will be described. Note that no interruption occurs during execution, and the interruption function wari is not executed.

The program starts with a main function. At line 22 of the object program in FIG. 9, an external variable and register information output code generation means 10412
The register use management area 301 and the reference frequency storage area 302 are secured and initialized from the code generated by the above. Here, the state transition of the register use management area 301 is as shown in FIG. 11A, and the state transition of the reference frequency storage area 302 is as shown in FIG.

Next, 2 of the object program shown in FIG.
The processing moves to the function func1 by the function call on the fourth line. f
In unc1, the processing from the 36th line to the 39th line in FIG. 9 is performed, using the registers # 2 and # 8 and setting the variable a to 2
Time, the variable b is referred to once. For this reason, the code generated by the external variable and the register information output code generation unit 10412 is used by the register use management area 301
11 (b) shows the state transition of the reference frequency storage area 302.
FIG. 12B shows the state transition of FIG.

Next, 4 of the object program shown in FIG.
In the processing from the first line to the 44th line, the registers $ 9 and $ 10
Are used to refer to the variable c once, the variable d once, and the variable e once. For this reason, the state transition of the register use management area 301 is controlled by the external variable and the code generated by the register information output code generation unit 10412 in FIG.
1 (c), the state transition of the reference frequency storage area 302 is shown in FIG.
(C).

Next, 4 of the object program in FIG.
In the processing from the sixth line to the 49th line, the registers # 11 and # 1
2, variable f once, variable g once, and variable h 1
Times referenced. Therefore, according to the external variable and the code generated by the register information output code generation unit 10412, the state transition of the register use management area 301 is shown in FIG. 11D, and the state transition of the reference frequency storage area 302 is shown in FIG.
2 (d).

Next, 5 of the object program in FIG.
The processing shifts to the function func2 by the function call on the first line. f
In the processing of unc2, the registers # 2 and # 2 are executed in the processing of the eleventh to fourteenth lines of the object program in FIG.
8, the variable a is referred to twice and the variable f is referred to once. For this reason, the state transition of the register use management area 301 does not change from FIG. 11D and the state transition of the reference frequency storage area 302 changes according to the code generated by the external variable and the register information output code generation unit 10412 in FIG.
2 (e).

Next, in the processing from the 16th line to the 21st line of the object program in FIG. 10, the registers e9, e10, and e11 are used, the variable e is set twice, the variable b is set once, and the variable g is set.
Is referenced once. For this reason, the state transition of the register use management area 301 is not changed from that of FIG. 11D by the external variable and the code generated by the register information output code generation unit 10412, and the state transition of the reference frequency storage area 302 is the state transition of FIG. ).

Next, the process returns to the calling side of the function func2 in the processing of the 23rd line of the object program in FIG.
Then, the function func1 returns to the calling side in the processing of the 55th line of the object program in FIG. Further, FIG.
Function ma in the processing of line 28 of the object program
Return to the startup routine that is the caller of in,
The process ends.

In the second translation process, a register obtained by executing an executable program obtained by assembling and linking the object programs of FIGS. 9 and 10 obtained in the first translation process. The use management area 301 and the reference frequency storage area 302 are input to the compiler. After that, first, the source program a. Obtained in the first translation process shown in FIG. The process is performed on the intermediate file 202 for c.

The code generation control means 10411 determines in step S1 based on the result of the determination processing in step S101 in FIG.
03, and unused register external variable allocating means 1
The control is transferred to 0413. The unused register external variable assignment unit 10413 executes the process of step S302 based on the result of the determination process of step S301 in FIG.

The register use management area 301 at this point
Is in the state of FIG. 11D, the unused register external variable allocating means 10413 stores the registers # 13 and # 1
4 and $ 15 are recognized as unused registers. Further, since the reference frequency storage area 302 at this point is in the state shown in FIG.
Reference numeral 13 assigns registers # 13, # 14, and # 15 to variables a, e, and b with a large number of references, respectively, and sets the reference frequency storage area 302 to the state shown in FIG. The variable b has the same number of references as the variables f and g. In this case, the same effect can be obtained by allocating a register to any variable. Therefore, in this example, the variable b is allocated to the variable b as an example.

Next, the process returns to the code generation control means 10411, and performs the processing of step S104 in FIG.
Control is transferred to 4.

In the unused register external variable assignment code generation means 10414, step S402 is executed based on the result of the determination processing in step S401 in FIG. Next, the processing of steps S403 and S404 is performed on the twentieth line of the object program in FIG. 9, and the codes on lines 18, 19 and 20 of the object program in FIG. 13 are generated. Thereafter, for a row that does not conform to the determination processing, the unused register external variable assignment code generation means 1041
4 corresponds to steps S403, S405, S407, S40
9, the processing of S401 and S402 is repeated.

Next, 3 of the object program shown in FIG.
The processes of steps S409 and S410 are performed on the sixth to 49th lines, and the codes on the 33rd to 42th lines of the object program in FIG. 13 are generated. The unused register external variable assignment code generation means 10414 recognizes the end of the intermediate file in the process of step S401 and ends the processing, and outputs the assembler code shown in FIG. 13 from the code output means 10401.

Next, the source program b. Shown in FIG. intermediate file 20 for c
2 is processed. First, the code generation control means 10
Step 411 performs step S103 according to the result of the determination processing in step S101 in FIG. 3, and transfers control to the unused register external variable allocating unit 10413. Here, since the unused registers have already been allocated to the external variables, this unit is terminated, the processing returns to the code generation control unit 10411, and the processing of step S104 in FIG. Code generation means 1041
The control moves to 4.

The unused register external variable assignment code generation means 10414 executes the process of step S402 according to the result of the determination process of step S401 in FIG. Next, the processes of steps S403 and S404 are performed on the twentieth line of the assembler program in FIG. 9, and the codes on lines 18, 19, and 20 of the assembler program in FIG. 13 are generated. Thereafter, steps S403, S405, S407, and S40 are performed for rows that do not conform to the determination processing.
9, the processing of S401 and S402 is repeated.

Next, one of the assembler programs shown in FIG.
The processing of steps S409 and S410 is performed on the first to 21st lines, and the codes on the 8th to 13th lines in FIG. 14 are generated. Next, 29 of the assembler program of FIG.
The processing of steps S405 and S406 is performed from the 38th line to the 38th line, and the registers # 13, # 14, and # 15 are excluded from the save register group, and the processes of the assembler program 2 shown in FIG.
The code from the first line to the 27th line is generated.

Next, 4 of the assembler program in FIG.
The processing of steps S407 and S408 is performed on the fourth to 53rd lines, and the registers # 13, # 14, and # 15 are excluded from the return register group, and the codes on the 33rd to 39th lines in FIG. 14 are generated. You. Next, steps S407 and S4 are executed on lines 44 to 53 of the assembler program in FIG.
The process 08 is performed, and the codes on the 28th line to the 32nd line in FIG. 14 are generated. Next, steps S405 and S4 are executed on lines 29 to 38 of the assembler program in FIG.
06, the registers # 13, # 14, and # 15
Are removed from the save register group, and 2 from line 21 in FIG.
The code on the seventh line is generated.

Then, the unused register external variable assignment code generating means 10414 finally returns to step S401.
Then, the end of the intermediate file 201 is recognized, and the process ends. The code output unit 10401 outputs the assembler program shown in FIG.

As described above, the second assembler program (FIGS. 13 and 14: this embodiment) for the first assembler program 203 (FIGS. 9 and 10: prior art) generated from the source programs of FIGS. FIG. 15 shows the reduction rates of the data area and the code area. From this figure,
According to the present embodiment, it can be seen that the memory area can be significantly reduced. It can be empirically predicted that the same reduction effect can be quantitatively obtained even for a large-scale source program different from this example.

As described above, in the compiler 10 according to the present embodiment, the external variable and register information output code generation means 10412 assembles the first assembler program 203 generated in the first translation processing.
By executing the linked executable program 205, a register that can be assigned to an external variable is checked and registered in the register use management area 301.

Then, the unused register external variable allocating means 10413 converts the register whose use flag is “0” in the register use management area 301 in a state where the executable program 205 is actually executed into an external variable with a high frequency of reference. Have assigned. In this manner, the unused register external variable allocation code generation means 10414 can generate a code by allocating registers to external variables having a high reference frequency, so that the second assembler program 204 is assembled and linked to the executable program 206.
Is code efficient and runs faster.

In the compiler 10 according to this embodiment, in the first translation processing by the external variable and register information output code generating means 10412, registers are allocated to variables other than external variables, and the register is allocated to external variables. Is performed in the second translation process. Therefore, a plurality of source programs 201
Since the same register can be assigned to the reference of an external variable between different ones, the executable program 206 in which the second assembler program 204 is assembled and linked has high code efficiency, Its execution speed is fast.

In the compiler 10 according to the present embodiment, when an external variable to be assigned to a register has an initial value, the unused register external variable assignment code generating means 10414 generates a code for setting the initial value to the register. Has been generated. Therefore, the external variables can be allocated to the same register from the beginning to the end, and the area for referencing the external variables, which must be secured in the memory area, can be reduced accordingly.

Further, in the compiler 10 according to the present embodiment, the unused register external variable assignment code generation means 10414 removes registers assigned to external variables from registers saved / restored by an interrupt function. Thus, the executable program 206 obtained by assembling and linking the second assembler program 204
Since the number of registers that must be saved / restored during interrupt processing can be reduced compared to the past,
The code efficiency is high and the execution speed is fast. Further, the area of a memory for saving / restoring registers can be reduced.

[Second Embodiment] The compiler 10 according to this embodiment is almost the same as that according to the first embodiment. However, in this embodiment, FIG.
As shown in (1), the register use management area 301 obtains information on registers not used in the first translation processing to generate the register use management area 301. That is, in this embodiment, the external variable and register information output code generation means 10412
Is different from that of the first embodiment.

FIG. 17 is a flowchart showing the processing of the external variable and register information output code generating means 1042 in this embodiment. In this embodiment,
External variable and register information output code generation means 104
12 first determines whether or not the register use management area 301 is secured in the memory (step S5).
01). If it is determined that the register use management area 301 is secured in the memory, the process proceeds to step S503.

On the other hand, when it is determined that the register use management area 301 is not secured in the memory, the external variable and register information output code generation means 10412 secures the register use management area 301 in the memory, The names of all registers other than special registers are registered in the register name column of the use management area 302 (step S502). Then, the process proceeds to step S503.

The processing from step S503 to step S509 is the same as the processing from step S203 to S209 in FIG.

If it is determined in step S509 that a code using a register is to be generated, an external variable and register information output code generating means 1041
2 sets “1” in the column of the use flag corresponding to the register to be used in the register use management area 302 (step S510). Then, the process returns to step S503.

As described above, in the compiler 10 according to this embodiment, the external variable and register information output code generation means 10412 secures the register use management area 301 and registers the names of all registers except special registers. In addition, when generating a code that uses a register, the use flag column corresponding to the register to be used is set to “1”. Thus, the compiler 10 according to this embodiment can obtain the following effects in addition to the effects of the first embodiment.

That is, depending on the source program 201, the operation may be different each time the program is executed due to input of information from outside or interruption. In such a case, a register that has not been used in one execution result may be used in another execution result. However, in this embodiment, the use flags corresponding to the registers that may be used at the time of execution are all set to “1” during the first translation, so that the registers assigned to the external variables are Used at runtime to prevent unauthorized operation.

[Modifications of Embodiment] The present invention is not limited to the above-described first and second embodiments, and various modifications and applications are possible. Hereinafter, modifications of the above-described embodiment applicable to the present invention will be described.

In the first and second embodiments, the unused register external variable assignment code generating means 10414 is used.
When the second translation processing is performed, the intermediate file 2 generated from the source program 201 input first is used.
02 was used. That is, the first translation processing and 2
The same intermediate file 202 was used in the second translation process. However, before the second translation process is performed, the source program 201 may be newly input to the compiler 10 and the intermediate file may be generated in the same manner as before the first translation process.

In the first and second embodiments, an assembler program is generated as an object program compiled from the source program 201 by the compiler 10, and the generated assembler program is converted into a machine language using the assembler 20. Was converted to code. However, a machine language code may be directly generated as an object program obtained by compiling an assembler program from a source program.

In the first and second embodiments, the compiler 10 includes the lexical analyzer 101 and the syntax analyzer 10.
2, the optimization means 103 and the code generation means 1041. However, even when the assembler code is generated based on an intermediate file obtained by merely lexical analysis and syntax analysis of the source program without the optimization unit 103, each unit included in the code generation unit 1041 may operate correctly. it can.

In the first and second embodiments, the compiler 10 has been described as a function realized by a processor that executes a compiler program stored in a memory. However, such a compiler program
The program may be stored and distributed on a computer-readable recording medium such as a magnetic disk or an optical disk. Further, the information may be distributed from a server on a network via the network.

In the first and second embodiments, the compiler 10 includes the lexical analyzer 101 and the syntax analyzer 10.
2. The optimization unit 103 and the code generation unit 1041 are configured as a single unit. However, since the lexical analysis means 101, the syntax analysis means 102, and the optimization means 103 are the same as the conventional ones, they may be provided as a module including only the code generation means 1041.

[0117]

As described above, according to the present invention,
It is possible to generate an object program with high code efficiency, that is, a high execution speed. Further, since it is not necessary to secure an area for referring to an external variable in the memory, it is possible to generate an object program with high memory use efficiency.

[Brief description of the drawings]

FIG. 1 is a functional block diagram illustrating a compiler according to a first embodiment of the present invention.

FIG. 2 is a diagram illustrating an entire system that performs processing up to generation of an executable program from a source program in the first embodiment of the present invention.

FIG. 3 is a flowchart illustrating a process of a code generation control unit in FIG. 1;

FIG. 4 is a flowchart showing a process of an external variable and register information output code generation unit of FIG. 1;

FIG. 5 is a flowchart showing a process of an unused register external variable assignment unit.

FIG. 6 is a flowchart showing the processing of an unused register external variable assignment code generation means.

FIG. 7 is a diagram showing an example of a source program described in C language.

FIG. 8 is a diagram showing an example of a source program described in C language.

FIG. 9 is a diagram showing assembler code generated in a first translation process from the source program of FIG. 7;

FIG. 10 is a diagram showing assembler code generated in a first translation process from the source program of FIG. 8;

FIG. 11 is a diagram showing a state transition of a register use management area.

FIG. 12 is a diagram showing a state transition of a reference frequency storage area.

FIG. 13 is a diagram showing assembler code generated in a second translation process from the source program of FIG. 7;

FIG. 14 is a diagram showing assembler code generated in a second translation process from the source program of FIG. 8;

FIG. 15 is a diagram illustrating the effect of the compiler according to the first embodiment of the present invention.

FIG. 16 is a diagram illustrating an entire system that performs processing up to generation of an executable program from a source program in the first embodiment of the present invention.

FIG. 17 is a flowchart illustrating processing of an external variable and register information output code generation unit according to the second embodiment of the present invention.

FIG. 18 is a functional block diagram showing a compiler according to a conventional example.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 10 Compiler 101 Lexical analysis means 102 Syntax analysis means 103 Optimization means 1041 Code generation means 10401 Code output means 10411 Code generation control means 10412 External variable and register information output code generation means 10413 Unused register external variable allocation means 10414 Unused register outside Variable assignment code generation means 20 Assembler 30 Linker 40 Program execution unit 201 Source program 202 Intermediate file 203 First assembler program 204 Second assembler program 205 Executable program 206 Executable program 301 Register use management area 302 Reference frequency storage area

Claims (16)

[Claims] 1. A compiling device for generating an object program based on a plurality of intermediate files obtained by parsing a plurality of source programs including external variables referred to each other, wherein the compiling device generates the object program based on the plurality of intermediate files. A first object program generating means for generating a plurality of first object programs for securing an area for referring to an external variable in a memory; and a plurality of first object programs generated by the object program generating means. As a result of executing the program in the execution format, in order from the external variable having the largest number of references, register allocating means for allocating a register that is not otherwise used, and referring to the register allocation by the register allocating means, Based on the registers allocated Compiling device, characterized in that it comprises a second object program generating means for generating a plurality of second object program with reference to an external variable performed by using the register assigned the. 2. The register according to claim 1, wherein the register that is not used except for assigning to an external variable by the register allocating means is obtained as a result of executing the program in the executable format. Compilation device. 3. The method according to claim 1, wherein the first object program generating means includes a register included in a device for executing an executable program obtained by combining the plurality of first and second object programs, and a register associated with each register. Means for generating code for generating register use management means for managing information on the use status when executing an executable program in which the plurality of first object programs are combined; and Means for generating, when a register is used by executing a program in an executable form combined with an object program, a code for setting a use state in the register use management means corresponding to the used register to a use state. The register allocating unit executes the plurality of first object programs in combination Referring to the register use management means obtained after executing the program of the form,
3. The compiling device according to claim 2, wherein registers are allocated to external variables. 4. The register that is not used in any other way than that the register allocating means allocates to an external variable is a register other than a register used in the plurality of first object programs. 2. The compiling device according to 1. 5. A method according to claim 1, wherein said first object program generating means associates each of said plurality of first and second object programs with a register included in an apparatus for executing an executable program which is combined with said plurality of first and second object programs. Means for generating register use management means for managing information about
5. The apparatus according to claim 4, further comprising: a unit that sets a use state in the register use management unit corresponding to the used register when a code that uses any of the registers is generated. 6. Compilation device. 6. The first object program generating means executes a program in an executable form in which the plurality of first object programs are combined with a reference frequency storing means for storing a reference count in association with each external variable. Means for generating code for generating, when the plurality of first
Means for executing a program in an executable form in which the object programs are combined to generate a code for adding a reference count in the reference frequency storage means corresponding to the external variable referred to when the external variable is referred to. The compiling device according to claim 1, wherein the compiling device includes a compiling device. 7. The reference frequency storage means further stores an initial value in association with each of the external variables, and the first object program generating means stores the initial value of the external variable in the reference frequency. 7. The compiling apparatus according to claim 6, further comprising means for generating a code to be set in the means. 8. The reference frequency storage means further stores information on registers allocated corresponding to each of the external variables, and the register allocation means executes an executable form combining the plurality of first object programs. Register allocation is performed according to the reference count of each external variable in the reference frequency storage unit after executing the program, and stored in a column of information on the register of the corresponding external variable, the second object program generation unit 8. The compiling apparatus according to claim 6, wherein the generating unit generates the plurality of second object programs by referring to the reference frequency storage unit. 9. The second object program generating means generates code for excluding a register assigned to an external variable by the register allocating means from a register to be saved and restored in interrupt processing. 9. The compiling device according to claim 1, further comprising: 10. The plurality of intermediate files are generated before the first object program generating means generates the plurality of first object programs and when the second object program generating means generates the plurality of second object programs. 10. The compiling device according to claim 1, wherein the compiling device is separately generated before and before the object program is generated. 11. A compiling method for generating an object program based on a plurality of intermediate files obtained by parsing a plurality of source programs including external variables referred to each other, wherein the compiling method includes the steps of: A first object program generating step of generating a plurality of first object programs for securing an area for referring to an external variable in a memory; and a plurality of first object programs generated in the object program generating step are combined. As a result of executing the program in the execution form, in order from the external variable having the largest number of references, a register allocating step of allocating a register that is not otherwise used, and referring to the register allocation in the register allocating step, the plurality of intermediate files are referred to. On the basis of, Compiling method which comprises a second object program generating step of generating a plurality of second object program performed using register is assigned the references assigned external variable register. 12. The method according to claim 11, wherein the registers that are not otherwise used to be allocated to the external variables in the register allocation step are obtained as a result of executing the program in the executable form. Compilation method. 13. The register used in the register allocation step, which is not used except for assigning to an external variable, is a register other than a register used in the plurality of first object programs. 12. The compiling method according to item 11. 14. A computer-readable recording medium on which a compiler program for generating an object program is recorded based on a plurality of intermediate files obtained by parsing a plurality of source programs including external variables referred to each other. A first object program generating step of generating a plurality of first object programs for securing an area for referring to the external variable in a memory based on the plurality of intermediate files; Executing a program in an executable form in which the plurality of first object programs are combined, and as a result, a register allocating step of allocating a register that is not used elsewhere in order from an external variable having a large number of references; A second object program generating a plurality of second object programs that reference external variables to which registers have been allocated using the allocated registers based on the plurality of intermediate files. A computer-readable recording medium for recording a program for executing the steps. 15. The register according to claim 14, wherein the register which is not otherwise used to be allocated to an external variable in the register allocating step is obtained as a result of executing the program in the executable form. Computer readable recording medium. 16. The register that is not used except for assigning to an external variable in the register allocating step is a register other than a register used in the plurality of first object programs. 15. The computer-readable recording medium according to 14.