# US 2020/0004542 A1 · Automatic predication of hard-to-predict convergent branches

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

- Number: US 2020/0004542 A1
- Document ID: US20200004542A1
- Status: Published application
- Kind: A1
- Application number: 16/021,838
- Filed: 2018-06-28
- Published: 2020-01-02
- Earliest claimed: 2018-06-28
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Adarsh Chauhan; Jayesh Gaur; Zeev Sperber; Sumeet Bandishte; Lihu Rappoport; Stanislav Shwartsman; Kamil Garifullin; Sreenivas Subramoney; Adi Yoaz; Hong Wang
- Web page: https://patentgrep.com/patent/US20200004542A1

## CPC

- G06F 9/3804: {for branches, e.g. hedging, branch folding}
- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F 9/30058: {Conditional branch instructions}
- G06F 9/323: {for indirect branch instructions}
- G06F 9/30163: {with implied specifier, e.g. top of stack}
- G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables}
- G06F 9/3846: {using static prediction, e.g. branch taken strategy}
- G06F 9/3848: {using hybrid branch prediction, e.g. selection between prediction techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A processing device includes a branch IP table and branch predication circuitry coupled to the branch IP table. The branch predication circuitry to: determine a dynamic convergence point in a conditional branch of set of instructions; store the dynamic convergence point in the branch IP table; fetch a first and second speculative path of the conditional branch; while determining which of the first speculative path and the second speculative path is a taken path of the conditional branch and determining whether a dynamic convergence point is fetched corresponding to the stored dynamic convergence point, stall scheduling of instructions of the first speculative path and the second speculative path; and in response to determining that one of the first speculative path and the second speculative path is the taken path and the fetched dynamic convergence point corresponds to the stored convergence point, resume scheduling of the instructions of the taken path.

## Claims

### Claim 1

A processing device comprising:
a branch instruction pointer (IP) table; and
branch predication circuitry coupled to the branch IP table, the branch predication circuitry to:
determine a dynamic convergence point in a conditional branch of set of instructions;
store the dynamic convergence point in the branch IP table;
fetch a first speculative path and a second speculative path of the conditional branch;
while determining which of the first speculative path and the second speculative path is a taken path of the conditional branch and determining whether a dynamic convergence point is fetched corresponding to the stored dynamic convergence point, stall scheduling of instructions of the first speculative path and the second speculative path; and
in response to determining that one of the first speculative path and the second speculative path is the taken path and the fetched dynamic convergence point corresponds to the stored convergence point, resume scheduling of the instructions of the taken path.

### Claim 2 (depends on 1)

The processing device of claim 1, further comprising:
a branch instruction buffer coupled to the branch IP table and the branch predication circuitry;
wherein the branch predication circuitry to determine a dynamic convergence point further comprises the branch predication circuitry to, in response to misprediction of the first speculative path:
store a number of instructions of the first speculative path in the branch instruction buffer;
fetch the number of instructions of the second speculative path; and
determine a matching instruction pointer between the stored number instructions of the first speculative path and the fetched number of instructions of the second speculative path.

### Claim 3 (depends on 1)

The processing device of claim 1, wherein the fetch the first speculative path and the second speculative path comprises:
override an original prediction of a branch prediction unit of the processing device to fetch the first speculative path.

### Claim 4 (depends on 3)

The processing device of claim 3, further comprising:
in response to completing fetching the first speculative path, override the original prediction of the branch prediction unit of the processing device to fetch the second speculative path.

### Claim 5 (depends on 1)

The processing device of claim 1, wherein the fetch the first speculative path and the second speculative path comprises:
comparing a number of bytes of the first speculative path or the second speculative path to a threshold value; and
determine divergence when the number bytes of the first speculative path or the second speculative path exceeds the threshold value.

### Claim 6 (depends on 5)

The processing device of claim 5, further comprising:
in response to determining the divergence, executing a control misspeculation/branch misprediction instruction.

### Claim 7 (depends on 5)

The processing device of claim 5, further comprising:
in response to determining the divergence, convert fetched micro-operations of a wrong path to no-operations.

### Claim 8 (depends on 1)

The processing device of claim 1, wherein the dynamic convergence point in the conditional branch is not static.

### Claim 9

A processing system comprising:
a memory; and
a processing core coupled to the memory, the processing core comprising:
a branch instruction pointer (IP) table; and
branch predication circuitry, wherein the branch predication circuitry to:
determine a dynamic convergence point in a conditional branch;
setting an automatic predication flag corresponding to the conditional branch in the branch IP table;
responsive to the setting of the automatic predication flag, fetch a first speculative path and a second speculative path of the conditional branch;
while determining which of the first speculative path and the second speculative path is a taken path of the conditional branch, stall scheduling of instructions of the first speculative path and the second speculative path; and
in response to determining that one of the first speculative path and the second speculative path is the taken path, resume scheduling of the instructions of the taken path.

### Claim 10 (depends on 9)

The processing system of claim 9, wherein the processing core further comprising a branch instruction buffer coupled to the branch IP table and the branch predication circuitry;
wherein the branch predication circuitry to determine a dynamic convergence point further comprises the branch predication circuitry to, in response to misprediction of the first speculative path:
store a number of instructions of the first speculative path in the branch instruction buffer;
fetch the number of instructions of the second speculative path; and
determine a matching instruction pointer between the stored number of instructions of the first speculative path and the fetched number of instructions of the second speculative path.

### Claim 11 (depends on 9)

The processing system of claim 9, wherein the fetch the first speculative path and the second speculative path comprises:
override original prediction of a branch prediction unit to fetch the first speculative path.

### Claim 12 (depends on 11)

The processing system of claim 11, further comprising:
in response to completing fetching the first speculative path, override the original prediction of the branch prediction unit of the processing device to fetch the second speculative path.

### Claim 13 (depends on 9)

The processing system of claim 9, wherein the fetch the first speculative path and the second speculative path comprises:
comparing a number of bytes of the first speculative path or the second speculative path to a threshold value; and
determine divergence when the number bytes of the first speculative path or the second speculative path exceeds the threshold value.

### Claim 14 (depends on 13)

The processing system of claim 13, further comprising:
in response to determining the divergence, executing a control misspeculation/branch misprediction instruction.

### Claim 15 (depends on 13)

The processing system of claim 13, further comprising:
in response to determining the divergence, convert fetched micro-operations of a wrong path to no-operations.

### Claim 16 (depends on 9)

The processing system of claim 9, wherein the dynamic convergence point in the conditional branch is not static.

### Claim 17

A method for comprising:
determining, by branch predication circuitry in a processing core, a dynamic convergence point in a conditional branch;
storing the dynamic convergence point in a branch instruction pointer (IP) table;
fetching a first speculative path and a second speculative path of the conditional branch;
while determining which of the first speculative path and the second speculative path is a taken path of the conditional branch, stalling scheduling of instructions of the first speculative path and the second speculative path; and
in response to determining that one of the first speculative path and the second speculative path is the taken path, resume scheduling of the instructions of the taken path.

### Claim 18 (depends on 17)

The method of claim 17, wherein the determining a dynamic convergence point comprises:
in response to misprediction of the first speculative path:
storing a number of instructions of the first speculative path in a branch instruction buffer;
fetching the number of instructions of the second speculative path; and
determining a matching instruction pointer between the stored instructions of the first speculative path and the fetched instructions of the second speculative path.

### Claim 19 (depends on 17)

The method of claim 17, wherein the fetching the first speculative path and the second speculative path comprises:
overriding an original prediction of a branch prediction unit of a processing device to fetch the first speculative path.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
in response to completing fetching the first speculative path, overriding the original prediction of the branch prediction unit of the processing device to fetch the second speculative path.
