Apple Inc.

Niket K Choudhary

Pruthivi Vuyyuru

Ian D Kountanis

Muawya M Al-Otoom

Wei-Han Lien

Kulin N Kothari

Douglas C Holman

Ethan R Schuchman

Ilhyun Kim

Ronald P Hall

Richard F Russo

John D Pape

Deepankar Duggal

Debasish Chandra

Haoyan Jia

Mary Douglass Brown

Mridul Agarwal

Abhishek Kumar

Siavash Zangeneh Kamali

Madhu Sudan Hari

Madhu Sudan Har

Disclosed techniques relate to branch prediction and trace caching. A processor may include both an instruction cache and a trace cache configured to store instructions. A branch predictor may include one or more prediction tables (e.g., tagged geometric length (TAGE) tables) configured to predict directions of conditional control transfer instructions. Rather than including a separate branch predictor for branches in the trace cache, the processor may share the prediction table(s) for instruction cache and trace cache predictions. In particular, the processor may include an additional trace prediction lane configured to access the prediction table to predict a direction of a final control transfer instruction in a trace cached by the trace cache circuitry. This may advantageously provide accurate predictions with limited impacts to circuit area and power consumption, e.g., relative to a separate predictor for the trace cache.

Sharing branch predictor resource for instruction cache and trace cache predictions

Disclosed techniques relate to next fetch predictor circuitry configured to operate in conjunction with a trace cache. The trace cache circuitry may identify and store traces of instructions based on predicted directions of one or more control transfer instructions. Trace next fetch predictor circuitry may predict a next fetch address based on a current fetch address for a current cycle, which may include predicting a next fetch address following execution of a first trace stored in the trace cache circuitry. The first trace may include multiple fetch groups and multiple control transfer instructions. Arbitration circuitry may select from among multiple predictors and the trace next fetch predictor may have priority in response to a trace cache hit. Disclosed techniques may advantageously improve overall fetch bandwidth in the context of trace cache hits.

Next fetch predictor for trace cache

An apparatus includes an instruction cache circuit and an instruction fetch circuit. The instruction fetch circuit is configured to retrieve, from the instruction cache circuit, a fetch group that includes a plurality of instructions for execution by a processing circuit, and to make a determination that the fetch group includes a control transfer instruction that is predicted to be taken. A target address associated with the control transfer instruction is directed to an instruction within the fetch group. The instruction fetch circuit is further configured to, based on the determination, alter instructions within the fetch group in a manner that is based on a type of the control transfer instruction.

Using a next fetch predictor circuit with short branches and return fetch groups

Techniques are disclosed relating to predicting a next fetch address based on a current fetch address and history information. In some embodiments, tracking circuitry generates history information based on respective addresses corresponding to multiple control transfer instructions in a stream of executed instructions. Prediction circuitry may predict a next fetch address based on a current fetch address and the history information, including to: index into a first prediction table based on at least a portion of the current fetch address and at least a portion of the history information, compare tag data for an indexed location in the first prediction table with a tag that includes at least a portion of the current fetch address, and in response to a comparison hit in the first prediction table, provide a predicted next fetch address from the first prediction table.

Next fetch prediction using history

An apparatus includes a context identification circuit and a translation lookaside buffer (TLB) circuit. The context identification circuit may be configured to receive a context identifier assigned to a process being executed by a processor, and to assign a rename value to the context identifier that has fewer bits than the context identifier. The TLB circuit may be configured to receive a translation request for a virtual address that is associated with the process. The TLB circuit may be further configured to cache a translation of the virtual address to a corresponding physical address. The given entry may be tagged with a portion of the virtual address and the rename value. In response to a subsequent translation request for the virtual address, the TLB circuit may detect, using the portion of the virtual address and the rename value, a hit on the given entry of the TLB circuit.

Renaming context identifiers in a processor

Disclosed techniques relate to re-use of speculative results from an incorrect execution path. In some embodiments, when a first control transfer instruction is mispredicted, a second control transfer instruction may have been executed on the wrong path because of the misprediction. Result storage circuitry may record information indicating a determined direction for the second control transfer instruction. Control flow tracker circuitry may store, for the first control transfer instruction, information indicating a reconvergence point. Re-use control circuitry may track registers written by instructions prior to the reconvergence point, determine, based on the tracked registers, that the second control transfer instruction does not depend on data from any instruction between the first control transfer instruction and the reconvergence point, and use the recorded determined direction for the second control transfer instruction, notwithstanding the misprediction of the first control transfer instruction.

Re-use of speculative control transfer instruction results from wrong path

Disclosed techniques relate to trace caches. Trace cache circuitry may identify traces that satisfy one or more criteria. Generally, internal branches of a trace should satisfy a threshold bias level in a particular direction. To achieve this goal, the processor may initially assume that branches meet the threshold, track their usefulness in the trace context over time, and prevent inclusion of branches that fall below a usefulness threshold (which indicates that those branches are not sufficiently biased). Branches that do not meet the threshold may be added to a Bloom filter, for example. Usefulness may be tracked during trace training, when valid in a trace cache, or both.

Trace cache with filter for internal control transfer inclusion

A multi-degree branch predictor is disclosed. A processing circuit includes an instruction fetch circuit configured to fetch branch instructions, and a branch prediction circuit having a plurality of prediction subcircuits. The prediction subcircuits are configured to store different amounts of branch history data with respect to other ones, and to receive an indication of a given branch instruction in a particular clock cycle. The prediction subcircuits implement a common branch prediction scheme to output, in different clock cycles, corresponding predictions for the given branch instruction using the different amounts of branch history data and cause, instruction fetches to be performed by the instruction fetch circuit. The prediction subcircuits are also configured to override, in subsequent clock cycles, instruction fetches caused by prediction subcircuits with comparatively less branch history data based on contrary predictions performed in subsequent clock cycles by prediction subcircuits with more branch history data.

Multi-degree branch predictor

A system may include multiple processors. One of the processors may receive an indication of a data synchronization barrier (DSB) instruction in another processor that follows a translation look-ahead buffer invalidate (TLBI) instruction to invalidate an entry of a translation look-ahead buffer. The processor may determine whether instructions are pending in the processor for which the virtual addresses used for memory accesses have been translated to physical addresses before receiving the DSB indication. If there are such pending instructions, the processor may provide, after these instructions retire, an indication to the other processor as a response to the DSB indication.

Processing of data synchronization barrier instructions

Disclosed techniques relate to re-use of speculative results from an incorrect execution path. In some embodiments, when a control transfer instruction is mispredicted, a load instruction may have been executed on the wrong path. In disclosed embodiments, result storage circuitry records information that indicates destination registers of speculatively-executed load instructions including a first load instruction. Control flow tracker circuitry may store information indicating a reconvergence point for the control transfer instruction. Re-use control circuitry may track registers written by instructions prior to the reconvergence point, determine that the first load instruction does not depend on data from any instruction between the control transfer instruction and the reconvergence point, and use, as a result of the first load instruction, a value from a recorded destination register that was written based on speculative execution of the first load, notwithstanding the misprediction of the control transfer instruction.

Re-use of speculative load instruction results from wrong path

A processor may include a bias prediction circuit and an instruction prediction circuit to provide respective predictions for a conditional instruction. The bias prediction circuit may provide a bias prediction whether a condition of the conditional instruction is biased true or biased false. The instruction prediction circuit may provide an instruction prediction whether the condition of the conditional instruction is true of false. Responsive to a bias prediction that the condition of the conditional instruction is biased true or biased false, the processor may use the bias prediction from the bias prediction circuit to speculatively process the conditional instruction. Otherwise, the processor may use the instruction prediction from the instruction prediction circuit to speculatively process the conditional instruction.

Conditional instructions prediction

A processor may include an instruction distribution circuit and a plurality of execution pipelines. The instruction distribution circuit may distribute a conditional instruction to a first execution pipeline for execution when the conditional instruction is associated with a prediction of a high confidence level, or to a second execution pipeline for execution when the conditional instruction is associated with a prediction of a low confidence level. The second execution pipeline, not the first execution pipeline, may directly instruct the processor to obtain an instruction from a target address for execution, when the conditional instruction is mispredicted. Thus, when the conditional instruction is distributed to the first execution pipeline for execution and determined to be mispredicted, the first execution pipeline may cause the conditional instruction to be re-executed in the second execution pipeline to cause the instruction from the correct target address to be obtained for execution.

Growing community of inventors

Santa Clara, CA, United States of America

Niket K Choudhary