JP3922699B2 - Optimization method and program for moving invariant expressions in loop - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an optimization method of a compiler, and particularly calculates an operation that cannot move as an invariant expression in a loop because a variable used in the operation selectively uses an invariant value in the loop. It relates to optimization that transforms as much as possible.
[0002]
[Prior art]
In general, as shown in the compiler 100 of FIG. 11, the compiler inputs a source program 200 described in a high-level language, and performs a lexical analysis, a syntax analysis, a semantic analysis, etc. by a syntax analysis unit 101 to generate an intermediate text 104. Next, the optimization unit 102 generates the intermediate text 105 obtained by performing the optimization process on the intermediate text 104, and then the code generation unit 103 generates the machine language instruction object program 300 from the intermediate text 105 and outputs it. To do. Various optimizations are performed by the optimization unit 102. One of them is to perform useless calculation by moving the invariant expression in the loop existing in the repeatedly executed part (that is, the loop) to the outside of the loop. There is an optimization process that eliminates repetition. Here, the invariant expression in the loop means an operation in which the calculation result is always constant regardless of the number of executions of the loop. The present invention relates to the optimization of such in-loop invariants.
[0003]
Conventionally, optimization of an invariant expression in this kind of loop is performed by detecting an invariant expression in a trivial loop, as shown in Japanese Patent Laid-Open No. 5-189244, and then converting those invariant expressions. Investigate whether the expression used is immutable. For this reason, optimization of movement out of the loop is performed only when the result of the operation has an invariant value in the loop, and variables with invariant values in the loop are selectively defined at multiple locations. In the case of an operation that refers to the variable, such an operation is determined not to be an invariant expression in the loop, and is not subject to optimization.
[0004]
[Problems to be solved by the invention]
However, when an operation refers to a variable that has an invariant value defined in the loop selectively at multiple locations in the loop, the location where the variable is actually defined is different even if it is a different iteration. If they are the same, the result is the same. That is, an operation that obtains the same result is executed many times in the repetition of the loop, and the execution time is long.
[0005]
OBJECT OF THE INVENTION
The object of the present invention is that in a certain operation, even if a variable referred to in the operation is selectively defined as an invariable value in the loop at a plurality of locations in the loop, the invariable value is not changed in the loop. The purpose is to make it possible to modify the program so that as many operations as possible can be moved out of the loop.
[0006]
[Means for Solving the Problems]
According to a first aspect of the present invention, there is provided a syntax analysis unit that reads and analyzes a source program stored in a first storage unit and stores the generated first intermediate text in a second storage unit, and the second storage unit A second intermediate text obtained by performing optimization processing on the first intermediate text read from the first intermediate text is generated and stored in the second storage means; and the second intermediate text read from the second storage means An object code is generated from the intermediate text of 2 and stored in a third storage means, and
The optimization unit reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in a loop, and obtains the processing result as the second intermediate text. In-loop invariant detection means for storing in the storage means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation Including
Since the variable used in the calculation selectively uses an invariant value in the loop, it is modified so that an operation that cannot be moved as an invariant expression in the loop can be calculated outside the loop.
[0007]
According to a second aspect of the present invention, there is provided a syntax analysis unit that reads and analyzes the source program stored in the first storage unit, and stores the generated first intermediate text in the second storage unit, and the second storage unit A second intermediate text obtained by performing optimization processing on the first intermediate text read from the first intermediate text is generated and stored in the second storage means; and the second intermediate text read from the second storage means An object code is generated from the intermediate text of 2 and stored in a third storage means, and
The optimization unit includes:
A loop that reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in the loop, and stores the processing result in the second storage means Inner invariant detection means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text, the processing result of the in-loop invariant detecting means and the processing result of the primary copyable arithmetic detecting means are read out from the second storage means, and all the variables used for the calculation are The primary copyable calculation detected by the primary copyable calculation detection means, and any of the primary copyable calculations is the same. The variable to which the result is assigned is defined only in one place and is always executed prior to this operation. The second copyable operation is detected, and the processing result is stored in the second storage means. A second copyable operation detection means stored in
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation ,
The processing result of the second copyable calculation detecting means and the first intermediate text after rewriting by the first copyable calculation detecting means are inputted from the second storage means, and the second copy is possible Each of the variables defined at multiple locations in the loop used in the operation of the primary copyable operation used in the operation, for the second copyable operation detected by the operation detection means Immediately after the primary copyable operation copied immediately after the definition of the variable, the second copyable operation is copied, and the variables defined at a plurality of locations cited in the copied operation are copied. A variable that temporarily replaces the temporary variable used in the primary copyable operation, sets the newly created variable to be temporarily used as the result of the copied operation, and temporarily uses the original secondary copyable operation To the result of the second copyable operation. And a second copy available computing copying means for replacing the assignment to variables that hold,
Since the variable used in the calculation selectively uses an invariant value in the loop, it is modified so that an operation that cannot be moved as an invariant expression in the loop can be calculated outside the loop.
[0009]
[Action]
In the first invention, the invariant detecting means in the loop detects the variable whose value is invariant in the loop and the operation whose result is invariant. All of the variables used are immutable in the loop, or are defined in multiple places in the loop, but one of them is always executed prior to this operation, and all of them are values that are immutable in the loop The primary copyable operation is detected which is one of the assigned variables. Then, the primary copyable operation copying means is defined at a plurality of locations in the loop used in the operation with respect to the primary copyable operation detected by the primary copyable operation detection means. The primary copyable operation is copied immediately after the definition of each variable, and the newly created variable to be used temporarily is used as the result of the copied operation. The variable used in the above is replaced with an assignment to the variable holding the result of the first copyable operation. Thus, the primary copyable operation copied under each condition can be treated as an invariant expression in the loop, and the execution time of the loop can be shortened by moving out of the loop.
[0010]
In the second invention, in addition to the first invention, the second copyable calculation detection means determines whether all of the variables used in the calculation are invariant in the loop or whether the first primary It is either the result of the primary copyable operation detected by the copyable operation detection means, and the variable to which the result of any primary copyable operation is assigned is defined only in one place And a secondary copyable operation that is always executed prior to this operation is detected and detected by the secondary copyable operation detection means by the secondary copyable operation copy means. For the secondary copyable operation, the primary copyable operation used in the operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation. The secondary copy is possible immediately after the primary copyable operation. Copy the calculation, replace the variable defined in multiple places cited in the copied operation with the temporary variable used in the above primary copyable operation, and create a new one to be used temporarily The variable is used as the result of the copied operation, and the original second copyable operation is replaced with a variable that temporarily uses the second copyable operation and substituted with the variable that holds the second copyable operation result. As a result, in addition to the primary copyable operation copied under each condition, the secondary copyable operation can also be treated as an invariant expression in the loop. Can be made shorter.
[0012]
First Embodiment of the Invention
Next, a first embodiment of the present invention will be described with reference to the drawings.
[0013]
[Description of configuration]
Referring to FIG. 1, the loop optimization unit 10 of the compiler according to the first embodiment of the present invention includes an in-loop invariant detection means 11, a primary copyable operation detection means 12, and a secondary copyable operation. It includes a detecting means 13, a primary copyable operational copying means 14, a secondary copyable operational copying means 15 and an invariant moving means 16 in the loop, and an intermediate text 21 is inputted and an intermediate text 22 optimized for it is obtained. Output. The intermediate text 21 corresponds to the intermediate text 104 in FIG. 11, the intermediate text 22 corresponds to the intermediate text 105 in FIG. 11, and the loop optimization unit 10 corresponds to the optimization unit 102 in FIG.
[0014]
The in-loop invariant detection means 11 receives the intermediate text 21, searches for and records a variable whose value is invariant in the loop and an operation whose operation result is invariant in the loop.
[0015]
The primary copyable calculation detecting means 12 inputs the intermediate text 21 and the above-mentioned record of the in-loop invariant detecting means 11 and determines whether all of the variables used for the calculation are invariant in the loop. A primary copy that is defined in multiple places, but any one of them is always executed prior to this operation, and any of them is a variable that is assigned an invariant value in the loop Detect possible operations and record them.
[0016]
The secondary copyable calculation detection means 13 receives the intermediate text 21, the in-loop invariant detection means 11 and the records of the primary copyable calculation detection means 12, and all the variables used for the calculation are in the loop. Or the result of the primary copyable operation detected by the primary copyable operation detection means 12, and any primary copyable operation substitutes the result Detects and records secondary copyable operations that are defined only at one location and are always executed prior to this operation.
[0017]
The primary copyable operation copying means 14 receives the intermediate text 21 and the above-mentioned records of the primary copyable operation detection means 12 and detects the primary copyable operation detected by the primary copyable operation detection means 12. In contrast, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. As a result of the operation, the original primary copyable operation is replaced with a variable that temporarily uses the primary copyable operation, and the replacement intermediate text is recorded. To do.
[0018]
The secondary copyable operation copying means 15 inputs the above-mentioned record of the secondary copyable operation detection means 13 and the intermediate text after the replacement by the primary copyable operation copy means 14, and obtains a secondary copyable operation copy. Each of the variables defined at a plurality of locations in the loop used in the operation of the primary copyable operation used in the operation with respect to the second copyable operation detected by the detecting means 13 Immediately after the primary copyable operation copied immediately after the definition of the above, the above secondary copyable operation is copied, and the variables defined in a plurality of places cited in the copied operation are A variable that temporarily replaces a temporary variable used in the primary copyable operation and that uses the newly created variable that is temporarily used as the result of the copied operation and temporarily uses the original secondary copyable operation. To the above secondary copyable operation Replaced with the assignment of the result to a variable to hold the records the intermediate text after the replacement.
[0019]
The in-loop invariant moving means 16 receives the intermediate text after the replacement by the secondary copyable operation copying means 15 and moves the in-loop invariant existing in the inputted intermediate text out of the loop for optimization. The intermediate text 22 is output.
[0020]
[Description of operation]
Next, the operation of the loop optimization unit 10 of the present exemplary embodiment will be described in detail with reference to FIGS.
[0021]
The in-loop invariant detection means 11 searches the intermediate text 21 for each loop, detects a variable whose value is invariant in the loop and an operation whose result is invariant and records it (step A1 in FIG. 2). For example, in the case of an actual Fortran program piece as shown in FIG. 3, the variables I1, I2, and S are recorded as invariant in the loop.
[0022]
Next, the primary copyable operation detection means 12 determines whether all of the variables used in the operation are invariant in the loop or are defined in a plurality of locations in the loop, but any one of them is necessarily this operation. The first copyable operation is detected, which is one of the variables that are executed prior to and any of which is a variable to which an invariant value is assigned in the loop (step A2 in FIG. 2). For example, in the case of an actual Fortran program fragment as shown in Fig. 3, in the operation IX * S of (3), S is invariant in the loop, and IX is defined in two places (1) and (2). , (1) and I2 in (2) are both substituted with invariable variables in the loop, and are recognized as primary copyable operations.
[0023]
In the above, if there is no detected operation, the processing in FIG. 2 ends. If there is even one, it proceeds to the next step A4 (step A3 in FIG. 2).
[0024]
Next, the secondary copyable calculation detecting means 13 determines whether all of the variables used for the calculation are invariable in the loop or the result of the primary copyable calculation detected in step A2. Any one of the primary copyable operations, the variable to which the result is assigned is defined in only one place and must be executed prior to this operation. An operation search is performed (step A4 in FIG. 2). For example, in the case of an actual Fortran program piece as shown in FIG. 3, in the operation T + S of (4), S is invariant in the loop, and T is the operation of the primary copyable operation ((3) of FIG. 3). As a result, it is recognized as a secondary copyable operation.
[0025]
Next, the primary copyable operation copying means 14 immediately after the definition of each of the variables defined at a plurality of locations in the loop used in the operation for the primary copyable operation searched in step A2. The newly created variable that is temporarily used for copying is used as the result of the copied operation, and the result of the primary copyable operation is obtained from the variable that temporarily uses the original primary copyable operation. Replace with the variable to be held (step A5 in FIG. 2). For example, FIG. 4 shows a case where this copying is performed on an actual Fortran program piece as shown in FIG. The operation IX * S of (3) in FIG. 3 which is the first copyable operation is copied immediately after (1) and (2) of FIG. 3, and the variable defined by the operation is newly generated variable T1. It is changed ((5) and (6) in FIG. 4). Also, the operation IX * S in (3) of FIG. 3 is replaced with the newly generated variable T1 ((7) in FIG. 4).
[0026]
If there is no detected operation in the secondary copyable operation detecting means (step A4 in FIG. 2), the processing in FIG. 2 ends. If there is even one, it proceeds to the next step A7 (step A6 in FIG. 2).
[0027]
Next, the secondary copyable operation copying means 15 performs the operation of the primary copyable operation used in the operation in the loop used in the operation for the secondary copyable operation searched in step A4. Immediately after the primary copyable operation copied immediately after the definition of each of the variables defined in multiple places, the second copyable operation is copied, and a plurality of references cited in the copied operation are made. Replace the variable defined in the location with the temporary variable used in the above primary copyable operation, and use the newly created variable that is temporarily used as the result of the copied operation. The variable that temporarily uses the copyable operation is replaced with an assignment to the variable that holds the result of the second copyable operation (step A7 in FIG. 2). For example, FIG. 5 shows a case where this copying is performed for an actual Fortran program piece as shown in FIG. The operation T + S of (4) in FIG. 3 which is a secondary copyable operation is copied immediately after (5) and (6) of FIG. 4, and T which is the result of the primary copyable operation is a step. The variable is changed to the new variable T1 generated in A3, and the variable defined by the operation is changed to the newly generated variable T2 ((8) and (9) in FIG. 5). Also, the operation T + S in (4) of FIG. 3 is replaced with the newly generated variable T2 ((10) in FIG. 5).
[0028]
The program piece changed as shown in FIG. 5 is transformed as shown in FIG. 6 by the in-loop invariant moving means 16 for optimizing the in-loop invariant movement according to the prior art. The number of execution instructions is reduced and the execution time is shortened.
[0029]
Second Embodiment of the Invention
Next, a second embodiment of the present invention will be described in detail with reference to the drawings.
[0030]
In the first embodiment, the variables to be referred to in the calculation are only variables defined by the primary copyable calculation in the secondary copyable calculation detection means 13 or invariable variables in the loop. The variable (T) defined in the primary copyable operation, such as T + U in (6), and any definition that is defined in multiple locations is executed prior to this operation, and in any definition The present invention can be applied by combining the primary copyable operation copying means 14 and the secondary copyable operation copying means 15 even when a variable (U) into which an invariant value is substituted is mixed in the loop. It is.
[0031]
In the above case, a variable (a U in FIG. 7 (6)) that is defined in a plurality of places and any of the definitions is executed prior to this operation and in each definition is assigned an invariant value in the loop. As for the first copyable operation copying means 14 (step A5 in FIG. 2), the operation is performed immediately after the definition of each of the variables defined at a plurality of locations in the loop used in the operation. The newly created variable that is copied and used temporarily is used as the result of the copied operation, and the original operation is replaced with a variable that temporarily stores the result of the operation. For example, FIG. 8 shows a case where this copying is performed on an actual Fortran program piece as shown in FIG. It is assumed that (7), (10), and (13) in FIG. The operation T + U of (6) in FIG. 7 which is the second copyable operation is copied immediately after (2) and (4) of FIG. 7, and T which is the result of the first copyable operation is a step. The variable is changed to the new variable T1 generated in A3, and the variable defined by the operation is changed to the newly generated variable T2 ((9) and (12) in FIG. 8).
[0032]
Next, with respect to variables defined in the primary copyable operation (T in FIG. 7 (6)), the calculation is performed for the secondary copyable operation (T + U in (6) in FIG. 7). Immediately after the primary duplicatable operation copied immediately after the definition of each of the variables defined in multiple places in the loop used in the operation of the primary duplicatable operation used Copy the second copyable operation, replace the variables defined in multiple places cited in the copied operation with the temporary variables used in the first copyable operation, and temporarily The newly created variable to be used is the result of the copied operation, and the original second copyable operation is replaced with a variable that temporarily uses the second copyable operation and assigned to the variable that holds the second copyable operation result. . For example, FIG. 8 shows a case where this copying is performed on an actual Fortran program piece as shown in FIG. It is assumed that (7), (10), and (13) in FIG. The operation T + U of (6) in FIG. 7 which is the second copyable operation is copied immediately after (7) and (10) of FIG. 8, and T is changed to the new variable T1 generated in step A3. Then, the variable defined by the operation is changed to a newly generated variable T2 ((8) and (11) in FIG. 8). Then, the second copyable operation (T + U in (6) of FIG. 7) is replaced with the newly generated variable T2 ((14) of FIG. 8).
[0033]
The program piece changed as shown in FIG. 8 is transformed as shown in FIG. 9 by the in-loop invariant moving means 16 for optimizing the in-loop invariant movement according to the prior art. The number of execution instructions is reduced and the execution time is shortened.
[0034]
Other Embodiments of the Invention
FIG. 10 is a block diagram illustrating a configuration example of a computer that implements the present invention. The computer in this example includes an external storage device 201 that stores a source program 200 written in a high-level language, an external storage device 301 that stores an object program 300 of generated machine language instructions, and a source program from the external storage device 201. 200, and the input / output unit 31 that outputs the object program 300 to the external storage device 301, the intermediate text 21 obtained by processing the source program 200 by the syntax analysis unit, and the intermediate text 21 obtained by optimizing the intermediate text 21 A computer-readable recording medium such as a memory 33 having a work area 32 for storing intermediate text 22 and temporarily storing various information obtained in the course of optimization processing, and a magnetic disk device for storing a compiling program 34 35, input / output unit 31, memory 33 and computer Consisting of being connected to the recording medium 35 and the central processing unit 36.
[0035]
The compiling program 34 recorded on the computer-readable recording medium 35 is read by the central processing unit 36, and the operation of the compiling program 34 is controlled to optimize the loop according to the first and second embodiments described above. It functions as a compiler having the unit 10. At this time, in the work area 32 of the memory 33, information transferred between each means in the loop optimization unit 10 is temporarily stored. For example, in the first embodiment, the in-loop invariant detection means 11 searches the work area 32 by searching for a variable whose value is invariant in the loop and an operation whose operation result is invariant in the loop. Record. When detecting the primary copyable calculation, the primary copyable calculation detecting means 12 refers to the work area 32 to recognize a variable that is invariant in the loop, and detects the detected primary copy. The calculation is recorded in the work area 32. When detecting the secondary copyable calculation, the secondary copyable calculation detecting means 13 refers to the work area 32 and recognizes a variable that is invariant in the loop, the detected primary copyable calculation, and the like. Then, the detected secondary copyable operation is recorded in the work area. The primary copyable operation copying means 14 recognizes the primary copyable operation detected by the primary copyable operation detection means 12 with reference to the work area 32, and deforms the intermediate text 21. The intermediate text as shown in FIG. 4 is recorded in the work area 32. The secondary copyable operation copying unit 15 refers to the work area 32 and the secondary copyable operation detected by the secondary copyable operation detection unit 13 and the processing result of the primary copyable operation copy unit 14. 5 and the like, and an intermediate process as shown in FIG. The invariant moving means 16 in the loop inputs the intermediate text as shown in FIG. 5 recorded in the work area 32, performs an optimization process relating to the movement of the invariant expression in the loop, and stores the result as the intermediate text 22 in the memory. 33. Similarly in the second embodiment, in-loop invariant detection means 11, primary copyable calculation detection means 12, secondary copyable calculation detection means 13, primary copyable calculation copy means 14, Necessary data is transferred through the work area 32 between the secondary copy enabling operation copying means 15 and the in-loop invariant moving means 16.
[0036]
【The invention's effect】
As described above, according to the present invention, even an operation that is not invariant in a loop can be transformed into an invariant expression in a loop when a predetermined condition is satisfied. For this reason, the optimization of the movement of the invariant expression in the loop can be performed for more operations, and the execution time can be greatly shortened by reducing the number of instructions executed in the loop.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a first embodiment of the present invention.
FIG. 2 is a flowchart illustrating a processing example of the first exemplary embodiment of the present invention.
FIG. 3 is a Fortran program fragment to which the first embodiment of the present invention can be applied.
FIG. 4 is a Fortran program fragment representing an intermediate text image after application of the primary copyable operation copying means in the first embodiment of the present invention.
FIG. 5 is a Fortran program fragment representing an intermediate text image after application of the secondary copyable operation copying means in the first embodiment of the present invention.
FIG. 6 is a Fortran program fragment representing an image of intermediate text after applying the in-loop invariant moving means in the first embodiment of the present invention.
FIG. 7 is a Fortran program fragment to which the second embodiment of the present invention can be applied.
FIG. 8 is a Fortran program fragment representing an intermediate text image after applying the first copyable operation copy means and the second copyable operation copy means in the second embodiment of the present invention.
FIG. 9 is a Fortran program fragment representing an intermediate text image after applying the in-loop invariant moving means in the second embodiment of the present invention.
FIG. 10 is a block diagram illustrating a configuration example of a computer to which the present invention is applied.
FIG. 11 is a block diagram illustrating a general configuration of a compiler.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 10 Loop optimization part 11 In-loop invariant detection means 12 Primary copyable calculation detection means 13 Secondary copyable calculation detection means 14 Primary copyable calculation copy means 15 Secondary copyable calculation copy means 16 Loop Inner invariant moving means 21 Intermediate text 22 Intermediate text

Claims (4)

A source program stored in the first storage means is read and analyzed, a syntax analysis unit that stores the generated first intermediate text in the second storage means, and a first read out from the second storage means An optimization unit that generates a second intermediate text obtained by performing an optimization process on the intermediate text and stores the second intermediate text in the second storage unit; and an object from the second intermediate text read from the second storage unit A code generation unit that generates a code and stores the code in a third storage unit; and
The optimization unit reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in a loop, and obtains the processing result as the second intermediate text. In-loop invariant detection means for storing in the storage means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation Including
In a loop that is modified so that an operation that cannot be moved as an invariant expression in the loop because the variable used in the operation selectively uses an invariant value in the loop can be calculated outside the loop Optimization method for moving invariant expressions. A source program stored in the first storage means is read and analyzed, a syntax analysis unit that stores the generated first intermediate text in the second storage means, and a first read out from the second storage means An optimization unit that generates a second intermediate text obtained by performing an optimization process on the intermediate text and stores the second intermediate text in the second storage unit; and an object from the second intermediate text read from the second storage unit A code generation unit that generates a code and stores the code in a third storage unit; and
The optimization unit includes:
A loop that reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in the loop, and stores the processing result in the second storage means Inner invariant detection means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text, the processing result of the in-loop invariant detecting means and the processing result of the primary copyable arithmetic detecting means are read out from the second storage means, and all the variables used for the calculation are The primary copyable calculation detected by the primary copyable calculation detection means, and any of the primary copyable calculations is the same. The variable to which the result is assigned is defined only in one place and is always executed prior to this operation. The second copyable operation is detected, and the processing result is stored in the second storage means. A second copyable operation detection means stored in
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation ,
The processing result of the second copyable calculation detecting means and the first intermediate text after rewriting by the first copyable calculation detecting means are inputted from the second storage means, and the second copy is possible Each of the variables defined at multiple locations in the loop used in the operation of the primary copyable operation used in the operation, for the second copyable operation detected by the operation detection means Immediately after the primary copyable operation copied immediately after the definition of the variable, the second copyable operation is copied, and the variables defined at a plurality of locations cited in the copied operation are copied. A variable that temporarily replaces the temporary variable used in the primary copyable operation, sets the newly created variable to be temporarily used as the result of the copied operation, and temporarily uses the original secondary copyable operation To the result of the second copyable operation. And a second copy available computing copying means for replacing the assignment to variables that hold,
In a loop that is modified so that an operation that cannot be moved as an invariant expression in the loop because the variable used in the operation selectively uses an invariant value in the loop can be calculated outside the loop Optimization method for moving invariant expressions. Computer
A syntax analysis unit that reads and analyzes the source program stored in the first storage unit, and stores the generated first intermediate text in the second storage unit;
An optimization unit that generates a second intermediate text obtained by performing an optimization process on the first intermediate text read from the second storage unit, and stores the second intermediate text in the second storage unit;
A loop that reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in the loop, and stores the processing result in the second storage means Inner invariant detection means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation Optimization part, including
A code generation unit for generating an object code from the second intermediate text read from the second storage unit and storing the object code in a third storage unit;
This is a program that can be used as an invariant expression in a loop because a variable used in the operation selectively uses an invariant value in the loop. A program characterized by being transformed into Computer
A syntax analysis unit that reads and analyzes the source program stored in the first storage unit, and stores the generated first intermediate text in the second storage unit;
An optimization unit that generates a second intermediate text obtained by performing an optimization process on the first intermediate text read from the second storage unit, and stores the second intermediate text in the second storage unit;
A loop that reads the first intermediate text from the second storage means, detects a variable whose value is invariant and an operation whose result is invariant in the loop, and stores the processing result in the second storage means Inner invariant detection means;
The first intermediate text and the processing result of the in-loop invariant detecting means are read from the second storage means, and all the variables used for the operation are invariant in the loop, or a plurality of variables in the loop Primary copyable, defined in places but any one of which is always executed prior to this operation and any of which is a variable that is assigned an invariant value in the loop A primary copyable calculation detecting means for detecting a calculation and storing the processing result in the second storage means;
The first intermediate text, the processing result of the in-loop invariant detecting means and the processing result of the primary copyable arithmetic detecting means are read out from the second storage means, and all the variables used for the calculation are The primary copyable calculation detected by the primary copyable calculation detection means, and any of the primary copyable calculations is the same. The variable to which the result is assigned is defined only in one place and is always executed prior to this operation. The second copyable operation is detected, and the processing result is stored in the second storage means. A second copyable operation detection means stored in
The first intermediate text and the processing result of the primary copyable calculation detection means are read from the second storage means, and the first copyable calculation detected by the primary copyable calculation detection means is used. On the other hand, the primary copyable operation is copied immediately after the definition of each variable defined in multiple places in the loop used in the operation, and the newly created variable that is temporarily used is copied. A primary copyable operation copying means for replacing the original primary copyable operation with a variable that temporarily retains the result of the primary copyable operation as a result of the operation ,
The processing result of the second copyable calculation detecting means and the first intermediate text after rewriting by the first copyable calculation detecting means are inputted from the second storage means, and the second copy is possible Each of the variables defined at multiple locations in the loop used in the operation of the primary copyable operation used in the operation, for the second copyable operation detected by the operation detection means Immediately after the primary copyable operation copied immediately after the definition of the variable, the second copyable operation is copied, and the variables defined at a plurality of locations cited in the copied operation are copied. A variable that temporarily replaces the temporary variable used in the primary copyable operation, sets the newly created variable to be temporarily used as the result of the copied operation, and temporarily uses the original secondary copyable operation To the result of the second copyable operation. Optimization unit and a secondary copiable operation copying means for replacing the assignment to variables that hold,
A code generation unit for generating an object code from the second intermediate text read from the second storage unit and storing the object code in a third storage unit;
This is a program that can be used as an invariant expression in a loop because a variable used in the operation selectively uses an invariant value in the loop. A program characterized by being transformed into

Images