Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-08-06
2001-12-04
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C712S234000
Reexamination Certificate
active
06327704
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention generally relates to computer systems or computer-implemented systems employing translating or optimizing compilers and methods, and, more particularly, to dynamic translating compilers and methods.
2. Related Art
A variety of techniques are known for static translation of the executable instructions of a computer software program. Such known techniques are implemented by static compilers, i.e., compilers that translate a program prior to execution. One disadvantage of such techniques is that the dynamic behavior of a program typically is more readily and accurately ascertained while it is being executed than while it is being compiled prior to execution.
Some systems and methods exist that avoid this disadvantage by a process generally referred to as dynamic translation. That is, a dynamic compiler operates upon an executable image of the original software program as it is being executed at run time. Typically, the dynamic compiler is thus better able to deduce those paths that execution is most likely to take through particular portions of the program (often referred to as the control flow through the instructions of the program).
Such known dynamic translation systems may be designed to accomplish one or more of a number of tasks. One task is referred to as cross-platform translation, in which a program designed and written for execution on a computer system having a particular architecture and operating system is translated so that the translated program may be executed on another type of computer system. Some existing dynamic translation systems include “Daisy” by International Business Machine Corporation, “fx!32” from Digital Equipment Corporation, and “Wabi” from Sun Microsystems.
Dynamic translation systems are also used for instrumentation and profiling of programs without the need for recompilation. The term “instrumentation” refers generally to the insertion of special code to detect or record various parameters of execution, and “profiling” refers generally to reporting such parameters. Such use may also be referred to as “monitoring.” Examples of existing products intended for such uses include “Shade” from Sun Microsystems and “ATOM” from Digital Equipment Corporation.
Such tasks of dynamic translation systems generally are also undertaken by static translation systems, albeit with the noted disadvantage. However, another task traditionally carried out by static translation systems is not adequately carried out by known dynamic translation systems. Such task is optimization; that is, the alteration, deletion, rearrangement, or other revision of instructions, or the addition of new instructions, with the specific objectives of increasing the speed of execution of executable instructions, decreasing the amount of computer resources needed for such execution, or both. Therefore, what is needed is a system, method, and product for increasing the opportunities for, and efficiencies of, dynamic optimization of executable instructions. More generally, what is needed is a system, method, and product for increasing the efficiencies of dynamic translation systems irrespective of their purpose.
SUMMARY OF THE INVENTION
The present invention is a system, method, and product for improving the speed of dynamic translation systems by backpatching multi-branch-jump instructions that have been translated. (As the term is used herein, an “instruction” may specify an operation, such as jump, add, or compare; may specify an address; or may perform another of a variety of known functions.) In one embodiment of the invention, a multi-branch backpatching dynamic translator is disclosed. In one aspect of such embodiment, the multi-branch backpatching dynamic translator undertakes backpatching on an “as-needed” basis at run time. That is, backpatching is done for those branch targets that are executed rather than for all branch targets, or rather than for those branch targets that are estimated or assumed will be executed.
The term “backpatch,” and its grammatical variants, will be understood by those skilled in the relevant art to refer to the replacement, typically by overwriting, of one or more executable instructions by new executable instructions. Typically, the function of backpatching is to redirect a jump instruction so that it transfers control to a new target instruction. With respect to the present invention, such new target instruction typically is the first-executed in a group of instructions that are a translated version of the instructions to which the backpatched jump instruction passed control. Optionally, such translated instructions may also be dynamically instrumented, optimized, profiled, otherwise processed, or any combination thereof. The terms “dynamically instrumented,” “dynamically optimized,” and their grammatical variants, refer respectively herein to the application of any of a variety of instrumentation and optimization techniques, now known or to be developed in the future, to instructions or groups of instructions at run time.
As the term is used herein, a “multi-branch-jump instruction” is one in which control is transferred from such instruction to one of two or more instructions, referred to herein as “target instructions.” Also, as the term is used herein, a multi-branch-jump instruction typically is an indirect jump instruction; that is, it passes control to an address containing another address to which control is in turn passed.
To effectuate such indirect jumps, a multi-branch-jump instruction typically utilizes a table with entries representing the addresses, or offsets from a base address, at which the target instructions of the indirect jumps are stored. Such a table is referred to herein as a “multi-branch-jump table” (also commonly referred to as a “switch table”). It will be understood by those skilled in the relevant art that a multi-branch-jump table may, for example, be constructed by a static compiler so that it includes possible target-instruction addresses. At run time, an index into the table typically is generated to specify to which of the possible target instructions control passes. As used herein, the term “multi-branch-jump table” is used broadly to refer to any known, or later-to-be developed, technique for specifying an address to which control passes. For example, the addresses specified in the instructions of a multi-branch-jump table may be kept in registers, or in memory locations that need not be contiguous. Also, the instructions of a multi-branch-jump table need not be included in a contiguous block of instructions such as is illustratively illustrated herein.
The term “hot trace” is used herein to refer to a trace through which control frequently passes, or, in some embodiments, has passed more than a predetermined number of times. For convenience, the term “frequent,” and its grammatical variants, are used herein to refer both to control passing through instructions either at a rate, or for a number of times, greater than a threshold value. A trace typically is made up of one or more “instruction blocks,” which are groups of original instructions of an executable file. An instruction block is made up of one or more “basic blocks,” each of which is a sequence of original instructions of an executable file. Each of the original instructions of a basic block may be reached through a common control path. That is, there is only one entrance into, and one exit out of, a basic block. The entrance is the first instruction in the sequence, and the exit is the last instruction in the sequence. A basic block may consist of a single instruction.
As the term is illustratively used herein, an instruction block also has one exit instruction through which control passes out of the block, which is the last instruction in the block. However, control may enter an instruction block through more than one instruction of the block. That is, because an instruction block may include more than one basic block, and control may pass to the first instruction of a basic block
Benitez Manuel E.
Buzbee William B.
Mattson, Jr. James S.
Shah Lacky V.
Dam Tuan Q.
Hewlett--Packard Company
Kendall Chuck O.
LandOfFree
System, method, and product for multi-branch backpatching in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method, and product for multi-branch backpatching in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and product for multi-branch backpatching in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574653