Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-10-01
2001-10-09
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C712S244000, C712S222000, C712S208000
Reexamination Certificate
active
06301705
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of the Invention
The present invention generally relates to computer program code optimization, and more particularly to a system and method for supporting code optimization through the deferral of exceptions generated during speculative execution.
2. Discussion of the Related Art
As is known, the performance of a computer system may be enhanced by optimizing the code of a computer program so that the computer can execute the program more quickly. One of the steps in optimizing a program is a process called scheduling. Scheduling is a process where the series of computer operations that comprise a program are organized for execution. During the scheduling process, operations of the program may be arranged, eliminated, or moved to make the program run more efficiently for a particular CPU design. Generally, there are two forms of scheduling: dynamic scheduling performed by the hardware during execution of a program, and static scheduling performed by a compiler before execution. Either of these techniques, or a combination of both, may be used to schedule operations in a computer program for processing by a computer system.
A computer program consists of a series of instructions to be carried out by a central processing unit (CPU) in the computer system. A typical program is written in a high level language and then compiled into a series of instructions compatible with the instruction set architecture of the CPU. A program, however, may also be directly written in “machine language” according to the instruction set architecture of the computer. The instruction set architecture defines the format or encoding of operations, including operators and operands in an instruction. Depending on the structure of the CPU and the scheduling techniques involved, each instruction may have one or more operations. An operation includes an operator encoded in an opcode representing functions such as add, subtract, load, store, branch, etc. Additionally, an operation identifies the operands and the results of the operation. To accomplish this, the operation typically includes a code identifying the location such as a register of an operand or operands. It is these operations that are organized for execution by the CPU using the optimization techniques.
There are different levels of optimization. One level of optimization is local optimization where code within a straight-line code fragment or “basic block” is manipulated to run more efficiently. By way of definition, a “basic block” is a contiguous set of instructions bounded by branches and/or branch targets, containing no branches or branch targets. This implies that if any instruction in a basic block is executed, then all instructions in the basic block will be executed, i.e. the instructions contained within any basic block are executed on an all-or-nothing basis. The instructions within a basic block are enabled for execution when control is passed to the basic block by an earlier branch targeting the basic block (“targeting” as used here includes both explicit targeting via a taken branch as well as implicit targeting via a not taken branch). The foregoing implies that if control is passed to a basic block, then all instructions in the basic block must be executed; if control is not passed to the basic block, then all instructions in the basic block must not be executed. The act of executing, or specifying the execution of, an instruction before control has been passed to the instruction is called “speculation.” Speculation performed by the processor at program runtime is called “dynamic speculation” while speculation specified by the compiler is called “static speculation.” Dynamic speculation is known in the prior art.
Two instructions are deemed “independent” when one does not require the result of the other; when one instruction does require the result of the other they are termed “dependent” instructions. Independent instructions may be executed in parallel while dependent instructions must be executed in serial fashion. Program performance is improved by identifying independent instructions and executing as many of them in parallel as possible. Experience indicates that more independent instructions can be found by searching across multiple basic blocks than can be found by searching only within individual basic blocks, however, simultaneously executing instructions from multiple basic blocks generally requires speculation. Identifying and scheduling independent instructions, and thereby increasing performance, is one of the primary tasks of compilers and processors.
The trend in compiler and processor design has been to increase the scope of the search for independent instructions in each successive generation. In prior art instruction sets, an instruction that may generate an exception cannot be speculated by the compiler since, if the instruction causes an exception, the program may erroneously generate an exception when the program should not have. This restricts the useful scope of the compiler's search for independent instructions and makes it necessary for speculation to be performed at program runtime by the processor via dynamic speculation. However, dynamic speculation entails a significant amount of hardware complexity, furthermore, the complexity increases exponentially with the number of basic blocks over which dynamic speculation is applied—this places a practical limit on the scope of dynamic speculation. By contrast, the scope over which the compiler can search for independent instructions is much larger—potentially the entire program. Furthermore, once the compiler has been designed to perform static speculation across a single basic block boundary, very little additional complexity is incurred by statically speculating across several basic block boundaries.
Examples of local optimization techniques are common subexpression elimination and constant propagation. Another level of optimization is global optimization which includes extending local optimization techniques across conditional branches in a program and further includes transformations for optimizing loops. One form of global optimization is code motion. An example of code motion is removing code from a loop that computes the same value each iteration of a loop. A third level of optimization is machine dependent optimization. Machine dependent optimization involves manipulation of code to take advantage of specific architectural attributes of the CPU. For example, if the CPU has a pipelined functional unit for executing instructions concurrently, then code can be reordered to improve pipeline performance.
To optimize a program, code may be moved above a conditional branch in a scheduling process called speculative code motion. Speculative code motion refers to the movement of an instruction above a conditional branch that controls its execution. The execution of a “speculative” instruction may be referred to as speculative or anticipatory execution because the instruction is executed before it is known whether the instruction will actually be used in the program. Speculative code motion can enhance instruction level parallelism. Because many instructions have a long latency, meaning they take several clock cycles to execute, it is advantageous to execute an instruction speculatively. They delay that an instruction would otherwise cause can be minimized by issuing the instruction in advance. Speculative code motion may also be useful in other optimizations such as redundancy elimination.
If static speculation is to be undertaken, then several problems must be solved, one of the most important of which is the handling of exceptional conditions encountered by statically speculated instructions.
Since, as noted above, exceptions on speculative instructions cannot be delivered at the time of execution of the instructions, a compiler-visible mechanism is needed to defer the delivery of the exceptions until control is passed to the basic block from which the instructions were speculated (known as the “originating basic block”
Colon-Bonet Glenn T.
Doshi Gautam B.
Huck Jerome C.
Karp Alan H.
Markstein Peter
Dam Tuan Q.
Institute for the Development of Emerging Architectures L.L.C.
LandOfFree
System and method for deferring exceptions generated during... 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 and method for deferring exceptions generated during..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for deferring exceptions generated during... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609163