Patent US5768576A successfully refreshed from Google Patents.
US5768576A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for predicting and handling resolving return from subroutine instructions in a computer processor
Assignee: Intel Corp
•
Filing: 1996-10-29
•
Granted: 1998-06-16
•
Expires: 2016-10-29
Abstract
Abstract A method and apparatus for resolving Return From Subroutine instructions in a computer processor are disclosed. The method and apparatus resolve Return From Subroutine instructions in four stages. A first stage predicts Call Subroutine instructions and Return From Subroutine instructions within the instruction stream. The first stage stores a return address in a return register when a Call Subroutine instruction is predicted. The first stage predicts a return to the return address in the return register when a Return From Subroutine instruction is predicted. A second stage decodes each Call Subroutine and Return From Subroutine instruction in order to maintain a Return Stack Buffer that stores a stack of return addresses. Each time the second stage decodes a Call Subroutine instruction, a return address is pushed onto the Return Stack Buffer. Correspondingly, each time the second stage decodes a Return From Subroutine instruction, a return address is popped off of the Return Stack Buffer. The second stage verifies predictions made by the first stage and predicts return addresses for Return From Subroutine instructions that were not predicted by the first stage. A third stage executes Return From Subroutine instructions such that the predictions are verified. Finally, a fourth stage retires Return From Subroutine instructions and ensures that no instructions fetch after a mispredicted return address are committed into permanent state.
Inventors
- 👤 Bradley D. Hoyt
- 👤 Glenn J. Hinton
- 👤 David B. Papworth
- 👤 Ashwani Kumar Gupta
- 👤 Michael Alan Fetterman
- 👤 Subramanian Natarajan
- 👤 Sunil Shenoy
- 👤 Reynold V. D'Sa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 15:59
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F21/00; G06F21/50; G06F21/52; G06F9/30003; G06F9/3005; G06F9/30054; G06F9/32; G06F9/322; G06F9/323; G06F9/44; G06F9/448; G06F9/4482; G06F9/4484; G06F9/4486
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
160 words
An apparatus for predicting return addresses for Return From Subroutine instructions, said apparatus comprising a branch target buffer, said branch target buffer comprising a plurality of branch entries for storing information about a plurality of branch instructions; a branch target buffer circuit, said branch target buffer circuit predicting said plurality of branch instructions in a stream of computer instructions using said information stored in said branch target buffer; a return stack buffer, said return stack buffer for storing a stack of return addresses, said return stack buffer providing a return address when said branch target buffer circuit predicts a Return From Subroutine instruction, said return stack buffer further comprising a first return stack buffer pointer for indexing into said return stack buffer, said first return stack buffer in synchronization with an instruction fetch unit, and a second return stack buffer pointer for indexing into said return stack buffer, said second return stack buffer in synchronization with an instruction decode unit.
Claim 2
Independent Claim
160 words
An apparatus for predicting return addresses for Return From Subroutine instructions, said apparatus comprising a branch target buffer, said branch target buffer comprising a plurality of branch entries for storing information about a plurality of branch instructions; a branch target buffer circuit, said branch target buffer circuit predicting said plurality of branch instructions in a stream of computer instructions using said information stored in said branch target buffer; a return stack buffer, said return stack buffer for storing a stack of return addresses, said return stack buffer providing a return address when said branch target buffer circuit predicts a Return From Subroutine instruction, said return stack buffer further comprising a first return stack buffer pointer for indexing into said return stack buffer, said first return stack buffer in synchronization with an instruction fetch unit, and a second return stack buffer pointer for indexing into said return stack buffer, said second return stack buffer in synchronization with an instruction decode unit.
Claim 3
Dependent Claim
43 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 1 wherein said second return stack buffer pointer is incremented and a return address pushed onto said return stack buffer when a Call Subroutine branch instruction is decoded.
Claim 4
Dependent Claim
39 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 3 wherein said first return stack buffer pointer is incremented when a Call Subroutine branch instruction is predicted by said branch target buffer circuit.
Claim 5
Dependent Claim
43 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 3 wherein said first return stack buffer pointer used to predict a return address from said return stack buffer when a Return From Subroutine branch instruction is predicted.
Claim 6
Dependent Claim
43 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 2 wherein a return address is popped off said return stack buffer using said second return stack buffer pointer when a Return From Subroutine branch instruction is decoded.
Claim 7
Dependent Claim
43 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 3 further comprising a branch information buffer, said branch information buffer storing said a copy of said first return stack buffer pointer when a branch instruction is decoded.
Claim 8
Dependent Claim
47 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 6 wherein said first return stack buffer pointer is restored using said copy of said first return stack buffer pointer stored in said branch information buffer when a branch misprediction is detected.
Claim 9
Dependent Claim
38 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 7 wherein said second return stack buffer pointer set equal to said first return stack buffer pointer when a branch misprediction is detected.
Claim 10
Independent Claim
134 words
A method for handling Return From Subroutine instructions in a computer processor, said method comprising the steps of: predicting branch instructions using a branch target buffer circuit; predicting a first return address when said branch target buffer circuit predicts a Return From Subroutine instruction by popping a return address off a return stack buffer with a first return stack buffer pointer; decoding said branch instructions in an instruction decode unit; pushing a return address on a return stack buffer using a second return stack buffer pointer when a Call Subroutine instruction is decoded; and predicting a second return address by popping said second return address off said return stack buffer using said second return stack buffer pointer when a Return From Subroutine instruction that was not predicted by said branch target buffer is decoded.
Claim 11
Independent Claim
134 words
A method for handling Return From Subroutine instructions in a computer processor, said method comprising the steps of: predicting branch instructions using a branch target buffer circuit; predicting a first return address when said branch target buffer circuit predicts a Return From Subroutine instruction by popping a return address off a return stack buffer with a first return stack buffer pointer; decoding said branch instructions in an instruction decode unit; pushing a return address on a return stack buffer using a second return stack buffer pointer when a Call Subroutine instruction is decoded; and predicting a second return address by popping said second return address off said return stack buffer using said second return stack buffer pointer when a Return From Subroutine instruction that was not predicted by said branch target buffer is decoded.
Claim 12
Dependent Claim
49 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 9 wherein said method further comprises the steps of: verifying said return address predicted by said branch target buffer circuit when a Return From Subroutine instruction is decoded by said instruction decode unit.
Claim 13
Dependent Claim
42 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 9 wherein said step of decoding said branch instructions further comprises storing a copy of said second return stack buffer pointer in a branch information buffer.
Claim 14
Dependent Claim
51 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 11 further comprising the step of: restoring said second return stack buffer pointer using said copy of said second return stack buffer pointer stored in said branch information buffer when a branch misprediction is detected.
Claim 15
Dependent Claim
43 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 12 further comprising the step of setting said first return stack buffer pointer equal to said second return stack buffer pointer when a branch misprediction is detected.
Claim 16
Dependent Claim
239 words
A branch instruction prediction mechanism in a computer processor, said branch instruction prediction mechanism predicting branch instructions within a stream of computer instructions, said branch instructions comprising Call Subroutine instructions and Return From Subroutine instructions, branch instruction prediction said mechanism comprising a branch target buffer, said branch target buffer comprising a plurality of entries for storing information about said branch instructions; a branch execution unit, said branch execution unit executing a plurality of branch instruction in said stream of computer instructions, said branch execution unit storing information about said executed branch instructions in said branch target buffer; a branch target buffer circuit, said branch target buffer circuit predicting said executed branch instructions in said stream of computer instructions when said executed branch instructions are encountered again; a return stack buffer, said return stack buffer for storing a stack of return addresses, said return stack buffer further comprising a first return stack buffer pointer for indexing into said return stack buffer, said first return stack buffer in synchronization with an instruction fetch unit, a second return stack buffer pointer for indexing into said return stack buffer, said second return stack buffer in synchronization with an instruction decode unit, and a return address prediction mechanism, said return address prediction mechanism predicting a branch to said return address pointed to by said first return stack buffer pointer when said each said Return From Subroutine instruction is predicted by said branch target buffer.
Claim 17
Dependent Claim
239 words
A branch instruction prediction mechanism in a computer processor, said branch instruction prediction mechanism predicting branch instructions within a stream of computer instructions, said branch instructions comprising Call Subroutine instructions and Return From Subroutine instructions, branch instruction prediction said mechanism comprising a branch target buffer, said branch target buffer comprising a plurality of entries for storing information about said branch instructions; a branch execution unit, said branch execution unit executing a plurality of branch instruction in said stream of computer instructions, said branch execution unit storing information about said executed branch instructions in said branch target buffer; a branch target buffer circuit, said branch target buffer circuit predicting said executed branch instructions in said stream of computer instructions when said executed branch instructions are encountered again; a return stack buffer, said return stack buffer for storing a stack of return addresses, said return stack buffer further comprising a first return stack buffer pointer for indexing into said return stack buffer, said first return stack buffer in synchronization with an instruction fetch unit, a second return stack buffer pointer for indexing into said return stack buffer, said second return stack buffer in synchronization with an instruction decode unit, and a return address prediction mechanism, said return address prediction mechanism predicting a branch to said return address pointed to by said first return stack buffer pointer when said each said Return From Subroutine instruction is predicted by said branch target buffer.
Claim 18
Dependent Claim
65 words
The branch instruction prediction mechanism as claimed in claim 14 wherein said second return stack buffer pointer is incremented and a return address pushed onto said return stack buffer when a Call Subroutine branch instruction is decoded and a return address is popped off said return stack buffer and said second return stack buffer pointer decremented when a Return From Subroutine branch instruction is decoded.
Claim 19
Dependent Claim
89 words
The branch instruction prediction mechanism as claimed in claim 15 wherein said first return stack buffer pointer is incremented when a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said first return stack buffer pointer used to predict a return address from said return stack buffer when a Return From Subroutine branch instruction is predicted and said return register valid bit is clear, said second return stack buffer pointer decremented when a Return From Subroutine branch instruction is predicted by said branch target buffer circuit.
Claim 20
Dependent Claim
42 words
The branch instruction prediction mechanism as claimed in claim 16 further comprising: a branch information buffer, said branch information buffer storing said a copy of said second return stack buffer pointer when a branch instruction is decoded by said instruction decode unit.
Claim 21
Dependent Claim
41 words
The branch instruction prediction mechanism as claimed in claim 17 wherein said second return stack buffer pointer is restored using said copy of said second return stack buffer pointer stored in said branch information buffer when a branch misprediction is detected.
Claim 22
Dependent Claim
32 words
The branch instruction prediction mechanism as claimed in claim 18 wherein said first return stack buffer pointer set equal to said second return stack buffer pointer when a branch misprediction is detected.
References Cited (Backward Citations)
US4394729A
Cited
US5355459A
Cited
US5179673A
Cited
US5276882A
Cited
US5592637A
Cited
US5313634A
Cited
US5604877A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-15 | 2001-12-15 | 2002-06-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-15 | 2005-12-15 | 2006-06-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-15 | 2009-12-15 | 2010-06-16 | $7700.00 | Window Closed / Lapsed |