1. Field of Invention
The present invention relates generally to methods and apparatus for improving the performance of software applications. More particularly, the present invention relates to methods and apparatus for reducing the number of edges in an interference graph.
2. Description of the Related Art
In an effort to increase the efficiency associated with the execution of computer programs, many computer programs are xe2x80x9coptimized.xe2x80x9d Optimizing a computer program generally serves to eliminate portions of computer code which are essentially unused. In addition, optimizing a computer program may restructure computational operations to allow overall computations to be performed more efficiently, thereby consuming fewer computer resources.
An optimizer is arranged to effectively transform or a computer program, e.g., a computer program written in a programming language such as C++, FORTRAN or Java bytecodes, into a faster program. The faster, or optimized, program generally includes substantially all the same, observable behaviors as the original, or pre-converted, computer program. Specifically, the optimized program includes the same mathematical behavior has its associated original program. However, the optimized program generally recreates the same mathematical behavior with fewer computations.
As will be appreciated by those skilled in the art, an optimizer generally includes a register allocator that is arranged to control the use of registers within an optimized or otherwise compiled, internal representation of a program. A register allocator allocates register space in which data associated with a program may be stored. A register is a location associated with a processor of a computer that may be accessed relatively quickly, as compared to the speed associated with accessing xe2x80x9cregularxe2x80x9d memory space, e.g., stack or heap space, associated with a computer.
Often, in order to allocate registers and stack slots, interference graphs are used to facilitate the allocation process. Interference graphs generally include a representation of a live range for each variable or value associated with a particular portion of code. A live range is generally a range in a portion of code over which a particular variable or value must remain accessible and available for use. A coloring process may be used on an interference graph to represent relationships between live ranges of variables represented in the interference graph, as will be appreciated by those skilled in the art.
Interference graphs are typically generated by a compiler during a process of compiling source code. FIG. 1 is a diagrammatic representation of a compiler with a register allocator. Source code 102 is provided as input to a compiler 106 which includes a register allocator 110. Compiler 106 may be an optimizing compiler, and is generally arranged to produce an internal representation 120 of source code 102. As shown, a live range 132 for a variable stored in xe2x80x9cCXxe2x80x9d overlaps a live range 134 for a variable stored in xe2x80x9cDX.xe2x80x9d Accordingly, when register allocator 110 assigns registers to live ranges 132, 134, the registers must be assigned to prevent interference between the registers.
Source code 102 includes a call 140 to a subroutine. In general, calls are relatively common in source code, especially source code created in a computing language such as the C++ programming language or the Java(trademark) programming language, developed by Sun Microsystems, Inc. of Palo Alto, Calif. Call 140 includes variables xe2x80x9cCXxe2x80x9d and xe2x80x9cDXxe2x80x9d as arguments. Specifically, call 140 is made with the contents ofxe2x80x9cCXxe2x80x9d and xe2x80x9cDXxe2x80x9d as arguments. Typically, during register allocation, at least some of the variables associated with call 140 are bound to specific registers. In other words, no other variables may use the registers to which arguments associated with call 140 are bound. As will be appreciated by those skilled in the art, incoming parameters used by some methods may also be bound to specific registers.
The information provided in internal representation 120 may be used to create an interference graph of source code 102. With reference to FIG. 2, an interference graph created as a representation of source code 102 of FIG. 1 will be described. An interference graph 204 is created to represent live ranges and conflicts between live ranges with respect to register allocation. All variables associated with source code 102 of FIG. 1 are represented in interference graph 204. Nodes 208 represent live ranges for variables. By way of example, node 208d is arranged to indicate a live range for xe2x80x9cCX,xe2x80x9d while node 208e is arranged to indicate a live range for xe2x80x9cDX.xe2x80x9d It should be appreciated that a representation of the live range for a variable associated with xe2x80x9cDX,xe2x80x9d which is bound to a specific real register, is included in interference graph 204.
Edges 212 drawn between two nodes 208 indicate that the two nodes 208 interfere. That is, edges 212 that are present between two nodes 208 are arranged to show that the variables associated with the two nodes 208 may not be stored in the same register, as they must be live simultaneously. For example, edge 212d between node 208d and node 208e indicates that contents of xe2x80x9cCXxe2x80x9d and contents of xe2x80x9cDXxe2x80x9d must be alive simultaneously and, as a result, interfere with each other, e.g., conflict with each other.
Building and manipulating, e.g., coloring, an interference graph in the course of performing a register allocation is intended to allow registers to be assigned to variables without conflicts. In general, the process of assigning registers to variables without interference, using an interference graph or other approach, is relatively complex. Interference graphs are often relatively large, and may require more than approximately 12 megabytes of memory space for a bit-set implementation when approximately 10,000 nodes are involved. Typically, for a bit-set implementation, each edge requires eight bytes. As source code that is provided to a compiler may often include thousands of variables, an interference graph which includes approximately 10,000 nodes may occur fairly frequently.
Interference graphs which occupy a relatively large amount of memory space tend to occupy memory space which would otherwise be available for other purposes. In addition, as creating and modifying an interference graph is a substantial part of an overall compilation process or, more specifically, a register allocation process, reducing the complexity associated with creating and modifying an interference graph may significantly affect the speed at which the overall compilation process may occur. Therefore, what is desired is a method and an apparatus for increasing the efficiency with which an interference graph. may be created and modified. That is, what is needed is a method and an apparatus for reducing the number of edges included in an interference graph without compromising the accuracy of a register allocation process.
The present invention relates to reducing the number of edges in an interference graph that is created for a register allocation process. According to one aspect of the present invention, a computer-implemented method for allocating registers in an object-based computing system includes obtaining source code that includes a code segment associated with a first variable and a code segment associated with a second variable. The method also includes obtaining a live range for the first variable and binding the first variable to a specific register, and obtaining a live range for the second variable. The representation of the second variable is then modified to exclude the specific register bound to the first variable form its potential allocation choices. Once the live range for the second variable is obtained and modified, a register allocation is performed. Performing the register allocation includes creating an interference graph that includes a representation of the second variable and does not to include a representation of the first variable. The representation of the second variable may be a representation of the live range for the second variable.
In one embodiment, obtaining source code that includes the code segment associated with the first variable includes obtaining a call to a subroutine which includes the first variable as an argument in the call. In another embodiment, obtaining the source code further includes obtaining a code segment associated with a third variable, in addition to obtaining a second live range that is associated with the third variable, and modifying that live range to exclude the specific register which was bound to the first variable from the choices available to the third variable. In such an embodiment, the interference graph includes a representation of the third variable, and performing the register allocation involves determining whether the first live range and the second live range overlap. When it is determined that the live ranges overlap, a coloring process is performed using the interference graph. Such a coloring process adds an indication, e.g., an edge, to the interference graph that indicates that the first live range and the second live range overlap.
By eliminating a representation of a variable that is bound to a register from an interference graph, the number of edges associated with the interference graph may be reduced. Reducing the number of edges increases the speed at which register allocation may occur. Since building and manipulating an interference graph is typically one of the most time-intensive part of an overall register allocation process, by reducing the number of edges in the interference graph, e.g., by keeping the interference graph sparse, the efficiency of the overall register allocation process may be improved.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.