US5333283A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Case block table for predicting the outcome of blocks of conditional branches having a common operand
Assignee: International Business Machines Corp
•
Filing: 1991-10-29
•
Granted: 1994-07-26
•
Expires: 2011-10-29
Abstract
Abstract A method and apparatus is disclosed for folding the execution of a multi-way branch or switch based upon an operand (e.g.,the block of instructions normally associated with a case statement) into a single instruction. This insulates branch prediction mechanisms from making incorrect predictions that are normally associated with a multi-way branch. A table saves the past history of multi-way branch execution. This table contains three fields: the starting address of a multi-way branch; a value of the operand used to execute that multi-way branch in the past; and the larger target address generated by that multi-way branch in the past when that particular operand value was used. In accordance with one embodiment of this invention, other branch prediction mechanisms (such as a Branch History Table or Decode History Table) are disabled from redirecting instruction fetching during execution of a multi-way branch in an instruction stream.
Inventors
- 👤 Philip G. Emma
- 👤 David R. Kaeli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 08:22
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/3005; G06F9/30054; G06F9/30061; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
215 words
An apparatus for predicting outcomes of blocks of conditional branch instructions having a common operand, comprising: a look-up table including a plurality of entries, each of the entries having a first field for storing a starting address for a block of the conditional branch instructions, a second field for storing a previous value of the common operand for the block and a third field for storing a target address produced when the previous value was used to execute the block; processor means, coupled to the look-up table, the processor means including: (a) means for detecting that one of the blocks is to be processed and for determining the starting address of the one of the blocks; (b) means for determining a current value of the common operand; (c) means for determining whether the look-up table contains a corresponding entry wherein the starting address of the one of the blocks matches data in the first field and the current value of the common operand matches the previous value of the common operand; (d) means, responsive to a determination that there is a corresponding entry, for prefetching an instruction at the target address stored in the third field of the corresponding entry prior to fetching of any of said conditional branches in the one of the blocks.
Claim 2
Independent Claim
215 words
An apparatus for predicting outcomes of blocks of conditional branch instructions having a common operand, comprising: a look-up table including a plurality of entries, each of the entries having a first field for storing a starting address for a block of the conditional branch instructions, a second field for storing a previous value of the common operand for the block and a third field for storing a target address produced when the previous value was used to execute the block; processor means, coupled to the look-up table, the processor means including: (a) means for detecting that one of the blocks is to be processed and for determining the starting address of the one of the blocks; (b) means for determining a current value of the common operand; (c) means for determining whether the look-up table contains a corresponding entry wherein the starting address of the one of the blocks matches data in the first field and the current value of the common operand matches the previous value of the common operand; (d) means, responsive to a determination that there is a corresponding entry, for prefetching an instruction at the target address stored in the third field of the corresponding entry prior to fetching of any of said conditional branches in the one of the blocks.
Claim 3
Dependent Claim
16 words
The apparatus of claim 1 further comprising a branch history table coupled to the processing means.
Claim 4
Dependent Claim
37 words
The apparatus of claim 1, further comprising: means responsive to a determination that said look-up table does not contain a corresponding entry for executing said one of the blocks using said current value of the common operand.
Claim 5
Dependent Claim
48 words
The apparatus of claim 3, further comprising: means responsive to execution of said one of the blocks for creating a new entry in said table, said new entry recording the target address which was produced by said execution of said one of the blocks using said current value.
Claim 6
Dependent Claim
42 words
The apparatus of claim 2, further comprising: means for detecting the end of said block; and means responsive to said means for detecting for enabling said branch history table to redirect instruction fetching in place of said entries in said look-up table.
Claim 7
Dependent Claim
25 words
The apparatus of claim 1 further comprising means, responsive to said means for detecting, for inhibiting the processing means from using the branch history table.
Claim 8
Independent Claim
229 words
An apparatus for predicting outcomes of blocks of conditional branch instructions having a common operand, comprising: a look-up table including a plurality of entries, each of the entries having a first field for storing a starting address for a block of the conditional branch instructions, a second field for storing a previous value of the common operand for the block and a third field for storing a target address produced when the previous value was used to execute the block; a processor, coupled to the look-up table, the processor including: (a) a decoder, the decoder including instruction detection means for detecting an instruction indicative that one of the blocks is to be processed; (b) instruction execution means, coupled to the decoder, for determining the starting address of the one of the blocks and a current value of the common operand and for determining whether the look-up table contains a corresponding entry wherein the starting address of the one of the blocks matches data in the first field and the current value of the common operand matches the previous value of the common operand; (c) instruction fetch means, responsive to a determination that there is a corresponding entry, for prefetching an instruction at the target address stored in the third field of the corresponding entry prior to fetching of any of said conditional branches in the one of the blocks.
Claim 9
Independent Claim
229 words
An apparatus for predicting outcomes of blocks of conditional branch instructions having a common operand, comprising: a look-up table including a plurality of entries, each of the entries having a first field for storing a starting address for a block of the conditional branch instructions, a second field for storing a previous value of the common operand for the block and a third field for storing a target address produced when the previous value was used to execute the block; a processor, coupled to the look-up table, the processor including: (a) a decoder, the decoder including instruction detection means for detecting an instruction indicative that one of the blocks is to be processed; (b) instruction execution means, coupled to the decoder, for determining the starting address of the one of the blocks and a current value of the common operand and for determining whether the look-up table contains a corresponding entry wherein the starting address of the one of the blocks matches data in the first field and the current value of the common operand matches the previous value of the common operand; (c) instruction fetch means, responsive to a determination that there is a corresponding entry, for prefetching an instruction at the target address stored in the third field of the corresponding entry prior to fetching of any of said conditional branches in the one of the blocks.
References Cited (Backward Citations)
US3559183A
Cited
US4477872A
Cited
US4984154A
Cited
US4679141A
Cited
US4763245A
Cited
US4853840A
Cited
US4881170A
Cited
US4991080A
Cited
US4894772A
Cited
US5121473A
Cited
US5210831A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-07-25 | 1998-01-24 | 1998-07-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-07-25 | 2002-01-24 | 2002-07-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-07-25 | 2006-01-24 | 2006-07-26 | $7700.00 | Window Closed / Lapsed |