Method and apparatus for precision optimization in compiled programs Number:7,143,402 from the United States Patent and Trademark Office (PTO) owispatent

Title: Method and apparatus for precision optimization in compiled programs

Abstract: A compiler mounted on a computer generates a first object code of a target method in a double precision mode in the floating-point computation. If the target method is found to be frequently called in a single precision mode and a runtime cost may be reduced by executing the target method in the single precision mode, a second object code of the target method is generated in the single precision mode. Alternatively, regardless of whether a target method to be compiled will be called by the double precision mode or the single precision mode in the floating-point computation, the object code is generated by setting the precision mode depending on the type of the computation within the target method. Then, a code for matching the precision mode is generated and added based on a relation between the target code and its caller method.

Patent Number: 7,143,402 Issued on 11/28/2006 to Ogasawara,   et al.

---

Inventors:	Ogasawara; Takeshi (Hachioji, JP), Suganuma; Toshio (Yokohama, JP)
Assignee:	International Business Machines Corporation (Armonk, NY)
Appl. No.:	10/621,281
Filed:	July 16, 2003

---

Foreign Application Priority Data

---

Jul 31, 2002 [JP]			2002-224207

Current U.S. Class:	717/151
Current International Class:	G06F 9/45 (20060101)
Field of Search:	717/151

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5587897		December 1996		Iida

Other References

Michael Paleczny, Christopher Vick and Cliff Click, "The Java.RTM. HotSpot Server Compiler", The USENIX Association: Proceedings of the Java.RTM. Virtual Machine Research and Technology Symposium (JVM '01). cited by oth- er.

Primary Examiner: Chavis; John
Attorney, Agent or Firm: Perez, Esq.; Rafael

---

Claims

---

The invention claimed is:

1. A method of optimizing machine language code generated from source code having both single and double precision computation, said machine language code used to create an executable program, the optimizing machine language code comprising the steps of: a) storing a count of times one or more precision computations are called in a double or single precision mode in a floating-point computation; b) selecting a default precision mode to be either the double precision mode or the single precision mode and examining a frequency with which a target precision computation is called in a non-default precision mode, based on said stored count; and c) generating and storing generalized code corresponding to a call in a non-default precision mode with respect to the target precision computation, based on said frequency with which a target precision computation is called.

2. The method of claim 1, wherein step (a) further comprising a step of: counting the number of times said precision computations are called in the non-default precision mode during runtime of said program.

3. The method of claim 1, wherein step (b) further includes a step of comparing said count with a preset threshold and step (c) further includes a step of generating said generalized code when said count exceeds said threshold.

4. The method of claim 1, wherein step (c) further comprising the steps of: determining prior to generating said generalized code, whether a processing cost may be reduced if said target precision computation is operated in the non-default precision mode.

5. The method of claim 1, wherein prior to generating and storing said generalized code, step (c) further comprises the steps of: detecting any target precision computations in which the computation is executed in an excessive precision; and replacing said detected target precision computations with single precision computations.

6. The method of claim 1, wherein step (c) further comprises a step of performing code analysis with respect to the target precision computations to be compiled; dividing the target precision computations into regions for executing single precision computations and regions for executing double precision computations, said regions being determined by results of the code analysis.

7. A method for generating a machine language code by controlling a computer to compile a program, the method comprising the steps of: a) setting a computation precision for calling a target computation, said computation precision being based on a precision mode in a floating-point computation of a caller computation and generating and storing a machine language code; b) determining the precision mode of said target computation and said caller computation, said precision mode being a double or single precision mode; and c) generating an auxiliary code depending on a relation between the precision mode in said target computation and the precision mode in said caller computation and adding the auxiliary code to the stored machine language code, if the precision mode in said caller computation is different from the precision mode in said target computation.

8. The method of claim 7, wherein step (a) further comprises the steps of: detecting said target computation which is executed in an excessive precision; and replacing said precision mode of said target computation with a single precision mode.

9. The method of claim 7, wherein step (a) further comprises the steps of: performing code analysis of said target computation; dividing said target computation into regions for executing single precision computations and regions for executing double precision computations in accordance with results of said analysis; and setting said computation precision for each of said regions to generate the machine language code.

10. An apparatus for optimizing machine language code generated from source code having both single and double precision computations, said machine language code used to create an executable program, the apparatus comprising: a compiler for compiling the source code according to a precision computation; and a program execution unit for executing the source code in an interpreter and said program compiled by said compiler, wherein said compiler generates a first code of a target computation in a default precision mode selected from at least one of a double precision mode and a single precision mode in a floating-point computation, and generates a second code of said target computation in a non-default precision mode selected from at least one of the double precision mode and the single precision mode if said target computation satisfies a predefined condition.

11. The apparatus of claim 10, wherein if said target computation operating in said non-default precision mode calls another computation operating in said non-default precision mode, said program execution unit calls said second code generated in said compiler.

12. The apparatus of claim 11, wherein if a target computation to be compiled may reduce processing costs by using said second code rather than said first code and if a frequency in which said another computation is called from the target computation in said non-default precision mode is high, said compiler generates said second code.

13. The apparatus of claim 10, wherein said compiler further comprises: an excessive-precision optimization unit for detecting in a target computation a portion to be compiled in which a computation is executed in an excessive precision and replacing the computation of the portion with a single precision computation; and a code generation unit for generating said first code and said second code to reflect a process result from said excessive-precision optimization unit.

14. The apparatus of claim 10, wherein said compiler further comprises: a precision region analysis unit for performing code analysis with respect to a target computation to be compiled and for dividing the target computation into regions for executing single precision computations and regions for executing double precision computations; and a code generation unit for setting a computation precision for each of said regions to generate machine language code based on an analysis result from said precision region analysis unit.

15. A data processing apparatus for generating a machine language code by compiling a program, said apparatus comprising: a code generation means for setting a computation precision, with respect to a target computation to be compiled, depending on a precision mode in a floating-point computation in a caller computation for calling said target computation, and generating a machine language code; and auxiliary code addition means for generating an auxiliary code, based on a relation between the precision mode in said target computation and the precision mode in said caller computation, for matching said precision mode, and adding the auxiliary code to the machine language code generated in said code generation means.

16. The apparatus of claim 15, wherein said auxiliary code addition means adds the code for matching the precision mode of the target computation with respect to said caller computation if the precision mode in said target computation is different from the precision mode in said caller computation.

17. The apparatus of claim 15, further comprising excessive precision optimization means for detecting a portion in the target computation to be compiled in which the computation is executed in an excessive precision, and replacing the portion with a single precision computation, wherein said code generation means generates machine language code to reflect a process result from said code addition means.

18. The apparatus of claim 15, further comprising precision region analysis means for executing a code analysis with respect to the target computation to be compiled and dividing the target computation into regions for executing single precision computations and regions for executing double precision computations, wherein said code generation means sets the computation precision for each of said regions to generate the machine language code, based on an analysis result from said precision region analysis means.

19. A computer program device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform computation steps for a program for generating a machine language code by controlling a computer to compile an executable program, said program causing said computer to perform the steps of: a) storing information regarding whether a computation is called in a double precision mode or a single precision mode in a floating-point computation when said executable program is executed; b) when a target computation is compiled, examining a frequency with which said target computation is called in a non-default precision mode, based on the stored information, if a default precision mode is selected from at least one of the double precision mode and the single precision mode in the floating-point computation in said executable program; and c) generating and storing a specialized machine language code corresponding to the call in said non-default precision mode with respect to said target computation based on obtained information on the frequency in which the target computation is called in said non-default precision mode.

20. The program of claim 19, wherein step (c) further comprises a step of generating said specialized machine language code with respect to said target computation to be compiled if processing costs are reduced when said target computation is operated in said non-default precision mode.

21. The program of claim 19, wherein step (c) further comprises the steps of: detecting a portion in said target computation to be compiled, in which the computation is executed in an excessive precision; and replacing the portion with a single precision computation.

22. The program of claim 19, wherein step (c) further comprising the steps of: performing code analysis with respect to said target computation to be compiled; and dividing the target computation into regions for executing single precision computations and regions for executing double precision computations based on results of the code analysis.

23. A computer program device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform computation steps for a program for generating a machine language code by controlling a computer to compile an executable program, said program causing said computer to perform the steps of: a) setting a computation precision, with respect to a target computation to be compiled, depending on a precision mode in a floating-point computation in a caller computation for calling said target computation and generating and storing a machine language code; b) examining a relation between said target computation and said caller computation; and c) generating an auxiliary code depending on the relation and adding the auxiliary code to the stored machine language code.

24. The program of claim 23, wherein step (c) further comprises the step of adding code for matching the precision mode of the target computation with respect to the caller computation if the precision mode in said target computation is different from the precision mode in said caller computation.

25. The program of claim 23, further comprising the steps of: detecting a portion to be compiled in said target computation, in which the computation is executed in an excessive precision; and replacing the detected portion with a single precision computation.

26. The program of claim 23, further comprising the steps of: performing code analysis with respect to said target computation to be compiled; dividing the target computation into regions for executing single precision computations and regions for executing double precision computations based on the results of the code analysis; and setting the computation precision for each of said regions to generate the machine language code.

---

Description

---

PRIORITY

This application claims priority to an application entitled "A PROGRAM CONVERSION METHOD, DATA PROCESSING APPARATUS AND PROGRAM USING THE METHOD" filed in the Japan Patent Office on Jul. 31, 2002 and assigned Serial No. 2002-224207, the contents of which are hereby incorporated by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to a technique for rapid program compilation, and more particularly to a method for providing accurate floating-point computation.

2. Description of the Related Art

In a floating-point computation in Java.RTM. (a registered trademark of Sun Microsystems Incorporated), precisions for a single precision computation and a double precision computation are defined by a language specification (24 bits mantissa and 8 bits exponent for the single precision computation, and 53 bits mantissa and 11 bits exponent for the double precision computation, respectively).

With CPUs of IA32 (Intel Architecture-32) architecture (the x86 family of Intel Corporation and compatible CPUs), it has been required to take either of the following approaches in order to execute both single precision computations and double precision computations:

(Approach 1) switching the CPU's floating-point computation mode by setting the floating-point control word (hereinafter, referred to as FCW); or

(Approach 2) executing the computation in the double precision mode, and if a computation result is to be obtained in single precision, storing the value on a floating-point register into a memory in single precision and reading it to degrade the computation precision.

A method executing the single precision computation is considered by way of example. Generally, this method may be called in the double precision computation CPU mode (hereinafter, referred to as a double precision mode) or in the single precision computation CPU mode (hereinafter, referred to as a single precision mode). If the method is called in the single precision mode, it is more efficient to execute the code assuming the single precision mode. If the method is called in the double precision mode, it is necessary to prevent loss of computation precision according to Approach 1 or Approach 2 described above. One means of improving efficiency is to analyze the program to compare execution costs for the case using Approach 1 and for the case using Approach 2, and to execute the faster Approach, i.e. the one with less overhead (this analysis is hereinafter referred to as an inter-method analysis).

In a separate compilation environment for compiling a method having a high execution frequency, as in a dynamic compiler such as a JIT (Just In Time) compiler for Java.RTM., it is not known whether the method being compiled will be called in the single precision mode or in the double precision mode. Therefore, for example, the precision mode is fixed as double precision at method boundaries (that is, all methods are called in the double precision mode), and if the single precision computation is executed, a code is generated according to the above described cost calculation.

A technique for the above described cost calculation and code generation is described in the following prior art document, incorporated here by reference:

M. Paleczny, C. Vick, and C. Click. The Java.RTM. HotSpot Server Compiler. The USENIX Association: Proceedings of the Java.RTM. Virtual Machine Research and Technology Symposium (JVM '01).

The above described prior art has a disadvantage in that the execution cost is high in either Approach 1 or Approach 2 and large overhead is incurred.

Specifically, in the case of Approach 1, a switch instruction for the FCW, with a form of, for example, (fldcw word ptr [mem]), is a high cost instruction. In addition, once the FCW is switched, it is necessary to switch the FCW again before and after a method call in that range and return the mode to the double precision mode as a standard, which may cause further overhead.

In the case of Approach 2, instructions for writing into and reading from a memory are executed whenever the single precision computation is executed; memory access may cause overhead and degrade overall execution performance.

In addition, in the dynamic compilation environment, an inter-method analysis may, for example, have excessive compilation time overhead, and so may not be effective for choosing a calculation Approach. Moreover, since new classes can be loaded dynamically, an analysis result may become invalid later, thus wasting computation resources.

Therefore, it is an object of the present invention to provide an efficient mechanism for preventing loss of precision for both a single precision computation and a double precision computation in a floating-point computation, while avoiding execution overhead and invalidation of the analysis result.

SUMMARY OF THE INVENTION

In order to achieve the above described object, a first embodiment of the present invention is realized as a program conversion method, as described below, for generating a specialized machine language code by controlling a computer to compile a program. The program conversion method includes the following steps: a first step of, when a method constituting the program is executed, storing information into a memory regarding whether the method is called in a double precision mode or a single precision mode in a floating-point computation; a second step of, if a default precision mode is selected to be either the double precision mode or the single precision mode in the floating-point computation in the program, when a target method is being compiled, examining a frequency with which the target method is called in a non-default precision mode, based on the information stored in the memory; and a third step of generating and storing in the memory a specialized machine language code corresponding to the call to the target method in the non-default precision mode, based on the information on the frequency with which the target method is called in the non-default precision mode.

The frequency with which the method is called in the non-default precision mode may be determined, for example, by counting how many times the method is called in the non-default precision mode in a runtime of the program, and by comparing the counter value with a predetermined threshold value. It is preferable to generate the specialized machine language code only when the execution cost can be reduced by running the target method in the non-default precision mode.

In a system in which it is standard to perform method calls in the double precision mode, such as Java.RTM., the single precision mode is the non-default precision mode.

The number of target methods for which the specialized machine language code is generated can be increased when the specialized machine language code is generated, as a preprocess, by detecting a portion of the target method to be compiled in which the computation is executed in an excessive precision, and by replacing the portion of the target method with a single precision computation. Alternatively, it may be possible to generate better code with more efficient control of the precision mode if the preprocess includes executing a program analysis with respect to the target method being compiled, and dividing the method into regions for single precision computations and regions for double precision computations.

Another embodiment of the program conversion method according to the present invention includes the following steps: a first step of, with respect to a target method to be compiled, setting a computation precision mode depending on a floating-point precision mode in a caller method that calls the target method, and generating and storing a machine language code in a memory; a second step of examining a relation between the target method and the caller method; and a third step of generating an auxiliary machine language code depending on the result of the examination and adding the auxiliary machine language code to the machine language code stored in the memory.

More particularly, the second step examines whether the caller method is in a double precision mode or in a single precision mode, and the third step generates and adds the auxiliary code for matching the precision mode, if the precision mode in the caller method is different from the precision mode in the target method.

The number of target methods for which the specialized machine language code is generated can be increased if the specialized machine language code is generated, as a preprocess, by detecting a portion of the target method to be compiled in which the computation is executed in an excessive precision, and by replacing the portion of the target method with a single precision computation. Alternatively, it may be possible to generate better code for each portion of the program, on a finer level of code fragment than the method level, if the preprocess includes executing a program analysis with respect to the target method being compiled, and dividing the method into regions for single precision computations and regions for double precision computations.

The present invention for achieving the above described objectives can also be realized as a data processing apparatus configured as follows. The data processing apparatus is provided with a compiler for compiling a program on a method by method basis, and a program execution unit for executing the program in an interpreter and in a code compiled in the compiler. The compiler generates a first version of code for the target method in a default precision mode which may be either the double precision mode or the single precision mode in a floating-point computation. If the target method satisfies a certain condition, the compiler generates a second version of code for the target method in the non-default precision mode.

The present invention can also be realized as a data processing apparatus provided with: code generation means for, with respect to a target method to be compiled, setting a computation precision depending on a precision mode in a floating-point computation in a caller method that calls the target method, and generating a machine language code; and means for adding auxiliary code, based on a relation between the precision mode in the target method and the precision mode in the caller method, for matching the precision mode, and for adding the auxiliary code to the machine language code generated by the code generation means.

The present invention is also realized as a program for controlling and causing a computer to execute a process corresponding to each step in the above described program conversion method, or as a program for operating the computer as the data processing apparatus described above. Either of these programs may be provided by storage in and distribution of a magnetic disk, an optical disk, a semiconductor memory, or other storage media, or by delivery via a network.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates a configuration of a computer system for realizing a method for preventing loss of precision in a floating-point computation according to a first embodiment of the present invention;

FIG. 2 shows a data structure generated by a runtime routine for realizing the operation according to the first embodiment, showing the data structure in an initial state;

FIG. 3 shows the data structure generated by the runtime routine for realizing the operation according to the first embodiment, showing a typical data structure after a first compilation;

FIG. 4 shows the data structure generated by the runtime routine for realizing the operation according to the first embodiment, showing the data structure in the case in which a specialized object code is generated;

FIG. 5 shows a data structure generated by a prior-art runtime routine;

FIG. 6 is a flow chart showing a process of performing specialization according to the first embodiment of the present invention;

FIG. 7 illustrates a code generation in the case that a caller method which calls a target method to be compiled has been already compiled, in a second embodiment of the present invention;

FIG. 8 illustrates code generation in the case that the caller method which calls the target method to be compiled has not been compiled yet, in the second embodiment;

FIG. 9 is a flow chart illustrating a compilation procedure according to the second embodiment of the present invention;

FIG. 10 illustrates a function of a compiler in a third embodiment of the present invention;

FIG. 11 shows an excessive-precision computation table used in the third embodiment;

FIG. 12 is a flow chart illustrating a process flow in which an excessive-precision optimization unit determines whether it is an excessive precision with respect to a floating point computation;

FIG. 13 is a flow chart illustrating a process flow for replacing the computation determined to be an excessive-precision computation with a lower precision computation;

FIG. 14 shows an example of a pseudo-code for converting a double precision computation, which is an excessive-precision computation with respect to a specific floating-point computation, into a single precision computation, as in the third embodiment;

FIG. 15 shows an example of a pseudo-code for converting a double precision computation, which is an excessive-precision computation with respect to a specific floating-point computation, into a single precision computation, as in the third embodiment;

FIG. 16 illustrates the function of the compiler in a fourth embodiment of the present invention;

FIG. 17 is a continuation of the flow chart illustrating a process flow in which a precision region analysis unit retrieves the single precision regions and determines a precision mode in the floating-point computation with respect to a target method, in the fourth embodiment;

FIG. 18 is the flow chart illustrating the process flow in which the precision region analysis unit retrieves the single precision regions and determines the precision mode in the floating-point computation with respect to a target method, in the fourth embodiment;

FIGS. 19(A) and 19(B) show an example of a source program and its corresponding basic blocks; and

FIG. 20 shows an example of a management table used in the fourth embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The invention proposes the following two approaches to prevent loss of precision in a floating-point computation in a code generated by compilation and to reduce overhead such as switching a precision mode setting in a FCW (floating-point control word) or storing to and reloading from a memory. A first embodiment is proposed in which a code generation is executed with either single precision mode or double precision mode as a default precision mode, the program is executed, and a specialized code corresponding to a non-default precision mode is generated for those methods which are frequently called in the non-default precision mode. A second embodiment is proposed in which, according to the precision mode of a caller method which calls a target method to be compiled, code generation is executed so as to optimize the target method.

To realize the above described two approaches more effectively, as a preprocess of these code generations, the present invention also proposes a third embodiment for replacing computations in the method and a fourth embodiment for analyzing codes in the method.

Application of the present invention to a JIT compiler for Java.RTM. will be described by way of example in the following embodiments. That is, the double precision mode is the default precision mode at method boundaries, and the program conversion method is executed if the method can be called in the single precision mode.

1. First Embodiment

In the first embodiment, in the case where a target method is compiled once the program is actually run, if the single precision mode is selected as the default for the target method, and the target method is called frequently enough from other methods where the single precision mode is selected as default, the program conversion method is executed for the target method. An efficient code can thus be generated without switching the FCW mode or having to execute memory write and read instructions to prevent loss of precision.

FIG. 1 illustrates a configuration of a computer system for realizing the floating-point computation with no loss of precision according to the first embodiment.

Referring to FIG. 1, the computer system in this embodiment is provided with a compiler 100 for compiling a source program (an input code), a program execution unit 200 for executing an object program (an output code) compiled by the compiler 100 to perform various processes, and a memory 300. The compiler 100 and the program execution unit 200 are realized in a CPU programmably controlled in the computer system, where the computer system may be, for example, a personal computer or a workstation. The memory 300 is a main memory in the computer, and is realized with, for example, a RAM. The memory 300 stores a program for controlling the CPU to execute the compiler 100, a program to be compiled (hereinafter, referred to as an executable program), and a runtime routine 310 to be used for execution of the executable program. The program stored in the memory 300 may be saved in a magnetic disk or other external storage device as necessary.

In FIG. 1, the compiler 100 takes the input code written in a byte code to process it, and generates and outputs the output code in a machine language. This input code is generated by a code generation device 400, or comes from a storage device 500 which stores the input code generated by the code generation device 400, or from the code generation device 400 or the storage device 500 residing on a network 600, via the network 600. The output code generated by the compiler 100 is executed by the program execution unit 200. The program execution unit 200 executes not only an object code (a machine language code) of the executable program compiled by the compiler 100, but also executes the executable program with an interpreter. When the executable program is executed, the program execution unit 200 collects its execution profile and stores it in the memory 300.

An operation according to this embodiment will be described below in detail with reference to FIGS. 2 to 5. The operation is realized in the runtime routine 310 stored in the memory 300.

FIGS. 2 to 4 show data structures generated by a runtime routine for realizing the operation according to this embodiment. FIG. 2 shows an initial state, FIG. 3 shows a typical data structure after a first compilation, and FIG. 4 shows the data structure in the case where the program conversion method is executed. In contrast, FIG. 5 shows a data structure generated by a prior-art runtime routine.

As shown in FIGS. 2 and 5, if methods 11 and 12 constituting the program are executed and a method call "call target" (a call instruction) is performed, the program execution unit 200 first refers to a corresponding entry in a method block 20. Then, from a registration point for a code address of a target method to be called (hereinafter, referred to as a target method) which is stored in the entry in the method block 20, via a gate code 31 corresponding to the entry, and via runtime routine 40, the program execution unit 200 executes the target method in the interpreter or in the compiled code. After executing the target method, the program execution unit 200 returns to the caller methods 11 and 12.

FIG. 5 shows the prior art data structure; in contrast, in the embodiment of the present invention shown in FIG. 2, in addition to a normal entry 21 (Code Ptr1) which is also shown in FIG. 5, a single precision mode dedicated entry 22 (Code Ptr2) is provided as the registration point for the code address of the target method in the method block 20. Depending on the current mode of the FCW at each call site of the caller methods 11 and 12, either the normal entry 21 or the single precision mode dedicated entry 22 is called accordingly. That is, if the target method is called from the caller method 12 where the single precision mode is selected, the newly provided single precision mode dedicated entry 22 is called.

In addition, as a gate code 32 corresponding to the single precision mode dedicated entry 22, the following codes are provided for: 1) setting the FCW to the double precision (fldcw f2d); 2) incrementing a dedicated counter (a single precision mode counter or F-mode counter) (inc counter); and 3) jumping to the normal gate code entry (jmp Gate).

In the method call in the single precision mode, it is not necessary to jump to a single precision dedicated code. That is, the called target method may be a method where the double precision mode is selected. Therefore, as shown in the caller method 12, at a return address right after a call instruction (call target), that is, after the called target method is executed, an instruction is generated for restoring the FCW to the single precision mode (fldcw d2f). A value of the single precision mode counter is retained in the memory 300 and referred to by the compiler 100 in the compilation as a means for obtaining information regarding whether the target method is called in the double precision mode or in the single precision mode, as will be described below.

Referring to the prior art shown in FIG. 5, in the method call in the single precision mode, according to a principle of fixing the double precision mode at method boundaries, as seen in the caller method 12, the FCW is switched to the double precision mode (fldcw f2d) before the call instruction (call target), and the FCW is switched back to the single precision mode (fldcw d2f) after the call instruction (call target).

In the state shown in FIG. 2, for the method call in the single precision mode, the FCW is set to the double precision mode at a method boundary, as in the prior art, by the gate code 32, and is restored to the single precision mode again after returning to the call point via a normal path. However, in this state, the call path under the single precision mode will suffer overhead such as incrementing the counter or performing the jump instruction in the gate code 32.

Next, the case will be considered where the target method called from the caller methods 11 and 12 is compiled. If the program is repeatedly executed and a counter value for counting the execution frequency of the target method exceeds a predefined threshold, the target method is compiled by the compiler 100, the compiler 100 acting as code generation means to generate the object code, and the execution of the target method is transferred from interpretation to execution of the compiled code.

In the compilation by the compiler 100, by checking the value of the single precision mode counter retained in the memory 300 and comparing it with the counter value for transferring from the interpreter to the compiler, it is possible to know which is more frequent between the single precision or the double precision in the settings of the FCW modes in the callers.

If the value of the single precision mode counter is small, then assuming that the method boundary is in the double precision mode, a generalized object code (general version) 50 is generated (as in the prior art). FIG. 3 shows the data structure in this case.

The generalized object code 50 is registered in the normal entry 21 of the code address in the method block 20. In addition, the jump instruction in the gate code 32 corresponding to the single precision mode dedicated entry 22 is rewritten such that the generalized object code 50 is assigned as a target of the jump address.

Below, recompilation is considered where the target method is a frequently called method (hot method) at runtime.

With respect to the call to the target method, if the value of the single precision mode counter in the gate code 32 corresponding to the single precision mode dedicated entry 22 is large enough, it is determined that the frequency of calls in the single precision mode (that is, from the caller method 12) is high. When the target method satisfies a condition to compile using the single precision mode as the base precision mode, recompilation will be executed to generate a specialized object code version for a direct call in the single precision mode. The condition may be defined arbitrarily: for example, a threshold may be set where a frequency of calling in the single precision mode is larger than a frequency of calling in the double precision mode. FIG. 4 shows the data structure in the case where a specialized object code (special version) 60 to be used for the direct call in the single precision mode is generated by the recompilation.

The generated specialized object code 60 is registered in the single precision mode dedicated entry 22 of the single precision dedicated code address in the method block 20. In addition, the entry code in the gate code 32 is rewritten to an unconditional jump instruction so as to jump directly to the specialized object code 60. Thereby, at a virtual method call site in the single precision mode, it may be possible to call a newly registered code automatically. In addition, at a static method or a nonvirtual method call site where the gate code 32 has been called directly, the specialized object code 60 will be called directly after the next invocation, according to an existing back patching mechanism.

Finally, the specialized object code 60 dedicated to the single precision mode slides a pointer of the return address by a fixed length byte, thereby skipping the instruction for resetting the FCW to the single precision mode (fldcw d2f) placed immediately after the call instruction (call target) in the caller method 12.

In addition to a procedure generating the specialized object code 60 in the recompilation, depending on an execution state of the target method, when the target method is compiled for the first time from the initial state as shown in FIG. 2, if the value of the single precision mode counter is already large enough (for example, if it exceeds 90 percent of the threshold for transferring from the execution in the interpreter to the execution in the compiler), the specialized object code 60 for the single precision mode may be generated without first generating the generalized object code 50 which assumes the call in the double precision mode. In this case, in order to keep the possibility of executing the normal compilation (the generation of the generalized object code 50) after executing the compilation generating the specialized object code 60, the value of the counter for transferring from the execution in the interpreter to the execution in the compiler needs to be adjusted (for example, by resetting the counter to a value of the threshold minus the F-mode counter value).

FIG. 6 is a flowchart showing a process of specializing the program according to this embodiment, as described above with references to the data structures shown in FIGS. 2 to 4.

As shown in FIG. 6, if a frequency with which a predetermined method (the target method in the above description) is called is high enough (the hot method is detected), and the target method is compiled, then the compiler 100 first examines whether the value of the single precision mode counter in the gate code 32 exceeds the threshold (that is, whether a preset condition is satisfied) (steps 601 and 602).

If the value of the single precision mode counter exceeds the threshold, the compiler 100 then determines whether it is possible to compile the target method using the single precision mode as the base mode (step 603). This may be determined by counting the number of single precision computations, double precision computations, and method call instructions, and analyzing the entire target method to calculate whether it is less expensive in terms of overhead to select the single precision mode as the base mode and switch the FCW to the double precision mode as necessary, or to select the double precision mode as the base mode and switch the FCW to the single precision mode as necessary (or to prevent loss of precision using the memory).

If it is determined that it is possible to compile the target method using the single precision mode as the base mode, the compiler 100 then generates the specialized object code 60 for calling in the single precision mode (step 604). Then the compiler 100 registers the specialized object code 60 in the single precision mode dedicated entry 22 in the method block 20 (step 605), converts (fldcw f2d) and (inc counter) to (nop) (that is, deletes (fldcw f2d) and (inc counter)) in the single precision dedicated gate code 32, rewrites the jump address to an address of the specialized object code 60, and completes the process (step 606).

On the other hand, if the value of the single precision mode counter does not exceed the threshold at step 602, or if it is determined that it is not possible to compile the target method using the single precision mode as the base mode in step 603, the compiler 100 generates the generalized object code 50 assuming the call in the double precision mode (step 607) and registers the generalized object code 50 in the normal entry 21 in the method block 20 (step 608).

Next, the compiler 100 examines whether the single precision dedicated object code 60 has already been generated for the target method (step 609). If the specialized object code 60 has not been generated yet, in order to use the generalized object code 50 thereafter, the compiler 100 rewrites the jump target address in the single precision dedicated gate code 32 from the gate code 31 to an address of the generalized object code 50, and completes the process (step 610). On the other hand, if the single precision dedicated object code 60 (the specialized object code) has been already generated, the compiler 100 completes the process since the specialized object code 60 may be used with respect to the call in the single precision mode.

As described above, according to the first embodiment, the specialized code dedicated to the single precision is generated with respect to the methods frequently called from the caller method in the single precision mode when the double precision mode is selected as default. Then, by calling the specialized code directly from the caller method in the single precision mode, it is possible to reduce a redundant execution of expensive instructions such as switching the FCW precision mode or writing into and reading from the memory.

In addition, since the specialized code is generated based on an execution history of the program with respect to the methods frequently called from the caller method in the single precision mode, unnecessary increase in code size can be avoided.

2. Second Embodiment

In the second embodiment, the target method to be compiled is called in the precision mode of the caller method. On compiling the target method, the compiler assumes the precision mode at the entry and the exit of the target method to be a calling precision mode (the precision of the caller method). The execution of the generated code is to be started in the assumed precision mode and ended in the same precision mode. A method of preventing loss of precision in the floating-point computation according to the second embodiment is realized in the computer system configured as shown in FIG. 1, as in the first embodiment.

In a program for executing the single precision computations, it is often the case that the methods for executing the single precision computations call each other. Therefore, if a method executing in the single precision mode calls another method for executing the single precision computations (hereinafter, this type of call will be referred to as a target status), overhead can be avoided if the call is performed without switching the FCW precision mode or writing into and reading from the memory.

If, as in Java.RTM., the double precision mode is selected as default at method boundaries, then it is preferable to avoid the following four kinds of overhead due to redundant mode conversions in the target status:

when a method A calls a method B in the target status: a) changing the mode from single precision to double precision in the method A; b) changing the mode from double precision to single precision at the entry to the method B; and

when the control is returned from the method B to the method A: c) changing the mode from single precision to double precision in the method B; d) changing the mode from double precision to single precision in the method A.

In this embodiment, as described above, the target method is called in the precision mode of the caller method. Therefore, if a single target method is called by different caller methods in different precision modes, the multiple versions of code corresponding to the different precision modes are generated with respect to the single target method. If it is necessary to restrict the multiple version code generation to limit, for example, code size or compile time, then once the target method is compiled in any precision mode, thereafter, even when the method is called in a different precision, the code corresponding to the different precision may not be generated. In that case, a target code will be called via a code for matching the precision. In addition, with respect to compilation operating under such restrictions, the first embodiment may also be applied.

As described above, in this embodiment, when the compiler 100 as the code generation means compiles the target method, it assumes that the call is executed in the precision mode of the caller method, and generates an optimized code specifically for the target method. If the call precision is double precision, the compiler 100 compiles assuming the double precision mode (the code generated in a compilation assuming the double precision mode is referred to as a double precision code), and if the call precision is single precision, the compiler 100 compiles assuming the single precision mode (the code generated in a compilation assuming the single precision mode is referred to as a single precision code). If the double precision computations and the single precision computations are mixed, the compiler 100 compiles by combining the approaches for preventing loss of precision using switching of the precision mode (Approach 1, described above) or writing and reading in the memory (Approach 2, described above).

In addition, with respect to the compiled target method, depending on the precision mode assumed when generating a compiled code, the compiler 100 registers a flag indicating the single precision code or the double precision code (a default precision mode) in the compiled code of the target method or in the runtime routine. Furthermore, if the switching of the precision mode (Approach 1) is executed with respect to the compiled method, the compiler 100 registers a section in which the precision mode is changed and also registers the precision mode.

If there is only the single precision code in the compiled code, and the compiled code may be called by a method executed in the interpreter, it is assumed that the interpreter operates constantly in the double precision mode, and the precision mode is switched before and after the call. Then, the precision mode is switched to the single precision mode before the compiled code is executed, and the precision mode is switched back to the double precision mode on returning from the compiled code.

A target method may be categorized as either a static method or a virtual method. In each case, either the single precision code is generated or the double precision code is generated. Further, if the target method is the virtual method and is called virtually, then it is either called from the single precision code or it is called from the double precision code. Therefore, with respect to the target method, the compiled code for the case of being called from the single precision code and the compiled code for the case of being called from the double precision code are generated for their respective cases, and one of the codes is selected depending on an execution status of the program.

Next, code generation by the compiler 100 will be further described by dividing it into specific cases.

In a separate compilation environment of the compiler 100, two possibilities are considered involving the target method to be compiled (referred to for this description as a Method B) and the caller method (referred to for this description as a Method A), as follows: Case 1: Method A has been already compiled, and now Method B is being compiled; and Case 2: Method A has not been compiled yet, and now Method B is being compiled.

With respect to the Case 1, the compiler 100 executes code generation as follows.

If the Method A is the double precision code, when the Method B contains the double precision computations only, the compiler 100 compiles in the double precision mode (the double precision code); when the Method B contains the single precision computations only, the compiler 100 compiles in the single precision mode (the single precision code). If the double precision computations and the single precision computations are mixed, the compiler 100 calculates the execution cost and compiles either in the double precision code or the single precision code, and as necessary, prevents loss of precision using the existing approaches (Approach 1 and Approach 2, described above) such as switching of the precision mode or writing and reading in the memory, or applies the fourth embodiment as will be described later.

On the other hand, if the Method A is the single precision code, when the Method B contains the single precision computations only, the compiler 100 compiles in the single precision mode (the single precision code). Otherwise, the compiler 100 compiles in the double precision mode (the double precision code), and as necessary, prevents loss of precision using the existing approaches (Approach 1 and Approach 2, described above) by combining switching of the precision mode and writing and reading in the memory, or applies the fourth embodiment as will be described later.

FIG. 7 conceptually illustrates code generation in the above described case.

With respect to the Case 2, the compiler 100 executes code generation as follows.

When the Method B contains the double precision computations only, the compiler 100 compiles in the double precision mode (the double precision code); when the Method B contains the single precision computations only, the compiler 100 compiles in the single precision mode (the single precision code). If the double precision computations and the single precision computations are mixed, the compiler 100 calculates the execution cost and compiles either in the double precision code or the single precision code, and as necessary, prevents loss of precision using the existing approaches by combining the switching of the precision mode and the writing and reading in the memory. Whether the compiler 100 generates the double precision code or the single precision code depends on the way of combining the switching of the precision mode and the writing and reading in the memory. Alternatively, the fourth embodiment may be applied as will be described later.

Since of Method A is executed by the interpreter, and the interpreter is typically executed with fixed precision mode, the precision mode is switched as necessary in a glue code for calling the compiled code. That is, if the interpreter is executed in the double precision mode, when Method B is the double precision code, the compiled code is called without switching the precision mode. On the other hand, when Method B is the single precision code, in the glue code, the precision mode is switched from the double precision mode to the single precision mode, then the compiled code is called, and the precision mode is switched back to the double precision mode on returning to Method A.

FIG. 8 illustrates the code generation in the above described case.

FIG. 9 is a flowchart illustrating a compilation procedure as described above.

As shown in FIG. 9, if the compiler 100 detects and compiles a hot method, it generates the compiled code depending on the type of the computations (the single precision computations only, the double precision computations only, or a mixture of both) in the target method to be compiled, and temporarily stores the code in the memory 300 (steps 901 and 902). Next, the compiler 100 examines a relation between the target method and the caller method which calls the target method (step 903), generates an auxiliary code depending on the determined relation, as described in FIGS. 7 and 8, and adds the auxiliary code to the code stored in the memory 300, which is generated in step 902. That is, the compiler 100 inserts the code for switching the precision mode into the code of the target method or the code of the caller method, or alternatively into the glue code if the caller method has not been compiled yet (step 904).

As described above, according to the second embodiment, if the target method is compiled, assuming that the compilation is started and ended in the same precision mode as in the caller method, code generation can be performed to optimize the target method to be compiled. Therefore, it is possible to reduce a redundant switching of the precision mode which is caused by selecting a default precision mode (for example, the double precision mode) at method boundaries.

3. Third Embodiment

In the above described first embodiment, the code in which the single precision mode is selected as the base mode is generated for the methods frequently called in the single precision mode during execution. In the second embodiment, the code is generated by setting the computation precision depending on the type of the computations within the target method. However, in some programs, there are, for example, methods where the code has to be generated in the double precision mode since the methods were originally written to execute the computations in the double precision mode even though the computations themselves may be executed sufficiently in the single precision mode, or methods where the computations requiring the double precision mode appear sporadically though most of the computations are in the single precision mode. With respect to such methods, the code can not be generated in the single precision mode using the first and second embodiments.

Therefore, the third embodiment further improves the effectiveness of the code generation based on the first and second embodiments, by replacing the computations in the method as a preprocess in compiling the method.

In this embodiment, with respect to the method for which the code is generated in the double precision mode, since the method is written to execute the computations in the double precision mode even though the computations themselves may be sufficiently executed in the single precision mode, the computations in the target method are replaced. This code rewriting process is referred to as an excessive-precision optimization (XPO).

There are various possible causes for the code being generated in an excessive double precision mode, for example, the Method API provided by Java.RTM. is only for double precision computation functions, or a programmer may specify an excessive precision when writing the method. In this embodiment, a precision bit number of a computation result is propagated based on a relation between definition and use (a def-use relation) of a function. Then, if the same result may be obtained in the single precision computation, the double precision computation in the target method is replaced with the single precision computation. A useless memory write for degrading the computation precision can thus be eliminated.

The excessive-precision optimization for preventing loss of precision in the floating-point computation in the third embodiment is realized in the computer system configured as shown in FIG. 1, as in the first embodiment.

FIG. 10 is a block diagram illustrating a function of the compiler 100 in this embodiment.

As shown in FIG. 10, the compiler 100 of this embodiment is provided with an excessive-precision optimization unit 110 for executing the excessive-precision optimization process with respect to the target method to be compiled, and a code generation unit 120 for converting a binary code of the target method on which the excessive-precision optimization process is applied into a machine language code. The excessive-precision optimization unit 110 and the code generation unit 120 are virtual software blocks which are realized in the CPU controlled by the program stored in the memory 300. It should be noted that an example configuration specific to this embodiment is shown in FIG. 10. It should be appreciated that, for example, in addition to the configuration shown in the figure, means for parsing the binary code of the target method to be compiled or means for executing various optimization processes other than the excessive-precision optimization according to this embodiment may also be provided.

The excessive-precision optimization unit 110, which is code rewriting means, detects a portion of the target method to be compiled in which an excessive-precision computation (the double precision computation) is executed, and replaces the portion of the target method with an appropriate lower precision computation (the single precision computation), as the preprocess of the code generation by the code generation unit 120. Specifically, the excessive-precision optimization unit 110 first determines whether the computation is the excessive precision with respect to each of the double precision computations (functions) in the target method, and replaces the computation which is determined to be the excessive-precision computation with the single precision computation. At this point, it is possible to execute a data-flow analysis in the compilation and determine mechanically whether the computation is the excessive-precision computation or not with respect to all of the double precision computations detected. Also, it is possible to, for example, refer to the execution profile stored in the memory 300, collected through the execution of the method, and determine whether the computation is the excessive-precision computation or not with respect to the double precision computations which are frequently executed.

A certain floating-point computation C is determined to be the excessive-precision computation if it satisfies two conditions as follows:

Condition (1) A function F (a code sequence for processing input in the computation C and providing output as a result, including both one instruction computation and a function calling another method) may provide the same result even by computing it in a lower precision mode (the single precision mode) if input values are certain restricted values (for example, input values whose mantissa can be represented in the single precision); and

Condition (2) all of the input values are the restricted values.

This embodiment provides an excessive-precision computation table 320 in which the floating-point computations satisfying these two conditions are listed, and uses this table to determine whether the computation is the excessiv