Software hint to improve the branch target prediction accuracy

Details Software hint to improve the branch target prediction accuracy Software hint to improve the branch target prediction accuracy

2001-03-01

2004-11-23

Tsai, Henry W. H. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Branching

C712S237000

Reexamination Certificate

active

06823447

ABSTRACT:

TECHNICAL FIELD
The present invention relates in general to methods for predicting branch target addresses in speculative instruction execution.
BACKGROUND INFORMATION
In some computer software, a “branch and link” instruction is executed to make a subroutine call. When a “branch and link” instruction executes, the address of the next instruction (where to return after the execution oft he branch) is placed in the link register and the execution starts from the target address of the branch instruction (the execution may continue on the fall through path, if the branch is a not-taken conditional branch). To return from the subroutine, a branch to link register (bclr) instruction is executed. This instruction has two forms, branch to link register (bclr) and branch to link register and link (bclrl). In this disclosure, these two forms are designated with the shortcut bclr[l] when both instructions are applicable. For nested sub-routine calls, the content of the link register is saved before making a new sub-routine call and restored after returning from that sub-routine.
Fetching an instruction precedes its execution by several machine cycles in high speed deeply pipelined microprocessors. Because of this, the content of the link register that should be used to start instruction fetching after a bclr[l] instruction has been found (and predicted taken) in the predicted path may not yet have the proper target address. Therefore, the content of the link register has to be predicted to keep instruction fetching far ahead of their execution.
If the link register is used only for subroutine calls and returns, a simple prediction mechanism may use a stack of link register values, called a “link stack”. When a bclr[l] instruction is found in the predicted path (and the predicted path is taken), the address of the next instruction is pushed (added in a specific order) into the link stack. For example the link stack pointer (address of link stack entry) is incremented by one on a “push” operation. When a bclr[l] instruction is found in the predicted path (and predicted path is taken), the last address pushed into the link stack is popped (read from the stack in a specific order) and used as the new address to start instruction fetching. During a “pop”, the link stack pointer is decremented by one. This approach should work perfectly, except for the following cases which may leave the link stack corrupted:
1. In the C programming language, a “long jump” instruction (usually used when an error case is detected) can cause the flow of instructions to skip several “subroutine returns” from nested subroutine calls.
2. In many compilers, an optimization called “tail recursion” is used. A recursive subroutine call in which the last statement is a call to itself is called a “tail recursion”. For example, let a subroutine A call subroutine B where subroutine B is a tail recursive subroutine. Then let B call itself several times before reaching the leaf subroutine call. When the leaf subroutine returns, it does not have to go through the nested returns (through the chain of subroutine calls to B itself), rather, it can directly return to the instruction in A that follows the first call to B.
3. In many computer architectures (e.g., PowerPC), if the distance (number of instructions) between a branch instruction and its target address is above a certain limit, instructions such as bclr[l] or “branch to count register” (bcctr) instruction are used and the target address is stored in a register such as a Link Register (LR) or a Count Register (CTR) before the branch instruction executes. In this disclosure, “branch to count register” and “branch to count register and link” may be designated as bcctr[l]. The bclr[l] instruction is sometimes used for reasons other than subroutine returns, for example, in some compilers it is used to implement the switch statement (in C programming language) and computed GOTO (in Fortran). For such use of the bclr[l] instruction, the link register is updated using a “move to link register” (mtlr) instruction.
The branch to count register instruction is used in some compilers for generating code for switch statements and computed GoTo statements. It is also used in “glue code” for the target address of an indirect subroutine call or for the target address to a subroutine call when the calling subroutine and the subsequent called subroutine do not belong to the same compilation module.
In many cases, the target address of the bcctr[l] instruction is highly predictable. For example, studies have shown that the indirect subroutine calls in many object-oriented programs do call the same subroutine most of the time, making the address highly predictable by remembering the target address used by the instruction in its last execution. In some processors, the target address is stored in an area called “Count Cache”. Count Cache is a small cache memory used in the prediction of target addresses for bcctr[l] instructions.
Branch instructions are used extensively in computer code for a variety of software functions. Since these branch instructions are key to speculative instruction execution, the accuracy of branch prediction is very important to improving instruction execution time. There has been much work done to improve branch direction prediction, however not much work has been done to improve branch target prediction. Therefore there is a need for a method for improving branch target prediction accuracy for modern computer systems.
SUMMARY OF THE INVENTION
A bit field in branch instructions is reserved for Hint bits which are added to the branch instruction by the programmer or the compiler depending on the use (context) of the branch instruction in software code. When the branch instruction is later speculatively executed, these Hint bits are decoded and used to direct the hardware as to the source of information and actions to take to improve the accuracy of the speculative branch instruction execution. A branch instruction may have multiple uses in a software routine, and Hint bits are only used in those branch instructions where the programmer or the compiler knows that the Hint bits and the corresponding hardware actions will improve instruction execution. The Hint bits are used in branch to link register (bclr) and branch to count register (bcctr) instructions; however, Hint bits may be used in other branch instructions and still be within the scope of the present invention. The hardware actions minimize link stack corruption and improve execution time by providing better branch prediction.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.


REFERENCES:
patent: 5136696 (1992-08-01), Beckwith et al.
patent: 5542109 (1996-07-01), Blomgren et al.
patent: 5655115 (1997-08-01), Shen et al.
patent: 5721855 (1998-02-01), Hinton et al.
patent: 5857104 (1999-01-01), Natarjan et al.
patent: 5887159 (1999-03-01), Burrows
patent: 6360297 (2002-03-01), Arimilli et al.
patent: 6446197 (2002-09-01), Krishnan et al.
Chen et al. “Analysis of Branch Prediction via Data Compression”, Proceedings of the 7th international Conference on Architectural Support fpr for Programming Languages and Operating Systems, vol. 31, 30 Issue 9, 5, Sep. 1996.

Affiliated with

Also associated with

Rating

Software hint to improve the branch target prediction accuracy does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Software hint to improve the branch target prediction accuracy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software hint to improve the branch target prediction accuracy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3351575