JP2000194569A - COMPILING DEVICE, COMPILING METHOD, COMPUTER-READABLE RECORDING MEDIUM STORED COMPILE PROGRAM, AND COMPUTER-READABLE RECORDING MEDIUM STORED OBJECT PROGRAM - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To reduce the capacity of a target program having loop processing and to reduce the time required for the processing. A loop processing extracting unit (124) for extracting a loop processing unit in an intermediate text obtained by converting a source program or a source language into a low-level language, and a recording area of a variable for controlling the number of loops in a conditional branch instruction are analyzed. A recording area analyzing means 125 for selecting an address recording area for recording a head address value to be described later; calculating a head address value for each state processing; A head address setting means 126 for writing in the address recording area, and a conditional branch instruction
Jump instruction conversion means 1 for jumping to the start address of the state processing to be executed next by referring to the start address value in the address recording area, and converting the processing for performing the state processing of the jump destination into a jump instruction to be executed by the processing device.
27.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a compiling device for converting a source program described in a source language into a target program which can be easily executed by a processing device, a compiling method, a computer-readable recording medium storing a compiling program, and a computer-readable recording medium. The present invention relates to a computer-readable recording medium storing a target program created by a compiling method, and more particularly to a technique for reducing the time required for loop processing and reducing the capacity of the target program.

[0002]

2. Description of the Related Art Generally, when developing a target program for causing a processing device such as a computer to execute a predetermined process, a developer first creates a source program using a source language, and then prepares the source program. By introducing the program into the compiling device, the source language is converted into the target language (compile processing), and the target program for executing the desired processing is generated. This is because, in the state of the source program written in the source language, it takes time for the processing device to interpret the instructions in the source program, and the time required for executing the predetermined processing becomes longer. On the other hand, in the target program generated by the compiling process, since each instruction to the processing device is described in a language suitable for understanding the processing device, the processing device cannot understand the given instruction. As a result, the time required to execute the predetermined processing can be significantly reduced. The "primitive language" mentioned here
Means a high-level programming language, such as C language, which facilitates programming work for developers, and a "target language" means a so-called machine language suitable for a processing device to execute actual processing. , "Purpose Program"
By performing a link procedure on one or more target programs (objects), the program is converted into an executable program executable by the processing device.

Next, the compile processing method will be briefly described.

[0004] A typical compiling process is performed in two stages: 1) parsing, 2) transcoding. That is, as a first step, an intermediate text is generated by converting the contents of a source program described in a source language into a lower-level language (syntax interpretation step). As a second step, the intermediate text in the intermediate text generated in the first step is generated. The character string is replaced with an instruction code suitable for the processing device, and a control code for linking an address with another target program is added as necessary (code conversion step). Here, the "low-level language" is a language depending on the processing device, belongs to a so-called intermediate position between the source language and the target language, and is generally called an assembly language.

[0005]

As described above, when creating a program for causing a processing device to execute a predetermined process, it is necessary to compile a source program described in a source language. Thus, the processing speed of the device is improved by generating a target program and causing the processing device to execute the target program. However, recently, it has become clear that some technical problems occur when compiling a source program having loop processing in the state of the conventional compiling device. Hereinafter, in order to explain this technical problem in an easy-to-understand manner, generation of a target program that causes the processing device to execute the processing illustrated in FIG. 12 will be considered. Having at least one or more common processing units as shown in FIG.
When writing a program that executes multiple processes sequentially,
A certain variable is circulated (hereinafter abbreviated as a cyclic variable), and processing X
For example, when the cyclic variable is 0, the process A is selected, the process is B when the variable is 1, the process C is selected when the cyclic variable is 2, and the process D is selected when the cyclic variable is 3. In this manner, a process realized by circulating a variable and selecting and executing a portion other than a common part of a plurality of state processes is called a loop process.

When generating a target program for causing the processing device to execute the processing shown in FIG. 12, a source program is first generated using a source language. There are several types of the source program for causing the processing device to execute this. Usually, a loop process as shown in FIGS. 13A and 13B is performed. That is, the common process X is collected in one place in the source program, and it is circulated in a range of values from 0 to 3 to control the number of loops and a if variable to if-else statement (a) or a switch to case statement (b). Are arranged between the state processings A, B, C and D. With this configuration, after executing the common process X, the value of the cyclic variable that controls the number of loops in each conditional branching unit is determined, and each of the state processes A, B, C, and D is sequentially executed. .

Next, the source program shown in FIGS. 13A and 13B is subjected to a syntax interpretation process, which is the first stage of the compile process, to generate an intermediate text shown in FIG. 14A. Note that there are several methods for the syntax interpretation processing according to the specifications of the processing device. Here, a MIPS R3000 processor is used as the processing device, and the corresponding method (“mips RISC architecture”) is used.
Here is the result of parsing using Kyoritsu Shuppan Co., Ltd.). As you can see, after the parsing process,
If-el constructing a loop processing unit in a source program
The “se” statement and the “switch to case” statement are both lower-level languages “l
i ", conditional branch instructions 57-59 indicated by" bne "
In addition, the cyclic variable i is converted into cyclic variables # 2 and # 3, respectively. However, the basic form of the intermediate text is the same as that of the source program. Processing X is also integrated in one place as common processing, a conditional branch instruction is provided after each state processing, and a cyclic variable for controlling the number of loops is provided. $ 3
Variable ＄ 2 used for comparison with the value of cyclic variable ＄ 3
Are sequentially shifted to each of the state processes A, B, C, and D while comparing the values of.

As described above, in the conventional compile processing, the form of loop processing specified in the source program is directly reflected in the intermediate text and the finally obtained target program.

Next, the operation of the processing apparatus when the processing apparatus executes the program having the loop processing section will be described.

When the processing device executes the program having the loop processing section, the processing device firstly controls the number of loops (defines a state process to be performed next) by changing the value of the cyclic variable # 3. After setting to 0,
2) Next, in the conditional branch instruction 57, after setting the value of the cyclic variable # 2 used for the comparison process to 0, the common variable X
2, and the values of $ 3 are compared (at this time, the values of the cyclic variables $ 2 and $ 3 are 0 and 0, respectively). 3) Since the respective values are equal, the state processing A ($ 3 =
0) is executed. 4) After incrementing the value of the cyclic variable # 3 by 1, the process returns to the top of the program and executes the common process X again. 5) In the conditional branch instruction 57, the value of the 0
, Then the values of the cyclic variables ＄ 2 and 比較 3 are compared (at this time, the values of the cyclic variables ＄ 2 and ＄ 3 are 0 and 1, respectively). 6) Since the values are not equal, The state process A is jumped to the conditional branch instruction 58 (broken line B). 7) In the conditional branch instruction 58, the value of the cyclic variable $ 2 is set to 1
, And the values of the cyclic variables # 2 and # 3 are compared (at this time, the values of the cyclic variables # 2 and # 3 are respectively 1 and 1). 8) Since the respective values are equal, the state Processing B ($ 3 =
9) After incrementing the value of the cyclic variable $ 3 by 1, return to the top of the program and execute the common processing X again. 10) In the conditional branch instruction 57, change the value of the After setting to 0, the values of the cyclic variables # 2 and # 3 are compared (at this time, the values of the cyclic variables # 2 and # 3 are 0 and 2, respectively). 11) Since the values are not equal, Jump to the state processing A, and go to the conditional branch instruction 58. 12) In the conditional branch instruction 58, after setting the value of the cyclic variable # 2 to 1, compare the values of the cyclic variables # 2 and # 3 (this At that time, the values of the cyclic variables # 2 and # 3 are 1 and 2, respectively). 13) Since the respective values are not equal, the state processing B is jumped to the conditional branch instruction 59 (dashed line C). ) In the conditional branch instruction 59, the value of the cyclic variable $ 2 was set to 2. , And the values of the cyclic variables # 2 and # 3 are compared (at this time, the values of the cyclic variables # 2 and # 3 are respectively 2 and 2). 15) Since the respective values are equal, the state processing C (# 3 =
16) After incrementing the value of the cyclic variable $ 3 by one, return to the top of the program and execute the common process X again. 17) In the conditional branch instruction 57, After setting the value to 0, the values of the cyclic variables # 2 and # 3 are compared (at this time, the values of the cyclic variables # 2 and # 3 are 0 and 3, respectively). 18) Each value is equal. Since there is not, jump the state processing A and go to the conditional branch instruction 58. 19) In the conditional branch instruction 58, set the value of the cyclic variable # 2 to 1 and then compare the values of the cyclic variables # 2 and $ 3 (At this time, the values of the cyclic variables # 2 and # 3 are 1, 3
20) Since the respective values are not equal, the state processing B is jumped to the conditional branch instruction 59 (broken line C). 21) In the conditional branch instruction 59, the value of the cyclic variable # 2 is set to 2 After that, the values of the cyclic variables # 2 and # 3 are compared (at this time, the values of the cyclic variables # 2 and # 3 are respectively 2 and 3). 22) Since the respective values are not equal, the state processing is performed. It jumps C (dotted line D), goes to the beginning of process D, and operates to execute process D.

In other words, in this program configuration, a plurality of conditional branch instructions are jumped from the common process X to each of the state processes A, B, C, and D, and the number of loops is executed in each conditional branch instruction. Is sequentially compared with the value of the cyclic variable # 3 for controlling the value of the comparison variable # 2, and a state process satisfying the condition is executed.

Here, when the cumulative number of jumps required for processing the entire program having such a conditional branch instruction is expressed by a mathematical expression using the number n of state processes, the jump required before shifting to the n-th state process n is obtained. The number (Jn) is obtained by a simple calculation as Jn = (n + 2) · (n−1) / 2 (times). That is, the cumulative number of jumps (Jn) when the processing device executes the program having the loop processing is proportional to the square of the number of state processing n. Therefore, the greater the number n of state processes in the program, the more
The number of jumps required to execute the program increases dramatically, the time required for the processor to execute a predetermined function increases, and the program size increases in proportion to the number of conditional branch instructions in the entire program. is there.

As described above, the conditional branch instruction used in the conventional loop processing searches and executes the next state processing by comparing two cyclic variable values a plurality of times, so that the entire loop processing time is reduced. growing. Also, if a source program with loop processing is converted to a target program by the conventional compilation process, the conditional branch instruction in the source program is inherited as it is in the target program. Nevertheless, with the increase in the number of loop processing units, it becomes difficult to speed up the processing of the generated target program, and the capacity of the program in which the conditional branch instruction is inherited as it is is large, so that a large load is imposed on the processing device. It will be.

The present invention has been made in view of such technical problems, and has as its object to provide a compiling device for converting a source program having loop processing into a target program optimal for execution by a processing device. It is in.

It is another object of the present invention to provide a compiling method for converting a source program having loop processing into a target program optimal for execution by a processing device.

Still another object of the present invention is to provide a recording medium storing a compile program for converting a source program having loop processing into a target program optimal for execution by a processing device.

Still another object of the present invention is to provide a recording medium storing a target program having a loop process converted into a state optimal for execution by a processing device.

[0018]

Means for Solving the Problems To solve the above problem, the inventor extracts a loop processing section in a source program or an intermediate text in a compiling process for converting a source program into a target program, By converting the extracted conditional branch instruction in the loop processing unit directly from the common processing to the start address of the next state processing, and converting it to jump means for causing the processing unit to execute the processing of performing the instruction at the jump destination, We have come to the idea that it is possible to shorten the time required for processing and further reduce the capacity of the entire target program.

Based on the above idea, a first feature of the present invention is that a compiling program for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which can be easily processed by the processing device. An optimizing means for extracting a loop processing unit comprising at least one common process and a plurality of state processes and a conditional branch instruction provided between these processes, and optimizing the loop process; Is a loop processing extraction means for extracting a loop processing unit in an intermediate text obtained by converting a source program or a source language into a lower-level language, and a recording area of a variable for controlling the number of loops in a conditional branch instruction is analyzed. A recording area analyzing means for selecting an address recording area for recording a value; After the end, the head address setting means for writing the head address value of the state processing to be executed next in the address recording area, and the state processing for executing the conditional branch instruction next by referring to the head address value in the address recording area Is a compiling device having a jump instruction conversion means for converting a process for performing a state process of a jump destination to a jump instruction for causing a processing device to execute the process for performing a state process of a jump destination.

Thus, since the jump from the common processing to each state processing is always performed once irrespective of the number of state processing, the time required for processing the target program having the loop processing can be shortened. The capacity of the program can be reduced.

A second feature of the present invention resides in a compiling method for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which can be easily processed by the processing device. There is provided an optimization step of extracting a loop processing unit including one common process and a plurality of state processes and a conditional branch instruction provided between these processes, and optimizing the loop process. Alternatively, a loop processing extracting step of extracting a loop processing unit in an intermediate text obtained by converting a source language into a lower-level language, and analyzing a recording area of a variable for controlling the number of loops in a conditional branch instruction, and recording a start address value to be described later An address recording area analysis step of selecting a recording area and a start address value are calculated for each of the state processing, and one state is calculated. After the completion of the processing, the start address setting step of writing the start address value of the next state processing to be executed in the address recording area, and the conditional branch instruction are executed next by referring to the start address value in the address recording area. The present invention is a compile method including a jump instruction conversion step of jumping to a start address of a state process and converting a process of performing a state process of a jump destination into a jump instruction to be executed by a processing device.

With this, the jump from the common process to each state process can be performed only once irrespective of the number of state processes, so that the time required for processing the target program having the loop process can be reduced, and The capacity of the program can be reduced.

A third feature of the present invention resides in storing a compile program for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which can be easily processed by the processing device. Extracting, on a computer-readable recording medium, a loop processing unit including at least one common process and a plurality of state processes and a conditional branch instruction provided between these processes;
The optimization processing includes optimization processing for optimizing loop processing. The optimization processing includes a loop processing extraction processing for extracting a loop processing unit in an intermediate text obtained by converting a source program or a source language into a lower-level language, and an optimization processing in a conditional branch instruction. Analyzing the recording area of the variable for controlling the number of loops, and calculating the head address value for each of the state processing and the recording area analysis processing for selecting the address recording area for recording the head address value to be described later. The start address setting processing for writing the start address value of the next state processing to be executed in the address recording area, and the start of the state processing for executing the conditional branch instruction by referring to the start address value in the address storage area Jump instruction conversion processing that jumps to an address and converts the processing that performs the state processing of the jump destination into a jump instruction that causes the processing unit to execute Hints, is that these processes a computer-readable recording medium storing a compiled program for causing a computer to execute.

Thus, the jump from the common processing to each state processing can be performed only once irrespective of the number of state processing. Therefore, the time required for processing the target program having the loop processing can be shortened. The capacity of the program can be reduced.

Further, a fourth feature of the present invention resides in a computer-readable recording medium storing a target program, characterized by including the target program created by the compiling method.

Thus, it is possible to provide a target program having optimized loop processing.

Here, the "recording medium" means a computer-readable medium on which a program can be recorded, such as a semiconductor memory, a magnetic disk, an optical disk, a magneto-optical disk, a magnetic tape, and a digital video disk. .

The "address recording area" means a readable and writable recording medium such as a register memory and a stack memory.

Further, in the loop process extraction, it is preferable to find a portion where a plurality of portions described as "bne $ a, $ b, Label1,... J Label2" exist in the intermediate text.

Further, a recording area analyzing step is executed for a recording area of a cyclic variable for controlling the number of loops.

[0031]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to FIGS.

First, the configuration of the compiling device according to the embodiment of the present invention will be described with reference to FIG.

A compiling apparatus 100 according to an embodiment of the present invention includes a source program input unit 110 for inputting a source program described in a source language, a compile processing unit 120 for converting a source program into a target program, and a generated target program. A linking processing unit 130 for linking with another target program, and an execution program output unit 131 that outputs an execution program generated by the linking process.
Has a syntax interpreter 121, an intermediate text generator 122, an optimization processor 123, a code converter 128, and a target program output unit 129.
A loop processing extraction unit 124 for extracting a program part that specifies a loop processing composed of at least one common processing and a plurality of state processings and a conditional branch instruction provided between these processings; A recording area analyzing unit 125 analyzes a recording area for recording a variable for controlling the number of times, selects an address recording area for recording a later-described first address value, calculates a first address value of each state process, and performs one state process. After completion, the start address setting unit 126 that writes the start address value of the next state process to the address recording area, jumps the conditional branch instruction to the start address value of each state process with reference to the address record area, and executes the jump destination instruction And a jump instruction conversion unit 127 for converting the processing for executing the processing into a jump instruction to be executed by the processing device. Further, the compiling device 100 includes an input device 20 for inputting a program language and an instruction to each processing unit.
0, an output device 300 for outputting information such as the generated target program and error display. Further, the compiling device 100 is connected to a recording device 400 storing another target program so that the jump instruction conversion unit 126 and the linking processing unit 130 can refer to information such as the address value of another target program. . Here, the “recording area” refers to a readable and writable recording medium such as a register memory and a stack memory.

Next, a compiling method according to the embodiment of the present invention will be described with reference to FIGS.

When a target program is created by the compiling method according to the embodiment of the present invention, as shown in FIG. 2, a source program is created in a source language (step S).
100), convert the source program into a target program (step S200), and link the target program with an existing target program as necessary (step S200).
300). During the series of the target program creating process, the optimization process of the program having the loop processing unit is performed in the compiling process in step S200. The details of the compiling method according to the embodiment of the present invention will be described below with reference to the flowchart shown in FIG.

The compiling method according to the embodiment of the present invention is as follows: 1) (Syntax interpretation, step S201) First, a source program described in a source language is converted into a lower-level language, and 2) (first intermediate text generation, Step S202) Save the source program converted into the lower language as a first intermediate text. 3) (Loop process extraction, step S203) Search in the first intermediate text, and at least one
It is determined whether there is a program part that specifies a loop processing composed of one common processing, a plurality of state processings, and a conditional branch instruction provided between these processings. If a loop processing exists, → ( Step S20
Go to 5) If there is no loop processing → (Step S20)
Go to 8) 4) (Recording area analysis, step S205) It is determined whether or not the recording area where the cyclic variable for controlling the number of loops in the conditional branch instruction is recorded is used for another purpose. If used, → (Step S
Go to 207) If not used for other purposes → (Step S
To 208) 5) (securing a recording area, step S207) securing a recording area capable of recording a value of a cyclic variable that is not used for another purpose, and 6) configuring (start address calculation, step S208) loop processing 7) (Start address write, step S209) Write the calculated start address value in the recording area, 8) (jump instruction conversion, step S210) conditional branch The instruction is jumped to the address value stored in the recording area with reference to the address value in the recording area, and is converted into a jump instruction for causing the processing device to execute a process of performing a state process of a jump destination. (2) Intermediate text generation, step S211) The first intermediate text after performing the processing of steps S203 to S210 is defined as a second intermediate text. 10) (code conversion, step S212) Replace the character string described in the second intermediate text with an instruction code suitable for the processing device and add a control code for linking with another target program It is done by doing.

Here, in the compiling method according to the embodiment of the present invention, the processing of "extraction of loop processing unit" and "analysis of recording area" is performed on the first intermediate text. May be compared with the description in the first intermediate text. For example, a conditional branch instruction for statement in a source program,
Since a while sentence, a do sentence, etc. are relatively easy to find, for example, the presence / absence and position of loop processing in the source program is determined, and a loop processing unit in the first intermediate text is extracted, or the source program is extracted. In contrast, if the above-described optimization processing is performed directly, the time required for the optimization processing can be reduced.

As the "loop processing extraction method" in the first intermediate text, "bne $ a, $ b, La
bel1, ... j Label2 "should be found. Then, by examining how the values of the two cyclic variables #a and #b used in the conditional branch instruction change, it is determined which cyclic variable is for controlling the number of loops. Normally, the cyclic variable specified by the li instruction in the conditional branch instruction is used for comparison processing, so that the cyclic variable for controlling the number of loops can be assumed to be not specified by the li instruction. . Thereafter, a recording area analysis step is performed on the recording area of the cyclic variable.

Further, the "jump instruction" used in the jump instruction conversion step is a processing device which jumps to an address value stored in a recording area designated by the jump instruction and subsequently executes the instruction at the jump destination. It is an instruction to urge. For example, in the MIPS R3000 processor, there are "j" and "jr", and if "jr $ 3" is set,
Jumps to the address value stored in the recording area # 3, and subsequently executes the instruction at the jump destination (# 3 is an (address) value designating one of a plurality of existing recording areas). ). When the address value is specified, if the program to be optimized is a part of another target program as shown in FIG. 4, the address value stored in the recording area is the address value of the other program. It is better to make an absolute decision rather than a relative decision.

According to such a compiling method, the jump from the common processing to each state processing can be performed only once irrespective of the number of state processing. Therefore, even if the number of state processing increases, the target program is executed. Number of jumps (J
The rapid increase of n) can be suppressed. Actually, when the cumulative jump number (Jn) in the target program obtained by the compiling method according to the present invention is expressed by a mathematical formula, when the number of state processes in the target program is n, the number of jumps from the common process to each state process is all Since the state processing is performed once, the total is n times. The number of jumps returning from each state process to the common process is one except for the last n-th state process, so that the total is n-1 times. Therefore, the cumulative jump number (Jn) is obtained by summing these two numerical values, which is 2n-1 times. When compared with the conventional cumulative jump number (Jn), as shown in FIG. Since the number of times can be reduced and the capacity of the program can be eliminated because the conditional branch instruction for comparing two cyclic variables can be deleted, it can be made smaller than the conventional one.

Next, in order to better understand the compiling method according to the embodiment of the present invention, a few experimental examples of the second intermediate text created using the compiling method according to the embodiment of the present invention will be described. . In the following experimental example, the “recording area” is a register provided in the processing device.
3 (Note: $ 3 indicates an address value assigned to each of the plurality of register memories).

FIG. 6 shows, as Experimental Example 1, a second intermediate text (first intermediate text) shown in FIG. 14A created by applying the compiling method according to the embodiment of the present invention.
It is a figure showing an intermediate text.

The compiling method according to the embodiment of the present invention is as follows: 1) First, the intermediate text (first intermediate text) is searched to determine whether or not there is a loop processing unit for defining the loop processing. In this case, the intermediate text (FIG. 14a)
Has conditional branch instructions 57, 58, 59, so that the optimization processing of the loop processing unit is executed.

2) Next, it is determined whether or not the register # 3 for storing the value of the cyclic variable for controlling the number of loops is used for a purpose other than the one related to the loop processing. In the case of this intermediate text, it is assumed that the register # 3 is used only for controlling the number of loops (the case where it is not used will be described later), and the processing proceeds to the next processing.

3) Subsequently, at the beginning of the intermediate text, an instruction "li $ 3, (start address of the first state process) which causes the processing device to execute a process of writing the start address of the first state process in the register # 3 "500. In the case of this experimental example, the start address (0x100) of the state processing A to be executed first is written into the register # 3.

4) Next, at the end of the common process X, an instruction "jr $ 3" 501 for prompting a jump to the address value specified by the register # 3 is arranged.

5) Next, at the end of each state process, after executing the state process, a start address calculation instruction 5 for setting the address value in register # 3 to the start address value of the next state process
03, 504 and 505 are arranged. In this experimental example, the state process A has six steps (here, step means a unit indicating the number of command statements, and one step has a size of 4 bytes) (6 steps × 4 bytes = 24 bytes)
Therefore, the start address value of the next state process B is 6 steps of the state process A and the instruction 5
Since there are 8 steps (32 bytes) obtained by adding 2 steps (8 bytes) of 02 and 503, 32 bytes are added to the start address value of the state processing A, and the start address value of the next state processing B is obtained. Is set after the state processing A, the start address setting instruction "addi $ 3, $ 3, 32", which sets the value in the register # 3. Similarly, state processing B (30 steps (1
20)), after the state processing B, 128 bytes are added to the start address value of the state processing B, and the register {
For the instruction “addi $ 3, $ 3,128” 504 having a value of 3 and the state processing C (14 steps (56 bytes)), 64 bytes are added to the start address value of the state processing C after the state processing C, and Instruction "addi $ 3, $ 3,64" as value
505 is arranged. Since the address is generally described in byte units, the start address calculation step is performed in byte units.

6) Next, each head address setting instruction 50
Immediately after 3, 504, and 505, after executing the start address setting processing, an instruction “j TOP” 502 that causes the processing device to execute processing for jumping to the start address of the common processing X is arranged. As a result, when the processing device interprets this instruction, it jumps to the start address of the common process X, and the common process X is executed.

By the above series of steps, the first intermediate text having the loop processing can be optimized. Here, if there are a plurality of similar independent loop processing units in the program before compilation, the second intermediate text obtained after the end of the first optimization process is set as a new first intermediate text and the unprocessed It is preferable to execute the optimization processing on the loop processing unit. Further, in this experimental example, the start address value of the next state processing is calculated by the addition processing, but any method may be used as long as the start address value of the state processing can be obtained.

Next, in order to clarify that the number of accumulated jumps can be significantly reduced by the compiling method according to the embodiment of the present invention, the processing unit executes the program obtained in Experiment 1 when executing the program. The operation will be described. Here, the number of bytes of the state processes A, B, and C is 24, 120, and 56 (bytes), respectively.
And

When the processing device executes the program of the form shown in FIG. 6, 1) First, the first address value (0x100) of the first state process A is written into register # 3 in instruction 500.

2) Subsequently, the first common process X is executed.

3) Next, in the jump instruction 501,
Jump to the start address value (0x100) of state processing A specified by register # 3 (solid line A).

4) Next, state processing A is executed.

5) Next, in the start address setting instruction 503, the number of bytes 24 of the state processing A and the number of bytes 8 of the instructions 502 and 503 (2 steps × 4 bytes) are added to the address value in the register # 3. The value in register # 3 is set to the start address value (0x120) of the next state processing B.

6) Next, a jump instruction 502 is used to jump to the start address value of the common process X.

7) Subsequently, the second common process X is executed.

8) Next, in the jump instruction 501,
Jump to the start address value (0x120) of state processing B specified in register # 3 (broken line B).

9) Subsequently, state processing B is executed.

10) Next, a start address setting instruction 504
, The number of bits 120 of the state process B and the number of bits 8 of the instructions 502 and 503 are added to the address value in the register # 3, and the value in the register # 3 is set as the start address value (0x1A0) of the next state process C. Set.

11) Subsequently, a jump instruction 502 is used to jump to the start address value of the common process X.

12) Subsequently, the third common process X is executed.

13) Next, in the jump instruction 501, jump to the start address value (0x1A0) of the state process C specified in the register # 3 (broken line C).

14) Next, state processing C is executed.

15) Next, a start address setting instruction 505
In the above, the number of bits 56 of the state process C and the number of bits 8 of the instructions 503 and 502 are added to the address value in the register # 3, and the value in the register # 3 is changed to the start address value (0x1E0) of the next state process D. Set.

16) Subsequently, a jump instruction 502 is used to jump to the start address value of the common process X.

17) Next, the fourth common process X is executed.

18) Next, in the jump instruction 501, jump to the start address value (0x1E0) of the state processing D specified in the register # 3 (broken line D).

19) Execute state processing D (end of loop processing).

As described above, when the program generated by the compiling method according to the embodiment of the present invention shifts from the common process X to each of the status processes A, B, C, and D,
Instead of successively comparing the values of two cyclic variables in a plurality of conditional branch instructions as in the related art, the program jumps directly to the next state processing by referring to the leading address value of the next state processing derived in advance. Higher-speed processing becomes possible. Also, since the number of instructions to be placed between state processes can be reduced from four to two,
It is also possible to reduce the capacity of the target program having the loop processing.

Next, as an experimental example 2, the register # 3
The case where it is used for other purposes, such as in common processing or state processing, will be described with reference to FIG.

In the experimental example 1 shown in FIG. 6, the case where the register # 3 is not used for another purpose has been described. However, the case where the register # 3 is used for another purpose is sufficiently considered. Basically, such a case can be solved by setting a register used for a cyclic variable to an empty register not used in another process.
For example, when a MIPS R3000 processor is considered as a processing device, this processing device has 32 registers at addresses $ 0 to $ 31 as a recording area, and most of them are not used. Therefore, it is easy to find registers that are not used for other purposes.
In the case of the intermediate text after the end of optimization shown in (a), the register # 16 confirmed to be not used for another purpose is selected as a recording area. Here, the difference from the intermediate text shown in FIG. 6 is that the register # 3 for writing the start address of each state process is set in the register # 16 ("Jr $ 16" 507).

If there is no empty register, it is preferable to use the stack memory area in the processing device as a recording area of the head address while using the register for other purposes.
Hereinafter, as an experimental example 3, a compiling method according to the embodiment of the present invention in such a case will be described with reference to FIG.
This will be briefly described with reference to FIG.

Assume now that register # 3 used in the loop processing is used for another purpose.

If the register for storing the start address value of the state processing to be executed next is used for another purpose and there is no empty register, 1) first, the latest in the register # 3 An instruction “sw $ 3, y ($ sp)” 508 for saving information in the stack memory area whose address is ($ sp + y) is arranged at the beginning of the program.

2) Next, an instruction "li $ 3, (first address of the first state process)" instructing the processing device to execute a process of writing the first address of the first state process to the register # 3 is issued. Placed after 508.

3) Next, an instruction “sw $ 3, x ($ sp)” 510 for saving the address value in the register $ 3 in the stack memory area whose address is ($ sp + x) is issued by the instruction 509.
Place after. In the processing of 2) and 3), the work of writing the start address of the state processing to the stack memory area via the register $ 3 is performed, but this is directly performed by the processing device (MIPS R3000 processor) at the present time. This is because there is no means for executing a process of writing information in the stack memory area. Therefore, if means for writing desired information directly into the stack memory becomes available, steps 2) and 3) can be combined into one.

4) Subsequently, an instruction "lw $ which instructs the processing unit to execute a process of writing the information of the stack memory area having the address (@ sp + y) into the register $ 3
“3, y ($ sp)” is arranged after the instruction 510.

5) The value in the register # 3 is changed to the address ($
The instruction “sw $ 3, y ($ sp)” 512 to be saved in the stack memory area (sp + y) is placed at the end of the common processing X.

6) An instruction “lw $ 3, x ($ s) that instructs the processing unit to execute a process of writing information in the stack memory area having the address ($ sp + x) to the register $ 3
p) ”513 is arranged next to the instruction 512.

7) At the end of the common processing X, an instruction "jr $ 3" 501 for prompting a jump to the address value stored in the register # 3 is arranged.

8) Register $ 3 at the end of each state process
Address setting instruction "addi $ 3, $ 3,
(Appropriate value) "503, 504, 505 are arranged.

9) Immediately after each head address calculation instruction, an instruction “j TOP” 502 for instructing the processing unit to execute a process for jumping to the head address of the common process X is arranged. Thus, when the processing device interprets this command, the common process X is executed.

By doing so, the compiling method according to the embodiment of the present invention can be executed even when there is no empty register. In other words, when there is no empty register, the head address value required for jumping to each state process and information used in other processes are saved to different address positions in the stack memory area, and each of the information is saved when necessary. By reading and writing information from the stack memory area to register # 3,
The compiling method according to the embodiment of the present invention can be executed. In addition, the information in the register related to another use is not erased by the compiling process.

In the above experimental example, each processing (X, A,
(B, C, D) are described only in one routine, but the processing of each processing is converted into a subroutine and described in another program. It goes without saying that the compile method according to the embodiment of the present invention can be applied by absolutely setting the start address value. Also, the case where the number of states is four (A to D) has been described, but it goes without saying that the function and effect of the present invention can be sufficiently obtained with five or more states.

Also, depending on the processing device, after executing an instruction such as a loop processing instruction or a jump instruction, the instruction immediately after the instruction is not executed, but another instruction block to be executed before the execution of the instruction is stored. Delay slot). The processing device having such a delay branch slot can also perform the optimization of the present invention. For example, the present invention can be applied to an intermediate text having a delay branch slot shown in FIG. With the compiling method according to the embodiment, the program size can be optimized like the intermediate text shown in FIG. still,
At this time, an appropriate instruction such as an instruction nop 514 for instructing the processing unit to execute the “do nothing” processing in the delay branch slot may be arranged.

The above is a basic experimental result using the compiling method according to the embodiment of the present invention. The compiling method according to the embodiment of the present invention is, for example, a PES packet of MPEG2 as shown in FIG. Regarding the structure, the present invention can be applied to optimization of a program (video processing program) for decoding the encoded stream.
That is, generally, as shown in FIG. 10, decoding of an encoded stream is configured to execute a plurality of state processes using a 1-byte acquisition process of acquiring an input stream of 1 byte as a common process. The basic structure of the decryption program is a loop process. Therefore, by creating the decoding program using the compiling method according to the embodiment of the present invention, the time required for decoding the encoded stream and the capacity of the decoding program can be reduced.

The compiling device according to the embodiment of the present invention has, for example, an appearance as shown in FIG.
That is, the compiling device according to the embodiment of the present invention is configured by incorporating each component of the compiling device 100 in the computer 80. The computer 80 includes a floppy disk drive 81 and an optical disk drive 82. Then, the floppy disk 83 is inserted into the floppy disk drive 81, and the optical disk 84 is inserted into the optical disk drive 82, and by performing a predetermined read operation, the compile programs stored in these recording media are loaded into the computer. Can be installed. Further, by connecting an appropriate drive device to the computer 80, for example, by using a ROM 85 serving as a memory device and a cartridge 86 serving as a magnetic tape device,
It is also possible to install programs and link with other target programs.

Further, the compiling device according to the embodiment of the present invention may be programmed and stored in a computer-readable recording medium. When compiling the source program, the recording medium is read into a computer system, the compilation program is stored in a recording unit such as a memory in the computer system, and the processing program executes the compilation program. A compiling device and a compiling method according to an embodiment of the present invention can be realized on a computer system. Here, the recording medium means a computer-readable medium on which a program can be recorded, such as a semiconductor memory, a magnetic disk, an optical disk, a magneto-optical disk, a magnetic tape, and a digital video disk.

Thus, it should be understood that the present invention covers various embodiments not described herein. Therefore, the present invention must be limited only by the matters specifying the invention according to the claims that are reasonable from this disclosure.

[0091]

As described above, according to the compiling device of the present invention, the number of accumulated jumps when the processing device executes the loop processing can be greatly reduced.
The time required for executing the loop processing can be reduced, and the capacity of the target program having the loop processing can be reduced.

According to the compiling method of the present invention,
Since the number of accumulated jumps when the processing device executes the loop processing can be greatly reduced, the time required for executing the loop processing can be reduced, and the capacity of the target program having the loop processing can be reduced.

Further, according to the computer-readable recording medium storing the compile program of the present invention, the number of accumulated jumps when the processing device executes the loop processing can be greatly reduced. The required time can be reduced, and the capacity of the target program having the loop processing can be reduced.

Further, according to the computer-readable recording medium storing the object program of the present invention,
Since the target program has been optimized, loop processing can be executed at high speed.

[Brief description of the drawings]

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

FIG. 2 is a flowchart illustrating a compiling method according to the embodiment of the present invention.

FIG. 3 is a flowchart illustrating a compiling method according to the embodiment of the present invention.

FIG. 4 is a diagram showing a method of linking an address value between an optimized program and another target program.

FIG. 5 is a diagram comparing the capacity and the accumulated jump number of the target program generated by the compiling method of the present invention with those of the conventional target program.

FIG. 6 is a diagram showing an intermediate text created by a compiling method according to the embodiment of the present invention.

FIG. 7 is a diagram showing an intermediate text created by a compiling method according to the embodiment of the present invention.

FIG. 8 is a diagram showing an intermediate text created by a compiling method according to the embodiment of the present invention.

FIG. 9 illustrates a typical MPEG2 PES packet structure.

FIG. 10 is a diagram for explaining a typical video processing process;

FIG. 11 is a diagram showing an overview of a compiling device according to the embodiment of the present invention.

FIG. 12 is a schematic diagram for explaining a loop process.

FIG. 13 is a diagram showing a source program having typical loop processing.

FIG. 14 illustrates an intermediate text having a typical loop processing.

[Explanation of symbols]

REFERENCE SIGNS LIST 100 compile device 110 source program input unit 120 compile processing unit 121 syntactic interpretation unit 122 intermediate text generation unit 123 optimization processing unit 124 loop processing Extraction unit 125 ... Recording area analysis unit 126 ... Start address setting unit 127 ... Jump instruction conversion unit 128 ... Code conversion unit 129 ... Object program output unit 130 ... Link processing unit 1
31 ... Execution program output section

Claims (4)

[Claims] 1. A compiling device for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which can be easily processed by the processing device, comprising: at least one common process and a plurality of state processes. And optimizing means for extracting a loop processing unit composed of conditional branch instructions provided between these processes and optimizing loop processing, wherein the optimizing means converts a source program or a source language into a lower-level language. Loop processing extraction means for extracting a loop processing unit in the intermediate text, and a recording area for analyzing a recording area of a variable for controlling the number of loops in the conditional branch instruction, and selecting an address recording area for recording a head address value to be described later. Area analyzing means, calculating a start address value for each of the state processes,
After completion of one state process, a start address setting means for writing a start address value of a state process to be executed next in the address recording area; and referring to the condition branch instruction with the start address value in the address recording area. A jump instruction converting means for jumping to the start address of the next state processing to be executed and converting the processing for performing the state processing of the jump destination into a jump instruction to be executed by the processing apparatus. 2. A compiling method for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which is easily processed by the processing device, comprising: at least one common process and a plurality of state processes. And optimizing loop processing by extracting a loop processing unit composed of conditional branch instructions provided between these processes, and optimizing the loop processing. The optimizing step converts a source program or a source language into a lower-level language. A loop processing extracting step of extracting a loop processing unit in the intermediate text, and an address recording for analyzing a recording area of a variable for controlling the number of loops in the conditional branch instruction and selecting a recording area for recording a leading address value to be described later. Calculating a start address value for each of the area analysis step and the state processing;
After completion of one state process, a start address setting step of writing a start address value of a state process to be executed next in the address recording area; and referring to the start address value in the address recording area for the conditional branch instruction. A jump instruction conversion step of jumping to a start address of a state processing to be executed next, and converting the processing for performing the state processing of the jump destination into a jump instruction to be executed by the processing device. 3. A computer-readable recording medium storing a compile program for converting a source program described in a source language for causing a processing device to execute a predetermined process into a target program which can be easily processed by the processing device. An optimization process of extracting a loop processing unit including one common process and a plurality of state processes and a conditional branch instruction provided between these processes, and optimizing the loop process; A loop processing extraction process for extracting a loop processing unit in an intermediate text obtained by converting a program or a source language into a lower-level language; and analyzing a recording area of a variable for controlling the number of loops in the conditional branch instruction, and determining a start address value to be described later. A recording area analysis process for selecting an address recording region to be recorded, and a start address for each of the status processes The calculated,
After completion of one state process, a start address setting process of writing a start address value of a next state process to be executed in the address recording area, and referring to the start address value in the address recording area for the conditional branch instruction. Jump processing to jump to the start address of the state processing to be executed next, and to convert the processing for performing the state processing of the jump destination into a jump instruction to be executed by the processing device, and causing the computer to execute these processing. A computer-readable recording medium storing a compilation program characterized by the above-mentioned. 4. A computer-readable recording medium storing a target program, comprising a target program created by the compiling method according to claim 2.