BRANCH PREDICTION USING LOOP ITERATION COUNT
An integrated circuit comprising instruction processing circuitry for processing a plurality of program instructions and instruction prediction circuitry. The instruction prediction circuitry comprises circuitry for detecting successive occurrences of a same program loop sequence of program instructions. The instruction prediction circuitry also comprises circuitry for predicting a number of iterations of the same program loop sequence of program instructions, in response to detecting, by the circuitry for detecting, that a second occurrence of the same program loop sequence of program instructions comprises a same number of iterations as a first occurrence of the same program loop sequence of program instructions.
1 . A system comprising:
a first memory configurable to store an instruction;
a first circuit coupled to the first memory and configurable to fetch the instruction from the first memory; and
a second circuit coupled to the first circuit and configurable to:
receive a value, wherein the value is based on an address of the instruction;
determine that the value corresponds to a loop;
determine that a data set for the loop is stored in a second memory, wherein the data set includes a status of the data set and a first number of iterations of the loop;
determine a second number of iterations of the loop when the status of the data set is invalid; and
compare the second number with the first number.
2 . The system of claim 1 , wherein the second circuit is configurable to set the status of the data set to a valid state when the second number matches the first number.
3 . The system of claim 2 , wherein the first circuit is configurable to fetch instructions from the first memory in a subsequent occurrence of the loop based on the first number of iterations of the loop.
4 . The system of claim 1 , wherein the second circuit is configurable to update the first number in the data set with the second number when the second number does not match the first number.
5 . The system of claim 1 , wherein the second circuit is configurable to maintain an invalid state for the status of the data set when the second number does not match the first number.
6 . The system of claim 1 , wherein to determine that the data set is stored in the second memory, the second circuit is configurable to match the value to an entry stored in the second memory.
7 . The system of claim 1 , wherein the status of the data set stored in the second memory includes a single bit indicating an invalid state.
8 . The system of claim 1 , wherein the second memory includes a branch target buffer.
9 . The system of claim 1 , wherein the second circuit is configurable to store a new data set characterizing the loop to the second memory when no data set characterizing the loop is stored in the second memory.
10 . The system of claim 9 , wherein the new data set includes a new number of iterations of the loop and an invalid state indication.
11 . The system of claim 1 , further comprising a program counter coupled to the first circuit and the second circuit,
wherein the program counter is configurable to store the value.
12 . The system of claim 11 , wherein the first circuit is configurable to:
generate the address of the instruction based on the value; and
fetch the instruction from the first memory based on the address of the instruction.
13 . The system of claim 1 , wherein the second circuit is configurable to determine the second number as a count of iterations of the loop executed by a processing circuit.
14 . The system of claim 1 , wherein the second circuit is configurable to determine the second number by incrementing a counter for each iteration of the loop.
15 . The system of claim 1 , wherein to determine that the value corresponds to the loop, the second circuit is configurable to determine that the value corresponds to a beginning of the loop.
16 . A method comprising:
receiving a value, wherein the value is based on an address of an instruction;
determining that the value corresponds to a loop;
determining that a data set for the loop is stored in a memory, wherein the data set includes a status of the data set and a first number of iterations of the loop;
determining a second number of iterations of the loop when the status of the data set is invalid; and
comparing the second number to the first number.
17 . The method of claim 16 , further comprising:
setting the status of the data set to a valid state when the second number matches the first number; and
fetching instructions from the memory in a subsequent occurrence of the loop based on the first number of iterations of the loop.
18 . The method of claim 16 , further comprising:
updating the first number in the data set with the second number when the second number does not match the first number; and
maintaining an invalid state for the status of the data set when the second number does not match the first number.
19 . A system comprising:
a program counter configurable to store a value, wherein the value is based on an address of an instruction;
processing circuitry coupled to the program counter and configurable to:
determine that the value corresponds to a loop;
determine that a data set for the loop is stored in a second memory, wherein the data set includes a validity bit and a first number of iterations of the loop;
determine a second number of iterations of the loop when the validity bit has an invalid state;
set the validity bit to a valid state when the second number matches the first number; and
update the first number in the data set with the second number when the second number does not match the first number.
20 . The system of claim 19 , wherein to determine that the value corresponds to the loop, the processing circuitry is configurable to determine that the value corresponds to a beginning of the loop.