Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-11-04
2003-10-14
Chaki, Kakali (Department: 2124)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S228000, C712S233000
Reexamination Certificate
active
06633974
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to information processing, and in particular to an apparatus and method for controlling link stack corruption during branching.
BACKGROUND INFORMATION
Modern high frequency microprocessors are typically deeply pipelined devices. For efficient instruction execution in such processors, instructions are often fetched and executed speculatively. An instruction may be fetched many cycles before it is executed. Since branch instructions may cause instruction fetching to start from a non-sequential location, the direction and target of a branch instruction is predicted when the branch is fetched so that instruction fetching can proceed from the most likely address. The prediction is compared with the actual direction and target of the branch instruction when the instruction is executed. If it is determined that the branch has been mispredicted (either its target or its direction), then the branch instruction is completed and all instructions fetched after the branch are flushed out of the instruction pipeline and new instructions are fetched either from the sequential path of the branch (if the branch is resolved as not taken) or from the target path of the branch (if the branch is resolved as taken).
Often there are a number of branches (i.e., subroutine calls and returns) between the instructions that are being fetched and the instructions that are being executed in the processor execution units. Therefore, to handle subroutine calls and returns efficiently, many high frequency microprocessors employ a link stack. On a subroutine call, the address of the following instruction is “pushed” into the stack while on a subroutine return, the contents at the top of the stack (which is expected to contain the address of the instruction following the original subroutine call) are “popped” from the stack. Since pushing and popping from a hardware stack can normally be done when the branch is fetched, which is several cycles before the corresponding branches are executed in a deeply pipelined processor, such a linked stack mechanism helps implement the instruction fetching scheme across subroutine calls and returns to a great extent. Notwithstanding, the link stack can become corrupted during the process of speculative instruction fetching and execution.
Consider, for example, the case where a subroutine call is performed using a “branch and link instruction” and a return from subroutine is achieved using a “branch to link register” or “bclr” instruction. It may happen that a “bclr” instruction, which for example returns to a location “A”, is fetched speculatively followed by a speculative fetch of a “branch and link” instruction, for example from call-site B. The link stack is updated at fetch time, such that after these instructions are fetched, the address location “A” is replaced by the address location “B+4” (each instruction consists of four bytes) at the top of the link stack. Since both the “bclr” and “branch and link” instructions are speculatively fetched, they may not ultimately be in the actual execution path. If these instructions are not in fact in the actual execution path, (in which case the instructions are flushed out), the link stack becomes corrupted.
Generally, any time one or more “bclr” instructions are followed by one or more “branch and link” instructions in the speculated path, the link stack becomes corrupted if the speculation turns out to be wrong. For a commercial programming workload, about 2% of the instructions are “bclr” instructions and therefore it becomes very important to be able to predict the target address for these instructions with a good degree of accuracy in deeply pipelined machines. Thus, the need has arisen for circuits, systems and methods to control link stack corruption, as well as to recover a link stack from corrupted condition.
SUMMARY OF THE INVENTION
The principles of the present invention are embodied in circuits, systems and methods for executing branch instructions. In accordance to one embodiment of these principles, instruction branching circuitry is disclosed which includes a plurality of logical stacks each having a plurality of entries for storing an address to a corresponding instruction in memory. A counter generates a pointer to an entry of an active one of the logical stacks, the counter including incrementation logic incrementing a stored pointer value following a Push operation and decrementation logic decrementing the stored pointer value following a Pop operation to the active logical stacks. Selector circuitry selects the active one of the logical stacks in accordance with the performance of the Push and Pop operations.
According to one specific embodiment of the inventive principles, the selector circuitry changes the active stack from a first stack to a second stack in response to a Pop operation followed by an instruction for a Push operation, the Push operation then performed to the second stack. In a second particular embodiment, the selector circuitry changes the active stack in response to the state of a bit associated with information popped from the active stack during a Pop operation.
The principles of the present invention provide substantial advantages over the prior art. Among other things, circuitry and methods are provided which allow for the control of link stack corruption. In particular, the present inventive principles allow for the construction and operation of a register file of m−logically separate stacks which allows recovery of m−1 number of redirections caused by misspeculation during the execution of branching instructions.
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: 5021993 (1991-06-01), Matoba et al.
patent: 5050067 (1991-09-01), McLagan et al.
patent: 5142634 (1992-08-01), Fite et al.
patent: 5313634 (1994-05-01), Eickemeyer
patent: 5511192 (1996-04-01), Shirakihara
patent: 5574871 (1996-11-01), Hoyt et al.
patent: 5604877 (1997-02-01), Hoyt et al.
patent: 5634046 (1997-05-01), Chatterjee et al.
patent: 5950221 (1999-09-01), Draves et al.
patent: 5964868 (1999-10-01), Gochman et al.
patent: 6006323 (1999-12-01), Ma et al.
patent: 6088787 (2000-07-01), Predko
patent: 6170054 (2001-01-01), Poplingher
patent: 6185597 (2001-02-01), Paterson et al.
patent: 6289444 (2001-09-01), Nair
patent: 6314514 (2001-11-01), McDonald
patent: 6526503 (2003-02-01), Sinharoy
“MC68030: Enhanced 32-Bit Microprocessor User's Manual Second Edition”; Motorola, Inc.; 1989.*
Rosenberg, Jerry M.; “Dictionary of Computers, Information Processing and Telecomuications, Second Edition”; John Wiley & Sons, Inc.; 1987; p. 526.*
Clark et al. “Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms”. Microarchitecture, 1998. MICRO-31. Proceedings. 31st Annual ACM/IEEE International Symposium on, 1998. pp 259-271.*
Hennessy et al. Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers, Inc.; 1996; pp. 232.*
Stephan Jourdan et al., “Recovery Requirements of Branch Prediction Storage Structures in the Presence of Mispredicted-Path Execution,”International Journal of Parallel Programming, vol. 25, No. 5 1997, p. 363-383.
Chaki Kakali
McBurney Mark E.
Newberger Barry S.
Winstead Sechrest & Minick P.C.
Wood William H.
LandOfFree
Apparatus and method for controlling link stack corruption... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for controlling link stack corruption..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for controlling link stack corruption... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129162