Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-04-23
2002-08-13
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06434743
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 allocating stack slots in substantially the same manner that is used to allocate registers.
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 preconverted, computer program. Specifically, the optimized program includes the samemathematical behavior has its associated original program. However, the 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.
The number of registers in a processor is fixed. As a result, when there is not enough register space available for the storage of data, “spill code” is identified. The spill code is code that moves data between stack slots and registers when all registers are full. A stack slot is a piece of a stack frame that an allocator uses to hold information when all registers are full. Typically, an optimizer includes a specialized stack slot allocator that is arranged to allocate stack slots for spill code as needed. Stack slots are also generally needed when passing more arguments than fit in the registers.
FIG. 1
a
is a diagrammatic representation of a segment of source code. Segment
104
of source code includes uses of variables. By way of example, an instruction
108
includes a use of a variable A which is stored in a register, e.g., register R
1
. Instruction
108
sets a variable B to equal the sum of variable A and an integer “1”. Variable B may be stored into a register R
2
. In addition to being used in instruction
108
, variable A is used in instruction
112
as well. Variable B, as shown, is used in instruction
114
.
A live range for variable B, i.e., “B live range”
120
, is defined as a range in segment
104
over which variable B must remain live. That is, B live range
120
is the “distance” over which a value for variable B needs to be maintained in a register, e.g., register R
2
. “A live range”
122
, or the distance over which variable A must be maintained in a register, overlaps B live range
120
. The overlapping live ranges
120
,
122
indicate that both variable A and variable B are to remain in their respective registers simultaneously over a certain distance. As shown, a first “C live range”
124
indicates that variable C is live in a register only until variable D is set. Therefore, variable C and variable D may in some cases be assigned to the same register.
An interference graph associated with segment
104
may be colored in order to assign registers to segment
104
without conflicts, e.g., without interference. The coloring, and subsequent register allocation, may be performed using a variety of different processes including, but not limited to, a Chaitin coloring heuristic developed at International Business Machines, Inc., of Yorktown Heights, N.Y. and a Briggs-Chaitin coloring algorithm, described in
Register Allocation via Graph Coloring,
by Preston Briggs (PhD thesis, Rice University, 1992), which is incorporated herein by reference.
FIG. 1
b
is a diagrammatic representation of an interference graph that is associated with segment
104
of
FIG. 1
a
. An interference graph
132
includes nodes
134
that are associated with variables A, B, C, D.
Edges
138
are included between two nodes that need to be live at the same time. As shown edge
138
a
is present between node A
134
a
and node D
134
d
, thereby indicating that variables A and D are alive at the same time. Similarly, the edge between node B
134
b
and node C
134
c
indicates that variables B and C also need to be live at the same time.
Interference graph
132
is arranged such that when it is successfully colored, registers may be assigned to associated nodes
134
without conflicts. Hence, coloring interference graph
132
with colors generally involves assigning colors, e.g., register numbers, to nodes
134
of interference graph
132
. Interference graph
132
indicates that three registers are needed for segment
104
of source code as shown in
FIG. 1
a
. Node A
134
a
and node B
134
b
each require individual registers, while node C
134
c
and node D
134
d
may share a register.
In general, since interference graphs may not always be colored with as few colors as the CPU has registers, a spill will occur in which some data is spilled into stack slots. By way of example, a spill may occur when two variables or values attempt to occupy a single register at any given time. When two values attempt to substantially simultaneously occupy a single register, because a register allocator has reached a stage where it is not possible to guarantee each value its own register, one of the values must be spilled into a stack slot. The identification of a value that may be spilled into a stack slot is considered to be the identification of a spill candidate. The register allocator attempts to assign colors to the interference graph such that no two nodes connected by an edge have the same color. Further, the register allocator attempts to use no more than k colors, where k is the number of registers in the central processing unit (CPU), i.e., 8 on Intel 80×86 CPUs and 32 on most RISC CPUs. When it is not possible, or when the algorithm used to color the interference graph does not find a k coloring, then some live ranges must be spilled.
For a hypothetical 2-register machine, interference graph
132
of
FIG. 1
b
may not be colored. For example, an assumption may be made that live ranges associated with variables A and B are identified as spill candidates. A register allocator inserts stores and loads around definitions and uses, as shown in
FIG. 1
c
. At the same time, stack slots must be allocated for use in storing spill code. In this example, separate stack slots are used for spilling live range A and live range B, yet only one of those two live ranges is ever alive at the same time. The interference graph for spilled program
104
′ is given in
FIG. 1
d
. Interference graph
180
of
FIG. 1
d
may be colored using only 2 colors, e.g., machine registers.
The use of store and load instructions allows values to be stored and retrieved, as will be appreciated by those skilled in the art. Further, the use of store and load instructions is associated with the allocation of stack space, or, more specifically, stack slots.
FIG. 2
is a process flow diagram which illustrates the steps associated with allocating stack space in response to coloring an interference graph. The process of allocating memory associated with a segment of source code begins at step
202
in which an interference graph, e.g., interference graph
132
of
FIG. 1
b
, is constru
Click, Jr. Clifford N.
Paleczny Michael H.
Vick Christopher A.
Beyer Weaver & Thomas LLP
Chaki Kakali
Kendall Chuck
Sun Microsystems Inc.
LandOfFree
Method and apparatus for allocating stack slots 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 allocating stack slots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for allocating stack slots will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2970420