JP3236714B2 - Program conversion device and program conversion method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a program conversion apparatus and a program conversion method which are applied to a compiler or the like for converting a source code into a target code and optimize a code for an induction variable used in a loop process.

[0002]

2. Description of the Related Art When converting a program source code into a target code by a compiler or the like, in many cases, various optimization processes are performed for the purpose of reducing the size of the target code and improving the execution speed. One of them is to optimize the induction variables. As described in, for example, “Compiler II” (authored by AV Eho R. Cessy JD Ullman, translated by Kenichi Harada: Science), the value of the induction variable is changed each time one loop is repeated in loop processing. Optimization is a variable that increases by a fixed amount, positive or negative, and optimization means, for example, when an induction variable that obtains a value by multiplying a control variable for loop processing by a predetermined number is used in the source code, In order to improve the processing speed and reduce the code size, for example, a code for obtaining a new value by adding the predetermined number to the value of the induction variable in the loop processing is generated.

[0003] The optimization of induction variables is particularly effective for loop processing described for performing data processing, in which a numerical value is stored in each element of an array having a large number of elements.
When translating a description that stores data in each element of an array into a machine language program, the compiler needs to calculate the address of each element, and the calculation of the address of each element includes the calculation of the address of each element. This is because the multiplication of the size of the size and a control variable indicating the rank of each element is performed. Generally, the execution time of a multiplication instruction of a machine language instruction is longer than that of an addition instruction. Therefore, when such multiplication is replaced with addition, the processing speed when the above-described loop processing is replaced with a machine language is further improved.

The above optimization of the induced variables in a compiler or the like is performed using a program conversion device. Before describing the program conversion device, terms used will be described below. Control variable This variable is used to determine whether to continue or stop the loop processing, and increases by a certain value each time the loop processing is performed once. • Arithmetic expression An expression that uses variables and constants as operands. (For example, 10
0 * x + 2, x / 200 + 10)-Assignment statement There is a variable on the left side of the equal sign, and there are variables, constants, and arithmetic expressions on the right side. This is the statement to be assigned. (For example, y = 130, y = 1
00 * x + 2, y = x / 200 + 10) Linear operation expression This is an operation expression in which variables are used as operands, and the order of all the variables is 1. (For example, 100 *
x + 2 x / 200 + 10) Definition of variable The value of a variable is set by an assignment statement. (For example, a = 100, s = 100 * 2) Use of a variable The use of a variable as an operand in an arithmetic expression.

FIG. 3 is a diagram showing the configuration of a conventional program conversion device provided in a C language compiler. The program conversion device includes an induction variable holding unit 21, an in-loop induction variable detection unit 22, and an in-loop induction variable rewriting unit 23. The induction variable holding unit 21 holds a linear operation expression in a loop, a variable name of an induction variable, an increment value for each loop process, and an initial value.

The in-loop induction variable detection unit 22 performs a linear operation expression detection operation for an operation in a loop process in a program, and converts a variable defined by the operation detected by the linear operation expression detection operation into an induction variable. Then, the induced variable and information on the induced variable are held in the induced variable holding unit 21. The linear operation expression detection operation will be specifically described. In each loop process in the program, the linear operation expression detection unit 22 detects an operation to be performed each time the loop process is executed once, and the operation expression determines a control variable and a constant by the operation. Check whether the operation expression is a child operation or an operation expression using a control variable and a variable as operands. (The operation expression is an operation expression using a control variable, a variable, and a constant as operands.) It may be an expression.). If the other operand is a variable, it checks whether the definition of the variable exists in the loop processing. As a result of such an investigation, if one operand is a control variable and the other operand is a constant or a variable whose value is invariable in the loop processing, the induced variable detection unit 22 determines that the operation expression is Check whether it is a linear operation expression. If the in-loop induction variable detection unit 22 detects a linear operation expression, the location where the linear operation expression exists is stored, and a variable defined by the linear operation expression is set as an induction variable. Thus, the in-loop induced variable detection unit 2
2 calculates the induction variable and causes the induction variable holding unit 21 to hold the induction variable. Then, the in-loop induction variable detection unit 22 calculates the calculation result of the linear operation expression detected by the linear operation expression detection operation by one loop processing. Calculate the increment value. Here, the increment value may be a positive value or a negative value. After obtaining the increment value of the operation result of the linear operation expression, the in-loop induction variable detection unit 22
The initial value of the induced variable is determined and held in the induced variable holding unit 21.

The in-loop induction variable rewriting unit 23 includes a definition rewriting unit 24 and a judgment condition rewriting unit 25. The definition rewriting unit 24 rewrites the definition of the induction variable in the loop processing. Specifically, the definition rewriting unit 24 determines whether the detected linear operation expression includes multiplication and division, and whether the rewriting is valid. If it is determined that rewriting is valid, a variable that can be used for rewriting is generated, and an addition-type code that increases the variable by the increment value obtained by the in-loop induced variable detection unit 22 is created. An assignment statement defined by the addition formula code created by the created variable is written at a predetermined position in the loop processing of the program. After the writing, the definition rewriting unit 24 rewrites, in the program, the linear operation expression at the position detected by the in-loop induction variable detection unit 22 into a variable.

The judgment condition rewriting unit 25 checks whether or not the control variable is used to define another variable outside the loop processing. If the control variable is not used, it is performed by the control variable. The new variable determines whether to continue or terminate the loop processing, and the code of the assignment statement to initialize the control variable, the code of the assignment statement that increases the content of the control variable, and the control variable Deletes the code of the assignment statement for which the determination is made from the loop processing.

In addition, a configuration for creating the above-mentioned initialization code,
The details of the configuration for rewriting the determination are not the focus of the present invention, and thus description thereof is omitted. The operation of the program conversion device configured as described above will be described. FIG.
(A) shows each element (a) of an array a [] in which the size of each element is a word type (2 bytes).

[0] to a [98])
Is a program written in C language so that is substituted.

A compiler having a program conversion device rewrites a description of an array in a program.
The rewritten result is shown in FIG. The description of the rewriting of the array is omitted because it is not the main purpose of the present invention, but the rewritten portion will be described. The variable s1 is a pointer variable for indicating the address of each element of the array. The pointer variable s1 is calculated by adding an offset value to the address of each element from the head address on the memory of the area reserved for the array. "S1 = & a + 2 * i" in the figure is an assignment statement for calculating the address of each element of the array and assigning the calculation result to the pointer variable s1. In this assignment statement, & a is the array a
[] Is the head address, and 2 indicates the byte size of each element of the array a []. Further, the variable i is a control variable indicating the order of each element. "* S1 =
"0" is a code for storing 0 in the memory at the address indicated by the pointer variable s1. The above-described program conversion device operates on the program whose array description has been rewritten in this way. Induction variable detection part 2 in loop
2 performs a linear operation expression detection operation, detects “& a + 2 * i” which is a code of the linear operation expression, and causes the induction variable holding unit 21 to hold the variable s1 as an induction variable. Further, the in-loop induction variable detection unit 22 obtains an increment value of the operation result of the linear operation expression “& a + 2 * i”. Induction variable detection part 2 in loop
2 refers to “i = i + 1”, which is the code of an assignment statement that increases the content of control variable i, obtains 1 which is the increment value of control variable i, and 2 which is the increment value of “& a + 2 * i” Is calculated. Next, the definition rewriting unit 24 generates a variable t that can be used for rewriting the linear operation expression,
Is an addition-type code such that “t” is added by “t”.
= T + 2 ”is written at a predetermined position in the program, and the portion of the program where“ & a + 2 * i ”, which is the code of the linear operation expression, is rewritten to the variable t. As a result, the assignment statement “s1 = & a + 2 * i”
Is rewritten to “s1 = t”. Further, definition rewriting unit 2
4 is a code for initializing the contents of the variable t, "t = &
a "are created, and these are written at predetermined positions in the program. The determination condition rewriting unit 25 checks whether or not the control variable i is used to define another variable outside the loop, and if not used, determines whether the control variable i is The variable t determines whether to continue or terminate the processing, the code of an assignment statement for initializing the control variable i, the code of an assignment statement for increasing the content of the control variable i, and the control variable i are looped. The code of the assignment statement that determines the processing is deleted from the loop processing. as a result,
The program shown in FIG. 4B is rewritten so that the loop processing is controlled by the variable t, as shown in FIG. 4C.

[0011]

However, according to the above prior art, when a control variable of a loop process is used as an operand in an arithmetic expression existing outside the loop process, the program conversion device is configured as follows. The problem is that the code of the assignment statement that increases the contents of the control variables in the loop processing cannot be erased, and the processing speed cannot be sufficiently increased when the loop processing is replaced with machine language. there were.

[0012] For example, FIG. 5A shows that a

0 is assigned to the elements from [0] to a [998], and the last element of the array, a

[999]
Is a program written so that 1 is assigned to When the program conversion device performs the above-described rewriting operation on such a program, the program conversion device

In order to obtain the address of [999], the control variable i that should have stored the numerical value of 999 at the end of the loop processing is not deleted.
Terminates processing while leaving the code using. In other words, the program conversion device rewrites the program as shown in FIG. 5B so that the calculation performed by the code of the linear operation expression “s1 = & a + 2 * i” is substituted by the code of the addition statement “t = t + 2”. However, the code of the assignment statement increasing the content of the control variable i cannot be erased, and the process ends in the state of FIG. Since this program is a program that repeats the processing 999 times, the machine language program finally generated by the compiler after rewriting the program by the program conversion device is a machine language program corresponding to the code of the redundant linear operation expression. The instruction is repeated 999 times. As a result, the execution time of the machine language instruction becomes longer than necessary.

The present invention has been made in consideration of the above problems, and has as its object to provide a program conversion apparatus which targets induction variables used for defining other variables outside loop processing and realizes high-speed program processing. And

[0014]

In order to solve the above-mentioned problems, a program conversion apparatus according to the present invention provides an operation result of an operation expression including a control variable in a loop process of a program to be processed held in a program holding unit. Is calculated, a new variable whose content increases by the increment is created, an addition expression is created using the new variable and the increment as an operand, and the operation result of the addition expression is added to the new variable. A program conversion device that creates an assignment statement to be substituted, rewrites the arithmetic expression with a new variable, and further rewrites an arithmetic expression containing the control variable outside the loop processing with a new variable, the program conversion device holding From within the loop processing of the program
In-loop arithmetic expression detecting means for detecting an arithmetic expression in which a control variable is used as an operand and a constant or an invariable variable is used in loop processing for another operator, and said arithmetic expression in loop detection means Detects the same operation expression from the outside of the loop process that includes the operation expression detected, and furthermore, the variable used as the operand in the operation expression is changed from the loop process to the operation expression outside the loop process. It is determined whether or not it is defined in the area, if it is determined that it is not defined, it is determined that the detected arithmetic expression is rewritable, and if it is determined that it is defined, the detected arithmetic expression is An out-of-loop operation expression detecting means for determining that rewriting is impossible, and an operation expression detected by the in-loop operation expression detecting means based on an increment value of the control variable in one loop processing. Performance Value calculating means for calculating an increment value of a calculation result by executing the above, variable creating means for creating a variable having an unused variable name in a program held in the program holding unit, and the variable creating means Adding the variable created by the above and the increment value calculated by the increment value calculating means, and updating the value of the control variable in the program; In-loop arithmetic expression rewriting means for rewriting the assignment statement to be written into the assignment statement created by the assignment statement creating means, and rewriting the arithmetic expression at the location detected by the in-loop arithmetic expression detecting means to the variable created by the variable creating means. When the arithmetic expression outside the loop is determined to be rewritable, the arithmetic expression at the position detected by the arithmetic expression outside the loop is
And an out-of-loop arithmetic expression rewriting means for rewriting the variable created by the variable creation means.

Further, according to the program conversion method of the present invention, an increment value of an operation result of an arithmetic expression including a control variable in a loop process of a program to be processed held in a program holding unit is obtained, and only the content of the increment value is obtained. Creates a new variable that increases, creates an addition expression with the new variable and the increment value as operands, creates an assignment statement in which the operation result of the addition expression is assigned to the new variable, A program conversion method for rewriting an arithmetic expression to a new variable and further rewriting an arithmetic expression including the control variable outside the loop processing to a new variable, wherein a control method is executed from within the loop processing of the program held in the program holding unit. Variables are used as operands,
In another loop, an arithmetic expression detection step for detecting an arithmetic expression in which a constant or an invariable variable is used in the loop processing, and a loop processing including an arithmetic expression detected by the arithmetic expression detection step in the loop From the outside, the same arithmetic expression is detected, and whether the variable used as the operand in the arithmetic expression is defined in the region from the loop processing to the arithmetic expression outside the loop processing is determined. If it is determined that it is not defined, it is determined that the detected arithmetic expression is rewritable, and if it is determined that it is defined, it is determined that the detected arithmetic expression is not rewritable. An arithmetic expression detecting step, and an arithmetic operation performed by a single arithmetic operation of the arithmetic expression detected by the arithmetic expression detecting step in the loop based on an increment value of the control variable in one loop processing. An increment value calculating step of calculating an increment value of a result, a variable creating step of creating a variable having a variable name that is not used in the program held in the program holding unit, and a variable created by the variable creating step. Adding an increment value calculated by the increment value calculating step and an assignment statement creating step of creating an assignment statement for assigning the added result to the variable; and an assignment statement updating a value of a control variable in the program. Rewriting the assignment expression created by the assignment statement creating step, and rewriting the arithmetic expression at the location detected by the in-loop arithmetic expression detection step to the variable created by the variable creating step; If the expression detection step determines that the operation can be rewritten, the expression at the location detected by the out-of-loop operation expression detection step is replaced with the variable. Comprising a loop outside arithmetic expression rewriting step of rewriting the variable creation step creates.

[0016]

According to the above-mentioned means, in the program conversion device (method) of the present invention, the in-loop operation expression detecting means (step) converts the control variable from the loop processing of the program held in the program holding section into the operand. Detects the arithmetic expression used as. Outside the loop processing that includes the detected arithmetic expression, the outside-loop arithmetic expression detection means (step) operates, and the same arithmetic expression as the arithmetic expression detected by the in-loop arithmetic expression detection means (step) is output. Then, it is determined whether or not the variable used as the operand in the operation expression is defined in a region from the loop processing to the operation expression outside the loop processing. An increment value calculating means (step) is operated for an increment value of the control variable in one loop processing, and one of the arithmetic expressions detected by the in-loop arithmetic expression detecting means (step) is calculated.
The increment value of the calculation result by performing the calculation twice is calculated.
The variable creating means (step) operates on the program held in the program holding unit, and a variable having an unused variable name is created as a usable variable. A variable created by the variable creating means (step);
The assignment statement creating means (step) operates on the increment value calculated by the increment value calculating means (step), and the variable created by the variable creating means (step) and the increment value calculating means (step) An assignment statement is created in which the result of adding the calculated increment value to the variable is assigned to the variable. The in-loop arithmetic expression detection means (step) operates on the assignment statement for updating the value of the control variable in the program and the assignment statement created by the assignment statement creation means (step), and the The arithmetic expression is rewritten to the variable created by the variable creating means (step), and the arithmetic expression at the position detected by the in-loop arithmetic expression detecting means (step) is replaced by the variable created by the variable creating means (step). Rewritten. If the out-of-loop arithmetic expression detection means (step) determines that the rewrite is possible, the out-of-loop arithmetic expression rewrite means (step) compares the arithmetic expression at the position detected by the out-of-loop arithmetic expression detection means (step). In operation, the arithmetic expression at the position detected by the out-of-loop arithmetic expression detecting means (step) is rewritten to the variable created by the variable creating means (step).

[0017]

FIG. 1 is a diagram showing the configuration of a program conversion device. The optimization of the induction variable by the program conversion device may be performed on, for example, a source code given to a compiler, or may be performed on an intermediate code obtained in the middle of a compiling process by the compiler. You may do so.

The program conversion device includes a control unit 11, a pre-optimization code holding unit 12, an induction variable holding unit 13, a loop induction variable detection unit 14, an outside loop induction variable detection unit 15, a loop induction The control unit 11 including the variable rewriting unit 16, the in-loop induction variable rewriting unit 16, and the out-of-loop induction variable rewriting unit 19 causes the program conversion device to control the entire program conversion process of the program.

The pre-optimization code holding unit 12 holds an original program to be processed. Induction variable holding unit 13
Holds the code of the linear operation expression in the loop processing in the program stored in the pre-optimization code storage unit 12, the variable name of the induction variable, the increment value for each loop processing, and the initial value. The in-loop induction variable detection unit 14 performs a linear operation expression detection operation on an operation existing in any of the loop processes of the program stored in the pre-optimization code storage unit 12 (linear operation expression detection). The operation has already been described as the prior art, so a detailed description will be omitted.) A variable defined by an arithmetic expression detected by the linear arithmetic expression detection operation is defined as an induction variable, and the induction variable and the induction variable The information is stored in the induction variable storage unit 13. If the in-loop induction variable detection unit 14 detects a linear operation expression,
The in-loop induction variable detection unit 14 stores the place where the linear operation expression was present, and sets a variable defined by the linear operation expression as an induction variable. After the induction variable is obtained in this way and held in the induction variable holding unit 21, the in-loop induction variable detection unit 14 calculates an increment value of the operation result of the linear operation expression detected by the linear operation expression detecting operation. . Here, the increment value may be a positive value or a negative value. After calculating the increment value of the linear operation expression, the in-loop induction variable detection unit 14 obtains the initial value of the induction variable and calculates the initial value of the induction variable.
To be held.

The induction variable detection unit 15 outside the loop detects the induction variable inside the loop from outside the loop processing of the program stored in the pre-optimization code storage unit 12 where the induction variable detection unit 14 detects the operation formula. The same arithmetic expression as the arithmetic expression detected by the detection unit 14 is searched, and if present, the location where the arithmetic is present is stored. After the storage, in the area from the loop processing to the arithmetic expression external to the detected loop processing, the variable (control variable or control variable or It is determined whether or not a variable (invariant in the loop processing) is defined. If not defined, the out-of-loop induction variable detection unit 15 determines that the searched arithmetic expression is rewritable, and if defined, determines that the searched arithmetic expression is not rewritable. For example, the code of the assignment statement “s1 = i * 3” exists in the loop processing of the program stored in the pre-optimization code storage unit 12, and the code “s1 = i * 3” exists outside the loop processing. When the code of the assignment statement and the code of the assignment statement “w3 = i * 3” are present, the induction variable detection unit 15 outside the loop detects the code of the arithmetic expression of any of the assignment statements, and performs the calculation on them. Remember where the expression exists. In addition, the code of the assignment statement “s1 = s * i” exists in the loop processing of the program stored in the pre-optimization code storage unit 12, and “s4 = s * i” exists outside the loop processing. When the code of the assignment statement exists and the area from the loop processing to the arithmetic expression “s4 = s * i” outside the detected loop processing, “s =
When the code of the assignment statement “3” exists, the induction variable detection unit 15 outside the loop detects the code “s4 = s * i” and the code “s = 3”.

The in-loop induced variable rewriting unit 16 is composed of a definition rewriting unit 17 and a judgment condition rewriting unit 18. The definition rewriting unit 17 rewrites the definition of the linear operation expression in the loop processing of the program stored in the pre-optimization code storage unit 12. Specifically, the in-loop induced variable detection unit 1
The multiplication and division are included in the linear operation expression detected by No. 4 and it is determined whether rewriting is valid. If it is determined that the rewriting is valid, the definition rewriting unit 17 generates a variable that can be used for the rewriting, and calculates the variable by the increment value of the linear operation expression calculated by the induction variable detection unit 14 in the loop. The addition-type code to be increased is created and written to a predetermined position in the loop processing of the program stored in the pre-optimization code storage unit 12. After the writing, the definition rewriting unit 17 rewrites, in the program stored in the pre-optimization code storage unit 12, the linear operation expression at the location detected by the in-loop induction variable detection unit 14 into a variable. Further, the definition rewriting unit 17 refers to the initial value of the induction variable held in the induction variable holding unit 13 to create a code of an assignment statement for initializing the variable used in the addition expression code, and executes the loop processing of the program. Write to a predetermined position in.

The determination condition rewriting unit 18 rewrites the loop processing of the program stored in the pre-optimization code storage unit 12 so as to determine whether a new variable continues or terminates the loop processing. Further, the code of the assignment statement for initializing the control variable, the code of the assignment statement for increasing the content of the control variable, and the code for determining the control variable are held in the pre-optimization code holding unit 12. Erase from the loop processing of the program.

When the out-of-loop induction variable detection unit 15 determines that the out-of-loop induction variable detection unit 15 is rewritable, the out-of-loop induction variable detection unit 15 of the program held in the pre-optimization code holding unit 12 The linear operation expression at the detected location is rewritten to a variable generated by the definition rewriting unit 17. For example, the definition rewriting unit 17 rewrites the code of the assignment statement “s1 = 3 * i” to “s1 = t”, and the out-of-loop induction variable detection unit 15 codes the code of the assignment statement “s2 = 3 * i”. Is detected, the out-of-loop induction variable rewriting unit 19 rewrites the code of “s2 = 3 * i” to “s2 = t”.

A configuration for creating the above-mentioned initialization code,
The details of the configuration for rewriting the determination are not the focus of the present invention, and thus description thereof is omitted. The operation of the program conversion device configured as described above will be described. FIG.
(A) shows each element (a) of an array a [] in which the size of each element is a word type (2 bytes).

[0] to a [98])
And assign the last element of the array, a

[99] is a program written in C language so that 1 is substituted as the closing value.

A compiler provided with a program conversion device once rewrites a description of an array in a program. The rewritten result is shown in FIG. The above-described program conversion device operates on the program whose array description has been rewritten in this way. First, the control unit 11
The in-loop induced variable detection unit 14 is started. The in-loop induction variable detection unit 14 performs a linear operation expression detection operation, and “& a +
2 * i ”is detected, and the variable s1 is held in the pre-optimization code holding unit 12 as an induction variable. The in-loop induction variable detection unit 14 calculates the increment value of the operation result of these linear operation expressions. That is, the in-loop induction variable detection unit 14
Refers to “i = i + 1”, which is the code of an assignment statement that increases the value of control variable i, obtains 1 that is the increment value of control variable i, and executes the linear operation expression once. Is calculated, which is an increment value of the linear operation expression “& a + 2 * i”. Next, the induction variable detection unit 15 outside the loop detects “& a + 2 * i”, which is an arithmetic expression detected by the induction variable detection unit 14 from outside the loop processing in which the induction variable detection unit 14 detects the arithmetic expression. The same arithmetic expression detects "s1 = & a + 2 * i" which is an assignment statement existing on the right side of the equal sign.
After the detection, the control unit 11 activates the out-of-loop induction variable detection unit 15. The out-of-loop induction variable detection unit 15 stores a location in the pre-optimization code holding unit 12 where the operation expression exists. Next, the control unit 11 activates the definition rewriting unit 17.
The definition rewriting unit 17 generates a variable t, which is a variable that can be used for rewriting, creates “t = t + 2”, which is a code of an addition expression in which the variable t is added by 2, and generates a program Then, "& a + 2 * i", which is a code of a linear operation expression in the program, is rewritten to a variable t. Further, the definition rewriting unit 17 creates "t = &a", which is a code for initializing the contents of the variable t, and writes these at a predetermined position in the program. Next, the control unit 11
Activates the judgment condition rewriting unit 18. Judgment condition rewriting unit 1
Reference numeral 8 designates the variable t to determine whether to continue or end the loop processing performed by the control variable i, the code of an assignment statement for initializing the original induction variable i, and the contents of the control variable i. And the code of the assignment statement for which the control variable i is making a determination is deleted from the loop processing. Next, the control unit 11 activates the induction variable rewriting unit 19 outside the loop. The induction variable rewriting unit 19 outside the loop
The linear operation expression “& a + 2 * i” at the location detected by the out-of-loop induction variable detection unit 15 is rewritten to the variable t generated by the definition rewriting unit 17. As a result, the program shown in FIG. 5B is rewritten so that the loop processing is controlled by the variable t. FIG. 5C shows the rewritten result.

[0026]

As described above, according to the program conversion apparatus of the present invention, the control variable is used as the operand in the arithmetic expression existing outside the loop processing. However, if the arithmetic expression outside the loop processing is the same as that existing in the loop, the external arithmetic expression can be rewritten, so the contents of the control variables in the loop processing are increased. There is an effect that the code of the assigned assignment statement can be deleted, and the processing speed can be sufficiently increased when the loop processing is replaced with a machine language.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a program conversion device according to an embodiment of the present invention.

FIG. 2 is a diagram showing rewriting of a program by the program conversion device of the present invention.

FIG. 3 is a configuration diagram of a conventional program conversion device.

FIG. 4 is a diagram showing rewriting of a program by a conventional program conversion device.

FIG. 5 is a diagram showing rewriting of a program by a conventional program conversion device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 11 Control part 12 Code storage part before optimization 13 Induction variable storage part 14 Induction variable detection part in a loop 15 Induction variable detection part outside a loop 16 Induction variable rewriting part in a loop 17 Definition rewriting part 18 Judgment condition rewriting part 19 Induction variable outside a loop Rewriting department

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-2-50257 (JP, A) JP-A-64-31232 (JP, A) Interface, CQ Publishing Company, 1989-3, Vol. 15, No. 3, Issue 3 (No. 142), pp. 202-203 Wolfe, "Beyond Induction Variable", ACM SIGGPLAN Notices, 1992, Vol. 27, No. 7, p. 162-174 (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 9/45

Claims (2)

(57) [Claims] 1. An incremental value of an operation result of an arithmetic expression including a control variable in a loop process of a program to be processed held in a program holding unit is calculated, and a new variable whose content increases by the increment value is created. Then, create an addition expression using the new variable and the increment value as operands, create an assignment statement in which the operation result of the addition expression is assigned to the new variable, and rewrite the operation expression with the new variable. A program conversion device for rewriting an arithmetic expression including the control variable outside the loop processing into a new variable, wherein the control variable is used as an operand from within the loop processing of the program held in the program holding unit. , An arithmetic expression in a loop for detecting an arithmetic expression in which a constant or an invariable variable is used in loop processing for another operator, and an arithmetic expression detected by the arithmetic expression in the loop The same arithmetic expression is detected from outside the included loop processing, and the variable used as the operand in the arithmetic expression is defined in the region from the loop processing to the arithmetic expression outside the loop processing. It is determined whether or not the detected arithmetic expression is rewritable. If it is determined that the arithmetic expression is not defined, it is determined that the detected arithmetic expression is rewritable. An arithmetic expression outside the loop to be determined, and an arithmetic result of execution of one arithmetic operation of the arithmetic expression detected by the arithmetic expression inside the loop based on an increment value of the control variable in one loop processing An increment value calculating means for calculating an increment value of the variable; a variable creating means for creating a variable having a variable name that is not used in the program held in the program holding unit; Statement assignment means for creating an assignment statement for adding the calculated variable and the increment value calculated by the increment value calculation means and assigning the addition result to the variable; and assignment for updating the value of the control variable in the program. The statement in the loop is rewritten to the assignment statement created by the assignment statement creating means, and the arithmetic expression at the location detected by the arithmetic expression in the loop detecting means is replaced by the variable created by the variable creating means. When the outer arithmetic expression detecting means determines that the rewriting is possible, the outer arithmetic expression rewriting means for rewriting the arithmetic expression at the location detected by the outer arithmetic expression detecting means to the variable created by the variable creating means is provided. A program conversion device, comprising: 2. An incremental value of an operation result of an arithmetic expression including a control variable in a loop process of a program to be processed held in a program holding unit is calculated, and a new variable whose content increases by the increment value is created. Then, create an addition expression using the new variable and the increment value as operands, create an assignment statement in which the operation result of the addition expression is assigned to the new variable, and rewrite the operation expression with the new variable. A program conversion method for rewriting an arithmetic expression including the control variable outside the loop processing into a new variable, wherein the control variable is used as an operand from within the loop processing of the program held in the program holding unit. In the loop, an arithmetic expression detecting step for detecting an arithmetic expression in which a constant or an invariable variable is used in the loop processing is used as another operator. From the outside of the loop process including the arithmetic expression, to detect the same arithmetic expression,
Furthermore, if it is determined whether the variable used as the operand in the arithmetic expression is defined in the area from the loop processing to the arithmetic expression outside the loop processing, if it is determined that the variable is not defined If the detected arithmetic expression is determined to be rewritable, and if it is determined to be defined, the detected arithmetic expression is determined not to be rewritable, an out-of-loop arithmetic expression detection step; An increment value calculating step of calculating an increment value of an operation result of one execution of an arithmetic expression detected by the arithmetic expression detection step in the loop based on an increment value in the first loop processing; A variable creation step of creating a variable having a variable name that is not used in the program held in the program; a variable created by the variable creation step; and a step of calculating the increment value. An assignment statement creating step of creating an assignment statement for adding the increment value calculated by the above and assigning the added result to the variable, and an assignment statement for updating the value of the control variable in the program, Rewriting the created assignment statement and rewriting the arithmetic expression at the location detected by the in-loop arithmetic expression detection step to the variable created by the variable creating step, the in-loop arithmetic expression rewriting step and the out-of-loop arithmetic expression detecting step can be rewritten. A program conversion method for rewriting an arithmetic expression at a location detected by the out-of-loop arithmetic expression detection step to a variable created by the variable creating step. .