Predicting branches for vector partitioning loops when processing vector instructions

1. A method for executing instructions in a vector processor, comprising:

while fetching instructions from program code in the processor, repeatedly:

starting from an initial instruction in a loop in the program code, fetching instructions from the loop; and

upon fetching a branch instruction from the loop that, when taken, causes the processor to branch back to the initial instruction, incrementing a branch instruction counter and predicting the branch instruction as taken, causing the processor to return to the initial instruction and continue fetching instructions from the loop;

while fetching the instructions from the loop, calculating a number of times that the branch instruction will actually be taken when the fetched instructions are executed, wherein calculating the number of times that the branch instruction will actually be taken comprises receiving a dependency index vector (DIV) for the loop in the program code, the DIV indicating dependencies between iterations for the loop of program code, and executing a SegCount instruction with the DIV as an input, wherein an output of the SegCount instruction indicates number of times that the branch instruction will actually be taken; and

upon determining that the branch instruction counter is greater than the number of times that the branch instruction will actually be taken, immediately commencing a mispredict operation for the branch instruction, which comprises:

flushing fetched instructions from the loop that will not be executed from the processor; and

commencing fetching instructions from an instruction following the branch instruction.

2. The method of claim 1 , wherein the method further comprises:

placing the fetched instructions in one or more issue queues, wherein instructions are buffered in the one or more issue queues before being issued for execution;

wherein flushing fetched instructions from the loop that will not be executed from the processor comprises flushing instructions from at least one of the one or more issue queues and clearing other instruction-tracking mechanisms in the processor after a first instance in the issue queue of the branch instruction that will not be taken.

3. The method of claim 1 , wherein the method further comprises:

encountering a SegCount instruction;

based on encountering the SegCount instruction, determining that the processor is about to, starting from the initial instruction, commence fetching instructions from the loop; and

configuring the processor to increment the branch instruction counter upon fetching a branch instruction that branches backward in the program code.

4. The method of claim 1 , wherein immediately commencing the mispredict operation for the branch instruction comprises commencing the mispredict operation without executing the branch instruction to determine that the branch was mispredicted.

5. The method of claim 1 , wherein flushing fetched instructions from the loop that will not be executed from the processor comprises:

determining a location of a first mispredicted branch instruction within the processor; and

flushing the first mispredicted branch instruction and any instructions fetched after the first mispredicted branch instruction from the processor.

6. The method of claim 1 , wherein commencing fetching instructions from the instruction following the branch instruction comprises:

updating a program counter from an initial value to the value where the instruction following the branch instruction is located; and

using the updated program counter to fetch subsequent instructions.

7. The method of claim 1 , wherein the method further comprises:

upon determining that the branch instruction counter is less than the number of times that the branch instruction will actually be taken, continuing to fetch instructions from the loop in program code.

8. A processor for executing program code, comprising:

an execution unit, wherein the execution unit is configured to:

while fetching instructions from program code, repeatedly:

starting from an initial instruction in a loop in the program code, fetch instructions from the loop; and

upon fetching a branch instruction from the loop that, when taken, causes the processor to branch back to the initial instruction, increment a branch instruction counter and predict the branch instruction as taken, causing the processor to return to the initial instruction and continue fetching instructions from the loop;

while fetching the instructions from the loop, calculate a number of times that the branch instruction will actually be taken when the fetched instructions are executed, wherein calculating the number of times that the branch instruction will actually be taken comprises receiving a dependency index vector (DIV) for the loop in the program code, the DIV indicating dependencies between iterations for the loop of program code, and executing a SegCount instruction with the DIV as an input, wherein an output of the SegCount instruction indicates number of times that the branch instruction will actually be taken; and

upon determining that the branch instruction counter is greater than the number of times that the branch instruction will actually be taken, immediately commence a mispredict operation for the branch instruction, which comprises:

flushing fetched instructions from the loop that will not be executed from the processor; and

commencing fetching instructions from an instruction following the branch instruction.

9. The processor of claim 8 , wherein the execution unit is configured to place the fetched instructions in one or more issue queues, wherein instructions are buffered in the one or more issue queues before being issued for execution; and

wherein, when flushing fetched instructions from the loop that will not be executed from the processor, the execution unit is configured to flush instructions from at least one of the one or more issue queues and clear other instruction-tracking mechanisms after a first instance in the issue queue of the branch instruction that will not be taken.

10. The processor of claim 8 , wherein the execution unit is configured to:

encounter a SegCount instruction;

based on encountering the SegCount instruction, determine that the execution unit is about to, starting from the initial instruction, commence fetching instructions from the loop; and

configuring the execution unit to increment the branch instruction counter upon fetching a branch instruction that branches backward in the program code.

11. The processor of claim 8 , wherein, when immediately commencing the mispredict operation for the branch instruction, the execution unit is configured to commence the mispredict operation without executing the branch instruction to determine that the branch was mispredicted.

12. The processor of claim 8 , wherein, when flushing fetched instructions from the loop that will not be executed from the processor, the execution unit is configured to:

determine a location of a first mispredicted branch instruction within the processor; and

flush the first mispredicted branch instruction and any instructions fetched after the first mispredicted branch instruction from the processor.

13. The processor of claim 8 , wherein, when commencing fetching instructions from the instruction following the branch instruction, the execution unit is configured to:

update a program counter from an initial value to the value where the instruction following the branch instruction is located; and

use the updated program counter to fetch subsequent instructions.

14. The processor of claim 8 , wherein upon determining that the branch instruction counter is less than the number of times that the branch instruction will actually be taken, the execution unit is configured to continue to fetch instructions from the loop in program code.

15. A computer system for executing program code, comprising:

a processor;

a memory coupled to the processor that stores data and instructions for the processor;

at least one execution unit in the processor configured to

while fetching instructions from program code, repeatedly:

starting from an initial instruction in a loop in the program code, fetch instructions from the loop; and

upon fetching a branch instruction from the loop that, when taken, causes the processor to branch back to the initial instruction, increment a branch instruction counter and predict the branch instruction as taken, causing the processor to return to the initial instruction and continue fetching instructions from the loop;

while fetching the instructions from the loop, calculate a number of times that the branch instruction will actually be taken when the fetched instructions are executed, wherein calculating the number of times that the branch instruction will actually be taken comprises receiving a dependency index vector (DIV) for the loop in the program code, the DIV indicating dependencies between iterations for the loop of program code, and executing a SegCount instruction with the DIV as an input, wherein an output of the SegCount instruction indicates number of times that the branch instruction will actually be taken; and

upon determining that the branch instruction counter is greater than the number of times that the branch instruction will actually be taken, immediately commence a mispredict operation for the branch instruction, which comprises:

flushing fetched instructions from the loop that will not be executed from the processor; and

commencing fetching instructions from an instruction following the branch instruction.

16. The computer system of claim 15 , wherein the execution unit is configured to place the fetched instructions in one or more issue queues, wherein instructions are buffered in the one or more issue queues before being issued for execution; and

wherein, when flushing fetched instructions from the loop that will not be executed from the processor, the execution unit is configured to flush instructions from at least one of the one or more issue queues and clear other instruction-tracking mechanisms after a first instance in the issue queue of the branch instruction that will not be taken.

17. The computer system of claim 15 , wherein the execution unit is configured to:

encounter a SegCount instruction;

based on encountering the SegCount instruction, determine that the execution unit is about to, starting from the initial instruction, commence fetching instructions from the loop; and

configuring the execution unit to increment the branch instruction counter upon fetching a branch instruction that branches backward in the program code.

18. The computer system of claim 15 , wherein, when immediately commencing the mispredict operation for the branch instruction, the execution unit is configured to commence the mispredict operation without executing the branch instruction to determine that the branch was mispredicted.

19. The computer system of claim 15 , wherein, when flushing fetched instructions from the loop that will not be executed from the processor, the execution unit is configured to:

determine a location of a first mispredicted branch instruction within the processor; and

flush the first mispredicted branch instruction and any instructions fetched after the first mispredicted branch instruction from the processor.

20. The computer system of claim 15 , wherein, when commencing fetching instructions from the instruction following the branch instruction, the execution unit is configured to:

update a program counter from an initial value to the value where the instruction following the branch instruction is located; and

use the updated program counter to fetch subsequent instructions.

21. The computer system of claim 15 , wherein upon determining that the branch instruction counter is less than the number of times that the branch instruction will actually be taken, the execution unit is configured to continue to fetch instructions from the loop in program code.