Globally inline a callee with high cost-effectiveness on the basis only of profile information in a call graph

A mechanism is provided to globally inline a callee with high cost-effectiveness on the basis only of profile information in a call graph, without looking through all call-graph edges. The mechanism provides a technique for inlining. An inline cost-effectiveness ratio for the callee reachable from a caller to be compiled is calculated. Calculating the inline cost-effectiveness ration includes using a ratio of a frequency of calls to the callee to a total of call frequencies as effectiveness and using a ratio of a code size of the callee to a total size of inlinable code as cost. A determination is made as to whether to inline the callee by comparing the inline cost-effectiveness ratio with a predetermined threshold. The callee is inlined into a source code in response to determining that the callee method is to be inlined.

BACKGROUND

The present invention relates to a compiler technique, and particularly relates to inlining which is a compiler optimization technique.

Inlining is also referred to as inline expansion or inline function expansion, and is one of most important optimization techniques for compilers. Inlining is a technique in which optimization is achieved by expanding code for a function called by a function caller and preventing control from being transferred to the function.

Function inlining is performed by inserting a directive, such as an inline keyword, into source code during coding.

For example, inlining can (1) reduce overhead associated with calls and returns, (2) expand the range of compiler optimization, and (3) improve spatial locality of code. Inlining is particularly effective for functions which are small and frequently called.

By default, a compiler can automatically determine whether code is to be inline-expanded.

Japanese Patent Application Publication No. 6-202875 describes a compiler that performs optimization through inline expansion. The compiler includes control flow weighting means for estimating the number of executions of each partial control flow included in a control flow on the basis of a result of analysis by control flow analyzing means, and weighting each partial control flow on the basis of the number of executions; and object generating means for determining, with reference to a result of the weighting performed by the control flow weighting means, the necessity of inline expansion of a function called by each function call, and generating an object program reflecting the determination.

Japanese Patent Application Publication No. 11-212797 describes a program converting method for converting a source program written in a programming language to an object program written in a language executable by a computer or processor, characterized in that the object program is generated by changing indirect calling code to direct calling code, wherein, in the indirect calling code, on the basis of information about a procedure, function, or subroutine obtained in the process of converting the source program to the object program, identification information of the procedure, function, or subroutine is assigned to a specific variable at a point in a program, and the procedure, function, or subroutine is indirectly called by using the variable at another point, whereas in the direct calling code, the procedure, function, or subroutine is directly called at a point in the program.

Japanese Patent Application Publication No. 2001-188681 describes an inline expansion method that includes the steps of translating source code into object code without inline-expanding at least some of functions included in the source code; selectively changing the object code; executing the object code and measuring the number of calls and the processing time of the at least some of the functions; and selectively inline-expanding the at least some of the functions included in the source code with reference to the number of calls and the processing time.

Japanese Patent Application Publication No. 11-306026 describes a code optimization method related to a CPU having a plurality of instruction sets. The code optimization method includes a cost calculating step of calculating a cost of program code to be optimized on the basis of a cost evaluation table, and storing a result of the calculation; and an optimization-instruction-set selecting step of selecting an optimum instruction set from the stored result of the calculation. In this code optimization method, the cost calculating step inline-expands the program code, calculates a cost of the inline-expanded program code on the basis of the cost evaluation table, and stores a result of the calculation.

Japanese Patent Application Publication No. 2004-62234 describes a compile program running on a computer and converting a source program including a function call to object code. In the compile program, if a function to be inline-expanded is called from the same function at a plurality of points, expansion code for the callee function is shared by using a branch instruction from the call points.

J. Cavazos and M. F. P. O'Boyle, “Automatic Tuning of Inlining Heuristics”, Proceedings of the 2005 ACM/IEEE SC Conference, page 14, November 2005; K. Hazelwood and D. Grove, “Adaptive Online Context-Sensitive Inlining”, Proceedings of the international symposium on Code generation and optimization”, feedback-directed and runtime optimization, pages 253-264, 2003; M. Arnold, S. Fink, V. Sarkar, and P. Sweeney, “A comparative study of static and dynamic heuristics for inlining”, ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization, 2000; S. Kulkarni, J. Cavazos, C. Wimmer, and D. Simon, “Automatic construction of inlining heuristics using machine learning”, Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, 2013; and T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani, “Design and Evaluation of Dynamic Optimizations for a Java Just-In-Time Compiler”, ACM Transactions on Programming Languages and Systems, Vol. 27, No. 4, pages 732-785, July 2005 each describe an inlining technique for dynamic compilers.

P. Zhao and J. N. Amaral, “To Inline or Not to Inline? Enhanced Inlining Decision”, 16th Workshop on Languages and Compilers for Parallel Computing, 2003 describes an inlining technique based on temperature heuristics.

SUMMARY

In one illustrative embodiment, a method is provided for inlining. The illustrative embodiment calculates an inline cost-effectiveness ratio for a callee reachable from a caller to be compiled. In the illustrative embodiment, calculating the inline cost-effectiveness ratio includes using a ratio of a frequency of calls to the callee to a total of call frequencies as effectiveness, and using a ratio of a code size of the callee to a total size of inlinable code as cost. The illustrative embodiment determines whether to inline the callee by comparing the inline cost-effectiveness ratio with a predetermined threshold. The illustrative embodiment inlines the callee into a source code in response to determining that the callee is to be inlined.

DETAILED DESCRIPTION

Embodiments of the present invention will be described with reference to the drawings. Throughout the drawings, the same reference numerals are used to refer to the same components unless otherwise specified. It is to be understood that the embodiments of the present invention are provided to describe preferred aspects of the present invention, and are not intended to limit the scope of the present invention to those described herein.

A computer that can be used in the embodiments of the present invention is not limited to a specific one, as long as it is a computer capable of performing inlining. The computer may be, for example, a mainframe computer, a server computer, a desktop computer, a notebook computer or integrated personal computer, or a tablet terminal or smartphone (e.g., a Windows (registered trademark)-based, Android (registered trademark)-based, or iOS-based tablet terminal or smartphone).

FIG. 1illustrates a computer that is according to, or that can be used in, an embodiment of the present invention.

A computer101includes a CPU102and a main memory103, which are connected to a bus104. The CPU102is preferably based on a 32-bit or 64-bit architecture. The CPU102may be, for example, a Core (trademark) i-series, Core (trademark) 2 series, Atom (trademark) series, Xeon (registered trademark) series, Pentium (registered trademark) series, or Celeron (registered trademark) series processor from Intel Corporation; an A-series, Phenom (trademark) series, Athlon (trademark) series, Turion (registered trademark) series, or Sempron (trademark) processor from Advanced Micro Devices (AMD) Inc.; or a Power (trademark) series processor from International Business Machines Corporation.

A display106, such as a liquid crystal display (LCD), can be connected via a display controller105to the bus104. The liquid crystal display may be a touch panel display or a floating touch display. The display106can be used to display, through an appropriate graphical interface, objects that can be displayed by operation of software running on the computer101(e.g., a computer program according to the embodiment of the present invention or various computer programs running on the computer101).

A disk108, such as a hard disk or a solid state drive (SSD), can be connected to the bus104, for example, via a SATA or IDE controller107.

A drive109, such as a CD, DVD, or ED drive, can be optionally connected to the bus104, for example, via the SATA or IDE controller107.

A keyboard111and a mouse112can be optionally connected to the bus104via a peripheral controller110, such as a keyboard/mouse controller or a USB bus.

The disk108can store an operating system, such as z/OS (registered trademark), z/VM (registered trademark), z/VSE (registered trademark), z/TPF, VOS3, UNIX (registered trademark), Windows (registered trademark), or Mac OS (registered trademark); a Java (registered trademark) processing environment, such as J2EE; a Java (registered trademark) application; a Java (registered trademark) virtual machine (VM); a program that provides a Java (registered trademark) Just-In-Time (JIT) compiler; the computer program according to the embodiment of the present invention and other programs; and data, in such a manner that they can be loaded into the main memory103.

The disk108may be included in the computer101, may be connected via a cable to the computer101such that the disk108can be accessed by the computer101, or may be connected via a wired or wireless network to the computer101such that the disk108can be accessed by the computer101.

The drive109can be used to install a program, such as an operating system, an application, or the computer program according to the embodiment of the present invention, from a CD-ROM, a DVD-ROM, or a BD, onto the disk108as necessary.

A communication interface114complies with, for example, the Ethernet (registered trademark) protocol. The communication interface114is connected via a communication controller113to the bus104, and allows wired or wireless connection of the computer101to a communication line115. The communication interface114provides a network interface layer for the TCP/IP communication protocol for the communication function of the operating system in the computer101. The communication line115may be, for example, a wireless LAN environment based on a wireless LAN connection standard, a Wi-Fi wireless LAN environment such as IEEE802.11a/b/g/n, or a mobile phone network environment 3G or 4G environment).

FIG. 2illustrates a call graph that can be used in the embodiment of the present invention.

A call graph is also referred to as a multigraph, and is a directed graph that represents calling relationships between methods in a computer program. Generally, in the call graph, each node represents a procedure and each edge (A, B) indicates that procedure A calls procedure B.

In the call graph that can be used in the embodiment of the present invention, a method corresponds to a node and a method call corresponds to an edge. This call graph may be either dynamic or static.

The call graph that can be used in the embodiment of the present invention may be used to calculate an inline cost-effectiveness ratio for a callee method reachable from a method to be compiled.

A call graph201illustrated inFIG. 2includes nodes211,212,213,214, and215corresponding to method A, method B, method C, method D, and method E, respectively, and edges221,222,223, and224corresponding to a call from method A to method B, a call from method B to method C, a call from method D to method B, and a call from method E to method B, respectively.

For example, in a call from method B to method C, method B is a caller method and method C is a callee method.

Method A, method D, and method E are also referred to as call sites for method B.

FIGS. 3A and 3Bare each a flowchart of an inlining process according to the embodiment of the present invention.

FIG. 3Ais a flowchart for inlining a callee method according to the embodiment of the present invention.

In step S301, for source code written in a language to be subjected to inlining, a computer301starts a compile process using a compiler. The compiler may be either a static compiler or a dynamic compiler. In optimization during the compile process, the computer301starts the miming process according to the embodiment of the present invention.

Examples of the language used in the embodiment of the present invention and subjected to inlining include, but are not limited to, an object-oriented language (e.g., C++ or Java (registered trademark)) and a functional programming language using small functions.

In step S302, the computer301obtains a set of all callee methods Scalleesthat can be called from one method to be compiled. The computer301may obtain the set Scallees, for example, from a call graph.

In step S303, the computer301determines whether any callee method unprocessed in step S305(described below) remains in the set Scalleesobtained in step S303. If any unprocessed callee method remains, the computer301advances the process to step S304. On the other hand, if no unprocessed callee method remains, the computer301advances the process to step S308.

In step S304, the computer301fetches one unprocessed canoe method Mcalleefrom the set Scallees.

In step S305, the computer301calculates an inline cost-effectiveness ratio (global inlining efficiency ratio (GIER)) for the callee method Mcalleefetched in step S304(i.e., the cost-effectiveness ratio of inlining the callee method Mcallee) in accordance with the following equation. The computer301can use a call graph in calculating the GIER. The computer301calculates the GIER for each edge (i.e., callee method Mcallee).

FrequencyRatio(edge) is calculated from Fcaller-callee/Ftotal). That is, FrequencyRatio(edge) is the ratio of the frequency of calls to the callee method Mcallee(Fcaller-callee; Frequency(edge)) to the total of call frequencies Ftotal; TotalFrequency). FrequencyRatio(edge) corresponds to “effectiveness” in the cost-effectiveness ratio.

SizeRatio(edge) is calculated from (Scallee/Stotal). That is, SizeRatio(edge) is the ratio of the code size of the callee method (Scallee; CalleeSize(edge)) to the total size of inlinable code. SizeRatio(edge) corresponds to “cost” in the cost-effectiveness ratio.

The computer301may optionally use, for example, a call graph size calculated in accordance with the following equation as the total size of inlinable code (Stotal; TotalInlineSize). Alternatively, the computer301may be optionally given a constant from the user as the total size of inlinable code (Stotal; TotalInlineSize).

In the following equation, the total size of inlinable code (Stotal) is a tuning parameter. An actual implementation experiment reveals that high cost-effectiveness can be achieved by using a value dynamically calculated in accordance with the following equation.
TotalInlineSize=ΣedgeεCallGraphEdgesCalleeSize(edge)  (Equation 1)

As indicated by the equation described above, since GIER is calculated only from information about the call frequency in profile information, it is not necessary to look through all call-graph edges. Also, since GIER is an absolute index, it is not necessary to make a comparison with other edges (i.e., callee methods).

The computer301can optionally change the GIER calculated using the above-described equation, in accordance with heuristics shown in one of the following (1) to (3). This change can further improve the effect of an algorithm at uses the GIER.(1) The computer301counts the number of call sites for a callee method. If the number of call sites is greater than or equal to a predetermined threshold, the computer301makes the value of GIER less than or equal to a predetermined threshold. That is, the computer301makes the value of GIER less than or equal to a predetermined threshold so that the callee method is not inlined. By making the GIER less than or equal to the predetermined threshold in the above-described case, it is possible to prevent an increase in footprint and to eventually prevent an increase in the size of binary code generated by a compiler.(2) If the code size of a callee method is greater than or equal to a predetermined threshold, the computer301makes the value of GIER less than or equal to a predetermined threshold. That is, the computer301makes the value of GIER less than or equal to the predetermined threshold so that the callee method is not inlined. By making the GIER less than or equal to the predetermined threshold in the above-described case, it is possible to prevent an increase in footprint and to eventually prevent an increase in the size of binary code generated by a compiler.(3) If the number of call sites for a callee method is one, the computer301increases the value of GIER (e.g., the computer301doubles the value of GIER). That is, the computer301increases the value of GIER so that all callee methods are unconditionally inlined. By increasing the value of GIER in the above-described case, it is possible to facilitate inlining when there is no increase in footprint.

When the following conditions are met, the computer301can optionally change the frequency of calls to the callee method Mcallee(Fcaller-callee). That is, in a multilevel call sequence where a first method calls a second method and the second method calls a third method, when the second method is determined to be inlined and a further determination is made as to whether to inline the third method, if there are multiple call sites (including the first method) for the second method, the computer301can correct the frequency of calls from the second method to the third method by using the ratio of the frequency of calls from the first method to the second method to the total of frequencies of calls from all the call sites to the second method. This correction will be described in detail with reference toFIG. 5.

In step S306, the computer301compares the value of GIER calculated step S305with a predetermined threshold.

When the GIER is calculated from the ratio of FrequencyRatio(edge) to SizeRatio(edge), if the value of the GIER is greater than or equal to the predetermined threshold, the computer301advances the process to step S307to inline the callee method Mcallee. On the other hand, if the value of the GIER is less than the predetermined threshold in the above-described case, the computer301returns the process to step S303without inlining the callee method Mcallee.

When the GIER is calculated from the ratio of SizeRatio(edge) to FrequencyRatio(edge), if the value of the GIER is less than a predetermined threshold, the computer301advances the process to step S307to inline the callee method Mcallee. On the other hand, if the value of the GIER is greater than or equal to the predetermined threshold, the computer301returns the process to step S303without inlining the callee method Mcallee.

In step S307, the computer301inlines the callee method Mcallee.

Also in step S307, the computer301adds all callee methods from the callee method Mcalleeto the set Scallee. By adding all callee methods from the callee method Mcalleeto the set Scallees, the computer301repeats steps S303to307for each callee method reachable from methods including the inlined method.

Upon completion of step S307, the computer301returns the process to step S303and repeats steps S303to307.

In step S308, the computer301determines whether there is any unprocessed method to be compiled. If there is an unprocessed method to be compiled, the computer301returns the process to step S302to perform steps S302to307for the unprocessed method. On the other hand, if there is no such an unprocessed method, the computer301advances the process to step S309.

In step S309, the computer301ends the compile process for the source code written in a language subjected to inlining.

FIG. 3Bis a flowchart for updating profile information.

In step S311, the computer301starts a process of updating profile information. The process of updating profile information can be performed in parallel with, or independent of, the inlining process illustrated inFIG. 3A.

In step S312, the computer301detects a call from a caller method Mcallerto a callee method Mcallee.

In step S313, each time the detection is made in step S312, the computer301updates a call graph in accordance with the following (1) to (3):(1) If there is no node corresponding to the caller method Mcallerin the call graph, the computer301adds a node corresponding to the caller method Mcallerto the call graph;(2) If there is no node corresponding to the callee method Mcalleein the call graph, the computer301adds anode corresponding to the callee method Mcalleeto the call graph; and(3) If there is no edge reachable from the caller method Mcallerto the callee method Mcalleein the call graph, the computer301adds such an edge to the call graph.

Also in step S313, the computer301increments the frequency of calls to the callee method (Fcaller-callee) (Fcaller-callee++, for example, by one); increments the total of call frequencies (Ftotal) (Ftotal++, for example, by one); and updates the total size of inlinable code (Stotal), that is, adds the code size of Scalleeto Stotal(Stotal+=Scallee).

The frequency of calls to the callee method (Fcaller-callee) can be incremented (Fcaller-callee++) and the total of call frequencies (Ftotal) can be incremented (Ftotal++) in response to the detection in step S312.

The total size of inlinable code (Stotal) can be updated in response to the addition of an edge in (3) described above.

The updated total size of inlinable code (Stotal), the incremented frequency of calls to the callee method (Fcaller-callee), and the incremented total of call frequencies (Ftotal) are used in step S305ofFIG. 3A. Step S305is performed separately from the process of the flowchart inFIG. 3B.

In step S313, the computer301determines whether to repeat steps S312and s313. The determination as to whether to repeat steps S312and s313can be made, for example, depending on whether a call from the caller method Mcallerto the callee method Mcalleeis detected before a predetermined time elapses. If steps S312and s313are to be repeated, the computer301returns the process to step S312. If steps S312and s313are not to be repeated, the computer301advances the process to step S314.

In step S314, the computer301ends the process of updating the profile information.

FIG. 4is a graph that visualizes a cost-effectiveness ratio that can be required in the embodiment of the present invention.

The graph ofFIG. 4shows a cumulative size of inlinable code (ratio expressed in % in the horizontal axis) and a cumulative frequency of calls to a callee method (ratio expressed in % in the vertical axis) when edges are sorted in descending order of GIER, in a call graph that can be actually obtained from benchmark software available from SPECjvm2008.

In the embodiment of the present invention, as shown in the flowchart ofFIG. 3A, the calculation in step S305(calculating step) and inlining in step S307(inlining step) are repeated for each callee method reachable from methods, including an inlined method, until there is no callee method to be inlined.

GIER is represented by the slope of a curve402on the graph401shown inFIG. 4. The steeper the slope of the curve, the higher the call frequency and the lower the cost, and thus the higher the inline cost-effectiveness. Therefore, high inline cost-effectiveness can be achieved by inlining a portion corresponding to a steep slope of the curve.

The example ofFIG. 4shows that by inlining about 10% of edges (i.e., callee methods) in the call graph, it is possible to reduce about 99% or more of method calls.

GIER is used to extract about 10% of edges without looking through all call-graph edges. The predetermined GIER threshold shown in step S306ofFIG. 3Amay be any value. For example, normalization is done to make the GIER threshold “1”. When the GIER threshold is “1”, the cost and the effectiveness are balanced. When normalization is done to make the GIER threshold “1”, it is easy to set the GIER threshold.

It was found that by using, for example, “1” as the GIER threshold, the performance of many benchmark software products available from SPECjvm2008 was improved.

By using a value smaller than “1” as the GIER threshold, the ratio of inlined methods can be increased. That is, the computer becomes aggressive toward inlining. On the other hand, by using a value larger than “1” as the GIER threshold, the ratio of inlined methods can be reduced. That is, the computer becomes conservative toward inlining.

FIG. 5is a call graph shown to describe correction of a call frequency in a call graph having a multilevel call sequence according to the embodiment of the present invention.

A call graph501shown inFIG. 5has the same structure (nodes and edges) as that of the call graph201shown inFIG. 2. For details the call graph501shown inFIG. 5, refer to the description of the call graph201shown inFIG. 2.

The call graph501shown inFIG. 5provides a multilevel call sequence where method A (511) on the first level calls method B (512) on the second level, method B (512) on the second level calls method C (513) on the third level.

It is already determined that method B (512) on the second level is to be inlined. Then the computer101is in the process of determining whether to inline method C (513). In the call graph501, there are multiple call sites, including method A (511), for method B (512) which is already determined to be inlined. That is, method D (514) and method F (515) as well as method A (511) are call sites for method B (512).

In the above-described case, the computer101corrects the frequency of calls from method B (512) to method C (513) using the ratio of the frequency of calls from method A (511) to method B (512) to the total of the frequencies of calls from all the call sites (i.e., method A (511), method D (514), and method E (515)) to method B (512). This correction makes it possible to estimate the frequency of calls through method B (512), which is already determined to be inlined.

The correction can be made in accordance with the following equation.

The correction of the frequency of calls from method B (512) to method C (513) will now be described by using the example of the call graph501.

The frequency of calls from method B (512) to method C (513) (i.e., the call frequency to be corrected) is 30%. The frequency of calls from method A (511) to method B (512) is 10%. The total of the frequencies of calls from all the call sites (i.e., method A (511), method D (514), and method E (515)) to method B (512) is 10%+10%+10%=30%.

Therefore, the frequency of calls from method B (512) to method C (513), CallFrequencyA(B→C), is corrected to 30×(10/30)=10%.

FIG. 6is a functional block diagram of a computer that preferably has the hardware configuration of the computer101illustrated inFIG. 1and performs an inlining process for inlining a callee method according to the embodiment of the present invention.

The computer101is a computer that performs an inlining process for inlining a callee method according to the embodiment of the present invention and may be, for example, the computer101illustrated inFIG. 1.

The compile means611includes front end means621and optimizing means622. The optimizing means622includes calculating means631, determining means632, inlining means633, call graph updating means635, and detecting means634which are added according to the embodiment of the present invention.

The front end means621includes a lexical analyzer, a syntax analyzer, and a semantic analyzer. The front end means621obtains source code601from a storage medium (e.g., the disk108shown inFIG. 1). The front end means621performs lexical analysis, syntax analysis, and semantic analysis on the obtained source code601in the same manner as in the related art and outputs compiler intermediate text.

The calculating means631calculates an inline cost-effectiveness ratio for a callee method reachable from a method to be compiled. The calculating means631fetches profile information603from a storage medium (e.g., the disk108shown inFIG. 1), and calculates the cost-effectiveness ratio by using the ratio of the frequency of calls to the callee method to the total of the call frequencies as effectiveness and using the ratio of the code size of the callee method to the total size of inlinable code as cost.

The calculating means631can calculate an inline cost-effectiveness ratio for a call-graph edge reachable from a method to be compiled on a call graph.

The calculating means631can repeat calculation of the cost-effectiveness ratio for each callee method reachable from methods, including an inlined method, until there is no callee method to be inlined.

In a multilevel call sequence where a first method calls a second method and the second method calls a third method, when the second method is determined to be inlined and a further determination is made as to whether to inline the third method, if there are multiple call sites (including the first method) for the second method, the calculating means631can correct the frequency of calls from the second method to the third method by using the ratio of the frequency of calls from the first method to the second method to the total of frequencies of calls from all the call sites to the second method.

The calculating means631can increment the frequency of calls to the callee method; increment the total of call frequencies; and update the total size of inlinable code after the call graph updating means635adds an edge described in (3) below to a call graph.

The determining means632determines whether to inline a callee method by comparing a cost-effectiveness ratio calculated by the calculating means631with a predetermined threshold.

The inlining means633inlines the callee method when the determining means632determines that the callee method is to be inlined.

If the number of call sites for the callee method is greater than or equal to a predetermined threshold, the inlining means633can be prevented from inlining the callee method.

If the code size of the callee method is greater than or equal to a predetermined threshold, the inlining means633can be prevented from inlining the callee method.

If the number of call sites for the callee method is one, the inlining means633can inline the callee method.

The call graph updating means635can update a call graph in the following cases (1) to (3):(1) if there is no node corresponding to the caller method in the call graph, a node corresponding to the caller method is added to the call graph;(2) if there is no node corresponding to the callee method in the call graph, a node corresponding to the callee method is added to the call graph; and(3) if there is no edge reachable from the caller method to the callee method in the call graph, an edge reachable from the caller method to the callee method is added to the call graph.

The detecting means634detects a call from a method to a caller method.

The optimizing means622outputs binary code602inlined in accordance with the embodiment of the present invention.

A computer program according to an embodiment of the present invention can be stored in one or a plurality of computer-readable recording media, such as flexible disks, MOs, CD-ROMs, DVDs, BDs, hard disk devices, USB-connectable memory media, ROMs, MRAMs, and RAMs. For storage in such a recording medium, the computer program can be downloaded from another computer (e.g., server computer) connected via a communication line, or can be copied from another recording medium. The computer program according to the embodiment of the present invention may be compressed or divided into a plurality of pieces and stored in one or a plurality of recording medium. Note that a computer program product according to the embodiment of the present invention can be provided in various forms. The computer program product according to the embodiment of the present invention may include, for example, a storage medium in which the computer program is recorded, or a transfer medium for transferring the computer program.

Note that the summary of the present invention described above does not enumerate all essential features of the present invention, and that combinations and sub-combinations of components may also be included in the present invention.

For example, each hardware component of the computer used in the embodiment of the present invention may be combined with a plurality of machines, so that functions may be distributed thereto and implemented. It is obvious that such various changes can readily occur to those skilled in the art. It is to be understood that these changes are concepts included in the idea of the present invention. The components described above are merely examples and not all of them are essential components of the present invention.

The present invention can be implemented as hardware, software, or a combination of hardware and software. A typical example of the implementation by the combination of hardware and software may be implementation in a computer having the above-described computer program installed thereon. In this case, when the computer program is loaded in a memory of the computer and executed, the computer program controls the computer to perform processing according to the present invention. This computer program may be formed by a set of instructions that can be expressed in any language, code, or notation. Such a set of instructions enables the computer to perform processing according to the embodiment of the present invention directly, or after (1) conversion to another language, code or notation, and/or (2) copying to another medium.

According to the embodiment of the present invention, a computer can calculate inline cost-effectiveness from call frequency information alone, and can globally inline callee methods with high cost-effectiveness, without looking through all call-graph edges. It is thus possible to reduce profile overhead, reduce compile time, and achieve efficient inlining.

EXAMPLE

A computer program according to the embodiment of the present invention was implemented on the 64-bit IBM (registered trademark) Java (registered trademark) 1.7 JIT Compiler.

As benchmark software, 12 types of benchmark software available from SPECjvm2008 were used.

Profile information in a call graph was collected by an online profiler using runtime instrumentation (RI) for the zEC12 processor. There is practically no overhead in this collection.

An edge whose value of GIER (i.e., the ratio of effectiveness (ratio of the frequency of calls to the callee method to the total of call frequencies) to cost (ratio of the code size of a callee method to the total size of inlinable code)) exceeds one was inlined. There is no threshold for each compile method.

Comparative Example 1

Baseline

An inlining technique (for static compilers) incorporated by default in the 64-bit IBM (registered trademark) Java (registered trademark) 1.7 JIT Compiler was used. An edge to be inlined was determined using a heuristic technique in which callee methods are inlined basically in ascending order of code size, without using a call graph. There is an inline size threshold for each compile method. A platform environment and benchmark software are the same as those in Example.

Comparative Example 2

An inlining technique combining the technique of Comparative Example 1 with a call graph was used. For an edge to be inlined, profile information from a call graph was used to calculate a cost-effectiveness ratio as a ratio of the call frequency to the code size of a callee method, and callee methods were inlined in descending order of the calculated cost-effectiveness ratio. As in Comparative Example 1, there is an inline size threshold for each compile method. A platform environment and benchmark software are the same as those in Example.

Throughput in Example was 3.7% higher than that in Comparative Example 1 (baseline) on average in the 12 types of benchmark software, and was up to 10.8% higher depending on the type of benchmark software. On the other hand, throughput in Comparative Example 2 was often lower than that in Comparative Example 1 (baseline).

(Relative Size of Inlined Code)

The relative size of inlined code in Example was much smaller than that in Comparative Example 1 (baseline) on average in the 12 types of benchmark software. This is because in the embodiment of the present invention, inlining with low cost-effectiveness was eliminated. The relative size of inlined code in Comparative Example 2 was smaller than that in Comparative Example 1 (baseline), but was larger than that in Example. This is because since, in the method of Comparative Example 2, inlining continues as long as the inlined code size is well within the threshold, the inlined code size in Comparative Example 2 is larger than that in the method according to the embodiment of the present invention.

The compile time in Example was shorter than that in Comparative Example 1 (baseline) on average in the 12 types of benchmark software. The compile time in Comparative Example 2 was longer than that in Comparative Example 1.