JP4579425B2 - Information processing device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an information processing apparatus, and more particularly to an information processing apparatus that compiles a source code and generates an object code.
[0002]
[Prior art]
Various methods for optimizing programs have been proposed. For example, there are a method of converting a multiple loop into a single loop and a method of switching indexes.
[0003]
FIG. 7 is a diagram for explaining a method of converting the former multiple loop into a single loop.
In the source program shown in FIG. 7A, in the row number “01”, real type matrices A, B, and C each having “10” in 2 rows and 2 columns are declared.
[0004]
In the line number “02”, a loop for counting up the index J from “1” to “10” is described. This is a loop that ends at the line number “06”. The line number “03” describes a loop for counting up the index I from 1 to 10, and this is a loop ending with the line number “05”. Therefore, this source program has a double loop formed by indexes I and J.
[0005]
In the row number “04”, an operation for storing the value obtained by adding the element (I, J) of the array B and the element (I, J) of the array C for the element (I, J) of the array A is executed. .
For such a double loop, as shown in FIG. 7B, the index I and the index J are combined into an index IJ, which is converted into a single loop that counts up from 1 to 100. Reduce the number of variables to speed up the process.
[0006]
FIG. 8 is a diagram for explaining a method of replacing the latter index.
The source code shown in FIG. 8A is the same as that in FIG. In this example, as shown in FIG. 8B, the inner and outer indexes are interchanged, thereby making the access to the memory continuous and optimizing. That is, since the two-dimensional array is secured in a continuous area on the memory, the index is changed so that access to this area is continuously performed.
[0007]
Although the above example has been described by taking a double loop as an example, the same effect can be obtained by the above-described method even in the case of a multiple loop.
[0008]
[Problems to be solved by the invention]
However, the multi-loop optimization method as described above is conditional on that there is no instruction (branch word) that involves a branch between the outer loop and the inner loop (hereinafter referred to as secondary). Therefore, there is a problem that optimization cannot be performed when a branching word exists in the secondary.
[0009]
The present invention has been made in view of such a point, and an object of the present invention is to provide an information processing apparatus that can optimize even a multiple loop including a branch word in the secondary.
[0010]
[Means for Solving the Problems]
In the present invention, in order to solve the above problem, in an information processing apparatus that compiles source code and generates object code, a double loop having a branch word that is a branch instruction between an outer loop and an inner loop From the source code when the condition is not branching out of the loop, there is no variable or array definition before the branching statement, and there are no multiple branching statements in the loop. Loop detecting means for detecting; true rate calculating code generating means for generating a true rate calculating code which is a source code for calculating the true rate of the branch word; and adding to the source code; a double loop excluding the branch word A copy means for copying the source code of the source code into the source code as a non-branch word loop code, and when the true rate is 100%, Branch code generation means for generating a branch code that branches to the original code and branching to the original double loop that includes the branch language, and for adding the non-branch language loop code to the source code. There is provided an information processing apparatus characterized by having optimization means for converting the information processing apparatus.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram showing a configuration example of an embodiment of the present invention. In this figure, the storage device 1 stores source code to be compiled.
[0013]
The multiple loop detection means 2 detects a multiple loop having a branch word in the secondary from the source code supplied from the storage device 1.
The true rate calculation code generation means 3 generates a true rate calculation code that is a code for calculating the true rate of the branching words included in the multiple loops and adds it to the source code.
[0014]
The copying means 4 copies the multi-loop code excluding the branching word into the source code as a non-branching word loop code.
The branch code generation means 5 generates a branch code that branches to a non-branch word loop code when the truth rate is 100%, and branches to the original multiple loop that includes the branch word otherwise. To the source code.
[0015]
The optimization means 6 optimizes the no-branch word loop code.
Next, the operation of the above embodiment will be described. First, the operation principle of the present invention will be briefly described with reference to FIG. 2 and then the specific operation will be described.
[0016]
FIG. 2A is a diagram illustrating an example of source code to be optimized. In this source code, a real type one-dimensional array C having the number of elements “10” is declared at the line number “01”, and a real type 2 having the number of elements 10 × 10 at the line number “02”. Dimensional arrays A and B are declared.
[0017]
The line number “03” describes a loop that counts up the index I from 1 to 10, and this is a loop that ends at the line number “09”. The line number “05” describes a loop for counting up the index J from 1 to 10, which is a loop ending with the line number “07”. Therefore, this source program has a double loop formed by indexes I and J.
[0018]
In the line number “04”, a determination instruction is described. This is because the line number “05” to the line number “07” are only obtained when the I-th element of the array C is larger than “1”. This is a decision instruction that branches to processing. This is therefore a bifurcation.
[0019]
Here, if the branching condition is always true in all cases, FIG. 2A can be simplified as shown in FIG. In this case, since it is a normal multiple loop that does not include a branch word in the secondary, it can be optimized by any of the methods described above.
[0020]
In the present invention, as described above, it is determined whether or not the branch word existing in the secondary of the multiple loop is true in all cases, and if it is true, the multiple words obtained by excluding the branch word are obtained. The optimized loop is executed, otherwise the original multiple loop (multiple loop including a branch word) is executed.
[0021]
Next, the specific operation of the embodiment shown in FIG. 1 will be described using the source code shown in FIG. 2A as an example.
Now, if the source code shown in FIG. 2A is stored in the storage device 1, and the processing is started with this source code being the target of compilation, the multiple loop detection means 2 can be read from the storage device 1. The source code to be read is read, and a multiple loop having a branch word in the secondary is detected.
[0022]
The true rate calculation code generation means 3 extracts the branch words from the multiple loop that includes the branch words detected by the multiple loop detection means 2 as secondary, and calculates the true rate of the branch words by referring to the change in the index value. The true rate calculation code that is the source code to be generated is generated.
[0023]
An example of the true rate calculation code is shown in line numbers “01” to “05” in FIG. In this example, in line number “01”, variable MASK2 is declared and its initial value is set to “0”.
[0024]
In the line number “02”, a loop for counting up the index I ′ from 1 to 10 is described. This is a loop that ends at the line number “05”.
In the row number “03” between the loops, a truth value for the proposition “the I'th element of the array C is“ 1 ”or less” is stored in the variable MASK1. Therefore, when the I'th element of the array C is larger than “1” (when the branching word indicated by the line number “04” in FIG. 2A is true), this proposition is false. “0” is assigned to MASK1.
[0025]
In the row number “04”, the value of MASK1 is cumulatively added to the variable MASK2. Therefore, when all the propositions of the line number “03” are false (that is, when all the branching words indicated by the line number “04” in FIG. 2A are true), the value of the variable MASK2 is “0”. "
[0026]
Next, the copying unit 4 acquires the target multiple loop and excludes the branch word from the acquired multiple loop. The obtained multi-loop code is copied to the source code as a non-branch word loop code.
[0027]
An example of the no-branch loop code is shown in line numbers “19” to “23” in FIG. In this example, the code in which the branching word with the line number “04” is excluded from the double loop shown in FIG.
[0028]
Next, the branch code generation means 5 branches to a non-branch word loop code if the true rate is 100%, and otherwise branches to the original multiple loop including the branch word. Is generated and added to the source code.
[0029]
An example of the no-branch loop code is shown in line number “07” in FIG. In this example, when the value of the variable MASK2 is “0”, that is, in all cases, the branching word indicated by the line number “04” in FIG. 2A is true, the line number “19” is set. In other cases, the process after the line number “09” is executed. Note that the line numbers “09” to “15” are the original source code, and branch words are included in the secondary. Therefore, when the value of the variable MASK2 is other than “0”, normal processing is executed.
[0030]
Since the branch code generation unit 5 adds a new branch instruction (unconditional branch instruction) to the line number “17”, the processing from the line number “09” to the line number “15” is completed. In this case, the process branches unconditionally to the line number “25”, and the execution of the process after the line number “19” is stopped.
[0031]
The optimization means 6 detects a no-branch loop (a normal multiple loop that does not have a branch phrase in the secondary) included in the source code generated as described above, and this is detected by the method described above. Optimize by either.
[0032]
The compiling unit 7 compiles the source code including the part optimized by the optimization unit 6 to generate an object code, and supplies the object code to the storage device 8 to be stored therein.
[0033]
Next, an outline of the source code generated by the above processing will be described.
FIG. 4 is a diagram schematically showing the flow of processing from line numbers “03” to “09” of the source code shown in FIG. In this figure, white circles “◯” correspond to the codes described in each line, and arrows indicate the flow of processing. As shown in this figure, “# 1” and “# 7” constitute an outer loop, and “# 3” and “# 5” constitute an inner loop. Furthermore, “# 2” is a branching word and branches to “# 3” or “# 6” depending on the result of the determination.
[0034]
FIG. 5 is a diagram schematically showing the flow of processing of the source code shown in FIG. In this figure, a black circle “●” indicates a newly added code. That is, “#A” corresponds to the row numbers “01” to “07” shown in FIG. “#B” corresponds to the line number “17” shown in FIG. “# 1 ′” to “# 7 ′” correspond to the line numbers “19” to “23” shown in FIG. “#C” corresponds to “END” of the row number “25” shown in FIG.
[0035]
When this source code is executed, first, the true rate is calculated from the branch code of “#A”, and when the true rate is “100%”, the process proceeds to “# 1 ′”, otherwise The processes after “# 1” are executed. If the processing after “# 1” is executed, the processing branches to “#C” unconditionally at “#B” and the processing is terminated.
[0036]
Further, when branching to “# 1 ′”, a non-branch word loop (optimized loop) is executed.
According to the above processing, when a multiple loop having a branch word in the secondary exists in the source code, the true rate calculation code for calculating the true rate of the branch word and the source code of the multiple loop excluding the branch word (Unbranched word loop code) and if the true rate is 100%, branch to the unbranched word loop code, otherwise branch to the original multiple loop including the branched word Since it is added to the source code and optimization is performed on the no-branch word loop code, it is possible to optimize the source code including the branch word in the secondary.
[0037]
Finally, an example of processing executed in the embodiment shown in FIG. 1 will be described with reference to FIG.
[S1] The multiplex loop detection means 2 proceeds to step S2 if a multiplex loop is detected from the source code stored in the storage device 1, otherwise returns to step S1 and repeats the same processing. .
[S2] The multiple loop detection means 2 determines whether or not the multiple loop detected in step S1 includes a branch word in the secondary. If the multiple loop includes the branch word, the process proceeds to step S3. Returning to S2, the same processing is repeated.
[S3] The multiplex loop detection means 2 determines whether or not the detected multiplex loop satisfies a condition to be described later. If satisfied, the process proceeds to step S4. Otherwise, the process proceeds to step S1. Go back to and repeat the same process.
[0038]
Here, the conditions for determination are shown below.
(1) There is one branch instruction in the loop.
(2) It is not a branch that jumps out of the loop.
(3) There is no definition for a variable or array before the branch instruction.
(4) The branch instruction exists in the secondary.
[0039]
The reason for imposing such a condition is to prevent the newly generated cost from becoming more expensive than the cost reduced by the loop optimization. For example, in the example of (1), when there are a plurality of branch instructions, it is necessary to obtain the true rate for all branch instructions, and the cost is assumed to exceed the cost reduction by optimization. Because it is done.
[S4] The copying unit 4 obtains a loop excluding the branch word from the source code.
[S5] The copying unit 4 copies the loop (non-branch word loop) excluding the branch word acquired in step S4 to the source code.
[S6] The branch code generation means 5 acquires a branch word from the source code.
[S7] The branch code generation means 5 generates a true rate calculation code and adds it to the source code.
[S8] The branch code generation means 5 generates a branch code and adds it to the source code.
[S9] The information processing apparatus determines whether or not to continue the process. If the process is continued, the process returns to step S1 and repeats the same process as described above. Otherwise, the process proceeds to step S10.
[S10] The optimization means 6 performs an optimization process on the non-branch word loop code.
[0040]
Note that this optimization processing may use any of the two types of optimization processing described with reference to FIG. 7 or FIG.
[S11] The compiling unit 7 compiles the optimized source code and outputs the obtained object code to the storage device 8.
[0041]
According to the above processing, the operation of the embodiment shown in FIG. 1 can be realized.
In the above embodiment, the case of a double loop has been described as an example. Needless to say, the present invention can be applied to a case of a triple loop or more.
[0042]
Finally, the above processing functions can be realized by a computer. In this case, the processing contents of the functions that the information processing apparatus should have are described in a program recorded on a computer-readable recording medium, and the above processing is realized by the computer by executing the program by the computer. Is done. Examples of the computer-readable recording medium include a magnetic recording device and a semiconductor memory. When distributing to the market, store the program on a portable recording medium such as a CD-ROM (Compact Disk Read Only Memory) or floppy disk, or store it in a computer storage device connected via a network. In addition, it can be transferred to another computer through the network. When executed by a computer, the program is stored in a hard disk device or the like in the computer, loaded into the main memory and executed.
[0043]
【The invention's effect】
As described above, according to the present invention, in an information processing apparatus that compiles source code and generates object code, multiple loop detection means for detecting a multiple loop having a branch word in the secondary from the source code, and the true rate of the branch word True rate calculation code generation means for generating and adding to the source code the true rate calculation code that is the source code for calculating the source code, and copying to copy the source code of multiple loops excluding branch language into the source code as non-branch language loop code If the truth rate is 100%, branch to a no-branch loop code, otherwise generate a branch code that branches to the original multiple loop containing the branch phrase and generate the source code Since the branch code generation means to be added and the optimization means for optimizing the no-branch loop code have been provided, It is possible to optimize the multiple loops having the word.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration example of an embodiment of the present invention.
FIG. 2 is a diagram illustrating the operating principle of the present invention.
FIG. 3 is an example of source code obtained when optimization is performed on the source code shown in FIG. 2;
4 is a diagram schematically showing the flow of processing from line numbers “03” to “09” of the source code shown in FIG.
FIG. 5 is a diagram schematically showing the flow of processing of the source code shown in FIG. 3;
6 is a flowchart for explaining an example of processing executed in the embodiment shown in FIG. 1; FIG.
FIG. 7 is a diagram illustrating an optimization method for converting a multiple loop into a single loop.
FIG. 8 is a diagram for explaining an optimization method for switching indexes of multiple loops.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 Storage device 2 Multiple loop detection means 3 True rate calculation code generation means 4 Copying means 5 Branch code generation means 6 Optimization means 7 Compile unit 8 Storage device

Claims (3)

In an information processing apparatus that compiles source code and generates object code,
A double loop having a branch word is a branch instruction between the outer loop and an inner loop, the possible branch word is not a branch outside the loop, that the definitions of branch words previously variable or array does not exist, the loop wherein a detection to Lulu-loop detecting means from the source code if the branch word will be free multiple, satisfies the condition of the inside,
A true rate calculation code generating means for generating a true rate calculation code that is a source code for calculating the true rate of the branching word and adding it to the source code;
And copying means for copying the source code of the double loop excluding the branch words in the source code as unbranched words loop code,
If the true rate is 100%, the branches to unbranched words loop code, the source code to generate a branch code for branching to the original double loop including a branch word in other cases Branch code generation means to be added to,
An optimization means for optimizing the no-branch loop code;
An information processing apparatus comprising: In a computer-readable recording medium recording a program for causing a computer to function to compile source code and generate object code,
Computer
A double loop having a branch word is a branch instruction between the outer loop and an inner loop, the possible branch word is not a branch outside the loop, that the definitions of branch words previously variable or array does not exist, the loop wherein the branch word is not included plurality of detection to Lulu-loop detecting means from the source code if they meet the condition within,
A true rate calculation code generating means for generating a true rate calculation code which is a source code for calculating the true rate of the branch word and adding the true rate calculation code to the source code;
Copying means for copying the source code of the double loop excluding the branch words in the source code as unbranched words loop code,
If the true rate is 100%, the branches to unbranched words loop code, the source code to generate a branch code for branching to the original double loop including a branch word in other cases Branch code generation means to be added to
Optimization means for optimizing the unbranched word loop code;
A computer-readable recording medium storing a program that functions as a computer. In a program that causes a computer to function to compile source code and generate object code,
Computer
A double loop having a branch word is a branch instruction between the outer loop and an inner loop, the possible branch word is not a branch outside the loop, that the definitions of branch words previously variable or array does not exist, the loop detection to Lulu-loop detecting means from the source code if the branch word will be free multiple, satisfies the condition of the inside,
A true rate calculation code generating means for generating a true rate calculation code which is a source code for calculating the true rate of the branch word and adding the true rate calculation code to the source code;
Copying means for copying the source code of the double loop excluding the branch words in the source code as unbranched words loop code,
If the true rate is 100%, the branches to unbranched words loop code, the source code to generate a branch code for branching to the original double loop including a branch word in other cases Branch code generation means to be added to
Optimization means for optimizing the unbranched word loop code;
Program to function as.

Images