Abstract:
A program conversion method that can increase variations of applicable optimizations and effects of the optimization, by being provided with characteristics of a variable or an association between two or more variables as hint information for optimization by a programmer or profiler. The program conversion method converts a source program in a computer and includes: obtaining a constraint equation including at least one of a variable in the source program, a constant, an operator, a pseudo variable, and a built-in function and producing a truth-value; and converting the source program by optimizing the constraint.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    (1) Field of the Invention 
         [0002]    The present invention relates to a program conversion method that achieves higher execution speed and size reduction of a program. 
         [0003]    (2) Description of the Related Art 
         [0004]    In language processors which generate, from a source program, a program which can be executed by a target machine, various optimizations are carried out for higher execution speed or size reduction of a program to be generated. 
         [0005]    One of the optimizations is a technique that focuses on a value taken by a variable in a program and studies a possible value that can be taken by the variable and frequency of appearance of the value to speed up a process in the case where the variable takes a value with high frequency of appearance (see, for example, Patent Reference: Japanese Unexamined Patent Application Publication No. 2002-222088). 
         [0006]    In conventional techniques, however, what a user provides as hint information or what is automatically generated from an analysis result of a profiler is a value that can be taken by an individual valuable in a program and its frequency of appearance. An optimization using such information is, therefore, limited to constant propagation within a function or between functions and to constant folding as an adjunct to the constant propagation. 
       SUMMARY OF THE INVENTION 
       [0007]    An object of the present invention is to provide a program conversion method that can increase variations of applicable optimizations and effects of the optimization, by being provided with characteristics of a variable or an association between two or more variables as hint information for optimization by a programmer or profiler. 
         [0008]    A program conversion method according to an aspect of the present invention is a program conversion method for converting a source program using a computer, the method comprising: obtaining a constraint equation including at least one of: a variable in the source program; a constant; an operator; a pseudo variable; and a built-in function, the constraint equation resulting in a truth-value; and converting the source program by optimizing the source program using the obtained constraint equation. 
         [0009]    The source program is optimized with use of the constraint equation as described above. The above structure allows providing characteristics of the variable or an association between two or more variables, thereby increasing variations of applicable optimizations and effects of the optimization compared to conventional method. 
         [0010]    Preferably, in the obtaining, a constraint equation that is associated with a function definition is obtained, the constraint equation including a formal parameter, the constant, and the operator, and the converting includes: generating a clone of the function indicated by the associated function definition; optimizing a process within the cloned function by assuming that the constraint equation results in true; and replacing function call statements which call when the constraint equation given by replacing formal parameters by actual parameters results in true. 
         [0011]    The process within the function that has been cloned is optimized by assuming that the function definition part constraint results in true, thereby eliminating the need for an operation process of a function definition part constraint. This makes it possible to reduce processing load of the function that is called by the function call statement. 
         [0012]    More preferably, in said obtaining, the constraint equation including the pseudo caller part parameters, the constant, and the operator, is obtained and the constraint equation is associated with a function call statement, and the converting includes: generating a clone of the function that is called by the function call statement when the constraint expression which is given by replacing pseudo caller part parameters by the related actual parameter at the call statement results in a true value; optimizing a process within the cloned function by assuming that the constraint equation results invariably in true; and replacing the function that is called by the function call statement with the cloned function. 
         [0013]    The process within the function that has been cloned is optimized by assuming that the equation in which the pseudo caller part parameter included in the caller part constraint equation has been replaced with the formal parameter of the function that is called by the function call statement results in true. This allows elimination of the need for an operation process of the equation. This makes it possible to reduce processing load of the function that is called by the function call statement. 
         [0014]    More preferably, a pseudo prototype part parameter that is a variable for specifying a formal parameter of function definition at the function declaration is used as the pseudo variable of constraint equation. 
         [0015]    Further, in the obtaining, a constraint equation that is a constraint equation associated with a function declaration is obtained, the constraint equation including the pseudo prototype part parameter, the constant, and the operator, and the converting includes: optimizing, in the case where the function definition corresponding to the function declaration exists in the source program, a clone of the function by assuming a constraint equation which is given by replacing pseudo prototype part parameters by formal parameters in the function is true; and replacing the function call statement with a call statement for the function to be cloned, in the case where the constraint equation which is given by replacing pseudo prototype part parameters by actual parameters in the function call results in true. 
         [0016]    More preferably, in the obtaining, an inner-function constraint equation is obtained, the inner-function constraint equation including at least a variable in a function, a global variable, a constant, and an operator, and the converting includes: obtaining, as optimization target statements, a statement sequence where all variables in constraint equation are live; generating a conditional branching statement including: statements that are obtained by optimizing the optimization target statements assuming the inner-function constraint equation results in true, as a process in the case where a result of a conditional expression is true; and the original optimization target statements in the case where a result of the conditional expression is false, the conditional expression being the inner-function constraint equation; and replacing the optimization target statements by the generated conditional branch statement that has been generated. 
         [0017]    In the case where a result of the constraint equation is true, it is possible to execute the optimized statement. This makes it possible to reduce processing load of the function when the provided constraint equation is satisfied. 
         [0018]    More preferably, in the obtaining, an inner-function constraint equation is obtained, the inner-function constraint equation including at least one of a variable in a function, a global variable, the constant, and the operator, and the converting includes: obtaining, from the function, two or more branch conditions, two or more branch destinations and a branch statement that includes an exclusive operation for each of the branch destinations or a branch-statement sequence; and rearranging an order of evaluating a conditional expression of the branch statement or the branch-statement sequence in the case where an equation same as the inner-function constraint equation is included in any one of the two or more branch conditions. 
         [0019]    It is possible to reduce necessary processing load for estimating a conditional expression when an expression given in a constraint equation is formed, by rearranging orders for estimating the conditional expression so that estimation for the conditional expression specified by the constraint equation is prioritized. 
         [0020]    It should be noted that the present invention can be implemented, in addition to implementation as a program conversion method including characteristic steps described above, as a program conversion apparatus including the characteristic steps of the program conversion method as its components, and as a program which, when loaded into a computer, allows a computer to execute the characteristic steps of the program conversion method. It should be understood that such a program can be distributed via a recording medium such as a compact disc-read only memory (CD-ROM) and a communication network such as the Internet. 
         [0021]    According to the present invention, it is possible to increase variations of applicable optimizations and effects of the optimization by converting a source program using the constraint equation described above. 
       FURTHER INFORMATION ABOUT TECHNICAL BACKGROUND TO THIS APPLICATION 
       [0022]    The disclosure of Japanese Patent Application No. 2008-026556 filed on Feb. 6, 2008 including specification, drawings and claims is incorporated herein by reference in its entirety. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0023]    These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings that illustrate a specific embodiment of the invention. In the Drawings: 
           [0024]      FIG. 1  is an external view of a program conversion apparatus. 
           [0025]      FIG. 2  is a block diagram that illustrates a functional configuration of the program conversion apparatus. 
           [0026]      FIG. 3  is a flowchart that illustrates program conversion processing executed by the program conversion apparatus. 
           [0027]      FIG. 4  is a diagram that explains an example of description method of a constraint equation. 
           [0028]      FIG. 5  is a flowchart that illustrates an overview of optimization processing of an intermediate representation performed by an intermediate representation conversion unit. 
           [0029]      FIG. 6  is a flowchart that illustrates conversion processing of a source program using a function definition part constraint including a formal parameter, a constant, and an operator of a function. 
           [0030]      FIG. 7  is a diagram that explains an example of executing program conversion using the function definition part constraint. 
           [0031]      FIG. 8  is a flowchart that illustrates conversion processing of a source program  110  using a caller part constraint equation including an actual parameter, a constant, and an operator of a function. 
           [0032]      FIG. 9  is a diagram that explains an example of executing program conversion using the caller part constraint equation. 
           [0033]      FIG. 10  is a flowchart that illustrates conversion processing of a source program using an inner-function constraint equation including a variable, a constant, and an operator within a function. 
           [0034]      FIG. 11  is a diagram that explains an example of executing program conversion using the inner-function constraint equation. 
           [0035]      FIG. 12  is a flowchart that illustrates conversion processing of a source program  110  using an inner-function constraint equation including a variable, a constant, and an operator within a function. 
           [0036]      FIG. 13  is a diagram that explains an example of executing program conversion using the inner-function constraint equation. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0037]    A program conversion apparatus according to an embodiment of the present invention will be described below with reference to the drawings. 
         [0038]      FIG. 1  is an external view of a program conversion apparatus. A program conversion apparatus  200  is a usual computer and implemented by executing a program on a processor of the computer. It is to be noted that various data such as intermediate data during executing a program are stored in a memory of the computer. Further, the program can be stored in a computer-readable recording medium and distributed. 
         [0039]      FIG. 2  is a block diagram that illustrates a functional configuration of the program conversion apparatus. 
         [0040]    A program conversion apparatus  200  receives, as inputs, a source program  110  described in a high-level language program and a constraint equation set  111 , converts the source program  110 , and outputs an object program  120  that is a conversion result. Here, the constraint equation set  111  includes a set of equations (hereinafter referred to as “constraint equations”) each of which contains at least one of: a variable; a constant; and an operator, which are included in the source program  110 ; and a pseudo variable; and a built-in function, which are provided by the program conversion apparatus  200 , and results in a truth-value. 
         [0041]    The program conversion apparatus  200  includes: an intermediate representation generation unit  230 ; a constraint equation set analysis unit  231 ; an intermediate representation conversion unit  232 ; an object program generation unit  233 ; a constraint equation database  140 ; and an intermediate representation database  141 . 
         [0042]    The intermediate representation generation unit  230  is a processing unit that converts the source program  110  into an intermediate representation that is an internal data representation of the program conversion apparatus  200  and stores the converted source program in the intermediate representation database  141 . 
         [0043]    The constraint equation set analysis unit  231  is a processing unit that converts a constraint equation included in the constraint equation set  111  into an equation representation that is the internal data representation of the program conversion apparatus  200  and stores the converted constraint equation in the constraint equation database  140 . 
         [0044]    The intermediate representation conversion unit  232  is a processing unit that converts an internal representation of the source program  110  included in the intermediate representation database  141  based on information in the constraint equation database  140  and stores the converted internal representation in the intermediate representation database  141 . 
         [0045]    The object program generation unit  233  is a processing unit that generates an object program  120  based on a detail of the intermediate representation database  141  in a format suitable to a target machine and outputs the generated object program  120 . 
         [0046]      FIG. 3  is a flowchart that illustrates program conversion processing executed by the program conversion apparatus  200 . 
         [0047]    The intermediate representation generation unit  230  converts the source program  110  into an intermediate representation and stores the converted source program in the intermediate representation database  141  (Step S 130 ). A three address code and an abstract syntax tree are general forms used for an intermediate representation and can be used for the present invention as well. 
         [0048]    The constraint equation set analysis unit  231  converts a constraint equation set  111  into an equation representation that is the internal data representation of the program conversion apparatus  200  and stores the converted constraint equation set  111  in the constraint equation database  140  (Step S 131 ). A general form for the equation representation includes an expression tree structure. 
         [0049]    The intermediate representation conversion unit  232  converts a detail of the intermediate representation database  141  based on information in the constraint equation database  140  and stores the converted details in the intermediate representation database  141  (Step S 132 ). An object of the conversion is speeding up an operation or reduction in the program size. 
         [0050]    The object program generation unit  233  generates an object program  120  based on a detail of the intermediate representation database  141  in a format suitable to the target machine and outputs the generated object program  120  (Step S 133 ). 
         [0051]      FIG. 4  is a diagram that explains an example of description method of a constraint equation. 
         [0052]    In the source program  110  illustrated in  FIG. 4 , a designator  300  is a function definition part constraint that includes a formal parameter of a function sample_ 1 . The first row of the designator  300  specifies, regarding the formal parameter p 0 , performing optimization for an operation of the function sample_ 1  assuming formation of a conditional expression p 0 &gt;0. The second row of the designator  300  specifies performing optimization for the operation in the case where formation of p 0 &gt;255 is assumed. 
         [0053]    A designator  301  is an caller part constraint equation using a pseudo variable that corresponds to a formal parameter of a function to be called (here, function sample  2 ). In the example, “$0,”, “$1”, . . . are assumed to be the 0th formal parameter, the first formal parameter, . . . of the function to be called, respectively. The first row of the designator  301  specifies performing optimization of an operation in the function sample_ 2  in the case where the 0th argument of the function sample_ 2  leaves a remainder of 0 when divided by two. The second row of the designator  300  specifies performing optimization of an operation in the function sample_ 2  in the case where the 0th argument of the function sample_ 2  leaves a remainder of 1 when divided by two. 
         [0054]    The designator  302  is an inner-function constraint equation that includes a variable within a function. The designator  302  specifies optimization for an operation of the next row in the case where p 0 ==5 and p 1 ==3 are formed. 
         [0055]    Although the constraint equation is given by the designator in the above example, the constraint equation can be defined by, for example, a file different from the input file, as long as a name of a variable and information regarding a live range of each of the variables are included. 
         [0056]    Next, optimization processing of the intermediate representation performed by the intermediate representation conversion unit  232  (Step S 132 ) will be described by refereeing to a specific conversion example. 
         [0057]      FIG. 5  is a flowchart that illustrates an overview of optimization processing (Step S 132 ) of an intermediate representation performed by an intermediate representation conversion unit  232 . It is to be noted that details for each process hereafter will be described with reference to  FIG. 6  and subsequent diagrams. 
         [0058]    The intermediate representation conversion unit  232  sequentially retrieves all of the constraint equations in the constraint equation database  140 , and the retrieved constraint equation is assumed to be e (Step S 400 ). 
         [0059]    The intermediate representation conversion unit  232  retrieves, from the intermediate representation database  141 , a statement, a function, or a declaration, each of which is associated with the constraint equation e, and the retrieved statement, function, or declaration is assumed to be an intermediate representation s (Step S 401 ). 
         [0060]    The intermediate representation conversion unit  232  analyzes the constraint equation e and the intermediate representation s associated with the constraint equation e, and selects an effective optimization method that is applicable to the internal representation of the source program  110  (Step S  402 ). The optimization method obtained here is assumed to be m. 
         [0061]    In the case where an effective and applicable optimization method has been obtained (Yes, in Step S 403 ), the intermediate representation conversion unit  232  converts and optimizes the intermediate representation s based on the constraint equation e and the optimization method m. Further, the intermediate representation conversion unit  232  stores, into the intermediate representation database  141 , the intermediate representation s that has been converted and optimized (Step S 404 ). 
         [0062]    In the case where an effective and applicable optimization method has not been obtained (No, in Step S 403 ), or subsequent to the intermediate representation optimization (Step S 404 ), the intermediate representation conversion unit  232  judges whether or not all of the constraint equations in the constraint equation database  140  has been retrieved (Step S 405 ). In the case where all of the constraint equations has been retrieved (Yes, in Step S 405 ), the intermediate representation conversion unit  232  ends the processing. In the case where not all of the constraint equations has been retrieved (No, in Step S 405 ), the intermediate representation conversion unit  232  repeats the process in Step S 400  and subsequent processes. 
         [0063]    Next, an optimization of the intermediate representation carried out for each constraint equation type by the intermediate representation conversion unit  232  (Step S 132  in  FIG. 5 ) will be described. 
         [0064]      FIG. 6  is a flowchart that illustrates conversion processing of the source program  110  using a function definition part constraint including a formal parameter, a constant, and an operator of a function. 
         [0065]    The intermediate representation conversion unit  232  sequentially retrieves all of the constraint equations in the constraint equation database  140 , and the retrieved constraint equation is assumed to be e (Step S 500 ). 
         [0066]    In the case where the constraint equation e is a function definition part constraint (Yes, in Step S 501 ), the intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a function p including a formal parameter that is a variable included in the constraint equation e (Step S 502 ). 
         [0067]    The intermediate representation conversion unit  232  generates a function p′ that is a clone of the function p (Step S 503 ). 
         [0068]    The intermediate representation conversion unit  232  optimizes the function p′, assuming that the constraint equation e results in true (Step S 504 ). 
         [0069]    The intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a set of function call statements S that calls the function p (Step S 505 ). 
         [0070]    The intermediate representation conversion unit  232  sequentially retrieves an element of the set of function call statements S, and the retrieved function call statement is assumed to be s (Step S  506 ). 
         [0071]    The intermediate representation conversion unit  232  generates a constraint equation e′ in which a variable included in the constraint equation e, that is, a formal parameter of the function p has been replaced with an actual parameter corresponding to the function call statement s (Step S 507 ). 
         [0072]    In the case where it is ensured that the constraint equation e′ is invariably true (Yes, in Step S 508 ), the intermediate representation conversion unit  232  replaces the function that is called by the function call statement s so that the function p is changed to the function p′ (Step S 509 ) and registers the function P′ and updated function call statement s on the intermediate representation database  141  (Step S 510 ). 
         [0073]    In the case where it is not ensured that the constraint equation e′ is invariably true (No, in Step S 508 ), or subsequent to the process in Step S 510 , the intermediate representation conversion unit  232  judges whether or not all of the function call statements s included in the set S has been retrieved (Step S 511 ). In the case where the function call statement s that has not been retrieved exists (No, in Step S 511 ), the intermediate representation conversion unit  232  repeats the process in Step S 506  and subsequent processes. 
         [0074]    In the case where all of the function call statements s has been retrieved (Yes, in Step S 511 ), or where the retrieved constraint equation e is not a function definition part constraint (No, in Step S 501 ), the intermediate representation conversion unit  232  judges whether or not all of the constraint equations in the constraint equation database  140  has been retrieved (Step S 512 ). In the case where all of the constraint equations has been retrieved (Yes, in Step S 512 ), the intermediate representation conversion unit  232  ends the processing. In the case where not all of the constraint equations has been retrieved (No, in Step S 512 ), the intermediate representation conversion unit  232  repeats the processes in Step S 500  and subsequent processes. 
         [0075]    Next, an example of executing program conversion using the function definition part constraint will be explained with reference to  FIG. 7 .  FIG. 7A  illustrates a program  600  that is an example of the source program  110 .  FIG. 7B  illustrates a program  610  that is a result of converting the program  600 . 
         [0076]    It is assumed that the intermediate representation conversion unit  232  has retrieved a designator  601  “b&gt;0” as the constraint equation e from the constraint equation database  140  (Step S 500 ). 
         [0077]    Since the retrieved constraint equation “b&gt;0” is a function definition part constraint (Yes, in Step S 501 ), the intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a function clip to which the constraint equation “b&gt;0” is added (Step S 502 ). 
         [0078]    The intermediate representation conversion unit  232  generates a function clip′ that is a clone of the function clip (Step S 503 ). 
         [0079]    The intermediate representation conversion unit  232  optimizes the function clip′, assuming that the constraint equation “b&gt;0” results in true (Step S 504 ). In this execution example, a conditional expression of an if statement that evaluates “b&gt;0” is replaced with a constant “true”. This allows reduction of a condition judgment and processing of an else portion, producing a statement  612  that is the processing details of the function clip′. 
         [0080]    The intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a set S of a function call statements  603  that calls the function clip (Step S 505 ). 
         [0081]    The intermediate representation conversion unit  232  retrieves the function call statement  603  from the set S (Step S  506 ). 
         [0082]    The intermediate representation conversion unit  232  obtains a constraint equation “a&gt;0” in which the formal parameter b of the constraint equation “b&gt;0” has been replaced with an actual parameter a of the function call statement  603  (Step S 507 ). 
         [0083]    As can be seen from the conditional expression “if (a&gt;5)” immediately preceding the function call statement  603 , it is ensured that the constraint equation “a&gt;0” results invariably in true when executing the function call statement  603 . Since it is ensured that the constraint equation “a&gt;0” results invariably in true (Yes, in Step S 508 ), the intermediate representation conversion unit  232  replaces the function that is called by the function call statement  603  so that the function is changed from the function clip to the function clip′ and generates a function call statement  613  that has been updated (Step S 509 ). 
         [0084]    As described above, branching operations contained in the function clip can be reduced by converting the program  600  to the program  610 . 
         [0085]      FIG. 8  is a flowchart that illustrates conversion processing of the source program  110  using an caller part constraint equation including an actual parameter, a constant, and an operator of a function. 
         [0086]    The intermediate representation conversion unit  232  sequentially retrieves all of the constraint equations in the constraint equation database  140 , and the retrieved constraint equation is assumed to be e (Step S 700 ). 
         [0087]    In the case where the constraint equation e is an caller part constraint equation (Yes, in Step S 701 ), the intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a function call statement s to which the constraint equation e is attached (Step S 702 ). 
         [0088]    The intermediate representation conversion unit  232  generates a constraint equation e′ in which a pseudo caller part parameter included in the constraint equation e has been replaced with an actual parameter of a function included in the function call statement s (Step S 703 ). 
         [0089]    The intermediate representation conversion unit  232  judges whether or not the constraint equation e′ is invariably true (Step S 704 ). In the case where it is ensured that the constraint equation e′ is invariably true (Yes, in Step S 704 ), the intermediate representation conversion unit  232  obtains, from the intermediate representation database  141 , a function p that is called by the function call statement s (Step S 705 ). 
         [0090]    The intermediate representation conversion unit  232  generates a constraint equation e″ in which the pseudo formal parameter included in the constraint equation e has been replaced with a formal parameter of the function p (Step  5706 ). 
         [0091]    The intermediate representation conversion unit  232  generates a function p′ that is a clone of the function p (Step S 707 ). 
         [0092]    The intermediate representation conversion unit  232  optimizes the function p′ using the condition that the constraint equation e″ results in true (Step S 708 ). 
         [0093]    The intermediate representation conversion unit  232  judges whether or not a function p″ that performs the same operation as the function p′ is stored in the intermediate representation database  141  (Step S 709 ). In the case where the function p″ is stored in the intermediate representation database  141  (Yes, in Step S 709 ), the intermediate representation unit  232  replaces the function that is called by the function call statement s so that the function is changed from the function p to the function p″, and registers, on the intermediate representation database  141 , the function call statement s that has been updated (Step S 710 ). 
         [0094]    In the case where the function p″ is not stored in the intermediate representation database  141  (No, in Step S 709 ), the intermediate representation unit  232  registers the function p′ on the intermediate representation database  141  (Step S 711 ). Further, the intermediate representation conversion unit  232  replaces the function that is called by the function call statement s so that the function is changed from the function p to the function p′, and registers, on the intermediate representation database  141 , the function call statement s that has been updated (Step S 712 ). 
         [0095]    The intermediate representation conversion unit  232  judges whether or not all of the constraint equations in the constraint equation database  140  has been retrieved (Step S 713 ). In the case where all of the constraint equations has been retrieved (Yes, in Step S 713 ), the intermediate representation conversion unit  232  ends the processing. In the case where not all of the constraint equations has been retrieved (No, in Step S 713 ), the intermediate representation conversion unit  232  repeats the processes in Step S 700  and subsequent processes. 
         [0096]    Next, an example of executing program conversion using the caller part constraint equation will be explained with reference to  FIG. 9 .  FIG. 9A  illustrates a program  800  that is an example of the source program  110 .  FIG. 9B  illustrates a program  810  that is a result of converting the program  800 . 
         [0097]    It is assumed that the intermediate representation conversion unit  232  has retrieved a designator  801  “$0&gt;0” as the constraint equation e from the constraint equation database  140  (Step S 700 ). 
         [0098]    Since the retrieved constraint equation e is the caller part constraint equation (Yes, in Step S 701 ), the intermediate representation conversion unit  232  obtains a function call statement  802  to which the constraint equation e is attached (Step S 702 ). 
         [0099]    The intermediate representation conversion unit  232  obtains “a&gt;0” as an expression e′ in which a pseudo caller part parameter $0 included in the constraint equation “$0&gt;0” has been replaced with the actual parameter of the function call statement  802  (Step S 703 ). 
         [0100]    As can be seen from the conditional expression “if (a&gt;5)” immediately preceding the function call statement  802 , it is ensured that the expression e′ results in true when executing the function call statement  802  (Yes, in Step S 704 ). For the above reason, the intermediate representation conversion unit  232  retrieves the function clip that is called by the function call statement s (Step S 705 ). 
         [0101]    The intermediate representation conversion unit  232  obtains “b&gt;0” as an expression e″ in which a pseudo caller part parameter included in the constraint equation “$0&gt;0” has been replaced with a formal parameter of the function clip (Step S 706 ). 
         [0102]    The intermediate representation conversion unit  232  generates a clone function clip′ of the function clip (Step S 707 ). 
         [0103]    The intermediate representation conversion unit  232  optimizes the function clip′ using the constraint equation e″, that is, “b&gt;0” (Step S 708 ). In this execution example, a conditional expression of an if statement that evaluates “b&gt;0” is replaced with a constant “true”. This allows reduction of a condition judgment and processing of an else portion, producing a statement  813  that is the processing details of the function clip′. 
         [0104]    It is assumed here that the intermediate representation database  141  does not include a function that performs the same operation as the function clip′ (No, in Step S 709 ). For the above reason, the intermediate representation conversion unit  232  registers the function clip′ on the intermediate representation database  141  (Step S 711 ). 
         [0105]    The intermediate representation conversion unit  232  replaces the function that is called by the function call statement  802  so that the function is changed from the function clip to the function clip′, and generates the function call statement  812  that has been updated (Step S 712 ). 
         [0106]    As described above, branching operations contained in the function clip can be reduced by converting the program  800  to the program  810 . 
         [0107]      FIG. 10  is a flowchart that illustrates conversion processing of a source program  110  using a inner-function constraint equation including a variable, a constant, and an operator within a function. 
         [0108]    The intermediate representation conversion unit  232  sequentially retrieves all of the constraint equations in the constraint equation database  140 , and the retrieved constraint equation is assumed to be e (Step S 900 ). 
         [0109]    The intermediate representation conversion unit  232  judges whether or not the constraint equation e is a inner-function constraint equation (Step S 901 ). In the case where the constraint equation e is the inner-function constraint equation (Yes, in Step S 901 ), the intermediate representation conversion unit  232  retrieves, from the intermediate representation database  141 , a function p to which the constraint equation e is attached (Step S 902 ). 
         [0110]    The intermediate representation conversion unit  232  obtains a live range that is common to all of the variables in the constraint equation e of the function p, and obtains a list S including a statement that exists within the range (Step S 903 ). 
         [0111]    The intermediate representation conversion unit  232  generates a conditional branching statement i that has a statement of the list S at each branch destination and includes a conditional branching statement that is the constraint equation e, and registers the conditional branching statement i on the intermediate representation database  141  (Step S 904 ). 
         [0112]    The intermediate representation conversion unit  232  optimizes the statement that is executed when the conditional expression of the conditional branching statement i results in true by using the condition that the constraint equation e results in true, and stores a result of the optimization in the intermediate representation database  141  (Step S 905 ). 
         [0113]    Next, an execution example of a program conversion using the inner-function constraint equation will be described with reference to  FIG. 11 .  FIG. 11A  illustrates a program  1000  that is an example of the source program  110 .  FIG. 11B  illustrates a program  1010  that is a result of converting the program  1000 . 
         [0114]    It is assumed that the intermediate representation conversion unit  232  has retrieved a designator  1001  “a+b==10” as the constraint equation e from the constraint equation database  140  (Step S 900 ). 
         [0115]    Since the retrieved constraint equation e is the inner-function constraint equation (Yes, in Step S 901 ), the intermediate representation conversion unit  232  retrieves a function func to which the constraint equation e is attached (Step S 902 ). 
         [0116]    The intermediate representation conversion unit  232  obtains a live range that is common to all of the variables in the constraint equation e of the function func, and obtains a list S including a statement that exists within the range (Step S 903 ). In this execution example, the live range common to all of the variables in the constraint equation e is the range from a start to an end of a statement  1002 . For that reason, the list S is a list of a statement including only the statement  1002 . 
         [0117]    The intermediate representation conversion unit  232  generates a conditional branching statement i that has a statement of the list S, that is, the statement  1002 , at each branch destination and includes a conditional branching statement that is the constraint equation e (Step S 904 ). In the execution example, a statement  1011  corresponds to the conditional branching statement i. 
         [0118]    The intermediate representation conversion unit  232  optimizes the statement that is executed when the conditional expression results in true, assuming that a conditional statement of the conditional branching statement i, that is, “a+b==10” results in true (Step S 905 ). In the execution example, a right-hand side of the statement  1002  “(a+b)*(a+b)” can be converted to “10*10” with use of the constraint equation “a+b==10”, and further converted to “100” since “10*10” is “100”. A result of the replacement is a statement  1013 . 
         [0119]    As described above, two additions and one multiplication can be replaced with condition judgment and branching by converting the program  1000  to the program  1010 . 
         [0120]      FIG. 12  is a flowchart that illustrates conversion processing of the source program  110  using a inner-function constraint equation including a variable, a constant, and an operator within a function. 
         [0121]    The intermediate representation conversion unit  232  sequentially retrieves all of the constraint equations in the constraint equation database  140 , and the retrieved constraint equation is assumed to be e (Step S 1100 ). 
         [0122]    The intermediate representation conversion unit  232  judges whether or not the constraint equation e is a inner-function constraint equation (Step S 1101 ). In the case where the constraint equation e is the inner-function constraint equation (Yes, in Step S 1101 ), the intermediate representation conversion unit  232  retrieves a function p to which the constraint equation e is attached (Step S 1102 ). 
         [0123]    The intermediate representation conversion unit  232  obtains, from the function p, two or more branch conditions, two or more branch destinations and a branch statement that includes an exclusive operation for each of the branch destinations or a branch-statement sequence s (Step S 1103 ). 
         [0124]    In the case where the conditional expression of the branch statement or the branch-statement sequence s includes the same equation as the constraint equation e (Yes, in Step S 1104 ), the intermediate representation conversion unit  232  modifies an order to evaluate the conditional expression of the branch statement or the branch-statement sequence s so that the conditional expression e is evaluated first, and updates the intermediate representation database  141  (Step S 1105 ). 
         [0125]    In the case where the conditional expression of the branch statement or the branch-statement sequence s does not include the same equation as the constraint equation e (No, in Step S 1104 ) or subsequent to the process of S 1105 , the intermediate representation conversion unit  232  judges whether or not all of the branch statements or the branch-statement sequences s has been retrieved from the function p (Step S 1106 ). In the case where not all of the branch statements or the branch-statement sequences s has been retrieved (No, in Step S 1106 ), the intermediate representation conversion unit  232  repeats the processes in Step S 1103  and subsequent processes. 
         [0126]    In the case where all of the branch statements or the branch-statement sequences s has been retrieved (Yes, in Step S 1106 ), the intermediate representation conversion unit  232  judges whether or not all of the constraint equations e in the constraint equation database  140  has been retrieved (Step S 1107 ). In the case where all of the constraint equations e has been retrieved (Yes, in Step S 1107 ), the intermediate representation conversion unit  232  ends the processing. In the case where not all of the conditional expressions e has been retrieved (No, in Step S 1107 ), the intermediate representation conversion unit  232  repeats the processes in Step S 1100  and subsequent processes. 
         [0127]    Next, an execution example of program conversion using the inner-function constraint equation will be explained with reference to  FIG. 13 . 
         [0128]      FIG. 13A  illustrates a program  1200  that is an example of the source program  110 .  FIG. 13B  illustrates a program  1210  that is a result of converting the program  1200 . 
         [0129]    It is assumed that the intermediate representation conversion unit  232  has retrieved a designator  1201  “20&lt;=a&amp;&amp;a&lt;30” as the constraint equation e from the constraint equation database  140  (Step S 1100 ). 
         [0130]    Since the retrieved constraint equation e is the inner-function constraint equation (Yes, in Step S 1101 ), the intermediate representation conversion unit  232  retrieves a function func to which the constraint equation e is attached (Step S 1102 ). 
         [0131]    The intermediate representation conversion unit  232  obtains a sequence of branch statements  1202  that includes two or more branch conditions and two or more branch destinations (hereinafter referred to as “conditional branching statement”) (Step S 1103 ). 
         [0132]    The intermediate representation conversion unit  232  determines that the conditional expression  1203  of the conditional branching statement  1202  is the same as the constraint equation e (Yes, in Step S 1104 ). 
         [0133]    For that reason, the intermediate representation conversion unit  232  converts the conditional branching statement  1202  so that the conditional expression  1203  is evaluated first. A result of the conversion is the conditional branching statement  1212  (Step S 1105 ). 
         [0134]    As described above, evaluation of the conditional expression specified by the constraint equation e can be prioritized by converting the program  1200  to the program  1210 , thereby reducing processing load of the program. 
         [0135]    As described above, according to the embodiment of the present invention, it is possible to provide a processor with a characteristic of a variable or a relationship between variables as a constraint equation or a constraint equation with frequency of appearance, thereby enabling execution of a number of optimizations. 
         [0136]    It is to be noted that the built-in function in the constraint equation described above may be a constant judgment built-in function that returns true when an argument is a constant and returns false when an argument is not a constant. 
         [0137]    Further, although a program conversion using a function definition part constraint has been described with reference to  FIG. 6  and  FIG. 7 , the function definition part constraint may be placed not immediately before a function definition, but a function prototype declaration (function declaration). In this case, optimization for the function definition corresponding to the function declaration is carried out according to the same method as shown in  FIG. 6  and  FIG. 7 . 
         [0138]    More specifically, a pseudo prototype part parameter that is a variable for specifying the argument in the function declaration of a source program is used as a pseudo variable in the constraint equation. Since the name of the argument in the function declaration does not match the formal parameter of function, the pseudo prototype part parameter is used so as to associate the argument name of the function declaration part with the formal parameter of the function definition and associate the argument name of the function declaration part with the actual parameter of the function call. 
         [0139]    Further, according to the pseudo prototype part parameter, a function definition part constraint is assumed to be a pseudo prototype part parameter constraint equation. In the case where the function definition corresponding to the function declaration exists in the source program, a function definition part constraint that is obtained by replacing a pseudo prototype part parameter of a pseudo prototype part parameter constraint equation with a formal parameter variable of the corresponding function is used to optimize a clone of the function by assuming the function definition part constraint results in true. Further, the function call statement is replaced with a call statement for the function to be cloned, in the case where the function call statement corresponding to the function declaration exists in the source program and where the function definition part constraint in which the pseudo prototype part parameter of the pseudo prototype part parameter constraint equation is replaced with an actual parameter variable of a corresponding function results invariably in true. 
         [0140]    According to this structure, it is possible to optimize a function even when cloning the function and replacing the function call are carried out on different files, by using the constraint equation associated with the function declaration as an intermediary. This enables adaptation for a division compile. 
         [0141]    Although only an exemplary embodiment of this invention has been described in detail above, those skilled in the art will readily appreciate that many modifications are possible in the exemplary embodiment without materially departing from the novel teachings and advantages of this invention. Accordingly, all such modifications are intended to be included within the scope of this invention. 
       INDUSTRIAL APPLICABILITY 
       [0142]    The program conversion apparatus according to the present invention can be applied to a compiler and the like which generate a program suitable to a target machine based on a source program described in a high-level language.