# US 2003/0204705 A1 · Prediction of branch instructions in a data processing apparatus

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0204705 A1
- Document ID: US20030204705A1
- Status: Published application
- Kind: A1
- Application number: 10/134,649
- Filed: 2002-04-30
- Published: 2003-10-30
- Earliest claimed: 2002-04-30
- Inventors: William H. Oldfield; Alexander E. Nancekievill
- Web page: https://patentgrep.com/patent/US20030204705A1

## CPC

- G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables}
- G06F 9/30054: {Unconditional branch instructions}
- G06F 9/30145: {Instruction analysis, e.g. decoding, instruction word fields}
- G06F 9/30167: {of immediate specifier, e.g. constants}
- G06F 9/322: {for non-sequential address}
- G06F 9/323: {for indirect branch instructions}
- G06F 9/324: {using program counter relative addressing}
- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention provides a data processing apparatus and method for predicting branch instructions in a data processing apparatus. The data processing apparatus comprises a processor for executing instructions, a prefetch unit for prefetching instructions from a memory prior to sending those instructions to the processor for execution, and branch prediction logic for predicting which instruction should be prefetched by the prefetch unit. The branch prediction logic is arranged to predict whether a prefetched instruction specifies a branch operation that will cause a change in instruction flow, and if so to indicate to the prefetch unit a target address within the memory from which a next instruction should be retrieved. The instructions include a first instruction and a second instruction that are executable independently by the processor, but which in combination specify a predetermined branch operation whose target address is uniquely derivable from a combination of attributes of the first and second instruction. The data processing apparatus further comprises target address logic for deriving from the combination of attributes the target address for the predetermined branch operation, the branch prediction logic being arranged to predict whether the predetermined branch operation will cause a change in instruction flow, in which event the branch prediction logic is arranged to indicate to the prefetch unit the target address determined by the target address logic. Accordingly, even though neither the first instruction nor the second instruction itself uniquely identifies the target address, the target address can nonetheless be uniquely determined thereby allowing prediction of the predetermined branch operation specified by the combination of the first and second instructions.

## Claims

### Claim 1

A data processing apparatus, comprising:
a processor for executing instructions;
a prefetch unit for prefetching instructions from a memory prior to sending those instructions to the processor for execution;
branch prediction logic for predicting which instructions should be prefetched by the prefetch unit, the branch prediction logic being arranged to predict whether a prefetched instruction specifies a branch operation that will cause a change in instruction flow, and if so to indicate to the prefetch unit a target address within said memory from which a next instruction should be retrieved;
the instructions including a first instruction and a second instruction that are executable independently by the processor, but which in combination specify a predetermined branch operation whose target address is uniquely derivable from a combination of attributes of the first and second instruction, the data processing apparatus further comprising:
target address logic for deriving from said combination of attributes the target address for the predetermined branch operation;
the branch prediction logic being arranged to predict whether the predetermined branch operation will cause a change in instruction flow, in which event the branch prediction logic is arranged to indicate to the prefetch unit the target address determined by the target address logic.

### Claim 2 (depends on 1)

A data processing apparatus as claimed in claim 1, wherein the combination of attributes comprises the address of the first instruction and predetermined operands of the first and second instructions, the address of the first instruction being specified by a program counter value, and the target address logic including adder logic for generating the target address by adding the program counter value to an offset value derived from the predetermined operands of the first and second instructions.

### Claim 3 (depends on 2)

A data processing apparatus as claimed in claim 2, wherein the target address logic is arranged to use the predetermined operands of one of the first and second instructions in the determination of the most significant bits of the offset value, and to use the predetermined operands of the other of the first and second instructions in the determination of the least significant bits of the offset value.

### Claim 4 (depends on 3)

A data processing apparatus as claimed in claim 3, wherein the predetermined operands of the first instruction are used in the determination of the most significant bits of the offset value, and the target address logic is arranged to shift the predetermined operands of the first instruction left by a predetermined number of bits to produce a first value, to sign extend the first value to produce a second value having the same number of bits as the program counter, and to add the predetermined operands of the second instruction to the second value to produce a third value from which the offset value is derived.

### Claim 5 (depends on 2)

A data processing apparatus as claimed in claim 2, wherein the target address logic is arranged upon occurrence of the first instruction to store the predetermined operands of the first instruction, and if the instruction following the first instruction is the second instruction, to then generate the target address.

### Claim 6 (depends on 1)

A data processing apparatus as claimed in claim 1, wherein the branch prediction logic comprises a static branch prediction logic, the static branch prediction logic incorporating the target address logic.

### Claim 7 (depends on 6)

A data processing apparatus as claimed in claim 6, wherein the processor is a pipelined processor of a processor core, the static branch prediction logic being located within the processor core such that it is arranged to issue the target address to the prefetch unit prior to committed execution of the second instruction by the processor.

### Claim 8 (depends on 1)

A data processing apparatus as claimed in claim 1, further comprising a branch target cache for storing predetermined information about branch operations executed by the processor, the predetermined information including an identification of an instruction specifying a branch operation and a target address for the branch operation, the branch prediction logic comprising dynamic branch prediction logic arranged to determine with reference to the branch target cache whether a prefetched instruction is identified within the branch target cache, to predict whether that prefetched instruction specifies a branch operation that will cause a change in instruction flow, and if so to indicate to the prefetch unit the target address as specified in the branch target cache.

### Claim 9 (depends on 8)

A data processing apparatus as claimed in claim 8, wherein upon committed execution of said second instruction by the processor, the processor is arranged to issue a branch target cache signal identifying the predetermined information about the predetermined branch operation to cause an update of the branch target cache to take place, the processor being arranged to obtain the target address from the target address logic for inclusion in the branch target cache signal.

### Claim 10 (depends on 8)

A data processing apparatus as claimed in claim 8, wherein the branch target cache includes for each branch operation identified within the branch target cache historical information about previous execution of that branch operation by the processor for use by the dynamic prediction logic in predicting whether that branch operation will cause a change in instruction flow.

### Claim 11 (depends on 8)

A data processing apparatus as claimed in claim 8, wherein said dynamic branch prediction logic is contained within said prefetch unit.

### Claim 12 (depends on 8)

A data processing apparatus as claimed in claim 8, wherein the branch prediction logic further comprises a static branch prediction logic, the static branch prediction logic incorporating the target address logic.

### Claim 13 (depends on 12)

A data processing apparatus as claimed in claim 12, wherein the processor is a pipelined processor of a processor core, the static branch prediction logic being located within the processor core such that it is arranged to issue the target address to the prefetch unit prior to committed execution of the second instruction by the processor.

### Claim 14

A method of predicting which instructions should be prefetched by a prefetch unit of a data processing apparatus, the data processing apparatus having a processor for executing instructions, and said prefetch unit being arranged to prefetch instructions from a memory prior to sending those instructions to the processor for execution, the instructions including a first instruction and a second instruction that are executable independently by the processor, but which in combination specify a predetermined branch operation whose target address is uniquely derivable from a combination of attributes of the first and second instruction, the target address specifying an address within said memory from which a next instruction should be retrieved, and the method comprising the steps of:
i) deriving from said combination of attributes the target address for the predetermined branch operation;
ii) predicting whether the predetermined branch operation will cause a change in instruction flow; and
iii) if it is predicted at said step (ii) that the predetermined branch operation will cause a change in instruction flow, indicating to the prefetch unit the target address determined at said step (i).

### Claim 15 (depends on 14)

A method as claimed in claim 14, wherein the combination of attributes comprises the address of the first instruction and predetermined operands of the first and second instructions, the address of the first instruction being specified by a program counter value, and said step (i) comprising the step of generating the target address by adding the program counter value to an offset value derived from the predetermined operands of the first and second instructions.

### Claim 16 (depends on 15)

A method as claimed in claim 15, wherein in said step (i), the predetermined operands of one of the first and second instructions are used in the determination of the most significant bits of the offset value, and the predetermined operands of the other of the first and second instructions are used in the determination of the least significant bits of the offset value.

### Claim 17 (depends on 16)

A method as claimed in claim 16, wherein the predetermined operands of the first instruction are used in the determination of the most significant bits of the offset value, and said step (i) comprises the steps of:
shifting the predetermined operands of the first instruction left by a predetermined number of bits to produce a first value;
sign extending the first value to produce a second value having the same number of bits as the program counter; and
adding the predetermined operands of the second instruction to the second value to produce a third value from which the offset value is derived.

### Claim 18 (depends on 15)

A method as claimed in claim 15, further comprising the step, prior to said step (i) of, upon occurrence of the first instruction, storing the predetermined operands of the first instruction, and if the instruction following the first instruction is the second instruction, then performing said step (i) to generate the target address.

### Claim 19 (depends on 14)

A method as claimed in claim 14, wherein said steps (i) to (iii) are performed within a static branch prediction logic of the data processing apparatus.

### Claim 20 (depends on 19)

A method as claimed in claim 19, wherein the processor is a pipelined processor of a processor core, the static branch prediction logic being located within the processor core such that it is arranged to issue the target address to the prefetch unit prior to committed execution of the second instruction by the processor.

### Claim 21 (depends on 14)

A method as claimed in claim 14, wherein the data processing apparatus further comprising a branch target cache for storing predetermined information about branch operations executed by the processor, the predetermined information including an identification of an instruction specifying a branch operation and a target address for the branch operation, the data processing apparatus further comprising dynamic branch prediction logic arranged to perform the steps of:
determining with reference to the branch target cache whether a prefetched instruction is identified within the branch target cache;
predicting whether that prefetched instruction specifies a branch operation that will cause a change in instruction flow; and
if so, indicating to the prefetch unit the target address as specified in the branch target cache.

### Claim 22 (depends on 21)

A method as claimed in claim 21, wherein upon committed execution of said second instruction by the processor, the processor is arranged to perform the step of issuing a branch target cache signal identifying the predetermined information about the predetermined branch operation to cause an update of the branch target cache to take place, the processor receiving the target address as derived at said step (i) for inclusion in the branch target cache signal.

### Claim 23 (depends on 21)

A method as claimed in claim 21, wherein the branch target cache includes for each branch operation identified within the branch target cache historical information about previous execution of that branch operation by the processor for use by the dynamic prediction logic in predicting whether that branch operation will cause a change in instruction flow.

### Claim 24 (depends on 21)

A method as claimed in claim 21, wherein said dynamic branch prediction logic is contained within said prefetch unit.

### Claim 25 (depends on 21)

A method as claimed in claim 21, wherein the data processing apparatus further comprises a static branch prediction logic, the static branch prediction logic being arranged to perform said steps (i) to (iii).

### Claim 26 (depends on 25)

A method as claimed in claim 25, wherein the processor is a pipelined processor of a processor core, the static branch prediction logic being located within the processor core such that it is arranged to issue the target address to the prefetch unit prior to committed execution of the second instruction by the processor.
