Apparatus and Method for Implementing a Loop Prediction of Multiple Basic Blocks
AssigneeCondor Computing Corporation
InventorThang Tran
Life of this patent
Estimating the term…
Abstract
A processor includes a branch execution unit to detect a dual basic-block loop type where a second basic block jumps to the start address of a first basic block. The dual basic-block loop includes a predicted loop count to write to an entry of a branch target buffer (BTB). Two basic-blocks loop of the loop prediction from BTB forms a loop buffer in an instruction queues of the processor to seamlessly sending loop instructions from plurality of iterations to the next pipeline stage.
Claims20
A processor comprising:
- a branch target buffer (BTB) that stores a predicted loop type of a loop, the BTB including a plurality of BTB entries addressable by an entry address, each of the BTB entries including a branch type comprising a loop type and a loop count, wherein the loop type comprises of a first basic block of a predicted loop and a second basic block of the predicted loop and wherein the combination of the first and second basic blocks is a dual basic-block loop prediction with a plurality of iteration of the loop;
- and
- an instruction queue that processes a plurality of iterations of the loop in response to the loop being classified as dual basic-block loop.
A processor comprising:
- a branch execution unit that identifies a loop and classifies the loop in accordance with a number of basic blocks to form a loop;
- a branch target buffer (BTB), including a plurality of BTB entries addressable by an entry address, the BTB receiving from the branch execution unit, an entry address for the loop, a loop type for the loop, and a predicted loop count for the loop;
- a branch prediction queue that tracks all branch predictions and tracks the predicted loop count in the branch execution unit and the instruction issue unit for program counter calculation;
- an instruction queue that receives a first basic block of a dual basic-block loop prediction and delays issuing of the loop instructions until a second basic block of the dual basic-block loop prediction is received;
- and
- the instruction queue operates to virtually unroll instructions in the corresponding plurality of iterations to a next pipeline stage of the processor.
A computer program product stored on a non-transitory computer readable storage medium and including computer system instructions for causing a computer system to execute a method that is executable by a processor, the method detecting a dual basic-block loop type in a series of instructions and generating a predicted loop count, the method comprising:
- identifying in the series of instructions, a basic block of instructions and classifying the basic block of instructions as a first basic block of the dual basic-block loop;
- identifying in the series of instructions, a basic block of instructions and classifying the basic block of instructions as a second basic block of the dual basic-block loop;
- classifying the loop into one of a plurality of loop types based on a first or second basic block of the dual basic-block loop;
- and
- sending the first and second basic blocks of instructions to an instruction queue based on the loop types of the dual basic-block loop.
Dependencies are inferred from the claim text.