Granted Patent B2

US 7,096,348 · App. 10/736,393 · Granted Aug 22, 2006

Abstract

Claims (42)

1. A method for allocating entries in a branch target buffer (BTB) in a pipelined data processing system, comprising:

fetching instructions from a plurality of instructions;

determining that one of the plurality of instructions is a branch instruction;

decoding the branch instruction to determine a branch target address;

determining that the branch instruction was not loaded into a predetermined slot of a prefetch buffer and no other stall condition will occur;

selectively allocating a BTB entry based on the determination; and

loading a branch target address corresponding to the branch instruction into a predetermined entry of the BTB.

2. The method of claim 1 wherein determining if the branch target address location can be obtained further comprises examining a predetermined slot of a prefetch buffer having a plurality of slots to identify the branch instruction.

3. The method of claim 2 further comprising loading a branch target address corresponding to the branch instruction into a predetermined entry of the BTB.

4. The method of claim 2 wherein the predetermined slot of the prefetch buffer is characterized as being a first slot.

5. The method of claim 1 further comprising:

determining that a stall condition exists in the data processing system;

determining that a BTB entry will not be allocated because of the stall condition; and

waiting for the branch instruction to be fetched from a memory location.

6. The method of claim 1 further comprising using a first-in, first-out replacement algorithm to load the BTB.

7. A method for allocating entries in a branch target buffer (BTB) in a pipelined data processing system, comprising:

fetching instructions from a plurality of instructions;

determining that one of the plurality of instructions is a branch instruction;

decoding the branch instruction to determine a branch target address;

determining that the branch instruction was not loaded into a predetermined slot of a prefetch buffer and no other stall condition will occur; and

selectively allocating a BTB entry based on the determination.

8. The method of claim 7 further comprising loading a branch target address corresponding to the branch instruction into a predetermined entry of the BTB.

9. The method of claim 7 wherein the predetermined slot of the prefetch buffer is characterized as being a first slot.

10. The method of claim 7 wherein determining further comprises:

examining a predetermined slot of a prefetch buffer having a plurality of slots to identify the branch instruction; and

calculating the branch target address using a program counter value and a displacement field value of the branch instruction.

11. The method of claim 10 further comprising using the branch target address in the BTB entry to prefetch a target instruction.

12. The method of claim 7 further comprising using a first-in, first-out replacement algorithm to load the BTB.

13. A data processing system comprising:

a prefetch buffer having a plurality of slots for storing instructions;

a branch target buffer (BTB) having a plurality of entries;

a control logic unit coupled to the prefetch buffer and to the BTB, wherein the control logic unit causes an entry of the plurality of entries of the BTB to be allocated to receive a branch target address of a branch instruction if the branch instruction is not detected in a predetermined slot of the plurality of slots of the prefetch buffer.

14. The data processing system of claim 13 , wherein the predetermined slot of the plurality of slots is characterized as being a first slot having an output coupled to an input of an instruction register.

15. The data processing system of claim 13 , wherein a first-in, first-out replacement algorithm is used to load the BTB.

16. The data processing system of claim 13 , further comprising a multiplexer having a plurality of inputs, an input of the plurality of inputs coupled to one of the plurality of entries of the BTB, and an output for providing a selected one of plurality of entries in response to a control signal.

17. The data processing system of claim 16 , further comprising a comparator having a first input for receiving an address, a second input coupled to each of the plurality of entries of the BTB, and an output for providing the control signal to the multiplexer.

18. The data processing system of claim 13 , further comprising:

a program counter; and

a branch address calculator for calculating a branch target address of the branch instruction using a value from the program counter and a displacement field of the branch instruction.

19. The data processing system of claim 13 , wherein the data processing system is a pipelined data processing system implemented on a single integrated circuit.

20. The data processing system of claim 13 , wherein each entry of the plurality of entries of the BTB includes a first bit field for storing an address value related to the address of the branch instruction and a second bit field for storing a branch target address.

21. The data processing system of claim 13 , wherein the predetermined slot of the plurality of slots is characterized as being a second slot having an output coupled to a first slot characterized as not being coupled to an input of an instruction register.

Assignments (19)