Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-04-23
2002-07-16
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06421824
ABSTRACT:
BACKGROUND OF THE INVENTION
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 “optimized.” 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 “regular” 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 “CX” overlaps a live range
134
for a variable stored in “DX.” 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™ programming language, developed by Sun Microsystems, Inc. of Palo Alto, Calif. Call
140
includes variables “CX” and “DX” as arguments. Specifically, call
140
is made with the contents of“CX” and “DX” 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
208
d
is arranged to indicate a live range for “CX,” while node
208
e
is arranged to indicate a live range for “DX.” It should be appreciated that a representation of the live range for a variable associated with “DX,” 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
212
d
between node
208
d
and node
208
e
indicates that contents of “CX” and contents of “DX” 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.
SUMMARY OF THE INVENTION
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 varia
Click, Jr. Clifford N.
Paleczny Michael H.
Vick Christopher A.
Beyer Weaver & Thomas LLP
Chaki Kakali
Chavis John Q.
LandOfFree
Method and apparatus for producing a sparse interference graph does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for producing a sparse interference graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for producing a sparse interference graph will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823250