Patent ID: 8806466

Claim:
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.