Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-10-22
2003-08-26
Ingberg, Todd (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06611956
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an instruction string optimization apparatus for a processor using variable length instructions, more specifically, to a technology for estimating constant values in relative branch instructions in an instruction string.
BACKGROUND OF THE INVENTION
The sizes of instructions containing a constant used in a processor using a set of variable-length instructions vary depending on the size of the constant.
For example, consider instruction formats shown in
FIGS. 1
a
to
1
c
. While the size of an instruction which contains a constant of five bits or less is only 16 bits (
FIG. 1
b
), the size of an instruction which contains a constant of more than five bits is 32 bits (
FIG. 1
c
).
Particularly, in an instruction which contains an address value or an address difference value as a constant, the exact size of the constant is not known until a number of relocatable codes are linked and an address is allocated to each instruction by a linker.
However, the sizes of instructions are used for certain optimization of various instruction strings performed prior to the linkage of the instructions. In order to determine the size of an instruction containing an address value or an address difference value as a constant, such as a function call instruction and a branch instruction, the size of the constant must be estimated.
In conventional instruction string optimization apparatuses, approaches to estimate the size of a constant to be resolved as an address or address difference value before linkage are used which estimate the constant size to be the maximum constant size or a constant size most frequently used in a processor of interest.
However, each of these prior art apparatuses has a certain problem associated with the estimation of the constant size before linkage.
With the approach which estimates a constant size to be the maximum constant size used in a processor of interest, a large number of long instructions are produced, and instructions of a size larger than necessary are generated, thus increasing the number of codes. Furthermore, in a very long instruction word (VLIW) processor, the number of instructions which can be parallelized because the number of instructions in a single long word instruction decreases, thus decreasing the performance of the processor.
With the approach which estimates a constant size to be the size of a constant which is most frequently used, if the estimated size is smaller than an actual size and the actual size is identified after addresses are allocated to instructions by an linker, each of the instructions must be converted into an instruction corresponding to that size, thus decreasing the processing speed of the linker. Furthermore, in VLIW processors, in addition to the conversion of instructions into instructions corresponding to the actual size, parallelization re-scheduling of the instructions is required, leading further lowering of the processing speed of the linker.
Therefore, a facility is needed for an instruction string optimization apparatus, which estimates the size of a constant so as to be a size close to and not less than the actual size of a constant which is resolved as an address difference value which can be estimated to some extent based on its relative position in a function before linkage.
The present invention is provided in view of above-mentioned problems and an object of the present invention is to provide an instruction string optimization apparatus used for processors which perform variable-length instructions and VLIW processors.
SUMMARY OF THE INVENTION
To attain the above-mentioned object, an apparatus of the present invention is characterized by comprising: code dividing means for dividing an instruction string comprising serially arranged instructions into sets of basic blocks each of the blocks being a string of sequential instructions having no branch in or branch out in the middle of the string; size dependence relation generation means for generating a size dependence relation representing the correspondence between a basic block having a constant to be resolved as an address difference and a depended basic block, the latter basic block being depended on by the former basic block and comprising an instruction string having a size on which the size of said constant depends; estimation order determining means for determining the order in which constants to be resolved as an address difference of a basic block are estimated; and size determining means for determining an unresolved size of said constant in a basic block selected according to said estimation order or determining an unresolved size of an instruction which uses said constant to be resolved in a basic block selected according to said estimation order.
REFERENCES:
patent: 5539907 (1996-07-01), Srivastava et al.
patent: 5768592 (1998-06-01), Chang
patent: 5787287 (1998-07-01), Bharadwaj
patent: 5923883 (1999-07-01), Tanaka et al.
patent: 5978588 (1999-11-01), Wallace
patent: 5999737 (1999-12-01), Srivastava
patent: 6061449 (2000-05-01), Candelore et al.
patent: 6139199 (2000-10-01), Rodriguez
patent: 6189141 (2001-02-01), Benitez et al.
patent: 6202199 (2001-03-01), Wygodny et al.
patent: 6269477 (2001-07-01), Fitzgerald et al.
patent: 6289507 (2001-09-01), Tanaka et al.
patent: 6460178 (2002-10-01), Chan et al.
patent: 11-73325 (1999-03-01), None
Odani Kensuke
Ogawa Hajime
Ingberg Todd
Matsushita Electric - Industrial Co., Ltd.
Parkhurst & Wendel L.L.P.
LandOfFree
Instruction string optimization with estimation of basic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Instruction string optimization with estimation of basic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction string optimization with estimation of basic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3100614