Program generation device, program production method, and program

1. A program generation apparatus for generating a program by referencing a source program including a loop for executing a block comprising one or more statements N times (N≧2), the source program having such dependence that a variable defined in a statement in the block pertaining to an i th execution (1≦i<N) is referenced by a statement in the block pertaining to a j th execution (i<j≦N), the program generation apparatus comprising:

a loop expansion unit configured to expand the loop to generate statements in the block;

a name dependence removal unit configured to remove name dependencies between consecutive iterations expanded by the loop expansion unit;

a calculation unit configured to generate an equality expression set that is a set of equivalent relation information pieces each indicating equivalent variables or expressions included in each of the statements, wherein equivalent relation information pieces are calculated between representations of variables with respect to statements in consecutive iterations from which name dependence has been removed by the name dependence removal unit;

a specification unit configured to, when a representation of a variable used in an operation target of a statement in the block pertaining to the j th execution is identical to a representation of a variable showing an operation result of a statement in the block pertaining to the i th execution, specify a variable that is equivalent to the variable showing the operation result and is not used as any variable showing an operation result in the block pertaining to the i th execution based on the equivalent relation information pieces; and

a generation unit operable to generate a program that is for executing the block M times (M≦N) and includes a modified statement in which the representation of the variable used in the operation target of the statement in the block pertaining to the j th execution is replaced by a representation of the variable specified by the specification unit to create the modified statement from a previous statement, such that the generated program does not have the dependence.

2. The program generation apparatus of claim 1 , wherein a representation of the variable specified by the specification unit is different from any representation of the variable used in the operation target of the statement in the block pertaining to the j th execution.

3. The program generation apparatus of claim 2 , wherein

until the specification unit specifies the representation of the variable not causing the dependence that is equivalent to the representation of the variable used in the operation target of the statement in the block pertaining to the j th execution, the calculation unit repeatedly increments the value of i by one and generates the equality expression set.

4. The program generation apparatus of claim 2 , wherein

the source program is to be executed by a single processor, and

the program generated by the generation unit is to be executed in parallel by a plurality of processors.

5. The program generation apparatus of claim 2 , wherein

when M<N is satisfied, the generation unit modifies the generated program so that the program after the modification is for executing the block N−M times in addition to the M times, and judges whether processing of the program after the modification is equivalent to processing of the source program, and

when judging affirmatively, the generation unit replaces the program before the modification with the program after the modification.

6. A program generation method used in a program generation apparatus for generating a program by referencing a source program including a loop for executing a block comprising one or more statements N times (N≧2), the source program having such dependence that a variable defined in a statement in the block pertaining to an i th execution (1≦i<N) is referenced by a statement in the block pertaining to a j th execution (i<j≦N), the program generation apparatus including a calculation unit, a specification unit and a generation unit, the program generation method comprising the steps of:

expanding the loop to generate statements in the block;

removing name dependencies between consecutive iterations expanded by the expanding of the loop;

generating, using the calculation unit, an equality expression set that is a set of equivalent relation information pieces each indicating equivalent variables or expressions included in each of the statements, wherein equivalent relation information pieces are calculated between representations of variables with respect to statements in consecutive iterations from which name dependence has been removed;

specifying, using the specification unit, when a representation of a variable used in an operation target of a statement in the block pertaining to the j th execution is identical to a representation of a variable showing an operation result of a statement in the block pertaining to the i th execution, a variable that is equivalent to the variable showing the operation result and is not used as any variable showing an operation result in the block pertaining to the i th execution based on the equivalent relation information pieces; and

generating, using the generation unit, a program that is for executing the block M times (M≦N) and includes a modified statement in which the representation of the variable used in the operation target of the statement in the block pertaining to the j th execution is replaced by a representation of the variable specified by said specifying of the variable to create the modified statement from a previous statement, such that the generated program does not have the dependence.

7. A non-transitory computer-readable recording medium having a program recorded thereon, the program for causing a processor in a program generation apparatus to perform a program generation processing method, the program generation apparatus being for generating a program by referencing a source program including a loop for executing a block comprising one or more statements N times (N≧2), the source program having such dependence that a variable defined in a statement in the block pertaining to an i th execution (1≦i<N) is referenced by a statement in the block pertaining to a j th execution (i<j≦N), the program generation processing method comprising the steps of:

expanding the loop to generate statements in the block;

removing name dependencies between consecutive iterations expanded by the expanding of the loop;

generating an equality expression set that is a set of equivalent relation information pieces each indicating equivalent variables or expressions included in each of the statements, wherein equivalent relation information pieces are calculated between representations of variables with respect to statements in consecutive iterations from which name dependence has been removed;

specifying, when a representation of a variable used in an operation target of a statement in the block pertaining to the j th execution is identical to a representation of a variable showing an operation result of a statement in the block pertaining to the i th execution, a variable that is equivalent to the variable showing the operation result and is not used as any variable showing an operation result in the block pertaining to the i th execution based on the equivalent relation information pieces; and

generating a program that is for executing the block M times (M≦N) and includes a modified statement in which the representation of the variable used in the operation target of the statement in the block pertaining to the j th execution is replaced by a representation of the variable specified by said specifying of the variable to create the modified statement from a previous statement, such that the generated program does not have the dependence.