JP3327634B2 - 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 device 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. It is.

[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.

The above-mentioned induction variable is, for example, “Compiler II”
As described in (AV Eiho R. Cessy JD Ullman, Translated by Kenichi Harada: Science), in loop processing, a variable whose value increases by a certain amount of positive or negative each time one loop is repeated The optimization means that, for example, when an induction variable that obtains a value by multiplying a control variable of a loop process by a predetermined number is used in the source code, the value of the induction variable in the previous loop processing is The purpose is to improve the processing speed and reduce the code size by, for example, generating a code that adds a predetermined number to obtain a new value.

More specifically, for example, in the code shown in FIG. 4A, the variables a and b in the loop processing from the label L to the if statement have a value of 2 for each loop processing.
4 or (b)
, The two multiplications can be replaced with two short additions of processing time.

Similarly, in the code shown in FIG. 5A, the number of multiplications can be reduced by converting the induction variables c, d, and e into codes as shown in FIG. 5B. Can be. The above-described optimization of the induced variable in the compiler or the like is performed in detail, for example, as follows.

First, in a syntax analysis of a source code, an induced variable is detected, and a change amount of the induced variable for each loop is obtained. Next, a code for obtaining the value of the induction variable for each loop by increasing the induction variable by the amount of change (positive or negative value) and a code for setting the initial value of the induction variable are generated, and the source code is converted. I do.

Here, in a conventional compiler or the like,
The above conversion was performed for all the induced variables.

[0008]

However, the above-mentioned conventional compiler or the like may generate a code for obtaining a useless value of an induced variable, or may generate a code for lowering the processing speed. There was a problem that. That is, in the example of FIG.
As a result of performing the above-described conversion on b and b, an expression a = for calculating a value that is not used anywhere (strictly, not used except for obtaining a new value of the induced variable itself)
a + 2 is generated. The expressions a = 0 and a = a + 2 relating to such an induction variable a are unnecessary, resulting in a reduction in processing speed and an increase in code size.

Further, the induced variables that have been optimized as described above are variables that have a high priority assigned to the registers of the processor and that live in a so-called loop process. Therefore, if the conversion to addition is always performed for all the induced variables as in the example of FIG. 5, for example, there is a high possibility that the number of induced variables exceeds the number of registers of the processor. Therefore, the number of codes increases, which tends to increase the code size and decrease the processing speed.

SUMMARY OF THE INVENTION In view of the above, the present invention suppresses generation of a code for obtaining a value of a useless induced variable, reduces the number of variables that live in a loop process, and improves the processing speed and the code. A program conversion method that can reduce the size,
And its equipment.

[0011]

To achieve the above object, the present invention provides a detecting means for detecting an induced variable used in a loop processing of a program code, and a holding means for holding information indicating the detected induced variable. Means and a code for defining a value of a detected induction variable in a program code are converted into a code for defining a value of a new induction variable by adding a predetermined value to the induction variable every time a loop process is performed. And converting the induced variable detected by the detecting means to the value of the one induced variable from the program code when the induced variable is only used to define the value of the one induced variable. And a deleting means for deleting a code defining the value of the induction variable used only for

Further, detecting means for detecting an induced variable used in the loop processing of the program code, holding means for holding information indicating the detected induced variable, and detecting the value of the detected induced variable in the program code. A conversion unit that converts a code to be defined into a code that defines a value of a new induction variable by adding a predetermined value to the induction variable every time a loop process is performed, and a plurality of induction variables detected by the detection unit. Is a derived variable whose value is defined using the same other induced variable, characterized in that it has a conversion suppressing unit that suppresses code conversion by the converting unit for the plurality of induced variables. .

[0013] Further, a detecting step of detecting an induced variable used in the loop processing of the program code, and changing a code defining the value of the detected induced variable in the program code into an induced variable every time the loop processing is performed. A conversion step of adding a predetermined value to convert the code into a code that defines a new induction variable value, and an induction step in which the induction variable detected in the detection step is used only to define the value of one induction variable. If the variable is a variable, a step of deleting a code defining the value of the induced variable used only to define the value of the one induced variable from the program code is provided.

A detecting step for detecting an induced variable used in the loop processing of the program code, and a code for defining a value of the detected induced variable in the program code is changed to an induced variable every time the loop processing is performed. A conversion step of converting to a code that defines a value of a new induction variable by adding a predetermined value; and a plurality of induction variables detected in the detection step, the value of which is defined using the same other induction variable. A conversion suppression step of suppressing execution of the conversion step for the plurality of induction variables.

[0015]

With the above arrangement, the detecting means detects the induced variable used in the loop processing of the program code, the holding means holds information indicating the detected induced variable, and the converting means operates the program code in the program code. The code that defines the value of the detected induction variable is converted to a code that defines a new value of the induction variable by adding a predetermined value to the induction variable every time the loop processing is performed.

[0016] Further, when the induction variable detected by the detection means is an induction variable used only for defining the value of the one induction variable, the deletion means determines the value of the one induction variable from the program code. Remove the code that defines the value of the induction variable that is used only to define Or, when the plurality of induction variables detected by the detection means are induction variables whose values are defined by using the same other induction variables, the conversion suppression means, for the plurality of induction variables, Suppress code conversion.

In the detecting step, an induced variable used in the loop processing of the program code is detected, and in the converting step, a code defining the value of the detected induced variable in the program code is loop-processed. By adding a predetermined value to the induction variable every time, it is converted into a code defining a new induction variable value. Further, when the induced variable detected in the detecting step is the induced variable used only for defining the value of the one induced variable, the value of the one induced variable is defined from the program code. The code that defines the value of the induction variable, which is used only for that purpose, is removed.

Alternatively, when the plurality of induction variables detected in the detection step by the conversion suppression step are induction variables whose values are defined by using the same other induction variables, Execution of the conversion step is suppressed.

[0019]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below with reference to FIGS. FIG. 1 is a block diagram showing the configuration of the 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.

In FIG. 1, code storage means 1 before optimization
Numeral 1 stores a code before optimization such as the above-mentioned source code and intermediate code. The induction variable detection unit 12 detects an induction variable included in the pre-optimization code stored in the pre-optimization code storage unit 11 and registers information on the detected induction variable in an induction variable holding unit 13 described later. Things. More specifically, for example, an induction variable definition statement that defines the value of an induction variable during loop processing in a code before optimization is detected, and a variable name of the induction variable, an increment value for each loop processing, and an initial value are stored as induction variable holding means. 13 is held. Here, the increment value may be a positive value or a negative value. Since the same configuration as that of the conventional program conversion device can be applied to detection of the above-mentioned induction variables, detailed description will be omitted.

The induced variable holding means 13 holds the variable name of the induced variable detected by the induced variable detecting means 12, the increment value for each loop processing, and the initial value. The induction variable optimization control unit 14 includes a definition sentence deleting unit 14a,
And a conversion suppressing means 14b. The definition sentence deleting unit 14a detects, for each of the induction variables registered in the induction variable holding unit 13, a usage sentence in which the value of the induction variable (used induction variable) is used in the code before optimization. When there is only one usage statement and the variable whose value is defined in the usage statement is registered in the induction variable holding means 13, that is, the variable defined using the used induction variable is also an induction variable. If, the definition statement that defines the value of the used induction variable is deleted from the pre-optimization code.
In other words, since the used sentence of the used induced variable is converted into a statement that does not use the used induced variable by the code conversion process described later, the definition sentence of the used induced variable becomes unnecessary, and therefore, should be deleted. Thus, the code size can be reduced and the processing speed can be improved. Since the definition sentence deleting means 14a does not need to perform the code conversion process on the used induced variables,
The registration of the used induction variable is deleted from the induction variable holding unit 13.

On the other hand, the conversion suppression means 14b detects a usage statement in which the value of the used induction variable is used, similarly to the definition statement deletion means 14a, and then detects a plurality of usage statements. In the case where all the variables whose values are defined in are registered in the induced variable holding means 13, that is, when those variables are also induced variables, the registration of the plurality of induced variables is deleted from the induced variable holding means 13. I do. In other words, since the code conversion process described later is not performed on the deleted induction variable, the number of induction variables that have a high priority assigned to the register of the processor and live in a so-called loop process can be reduced. Note that all variables whose values are defined in the above usage statements are all derived variable holding means 13.
Not only in the case where a plurality of variables are registered, but also in a case where at least a plurality of variables are registered, the information may be deleted from the induced variable holding unit 13.

After the process of the induction variable optimization control unit 14 is completed, the code conversion unit 15 sets the variable name of the induction variable registered in the induction variable holding unit 13, the increment value for each loop processing, and the initial value. Based on the value, a definition statement defining the value of the induction variable in the pre-optimization code stored in the pre-optimization code storage means 11 is added to the original induction variable value by adding the increment value to a new value. Generates a code that converts the value of the induction variable into a definition statement that defines the value, and sets the initial value of the induction variable.

The optimized code storage means 16 stores the code obtained by the code conversion means 15. In the above configuration, the operation of the program conversion device is described in FIG.
A description will be given of an example in which induction variables are optimized for the codes shown in FIG. 3A and FIG. 3A. In addition,
In the following description, the description regarding the control variables i and j of the loop processing will be omitted for simplicity. (Example 1) When a code as shown in FIG. 2A is stored in the pre-optimization code storage unit 11, the induction variable detection unit 12 sets the value during the loop processing from the label L to the if statement. Are defined as variables, a and b whose values increase by 2 or 6 for each loop processing are detected as induction variables, and variable names “a, b”, increment values for each loop processing “2, 6”, and The initial value “0, 0” is registered in the induced variable holding unit 13.

The definition sentence deleting means 14a determines that the use sentence in which the value of the induction variable a is used is only b = a * 3,
It is detected that the variable “b” whose value is defined by this usage statement is also registered in the induced variable holding means 13, and as shown in FIG. * I is deleted from the pre-optimization code stored in the pre-optimization code storage means 11. Further, the registration of the induction variable a is deleted from the induction variable holding unit 13.

The code conversion unit 15 performs the processing shown in FIG. 2 based on the variable name “b” registered in the induction variable holding unit 13, the increment value “6” for each loop processing, and the initial value “0”.
As shown in (c), the definition sentence b = a * of the value of the induction variable b
3 is converted to b = b + 6, and a code to which a sentence b = 0 for setting the initial value of the induction variable b is generated, and stored in the code storage unit 16 after optimization. Here, the definition sentence b = b + 6 of the value of the induction variable b is obtained from the label L
The statement b = 0, which is placed at the end of the loop processing up to the statement (after the function f (b) using the value of b) and sets the initial value, is placed before the label L. The conversion is not limited to such code conversion. For example, if the conversion of the algorithm is equivalent, for example, the initial value of the induction variable is set to -6, and the definition statement of the value of the induction variable b is arranged at the front of the loop processing. Good.

The post-optimization code thus obtained includes only one definition variable of the induction variable except the control variable i of the loop processing, and the value of the induction variable is obtained by addition. And the processing speed is improved. (Example 2) When a code as shown in FIG. 3 (a) is stored in the pre-optimization code storage means 11, the induction variable detection means 12 performs the processing from the label L to the if sentence as in the case of Example 1. Variables c, d, and e whose values increase by 2, 6, or 8 for each loop processing
Are registered as the induction variables, and the variable name “c, d, e”, the increment value “2, 6, 8” for each loop processing, and the initial value “0, 0, 0” are registered in the induction variable holding unit 13. I do.

The conversion suppressing means 14b determines that the usage statement in which the value of the induction variable c is used is d = c * 3 and e = c * 4.
Further, it is detected that the variables d and e, the values of which are defined in these usage statements, are both registered in the induced variable holding means 13, and the induced variables d and e are read from the induced variable holding means 13.
Remove registration for. Therefore, code conversion means 1
5 is a variable name “c” registered without being deleted in the induction variable holding means 13, an increment value “2” for each loop processing,
As shown in FIG. 3B, the definition sentence c = 2 * j of the value of the induction variable c is converted into c = c + 2 based on the initial value “0” and the initial value of the induction variable c is set. While the sentence c = 0 is added, the induced variables d and e are stored as they are in the post-optimization code storage unit 16.

The post-optimization code thus obtained, except for the control variable j of the loop processing, contains only one definition statement of the induction variable whose value is obtained by addition. The number of living variables is reduced to one, the possibility of being reliably allocated to the register of the processor is increased, the code size is reduced, and the processing speed is improved.

In the above example, the definition statement deleting means 14
FIG. 4A shows an example in which the definition statement defining the value of the used induction variable is deleted from the pre-optimization code stored in the pre-optimization code storage unit 11. May be deleted, or after the converted code is stored in the post-optimization code storage unit 16.

Further, the definition sentence deleting means 14a has been described as an example in which the use sentence in which the value of the induction variable (used induction variable) is used in the pre-optimization code is described. The usage sentence may be detected for the code after the conversion by the conversion means 15. In this case, if the detected sentence is only a sentence that defines a new value of the used induced variable itself, the sentence may be deleted.

In the description of the operation of the program conversion device, the definition sentence deletion means 14a or the conversion suppression means 14b
An example of the pre-optimization code in which the registration of the induction variable is deleted by only one of the above is shown, but in the case of a code that becomes one processing target and then becomes the other processing target Will result in a more optimized code being generated.

[0033]

As described above, according to the present invention,
If the induction variable is an induction variable used only to define the value of one induction variable, the program code defines the value of the induction variable used only to define the value of the one induction variable. If the code to be executed is deleted, or if the plurality of induction variables are induction variables whose values are defined using the same other induction variables, the code conversion is suppressed for the plurality of induction variables. , Suppresses the generation of code that calculates the value of useless induction variables, or
The number of variables alive in the loop processing is reduced, so that the processing speed is improved and the code size is reduced.

[Brief description of the drawings]

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

FIG. 2 is an explanatory diagram showing examples of program codes before and after conversion by a program conversion device of the present invention.

FIG. 3 is an explanatory diagram showing another example of a program code before and after conversion by the program conversion device of the present invention.

FIG. 4 is an explanatory diagram showing examples of program codes before and after conversion by a conventional program conversion device.

FIG. 5 is an explanatory diagram showing another example of a program code before and after conversion by a conventional program conversion device.

[Explanation of symbols]

 11 Code storage unit before optimization 12 Induction variable detection unit 13 Induction variable holding unit 14 Induction variable optimization control unit 14a Definition sentence deletion unit 14b Conversion suppression unit 15 Code conversion unit 16 Code storage unit after optimization

────────────────────────────────────────────────── ─── Continuation of the front page (56) References Ikuo Nakata, Compiler, Sangyo Tosho Co., Ltd., 1981, p. 221-237 (58) Fields surveyed (Int. Cl. ⁷ , DB name) G06F 9/45

Claims (6)

(57) [Claims] An information processing apparatus detects an induction variable used in a loop processing of a program code, and indicates information indicating the induction variable.
First detecting means for outputting the initial value of the induced variable for each loop, increment value for each loop processing, holding means for holding the output of the detecting means, and holding means for holding the output of the program code . information
The code that defines the value of the induction variable indicated by
Code for setting the initial value in advance, and loop processing
The increment value converting means for converting the code for the value of the new induction variables by adding the value of induction variables, among the detected induction variables in the first detecting means in the middle, the induction of one An induction variable that is used only to define the value of the variable
A program conversion device , comprising: a second detecting means for detecting; and a deleting means for deleting, from a program code, a code defining a value of an induced variable detected by the second detecting means . 2. A detecting means for detecting an induced variable used in a loop processing of a program code, a holding means for holding information indicating the detected induced variable, and a detecting means for detecting a value of the detected induced variable in the program code. A conversion means for converting a code to be defined into a code for defining a value of a new induction variable by adding a predetermined value to the induction variable every time loop processing is performed; and a plurality of induction variables detected by the detection means. Is an induction variable whose value is defined using the same other induction variable,
For the plurality of induction variables, possess the inhibiting transduction inhibitor means the conversion of the code by converting means, said converting suppression means, a plurality of induction detected by the detection means
The variable is defined to be valued using the same other induction variable
In the case of a derived variable, the information indicating the plurality of induced variables is
Characterized in that it is configured to be deleted from the holding means
Program conversion apparatus according to. 3. A program conversion apparatus comprising: the first and second detection means, the holding means, the conversion means, and the deletion means according to claim 1; and the conversion suppression means according to claim 2. 4. An induction variable used in a loop process of a program code is detected, and information indicating the induction variable and an induction variable are detected.
Outputs the initial value of the derived variable and the increment value for each loop processing .
A detection step of the 1, in the program code, a code that defines the value of the detected induction variable by the first detecting means, a loop
Code for setting the initial value in advance, and loop processing
The increment value a conversion step of converting the code that defines the value of the new induction variables by adding the value of induction variables, among the detected induction variables in the first detecting means in the middle, the induction of one An induction variable that is used only to define the value of the variable
A program conversion method comprising: a second detecting step of detecting; and a deleting step of deleting, from the program code, a code defining a value of an induced variable detected by the second detecting means . 5. A detecting step of detecting an induced variable used in a loop processing of a program code, and a code defining a value of the detected induced variable in the program code is converted into an induced variable every time the loop processing is performed. A conversion step of adding a predetermined value to convert to a code that defines a value of a new induction variable; and a plurality of induction variables detected in the detection step are defined with a value using the same other induction variable. when an induction variable that, for the plurality of induction variables, possess the inhibiting transduction inhibitor step execution of the conversion steps, double the conversion suppression step, detected by the detection step
A number of induction variables define values using the same induction variable
If the derived variable is
Information from the detection result of the detection step.
Program conversion method which is characterized in that characterized in that it is made. First 6. The method of claim 4, the second detection step, the conversion step, and a deletion step, the program conversion method characterized by having a conversion suppression step of claim 5.