Synthetic dynamic branch prediction

• US 5,857,104 A
• Filed: 11/26/1996
• Issued: 01/05/1999
• Est. Priority Date: 11/26/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Natarjan, Balas K., Mahlke, Scott A.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Dam, Tuan Q.
• Application Number:
  US08/757,038
• Time in Patent Office: 770 Days
• Field of Search: 395/704-706, 395/709, 395/183.11, 395/183.14, 395/586, 395/587, 395/581
• US Class Current: 717/158
• CPC Class Codes: G06F 8/4451 Avoiding pipeline stalls
• CPC Class Codes: G06F 8/447 Target code generation
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/30094 Condition code generation, e.g. Carry, Zero flag
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3846 using static prediction, e.g. branch taken strategy

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.

Claims

1. 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.

2. 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.

3. The compiler of claim 2, wherein the branch predictor function correlates at least one register content with the branch direction of the branch instruction.

4. 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.

5. 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.

6. The compiler of claim 1, wherein the prediction instruction, when inserted, is one to sixty-four cycles prior to the branch instruction.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. The apparatus of claim 12, wherein the prediction instruction, when inserted, is one to sixty-four cycles prior to the branch instruction.

18. 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.

19. 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.