Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-03-08
2003-01-07
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C710S261000, C710S269000
Reexamination Certificate
active
06505296
ABSTRACT:
THE FIELD OF THE INVENTION
The present invention generally relates to the execution of instructions in computer systems and more particularly to a trampoline mechanism for effecting control flow change in a computer system to emulate a branch, such as a trampoline mechanism employed for recovery of an exception caused by advanced or speculatively executed instructions.
BACKGROUND OF THE INVENTION
Computer systems include at least one processor and memory. The memory stores program instructions, data, and an operating system. The program instructions can include a compiler for compiling application programs. The operating system controls the processor and the memory for system operations and for executing the program instructions.
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, 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 forgoing 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 no instructions in the basic block are executed.
Thus, control flow between basic blocks in computer programs is typically effected with branches. A branch typically evaluates some condition and conditionally changes control flow to a new basic block, based on the outcome of the condition.
In some cases, a branch is very unlikely to be taken, such as when the branch occurs as a result of an error condition which generally does not arise during normal program execution. For such unlikely cases, branches are still typically employed to effect control flow change to a special basic block to handle the error condition.
An alternative approach that has been employed for handling error conditions is for the error condition to cause an interruption. The interruption generally invokes a different control flow mechanism and redirects execution to a special program referred to as a generic interruption handler, which is typically part of an operating system. Typically, the generic interruption handler handles the error condition in one of two ways depending on the type of error condition.
In the first scenario, the generic interruption handler responds to the error condition and resolves the problem associated with the error condition. The program which caused the error condition is then restarted at the point where the program encountered the error. In this first scenario, the error condition is generic across programs (e.g., a translation look-aside buffer (TLB) translation miss error condition). Therefore, the resolution of the error condition is performed entirely by the generic interruption handler. The generic interruption handler resolves the error condition in the same way no matter what function the program that encountered the error condition performs.
In the second scenario, the generic interruption handler determines that the program that encountered the error condition is to handle the error condition. Typically, the program provides some information to the generic interruption handler to indicate that the program itself is to handle the error condition. In addition, the program typically indicates which portion of the program should be invoked upon an error condition. After the generic interruption handler determines that the generic interruption handler cannot deal with the error condition itself and that the program that encountered the error condition has indicated that the program is to deal with the error condition, the generic interruption handler typically builds a data structure and invokes the program's own specific handler. The data structure built by the generic interruption handler is typically very large, because the generic interruption handler does not have sufficient information to determine which data items are required to handle the error condition. The error condition is then handled by the program directly. After the program completes the handling of the error condition, the operating system is invoked again to restart the program at the point where the error was encountered. This approach for handling an error condition is referred to as a signal handler approach and the generic interruption handler is referred to as a signal handler.
In summary, when changes in control flow are effected based on conditions which are relatively infrequent and which require specialized handling (i.e., not generic handling), there are two basic approaches that have been employed to effect control flow. In the first approach, a branch is made to the specialized handler portion of the program. In the second approach, a generic signal handler which is typically part of the operating system, is invoked via an interruption to control flow and the generic signal handler builds a data structure and invokes the specialized handler portion of the program.
These two basic approaches have generally worked well for simple scalar processors. Either approach generally involves some instruction, such a conditional branch or some other instruction that causes an interruption based on a condition. In earlier computer systems, the overhead for conditional branch instructions was similar to the overhead for other instructions that cause an interruption based on a condition.
The overhead for branch instructions, however, has increased significantly with present day computer systems and is projected to increase further with future computer systems. In many computer systems, some costly branch mispreditions are avoided when programs indicate that the branch is unlikely and the processor factors this into branch prediction. Nevertheless, as computer systems become wider, the need to execute multiple branches each cycle increases. Executing multiple branches each cycle requires additional resources and/or complicates branch prediction which decreases the accuracy of the prediction. Therefore, the effective costs of a branch instruction for a relatively rare condition is increasing.
On the other hand, optimizations are now being employed to effectively treat the most-likely path of a program as a single unit. Less-likely paths of the program are treated similar to error conditions. One advantage of this optimization technique is that it permits much better scheduling of hardware resources on the most-likely program path. This kind of less-likely path “error condition” is infrequent, but not nearly as infrequent as the traditional kind of error condition handled by the signal handler approach. The signal handler approach involves a tremendous amount of overhead and is only effective when the likelihood of the error is not merely small, but miniscule.
In view of the above, there is a need for an improved mechanism for changing control flow without branches for infrequent, but not ultimately rare, situations. A computer system employing such an improved control flow change mechanism is desired to permit better code scheduling, to avoid misprediction problems, and to avoid complications resulting from multiple branches per cycle. Furthermore, there is a desire that such an improved control flow change mechanism be much faster, when invoked, than the high overhead signal handler approach, so that the improved control flow change mechanism's performance cost is not significant.
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 “stat
Hays James O.
Huck Jerome C.
Morris Dale C.
Ross Jonathan K.
LandOfFree
Emulated branch effected by trampoline mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Emulated branch effected by trampoline mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Emulated branch effected by trampoline mechanism will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056992