Storing taken branch information

A method and system for storing branch information is disclosed. First data may be stored in a first entry of a first table in response to a determination that a fetched instruction is a branch instruction. Second data that is dependent upon at least one previously taken branch may be stored in a second entry in a second table in response to a determination that a branch associated with the instruction is predicted to be taken. The first data may be updated to include an index to the second data in response to the determination that the branch is predicted to be taken.

BACKGROUND

Technical Field

Embodiments described herein relate to processors or processor cores, and more particularly, to techniques for branch prediction.

Description of the Related Art

Computing systems may include one or more systems-on-a-chip (SoC), which may integrate a number of different functions, such as, graphics processing, onto a single integrated circuit. With numerous functions included in a single integrated circuit, chip count may be kept low in mobile computing systems, such as tablets, for example, which may result in reduced assembly costs, and a smaller form factor for such mobile computing systems.

To implement the desired functions on an SoC, one or more processors may be employed. Each processor may retrieve program instructions from memory (commonly referred to as an “instruction fetch”). When fetching such program instructions, a processor may check a hierarchy of local or cache memories for the desired instruction. If the instruction is not available in the hierarchy of local of cache memories, the processor may issue a request to retrieve the desired instruction from main memory or other storage such as, a CD-ROM, or a hard drive, for example.

Each fetched instruction may cause the processor to perform different functions. Some instructions cause the processor to perform arithmetic or logical operations on one or more operands. Other instructions may cause the processor to load data from or store data to a memory or other storage device, while some instructions may cause the processor to change a location from which a subsequent instruction will be fetched.

SUMMARY OF THE EMBODIMENTS

Various embodiments of a computing system are disclosed. Broadly speaking, a system may include circuitry configured to store first data in a first entry of a first plurality of entries in a first memory in response to a determination that an instruction is a branch instruction. The circuitry may be further configured to store second data that is dependent upon at least one previously taken branch in a second entry in a second plurality of entries in a second memory in response to a determination that a prediction indicates that a branch associated with the instruction will be taken. The first data may be updated by the circuitry to include an index to the second entry in response to the determination that the prediction indicates the branch will be taken.

In one embodiment, the circuitry may be further configured to store third data in third entry of the second plurality of entries in response to a determination that, upon execution, the branch associated with the instruction is taken and a determination that the prediction indicates that the instruction would not be taken.

In a further embodiment, the circuitry may be further configured to retrieve the second data from the second entry in response to a determination that, upon execution, the branch associated with the instruction is not taken and the determination that the prediction indicates that the branch associated with the instruction would be taken.

DETAILED DESCRIPTION OF EMBODIMENTS

Some instructions executed by a processor or processor core may affect a location from where subsequent instructions may be fetched. Such instructions are commonly referred to as branch instructions. Some branch instructions unconditionally change the program flow, while other branch instructions affect the program flow dependent upon a conditional.

Each time a conditional branch instruction is encountered, the processor or processor core may attempt to predict whether or not the branch will be taken (commonly referred to as “branch prediction”). Such predictions may be made based on a history of previous branch instructions and whether their associated branches were taken or not taken.

Once a prediction has been made, the processor or processing core may begin to fetch instructions from along the predicted path (either the original path or the branch path depending on the prediction). While the speculative fetching is occurring, the branch instruction is continuing through the processor or processing core to the execution unit, where it is finally evaluated and the actual outcome of the conditional is determined. If the prediction was correct, then no further action may be needed. If, however, the prediction was incorrect, i.e., a misprediction, then speculatively fetched, and possibly executed instructions, need to be discarded, and instructions fetched from the correct program path.

Following a misprediction, it is desirable to have information regarding the branch instruction in order to determine from which location in memory to begin fetching instructions along the correct path. Such information may include branch history up to the point of a particular branch instruction, branch address information, and the like. Storing such data may require large amounts of storage space. The embodiments illustrated in the drawings and described below may provide techniques for storing branch information while limiting the overall storage requirements in order to save area and power.

A block diagram of an integrated circuit including multiple functional units is illustrated inFIG. 1. In the illustrated embodiment, the integrated circuit100includes a processor101, and a processor complex (or simply a “complex”)107coupled to memory block102, and analog/mixed-signal block103, and I/O block104through internal bus105. In various embodiments, integrated circuit100may be configured for use in a desktop computer, server, or in a mobile computing application such as, e.g., a tablet or laptop computer.

An embodiment of a computing system that may prefetch instructions along a predicted path is illustrated inFIG. 1. As described below in more detail, processor101may, in various embodiments, be representative of a general-purpose processor that performs computational operations. For example, processor101may be a central processing unit (CPU) such as a microprocessor, a microcontroller, an application-specific integrated circuit (ASIC), or a field-programmable gate array (FPGA).

Complex107includes processor cores108A and108B. Each of processor cores108A and108B may be representative of a general-purpose processor configured to execute software instructions in order to perform one or more computational operations. Processor cores108A and108B may be designed in accordance with one of various design styles and may include one or more cache memories. In various embodiments, coherency may be maintained across cache memories included in processor cores108A and108B. It is noted that although only two processor cores are depicted in complex107, in other embodiments, any suitable number of processor cores.

Memory block102may include any suitable type of memory such as a Dynamic Random Access Memory (DRAM), a Static Random Access Memory (SRAM), a Read-only Memory (ROM), Electrically Erasable Programmable Read-only Memory (EEPROM), or a non-volatile memory, for example. It is noted that in the embodiment of an integrated circuit illustrated inFIG. 1, a single memory block is depicted. In other embodiments, any suitable number of memory blocks may be employed.

In some cases, Memory block102may store a copy of data also stored in cache memories included in processor cores108A and108B. In various embodiments, multiple copies of particular data items may be maintained according to a coherency protocol such as, MOESI, for example. Coherent requests and corresponding responses (collectively “transactions” may be transmitted via bus105). In other embodiments, additional busses connecting different circuit blocks may be employed. Such additional busses may only support non-coherent commands.

Analog/mixed-signal block103may include a variety of circuits including, for example, a crystal oscillator, a phase-locked loop (PLL), an analog-to-digital converter (ADC), and a digital-to-analog converter (DAC) (all not shown). In other embodiments, analog/mixed-signal block103may be configured to perform power management tasks with the inclusion of on-chip power supplies and voltage regulators. Analog/mixed-signal block103may also include, in some embodiments, radio frequency (RF) circuits that may be configured for operation with wireless networks.

I/O block104may be configured to coordinate data transfer between integrated circuit100and one or more peripheral devices. Such peripheral devices may include, without limitation, storage devices (e.g., magnetic or optical media-based storage devices including hard drives, tape drives, CD drives, DVD drives, etc.), audio processing subsystems, or any other suitable type of peripheral devices. In some embodiments, I/O block104may be configured to implement a version of Universal Serial Bus (USB) protocol or IEEE 1394 (Firewire®) protocol.

I/O block104may also be configured to coordinate data transfer between integrated circuit100and one or more devices (e.g., other computer systems or integrated circuits) coupled to integrated circuit100via a network. In one embodiment, I/O block104may be configured to perform the data processing necessary to implement an Ethernet (IEEE 802.3) networking standard such as Gigabit Ethernet or 10-Gigabit Ethernet, for example, although it is contemplated that any suitable networking standard may be implemented. In some embodiments, I/O block104may be configured to implement multiple discrete network interface ports.

It is noted that the embodiment illustrated inFIG. 1is merely an example. In other embodiments, different functional units, and different arrangements of functional units may be employed.

A possible embodiment of a cores108a-bis illustrated inFIG. 2. In the illustrated embodiment, core200includes an Instruction Fetch Unit (IFU)210coupled to a Memory Management Unit (MMU)220, a Cache Interface270, Branch Predictor280, and one or more of Execution Units230. Execution unit(s)230is coupled to Load Store Unit (LSU)250, which is also coupled to send data back to each of execution unit(s)230. Additionally, LSU250is coupled to cache interface270, which may in turn be coupled to on-chip network, such as internal bus105as shown inFIG. 1, for example.

Instruction Fetch Unit210may be configured to provide instructions to the rest of core200for execution. In the illustrated embodiment, IFU210may be configured to perform various operations relating to the fetching of instructions from cache or memory, the selection of instructions from various threads for execution, and the decoding of such instructions prior to issuing the instructions to various functional units for execution. Instruction Fetch Unit210further includes an Instruction Cache214. In one embodiment, IFU210may include logic to maintain fetch addresses (e.g., derived from program counters) corresponding to each thread being executed by core200, and to coordinate the retrieval of instructions from Instruction Cache214according to those fetch addresses. Additionally, in some embodiments IFU210may include a portion of a map of virtual instruction addresses to physical addresses. The portion of the map may be stored in an Instruction Translation Lookaside Buffer (ITLB), such as ITLB215, for example. In the case of a branch misprediction, IFU210may fetch some instructions based on data received from Branch Predictor280.

Branch Predictor280is coupled to IFU210and may be configured to determine instructions to fetch into Instruction Cache210in response to detecting branch instruction. As used and described herein, a branch instruction is an instruction which may affect a location from which subsequent instructions are fetched. Branch Predictor280may predict if a branch included in a particular branch instruction will be taken or not taken. In response to the prediction made my Branch Predictor280, IFU210may fetch instructions along the program path indicated by whether the branch was predicted as being taken or not taken. In various embodiments, Branch Predictor280includes Branch Instruction Unit (BIU)290. As described below, in more detail, BIU290may be configured to store information relating to branch instructions. Once Execution unit(s)230have executed a particular branch instruction, it may be determined if the prediction regarding the particular branch instruction was correct. In the event that the prediction was incorrect, information stored in BIU290may be used to reset IFU210so that instructions along the correct program path may be fetched.

Execution Unit230may be configured to execute and provide results for certain types of instructions issued from IFU210. In one embodiment, Execution Unit230may be configured to execute certain integer-type and floating-point instructions defined in the implemented ISA, such as arithmetic, logical, and shift instructions. It is contemplated that in some embodiments, core200may include more than one execution unit, and each of the execution units may or may not be symmetric in functionality.

Load Store Unit250may be configured to process data memory references, such as integer and floating-point load and store instructions. In some embodiments, LSU250may also be configured to assist in the processing of Instruction Cache214misses originating from IFU210. LSU250includes Data Cache352as well as logic configured to detect cache misses and to responsively request data from a particular cache memory via Cache Interface270. In one embodiment, Data Cache252may be configured as a write-through cache in which all stores are written to a particular cache memory regardless of whether they hit in Data Cache252. In other embodiments, Data Cache252may be implemented as a write-back cache.

In one embodiment, LSU250may include a miss queue configured to store records of pending memory accesses that have missed in Data Cache252such that additional memory accesses targeting memory addresses for which a miss is pending may not generate additional cache request traffic. In the illustrated embodiment, address generation for a load/store instruction may be performed by one of Execution Unit(s)230. Depending on the addressing mode specified by the instruction, one of Execution Unit(s)230may perform arithmetic (such as adding an index value to a base value, for example) to yield the desired address. Additionally, in some embodiments LSU250may include logic configured to translate virtual data addresses generated by Execution Unit(s)230to physical addresses. For example, in the present embodiment, LSU250includes a Data Translation Lookaside Buffer (DTLB)253.

It is noted that the embodiment illustrated inFIG. 2is merely an example and that some circuit blocks have been omitted for clarity. In other embodiments, different numbers of circuit blocks and different arrangements of circuit blocks may be employed.

Turning toFIG. 3, an embodiment of a Branch Information Unit is illustrated. In the illustrated embodiment, BIUt300may correspond to BIU290as depicted in the embodiment illustrated inFIG. 2. BIU300includes, Branch Information Table (BIT)301, taken Branch Information Table (tBIT)303, and Circuitry305coupled to both BIT301and tBIT303.

BIT301may include multiple entries, such as, entry302, for example. In some embodiments, BIT301may include 60 entries. As described below in more detail, portions of Branch instruction information308may be stored in a particular entry in BIT301. Each entry in BIT301may correspond to a particular branch instruction. A given entry in BIT301may also include a pointer to a corresponding entry in tBIT303. Although only a single entry is depicted in BIT301, it is noted that any suitable number of entries may be employed.

tBIT303may also include multiple entries, such as, entry304, for example. In some embodiments, tBIT303may include 96 entries. Different portions of Branch instruction information308may be stored in a particular entry in tBIT303. As described below in more detail, branch history information may be stored in a given entry in tBIT303. Such branch history information may be stored in response to a determination a prediction indicates that a branch associated with a current instruction will be taken. If it is determined that a branch associated with the branch instruction was actually taken upon execution of the branch instruction, the branch history information may also be stored in an entry in tBIT303even though it was mispredicted as not being taken. When data is stored in an entry in tBIT303, an index value may be added to a corresponding entry in BIT301that points to the entry in tBIT303. By storing branch history information for only branches that are taken, the overall storage requirements for storing branch information may be reduced, thereby saving area and power, in some embodiments.

Both BIT301and tBIT303may be designed according to one of various design styles. For example, in some embodiments, BIT301and tBIT303may each include a register file, which include multiple latches, flip-flop, or other suitable storage circuits, each configured to store a single data bit. In various embodiments, the storage circuits may by dual-ported providing separate ports for storing and retrieving data from the storage circuits. Pointers306and307may be used, in some embodiments, to connect specific groups of storage circuits to common data input and output lines. It is noted that register files may be used in a particular embodiment, and that, in other embodiments, any suitable memory circuit may be employed.

In some embodiments, BIT301and tBIT303may have multiple read ports, each of which may be used in conjunction with different pipelines within an execution unit. The data retrieved through the read ports may be used to restore the respective histories of the Branch Direction Predictor (BDP) and Branch Target Predictor (BTP). Other read ports may be used to retrieve data in BIT301and tBIT303to train the BDP or the Return Address Stack (RAS). A separate read port may be used when a given branch is ready to retire and the BDP needs to be trained.

Circuitry305may be configured to generate pointers306and307, which are coupled to BIT301and tBIT303, respectively. It is noted that, in various embodiments, pointers306and307may each include multiple pointers used to read and write their respective tables. As described above, multiple read pointers may be used to retrieve information from BIT301and tBIT303to send to front-end instruction fetch and branch prediction circuits. Write pointers may point to entry which should be used to store data relating to a new branch instruction. Retire pointers may be employed to indicate the next branch to retire. Additionally, training pointers may be used to indicate the next branch that needs to be trained in the BDP or RAS. It is noted that when no further free entries are available in BIT301and tBIT303, Circuitry305may reuse previous pointer values allowing previously used entries to be re-used for new data.

Circuitry305may be designed according to several design styles. In various embodiments, Circuitry305may include multiple static logic gates coupled together to perform the desired logic function. Alternatively, or additionally, Circuitry305may include one or more state elements, allowing Circuitry305to function as a sequential logic circuit or state machine.

It is noted that the embodiment illustrated inFIG. 3is merely an example. In other embodiments, different circuit blocks and different configurations of circuit blocks may be employed.

Turning toFIG. 4, a table illustrating data stored in a BIT, such as, BIT301, is depicted. A BIT may be separated into different sections (referred to herein as “slices”), each of which may correspond to a particular type of branch instruction. Within each slice, different fields may store different information.

In the present embodiment, Slice 0 is used for all types of branches and includes 4 different fields. TBITTIDX may include a pointer to a corresponding entry in a tBIT as described above. BPADDRLO may include a branch address, while BDPTAKEN may indicate if the corresponding branch was predicted to be taken.

When a particular branch involves the use of a Branch Detection Predictor (BDP), additional information may be stored in slice 1 fields. For example, BSPADDRHI includes different bits of the branch address, and BDPUPDU may indicate if the corresponding branch will update “U-bits” used in the training of the BDP.

It is noted that the table depicted inFIG. 4is merely an example. In other embodiments, different fields and different organization of slices may be employed.

Just as different types of branches store different information in a BIT, different types of branches may store different information in a tBIT. A table depicting an embodiment of data storage in a tBIT, such as, e.g., tBIT303, is illustrated inFIG. 5.

The fields included in slice 0 may be used to store data for branches using the Branch Target Predictor (BTP). As depicted in the table illustrated inFIG. 5, the fields include information specifying the BTP hit table index, U-bits for BTP tables, a counter bit for the BTP hit table, and the fetch group program counter value for the BTP branch. It is noted that, in some embodiments, slice 0 of a tBIT may a logical slice and may share the physical storage of slice 1 of a BIT.

Slice 1 in the tBIT may be used for all types of branches and may store branch target path history (GHIST) and branch address path history (PHIST) values for the BDP. In various embodiments, the GHIST value may be updated for each taken branch by shifting the old history left by one bit and the performing an exclusive-OR (XOR) operation using the target of every taken branch, excluding the bottom bits.

The PHIST value, in some embodiments, may be updated by shifting the old PHIST value left by one bit and the performing an XOR operation on the shifted value and 4-bits of the branch address. By employing a different method for generating the PHIST values, more useful information is available when performing a lookup in the BDP tables.

In the present embodiment, slice 2 includes information for function calls and returns. Specifically, slice 2 stores information for the Return Address Stack (RAS) pop branch, the age of a RAS branch, and the RAS pop pointer.

It is noted that the embodiment illustrated inFIG. 5is merely an example. In other embodiments, different numbers of slices and different fields within a given slice are possible and contemplated.

Turning toFIG. 6, a flow diagram depicting an embodiment of method for allocating entries in a BIU is illustrated. Referring collectively to the embodiment ofFIG. 3, along with the flow diagram ofFIG. 6, the method begins in block601. BIU300may then receive an instruction602. In various embodiments, IFU210may perform at least a partial decode of the instruction to determine whether the instruction is a branch instruction. Information indicating if the instruction is a branch instruction to BIU300. The method may then depend on whether the instruction is a branch instruction (block603).

If the instruction is not a branch instruction, then the method may conclude in block607. Alternatively, if the instruction is a branch instruction, then an entry may be allocated in BIT301(block604). In various embodiments, Circuitry306may adjust pointer306to allow Branch instruction information308to be written in a particular entry of BIT301, such as, entry302, for example. The method may then depend on a prediction associated with the branch instruction (block605).

When a branch instruction is detected, a branch predictor, such as, e.g., Branch Predictor280, may generate a prediction as to whether the branch included in the instruction is taken or not taken. Based on the prediction, further instructions are fetched along the predicted program path. In the case when it is predicted that the branch will not be taken, the method may conclude in block605.

If, however, it is predicted that the branch will be taken, then an entry may be allocated in tBIT302(block606). Circuitry306may adjust pointer307to allow Branch instruction information308to be written into a particular entry of tBIT303, such as, entry304, for example. In various embodiments, branch history information may be stored in the particular entry of tBIT303. Additionally, an index indicating in which entry in tBIT303the branch history information is stored may be added to the corresponding entry in BIT301. It is noted that by storing branch history information in tBIT303for branch instructions that have been predicted to be taken, the size of BIT301may be reduced, saving area and power. Once the branch history information has been stored in tBIT303, then method may conclude in block607.

It is noted that the method depicted in the flow diagram ofFIG. 6is merely an example. In other embodiments, different operations and different orders of operations are possible and contemplated.

After information relating to a particular branch instruction has been stored in branch information tables, such as BIT301and tBIT302, the particular branch instruction may continue through the pipelines of the processor or processor core. Upon reaching an execution unit, such as, e.g., one of Execution units230as illustrated inFIG. 2, the particular branch instruction may be executed. Once the particular branch instruction has been executed, the accuracy of the prediction regarding whether the branch included in the instruction was to be taken or not taken, may be determined.

A flow diagram depicting an embodiment of a method for utilizing a BIU once a branch instruction has been executed is illustrated inFIG. 7. Referring collectively to the embodiment ofFIG. 3, and the flow diagram ofFIG. 7, the method begins in block701. A branch instruction may then be executed (block702). In various embodiments, a particular execution unit, such as, e.g., one of Execution units230, included within a processor or processor core may execute the branch instruction. The method may then depend on if the branch is taken or not taken (block703).

If the branch was actually taken, then the method may depend on if the branch was predicted as not taken (block707). If the branch was not predicted as not taken, then the method may conclude in block706. Alternatively, if the branch was predicted as being taken, then an entry will be allocated in tBIT303. As described above, the entry allocated in tBIT303may correspond to an existing entry in BIT301, and the existing entry in BIT301may be update with an index indicating the location of the newly allocated entry in tBIT303. Branch history information associated with the branch instruction may be stored in the newly allocated entry in tBIT303. In various embodiments, pointer307may be updated in order to store data in the entry in tBIT303. Once the data has been stored in tBIT303, the method may conclude in block706.

Alternatively, if the branch was not actually taken, the method may then depend on if the branch was predicted to be taken (block704). If the branch was predicted to not be taken, then the method may conclude in block706. If, however, the branch was predicted to be taken, then the front-end predictors may be restored using information in the BIU (block705). Information may be read from BIT301corresponding the executed branch instruction. In various embodiments, Circuitry305may maintain pointer306so that the entry corresponding to the executed branch instruction may be read. An index to a particular entry in tBIT303may be included in the information read from BIT301. The index may then be used to retrieve branch history information from tBIT303. Such information may be used by the instruction fetch unit and/or the branch prediction unit to reset fetching and prediction to the path not taken. Once the branch history information has been retrieved from tBIT303, the method may conclude in block706. In some embodiments, Circuitry305may maintain pointers for entries in both BIT301and tBIT303. In such cases, branch history information may be retrieved from both BIT301and tBIT303in parallel in order to reset fetching and prediction to the path not taken.

It is noted that the embodiment of the method depicted in the flow diagram ofFIG. 7is merely an example. In other embodiments, the operations may be performed in different orders than the order depicted in the flow diagram ofFIG. 7.