US5721893A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Exploiting untagged branch prediction cache by relocating branches
Assignee: HTC Corp
•
Filing: 1996-05-14
•
Granted: 1998-02-24
•
Expires: 2016-05-14
Abstract
Abstract An untagged branch prediction cache is exploited by relocating branches during a final pass in the compilation process, after all other optimizations have been applied, where a pass is made over the instructions in each subprogram, and all branches that use the branch prediction cache (BPC) are placed into buckets, where each bucket corresponds to a position in the BPC. Recorded with each branch is its expected direction (taken, not taken), based either on profiling data or on static heuristics. Each bucket is then inspected. For buckets containing branches whose predicted directions conflict, an attempt is made to move some of those branches to another bucket. If other branches' positions are affected, the bucket inspection process is restarted, after recalculation of the bucket positions of all BPC branches. Branches that have matching predicted directions, but that currently fall into separate buckets, may be moved into the same bucket, so that the histories of branches can reinforce one another. Heuristics may be used to dictate which branches are considered, what code transformations are used to relocate branches, and whether both conflict avoidance and match enhancement are performed.
Inventors
- 👤 Anne M. Holler
- 👤 Lacky V. Shah
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 09:35
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F8/443
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
157 words
A method for exploiting an untagged branch prediction cache, comprising the steps of: passing over a subprogram's instructions during a final optimization pass as part of a compilation process, after all other optimizations of said compilation process have been applied; placing all branch instructions that use a branch prediction cache (BPC) into buckets, where each bucket corresponds to a position in said BPC; recording in said buckets with each branch instruction an expected direction (taken, not taken), based either on either of profiling data or static heuristics; inspecting each bucket; and for buckets containing branch instructions whose predicted directions conflict, moving one or more of said conflicting branch instructions to another bucket if said move reduces or eliminates said conflict at said bucket without creating or exacerbating another conflict at said other bucket, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 2
Independent Claim
157 words
A method for exploiting an untagged branch prediction cache, comprising the steps of: passing over a subprogram's instructions during a final optimization pass as part of a compilation process, after all other optimizations of said compilation process have been applied; placing all branch instructions that use a branch prediction cache (BPC) into buckets, where each bucket corresponds to a position in said BPC; recording in said buckets with each branch instruction an expected direction (taken, not taken), based either on either of profiling data or static heuristics; inspecting each bucket; and for buckets containing branch instructions whose predicted directions conflict, moving one or more of said conflicting branch instructions to another bucket if said move reduces or eliminates said conflict at said bucket without creating or exacerbating another conflict at said other bucket, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 3
Dependent Claim
25 words
The method of claim 1, further comprising the steps of: recalculating the bucket positions of all BPC branch instructions; and restarting said bucket inspection process.
Claim 4
Dependent Claim
37 words
The method of claim 1, further comprising the steps of: moving branch instructions that have matching predicted directions, but that currently fall into separate buckets, into the same bucket, wherein said branch instruction histories reinforce one another.
Claim 5
Independent Claim
165 words
An apparatus for exploiting an untagged branch prediction cache, comprising: a compiler for passing over a subprogram's instructions during a final optimization pass as part of a compilation process, after all other optimizations of said compilation process have been applied; said compiler placing all branch instructions that use a branch prediction cache (BPC) into buckets, where each bucket corresponds to a position in said BPC; said compiler recording in said buckets with each branch instruction an expected direction (taken, not taken), based either on either of profiling data or static heuristics; said compiler inspecting each bucket; and for buckets containing branch instructions whose predicted directions conflict, said compiler moving one or more of said conflicting branch instructions to another bucket if said move reduces or eliminates said conflict at said bucket without creating or exacerbating another conflict at said other bucket, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 6
Independent Claim
165 words
An apparatus for exploiting an untagged branch prediction cache, comprising: a compiler for passing over a subprogram's instructions during a final optimization pass as part of a compilation process, after all other optimizations of said compilation process have been applied; said compiler placing all branch instructions that use a branch prediction cache (BPC) into buckets, where each bucket corresponds to a position in said BPC; said compiler recording in said buckets with each branch instruction an expected direction (taken, not taken), based either on either of profiling data or static heuristics; said compiler inspecting each bucket; and for buckets containing branch instructions whose predicted directions conflict, said compiler moving one or more of said conflicting branch instructions to another bucket if said move reduces or eliminates said conflict at said bucket without creating or exacerbating another conflict at said other bucket, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 7
Dependent Claim
26 words
The apparatus of claim 4, further comprising: means for recalculating the bucket positions of all BPC branch instructions; and means for restarting said bucket inspection process.
Claim 8
Dependent Claim
34 words
The apparatus of claim 4, wherein branch instructions that have matching predicted directions, but that currently fall into separate buckets, are moved into the same bucket, wherein said branch instruction histories reinforce one another.
Claim 9
Dependent Claim
13 words
The apparatus of claim 4, said compiler further comprising a low level optimizer.
Claim 10
Independent Claim
134 words
A method for exploiting untagged branch prediction cache by relocating branches, said method, for each procedure in a program, comprising the steps of: compiling and optimizing said procedure code; numbering each instruction in said procedure; creating an array of buckets; putting an instruction in a bucket for said instruction's number modulo branch prediction cache size for each branch instruction in said procedure that is to be predicted; noting a direction (taken, not taken) said branch instruction is expected to go; and for each bucket, attempting to move conflicting branch instructions to a next bucket if said bucket contains more than one branch instruction and if said branch instruction directions conflict, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 11
Independent Claim
134 words
A method for exploiting untagged branch prediction cache by relocating branches, said method, for each procedure in a program, comprising the steps of: compiling and optimizing said procedure code; numbering each instruction in said procedure; creating an array of buckets; putting an instruction in a bucket for said instruction's number modulo branch prediction cache size for each branch instruction in said procedure that is to be predicted; noting a direction (taken, not taken) said branch instruction is expected to go; and for each bucket, attempting to move conflicting branch instructions to a next bucket if said bucket contains more than one branch instruction and if said branch instruction directions conflict, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 12
Dependent Claim
18 words
The method of claim 8, wherein said bucket array length is equal to a branch prediction cache size.
Claim 13
Dependent Claim
20 words
The method of claim 8, further comprising the step of: noting which direction a branch instruction is expected to go.
Claim 14
Dependent Claim
20 words
The method of claim 10, wherein backward branches tend to be taken and forward branches tend not to be taken.
Claim 15
Dependent Claim
18 words
The method of claim 8, further comprising the step of: using two branches' history to reinforce each other.
Claim 16
Dependent Claim
26 words
The method of claim 8, further comprising the step of: adding up an amount of conflict to determine if it is possible to reduce the conflict.
Claim 17
Dependent Claim
30 words
The method of claim 13, further comprising the step of: moving an instruction down to a next bucket to reduces conflict in said next bucket by reinforcing a direction preference.
Claim 18
Dependent Claim
27 words
The method of claim 8, further comprising the step of: providing a system hardware branch prediction cache that is a same size as said array of buckets.
Claim 19
Dependent Claim
34 words
The method of claim 15, wherein said branch prediction cache remembers a plurality of recent historical events with respect to a particular address, such that said branch prediction cache adapts as branch history changes.
Claim 20
Independent Claim
144 words
An apparatus for exploiting untagged branch prediction cache by relocating branches, said apparatus, for each procedure in a program, comprising: a compiler for compiling and optimizing said procedure code; said compiler numbering each instruction in said procedure; said compiler creating an array of buckets; said compiler putting an instruction in a bucket for said instruction's number modulo branch prediction cache size for each branch instruction in said procedure that is to be predicted; said compiler noting a direction (taken, not taken) said branch instruction is expected to go; and for each bucket, said compiler attempting to move conflicting branch instructions to a next bucket if said bucket contains more than one branch instruction and if said branch instruction directions conflict, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 21
Independent Claim
144 words
An apparatus for exploiting untagged branch prediction cache by relocating branches, said apparatus, for each procedure in a program, comprising: a compiler for compiling and optimizing said procedure code; said compiler numbering each instruction in said procedure; said compiler creating an array of buckets; said compiler putting an instruction in a bucket for said instruction's number modulo branch prediction cache size for each branch instruction in said procedure that is to be predicted; said compiler noting a direction (taken, not taken) said branch instruction is expected to go; and for each bucket, said compiler attempting to move conflicting branch instructions to a next bucket if said bucket contains more than one branch instruction and if said branch instruction directions conflict, wherein moving said one or more conflicting branch instructions to another bucket changes a respective instruction position in a corresponding object code instruction stream.
Claim 22
Dependent Claim
18 words
The apparatus of claim 17, wherein said bucket array length is equal to a branch prediction cache size.
Claim 23
Dependent Claim
17 words
The apparatus of claim 17, said compiler noting which direction a branch instruction is expected to go.
Claim 24
Dependent Claim
20 words
The apparatus of claim 19, wherein backward branches tend to be taken and forward branches tend not to be taken.
Claim 25
Dependent Claim
15 words
The apparatus of claim 17, said compiler using two branches' history to reinforce each other.
Claim 26
Dependent Claim
23 words
The apparatus of claim 17, said compiler adding up an amount of conflict to determine if it is possible to reduce the conflict.
Claim 27
Dependent Claim
27 words
The apparatus of claim 22, said compiler moving an instruction down to a next bucket to reduces conflict in said next bucket by reinforcing a direction preference.
Claim 28
Dependent Claim
23 words
The apparatus of claim 17, further comprising: a system hardware branch prediction cache that is a same size as said array of buckets.
Claim 29
Dependent Claim
34 words
The apparatus of claim 24, wherein said branch prediction cache remembers a plurality of recent historical events with respect to a particular address, such that said branch prediction cache adapts as branch history changes.
References Cited (Backward Citations)
US5450588A
Cited
US5568623A
Cited
US5530964A
Cited
US5511198A
Cited
US5596732A
Cited
US5655122A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-23 | 2001-08-25 | 2002-02-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-23 | 2005-08-25 | 2006-02-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-23 | 2009-08-25 | 2010-02-24 | $7700.00 | Window Closed / Lapsed |