Compiler Optimization

Abstract

Provides effective use of architecture-specific instructions. There is provided a compiler including: a target partial program detecting unit for detecting, from among a partial programs of the program to be optimized, a partial program including instructions corresponding to all instructions included in the pattern to be replaced as a partial program to be optimized; an instruction sequence transforming unit for transforming, in the partial program to be optimized, instructions other than those instructions corresponding to instructions included in the pattern to be replaced and those instructions having execution dependencies different from the pattern to be replaced, so that dependencies between instructions included in the partial program to be optimized match the pattern to be replaced; an instruction sequence replacing unit for replacing the partial program to be optimized transformed by the instruction sequence transforming unit with a target instruction sequence determined in accordance with the pattern to be replaced.

1 ) An optimizing compiler detecting a pattern that is to be replaced and includes multiple predetermined instructions in a program to be optimized and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with the pattern to be replaced, comprising:
 a target partial program detecting unit for detecting, from among a partial programs of said program to be optimized, a partial program including instructions corresponding to all instructions included in said pattern to be replaced as a partial program to be optimized;   an instruction sequence transforming unit for transforming, in said partial program to be optimized, instructions other than those instructions corresponding to instructions included in said pattern to be replaced and those instructions having execution dependencies different from said pattern to be replaced, so that dependencies between instructions included in said partial program to be optimized match said pattern to be replaced; and   an instruction sequence replacing unit for replacing said partial program to be optimized transformed by said instruction sequence transforming unit with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       2 ) The compiler according to  claim 1 , wherein said target partial program detecting unit detects each of the partial programs as the partial program to be optimized, if the instructions in the partial program corresponding to all the instructions included in said pattern to be replaced are executed in the order designated by the execution dependencies between the instructions in said pattern to be replaced. 
   
   
       3 ) The compiler according to  claim 2 , wherein in a case where said pattern to be replaced includes loop processing, said target partial program detecting unit detects each of the partial programs as the partial program to be optimized, if the partial program includes in loop processing the instructions corresponding to all the instructions included in said loop processing, and if all the instructions out of the loop processing in the partial program conform to the dependencies determined by said pattern to be replaced. 
   
   
       4 ) The compiler according to  claim 1 , wherein said pattern to be replaced is a dependence graph having as a node each of multiple instructions included in the said pattern to be replaced and having directed edges representing the execution dependencies between multiple instructions, and
 wherein said target partial program detecting unit generates, with respect to each of the partial programs, a dependence graph having as a node each of multiple instructions included in the partial program and having directed edges representing the execution dependencies between multiple instructions, and makes a determination on the basis of the dependence graph and a dependence graph representing said pattern to be replaced as to whether or not the partial program should be detected as the partial program to be optimized.   
   
   
       5 ) The compiler according to  claim 4 , wherein said pattern to be replaced indicate control flows between the instructions,
 wherein the dependence graph of said pattern to be replaced has, with respect to a multiple-branch instruction to hand over control to an external instruction out of said pattern to be replaced in a case where one of multiple conditions is satisfied, a representative edge representative of multiple control flows through which control is handed over from the multiple-branch instruction to the external instruction, and   wherein said target partial program detecting unit determines, with respect to each of multiple partial programs, that the partial program includes the corresponding multiple-branch instruction, if the dependence graph showing control flows of the partial program has an edge corresponding to the representative edge.   
   
   
       6 ) The compiler according to  claim 1 , further comprising an optimization candidate detecting unit which detects, in the program to be optimized, as a candidate for the partial program to be optimized, the partial program including a memory access instruction to access the same type of data as data to be accessed according to a memory access instruction included in said pattern to be replaced,
 wherein said target partial program detecting unit detects the partial program to be optimized in the partial programs detected by said optimization candidate detecting unit.   
   
   
       7 ) The compiler according to  claim 1 , further comprising an optimization candidate detecting unit which detects, in the program to be optimized, as a candidate for the partial program to be optimized, the partial program including loop processing having the same increment in a loop induction variable as that in loop processing included in said pattern to be replaced,
 wherein said target partial program detecting unit detects the partial program to be optimized in the partial programs detected by said optimization candidate detecting unit.   
   
   
       8 ) The compiler according to  claim 1 , further comprising an
 optimization candidate detecting unit which detects, in the program to be optimized, as a candidate for the partial program to be optimized, the partial program including loop processing repeatedly performed a number of times equal to or larger than a predetermined reference number of times,   wherein said target partial program detecting unit detects the partial program to be optimized in the partial programs detected by said optimization candidate detecting unit.   
   
   
       9 ) The compiler according to  claim 1 , wherein said target partial program detecting unit detects, as the partial program to be optimized, one of the partial programs including in loop processing an additional instruction which does not correspond to any of the instructions included in said pattern to be replaced,
 wherein said instruction sequence transforming unit executes the additional instruction out of the loop processing of the partial program to be optimized, on condition that the result of execution of the additional instruction included in the loop processing is constant independently of repetition of the loop processing, and   wherein said instruction sequence replacing unit replaces the loop processing from which the additional instruction has been removed with the target instruction sequence.   
   
   
       10 ) The compiler according to  claim 1 , wherein said target partial program detecting unit detects, as the partial program to be optimized, one of the partial programs including in loop processing an additional instruction which does not correspond to any of the instructions included in said pattern to be replaced,
 wherein said instruction sequence transforming unit divides the loop processing of the partial program to be optimized into two loop processes in which the additional instruction and the instruction sequence other than the additional instruction are respectively executed, and   wherein said instruction sequence replacing unit replaces the instruction sequence other than the additional instruction with the target instruction sequence.   
   
   
       11 ) The compiler according to  claim 1 , wherein said target partial program detecting unit detects, as the partial program to be optimized, one of the partial programs including an instruction sequence executed in an order different from that of the execution dependencies in said pattern to be replaced,
 wherein said instruction sequence transforming unit changes, on the basis of the execution dependencies, the order of execution of the instruction in the partial program to be optimized, on condition that the result of processing of the partial program to be optimized is not changed even if the order of execution of the instructions in the partial program to be optimized is changed, and   wherein said instruction sequence replacing unit replaces the partial program to be optimized in which the instruction execution order has been changed with the target instruction sequence.   
   
   
       12 ) The compiler according to  claim 1 , wherein if one of the partial programs lacks some of the instructions included in said pattern to be replaced, said target partial program detecting unit detects the partial program as the partial program to be optimized, on condition that the proportion of the instructions in the partial program corresponding to the other instructions included in said pattern to be replaced in all the instructions included in said pattern to be replaced is equal to or higher than a predetermined reference proportion. 
   
   
       13 ) The compiler according to  claim 12 , wherein said instruction sequence transforming unit adds to the partial program to be optimized the absent instruction absent in the instructions in the partial program to be optimized corresponding to all the instructions included in said pattern to be replaced, generates a cancel instruction to return the result of processing of the program to be optimized changed by the addition of the absent instruction to the processing result obtained in the case where the absent instruction is not added, and executes the cancel instruction out of the partial program to be optimized, and
 wherein said instruction sequence replacing unit replaces the partial program to be optimized including the added instruction that has been absent with the target instruction sequence.   
   
   
       14 ) The compiler according to  claim 13 , wherein said instruction sequence transforming unit generates as the cancel instruction a save instruction to save, before the absent instruction, the value in a storage area in which the result of processing according to the absent instruction is stored, and a recovery instruction to recover the value saved in the storage area after execution of the absent instruction, and executes the save instruction and the recovery instruction out of the partial program to be optimized. 
   
   
       15 ) The compiler according to  claim 12 , wherein said target partial program detecting unit detects each of the partial programs as the partial program to be optimized, if the processing time increased in a case where the instruction absent in the partial program in comparison with said pattern to be replaced is added to the partial program is shorter than the reduced processing time in a case where the partial program is replaced with the target instruction sequence by said instruction sequence transforming unit. 
   
   
       16 ) The compiler according to  claim 1 , wherein said instruction sequence replacing unit comprises a limitation selected from a group of limitations consisting of:
 said instruction sequence replacing unit generates the target instruction sequence by replacing each of variables in the target instruction template showing the structure of the target instruction with a variable in the partial program to be optimized corresponding to the variable in the target instruction template;   said instruction sequence replacing unit replaces two or more of the instructions of the partial program to be optimized with one instruction for performing the same processing as that according to the two or more instructions;   said instruction sequence replacing unit replaces an instruction sequence for processing based on an algorithm requiring a longer processing time with an instruction sequence for processing based on a different algorithm requiring a shorter processing time; and   any combination of these limitations.   
   
   
       17 ) A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing functions of an optimizing compiler, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of  claim 1 . 
   
   
       18 ) An optimization method for optimizing a program to be optimized detecting, from a program to be optimized, a pattern that is to be replaced and includes multiple predetermined instructions and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with said instruction sequence to be replaced, comprising:
 a target partial program detecting step of detecting a partial program as said target partial program to be optimized if it is determined that instructions in said partial program that correspond to all instructions included in said pattern to be replaced are executed in an execution order indicated by execution dependencies between instructions in said pattern to be replaced; and   an instruction sequence replacing step of replacing said partial program to be optimized with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       19 ) A compiler detecting, from a program to be optimized, a pattern that is to be replaced and includes multiple predetermined instructions and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with said pattern to be replaced, comprising:
 a target partial program detecting unit for detecting a partial program as said target partial program to be optimized if it is determined that instructions in said partial program that correspond to all instructions included in said pattern to be replaced are executed in an execution order indicated by execution dependencies between instructions in said pattern to be replaced; and   an instruction sequence replacing unit for replacing said partial program to be optimized with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       20 ) The compiler according to  claim 19 , wherein in a case where said pattern to be replaced determines dependencies recurring among the instructions, said target partial program detecting unit detects, as the partial program to be optimized, one of the partial programs including an instruction sequence having the same dependencies as those determined by said pattern to be replaced but differing in recurrence phase, and
 wherein said instruction sequence replacing unit replaces the partial program to be optimized with the target instruction sequence.   
   
   
       21 ) An optimization method for detecting a pattern that is to be replaced and includes multiple predetermined instructions in a program to be optimized and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with the instruction sequence to be replaced, comprising:
 a target partial program detecting step of detecting, from among a partial programs of said program to be optimized, a partial program including instructions corresponding to all instructions included in said pattern to be replaced as a partial program to be optimized;   an instruction sequence transforming step of transforming, in said partial program to be optimized, instructions other than those instructions corresponding to instructions included in said pattern to be replaced and those instructions having execution dependencies different from said pattern to be replaced, so that dependencies between instructions included in said partial program to be optimized match said pattern to be replaced;   an instruction replacing step of replacing said partial program to be optimized transformed by said instruction sequence transforming unit with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       22 ) An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing detection by a compiler, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of  claim 19 . 
   
   
       23 ) A compiler program for causing a computer to function as a compiler detecting a pattern that is to be replaced and includes multiple predetermined instructions in a program to be optimized and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with the instruction sequence to be replaced, said compiler program causing said computer as:
 a target partial program detecting unit for detecting, from among a partial programs of said program to be optimized, a partial program including instructions corresponding to all instructions included in said pattern to be replaced as a partial program to be optimized;   an instruction sequence transforming unit for transforming, in said partial program to be optimized, instructions other than those instructions corresponding to instructions included in said pattern to be replaced and those instructions having execution dependencies different from said pattern to be replaced, so that dependencies between instructions included in said partial program to be optimized match said pattern to be replaced;   an instruction sequence replacing unit for replacing said partial program to be optimized transformed by said instruction sequence transforming unit with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       24 ) A compiler program for causing a computer to function as a compiler detecting a pattern that is to be replaced and includes multiple predetermined instructions in a program to be optimized and replacing the detected pattern to be replaced with a target instruction sequence determined in accordance with the instruction sequence to be replaced, said compiler program causing said computer as:
 a target partial program detecting unit for detecting a partial program as said target partial program to be optimized if it is determined that instructions in said partial program that correspond to all instructions included in said pattern to be replaced are executed in an execution order indicated by execution dependencies between instructions in said pattern to be replaced; and   an instruction sequence replacing unit for replacing said partial program to be optimized with a target instruction sequence determined in accordance with said pattern to be replaced.   
   
   
       25 ) A recording medium on which the compiler program according to  claim 23  is recorded.