Enhancing program execution using optimization-driven inlining

Optimizing program execution includes performing, to obtain a first expanded call graph, a first expansion of an initial call graph. The first initial call graph is defined for a program that includes a root method, a first child method, and a second child method. Based on an analysis of the first expanded call graph, the first child method, corresponding to a node in the first expanded call graph, is inlined into the root method. An optimization operation is performed in response to inlining the child method, and the first expanded call graph is updated based on the optimization operation. A second expansion of the updated call graph is performed. Based on an analysis of the second expanded call graph, the second child method is inlined into the root method, where the second child method corresponds to a node in the second expanded call graph. Compilation of the program is completed.

BACKGROUND

When a computer program is written, the computer program is written as source code. A compiler is a software program that translates the source code into object code, byte code, or assembly code. Object code or byte code or assembly can be executed directly by a computer processor or a virtual machine. During compilation, the compiler may perform various optimizations. For example, optimizations may reduce the number of instructions executed by a computer processor. By performing the optimizations, the compiler is able to provide more efficient use of the computer processor.

One way to benefit from the information spread across a call graph data structure and to apply additional optimizations to the computer program is to replace the function calls with the respective function bodies, a transformation called inline expansion or inlining. Most compilers rely heavily on inlining, since inlining a function body is fast, enables other optimizations, and does not require a whole-program analysis.

Although replacing a call-site (e.g., the location, or line of code, where the function is called) with the body of the callee function is a simple transformation, deciding which functions to inline is in practice difficult. Consequently, in many compilers, inlining is based on hand-tuned heuristics and proverbial rules of thumb.

SUMMARY

In general, in one aspect, one or more embodiments relate to a method, system, and computer readable medium for optimizing program execution of a program. The system includes memory and computer processor configured to execute a compiler stored in memory. The compiler for causing the computer processor to optimize the program execution. The non-transitory computer readable medium comprises computer readable program code for optimizing the program execution. The optimizing of the program execution includes performing, to obtain a first expanded call graph, a first expansion of an initial call graph, the first expanded call graph including multiple nodes. The first initial call graph is defined for a program that includes a root method, a first child method, and a second child method. Based on an analysis of the first expanded call graph, the first child method is inlined into the root method. The first child method corresponds to a node of the multiple nodes in the first expanded call graph. An optimization operation is performed in response to inlining the child method, and the first expanded call graph is updated based on the optimization operation to obtain an updated call graph. The optimizing the program execution further includes performing, to obtain a second expanded call graph, a second expansion of the updated call graph. The second expanded call graph includes multiple nodes. Based on an analysis of the second expanded call graph, the second child method is inlined into the root method, where the second child method corresponds to a node in the second expanded call graph. Compilation of the program is completed.

DETAILED DESCRIPTION

Embodiments of the inventions relate to an inlining procedure based on several concepts. One is that the call graph exploration is incremental. The procedure partially explores the call graph during the expansion stage, then switches to the inlining stage. These two stages alternate until a termination condition is met. Further, embodiments of the invention relate to call graph exploration being prioritized using a ratio of the inlining benefit and the inlining cost of the candidate call-sites. Embodiments of the invention relate to inlining benefit, which is estimated by performing optimizations speculatively throughout the call graph, after replacing the function parameters with the concrete call-site arguments, and by relying on the profile information obtained during the prior execution of the program.

In one or more embodiments of the invention, cost-benefit analysis identifies call graph subcomponents that should be inlined together using a heuristic. Cost-benefit analysis is performed by analyzing if inlining the call-site increases the benefit-per-cost ratio of the caller. In one or more embodiments of the invention, inlining is budget-driven: the minimum benefit-per-cost ratio required for inlining grows dynamically with the amount of work performed by the invention.

FIG. 1shows a system in accordance with one or more embodiments of the invention. As shown inFIG. 1, the system is a computing system (101), such as the computer system shown inFIGS. 8A and 8B, and described below. The computing system (101) includes a target program (110) is provided to the compiler (111), which invokes a profiler (112) to assist with creating a call graph (108). The compiler (111) executes on the computer system (101) to transform the provided target program (110) to bytecode or object code, or some other program representation. The profiler (112) analyzes dynamically the source code and identifies critical sections of the code.

The computing system (101) also includes a data repository (102), which stores the data used by or generated by the components of the computing system. For example, the data repository (102) may be a relational database, a hierarchical database, or any other form of repository of data. In one or more embodiments, the repository (102) is essentially the same as the repository shown and described in relation to the computing system inFIG. 8A.

Continuing withFIG. 1, the data repository (102) may include logs (103), a termination condition (104), a dynamic threshold (105), and expansion threshold (106), profiling information (107). Within the profiling information (107) is the call graph (108), which is a control flow graph representing the relationship between subroutines (or methods) in the target program (110). Using the expansion threshold (106) and the dynamic threshold (105), one or more embodiments proceed to evaluate whether to inline methods or not, depending on whether a certain termination condition (104) is met. The results of this activity are logged in the logs (103).

In one or more embodiments, the compiler (111) analyzes the methods of the target program (110). In one or more embodiments of the invention, the compiler (111) starts with a call graph consisting only of the root node (i.e. the compilation unit) and creates an expanded call graph. The expanded call graph is obtained by adding call graph nodes for callsites inside some nodes that are not yet associated with their own (i.e., the callsites' own) call graph nodes. In one or more embodiments, the compiler (111) then inlines, based on an analysis of the expanded call graph, one or more methods found within the target program (110) into a root method. The compiler (111) then performs an optimization operation in response to inlining the method. The compiler (111) then updates the expanded call graph based on the optimization operation to obtain an updated call graph. The following process may be repeated multiple times: the compiler (111) obtains an expanded call graph, and an expansion of the updated call graph. Then, the compiler (111) inlines, based on an analysis of the expanded call graph, the method into the root method. If certain termination conditions are met, the compiler (111) completes compilation of the target program (110). Details of these steps are shown and discussed in relation toFIG. 3.

In one or more embodiments,FIG. 2shows the types and states of call graph nodes (200), which are elements of the call graph, used in this invention, including Cutoff (C) Node (201), Inline Cache (I) Node (202), Deleted (D) Node (203), Generic (G) Node (204), and Explored (E) Node (205). A Cutoff Node (201) represents a call to a function whose body has not been explored. An Inline Cache Node (202) represents calls that can dispatch to multiple known target functions. A Deleted Node (203) represents a call-site that was originally in the intermediate representation, but was removed by a optimization. A Generic Node (204) represents a call to a function that will nut be considered for inlining. An Explored Node (205) represents a call to a function whose body was explored. In one or more embodiments, the compiler evaluating methods of the target program uses the above-named nodes as part of its optimization.

FIG. 3shows a method for the overall process of one or more embodiments of the invention. In Step301, the call graph of the program is expanded. The expand function repetitively calls the ‘descend and expand’ subroutine until the policy returns “true” from the subroutine that checks whether the expansion is completed.

The expand policy subroutine ensures that the queue data structure of each node initially contains the children of that node, sorted by the priority P. The priority can be computed as, but is not limited to, the value B/C, where B is the benefit of inlining that (and only that) specific node, and C is the code size increase resulting from inlining the node. The ‘descend and expand’ subroutine descends on one path in the call graph, by choosing a node with the highest priority, until reaching a cutoff node, and then expands that node. If the ‘descend and expand’ subroutine encounters an expanded node or an inline cache node, then the best child node is removed from the queue data structure, and the subroutine recursively calls itself for that child node. If the node returned from the recursive call is not null or has a non-empty queue, then the child node is placed back on the expansion queue of the current node. Before returning the current node, the update metric subroutine updates the metrics field. The metrics field contains various information about the relevant subtree of the call graph, including, but not limited to, total program size of all the call graph nodes in that subtree, or the number of cutoff nodes in that subtree. Otherwise, if the current node is a cutoff node (i.e. a leaf in the tree), then the expand subroutine is called on the policy object.

In one or more embodiments, the expand subroutine may return either null (indicating that the respective cutoff should not be considered in this round) or return a generic, expanded, or an inline cache node. In one or more embodiments, the expansion of the call graph begins at the request of a user of a computing device. In one or more embodiments, the expansion of the call graph begins as a part of scheduled functionality of a computing device. In one or more embodiments, the expansion of the call graph of the program begins as a result of being invoked by other software running on a computing device.

Step302analyzes the expanded call graph to select a child method of the program. Step302analyzes the expanded call graph to identify groups of methods in the call graph that should be inlined simultaneously. Simultaneously is at the same time, overlapping times, or immediately one after the other. Each group of methods is assigned a benefit and a cost value. In one or more embodiments, the analysis of the expanded call graph is designed to be executable by the compiler.

Step303inlines a child method into a root method of the program. In one or more embodiments, several groups of methods are inlined into the root method of the program in Step303. A group of methods is a set of methods whose inlining improve program performance only if the methods in the set are inlined together, and can be inlined either entirely (if there is sufficient budget remaining), or not at all. In one or more embodiments, the inlining of a child method is designed to be executable by the compiler.

Step304performs an optimization operation for inlining the one or more child methods into the root method. In one or more embodiments, the optimization operation for inlining the child method into the root method is designed to be executable by the compiler.

Step305updates the expanded call graph based on the optimization operation. In one or more embodiments, the update of the expanded call graph based on the optimization operation is designed to be executable by the compiler.

Step306checks to determine whether the termination condition is satisfied. In one or more embodiments, if the termination is satisfied, the process continues to Step307. In one or more embodiments, if the termination condition is not satisfied, the process returns to Step301.

Step307completes the optimization of the program. In one or more embodiments, completion of the optimization of the program is designed to be executable by the compiler.

FIG. 4shows the expansion part of one or more embodiments of invention. Any of the steps shown inFIG. 4may be designed to be executed by the compiler. Initially, step401initializes priority queue for expansion of the call graph. The initial priority queue value is a function of the initial benefit and the cost size.

Step402the determines whether the expansion is completed. In one or more embodiments, if the expansion is completed, the process proceeds to the END. The expansion is completed either when there are no more cutoff nodes to expand, or according to a heuristic. A heuristic can be, but is not limited to, to check whether the benefit-per-cost ratio of the cutoff node exceeds the value e^((root-size−C1)/C2), where root-size is the size of the root method, and C1 and C2 are empirically derived constants. In one or more embodiments, if the expansion is not done, the process proceeds to Step403, which starts the descend into the call graph. Step403marks the root node as the current node.

Step404checks whether the node is of type explored or inlined. In one or more embodiments, if the node is of type explored or inlined, the process proceeds to Step405. In one or more embodiments, if the node is not of type explored or inlined, the process proceeds to Step406.

In one or more embodiments, step405assigns the new current node as child of current node with the greatest expansion priority value. Upon completion of Step405, the process proceeds back to Step404.

In one or more embodiments, the benefit value is calculated as a function of frequency of the number of times a method is called by the root method, the number of optimizations triggered by the improved call-site arguments (which is determined by the expansion policy, for nodes of type C, G, D, E), and a function of probability of the respective child and the local benefit value, for nodes type I. The benefit can be estimated with, but not limited to, the expression f*(1+Ns), where f is the frequency with which the cutoff node is called in the program, and Ns is the number of its parameters that can potentially trigger optimizations after inlining. The cost value is calculated as a function of the bytecode size for nodes type C; infinite for nodes type G; 0 for nodes type D; the size of the intermediate representation for nodes type E; and the sum of the cost value of the children of the root node for nodes type I.

Step406replaces the node with the node expansion. Step407records the optimization. In one or more embodiments, Step407records the optimizations triggered in the call graph by expanding the cutoff node. Finally, Step408updates the priority queue.

FIG. 5shows the analysis part of one or more embodiments of the invention. Any of the steps shown inFIG. 5may be designed to be executed by the compiler. Initially, step501sets the worklist as nodes of the call graph ordered from bottom to top. During the analysis part of one or more embodiments, nodes are assigned cost-benefit tuples. The merged cost-benefit tuple models the cumulative benefit and cost obtained by inlining one call-site into another. The analysis is done in the ‘analyze’ subroutine. The cost-benefit analysis proceeds bottom-up. First, the child nodes are analyzed. After these calls complete, the following invariants hold for each child node m: (1) some connected subgraph B below m has the nodes with inlined set to true. Being set to true indicates that if in were the root method, these descendants would be inlined into m; (2) the tuple in m is set to the benefit and cost of inlining the subgraph B into m. The subgraph B is heuristically chosen in a way such that its inlining maximally improves the benefit per cost of the method m. Inlining some subset of the subgraph B may improve the benefit per cost less, or even decrease it. More details regarding the analysis are shown and provided in regard toFIG. 7GandFIG. 7H.

Step502checks whether the worklist is empty. In one or more embodiments, if the worklist is empty then the process proceeds to END. Otherwise, if the worklist is not empty, then the process proceeds to Step503. Step503selects the current node from the worklist.

Step504calculates the inlining priority value of the current node. Step505creates list of descendants of current node. Child nodes are put in a list, where the child nodes with the highest benefit-cost ratio are repetitively removed in a loop, while the other children are left in the list.

Step506calculates the cost value and benefit value for inlining each child node in list of descendants. The cost value is calculated as a function of the bytecode size for nodes type C; infinite for nodes type G; 0 for nodes type D; the size of the intermediate representation for nodes type E; and the sum of the cost value of the children of the root node for nodes type I. The benefit value is calculated as a function of frequency of the number of times a method is called by the root method, the number of optimizations triggered by the improved call-site arguments, which is determined by the expansion policy, for nodes of type C, G, D, E; a function of probability of the respective child and the local benefit value for nodes type I.

Step507calculates an inlining priority value as a function of the cost value and the benefit value. Step508selects child node having greatest inlining priority value. Such use of priority values based on cost value and benefit value is important to one or more embodiments of the invention.

In Step509the inlining priority value of child node and inlining priority value of current node is checked to determine whether the criteria is satisfied. In one or more embodiments, if the inlining priority value of child node and inlining priority value of current node satisfy criteria, then the process proceeds to Step510. In one or more embodiments, if inlining priority value of child node and inlining priority value of current node does not satisfy criteria, then the process proceeds to Step502.

In one or more embodiments, Step510removes child node from descendant list, marks child node to inline, and adds children of child node to descendant list.

Step511checks whether the descendant list is empty. In one or more embodiments, if the descendant list is empty, then the process proceeds to Step502. In one or more embodiments, if the descendant list is not empty, then the process proceeds to Step508. The inline priority value is calculated as a function of the local benefit, and the cost of inlining the node and of a reduced priority penalty. The calculation of the local benefit and the cost of inlining the node has been described above and the same methodology is used here. The priority penalty is a function of the size of the intermediate representation of the nodes, the size of the bytecode, and several empirically determined constants.

FIG. 6shows the inlining part of one or more embodiments of the invention. Any of the steps shown inFIG. 6may be designed to be executed by the compiler. In Step601, the queue is initialized to include children of root method.

Step602checks whether the queue is empty. In one or more embodiments, if the queue is empty, then the process proceeds to Step609. In one or more embodiments, if the queue is not empty, then the process proceeds to Step603. Step603selects node from queue.

Step604computes a cost value and a benefit value for inlining a method. In one or more embodiments, the cost of expanded nodes is based on the sum of the costs of the children that were previously marked inlined during the analysis part. Similarly, in one or more embodiments, the benefit of expanded nodes is based on the sum of the benefits of inlining the children that were previously marked inlined during the analysis part. The combination of inlining and expansion in this manner is an important improvement, whose goal is to model the inlining decisions that each call graph node would make if it were the root compilation unit, and henceforth to decide whether it is more optimal to inline those methods into the callsite, or to compile them separately. Likewise, so is the use of iterative expansion and inlining of methods. In one or more embodiments, the cost of inlined nodes is based on the size of the intermediate representation for the expanded nodes.

Step605computes an inlining priority value as a function of the cost value and benefit value. Step606computes the cost value of the root method based on the size of the method.

Step607calculates the dynamic threshold based on the size of the root method and the explored part of the call graph. The use of dynamic threshold to process nodes in the call graph is an important improvement. In Step608the dynamic threshold is evaluated to determine whether it is satisfied. The dynamic threshold can be computed as, but not limited to, the value e^((root-size−C1)/C2), where root-size is the size of the root method, and C1 and C2 are empirically derived constants. In one or more embodiments of the invention, if the dynamic threshold is satisfied, then the process proceeds to END. In one or more embodiments, if the queue is not empty, then the process proceeds to Step610.

FIGS. 7A, 7B, 7C, 7D, 7E, 7F, 7G, and 7Hshow examples of calculating priorities as well as managing the call graph data structure.

FIG. 7Ashows example source code (700) that is analyzed in the example shown inFIGS. 7B, 7C, 7D, 7E, 7F, 7G, and 7H. In particular, lines 1-3 of the example source code are code for the half function. Lines 5-14 of the example source code (700) are code for the collatz function. Lines 16-20 of the example source code (700) are code for the main function.FIG. 7Bshows, in one or more embodiments of the invention, the initial call graph for a main function (711), labeled E since it an explored node, representing a call to a function whose body has been explored. The main function calls the collatz and error functions. In one or more embodiments the methods collatz (712) and error (713) are, before inlining starts, labeled C for cutoff nodes, since they are functions whose bodies have not been explored yet. The arrows pointing to main show that collatz (712) and error (713) are the children nodes of main (711).

FIG. 7Cshows, in one or more embodiments, the call graph structure after main (721), collatz (712) and error (713) fromFIG. 7Bhave been explored. InFIG. 7C, in one or more embodiments, exploration has generated another collatz (724) method, a half (725) method, and a second collatz (726) method. In one or more embodiments, the old collatz (722) method has been labeled E since the method has been explored, the error (723) method has been labeled G for generic, since the inlining procedure could not determine a concrete target, so the method was replaced with this generic node. In one or more embodiments, the new nodes, the two collatz methods (724,726) and the half (725) methods are labeled C for cutoff nodes because the methods are functions whose bodies have not been explored yet. The call graph structure is built up, and later the cost-benefit analysis is applied to see how to improve the call graph.

FIG. 7Dshows, in one or more embodiments, the outcome after the inlining procedure has been applied toFIG. 7C, starting with main (731). In one or more embodiments, a deleted node, denoted with D, which represents a call-site that was originally in the intermediate representation, is removed by an optimization. Continuing withFIG. 7D, in one or more embodiments, the inlining algorithm propagates the concrete call-site arguments into the body of the first collatz (732) call, and triggers an optimization. Consequently, in one or more embodiments, the if-cascade in the collatz (736) body is optimized away, and the first recursive call to collatz (734) is removed. error (733) is labeled with G, half (735) is labelled as cutoff C, as is the second collatz (736).

FIG. 7Eshows, in one or more embodiments, the state after the inlining procedure has been applied toFIG. 7D. In one or more embodiments of the invention, several more nodes (744,747,748,749) have been labeled as deleted nodes, denoted with D, while the explored nodes (741,742,745,746) have been labeled E. The error node (743) has been labeled generic, G. Although more nodes are generated to explore, several of the nodes (744,747,748,749) will be deleted. This is an example of how more opportunities are found for call graph expansion which were not known to exist at the beginning of the process. Accordingly, more opportunities for optimization exist.

FIG. 7Fshows that in one or more embodiments of the invention, the compiler may alternatively conclude that the only implementations of the error method (753) are in the StdLog (754) and FileLog (755) classes, and create an inline cache node with the respective children, and label those methods C (cutoff) and the error node (753) as I (inlined). The main node (751) is labeled E (explored), while the collatz node (752) is labeled C (cutoff).

FIGS. 7G and 7Hshow, in one or more embodiments, the analysis part of the invention. The currently considered node is main (761) at depth 0, marked with an arrow. Each child node at depth 1 is analyzed—the collatz (762) on the left has the benefit|cost 2|4, and the generic error call on the right has the benefit|cost 1|inifinite. In addition, the analysis concludes that the subgraph B of collatz (762) (namely, the nodes half (765) and collatz (764,766) at depth 2) must be inlined together, because the arguments from the first collatz (762) considerably simplify the half node (765) and the second collatz node (766). The child node error (763) is labeled generic, G, with B_L|C values of 1|infinity. The child nodes collatz (767), half (777), collatz (778) are labeled for deletion, D, with B_L|C values of 1|0. The analysis part of the invention allows a decision to be made which nodes to keep and which to delete, based on the cost-benefit calculations.

The initial benefit B_I is calculated using the local benefit and the benefit of the child nodes present. With the initial benefit B_I, the benefit is modeled from inlining n, and the fact that no benefits from inlining the children of n has yet occurred. For most nodes, the initial benefit B_I is a negative value. For example, the B_I for the main method inFIG. 7Gis B_I=1−2−1=−2.

FIGS. 7G and 7Hshow, in one or more embodiments, the values of the analysis of some methods. The initial cost benefit tuple is B_I(main)|C(main)=−2|5. The best child is collatz (762) with the tuple 2|4. The merged tuple is 0|9, which is better than −2|5, so the collatz (772) call is marked for inlining (seeFIG. 7H). In the inlining stage, the collatz (774,776) and half (775) calls at depth 2 are also inlined into main (771), since the calls are a part of the marked connected subgraph. The error (773) call is in this case generic, and cannot improve main further.

Embodiments of the invention may be implemented on a computing system. Any combination of mobile, desktop, server, router, switch, embedded device, or other types of hardware may be used. For example, as shown inFIG. 8A, the computing system (800) may include one or more computer processors (802), non-persistent storage (804) (e.g., volatile memory, such as random access memory (RAM), cache memory), persistent storage (806) (e.g., a hard disk, an optical drive such as a compact disk (CD) drive or digital versatile disk (DVD) drive, a flash memory, etc.), a communication interface (812) (e.g., Bluetooth interface, infrared interface, network interface, optical interface, etc.), and numerous other elements and functionalities.

The computer processor(s) (802) may be an integrated circuit for processing instructions. For example, the computer processor(s) may be one or more cores or micro-cores of a processor. The computing system (800) may also include one or more input devices (810), such as a touchscreen, keyboard, mouse, microphone, touchpad, electronic pen, or any other type of input device.

The communication interface (812) may include an integrated circuit for connecting the computing system (800) to a network (not shown) (e.g., a local area network (LAN), a wide area network (WAN) such as the Internet, mobile network, or any other type of network) and/or to another device, such as another computing device.

Further, the computing system (800) may include one or more output devices (808), such as a screen (e.g., a liquid crystal display (LCD), a plasma display, touchscreen, cathode ray tube (CRT) monitor, projector, or other display device), a printer, external storage, or any other output device. One or more of the output devices may be the same or different from the input device(s). The input and output device(s) may be locally or remotely connected to the computer processor(s) (802), non-persistent storage (804), and persistent storage (806). Many different types of computing systems exist, and the aforementioned input and output device(s) may take other forms.

The computing system (800) inFIG. 8Amay be connected to or be a part of a network. For example, as shown inFIG. 8B, the network (820) may include multiple nodes (e.g., node X (822), node Y (824)). Each node may correspond to a computing system, such as the computing system shown inFIG. 8A, or a group of nodes combined may correspond to the computing system shown inFIG. 8A. By way of an example, embodiments of the invention may be implemented on a node of a distributed system that is connected to other nodes. By way of another example, embodiments of the invention may be implemented on a distributed computing system having multiple nodes, where each portion of the invention may be located on a different node within the distributed computing system. Further, one or more elements of the aforementioned computing system (800) may be located at a remote location and connected to the other elements over a network.

The nodes (e.g., node X (822), node Y (824)) in the network (820) may be configured to provide services for a client device (826). For example, the nodes may be part of a cloud computing system. The nodes may include functionality to receive requests from the client device (826) and transmit responses to the client device (826). The client device (826) may be a computing system, such as the computing system shown inFIG. 8A. Further, the client device (826) may include and/or perform all or a portion of one or more embodiments of the invention.

Other techniques may be used to share data, such as the various data described in the present application, between processes without departing from the scope of the invention.

The above description of functions presents only a few examples of functions performed by the computing system ofFIG. 8A. Other functions may be performed using one or more embodiments of the invention.