Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1993-11-08
2002-07-23
Oberley, Alvin (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S151000
Reexamination Certificate
active
06425124
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
The present invention relates to a resource allocation device employed by a computer to allocate a variable to a resource when translating a source program into an object program.
(2) Description of Related Art
Development of a program has been promoted by describing a program in a high-level language such as a C language. A compiler translates a source program from a high-level language into a machine language which can be understood by a target computer.
A source program employs variables to hold numeric values to be computed in an operation or to hold operation results. Variables are defined by a programmer depending on the needs; or, they are generated by a compiler so that internal processing will be facilitated. Only a required number of the generated variables will be used.
A machine language program, on the other hand, operates a register or a memory to hold numeric values to be computed in an operation or to hold operation results. Both a register and a memory are hardware, so that the number of registers and memories which can be employed at each source program is limited.
When translating a source program into a machine language program, all the variables included in the source program need to be allocated to either a register or a memory. A conventional compiler operates a resource allocation device to allocate each variable to either a register or a memory.
A register and a memory are also called resources defined in a program and are referred to as “alive” until their final references in the program.
Generally the number of available registers is small, so that the compiler implements the best use thereof by allocating a frequently used variable to a register. To be concrete, the compiler determines the frequency each variable used in a source program, and divides the frequency of appearance of the variable by its live range, which indicates how long the variable is alive. Then, the variable with a large dividing result will be allocated to a register while the variable with a small dividing result will be allocated to a memory.
According to the conventional compiler, however, size and run time of the translated machine language program are not considered when allocating a variable to a resource. That is, when allocating a variable to either a register or a memory, an operation including the variable and an instruction sequence replacing the operation are not considered; consequently, size of the machine language program including a plurality of the instruction sequences tends to be large. As a result, run times of such machine language programs are often long.
For example, it is assumed that a target machine manipulates operand at registers. With the allocation by the conventional resource allocation device, a variable x representing the operand in the machine language program may be allocated to a memory. In this case, a transfer instruction which directs transfer of the content of the memory to the register must be included in the machine language program. If a number of the transfer instructions are included in the machine language program, size of the program will be expanded and run time thereof will be extended by the transfer instructions.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a resource allocation device for reducing run time and size of a machine language program.
The above object may be fulfilled by a resource allocation device employed by a compiler for translating a high-level language program or a program translated from the high-level language program by a compiler for its internal processing, into a machine language of a target machine, the resource allocation device allocating a variable included in a resource allocation portion of the program to a resource such as a register or a memory, the resource allocation portion being subjected to the resource allocation, the resource allocation device comprising a variable holding unit for holding all live variables placed within the resource allocation portion, a pattern generation unit for generating every pattern of the resource and each variable held by the variable holding unit, the variable to be allocated to the resource, an instruction sequence holding unit for holding an instruction sequence corresponding to each combination of an operation and the resource, the instruction sequence written in an assembly language and/or a macro language, an instruction extraction unit for extracting the instruction sequence for each pattern generated by the pattern generation unit in accordance with each operation placed within the resource allocation portion and the resource to which the variable in the operation is allocated, and generating a program corresponding to the resource allocation portion, the program comprising the extracted instruction sequences, a cost table for holding the instruction sequence and a cost thereof representing the number of execution clocks taken in execution of the instruction sequence, a cost detection unit for detecting from the cost table the cost of each instruction sequence included in each program generated by the instruction extraction unit, a total cost computation unit for computing a total cost of each pattern generated by the pattern generation unit as referring to the cost of each instruction sequence detected by the cost detection unit, and a best pattern decision unit for deciding the pattern with the lowest cost in the patterns generated by the pattern generation unit as referring to the total cost of each pattern.
The pattern generation unit may be comprised of a first variable selection unit for selecting all the variables held by the variable holding unit unless a predetermined direction is given by a user; a variable evaluation unit for obtaining a variable evaluation value of each live variable by dividing the number of the operations referring to/defining the live variable by its live range; a second variable selection unit for arranging the variables by the variable evaluation values and selecting a predetermined number of the variables which starts with a first variable with the largest variable evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number; and a generation unit for generating every pattern of the variables selected by the first variable selection unit or the second variable selection unit and the resource corresponding to each of the variables.
The second variable selection unit may be comprised of a computation unit for computing the predetermined number by doubling the number of the registers employed by the target machine; a first selection unit for selecting all the variables from the resource allocation portion when the number of the selected variables is the predetermined number or smaller than the same; and a second selection unit for arranging the variables by the variable evaluation values and selecting the predetermined number of variables which starts with a first variable with the largest evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number computed by the computation unit when the number of the variables placed within the resource allocation portion is larger than the predetermined number.
The instruction sequence holding unit may hold the instruction sequence which corresponds to a combination of an action type, a variable type, an operand, and a storage in which the action type, the variable type, and the operand are included in the operation while results of the operation are stored into the storage; and an instruction extraction unit may extract the instruction sequence for each pattern generated by the pattern generation unit as referring to the action type, the variable type, and the operand, all of which are included in the operation placed within the resource allocation portion
Tanaka Akira
Tominaga Nobuki
Urushibara Seiichi
Lao Sue
Matsushita Electric - Industrial Co., Ltd.
Oberley Alvin
Price and Gess
LandOfFree
Resource allocation device for reducing the size and run... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resource allocation device for reducing the size and run..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource allocation device for reducing the size and run... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2870194