Advanced Micro Devices Corporation

Nexgen, Inc.

Larry Widigen

Korbin S Van Dyke

David L Puziol

Elliot A Sowadsky

Walstein Bennett Smith, Iii

Len Shar

William A Stutz

In a first aspect of the invention, branch prediction hardware, comprising logic and interconnect, is configurable via a control line to alter the manner in which the branch prediction is generated. The configuration can be done programmatically in software. Or, the configuration can be done by hardware in response to processor events. Such processor events include the loading of the CS register and changes in the instruction workload. In a second aspect of the invention, related to speculative execution, the directions of a plurality of branches are predicted based partly on resolved branch history information. Tentative branch history information is then stored for each of the predicted branches. When a predicted branch is resolved, the resolved branch history information is updated based on the stored tentative branch history information for the branch most recently resolved. Additionally, the predictions may be partly based on preceding unresolved branch predictions if any are outstanding. In a third aspect of the invention, Hit/Miss information from a Branch Prediction Cache (BPC) can optionally be used in formulating the next state value of an addressed two-bit counter stored in a correlation-based branch history table. Since a Miss in the BPC may indicate that this branch has not been encountered recently, whatever state currently exists can be optionally forced to a state that is based solely on whether the branch is resolved taken or not. This feature may be enabled and disabled under software control. In a fourth aspect of the invention, information from the instruction decoder is optionally used to override the correlation-based branch history table based prediction for select branch instructions. This feature may be enabled and disabled under software or hardware control.

Configurable branch prediction for a processor performing speculative execution

In a first aspect of the invention, branch prediction hardware, comprising logic and interconnect, is configurable via a control line to alter the manner in which the branch prediction is generated. The configuration can be done programmatically In software. Or, the configuration can be done by hardware in response to processor events. Such processor events include the loading of the CS register and changes in the instruction workload. In a second aspect of the invention, related to speculative execution, the directions of a plurality of branches are predicted based partly on resolved branch history information. Tentative branch history information is then stored for each of the predicted branches. When a predicted branch is resolved, the resolved branch history information is updated based on the stored tentative branch history information for the branch most recently resolved. Additionally, the predictions may be partly based on preceding unresolved branch predictions if any are outstanding. In a third aspect of the invention, Hit/Miss information from a Branch Prediction Cache (BPC) can optionally be used in formulating the next state value of an addressed two-bit counter stored in a correlation-based branch history table. Since a Miss in the BPC may indicate that this branch has not been encountered recently, whatever state currently exists can be optionally forced to a state that is based solely on whether the branch is resolved taken or not. This feature may be enabled and disabled under software control. In a fourth aspect of the invention, information from the instruction decoder is optionally used to override the correlation-based branch history table based prediction for select branch instructions. This feature may be enabled and disabled under software or hardware control.

In a first aspect of the invention, branch prediction hardware, comprising logic and interconnect, is configurable via a control line to alter the manner in which the branch prediction is generated. The configuration can be done programmatically in software. Or, the configuration can be done by hardware in response to processor events. Such processor events include the loading of the CS register and changes in the instruction workload. In a second aspect of the invention, related to speculative execution, the directions of a plurality of branches are predicted based partly on resolved branch history information. Tentative branch history information is then stored for each of the predicted branches. When a predicted branch is resolved, the resolved branch history information is updated based on the stored tentative branch history information for the branch most recently resolved. Additionally, the predictions may be partly based on preceding unresolved branch predictions if any are outstanding. In a third aspect of the invention, Hit/Miss Information from a Branch Prediction Cache (BPC) can optionally be used in formulating the next state value of an addressed two-bit counter stored in a correlation-based branch history table. Since a Miss in the BPC may indicate that this branch has not been encountered recently, whatever state currently exists can be optionally forced to a state that is based solely on whether the branch is resolved taken or not. This feature may be enabled and disabled under software control. In a fourth aspect of the invention, information from the instruction decoder is optionally used to override the correlation-based branch history table based prediction for select branch instructions. This feature may be enabled and disabled under software or hardware control.

The existing execution units of a high-performance processor are augmented by tile addition of a supplemental integer execution unit, termed the Add/Move Unit (AMU), which performs select adds and moves in parallel and out-of-order with respect to the other execution units. At small incremental cost, AMU enables better use of the expensive limited resources of an existing Address Preparation unit (AP), which handles linear and physical address generation for memory operand references, control transfers, and page crosses. AMU removes data dependencies and thereby increases the available instruction level parallelism. The increased instruction level parallelism is readily exploited by the processor's ability to perform out-of-order and speculative execution, and performance is enhanced as a result.

Pipeline throughput via parallel out-of-order execution of adds and moves in a supplemental integer execution unit

Configurable branch prediction for a processor performing speculative

A structure for, and a method of operating, a descriptor cache to store segment descriptors retrieved from memory. In one embodiment, the descriptor cache is direct-mapped and addressed by a first part of the physical address in memory at which a desired descriptor is stored. If the desired descriptor is not stored in the addressed entry of the descriptor cache then the descriptor is retrieved from a descriptor table held in memory and loaded into the addressed entry of the descriptor cache (which will then be able to satisfy future requests for the same descriptor). At the same time, a second part of the descriptor's physical address is loaded into an entry of a physical address cache corresponding to the addressed entry of the descriptor cache. Whenever a write to the memory occurs, the physical address cache receives the physical address written into and compares the contents of the entry of the physical address cache addressed by the first part of the physical address with the second part of the physical address. If a match occurs, the corresponding entry of the descriptor cache is modified to indicate invalidity. In this way, coherence between the descriptor tables held in memory (which may be modified) and the descriptor cache is maintained.

Segment descriptor cache addressed by part of the physical address of

A three-input comparator, where one of the inputs is an implicit constant, is formed with a special carry-save adder (CSA) followed by carry propagation circuitry. The special CSA uses two different bit cells depending upon whether that bit position in the constant input is a one or a zero. The three-input comparator can be modified to be a three-input adder by using a full carry-propagate adder (CPA). By taking into account a priori restrictions on the possible input operands, these arithmetic circuits are smaller and more efficient than conventional adders and comparators, which must be designed to deal with all possible input operands.

Optimized binary adder and comparator having an implicit constant for an

A structure for, and a method of operating, an operand cache to store operands retrieved from a memory. An instruction requiring an operand stored in the memory, is allowed to speculatively execute in an execution unit of a processor using an operand stored in an entry (corresponding to the address of the instruction) of the operand cache. When the actual operand is later retrieved from the memory it is compared to the cached operand used for speculative execution. If the cached and actual operands are unequal then the speculatively executed instruction and all subsequent instructions are aborted and the processor resumes execution at the address of the instruction that was speculatively executed.

Operand cache addressed by the instruction address for reducing latency

Dedicated parallel comparators perform expand up or expand down segment limit checks for memory accesses. A first three-input comparator has as inputs the complement of the segment limit, the effective address of the first byte of the access, and an configurable third input. For expand up segments, the configurable third input is set to one less than the memory access size. A carry out of the first comparator is generated, and thereby a limit fault indicated, if the address of the last byte of the access exceeds the segment limit. For expand down segments, the configurable third input is set to zero. In this case, the lack of a carry out of the first comparator indicates that the address of the first byte of the access exceeds the segment limit. For expand down segments a parallel second two-input comparator is also used. The second comparator has as inputs the effective address and a hybrid second input. A least significant portion of the hybrid input is set to one less than the memory access size. Multiple bits in a most significant portion of the hybrid input reflect the complement of the segment descriptor's B-bit. The second comparator generates a carry whenever the address of the last byte of the memory access wraps the segment's maximum address value. For expand down segments, a limit fault is indicated by the logical OR of the complement of the first comparator's carry out with the carry out of the second comparator.

Apparatus and method for determining if an operand lies within an expand

The existing execution units of a high-performance processor are augmented by the addition of a supplemental integer execution unit, termed the Add/Move Unit (AMU), which performs select adds and moves in parallel and out-of-order with respect to the other execution units. At small incremental cost, AMU enables better use of the expensive limited resources of an existing Address Preparation unit (AP), which handles linear and physical address generation for memory operand references, control transfers, and page crosses. AMU removes data dependencies and thereby increases the available instruction level parallelism. The increased instruction level parallelism is readily exploited by the processor's ability to perform out-of-order and speculative execution, and performance is enhanced as a result.

Pipeline throughput via parallel out-of-order execution of adds and

A first two-input adder computes the sum of one wider and one narrower input by combining a conventional adder for the low-order bits with an incrementer and selection logic for the high-order bits. A second three-input adder computes the sum of one wider and two narrower inputs in a similar way: the low-order bits are computed with a conventional carry save adder (CSA) followed by a carry propagate adder (CPA), while the high-order bits are computed with an incrementer and selection logic. The first and second circuits are combined to form a third arithmetic circuit that takes four input operands, the first of which is wider than the other three, and speculatively computes two results: (1) the sum of the first and second input operands; and (2) the sum of the first, third, and fourth input operands. This combined circuit contains all of the elements of the first two circuits, but shares a single incrementer. A degenerate case of the third circuit occurs when the second and third inputs are common. This degenerate case has particular application to superscalar instruction pointer updates for variable length instructions. By taking into account a priori restrictions on the possible input operands, these circuits are smaller and more efficient than conventional adders and comparators, which must be designed to deal with all possible input operands.

Optimized binary adders and comparators for inputs having different

Processor having primary integer execution unit and supplemental integer

A Branch Prediction Cache (BPC) selects from among multiple branch address entries for a single return-type instruction that returns to multiple callers. The BPC has a branch address associative memory, a return address associative memory, and word line logic used to validate and qualify entries. The branch address associative memory monitors program addresses for previously stored branch addresses. The return address stack (RtnStack) stores the return addresses for the most recent call-type instructions. The top of the stack is input to the return address associative memory. When a program address has multiple matches in the branch address associative memory, the return address associative memory enables only the entry that has an associated return address matching the top of the RtnStack. In an alternate embodiment, the return address associative memory is combined with a branch address cache and target address associative memory.

Branch prediction cache with multiple entries for returns having

An execution unit performs multiple sequential instruction pointer updates and segment limit checks within a cycle. The updates and checks are carried out in a high-performance pipelined processor that speculatively executes variable length instructions. A disclosed embodiment of the execution unit includes Next EIP (Extended Instruction Pointer) selection logic, Current EIP selection logic, an EIP History RAM, a Dual EIP Adder, a CS Limit check adder, limit checking combinational logic, and a limit fault History RAM.

Growing community of inventors

Salinas, CA, United States of America

Larry Widigen