US5857104A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Synthetic dynamic branch prediction
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-11-26
•
Granted: 1999-01-05
•
Expires: 2016-11-26
Abstract
Abstract A compiler includes a branch statistics data analyzer to analyze branch statistics data of a branch instruction to construct a branch predictor function for the branch instruction. A branch prediction instruction generator is coupled to the branch statistics data analyzer to generate at least one prediction instruction to implement the branch predictor function. A main compiling engine is coupled to the branch prediction instruction generator to insert the prediction instruction before the branch instruction. A method of dynamically predicting a branch instruction of a program is also described.
Inventors
- 👤 Balas K. Natarjan
- 👤 Scott A. Mahlke
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:40
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/30094; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F8/4451; G06F8/447; G06F9/30003; G06F9/3005; G06F9/30058; G06F9/32; G06F9/322; G06F9/323; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3844; G06F9/3846
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
88 words
A compiler, comprising: (A) a branch statistics data analyzer that analyzes branch statistics data of a branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (B) a branch prediction instruction generator coupled to the branch statistics data analyzer to generate at least one prediction instruction to implement the branch predictor function; (C) a main compiling engine coupled to the branch prediction instruction generator to insert the prediction instruction before the branch instruction.
Claim 2
Dependent Claim
88 words
A compiler, comprising: (A) a branch statistics data analyzer that analyzes branch statistics data of a branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (B) a branch prediction instruction generator coupled to the branch statistics data analyzer to generate at least one prediction instruction to implement the branch predictor function; (C) a main compiling engine coupled to the branch prediction instruction generator to insert the prediction instruction before the branch instruction.
Claim 3
Dependent Claim
36 words
The compiler of claim 1, wherein the branch statistics data analyzer constructs the branch predictor function by analyzing the branch profile information and the register dump information to identify correlations between branch directions and register contents.
Claim 4
Dependent Claim
24 words
The compiler of claim 2, wherein the branch predictor function correlates at least one register content with the branch direction of the branch instruction.
Claim 5
Dependent Claim
44 words
The compiler of claim 3, wherein the branch prediction instruction generator generates a prepare-to-branch instruction that specifies the branch target address of the branch instruction and a compare instruction that compares the register content with a threshold value specified by the branch predictor function.
Claim 6
Dependent Claim
79 words
The compiler of claim 1, wherein the main compiling engine is also coupled to the branch statistics data analyzer to determine if the branch statistics data is available in the branch statistics data analyzer before compiling the branch instruction, wherein when the main compiling engine determines that the branch statistics data is not available to the branch statistics data analyzer, the main compiler engine does not insert any instruction when compiling the source code that contains the branch instruction.
Claim 7
Dependent Claim
21 words
The compiler of claim 1, wherein the prediction instruction, when inserted, is one to sixty-four cycles prior to the branch instruction.
Claim 8
Independent Claim
69 words
A method of dynamically predicting a branch instruction of a program, comprising the steps of: analyzing branch statistics data of the branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (B) generating at least one prediction instruction to implement the branch predictor function; (C) a inserting the prediction instruction before the branch instruction.
Claim 9
Independent Claim
69 words
A method of dynamically predicting a branch instruction of a program, comprising the steps of: analyzing branch statistics data of the branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (B) generating at least one prediction instruction to implement the branch predictor function; (C) a inserting the prediction instruction before the branch instruction.
Claim 10
Dependent Claim
55 words
The method of claim 7, wherein the step of analyzing further comprises the steps of: (i) analyzing the branch profile information and the register dump information of the branch instruction to identify correlations between branch directions and register contents; (ii) generating the branch predictor function based on the correlations between branch directions and register contents.
Claim 11
Dependent Claim
68 words
The method of claim 8, wherein the step (i) further comprises the steps of: (a) determining the content of each register some time prior to each execution of the branch instruction; (b) determining the branch direction for each execution of the branch instruction; (c) establishing the correlations between the branch directions and the register contents by determining at what content value of which register, the branch instruction branches.
Claim 12
Dependent Claim
40 words
The method of claim 7, wherein the step of generating generates a compare instruction that implements the branch predictor function and a prepare-to-branch instruction that specifies the branch target address of the branch instruction upon receiving the branch predictor function.
Claim 13
Dependent Claim
61 words
The method of claim 7, further comprising the steps of: (D) determining if the branch statistics data is available in the branch statistics data analyzer prior to the step (C); (E) if the branch statistics data is not available to the branch statistics data analyzer, then not performing the step (C) when compiling the source code that contains the branch instruction.
Claim 14
Independent Claim
119 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable compiler program stored in the storage medium that dynamically predicts a branch instruction of a program, the computer executable compiler program further comprising (a) a first set of instructions that analyze branch statistics data of the branch instruction to obtain a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (b) a second set of instructions that generate at least one prediction instruction to implement the branch predictor function; (c) a third set of instructions that insert the prediction instruction before the branch instruction when compiling a source code containing the branch instruction into a machine code.
Claim 15
Independent Claim
119 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable compiler program stored in the storage medium that dynamically predicts a branch instruction of a program, the computer executable compiler program further comprising (a) a first set of instructions that analyze branch statistics data of the branch instruction to obtain a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information; (b) a second set of instructions that generate at least one prediction instruction to implement the branch predictor function; (c) a third set of instructions that insert the prediction instruction before the branch instruction when compiling a source code containing the branch instruction into a machine code.
Claim 16
Dependent Claim
65 words
The apparatus of claim 12, wherein the first set of instructions further comprises: (i) a first subset of instructions that analyze the branch profile information and the register dump information of the branch instruction to identify correlations between branch directions and register contents; (ii) a second subset of instructions that generate the branch predictor function based on the correlations between branch directions and register contents.
Claim 17
Dependent Claim
80 words
The apparatus of claim 13, wherein the first subset of instructions analyzes the branch profile information and the register dump information of the branch instruction by (a) determining the content of each register some time prior to each execution of the branch instruction; (b) determining the branch direction for each execution of the branch instruction; (c) establishing the correlations between the branch directions and the register contents by determining at what content value of which register, the branch instruction branches.
Claim 18
Dependent Claim
67 words
The apparatus of claim 12, further comprising: (D) a fourth set of instructions that determine if the branch statistics data is available in the branch statistics data analyzer prior to compilation of the source code that contains the branch instruction; (E) a fifth set of instructions that cause the third set of instructions not to insert the prediction instruction if the branch statistics data is not available.
Claim 19
Dependent Claim
41 words
The apparatus of claim 12, wherein the second set of instructions generates a compare instruction that implements the branch predictor function and a prepare-to-branch instruction that specifies the branch target address of the branch instruction upon receiving the branch predictor function.
Claim 20
Dependent Claim
21 words
The apparatus of claim 12, wherein the prediction instruction, when inserted, is one to sixty-four cycles prior to the branch instruction.
Claim 21
Dependent Claim
122 words
A runtime branch prediction synthesizer, comprising: (A) a branch statistics data analyzer that analyzes branch statistics data of a branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information, wherein the branch statistics data analyzer constructs the branch predictor function by analyzing the branch profile information and the register dump information to identify correlations between branch directions and register contents; (B) a branch prediction instruction generator coupled to the branch statistics data analyzer to generate at least one prediction instruction to implement the branch predictor function; (C) a runtime code manager coupled to the branch prediction instruction generator to insert the prediction instruction before the branch instruction.
Claim 22
Dependent Claim
122 words
A runtime branch prediction synthesizer, comprising: (A) a branch statistics data analyzer that analyzes branch statistics data of a branch instruction to construct a branch predictor function for the branch instruction, wherein the branch statistics data includes branch profile information and register dump information, wherein the branch statistics data analyzer constructs the branch predictor function by analyzing the branch profile information and the register dump information to identify correlations between branch directions and register contents; (B) a branch prediction instruction generator coupled to the branch statistics data analyzer to generate at least one prediction instruction to implement the branch predictor function; (C) a runtime code manager coupled to the branch prediction instruction generator to insert the prediction instruction before the branch instruction.
Claim 23
Dependent Claim
66 words
The runtime branch prediction synthesizer of claim 18, wherein the branch predictor function correlates at least one register content with the branch direction of the branch instruction, wherein the branch prediction instruction generator generates a prepare-to-branch instruction that specifies the branch target address of the branch instruction and a compare instruction that compares the register content with a threshold value specified by the branch predictor function.
References Cited (Backward Citations)
US5293631A
Cited
US5367703A
Cited
US5596732A
Cited
US5655122A
Cited
US5687360A
Cited
US5659752A
Cited
US5721893A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-04 | 2002-07-06 | 2003-01-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-04 | 2006-07-06 | 2007-01-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-04 | 2010-07-06 | 2011-01-05 | $7700.00 | Window Closed / Lapsed |