Patent US5604877A successfully refreshed from Google Patents.
US5604877A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for resolving return from subroutine instructions in a computer processor
Assignee: Intel Corp
•
Filing: 1994-01-04
•
Granted: 1997-02-18
•
Expires: 2014-01-04
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 K. Gupta
- 👤 Michael A. Fetterman
- 👤 Subramanian Natarajan
- 👤 Sunil Shenoy
- 👤 Reynold V. D'Sa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 12:43
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: 31
Claim 1
Independent Claim
157 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 register, said branch target buffer circuit storing a return address into said return register after a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said branch target buffer circuit predicting a branch to said return address in said return register when a Return From Subroutine branch instruction is predicted by said branch target buffer circuit; and a return register valid bit, said return register valid bit determining how said branch target buffer circuit predicts said return address for said Return From Subroutine instruction.
Claim 2
Independent Claim
157 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 register, said branch target buffer circuit storing a return address into said return register after a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said branch target buffer circuit predicting a branch to said return address in said return register when a Return From Subroutine branch instruction is predicted by said branch target buffer circuit; and a return register valid bit, said return register valid bit determining how said branch target buffer circuit predicts said return address for said Return From Subroutine instruction.
Claim 3
Dependent Claim
93 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 1 wherein said return register valid bit is set after a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said branch target buffer circuit predicting a branch to said return address in said return register only when said return register valid bit is set, said branch target buffer circuit clearing said return register valid bit after said return address in said return register is predicted when a Return From Subroutine branch instruction is predicted.
Claim 4
Dependent Claim
68 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 2 further comprising a return stack buffer, said return stack buffer storing a stack of return addresses, said branch target buffer circuit predicting a branch to a return address on top of said return stack buffer when a Return From Subroutine branch instruction is predicted and said return register valid bit is clear.
Claim 5
Dependent Claim
75 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 3 further comprising a first return stack buffer pointer, said first return stack buffer pointer incremented and a return address pushed onto said return stack buffer when a Call Subroutine branch instruction is decoded, a return address popped off said return stack buffer and said first return stack buffer pointer decremented when a Return From Subroutine branch instruction is decoded.
Claim 6
Dependent Claim
101 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 4 further comprising a second return stack buffer pointer, said second return stack buffer pointer incremented when a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said second 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 7
Dependent Claim
40 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 5 wherein said return address popped off said return stack buffer is used to verify the return address predicted by said branch target buffer circuit.
Claim 8
Dependent Claim
48 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 5 wherein said return address popped off said return stack buffer is used to predict a return address when said branch target buffer circuit did not predict said Return From Subroutine branch instruction.
Claim 9
Dependent Claim
43 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 5 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 10
Dependent Claim
47 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 8 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 11
Dependent Claim
38 words
The apparatus for predicting return addresses for Return From Subroutine instructions as claimed in claim 9 wherein said second return stack buffer pointer set equal to said first return stack buffer pointer when a branch misprediction is detected.
Claim 12
Independent Claim
79 words
A method for handling Return From Subroutine instructions in a computer processor, said method comprising predicting branch instructions using a branch target buffer circuit; storing a return address in a return register when said branch target buffer circuit predicts a Call Subroutine instruction; determining a return register valid bit status; and predicting said return address in said return register when said branch target buffer circuit predicts a Return From Subroutine instruction based on said return register valid bit status.
Claim 13
Independent Claim
79 words
A method for handling Return From Subroutine instructions in a computer processor, said method comprising predicting branch instructions using a branch target buffer circuit; storing a return address in a return register when said branch target buffer circuit predicts a Call Subroutine instruction; determining a return register valid bit status; and predicting said return address in said return register when said branch target buffer circuit predicts a Return From Subroutine instruction based on said return register valid bit status.
Claim 14
Dependent Claim
101 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 11 wherein said method further comprises the steps of decoding said branch instructions; pushing a return address on a return stack buffer using a first return stack buffer pointer when a Call Subroutine instruction is decoded; popping a return address off said return stack buffer using said first return stack buffer pointer when a Return From Subroutine instruction is decoded; and predicting said return address popped off said return stack buffer when said branch target buffer circuit fails to predict a Return From Subroutine instruction.
Claim 15
Dependent Claim
48 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 12 wherein said method further comprises the steps of verifying said return address predicted by said branch target buffer circuit when said branch target buffer circuit predicts a Return From Subroutine instruction.
Claim 16
Dependent Claim
90 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 12 wherein said step of storing a return address in a return register further comprises setting a return register valid bit, said step of predicting said return address in said return register when said branch target buffer circuit predicts a Return From Subroutine instruction only occurs if said return register valid bit is set, and said step of predicting said return address in said return register further comprises clearing said return register valid bit.
Claim 17
Dependent Claim
87 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 14 further comprising the steps of incrementing a second return stack buffer pointer when a Call Subroutine instruction is decoded; decrementing said second return stack buffer pointer when a Return From Subroutine instruction is decoded; and predicting a return address from said return stack buffer using said second return stack buffer pointer when said branch target buffer circuit predicts a Return From Subroutine instruction and return register valid bit is clear.
Claim 18
Dependent Claim
42 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 15 wherein said step of decoding said branch instructions further comprises storing a copy of said first return stack buffer pointer in a branch information buffer.
Claim 19
Dependent Claim
51 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 16 further comprising the step of restoring said first return stack buffer pointer using said copy of said first return stack buffer pointer stored in said branch information buffer when a branch misprediction is detected.
Claim 20
Dependent Claim
43 words
The method for handling Return From Subroutine instructions in a computer processor as claimed in claim 17 further comprising the step of setting said second return stack buffer pointer equal to said first return stack buffer pointer when a branch misprediction is detected.
Claim 21
Dependent Claim
229 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, said branch instruction prediction 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 register, said branch target buffer circuit storing a return address into said return register after each said Call Subroutine instruction predicted by said branch target buffer circuit; a return register valid bit, said return register valid bit associated with said return register determining source of said return address predicted by said branch target buffer circuit; and a return address prediction mechanism, said return address prediction mechanism predicting a branch to said return address stored in said return register when said each said Return From Subroutine instruction is predicted by said branch target buffer circuit based on a return register valid bit.
Claim 22
Dependent Claim
229 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, said branch instruction prediction 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 register, said branch target buffer circuit storing a return address into said return register after each said Call Subroutine instruction predicted by said branch target buffer circuit; a return register valid bit, said return register valid bit associated with said return register determining source of said return address predicted by said branch target buffer circuit; and a return address prediction mechanism, said return address prediction mechanism predicting a branch to said return address stored in said return register when said each said Return From Subroutine instruction is predicted by said branch target buffer circuit based on a return register valid bit.
Claim 23
Dependent Claim
87 words
The branch instruction prediction mechanism as claimed in claim 19 wherein said return register valid bit is set after a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said branch target buffer circuit predicting a branch to said return address in said return register only when said return register valid bit is set, said branch target buffer circuit clearing said return register valid bit after said return address in said return register is predicted when a Return From Subroutine branch instruction is predicted.
Claim 24
Dependent Claim
62 words
The branch instruction prediction mechanism as claimed in claim 20 further comprising a return stack buffer, said return stack buffer storing a stack of return addresses, said branch target buffer circuit predicting a branch to a return address on top of said return stack buffer when a Return From Subroutine branch instruction is predicted and said return register valid bit is clear.
Claim 25
Dependent Claim
69 words
The branch instruction prediction mechanism as claimed in claim 21 further comprising a first return stack buffer pointer, said first return stack buffer pointer incremented and a return address pushed onto said return stack buffer when a Call Subroutine branch instruction is decoded, a return address popped off said return stack buffer and said first return stack buffer pointer decremented when a Return From Subroutine branch instruction is decoded.
Claim 26
Dependent Claim
95 words
The branch instruction prediction mechanism as claimed in claim 22 further comprising a second return stack buffer pointer, said second return stack buffer pointer incremented when a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said second 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 27
Dependent Claim
34 words
The branch instruction prediction mechanism as claimed in claim 23 wherein said return address popped off said return stack buffer is used to verify the return address predicted by said branch target buffer circuit.
Claim 28
Dependent Claim
42 words
The branch instruction prediction mechanism as claimed in claim 23 wherein said return address popped off said return stack buffer is used to predict a return address when said branch target buffer circuit did not predict said Return From Subroutine branch instruction.
Claim 29
Dependent Claim
37 words
The branch instruction prediction mechanism as claimed in claim 23 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 30
Dependent Claim
41 words
The branch instruction prediction mechanism as claimed in claim 26 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 31
Dependent Claim
32 words
The branch instruction prediction mechanism as claimed in claim 27 wherein said second return stack buffer pointer set equal to said first return stack buffer pointer when a branch misprediction is detected.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-18 | 2000-08-19 | 2001-02-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-18 | 2004-08-19 | 2005-02-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-18 | 2008-08-19 | 2009-02-18 | $7700.00 | Window Closed / Lapsed |