Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-04-23
2002-06-18
Morse, Gregory (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S159000
Reexamination Certificate
active
06408433
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 enabling a register allocator to build calling convention prolog and epilog code for subroutine calls.
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” during a compilation process. Optimizing a computer program generally serves to eliminate portions of computer code which are essentially unused. In addition, optimizing a computer program as a part of a compilation process 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 otherwise compile 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 as 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 which 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 space which is partitioned into stack slots, associated with a computer.
Prior to a register allocation process, a set of values, i.e., incoming arguments, are known to a compiler, and are in fixed locations as specified by a calling convention. A calling convention, as will be appreciated by those skilled in the art, is generally a convention by which calls to a subroutine are made. A calling convention typically specifies where arguments are passed, i.e., which register or stack slot each argument appears in. In addition, a calling convention may specify which registers must be preserved across the subroutine, i.e., callee-save registers. If callee-save registers are used in the subroutine, the callee-save registers generally need to be saved and restored. The calling convention may also specify whether some registers are unused or used for special purposes. Saving and restoring registers, along with any other special handling, typically occurs at the entry and exit of subroutines, and is called prolog and epilog code. Additional information is available after the register allocation process is completed. Such additional information includes, but is not limited to, the stack frame size associated with the subroutine and a set of registers, which is to be saved and restored.
FIG. 1
is a diagrammatic representation of a compiler which includes a register allocator and a calling convention code generator. Source code
102
is provided as input to a compiler
106
, which may be an optimizing compiler. Typically, source code
102
includes a call
108
to a subroutine
110
, as well as incoming arguments
112
associated with call
108
. Specifically, the location of incoming arguments
112
is specified with respect to call
108
.
A register allocator
116
, which is included in compiler
106
, is arranged to allocate memory space for use by source code
102
. After register allocator
116
performs a register allocation, a calling convention code generator
118
generates prolog and epilog code associated with source code
102
. By way of example, if any callee-save register is used in any part of the allocation, then code which is used to save and to restore the callee-save register is inserted into the prolog and epilog code. Prolog and epilog code is included in an internal representation
120
of source code
102
. Once internal representation
120
is generated, compiler
106
creates machine instructions
124
from internal representation
120
.
Internal representation
120
includes copy, load, and store instructions that are associated with definitions and uses of variables, in addition to a calling convention for a subroutine. As shown, variables, or values, “c” and “d” are stored on a stack. Variable “d” must be spilled across the subroutine call, as will be appreciated by those skilled in the art. Hence, variable “d” is reloaded from a stack after the subroutine call to “foo.”
With reference to
FIG. 2
, a process of generating machine instructions from source code which includes calling conventions will be described. The process
202
generally involves the conversion of “virtual” registers into “real” registers, as will be appreciated by those skilled in the art. Prior to allocation, the compiler assumes that it has an unlimited number of “virtual” registers to work with. It is the job of the allocator to map the unlimited virtual registers into the very limited set of real registers that the overall machine has. Process
202
begins at step
204
in which calling convention code is inserted into source code obtained by a compiler.
Typically, after the compiler inserts calling convention code, or code associated with a convention by which a subroutine call may be made, the compiler studies the calling convention in step
206
. Specifically, the compiler studies an incoming argument associated with the calling convention. In step
208
, a determination is made as to whether the incoming value, or argument, is associated with a register or a stack location, e.g., a stack slot. When it is determined that the incoming argument is stored in a register, then process flow moves to step
216
where the incoming value is copied to a virtual register. Typically, the copying is performed using a register-to-register copy command.
Once the incoming value is copied into a virtual register, then in step
212
, register allocation is performed. The steps associated with performing a register allocation will be discussed below with respect to
FIG. 3. A
register allocation process generates allocation choices. That is, an overall register allocation process may be used to determine how different values are assigned to registers, i.e., “real” registers, and stack slots. After the register allocation process is completed, then the allocation choices generated by the register allocation process are converted into machine instructions by the compiler in step
214
. It should be appreciated that turning allocation choices into machine instructions includes building prolog and epilog code using information obtained during the register allocation process. The process of creating machine instructions is completed once allocation choices have been converted.
Returning to step
208
and the determination of whether an incoming value is associated with a register or a stack location, when it is determined that the incoming value is stored in a stack location, then in step
210
, the incoming value is loaded into a virtual register. From step
210
, process flow proceeds to step
212
where a register allocation is performed.
FIG. 3
is a process flow diagram which illustrates the steps associated with allocating stack space, i.e., step
212
of
FIG. 2
, in response to coloring an interference graph. The process
212
of allocating memory associated with a segment of source code begins at step
302
in which an interference graph is constructed for the segment of source code. After the interference graph is constructed, an attempt is made to color the interference graph in step
306
. Typically, a variety o
Click, Jr. Clifford N.
Paleczny Michael H.
Vick Christopher A.
Beyer Weaver & Thomas LLP
Chavis John Q.
Morse Gregory
Sun Microsystems Inc.
LandOfFree
Method and apparatus for building calling convention prolog... 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 building calling convention prolog..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for building calling convention prolog... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895704