Program generation device, program production method, and program

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 ith execution (1≦i<N) is referenced by a statement in the block pertaining to a jth 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 jth execution is identical to a representation of a variable showing an operation result of a statement in the block pertaining to the ith 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 ith 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 jth 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.

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 ith execution (1≦i<N) is referenced by a statement in the block pertaining to a jth 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 jth execution is identical to a representation of a variable showing an operation result of a statement in the block pertaining to the ith 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 ith 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 jth 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.