Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-05-04
2001-02-13
Hafiz, Tariq R. (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06189141
ABSTRACT:
RELATED APPLICATIONS
The following applications are related to the present application.
U.S. Patent Application entitled “SYSTEM, METHOD, AND PRODUCT FOR JUMP-EVALUATED TRACE DESIGNATION,” attorney docket number 10971492-1, naming as inventors Lacky V. Shah, James S. Mattson, Jr., and William B. Buzbee, assigned to the assignee of the present invention and filed concurrently herewith.
U.S. Patent Application entitled “METHOD, APPARATUS, AND PRODUCT FOR DYNAMIC SOFTWARE CODE TRANSLATION SYSTEM,” attorney docket number 10980332-1, naming as inventors James S. Mattson, Jr., William B. Buzbee, and Lacky V. Shah, assigned to the assignee of the present invention and filed concurrently herewith.
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 dynamic optimization of executable instructions.
In particular, what is needed is a system, method, and product for determining those particular sequences of instructions of an original executable file such that, if the instructions are translated and optimized, quicker execution, reduced resource usage, or both, will most likely be achieved. Such selectivity generally is advantageous because it is possible to spend more time translating and optimizing instructions than will be gained by such translation and optimization. For example, control may flow through a group of instructions that, for any of a variety of reasons, is not amenable to, or significantly benefited by, optimization. Accordingly, what is particularly needed is a system, method, and product for selecting sequences of instructions, based on control flow through such instructions at run time, that are most amenable to dynamic optimization.
SUMMARY OF THE INVENTION
The present invention is a system, method, and product for continuous path evaluation at run time in order to identify and evaluate hot traces. In one aspect of the invention, a control-path-evaluating trace designator is disclosed. The control-path-evaluating trace designator designates at least one hot trace, if present, in the original instructions of the executable file. A hot trace is a trace through which control frequently passes, or has passed more than a predetermined number of times, as determined in accordance with the invention and described below. 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 (sometimes referred to as the magnitude of occurrences), greater than a threshold value. In one embodiment, such threshold is predetermined. In alternative embodiments, such threshold is dynamically selected or adjusted (hereafter, simply “dynamically adjusted”).
A trace typically is made up of one or more blocks of original instructions of an executable file, each of which may be reached through a common control path. A block is made up of one or more basic blocks. A basic block typically is a sequence of instructions of an executable file such that there is only one entrance into the basic block and such entrance is the first instruction in the sequence. A basic block may also consist of a single instruction. A basic block has at least one exit instruction from which control passes out of the basic block to another basic block. A control path from one block to another block is referred to herein as an arc. The action of transferring control over an arc, other than by an unconditional fall-through, is referred to as a jump. An unconditional fall-through is the unconditional passing of control from a first instruction to the instruction immediately following such first instruction. An instruction that causes a jump to occur is referred to herein as a jump instruction. The instruction to which a jump is directed is referred to herein as a target instruction.
In one embodiment, the control-path-evaluating trace designator includes a hot block manager that identifies a block as a hot block if control flows through the block at a frequency that is equal to, or greater than, a start-instruction frequency threshold. Such threshold may be predetermined, or, in alternative implementations, it may be dynamically adjusted. The hot block manager also translates and instruments the hot blocks to continuously record occurrences of control flow through them. In some implementations, the hot block manager removes hot blocks that have become cold. Such removal is undertaken if the frequency of control flow through the hot block has changed so that it has decreased to, or below, a cold-block threshold.
In one embodiment, the control-path-evaluating trace designator also includes a backpatcher that determines if a first translated hot block includes a target instruction that is a target of a jump instruction that is part of a second translated hot block. If so, the backpatcher backpatches the translated jump instruction so that control is directed through it to the target instruction.
The control-path-evaluating trace designator may also include a hot trace selector that selects at least one hot trace, if present. The hot trace is so selected if it includes a first hot block through which control has passed
Benitez Manuel E.
Buzbee William B.
Mattson, Jr. James S.
Shah Lacky V.
Hafiz Tariq R.
Hewlett--Packard Company
Ingberg Todd
LandOfFree
Control path evaluating trace designator with dynamically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Control path evaluating trace designator with dynamically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control path evaluating trace designator with dynamically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2589454