Prioritized pre-fetch/preload mechanism for loading and speculative preloading of candidate branch target instruction

• US 6,374,348 B1
• Filed: 10/17/2000
• Issued: 04/16/2002
• Est. Priority Date: 10/01/1999
• Status: Expired due to Term

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Hitachi, Ltd.
• Inventors: Irie, Naohiko, Werner, Tony Lee
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/690,340
• Time in Patent Office: 546 Days
• Field of Search: 712/237, 712/238, 712/239
• US Class Current: 712/237
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/322 for non-sequential address
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3846 using static prediction, e.g. branch taken strategy
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

An improved preload/prefetching architecture is disclosed for controlling branch target instruction loading in a pipelined processor. Branch target instructions can be speculatively preloaded/prefetched based on a first prediction indicator provided in a branch control instruction, and they also can be actually loaded/fetched based on a second prediction indicator provided in a branch instruction. This mechanism results in reduced cache latency during program execution. The preloading/prefetching of branch target instructions can also be prioritized under software control to optimize instruction execution, based on particular indicators specified for branch target instructions within a branch hint buffer.

Claims

1. A circuit for controlling loading of instructions from an instruction cache to a pipeline in a computing system, said circuit including:

branch control means for initiating a speculative preloading operation and/or an actual loading operation of a branch target instruction based on a branch prediction indicator;

monitoring means coupled to the branch control means for determining whether branch target instructions available for loading in the pipeline are invalid;

selecting means coupled to said branch control means and said monitoring means for selecting a replacement branch target instruction when an invalid branch target instruction is found, said replacement branch instruction being selected by ranking a number of potential branch target addresses when a speculative preloading operation is initiated;

loading means coupled to said branch control means, said monitoring means and said selecting means for (i) replacing said invalid branch target instruction with said replacement branch target instruction by causing said instruction cache to load said replacement branch target instruction for execution in the pipeline in response to initiation of said speculative preloading operation, and/or (ii) causing said instruction cache to load said branch target instruction for execution in the pipeline in response to initiation of said actual loading operation.

2. The circuit of claim 1, wherein said monitoring means includes an N bit register loaded in accordance with a validity status of N separate branch target instructions stored in an N entry branch target instruction buffer, such that each bit of N bit register identifies whether the corresponding entry in the branch target instruction buffer is valid or invalid.

3. The circuit of claim 1, wherein said loading means loads said replacement branch target instruction into an N entry branch target instruction buffer, where N>

8.

4. The circuit of claim 1, wherein said selecting means includes a pre-load register, and which pre-load register includes a bit identifying whether which if any storage locations holding said potential branch target addresses can be used for loading a replacement branch target instruction.

5. The circuit of claim 4, wherein said selecting means includes a branch instruction hint register, which hint register includes a bit identifying whether a branch target instruction is likely to be needed.

6. The circuit of claim 1, wherein said ranking is performed by examining a storage location identification for each potential branch target address, such that branch target addresses can be prioritized in accordance with which storage location they are associated with.

7. The circuit of claim 1, wherein the loading means suspends loading of said replacement branch target instruction if a cache access demand is pending.

8. The circuit of claim 1, wherein the loading means suspends loading of said replacement branch target instruction if an instruction buffer in the pipeline is below a predetermined instruction level threshold.

9. The circuit of claim 1, wherein said replacement branch target instruction is speculatively loaded during said speculative loading operation based on said prediction indicator being associated with a branch control instruction prior to a first execution of a branch instruction requiring said branch target instruction.

10. The circuit of claim 1, wherein said loading means generates a cache access demand when a branch instruction is actually decoded within the pipeline, and a prediction indicator for said branch instruction indicates that a program branch is to be taken.

11. The circuit of claim 1, further including a target address buffer coupled to said loading means, said target address buffer being loaded with incremented target addresses corresponding to addresses for instructions following said replacement target instruction, so that said incremented target addresses can be used for cache accesses if said replacement target instruction is actually executed later by the pipeline.

12. A method for controlling loading of instructions from an instruction cache to a pipeline in a computing system, the method including:

(a) initiating a speculative preloading operation and/or an actual loading operation of a branch target instruction based on a branch prediction indicator; and

(b) determining whether branch target instructions available for loading in the pipeline are valid; and

(c) selecting a replacement branch target instruction when an invalid branch target instruction is found, said replacement branch instruction being selected by ranking a number of potential branch target addresses when a speculative preloading operation is initiated; and

(d) during a speculative loading operation, replacing said invalid branch target instruction with said replacement branch target instruction by causing said instruction cache to load said replacement branch target instruction for execution in the pipeline; and

(e) during an actual loading operation, causing said instruction cache to load said branch target instruction for execution in the pipeline.

13. The method of claim 12, wherein during step (b), a validity status of N separate branch target instructions stored in an N entry branch target instruction buffer are examined.

14. The method of claim 12, wherein said replacement branch target instruction is loaded into an N entry branch target instruction buffer, where N>

8.

15. The method of claim 12, wherein said ranking is performed by examining a storage location identification for each potential branch target address, such that branch target addresses can be prioritized in accordance with which storage location they are associated with.

16. The method of claim 12 wherein loading of said replacement branch target instruction is suspended if a cache access demand is pending.

17. The method of claim 12, wherein loading of said replacement branch target instruction is suspended if an instruction buffer in the pipeline is below a predetermined instruction level threshold.

18. The method of claim 12, wherein said replacement branch target instruction is speculatively loaded during said speculative loading operation based on said prediction indicator being associated with a branch control instruction prior to a first execution of a branch instruction requiring said branch target instruction.

19. The method of claim 12, wherein a cache access demand is generated when a branch instruction is actually decoded within the pipeline, and when a prediction indicator for said branch instruction indicates that a program branch is to be taken.

20. The method of claim 12, further including a step (f):

providing a target address buffer coupled to said loading means, said target address buffer being loaded with incremented target addresses corresponding to addresses for instructions following said replacement target instruction, so that said incremented target addresses can be used for cache accesses if said replacement target instruction is actually executed later by the pipeline.