Electrical computers and digital processing systems: processing – Processing control – Branching
Utility Patent
1998-11-16
2001-01-02
Ellis, Richard L. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S219000, C712S238000
Utility Patent
active
06170054
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to the field of microprocessors. More specifically, the present invention relates to processing of instructions associated with subroutines in pipelined computers.
II. Background Information
The concept of pipelining of instructions in a computer is well known. In a pipeline computer, the processing of instructions such as fetching, decoding, execution, etc., is typically performed in a number of different pipeline stages. Each of the various pipeline stages process different instructions at the same time.
Pipelining is a more efficient method of processing instructions than the alternative waiting for a single instruction to be completely processed before beginning the processing of a second instruction. In the normal flow of a computer program, it is easy to know which instruction is next to enter the pipeline. In most instances, it is the sequentially next instruction that enters the pipeline. For example, an instruction at address A+1 will enter the pipeline after the instruction at address A entered the pipeline. One exception to this sequential flow of control is known as a branch instruction. One type of branch instruction is a “call” to a subroutine. A subroutine is a program or a sequence of instructions that may be “called” to perform the same tasks at different points in a program, or even in different programs.
Subroutines, pose problems for pipelined computers, particularly for those with many stages in the pipeline. Although the instruction which calls for a subroutine may contain enough information to determine which is the next instruction to enter the pipeline (i.e., the first instruction in the called subroutine), the return instruction in the subroutine does not contain such information. Instead, a return instruction needs to pass through all of the stages of the pipeline before the return address is determined from the return instruction. If the computer waited for the return instruction to pass through the pipeline before entering another instruction in the pipeline, a “bubble” would occur in the pipeline behind the return instruction. During a “bubble” there is no meaningful processing of instructions and the performance of the computer is slowed down.
To avoid bubbles, a prediction mechanism known as a return stack buffer has been in use. A return stack buffer stores the return address of a subroutine i.e., the address following the instruction that is causing the subroutine to be called, when a subroutine is called. When the subroutine has completed and control is returned to the main program flow by a return instruction, the return address is located in the stack and provided to the pipeline. The pipeline is then able to return control to the main program flow by entering the proper instruction into the pipeline. By keeping a stack of the return addresses, and using these return addresses to locate the next instruction upon return from the subroutine, bubbles in the pipeline may be eliminated.
A problem with the stack mechanism is the limited size of the stack and the complicated procedures to deal with stack overflows and underflows when there are a large number of subroutines that have been called, i.e., nested subroutines. In other words, if the stack contains twelve locations, only twelve subroutines may be called at one time without resorting to the complicated procedures for stack overflows. Circular buffers have been provided to overcome the problems posed by stacks. However, circular buffers also pose problems when there are more subroutine calls than the number of locations that store return addresses in the circular buffer, as return addresses may be overwritten for nested subroutines. When return addresses are overwritten, prediction of return instructions corresponding to the overwritten return addresses may generate mispredicted, return addresses. Furthermore, circular buffer implementations may not provide the right return addresses for subroutines in cases of misprediction of a branch that is not a call or return.
It is desirable to provide an apparatus and method, for subroutines in pipelined microprocessors, that provide uncorrupted return addresses in case of branch misprediction. It is also desirable that the above-mentioned apparatus and method detect underflow and overflow inaccuracies.
SUMMARY OF THE INVENTION
A method of operation in a microprocessor is disclosed. A return address cache (RAC) is initialized. The RAC includes a portion to store predicted subroutine return addresses (PSRA) and first and second corresponding cache portions to store retired most recently updated (RMRU) and speculative most recently updated (SMRU) ages of the PSRA respectively. A PSRA is stored in a portion of the RAC corresponding to a first SMRU age and the SMRU ages are incremented responsive to prediction of a call instruction. A PSRA is read from a portion of the RAC corresponding to a second SMRU age and the SMRU ages are decremented responsive to prediction of a return instruction.
REFERENCES:
patent: 5964868 (1999-10-01), Gochman et al.
IBM Technical Disclosure Bulletin,Return Address Stack Cache,vol. 34, No. 11, Apr. 1992, pp. 269-271.
IBM Technical Disclosure Bulletin,Subroutine Call/Return Stack,vol. 30, No. 11, Apr. 1988, pp. 221-225.
IBM Technical Disclosure Bulletin,Highly Accurage Subroutine Stack Prediction Mechanism,vol. 28, No. 10, Mar. 1986, pp. 4635-4637.
IBM Technical Disclosure Bulletin,Subroutine Return Address Stack,vol. 24, No. 7a, pp. 3255-3258.
Skadron, Kevin et al.,Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms,IEEE, 1988, pp. 259-271.*
Blakely , Sokoloff, Taylor & Zafman LLP
Ellis Richard L.
Intel Corporation
LandOfFree
Method and apparatus for predicting target addresses for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for predicting target addresses for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for predicting target addresses for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457309