Patent US1671976A successfully refreshed from Google Patents.
Patent US6115809A successfully refreshed from Google Patents.
US6115809A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiling strong and weak branching behavior instruction blocks to separate caches for dynamic and static prediction
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1998-04-30
•
Granted: 2000-09-05
•
Expires: 2018-04-30
Abstract
Abstract A method and apparatus varies branch prediction strategy associated with branch instructions in a trace of program code. The present invention first profiles branch instructions within a trace to record branching behavior. Next, the present invention partitions branch instructions into groups of branch instructions that can be statically predicted and groups of branch instructions that can be dynamically predicted. Branch instructions that are profiled to have "strong" branching behavior (e.g., the same branch direction is taken 80% of the time) are placed in the group of branch instruction that are statically predicted. Branch instructions that are profiled to have "weak" branching behavior (e.g., the same branch direction is taken 60% of the time) are placed in the group of branch instruction that are dynamically predicted. Finally, branch instructions are adjusted by associating an indication of prediction strategy with each profiled branch instruction. In an embodiment of the present invention, dynamic and static code caches are defined in physical memory by allocating pools of memory pages that have prediction flags set to dynamic and static, respectively. In this embodiment, the trace is translated into the dynamic and static caches by moving branch instruction and basic blocks of code associated with branch instructions into the appropriate code cache based on the groups into which the branch instructions were partitioned. The present invention may be used when a program is originally compiled or when a program is recompiled after a profile-based optimization run. Additionally, the present invention may be used as part of a run-time optimization strategy.
Inventors
- 👤 James S. Mattson, Jr.
- 👤 Lacky V. Shah
- 👤 William B. Buzbee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:27
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
174 words
A method of varying branch prediction strategy within a trace of program code having branch instructions comprising: identifying branch instructions within the trace that have a branch direction that is taken more often than not; partitioning the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; associating a basic block of instructions with each identified branch instruction that has weak branching behavior, wherein each identified branch instruction that has weak branching behavior is a member of the basic block of instructions to which it is associated; translating basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache; associating a basic block of instructions with each identified branch instruction that has strong branching behavior, wherein each identified branch instruction that has strong branching behavior is a member of the basic block of instructions to which it is associated; translating basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache.
Claim 2
Independent Claim
174 words
A method of varying branch prediction strategy within a trace of program code having branch instructions comprising: identifying branch instructions within the trace that have a branch direction that is taken more often than not; partitioning the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; associating a basic block of instructions with each identified branch instruction that has weak branching behavior, wherein each identified branch instruction that has weak branching behavior is a member of the basic block of instructions to which it is associated; translating basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache; associating a basic block of instructions with each identified branch instruction that has strong branching behavior, wherein each identified branch instruction that has strong branching behavior is a member of the basic block of instructions to which it is associated; translating basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache.
Claim 3
Dependent Claim
47 words
The method of claim 1 wherein a prediction strategy flag indicating a static prediction strategy is associated with each memory page comprising the static code cache and a prediction strategy flag indicating a dynamic prediction strategy is associated with each memory page comprising the dynamic code cache.
Claim 4
Dependent Claim
26 words
The method of claim 1 wherein a prediction strategy flag indicating a static prediction strategy is associated with each memory page comprising the static code cache.
Claim 5
Dependent Claim
30 words
The method of claim 1 wherein associating a static prediction with each identified branch instruction that has strong branching behavior comprises: adjusting an operand order in a conditional branch instruction.
Claim 6
Dependent Claim
117 words
The method of claim 4 wherein adjusting an operand order in a conditional branch instruction comprises: encoding a backward branch to be predicted as taken and forward branch to be predicted as not taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is lower than the second register number of the condition branch instruction; and encoding a backward branch to be predicted as not taken and forward branch to be predicted as taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is higher than the second register number of the condition branch instruction.
Claim 7
Dependent Claim
26 words
The method of claim 1 wherein a prediction strategy flag indicating a dynamic prediction strategy is associated with each memory page comprising the dynamic code cache.
Claim 8
Dependent Claim
251 words
A program storage medium having computer readable program code thereon for causing branch prediction strategy to be varied within a trace of program code having branch instructions, the program storage medium comprising: a first segment of computer readable program code for identifying branch instructions within the trace that have a branch direction that is taken more often than not; a second segment of computer readable program code for partitioning the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; a third segment of computer readable program code for associating a basic block of instructions with each identified branch instruction that has weak branching behavior, wherein each identified branch instruction that has weak branching behavior is a member of the basic block of instructions to which it is associated, and translating basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache; a fourth segment of computer readable program code for associating a basic block of instructions with each identified branch instruction that has strong branching behavior, wherein each identified branch instruction that has strong branching behavior is a member of the basic block of instructions to which it is associated, and translating basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache; and a fifth segment of computer readable program code for associating a static prediction with each identified branch instruction that has strong branching behavior.
Claim 9
Dependent Claim
251 words
A program storage medium having computer readable program code thereon for causing branch prediction strategy to be varied within a trace of program code having branch instructions, the program storage medium comprising: a first segment of computer readable program code for identifying branch instructions within the trace that have a branch direction that is taken more often than not; a second segment of computer readable program code for partitioning the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; a third segment of computer readable program code for associating a basic block of instructions with each identified branch instruction that has weak branching behavior, wherein each identified branch instruction that has weak branching behavior is a member of the basic block of instructions to which it is associated, and translating basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache; a fourth segment of computer readable program code for associating a basic block of instructions with each identified branch instruction that has strong branching behavior, wherein each identified branch instruction that has strong branching behavior is a member of the basic block of instructions to which it is associated, and translating basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache; and a fifth segment of computer readable program code for associating a static prediction with each identified branch instruction that has strong branching behavior.
Claim 10
Dependent Claim
40 words
The program storage medium of claim 7 wherein the fifth segment of computer readable program code associates a static prediction with each identified branch instruction that has strong branching behavior by adjusting an operand order in a conditional branch instruction.
Claim 11
Dependent Claim
126 words
The program storage medium of claim 8 wherein the fifth segment of computer readable code adjusts an operand order in a conditional branch instruction by encoding a backward branch to be predicted as taken and forward branch to be predicted as not taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is lower than the second register number of the condition branch instruction, and encoding a backward branch to be predicted as not taken and forward branch to be predicted as taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is higher than the second register number of the condition branch instruction.
Claim 12
Independent Claim
273 words
An apparatus implemented in a computer system that varies branch prediction strategy within a trace of program code having branch instructions, the apparatus comprising: a profiler that identifies branch instructions within the trace that have a branch direction that is taken more often than not; a partitioner that partitions the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; and a translator that associates a dynamic prediction strategy with identified branch instructions that have weak branching behavior, associates a static prediction strategy with identified branch instructions that have strong branching behavior, and associates a static prediction with each identified branch instruction that has strong branching behavior, wherein the translator associates a static prediction strategy with identified branch instructions that have strong branching behavior by associating a basic block of instructions with each identified branch instruction that has strong branching behavior, with each identified branch instruction that has strong branching behavior being a member of the basic block of instructions to which it is associated, and translates basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache, and wherein the translator associates a dynamic prediction strategy with identified branch instructions that have weak branching behavior by associating a basic block of instructions with each identified branch instruction that has weak branching behavior, with each identified branch instruction that has weak branching behavior being a member of the basic block of instructions to which it is associated, and translates basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache.
Claim 13
Independent Claim
273 words
An apparatus implemented in a computer system that varies branch prediction strategy within a trace of program code having branch instructions, the apparatus comprising: a profiler that identifies branch instructions within the trace that have a branch direction that is taken more often than not; a partitioner that partitions the identified branch instructions into identified branch instructions that have strong branching behavior and identified branch instructions that have weak branching behavior; and a translator that associates a dynamic prediction strategy with identified branch instructions that have weak branching behavior, associates a static prediction strategy with identified branch instructions that have strong branching behavior, and associates a static prediction with each identified branch instruction that has strong branching behavior, wherein the translator associates a static prediction strategy with identified branch instructions that have strong branching behavior by associating a basic block of instructions with each identified branch instruction that has strong branching behavior, with each identified branch instruction that has strong branching behavior being a member of the basic block of instructions to which it is associated, and translates basic blocks of instructions that include branch instructions having strong branching behavior into a static code cache, and wherein the translator associates a dynamic prediction strategy with identified branch instructions that have weak branching behavior by associating a basic block of instructions with each identified branch instruction that has weak branching behavior, with each identified branch instruction that has weak branching behavior being a member of the basic block of instructions to which it is associated, and translates basic blocks of instructions that include branch instructions having weak branching behavior into a dynamic code cache.
Claim 14
Dependent Claim
47 words
The apparatus of claim 10 and further comprising: a prediction strategy flag indicating a static prediction strategy associated with each memory page comprising the static code cache; and a prediction strategy flag indicating a dynamic prediction strategy associated with each memory page comprising the dynamic code cache.
Claim 15
Dependent Claim
28 words
The apparatus of claim 10 and further comprising: a prediction strategy flag indicating a static prediction strategy is associated with each memory page comprising the static code cache.
Claim 16
Dependent Claim
32 words
The apparatus of claim 10 wherein the translator associates a static prediction with each identified branch instruction that has strong branching behavior by adjusting an operand order in a conditional branch instruction.
Claim 17
Dependent Claim
118 words
The apparatus of claim 13 wherein translator adjusts an operand order in a conditional branch instruction by encoding a backward branch to be predicted as taken and forward branch to be predicted as not taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is lower than the second register number of the condition branch instruction, and encoding a backward branch to be predicted as not taken and forward branch to be predicted as taken by adjusting the operand in the conditional branch instruction such that a first register number of the conditional branch instruction is higher than the second register number of the condition branch instruction.
Claim 18
Dependent Claim
27 words
The apparatus of claim 10 and further comprising: a prediction strategy flag indicating a dynamic prediction strategy associated with each memory page comprising the dynamic code cache.
References Cited (Backward Citations)
US5687360A
Cited
US5659752A
Cited
US5752014A
Cited
US5933628A
Cited
US5857104A
Cited
US5805878A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-05 | 2004-03-06 | 2004-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-05 | 2008-03-06 | 2008-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-05 | 2012-03-06 | 2012-09-05 | $7700.00 | Window Closed / Lapsed |