US5226130A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for store-into-instruction-stream detection and maintaining branch prediction cache consistency
Assignee: Nexgen Inc
•
Filing: 1990-02-26
•
Granted: 1993-07-06
•
Expires: 2010-02-26
Abstract
Abstract The present invention provides for the updating of both the instructions in a branch prediction cache and instructions recently provided to an instruction pipeline from the cache when an instruction being executed attempts to change such instructions ("Store-Into-Instruction-Stream"). The branch prediction cache (BPC) includes a tag identifying the address of instructions causing a branch, a record of the target address which was branched to on the last occurrence of each branch instruction, and a copy of the first several instructions beginning at this target address. A separate instruction cache is provided for normal execution of instructions, and all of the instructions written into the branch prediction cache from the system bus must also be stored in the instruction cache. The instruction cache monitors the system bus for attempts to write to the address of an instruction contained in the instruction cache. Upon such a detection, that entry in the instruction cache is invalidated, and the corresponding entry in the branch prediction cache is invalidated. A subsequent attempt to use an instruction in the branch prediction cache which has been invalidated will detect that it is not valid, and will instead go to main memory to fetch the instruction, where it has been modified.
Inventors
- 👤 John G. Favor
- 👤 Korbin Van Dyke
- 👤 David R. Stiles
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 19:17
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3812; G06F9/3804; G06F9/3836; G06F9/3842; G06F9/3844; G06F9/3861; G06F9/3863
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
245 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch entry address, a branch target address, branch target instruction data and a validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein said instruction cache is direct-mapped and said branch prediction cache is fully associative; and wherein index bits of an instruction address are used to map into said instruction cache, and bits more significant than said index bits are not compared to said branch target addresses.
Claim 2
Independent Claim
245 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch entry address, a branch target address, branch target instruction data and a validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein said instruction cache is direct-mapped and said branch prediction cache is fully associative; and wherein index bits of an instruction address are used to map into said instruction cache, and bits more significant than said index bits are not compared to said branch target addresses.
Claim 3
Independent Claim
276 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch instruction address, a branch target address, branch target instruction data and validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein each line of said branch prediction cache includes a plurality of branch target instructions immediately following said branch instruction to form a set of instruction bytes, said set of instruction bytes being aligned differently than a line of said instruction cache, and further comprising means for storing at least a portion of an end address of said set and comparing said portion of said end address to a portion of an address of an instruction cache entry.
Claim 4
Independent Claim
276 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch instruction address, a branch target address, branch target instruction data and validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein each line of said branch prediction cache includes a plurality of branch target instructions immediately following said branch instruction to form a set of instruction bytes, said set of instruction bytes being aligned differently than a line of said instruction cache, and further comprising means for storing at least a portion of an end address of said set and comparing said portion of said end address to a portion of an address of an instruction cache entry.
Claim 5
Dependent Claim
63 words
The apparatus of claim 2 further comprising control means for ensuring that all the addresses of said set of instructions are within the same page of memory, such that said second means for comparing said portion of said end address to a portion of an address of an instruction cache entry being operable without comparing bits more significantly than a page boundary bit.
Claim 6
Independent Claim
217 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch instruction address, a branch target address, branch target instruction data and a validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein said means for comparing does not compare bits more significant than index bits of said instruction cache.
Claim 7
Independent Claim
217 words
An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including validity bits for indicating whether an entry is valid and means for setting a validity bit for an entry to an invalid state upon detection of a store signal on said system bus for an address matching said entry; a branch prediction cache including, for each entry, a branch instruction address, a branch target address, branch target instruction data and a validity bit; means for comparing an address of an instruction cache entry to said branch target addresses; control means for writing instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting a validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with a validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction queue; wherein said means for comparing does not compare bits more significant than index bits of said instruction cache.
References Cited (Backward Citations)
US4295193A
Cited
US4442488A
Cited
US4594659A
Cited
US4777594A
Cited
US4802113A
Cited
US4827402A
Cited
US4679141A
Cited
US4777587A
Cited
US4775955A
Cited
US4853840A
Cited
US4722050A
Cited
US4796175A
Cited
US4847753A
Cited
US4933837A
Cited
US4860199A
Cited
US4894772A
Cited
US4942520A
Cited
US4991078A
Cited
US4882673A
Cited
US4943908A
Cited
US4926323A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-05 | 1997-01-04 | 1997-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-05 | 2001-01-04 | 2001-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-05 | 2005-01-04 | 2005-07-06 | $7700.00 | Window Closed / Lapsed |