US 5,875,324 AGrant

Superscalar Microprocessor Which Delays Update of Branch Prediction Information in Response to Branch Misprediction Until a Subsequent Idle Clock

Issue Date:1999-02-23

•26 Claims

•40 Drawing Sheets

Abstract

A superscalar microprocessor employing a branch prediction array update unit is provided. The branch prediction array update unit collects the update prediction information for each branch misprediction or external fetch. When a fetch address is presented for branch prediction, the fetch address is compared to the update address stored in the update unit. If the addresses match, then the update prediction information is forwarded as the output of the array. If the addresses do not match, then the information stored in the indexed storage location is forwarded as the output of the array. When the next external fetch begins or misprediction is detected, the update is written into the branch prediction array. The update unit allows for a single-ported array implementation of the branch prediction array while still maintaining the operational aspects of the dual-ported array implementation, as well as allowing for speculative branch prediction update.

Metadata

Assignee

Advanced Micro Devices, Inc.

Inventors

Thang M. Tran
David B. Witt

Application Information

Application Number:US 9472258

Filing Date:1997-10-08

Priority Date:1995-06-07

Art Unit:274

Classifications

IPC:

G06F 938

Field of Search:

395585;582;584;586;587

Patent Drawings (40 sheets)

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to the field of superscalar microprocessors, and more particularly to array updates in superscalar microprocessors.

2. Description of the Relevant Art

Integrated circuits are groups of transistors employed on a single monolithic substrate. The groups of transistors embody various functions for a system (for example, a computer system). One particular example of an integrated circuit is a superscalar microprocessor which embodies multiple instruction processing pipelines. Integrated circuits typically have a clock input associated with them, which defines a "clock cycle". A clock cycle is an interval of time in which the functions embodied on the integrated circuit complete a portion of their tasks (a "subfunction"). At the end of a clock cycle, the results are moved to the next function or subfunction which operates on the value.

Integrated circuits may employ arrays for storing information useful to the embodied functions. For example, data and instruction caches are arrays that are commonly employed within superscalar microprocessors. As used herein, the term "array" means a plurality of storage locations configured into a structure from which the values stored in one or more of the plurality of storage locations may be selected for manipulation. Arrays are configured with one or more input ports which allow functions to access information stored in the array. Each input port may be associated with an output port. A particular input port may allow read access, write access, or read/write access to storage locations within the array and is referred to as a read port, a write port, or a read/write port, respectively. A read access is an access in which the value in the selected storage location is transferred to the associated output port and the storage location is left unchanged. A write access is an access in which the value in the selected storage location is changed to a value provided with the input port. A port which allows read/write access allows either a read or a write access to occur. Ports which allow write accesses typically are associated with a write data input port. The write data input port conveys the data to be stored at the address provided on the write port.

"Indexes" are often used to select a storage location within an array. An index is a value which indicates which of the plurality of storage locations of an array that a particular access intends to manipulate. The act of selecting one of a plurality of storage locations according to an index is called "indexing". In one particular example, a set associative cache has an index which identifies which group of sets to access and a "way value" which selects one of the sets within the selected group for manipulation.

In many cases, more than one access to an array in a given clock cycle may be desirable for the functions an integrated circuit embodies. An array which allows two accesses per clock cycle is referred to as "dual-ported". Each port may allow a read access, a write access, or a read/write access. Unfortunately, dual-ported arrays are much larger than single ported arrays, often occupying more than double the silicon area of a single ported array which stores the same amount of information.

One particularly useful dual-ported array is an array in which one port allows a read access while a second (write) port updates a storage location with new information. Arrays that are configured in this way do not block a read access with an update, which simplifies array control logic and may improve performance. An example of an array configured with a read port and a write port for updates is a branch prediction array associated with a branch prediction unit of a superscalar microprocessor. The branch prediction array stores information related to past branch predictions. A fetch address is used to index into the branch prediction array, and the information read from the array is used to create a branch prediction associated with the instructions residing at the fetch address. When a branch instruction is mispredicted, then the correct address is fetched and new prediction information is calculated. The new prediction information should be stored into the branch prediction array in a storage location indexed by the address of the mispredicted branch instruction. Then, the next time the branch instruction is fetched, a correct prediction may be made. The new prediction information is available to update the branch prediction array in the clock cycle following the cycle in which the correct address is fetched. However, the clock cycle that the update is available is also a clock cycle in which a fetch address is presented to the branch prediction unit. Therefore, a read port for the fetch address and a write port for the update would be useful for the branch prediction array, but the silicon area cost for the dual-ported array is relatively large. A mechanism which achieves the effects of a dual-ported array with a read port and a write port without the associated silicon area penalty is desired.

SUMMARY OF THE INVENTION

The problems outlined above are in large part solved by a superscalar microprocessor employing a branch prediction array update unit. The branch prediction array update unit collects the update prediction information for each branch misprediction or external fetch. When a fetch address is presented for branch prediction, the fetch address is compared to the update address stored in the update unit. If the addresses match, then the update prediction information is forwarded as the output of the array. If the addresses do not match, then the information stored in the indexed storage location is forwarded as the output of the array. When the next external fetch begins or misprediction is detected, the update is written into the branch prediction array. In this manner, the update appears to have occurred when the update information is collected, as is the case with a dual-ported array. However, the second port may be eliminated.

The branch prediction array update unit further allows a microprocessor to update branch prediction information speculatively. This functionality is desirable because modern microprocessors allow out-of-order execution of instructions, including branch instructions. Out-of-order instructions are generally executed speculatively, meaning that the instruction execution is not known to be needed by the sequential execution of the program. An instruction may be executed speculatively, for example, if it is on the path that is the target of a predicted branch instruction which has not yet executed. An instruction becomes non-speculative when each instruction previous to it is guaranteed to execute, and therefore that instruction is guaranteed to execute. If updates were written directly into the array, then speculatively updating the branch prediction information would skew the information with incorrect data. Correct prediction rates might suffer. However, by placing the update information in the update unit, a speculative update may occur. If the next branch misprediction is for a branch instruction that is prior to the branch instruction associated with the current update information, the current update information is discarded instead of being written into the branch prediction array. Performance may be increased by advantageously updating branch prediction information speculatively but being able to discard the information if the branch is not to be executed.

BRIEF DESCRIPTION OF THE DRAWINGS

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:

FIG. 1 is a block diagram of a superscalar microprocessor embodying the present invention in a branch prediction unit.

FIG. 2 is a diagram of an instruction cache and the branch prediction unit of FIG. 1, depicting one embodiment of the present invention.

FIG. 3 is a timing diagram showing one set of events occurring with respect to the embodiment shown in FIG. 2, illustrating the delayed update mechanism for the branch prediction array for two consecutive mispredicted branches.

FIG. 4 is a timing diagram showing another set of events occurring with respect to the embodiment shown in FIG. 2, illustrating the delayed update mechanism for a mispredicted branch followed by an instruction cache miss.

FIG. 5 is a block diagram of a superscalar microprocessor.

FIG. 6 is a block diagram of a pipeline for calculating addresses within processor 500.

FIG. 7 shows a programmer's view of the x86 register file.

FIG. 8 is a timing diagram which shows fetching, scanning, aligning, decoding, and muxing of instructions in microprocessor 500.

FIG. 9 is a block diagram which illustrates a portion of an exemplary embodiment of processor 500.

FIG. 10 is a block diagram of a portion of the instruction cache shown in FIG. 5.

FIG. 11 is a block diagram illustrating routing of instructions starting at various byte positions to various decode units.

FIG. 12 is a block diagram of an exemplary layout for the ICTAGV.

FIG. 13 is a block diagram of one embodiment of ICNXTBLK.

FIG. 14 is a block diagram of a global branch predictor.

FIG. 15 illustrates processor 500 pipeline execution cycles with a branch misprediction detected.

FIG. 16 is a block diagram of an exemplary layout for ICNXTBLK.

FIG. 17 is a timing diagram illustrating branch misprediction.

FIG. 18 is a block diagram of a return stack.

FIG. 19 is a block diagram of a predecode unit.

FIG. 20 is a timing diagram illustrating fetching, scanning, and aligning of instructions in processor 500.

FIG. 21 is a block diagram illustrating alignment, early decode, and decode blocks.

FIG. 22 is a block diagram illustrating exemplary hardware for early decoding of prefixes and opcodes.

FIG. 23 is a block diagram of logic for forming OPBYTE signals.

FIG. 24 is a block diagram illustrating MROM register decoding.

FIG. 25 is a block diagram illustrating multiplexing of 2-dispatch position instructions.

FIG. 26 shows an embodiment of the ICCNTL state machine.

FIG. 27 is a block diagram illustrating an exemplary layout of ICACHE arrays.

FIG. 28 is a block diagram of an exemplary ICDECODE layout.

FIG. 29 is a block diagram of exemplary reservation station logic.

FIG. 30 is a timing diagram for one embodiment of the reservation stations.

FIG. 31 is a block diagram of one embodiment of a functional unit.

FIG. 32 is a more detailed block diagram of one embodiment of a functional unit.

FIG. 33 is a block diagram of an exemplary reorder buffer.

FIG. 34 is a block diagram of an exemplary layout for a reorder buffer.

FIG. 35 is a block diagram illustrating dependency checking in one embodiment of a reorder buffer.

FIG. 36 is a block diagram of another exemplary layout for the reorder buffer.

FIG. 37 is a timing diagram for an exemplary register file.

FIG. 38 is a block diagram of one embodiment of a register file.

FIG. 39 is a block diagram of one embodiment of a load/store unit.

FIG. 40 is a block diagram illustrating an exemplary common load/store buffer.

FIG. 41 illustrates an exemplary load/store buffer entry.

FIG. 42 is a timing diagram illustrating update of the common load/store buffer.

FIG. 43 is an exemplary timing diagram for aligned load/store data cache accesses.

FIG. 44 is an exemplary timing diagram for dependency checking in the load/store unit.

FIG. 45 is a block diagram illustrating dependency checking according to one embodiment of the load/store unit.

FIG. 46 is a block diagram illustrating segment calculations according to one embodiment of the load/store unit.

FIG. 47 is a timing diagram illustrating limit/protection checks according to one embodiment of the load/store unit.

FIG. 48 is a block diagram of one embodiment of a special register block.

FIG. 49 is a block diagram of one embodiment of protection checking hardware.

FIG. 50 is a block diagram illustrating an exemplary load/store unit partitioning.

FIG. 51 is a block diagram illustrating a layout of the exemplary load/store unit with respect to other units.

FIG. 52 is a block diagram of one embodiment of the data cache.

FIG. 53 is a block diagram of one embodiment of a tag array entry.

FIG. 54 is a block diagram of one embodiment of a way prediction entry.

FIG. 55 is a timing diagram for dcache load accesses according to one embodiment of the data cache.

FIG. 56 is a block diagram showing exemplary hardware for performing aligned loads.

FIG. 57 is a timing diagram for dcache store accesses according to one embodiment of the data cache.

FIG. 58 is a timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 59 is a second timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 60 is a third timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 61 is a fourth timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 62 is a timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 63 is a second timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 64 is a third timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 65 is a timing diagram for processing a load miss according to one embodiment of the data cache.

FIG. 66 is a timing diagram for data cache reloads according to one embodiment of the data cache.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE INVENTION

Turning now to FIG. 1, a block diagram of a superscalar microprocessor 200 including a branch prediction unit 220 in accordance with the present invention is shown. As illustrated in the embodiment of FIG. 1, superscalar microprocessor 200 includes a prefetch/predecode unit 202 and a branch prediction unit 220 coupled to an instruction cache 204. Instruction alignment unit 206 is coupled between instruction cache 204 and a plurality of decode units 208A-208F (referred to collectively as decode units 208). Each decode unit 208A-208F is coupled to respective reservation station units 210A-210F (referred to collectively as reservation stations 210), and each reservation station 210A-210F is coupled to a respective functional unit 212A-212F (referred to collectively as functional units 212). Decode units 208, reservation stations 210, and functional units 212 are further coupled to a reorder buffer 216, a register file 218 and a load/store unit 222. A data cache 224 is finally shown coupled to load/store unit 222, and an MROM (Microcode Read-only Memory or ROM) unit 209 is shown coupled to instruction alignment unit 206.

Generally speaking, instruction cache 204 is a high speed cache memory provided to temporarily store instructions prior to their dispatch to decode units 208. In one embodiment, instruction cache 204 is configured to cache up to 32 kilobytes of instruction code organized in lines of 16 bytes each (where each byte consists of 8 bits). During operation, instruction code is provided to instruction cache 204 by prefetching code from a main memory (not shown) through prefetch/predecode unit 202. It is noted that instruction cache 204 could be implemented in a set-associative, a fully-associative, or a direct-mapped configuration.

Prefetch/predecode unit 202 is provided to prefetch instruction code from the main memory for storage within instruction cache 204. In one embodiment, prefetch/predecode unit 202 is configured to burst 64-bit wide code from the main memory into instruction cache 204. It is understood that a variety of specific code prefetching techniques and algorithms may be employed by prefetch/predecode unit 202.

As prefetch/predecode unit 202 fetches instructions from the main memory, it generates three predecode bits associated with each byte of instruction code: a start bit, an end bit, and a "functional" bit. The predecode bits form tags indicative of the boundaries of each instruction. The predecode tags may also convey additional information such as whether a given instruction can be decoded directly by decode units 208 or whether the instruction must be executed by invoking a microcode procedure controlled by MROM unit 209, as will be described in greater detail below.

Table 1 indicates one encoding of the predecode tags. As indicated within the table, if a given byte is the first byte of an instruction, the start bit for that byte is set. If the byte is the last byte of an instruction, the end bit for that byte is set. If a particular instruction cannot be directly decoded by the decode units 208, the functional bit associated with the first byte of the instruction is set. On the other hand, if the instruction can be directly decoded by the decode units 208, the functional bit associated with the first byte of the instruction is cleared. The functional bit for the second byte of a particular instruction is cleared if the opcode is the first byte, and is set if the opcode is the second byte. It is noted that in situations where the opcode is the second byte, the first byte is a prefix byte. The functional bit values for instruction byte numbers 3-8 indicate whether the byte is a MODRM or an SIB byte, or whether the byte contains displacement or immediate data.

As stated previously, in one embodiment certain instructions within the x86 instruction set may be directly decoded by decode unit 208. These instructions are referred to as "fast path" instructions. The remaining instructions of the x86 instruction set are referred to as "MROM instructions". MROM instructions are executed by invoking MROM unit 209. More specifically, when an MROM instruction is encountered, MROM unit 209 parses and serializes the instruction into a subset of defined fast path instructions to effectuate a desired operation. A listing of exemplary x86 instructions categorized as fast path instructions as well as a description of the manner of handling both fast path and MROM instructions will be provided further below.

Instruction alignment unit 206 is provided to channel variable byte length instructions from instruction cache 204 to fixed issue positions formed by decode units 208A-208F. Instruction alignment unit 206 independently and in parallel selects instructions from three groups of instruction bytes provided by instruction cache 204 and arranges these bytes into three groups of preliminary issue positions. Each group of issue positions is associated with one of the three groups of instruction bytes. The preliminary issue positions are then merged together to form the final issue positions, each of which is coupled to one of decode units 208.

Before proceeding with a detailed description of the branch prediction array update mechanism within branch prediction unit 220, general aspects regarding other subsystems employed within the exemplary superscalar microprocessor 200 of FIG. 1 will be described. For the embodiment of FIG. 1, each of the decode units 208 includes decoding circuitry for decoding the predetermined fast path instructions referred to above. In addition, each decode unit 208A-208F routes displacement and immediate data to a corresponding reservation station unit 210A-210F. Output signals from the decode units 208 include bit-encoded execution instructions for the functional units 212 as well as operand address information, immediate data and/or displacement data.

The superscalar microprocessor of FIG. 1 supports out of order execution, and thus employs reorder buffer 216 to keep track of the original program sequence for register read and write operations, to implement register renaming, to allow for speculative instruction execution and branch misprediction recovery, and to facilitate precise exceptions. As will be appreciated by those of skill in the art, a temporary storage location within reorder buffer 216 is reserved upon decode of an instruction that involves the update of a register to thereby store speculative register states. Reorder buffer 216 may be implemented in a first-in-first-out configuration wherein speculative results move to the "bottom" of the buffer as they are validated and written to the register file, thus making room for new entries at the "top" of the buffer. Other specific configurations of reorder buffer 216 are also possible, as will be described further below. If a branch prediction is incorrect, the results of speculatively-executed instructions along the mispredicted path can be invalidated in the buffer before they are written to register file 218.

The bit-encoded execution instructions and immediate data provided at the outputs of decode units 208A-208F are routed directly to respective reservation station units 210A-210F. In one embodiment, each reservation station unit 210A-210F is capable of holding instruction information (i.e., bit encoded execution bits as well as operand values, operand tags and/or immediate data) for up to three pending instructions awaiting issue to the corresponding functional unit. It is noted that for the embodiment of FIG. 1, each decode unit 208A-208F is associated with a dedicated reservation station unit 210A-210F, and that each reservation station unit 210A-210F is similarly associated with a dedicated functional unit 212A-212F. Accordingly, six dedicated "issue positions" are formed by decode units 208, reservation station units 210 and functional units 212. Instructions aligned and dispatched to issue position 0 through decode unit 208A are passed to reservation station unit 210A and subsequently to functional unit 212A for execution. Similarly, instructions aligned and dispatched to decode unit 208B are passed to reservation station unit 210B and into functional unit 212B, and so on.

Upon decode of a particular instruction, if a required operand is a register location, register address information is routed to reorder buffer 216 and register file 218 simultaneously. Those of skill in the art will appreciate that the x86 register file includes eight 32 bit real registers (i.e., typically referred to as EAX, EBX, ECX, EDX, EBP, ESI, EDI and ESP). Reorder buffer 216 contains temporary storage locations for results which change the contents of these registers to thereby allow out of order execution. A temporary storage location of reorder buffer 216 is reserved for each instruction which, upon decode, is determined to modify the contents of one of the real registers. Therefore, at various points during execution of a particular program, reorder buffer 216 may have one or more locations which contain the speculatively executed contents of a given register. If following decode of a given instruction it is determined that reorder buffer 216 has a previous location or locations assigned to a register used as an operand in the given instruction, the reorder buffer 216 forwards to the corresponding reservation station either: 1) the value in the most recently assigned location, or 2) a tag for the most recently assigned location if the value has not yet been produced by the functional unit that will eventually execute the previous instruction. If the reorder buffer has a location reserved for a given register, the operand value (or tag) is provided from reorder buffer 216 rather than from register file 218. If there is no location reserved for a required register in reorder buffer 216, the value is taken directly from register file 218. If the operand corresponds to a memory location, the operand value is provided to the reservation station unit through load/store unit 222.

Details regarding suitable reorder buffer implementations may be found within the publication "Superscalar Microprocessor Design" by Mike Johnson, Prentice-Hall, Englewood Cliffs, N.J., 1991, and within the co-pending, commonly assigned patent application entitled "High Performance Superscalar Microprocessor", Ser. No. 08/146,382, filed Oct. 29, 1993 by Witt, et al. now abandoned. These documents are incorporated herein by reference in their entirety.

Reservation station units 210A-210F are provided to temporarily store instruction information to be speculatively executed by the corresponding functional units 212A-212F. As stated previously, each reservation station unit 210A-210F may store instruction information for up to three pending instructions. Each of the six reservation stations 210A-210F contain locations to store bit-encoded execution instructions to be speculatively executed by the corresponding functional unit and the values of operands. If a particular operand is not available, a tag for that operand is provided from reorder buffer 216 and is stored within the corresponding reservation station until the result has been generated (i.e., by completion of the execution of a previous instruction). It is noted that when an instruction is executed by one of the functional units 212A-212F, the result of that instruction is passed directly to any reservation station units 210A-210F that are waiting for that result at the same time the result is passed to update reorder buffer 216 (this technique is commonly referred to as "result forwarding"). Instructions are issued to functional units for execution after the values of any required operand(s) are made available. That is, if an operand associated with a pending instruction within one of the reservation station units 210A-210F has been tagged with a location of a previous result value within reorder buffer 216 which corresponds to an instruction which modifies the required operand, the instruction is not issued to the corresponding functional unit 212 until the operand result for the previous instruction has been obtained. Accordingly, the order in which instructions are executed may not be the same as the order of the original program instruction sequence. Reorder buffer 216 ensures that data coherency is maintained in situations where read-after-write dependencies occur.

In one embodiment, each of the functional units 212 is configured to perform integer arithmetic operations of addition and subtraction, as well as shifts, rotates, logical operations, and branch operations. It is noted that a floating point unit (not shown) may also be employed to accommodate floating point operations.

Each of the functional units 212 also provides information regarding the execution of conditional branch instructions to the branch prediction unit 220. If a branch prediction was incorrect, branch prediction unit 220 flushes instructions subsequent to the mispredicted branch that have entered the instruction processing pipeline, and causes prefetch/predecode unit 202 to fetch the required instructions from instruction cache 204 or main memory. It is noted that in such situations, results of instructions in the original program sequence which occur after the mispredicted branch instruction are discarded, including those which were speculatively executed and temporarily stored in load/store unit 222 and reorder buffer 216. Exemplary configurations of suitable branch prediction mechanisms are well known.

Results produced by functional units 212 are sent to the reorder buffer 216 if a register value is being updated, and to the load/store unit 222 if the contents of a memory location is changed. If the result is to be stored in a register, the reorder buffer 216 stores the result in the location reserved for the value of the register when the instruction was decoded. As stated previously, results are also broadcast to reservation station units 210A-210F where pending instructions may be waiting for the results of previous instruction executions to obtain the required operand values.

Generally speaking, load/store unit 222 provides an interface between functional units 212A-212F and data cache 224. In one embodiment, load/store unit 222 is configured with a load/store buffer with eight storage locations for data and address information for pending loads or stores. Decode units 208 arbitrate for access to the load/store unit 222. When the buffer is full, a decode unit must wait until the load/store unit 222 has room for the pending load or store request information. The load/store unit 222 also performs dependency checking for load instructions against pending store instructions to ensure that data coherency is maintained.

Data cache 224 is a high speed cache memory provided to temporarily store data being transferred between load/store unit 222 and the main memory subsystem. In one embodiment, data cache 224 has a capacity of storing up to eight kilobytes of data. It is understood that data cache 224 may be implemented in a variety of specific memory configurations, including a set associative configuration.

Turning now to FIG. 2, a diagram of instruction cache 204 and branch prediction unit 220 is shown. Instruction cache 204 includes a branch holding register 250, a current fetch PC register 251, and an instruction cache storage array 252. Current fetch PC register 251 contains the current fetch address and indexes into instruction storage array 252 to fetch instructions. Both fetch PC register 251 and branch holding register 250 are coupled to a comparator 253 and an input multiplexor 254 within branch prediction unit 220. Input multiplexor 254 is coupled to a read/write input port of a branch prediction array 255. Coupled to a write data port of branch prediction array 255 is branch update data register 256. Both the output of branch prediction array 255 and branch update data register 256 are coupled to an output multiplexor 257 which receives its select line from comparator 253. Output multiplexor 257 is coupled to a branch prediction logic block 258, which manipulates the data transferred by output multiplexor 257 and produces a branch prediction which is conveyed to instruction cache 204 on a branch prediction bus 259. Therefore, the output of multiplexor 257 is considered to be the output of branch prediction array 255. Instruction cache 204 stores the address conveyed on branch prediction bus 259 in the current fetch PC register unless a branch misprediction or exception is indicated by reorder buffer 216.

Generally speaking, branch holding register 250, branch update data register 256, input multiplexor 254 and output multiplexor 257 provide a mechanism by which a delayed update of branch prediction array 255 may be made. The address of the branch instruction which was mispredicted is stored in branch holding register 250, and the associated branch prediction data is stored in branch update data register 256. Input multiplexor 254 is an input selection device for branch prediction array 255, and is used to select the current fetch PC address for branch prediction processing or the branch holding register to provide the update to branch prediction array 255. Therefore, the current fetch PC address is selected for reading only and the branch holding register is selecting for writing only. In this way, branch prediction array 255 may be single ported while still effectively providing the simultaneous read and update function of the dual-ported array. Instead of performing the update immediately, the update is delayed until a cycle in which the current fetch PC register is invalid. However, the update information is made visible via comparator 253 and output multiplexor 257. Comparator 253 compares the addresses stored in current fetch PC register 251 and branch holding register 250. Output multiplexor 257 is an output selection device which selects the output of branch prediction array 255 if comparator 253 indicates not equal and selects the branch update data register if comparator 253 indicates equal. Therefore, if the branch instruction whose correct prediction information is held in branch update data register 256 is refetched before the update is written to branch prediction array 255, the correct prediction information will be processed.

As mentioned above, branch holding register 250 stores the address of the last mispredicted branch instruction until an opportunity to update branch prediction array 255 occurs. Branch update data register 256 stores the branch prediction data associated with the address stored in branch holding register 250. Together, branch update data register 256 and branch holding register 250 form an update storage device that allows a branch prediction update to be stored until a convenient clock cycle in which to perform the update to branch prediction array 255. In one embodiment, an update occurs the clock cycle following another mispredicted branch detection by reorder buffer 216 and the clock cycle when an external instruction fetch is started in response to an instruction cache miss. Instruction cache 204 detects such clock cycles and causes an update select line 260 to convey a signal to input multiplexor 254 indicating that branch holding register 250 should be selected to access branch prediction array 255. In clock cycles in which the above mentioned events are not detected, the current fetch PC is selected to access branch prediction array 255 such that branch predictions are provided for each instruction fetch.

The clock cycle following a branch misprediction detection by reorder buffer 216 is a clock cycle in which the current fetch PC is invalid because the corrected address provided by reorder buffer 216 (or one of functional units 212) is a logical address. The logical address is converted to a linear address before accessing instruction cache 204. As will be appreciated by those skilled in the art, branch instruction execution in the x86 architecture produces a logical (or virtual) address. The logical address is translated first to a linear address and then to a physical address as detailed in the publication "Programming the 80386" by John H. Crawford, et al, Sybex, Inc. San Francisco, Calif., 1987. This publication is incorporated herein by reference in its entirety. In an embodiment of microprocessor 200, instruction cache 204 stores instructions based on their linear address. Therefore, the update occurs during a clock cycle in which current fetch PC register 251 cannot access branch prediction array 255, and so the update is performed with no performance penalty.

Similarly, when an external fetch is started, the current fetch PC contains an address that need not access the branch prediction array. The instructions associated with the current fetch PC address will not be available until they are returned from external memory, typically at least several clock cycles. The branch prediction information will be determined from the instructions fetched, and so branch prediction array 255 need not be accessed. Therefore, the update occurs during a clock cycle in which current fetch PC register 251 does not need access to branch prediction array 255. Branch holding register 250 and branch update data register 256 are also used to hold predecoded branch prediction information produced by prefetch/predecode unit 202 when instructions are being fetched into instruction cache 204 from main memory. The update to branch prediction array 255 when an external fetch is started allows prefetch/predecode unit 202 access to branch holding register 250 and branch update data register 256.

In one embodiment, branch update data register 256 stores the successor index, branch counters, the byte position within the cache line of the branch instruction, and a way value associated with the branch address in branch holding register 250. The successor index includes the index bits for instruction cache 204 of the branch prediction for the branch instruction. The branch counters are counters associated with the branch prediction mechanisms employed by microprocessor 200. Any suitable branch prediction mechanism may be employed, and various branch prediction mechanisms are well-known. The way value recorded is the way of instruction cache 204 in which the corrected fetch address is stored.

Branch prediction array 255 is, in one embodiment, a linear array of storage locations which store the information stored in branch update data register 256. In one embodiment, two fields of data in the form stored in branch update data register 256 are stored and branch prediction array 255 is configured with 2048 entries. Branch prediction logic block 258 chooses one of the two fields from an indexed storage location according to the branch prediction mechanism implemented by microprocessor 200. When updating branch prediction array 255, one of the two fields stored in a the storage location indexed by the branch instruction address is replaced by the update information. If the update is due to a misprediction with respect to an address stored within branch prediction array 255, then the mispredicted address is updated with the corrected prediction information. If the branch was not detected at prediction time or was predicted not taken, then the field that predicts a non-taken branch is replaced by the new information. A bit for each field is sent along with the predicted branch instruction and returned by reorder buffer 216 along with the misprediction indication and corrected fetch address. The bit indicates when set that the corresponding field predicts a taken branch. The bit indicates when cleared that the corresponding field predicts a non-taken branch. This information is used to select a non-taken branch for replacement with the new information. If both addresses stored in a particular entry are predicted taken, then a pseudo-random selection policy is used for the replacement. In one embodiment, the pseudo-random policy is to select an entry to replace based on the least significant bit of the corrected fetch address. If the bit is set, the second entry is replaced. If the bit is clear, the first entry is replaced.

It is noted that the branch holding register and branch update data may be used to allow out of order update of branch prediction information without disturbing the contents of the branch prediction array. If a branch instruction is executed speculatively and mispredicted, it may be written into the branch prediction register and the branch update data register. On the next misprediction, the new misprediction is checked to see if it is prior to the speculatively stored misprediction. If the new misprediction is prior to the speculative misprediction, the branch holding register and branch update data register are invalidated and not written into the branch prediction array. Instead, the new misprediction data overwrites the previously stored misprediction data. If the new misprediction is not prior to the speculative misprediction, the speculative misprediction data is correct and the new misprediction information is not written into the branch holding register at this time. Speculative misprediction results are held in the branch holding register until they are indicated to be non-speculative by reorder buffer 216. Then they may be written into the branch prediction array at the next misprediction or external fetch.

It is further noted that the information stored in branch update data register 256 may vary from embodiment to embodiment, as may the information stored in branch prediction array 255 and the size of branch prediction array 255. It is also noted that, although the input selection device is represented by input multiplexor 254, the input selection device may vary from embodiment to embodiment. Specifically, multiple multiplexor devices may form the input selection device. Similarly, the output selection device may vary from embodiment to embodiment.

Turning now to FIG. 3, a timing diagram illustrates the clock cycles during which branch prediction array 255, branch holding register 250, and branch update data register 256 are updated for the case of two consecutive mispredicted branches. In ICLK1, branch holding register 250 contains an address A as shown in block 300, and branch update data register 256 contains the update data associated with address A. Address A is a misprediction or external fetch address detected in a clock cycle prior to ICLK1. In ICLK1, reorder buffer 216 indicates that a misprediction has been detected, as shown in block 301. The corrected fetch address associated with the mispredicted branch instruction is conveyed to instruction cache 204. In ICLK2, a signal on update select line 260 indicates that the branch history register should be selected by input multiplexor 254. While the instruction cache translates the logical corrected address to a linear address (as indicated by block 302 in FIG. 3), address A and its associated branch prediction information are written into branch prediction array 255 (as indicated by block 303 where "BPA" is an abbreviation for branch prediction array). In ICLK3, the corrected address has been translated to a linear address and accesses instruction cache 204 and branch prediction array 255, as indicated by block 305. The way value of instruction cache 204 storing the instructions associated with the corrected address is stored in branch update data register 256. In ICLK4 and subsequent clock cycles, branch holding register 250 and branch update data register 256 contain the corrected fetch address and associated branch prediction data, respectively (as indicated by block 306). Later, in ICLKN, another branch misprediction is detected as indicated by block 307. In ICLKN+1, similar to ICLK2, the new address ("Corrected Addr2") is translated to a linear address and the corrected address currently stored in branch holding register 250 ("Corrected Addr") is written into the branch prediction array (as indicated by blocks 308 and 209, respectively).

Turning now to FIG. 4, a second timing diagram depicts a misprediction followed by an external fetch to further illustrate operation of the branch holding register. Similar to FIG. 4, branch holding register 250 contains an address A as shown in block 400, and branch update data register 256 contains the update data associated with address A. In ICLK1, reorder buffer 216 indicates that a misprediction has been detected, as shown in block 401. In ICLK2, a signal on update select line 260 indicates that the branch history register should be selected by input multiplexor 254. While instruction cache 204 translates the logical corrected address to a linear address (as indicated by block 402 in FIG. 4), address A and its associated branch prediction information are written into branch prediction array 255 (as indicated by block 403). In ICLK3, the corrected address has been translated to a linear address and accesses instruction cache 204 and branch prediction array 255, as indicate by block 405. The way value of instruction cache 204 storing the instructions associated with the corrected address is stored in branch update data register 256. In ICLK4 and subsequent clock cycles, branch holding register 250 and branch update data register 256 contain the corrected fetch address and associated branch prediction data, respectively (as indicated by block 406). Later, in ICLKN, instruction cache 204 detects an instruction cache miss (as indicated by block 407). In ICLKN+1, an external fetch begins (as indicated by block 408) and the corrected fetch address from the previous misprediction is written into branch prediction array 255 (as indicated by block 409). In a later clock cycle (not shown) the external fetch data arrives and predecoding is performed. When a branch instruction is predecoded, the predecoded information and branch address are stored in branch update data register 256 and branch holding register 250, respectively, until the next misprediction is detected or until the next external fetch begins.

As can be seen from the above timing diagrams, external fetches and branch mispredictions may occur in any order. Each time one of the two events occurs, the data associated with the previous event is written into the branch prediction array. The data associated with the new event is written into the branch holding register and branch update data register.

It is noted that aspects regarding instruction cache 204 are described within the co-pending, commonly assigned patent application entitled: "Linearly Addressable Microprocessor Cache", Ser. No. 08/146,381, filed Oct. 29, 1993 by Witt now abandoned. The disclosure of this patent application is incorporated herein by reference in its entirety.

Turning next to FIGS. 5-66, details regarding various aspects of another embodiment of a superscalar microprocessor are next considered. FIG. 5 is a block diagram of a processor 500 including an instruction cache 502 coupled to a prefetch/predecode unit 504, to a branch prediction unit 506, and to an instruction alignment unit 508. A set 510 of decode units is further coupled to instruction alignment unit 508, and a set 512 of reservation station/functional units is coupled to a load/store unit 514 and to a reorder buffer 516. A register file unit 518 is finally shown coupled to reorder buffer 516, and a data cache 522 is shown coupled to load/store unit 514.

Processor 500 limits the addressing mechanism used in the x86 to achieve both regular simple form of addressing as well as high clock frequency execution. It also targets 32-bit O/S and applications. Specifically, 32-bit flat addressing is employed where all the segment registers are mapped to all 4GB of physical memory. The starting address being 0000-0000 hex and their limit address being FFFF hex. The setting of this condition will be detected within processor 500 as one of the conditions to allow the collection of accelerated data paths and instructions to be enabled. The absence of this condition of 32-bit flat addressing will cause a serialization condition on instruction issue and a trapping to MROM space.

Another method to ensure that a relatively high clock frequency may be accommodated is to limit the number of memory address calculation schemes to those that are simple to decode and can be decoded within a few bytes. We are also interested in supporting addressing that fits into our other goals, i.e., regular instruction decoding.

As a result, the x86 instruction types that are supported for load/store operations are:

push implied ESP-4!

pop implied ESP+4!

call implied ESP+8!

ret (implied ESP-8!

load base+8-bit displacement!

storebase+8-bit displacement!

oper. EBP+8-bit displacement!

oper. (EAX+8-bit displacement!

The block diagram of FIG. 6 shows the pipeline for calculating addressing within processor 500. It is noted that base+8/32 bit displacement takes 1 cycle, where using an index register takes 1 more cycle of delay in calculating the address. More complicated addressing than these requires invoking an MROM routine to execute.

An exemplary listing of the instruction sub-set supported by processor 500 as fast path instructions is provided below. All other x86 instructions will be executed as micro-ROM sequences of fast path instructions or extensions to fast path instructions.

The standard x86 instruction set is very limited in the number of registers it provides. Most RISC processors have 32 or greater general purpose registers, and many important variables can be held during and across procedures or processes during normal execution of routines. Because there are so few registers in the x86 architecture and most are not general purpose, a large percentage of operations are moves to and from memory. RISC architectures also incorporate 3 operand addressing to prevent moves from occurring of register values that are desired to be saved instead of overwritten.

The x86 instruction set uses a set of registers that can trace its history back to the 8080. Consequently there are few registers, many side effects, and sub-registers within registers. This is because when moving to 16-bit, or 32-bit operands, mode bits were added and the lengths of the registers were extended instead of expanding the size of the register file. Modern compiler technology can make use of large register sets and have a much smaller percentage of loads and stores. The effect of these same compilers is to have a much larger percentage of loads and stores when compiling to the x86. The actual x86 registers are often relegated to temporary registers for a few clock cycles while the real operation destinations are in memory.

FIG. 7 shows a programmer's view of the x86 register file. One notes from this organization that there are only 8 registers and few are general purpose. The first four registers, EAX, EDX, ECX, and EBX, have operand sizes of 8, 16, or 32-bits depending on the mode of the processor or instruction. The final 4 registers were added with the 8086 and extended with the 386. Because there are so few real registers, they tend to act as holding positions for the passing of variables to and from memory.

The important thing to note is that when executing x86 instructions, one must be able to efficiently handle 8, 16, and 32-bit operands. If one is trying to execute multiple x86 instructions in parallel, it is not enough to simply multi-port the register file. This is because there are too few registers and all important program variables must be held in memory on the stack or in a fixed location.

RISC designs employ regular instruction decoding along natural boundaries to achieve very high clock frequencies and also with a small number of pipeline stages even for very wide issue processors. This is possible because finding a large number of instructions and their opcodes is relatively straightforward, since they are always at fixed boundaries.

As stated previously, this is much more difficult in an x86 processor where there are variable byte instruction formats, as well as prefix bytes and SIB bytes that can effect the length and addressing/data types of the original opcode.

Processor 500 employs hardware to detect and send simple instructions to fixed issue positions, where the range of bytes that a particular issue position can use is limited. This may be compensated for by adding many issue positions that each instruction cache line can assume in parallel.

Once the instructions are aligned to a particular issue position, the net amount of hardware required to decode common instructions is not significantly greater than that of a RISC processor, allowing equivalent clock frequencies to be achieved. Processor 500 achieves high frequency, wide issue, and limited pipeline depth by limiting the instructions executed at high frequency to a sub-set of the x86 instructions under the conditions of 32-bit flat addressing.

The results of executing instructions are returned to the corresponding entry in the reorder buffer. If a store, the store is held in speculative state in front of the data cache in a store buffer, from which point it can be speculatively forwarded from. The reorder buffer then can either cancel this store or allow it to writeback to the data cache when the line is retired.

The following set of instructions probably comprise 90% of the dynamically executed code for 32-bit applications:

8/32-bit operations

move reg/reg reg/mem

arithmetic operations reg/mem reg/reg logical operations reg/reg reg/mem push

logical operations reg/reg reg/mem

push

pop

call/return

load effective address

jump cc

jump unconditional

16-bit operations

prefix/move reg/reg

prefix/move reg/mem

prefix/arithmetic operations reg/reg, reg/mem

prefix/logical operations reg/reg reg/mem

prefix/push

prefix/pop

When executing 32-bit code under flat addressing, these instructions almost always fall within 1-8 bytes in length, which is in the same rough range of the aligned, accelerated fast path instructions.

Accelerated instructions are defined as fast-path instructions between 1 and 8 bytes in length. It noted that it is possible that the start/end positions predecoded reflect multiple x86 instructions, for instance 2 or 3 pushes that are predecoded in a row may be treated as one accelerated instruction that consumes 3 bytes.

When a cache line is fetched from the instruction cache, it moves into an instruction alignment unit which looks for start bytes within narrow ranges. The instruction alignment unit uses the positions of the start bytes of the instructions to dispatch the instructions to four issue positions. Instructions are dispatched such that each issue position accepts the first valid start byte within its range along with subsequent bytes.

A multiplexer in each decoder looks for the end byte associated with each start byte, where an end byte can be no more than seven bytes away from a start byte. The mechanism to scan for a constant value in an instruction over four bytes in length may be given an extra pipeline stage due to the amount of time potentially required.

Note that instructions included in the subset of accelerated instructions, and which are over four bytes in length, always have a constant as the last 1/2/4 bytes. This constant is usually not needed until the instruction is issued to a functional unit, and therefore the determination of the constant value can be delayed in the pipeline. The exception is an instruction requiring an eight-bit displacement for an address calculation. The eight-bit displacement for stack-relative operations is always the third byte after the start byte, so this field will always be located within the same decoder as the rest of the instruction.

It is possible that a given cache line can have more instructions to issue than can be accommodated by the four entry positions contained in each line of the four issue reorder buffer. If this occurs, the four issue reorder buffer allocates a second line in the buffer as the remaining instructions are dispatched. Typically, in 32-bit application and O/S code, the average instruction length is about three bytes. The opcode is almost always the first two bytes, with the third byte being a sib byte specifying a memory address (if included), and the fourth byte being a 16-bit data prefix.

The assumption in the processor 500 alignment hardware is that if the average instruction length is three, then four dedicated issue positions and decoders assigned limited byte ranges should accommodate most instructions found within 16-byte instruction cache lines. If very dense decoding occurs (i.e., lots of one and two byte instructions), several lines are allocated in the four issue reorder buffer for the results of instructions contained in a few lines of the instruction cache. The fact that these more compact instructions are still issued in parallel and at a high clock frequency more than compensates for having some decoder positions potentially idle.

Overview of the Processor 500 Instruction Cache (Icache)

This section describes the instruction cache organization, fetching mechanism, and pre-decode information. The Processor 500 instruction cache has basic features including the ICSTORE, ICTAGV, ICNXTBLK, ICCNTL, ICALIGN, ICFPC, and ICPRED. Highlights are: the pre-decode bits per byte of instructions are 3 bits, the branch prediction increases to 2 targets, 2 different types of branch prediction techniques (bimodal and global) are implemented, the X86 instructions align to 4 fixed length RISC-type instructions, and the pre-decode logic eliminates many serializtion conditions. Processor 500 executes the X86 instructions directly with a few instructions requiring two Rops, the BYTEQ is configured for fast scanning of instructions, and instructions are aligned to 4 decode units. The pre-decode data is separate in a block called ICPDAT, instead of inside the ICSTORE. The pre-fetch buffers are added to the ICSTORE to write instructions directly into the array, and the prefixes are not modified. All branches are detected during pre-decoding. Unconditional branches are taken during pre-decoding and aligning of instructions to the decode units. A return stack is implemented for CALL/RETURN instructions. Way prediction is implemented to read the current block and fetch the next block because the tag comparison and branch prediction do not resolve until the second cycle. The scanning for 4 instructions is done from ICPDAT before selected by tag comparison. Since the pre-decode data does not include the information for the 2-Rop instructions, the instructions must be partially decoded for the 2-rop during prioritizing and aligning of instructions to decode units. The early decoding includes decoding for unconditional branches, operand addresses, flags, displacement and immediate fields of the instruction. The CMASTER takes care of the replacement algorithm for the Icache and sends the way associative along with the data to the pre-fetch buffer. This section includes signal lists, timings and implementation issues for the Icache and all sub-blocks.

The Icache size is 32K bytes with 8-way set associative. The Icache is linearly addressed. The number of pipeline stages is 9. Icache will have more than one clock cycle to read and align the instructions to the decode units. The row decoding of index address is calculated in first half of ICLK, the data, tag, pre-decode, and predicting information are read in by the end of ICLK. In the next cycle, the data are selected by the TAGHITs and latched. The pre-decode data are scanned to generate the controls to the multiplexers for aligning and sending the instructions to the decode units and MROM units. A part of the scanning logic is done in parallel with the tag comparison. The scanning and alignment of instructions takes two clock cycles. The decode units can start decoding in the second half of the third clock. The Icache includes a way-prediction which can be done in a single clock using the ICNXTBLK target. The branch prediction includes bimodal and global branch prediction which takes two clock cycles. The timing from fetching, scanning, aligning, decoding, and muxing of instructions to decode units are shown in FIG. 8.

Throughout this documentation, a discussion of the layout organization is included in each section. The array is organized into many sets, and each set has its own decoder. The decoder is in the center of the set.

Signal list

SRBB(31:0)--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB.

SRB.sub.-- VAL--Input from SRB indicates a special register instruction is on the SRBB.

ICTAR.sub.-- VAL--Output to SRB indicates completion of the special register instruction, for read the data is on the SRBB.

IRESET--Global signal used to reset ICACHE block. Clears all state machines to Idle/Reset.

IDECJAMIC--Global signal from FIROB. Used to indicate that an interrupt or trap is being taken. Effect on Icache is to clear all pre-fetch or access in progress, and set all state machines to Idle/Reset.

EXCEPTION--Global input from FIROB indicates that an interrupt or trap is being taken including re-synchronization. Effect on Idecode and FUs is to clear all instructions in progress.

REQTRAP--Global input from FIROB, one cycle after EXCEPTION, indicates that the trap is initiated with new entry point or new PC is driven.

INVBHREG--Input from FIROB to invalidate the branch holding register. The branch mis-prediction is speculative, an early branch can be mis-predicted at a later time.

CS32X16--Input from LSSEC indicates operand and address size from the D bit of the segment descriptor of the code segment register. If set, 32-bit, if clear, 16-bit.

SUPERV--Input from LSSEC indicates the supervisor mode or user mode of the current accessed instruction.

TR12DIC--Input from SRB indicates that all un-cached instructions must be fetched from the external memory.

SRBINVILV--Input from SRB to invalidate the Icache by clear all valid bits.

INSTRDY--Input from BIU to indicates the valid external fetched instruction is on the INSB(63:0) bus.

INSTFLT--Input from BIU to indicates the valid but faulted external fetched instruction is on the INSB(63:0) bus.

INSB(63:0)--Input from external buses for fetched instruction to the Icache.

L2.sub.-- IC.sub.-- ALIAS--Input from CMASTER indicates the instruction is in the Icache with different mapping. The CMASTER provides the way associative and new supervisor bit. The LV will be set in this case.

PFREPLCOL(2:0)--Input from CMASTER indicates the way associative for writing of the ICTAGV.

UPDFPC--Input from FIROB indicate that a new Fetch PC has been detected. This signal accompanies the FPC for the Icache to begin access the cache arrays.

FPC(31:0)--Input from FIROB as the new PC for branch correction path.

BPC(11:0)--Input from FIROB indicates the PC index and byte-pointer of the branch instruction which has been mis-predicted for updating the ICNXTBLK. This index must be compared to the array index for exact recovery of the global shift register.

BRNMISP--Input from the Branch execution of the FU indicates a branch mis-prediction. The Icache changes its state machine to access a new PC and clears all pending instructions.

BRNTAKEN--Input from FIROB indicate the status of the mis-prediction. This signal must be gated with UPDFPC.

BRNTAG(3:0)--Input from FIROB indicates the instruction byte for updating the branch prediction in the ICNXTBLK.

FPCTYP--Input for FIROB indicates the type of address that is being passed to the Icache.

HLDISP(1:0)--Output to Idecode indicates all instructions of the first (bit 0) and/or the second (bit 1) 8-byte of the current line has been dispatched to decode units.

REFRESH2--Input from Idecode indicates current line of instructions will be refreshed and not accept new instructions from Icache.

MROMEND--Input from MENG indicates completion of the MROM.

D0USEFL(4:0)

D0WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 0:

xx1 CF-carry flag,

x1x OF-overflow flag,

1xx SF-sign, ZF-zero, PF-parity, and AF-auxiliary carry

D1USEFL(4:0)

D1WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 1.

D2USEFL(4:0)

D2WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 2.

D3USEFL(4:0)

D3WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 3.

RD0PTR1(5:0)--Indicates the register address for operand 1 of decode unit 0. The MROM is responsible to send bit 5:3 for the MROM register.

RD1PTR1(5:0)--Indicates the register address for operand 1 of decode unit 1. The MROM is responsible to send bit 5:3 for the MROM register.

RD2PTR1(5:0)--Indicates the register address for operand 1 of decode unit 2. The MROM is responsible to send bit 5:3 for the MROM register.

RD3PTR1(5:0)--Indicates the register address for operand 1 of decode unit 3. The MROM is responsible to send bit 5:3 for the MROM register.

RD0PTR2(5:0)--Indicates register address for operand 2 of decode unit 0. The MROM is responsible to send bit 5:3 for the MROM register.

RD1PTR2(5:0)--Indicates register address for operand 2 of decode unit 1. The MROM is responsible to send bit 5:3 for the MROM register.

RD2PTR2(5:0)--Indicates register address for operand 2 of decode unit 2. The MROM is responsible to send bit 5:3 for the MROM register.

RD3PTR2(5:0)--Indicates register address for operand 2 of decode unit 3. The MROM is responsible to send bit 5:3 for the MROM register.

IDxDAT(1:0)--Output to indicates the data size information. 01-byte, 10-half word, 11-word, 00-not used.

ICBTAG1(3:0)--Output to Idecode indicates the position of the first target branch instruction with respect to the global shift register in case of branch mis-prediction. The branch can be taken or non-taken, branch tag must be sent with all branch instruction.

ICBTAG2(3:0)--Output to Idecode indicates the position of the second target branch instruction with respect to the global shift register in case of branch mis-prediction. The branch can be taken or non-taken, branch tag must be sent with all branch instruction.

UNJMP(3:0)--Output indicates the unconditional branch instruction needs to calculate target address.

BRNTKN(3:0)--Output indicates which decode unit has a predicted taken branch. The operand steering uses this signal to latch and send BTADDR(31:0) to the functional unit.

BRNINST(3:0)--Output indicates which decode unit has a global branch prediction. The operand steering uses this signal to latch and send ICBTAG1(3:0) and ICBTAG2(3:0) to the functional units.

CALLDEC(3:0)--Output to FIROB indicates the CALL instruction is detected, the return stack should be updated with the PC address of instruction after CALL. The information is latched for mis-predicted CALL branch.

RETDEC(3:0)--Output to FIROB indicates a RETURN instruction is detected. The information is latched for mis-predicted RETURN branch.

ICPREF(9:0)--Output to Idecode and MROM indicates the encoded prefix byte. The two most significant bits are repeat prefixes for MROM.

IC2ROP0(3:0)--Output to decode unit 0 indicates 2-rop instruction. Bit 3 indicates the first rop or second rop of the 2-rop instruction, bit 2 indicates POP instruction, bit 1 indicates the MUL instruction, and bit 0 indicates the SIB-byte instruction.

NODEST(3:0)--Output to FIROB indicates no destination for the first rop of the SIB-byte instruction.

DEPTAG(3:1)--Output to FIROB indicates forced dependency tag on the first instruction; the second rop of the SIB-byte instruction.

REFRESH2--Input from Idecode indicates current line of instructions will be refreshed and not accept new instructions from Icache.

IB1(191:0)--Output indicates the combined instruction line for dispatching to decode units.

MROMEN--Input from MENG indicates the micro-instructions is sent to Idecode instead of the Icache.

M0USEFL(4:0)

M0WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 0:

xx1 CF-carry flag,

x1x OF-overflow flag,

1xx SF-sign, ZF-zero, PF-parity, and AF-auxiliary carry

M1USEFL(4:0)

M1WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 1.

M2USEFL(4:0)

M2WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 2.

M3USEFL(4:0)

M3WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 3.

MINS0(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 0.

MINS1(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 1.

MINS2(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 2.

MINS3(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 3.

MR0OPC(7:0)--Input from MENG to decode unit 0 indicates the opcode byte.

MR1OPC(7:0)--Input from MENG to decode unit 1 indicates the opcode byte.

MR2OPC(7:0)--Input from MENG to decode unit 2 indicates the opcode byte.

MR3OPC(7:0)--Input from MENG to decode unit 3 indicates the opcode byte.

MR0EOP(2:0)--Input from MENG to decode unit 0 indicates the extended opcode field.

MR1EOP(2:0)--Input from MENG to decode unit 1 indicates the extended opcode field.

MR2EOP(2:0)--Input from MENG to decode unit 2 indicates the extended opcode field.

MR3EOP(2:0)--Input from MENG to decode unit 3 indicates the extended opcode field.

MR0SS(1:0)--Input from MENG to decode unit 0 indicates the scale factor of the SIB byte.

MR1SS(1:0)--Input from MENG to decode unit 1 indicates the scale factor of the SIB byte.

MR2SS(1:0)--Input from MENG to decode unit 2 indicates the scale factor of the SIB byte.

MR3SS(1:0)--Input from MENG to decode unit 3 indicates the scale factor of the SIB byte.

ICMROM--Output to MENG indicates the current instruction is MROM. The MROM instruction may take two cycles to read the IB, ICEND, and ICFUNC.

ENDINST--Input from ICPRED indicates that pre-decoding is completed for the current instruction. The byte position of the branch instruction is from STARTPTR. The selected instruction from IB should be sent to decode unit 0.

ICVALI(3:0)--Output to Idecode indicates valid instructions. NOOP is generated for invalid instruction.

IC0OPC(7:0)--Output to decode unit 0 indicates the opcode byte.

IC1OPC(7:0)--Output to decode unit 1 indicates the opcode byte.

IC2OPC(7:0)--Output to decode unit 2 indicates the opcode byte.

IC3OPC(7:0)--Output to decode unit 3 indicates the opcode byte.

IC0EOP(2:0)--Output to decode unit 0 indicates the extended opcode field.

IC1EOP(2:0)--Output to decode unit 1 indicates the extended opcode field.

IC2EOP(2:0)--Output to decode unit 2 indicates the extended opcode field.

IC3EOP(2:0)--Output to decode unit 3 indicates the extended opcode field.

IC0SS(1:0)--Output to decode unit 0 indicates the scale factor of the SIB byte.

IC1SS(1:0)--Output to decode unit 1 indicates the scale factor of the SIB byte.

IC2SS(1:0)--Output to decode unit 2 indicates the scale factor of the SIB byte.

IC3SS(1:0)--Output to decode unit 3 indicates the scale factor of the SIB byte.

DISPTR0(6:0)--Output to decode unit 0 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

DISPTR1(6:0)--Output to decode unit 1 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

DISPTR2(6:0)--Output to decode unit 2 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5 =00 indicates no displacement.

DISPTR3(6:0)--Output to decode unit 3 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

IMMPTR0(4:0)--Output to decode unit 0 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block. Decoding of all opcodes is needed to detect immediate field.

IMMPTR1(4:0)--Output to decode unit 1 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block. Decoding of all opcodes is needed to detect immediate field.

IMMPTR2(4:0)--Output to decode unit 2 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block. Decoding of all opcodes is needed to detect immediate field.

IMMPTR3(4:0)--Output to decode unit 3 indicates the displacement pointer and size. Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block. Decoding of all opcodes is needed to detect immediate field.

CONSTn(2:0)--Output to decode unit n indicates the constant for add/substract to ESP of the two-dispatch position instruction.

MROMEN--Input from MENG indicates the micro-instructions is sent to Idecode instead of the Icache.

IB2(191:0)--Output to decode units indicates the current line of instructions.

ICMROM--Output to MENG indicates the current instruction is MROM. The MROM instruction may take two cycles to read the IB, ICEND, and ICFUNC.

ICPC1TAR--Output to Idecode indicates is ICPC1 a branch target of a previous instruction which is a predicted taken branch instruction.

ICPC2TAR--Output to Idecode indicates is ICPC2 a branch target of a previous instruction which is a predicted taken branch instruction.

ICPC1(31:0)--Output to Idecode indicates the current line PC of the first instruction in the 4 issued instructions to pass along with the instruction to FIROB.

ICPC2(31:0)--Output to Idecode indicates the current line PC of a second instruction which cross the 16-byte boundary or branch target in the 4 issued instructions to pass along with the instruction to FIROB.

ICPOS0(4:0)--Output to decode unit 0 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS1(4:0)--Output to decode unit 1 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS2(4:0)--Output to decode unit 2 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS3(4:0)--Output to decode unit 3 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

BTAG1N(3:0)--Output indicates the position of the first target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

BTAG2N(3:0)--Output indicates the position of the second target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

BTAKEN1(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVAL1. Bit 0 is the last line and bit 1 is new line.

BTAKEN2(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVAL2. Bit 0 is the last line and bit 1 is new line.

ICERROR--Output, indicates an exception has occurred on an instruction pre-fetched, the type of exception (TLB-miss, page-fault, illegal opcode, external bus error) will also be asserted.

INSPFET--Output to BIU and CMASTER requests instruction fetching from the previous incremented address, the pre-fetch buffer in the Icache has space for a new line from external memory.

ICAD(31:0)--Output to MMU indicates a new fetch PC request to external memory.

RETPRED--Output to Idecode indicates the current prediction of the return instruction of the fetched line. The return instruction must be detected in the current line of instruction or the Icache must be re-fetched from a new line.

IC.sub.-- EXT.sub.-- RD--Output to CMASTER indicates the next line of instruction should be fetched from external regardless of aliasing. This is for pre-fetching of instruction which crosses the line boundary.

MMUPFPGFLT--Input from MMU indicates page fault for the current instruction address.

TLB.sub.-- MISS.sub.-- PF--Input from MMU indicates TLB miss for the current instruction address.

PF.sub.-- IC.sub.-- XFER--Output to CMASTER indicates the address for the current line is written into the cache, the L2 should be updated with the physical address. This is when the ICPDAT and the valid bit is written.

BIU.sub.-- NC--Input from BIU indicates the current line should not be cached.

LS2ICNOIC--Input from LSSEC indicates no caching, pre-fetch only.

LS.sub.-- CS.sub.-- WR--Input from LSSEC indicates the CS is being updated.

L2.sub.-- IC.sub.-- INV(1:0)--Input from CMASTER to invalidate up to 2 lines in the Icache.

PF.sub.-- IDX(6:0)--Input from CMASTER indicates the array index for invalidating up to 2 lines in the Icache or for aliasing.

PF.sub.-- SNP.sub.-- COL(2:0)--Input from CMASTER indicates the way associative for invalidating up to 2 lines in the Icache or aliasing. This signal may be redundant with PFREPLCOL(2:0).

BIT20MASK--Input from CMASTER indicates masking of bit 20 for backward compatible with 8086. The line should not be cache if outside of the page.

BSTRUN--Input from TAP indicates to start the BIST.

BSTRD--Input from TAP indicates to read the array and compare to set the result.

BSTWR--Input from TAP indicates to write the array from input registers.

BSTRST--Input from TAP indicates to reset the counter.

BSTINCR--Input from TAP indicates to increment the counter.

BSTDIN--Input from TAP indicates the test pattern to the input registers. The input can be from the TDI pin or normal burn-in patterns.

FLUSHON--Input from TAP indicates flushing register mode, the result latch should use BSTDIN instead of the compare input for flushing the result registers.

UPDOWN--Input from TAP indicates counting up or down.

BSTSHF1--Input from TAP indicates shifting of the master latch of registers.

BSTSHF2--Input from TAP indicates shifting of the slave latch of registers.

BSTFALSE--Input from TAP indicates to invert the test pattern.

PORTSEL--Input from TAP indicates to select the second dual port.

BSTIDOUT--Output to TAP indicates the result of the data chain from the ICSTORE and ICPDAT arrays.

BSTITOUT--Output to TAP indicates the result of the data chain from the ICNXTBLK and ICTAGV arrays.

BSTAMSB--Output to TAP indicates maximum count for dual port arrays.

MAXADDR--Output to TAP indicates maximum index counter.

ATPGIN(15:14)--Input from dedicated pins for ATPG.

ATPGOUT(15:14)--Output to dedicated pins for ATPG.

ICSTORE

Processor 500 executes fast X86 instructions directly, no ROPs are needed. The pre-decode bits with each byte of instruction are 3 bits; start bit, end bit, and functional bit. All the externally fetched instructions will be latched into the Icache. This should not be a problem since the Icache is idle and waits for external instructions. Only single byte prefix of 0x66 and 0x0F is allowed for Processor 500's fast path, multiple prefixes including 0x67 is allowed for multi-prefix, all other prefixes will take an extra cycle in decoding or go to MROM. With these simple prefixes, the instruction bytes need not be modified. The linear valid bit is used for the whole cache-line of instructions, 16-byte. The replacement procedure is done by the CMASTER. Along with each line of instruction, the CMASTER tells the Icache which way to put in the data and tag. The start and end bits are sufficient to validate the instruction. If branching to the middle of the line or instructions wrapping to the next line, the start and end bits must be detected for each instruction or else the instruction must be pre-decoded again. The possible cases are branching to the opcode and skipping the prefix (punning of instruction) and part of the wrapping instruction is replaced in the Icache. The instructions must first pass through the pre-fetch buffers before sending to the ICPRED. The ICPRED has only one input from the IB(127:0) for both the pre-fetched or cached instructions. The pre-decode information is written into the ICPDAT as the whole line is decoded. The output IB(127:0) is merged with the previous 8-byte to form a 24-byte line for the alignment unit to select and send to 4 decode units.

Since the instruction fetching from external memory will be written directly into the Icache, the pre-fetch buffer should be built into the ICSTORE; the input/output path of the array. In this way, the data will be written into the Icache regardless of the pre-decode information or the taken branch instruction and the instructions is available to the Icache as soon as they are valid on the bus. The number of pre-fetch buffers is two, and request will be made to BIU as soon as there is space in the pre-fetch buffer for another line of instructions. The pre-fetch buffer consists of a counter and a valid bit for instructions written into the cache and a valid bit for instructions sent to the decode unit. As long as the address pointer is still in the same block, the data will be written to the array. With the pre-fetch buffer in the Icache, a dedicated bus should be used to transfer instructions directly from the pads to the Icache; this is a step to keep Processor 500 from using dynamic pre-charged buses.

ICSTORE ORGANIZATION

The ICSTORE on Processor 500 does not store the pre-decode data, as shown in FIG. 9. The ICSTORE consists of 32K bytes of instructions organized as 8 sets of 128 rows by 256 columns. The array set in this documentation has its own decoder. The decoder is in the center of the set. Each of the sets consist of 2-byte of instructions. The 8-way associative muxing from the 8 TAG-HITs is performed before the data is routed to the ICALIGN block. With this arrangement, the input/output to each set is 16-bit buses. The muxing information relating to which byte is going to which decode unit should also be decoded; this topic will be discussed in detail below in the ICALIGN block section. For optimal performance the layout of the column should be 64 RAM cells, pre-charge, 64 RAM cells, write buffer and senamp. The row decoder should be in the middle of the array to drive 128 column each way. Basically, the pre-charge and the row decoder should be crossed in the middle of the array. The self-time column is used to generate internal clock for each set of the array. Pre-charge is gated by ICLK. The instruction is valid by the end of ICLK, the data muxes by the TAG-HIT should be gated by ICLK to be valid for the second ICLK. The two-entry pre-fetch buffers are implemented inside the array with data can be written from either entry. The output IB bus is taken from either the array or the pre-fetch buffer.

The BIST for the ICSTORE array uses 128 TAEC cells for reading and writing the arrays, as discussed further below.

Signal list

ISADD(11:2)--2--Input from ICFPC indicates the address of instruction to access the array. Bits 11:5 are for the row decoder, bits 4:2 are for column select. For normal operation, bits 11:4 is used to read/write 16-byte only. For special register operation, bits 11:2 is used to read/write 4-byte.

TAGHIT(7:0)--2--Input from ICTAGV indicates which set is selected to read instructions.

ICSRD--2--Input from ICCNTL to read instruction.

ICSWR--2--Input from ICCNTL to write instructions from pre-fetch buffers into the array. This signal is asserted at starting of the pre-fetch enable and de-asserted when a pre-fetch buffer entry is valid, the instruction is written into the array and the valid bit is reset.

GETNEWL--2--Input from ICPRED indicates that pre-decoding has reached the end of the line or encountered a taken branch instruction, a new line of instructions is needed in the next cycle. The ICSTORE should send a new line onto IB bus and write into the array.

SRSRD--2--Input from ICCNTL to read instruction from the array in the next cycle.

SRSWR--2--Input from ICCNTL to write instruction to the array in the next cycle.

ICSRBB(31:0)--14--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB.

SETSEL(7:0)--14--Input from ICFPC indicates which set to read, no tag compare is needed.

TAGCHK--14--Input from ICCNTL to indicates the valid set is from TAGHIT or SETSEL.

PBENAB--14--Input from ICCNTL to enable the pre-fetch buffer to latch the INSB(31:0) bus and write into the array.

INSTRDY--13--Input from BIU to indicates the valid external fetched instruction is on the INSB(63:0) bus.

INSTFLT--13--Input from BIU to indicates the valid but faulted external fetched instruction is on the INSB(63:0) bus.

INSB(63:0)--3--Input from external buses for fetched instruction to the Icache.

IB(127:0)--1--Output to ICALIGN after the set select to align instructions to decode units.

PBFLT--15--Output to ICCNTL indicates a valid faulted line of instruction from external fetch.

PBVAL--15--Output to ICCNTL indicates a valid line of instruction from external fetch.

PBEMPTY--15--Output to ICCNTL indicates the pre-fetch buffer is empty.

PBONE--15--Output to ICCNTL indicates the pre-fetch buffer has one available entry.

PBFULL--15--Output to ICCNTL indicates the pre-fetch buffer is full.

BSTRD--Input from TAP indicates to read the array and compare to set the result.

BSTWR--Input from TAP indicates to write the array from input registers.

BSTDIN--Input from TAP indicates the test pattern to the input registers. The input can be from the TDI pin or normal burn-in patterns.

FLUSHON--Input from TAP indicates flushing register mode, the result latch should use BSTDIN instead of the compare input for flushing the result registers.

BSTSHF1--Input from TAP indicates shifting of the master latch of registers.

BSTSHF2--Input from TAP indicates shifting of the slave latch of registers.

BSTFALSE--Input from TAP indicates to invert the test pattern.

BSTSTOUT--Output to ICPDAT indicates the result of the data.

ICPDAT

In Processor 500, the pre-decode data is in a separate block than the ICSTORE, and is updated with a different timing than that of instructions. The ICPDAT is updated as the whole instruction line is completed decoding in the ICPRED. To prevent erroneous setting of the pre-decode bits, the valid bit in the ICTAGV is not set until the pre-decode data is written into the array. The pointer to ICSTORE can advance before the whole line of instruction is completed in pre-decode for split-line instruction. The pre-decode data includes three bits: start-byte, end-byte, and functional-byte. During pre-decoding, the ICPDAT uses 2 sets of latches to keep the pre-decode information for each line of instructions. The first set is for the current line and the second set is used for split-line instructions. As each instruction is completed in pre-decoding, the start and end pointers set the latches. The functional bits are kept in the ICPRED and write into the array at the completion of pre-decoding for the line. If a taken branch instruction is detected in ICPRED, the control should allow one clock cycle to write the current pre-decode data into the ICPDAT array. A special case of split-line taken branch instruction, the control allows 2 clock cycles to write the two pre-decode lines into the array.

The start-byte and the end-byte are scanned to align the instructions from ICSTORE to the decode units. A valid instruction should start with a start byte and end with an end byte before another start byte can be detected. Any invalid instruction should be detected in the scanning logic before sending the instruction to early decoding. The invalid instruction must be pre-decoded again by the ICPRED block. ICPDAT should keep all pre-decode data for the line of the confused instruction from the array which will be ORed with the functional bits from pre-decoding for writing back into the array. The pre-decoding stops on two conditions: a taken branch is detected or valid start byte (or valid instruction) is detected after the end byte from pre-decoding; this condition should be detected in the ICPDAT.

The start bits are decoded into byte-shifting information for up to 4 instructions per 8-byte block which will be used by the ICALIGN block. The start-byte pointer for the current fetching instruction is used to reset all the start and end bits before the current pointer, and the taken branch pointer from the way prediction is used to reset all the start and end bits after the branch pointer. All 8-way data should be latched in case of way mis-prediction, the corrected way should be read again from the latches for scanning. An 8-byte or 16-byte block can be read from the array to merge with the previous data to form a 16-byte line for scanning and sending to early decoding. The scanning of the start bits is sectioned into two 8-byte blocks, the maximum scanned path is 8-byte long. The scanning outputs control the muxing of up to 7 bytes for each instruction to early decoding unit. In addition, the scanning of the 8-start-byte generates the look-ahead controls of next 8-byte blocks.

ICPDAT ORGANIZATION

For each 8-byte, the ICPDAT (as shown in FIG. 10) generates 4 sets of valid bits based on the start and end bits. The valid bits are muxed to the ICALIGN the same way as the instruction bytes. The valid bits are used to qualify the functional bits. Example of the valid bits for 8-byte instruction:

Start bits 10100100 01110101

End bits 01001000 11101010

Valid bits 1 11000000 01000000

Valid bits 2 00111000 00100000

Valid bits 3 00000111 10011000

Valid bits 4 00000000 00000110

In setting up the valid bits for the instructions, ICPDAT needs to validate the instruction with proper the start and end bits. Only instructions with valid start and end bits can be in ICALIGN. If the line is hit in the cache, the pre-decode data should be latched into the buffer for future reference. ICPDAT notifies ICCNTL to pre-decode the invalid instruction. The functional bits from ICPRED are ORed with the local buffer of functional bits for writing back into the array. During pre-decoding if a valid start byte is detected after an end byte, ICPDAT should notify ICCNTL to stop pre-decoding, writing the current pre-decode data into the array, and re-fetching the line for scanning. The scanning logic should use only the pre-decode data from the array. The MROM instruction should also be detected in ICPDAT with a pointer to the ICALIGN and the MROM. The MROM instruction is read directly from the IB(127:0). MROM is responsible to detect and decode the prefixes and opcode as with ICALIGN. Exemplary hardware is shown in FIG. 11.

The Icache line sets up as two 8-byte sections, the scanned logic and fetching of next line should be independent of each other. While scanning, the end-byte should also be detected to indicate that all 8-byte can be dispatched in one clock cycle and to fetch a new line. Conditions to fetch the next 8-byte are:

Three start bits or less.

Four start bits with no more than 3 end bits.

Four start bits with 4 end bits, the last end bit is on the last byte.

Hold indication from early decoding.

Hold for more than one MROM instruction in the current 16 bytes.

Since the instruction can have up to 15 bytes which can span more than two 8-byte blocks, the ICPDAT can send the instruction to the next stage with assumed valid bits. The split-line instruction has indication to read the rest of the instruction in the next clock cycle. In the next cycle if the end bit is not detected within 15 bytes, the instruction must be sent to ICPRED for pre-decoding. The output from the ICSTORE is IB(127:0), ICPDAT provides the controls for muxing of this bus to the IB1(191:0) which is in the ICALIGN block. The muxing is for any of the 8-byte block on IB(127:0) to any of the 8-byte block on IB1(191:0). ICPRED also provides similar controls for the muxes.

If there are more than 4 instructions in the 8-byte block, the ICPDAT muxes the 8-byte block from IB(127:0) to IB1(191:0) and stalls the next 8-byte block. In the next clock cycle, the first 4 instructions clear the pre-decode data and the 8-byte block starts scanning with the fifth instruction. The same 8-byte block should be muxed from IB(127:0) to IB1(191:0) again. This mechanism keeps the ICALIGN from feeding back information on dispatching of the first 4 instructions. With this method the scanning of instructions in ICPDAT is independent of the next stage and is more flexible; either 3 or 4 instructions can be scanned.

The scanning logic for each 8-byte segment of instructions is done in parallel with the TAGHITs in the ICTAGV block. More details regarding the scanning logic may be found in the commonly assigned, co-pending patent application entitled "A Parallel and Scalable Instruction Scanning Unit" filed concurrently herewith by Narayan. The disclosure of this patent application is incorporated herein by reference in its entirety. It is possible to implement the fetching, scanning, early decoding, and shifting of instructions to the decode units in 4 clock cycles.

MROM INTERFACING

The ICPDAT sends the MROM instruction directly to the MENG. Only one MROM instruction can be sent to the MENG per clock cycle. The MENG pipelines the MROM instructions and provides latches to keep up to 3 MROM instructions including the last MROM on IB(127:0). MROMFULL indicates that the next MROM instruction should be stalled in ICPDAT until the previous MROM instruction is dispatched to a decode unit. ICPDAT provides the byte pointer for the MENG to read the instruction from the IB(127:0) along with the functional and valid bits for decoding the instruction. ICPDAT should indicate MROM instruction to MENG only if the associated 8-bytes can be shifted to the next stage. If the instruction continues to the next line, MENG can expect to read the rest of the instruction on IB(127:0) in the next cycle (similar to sending split-line instruction to ICALIGN). The signal MROMFULL is used to stop ICPDAT to keep the data on IB(127:0) for MENG to process prefixes of the instruction. The micro-instructions rejoin the instruction pipeline in the muxing stage to the decode units. With early detection of MROM instruction to MENG, the penalty for MROM instruction is one clock cycle. MENG is responsible to decode prefixes and all fields of instructions. The same decoding logic is used in the ICPRED and ICALIGN.

In ICALIGN, as the MROM instruction is detected, it moves to dispatched position 0 and waits for micro-instructions from MENG. The following instructions fill the pipeline and dispatch as soon as the last micro-instruction is sent to decode unit. In dispatch position 0, the MROM instruction should start in the first 8-byte block of the IB2(191:0) bus. The MENG can provide pointers to read the displacement and immediate fields of the MROM instruction directly from the IB2(191:0).

ICPDAT ORGANIZATION

The ICPDAT includes of 32K of 3-bit pre-decode data organized as 8 sets of 64 rows by 192 columns. Each of the sets consists of two 3-bit pre-decode data. The pre-decode data is decoded into byte-shifting information which is used by the ICALIGN block. The 8-way associative muxing from the 8 TAGHITs is performed before the byte-shifting data is routed to the ICALIGN block. In order for the instructions to get to the Idecode in middle of the second ICLK, the decode logic for the byte-shifting should be less than 7 gates. The byte-shifting logic has been done. Because of this byte-shifting logic, the array for ICPDAT is 64 rows instead of 128 rows for the ICSTORE array. For optimal performance the layout of the column should be 32 RAM cells, pre-charge, 32 RAM cells, write buffer and senseamp. The row decoder should be in the middle of the array to drive 96 column each way. Basically, the pre-charge and the row decoder should be crossed in the middle of the array. The self-time column is used to generate internal clock for each set of the array. Pre-charge is gated by ICLK. The byte-shifting data muxed by the TAGHIT should be gated by ICLK to be valid for the second ICLK. The output of the array should include logic to feedback the previous pre-decode data for breaking up of the line for second cycle access.

The BIST for the ICDAT array uses 48 TAEC cells for reading and writing the arrays as explained further below.

Signal list

IPADD(11:2)--Input from ICFPC indicates the address of instruction to access the array. Bits 11:6 are for the row decoder, bits 5:2 are for column select. For normal operation, bits 11:4 is used to read/write 16-byte only. For special register operation, bits 11:2 is used to read/write 4-byte.

TAGHIT(7:0)--Input from ICTAGV indicates which set is selected to read instructions.

ICSRD--Input from ICCNTL to read instruction.

ICPWR--Input from ICCNTL to write pre-decoded data from ICPRED into the array. This signal is asserted at starting of the pre-fetch enable and when ENDLINE is asserted, the pre-decode data is written into the array.

GETNEWL--Input from ICPRED indicates that pre-decoding has reached the end of the line or encountered a taken branch instruction, a new line of instructions is needed in the next cycle. Used to clear the pre-decode latch.

ENDLINE--Input from ICPRED indicates that pre-decoding has reached the end of the line or encountered a taken branch instruction, the pre-decode data should be written into the array.

SRPRD--Input from ICCNTL to read pre-decode data for special register.

SRPWR--Input from ICCNTL to write pre-decode data for special register.

ICSRBB(23:0)--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB. 8-byte of pre-decode data is transferred at one time. The order is Start, Functional, End bits for each byte of instruction.

SETSEL(7:0)--Input from ICFPC indicates which set to read, no tag compare is needed. This signal is from SRB or branch prediction.

TAGCHK--Input from ICCNTL to indicates the valid set is from TAGHIT or SETSEL.

NEWWAY--Input from ICCNTL to indicates way mis-prediction to select the correct way from the latches using TAGHIT.

ENDINST--Input from ICPRED indicates that pre-decoding is completed for the current instruction. The pre-decode bits should be set at this time. This signal should also be sent along with ENDLINE for partially decode instruction.

PENDIB(4:0)--Input from ICPRED indicates the end byte position of the current instruction. The end bit is set and latched until pre-decoding of the whole line is completed. Bit 4 indicates if the end bit is on the next line.

PFUNCB(15:0)--Input from ICPRED indicates the functional bits of current line of instructions. ICPDAT uses ENDLINE to OR these bits previous pre-decode data and write into the array. As a new line is read from the array the pre-decode data is latch in the buffer. The ICPRED must keep all the functional bits for all the pre-decoded instruction in the line.

STARTPTR(3:0)--Input from ICFPC indicates the byte position of the pre-decoded bytes for current instruction. The start byte should be set at this pointer for writing. For reading, this pointer is decoded into 16 bits to zero-out all bytes before the pointer for scanning logic.

WAYBPTR(3:0)--Input from ICNXTBLK indicates the byte position of the branch taken pointer of way prediction. For reading, this pointer is decoded into 16 bits to zero-out all bytes after the pointer for scanning logic.

NEXTB(1:0)--Input from ICALIGN indicates that ICALIGN can accept any 8-byte block. This signal includes other hold inputs from MROM and Idecode.

NEWLINE(1:0)--Output to ICALIGN and ICFPC indicates the first (bit 0) or the second (bit 1) 8-byte is the starting of a new line. The current line can start at the second 8-byte. The PC and offset of instructions sending to the decode units should be adjusted accordingly.

VALSTART--Output to ICCNTL indicates a valid start-byte after the end pointer from ICPRED for the current lines of instructions. The pre-decoding stops and instructions is fetched from the array.

IC0POS1(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 0 of the first 8-byte.

IC1POS1(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 1 of the first 8-byte.

IC2POS1(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 2 of the first 8-byte.

IC3POS1(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 3 of the first 8-byte.

IC0POS2(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 0 of the second 8-byte.

IC1POS2(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 1 of the second 8-byte.

IC2POS2(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 2 of the second 8-byte.

IC3POS2(3:0)--Output to ICALIGN indicates the PC's byte position of the next instruction using the end bit for instruction 3 of the second 8-byte.

IC0VAL1(7:0)--Output to ICALIGN indicates valid bytes for instruction 0 of the first 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC1VAL1(7:0)--Output to ICALIGN indicates valid bytes for instruction 1 of the first 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC2VAL1(7:0)--Output to ICALIGN indicates valid bytes for instruction 2 of the first 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC3VAL1(7:0)--Output to ICALIGN indicates valid bytes for instruction 3 of the first 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

ICOVAL2(7:0)--Output to ICALIGN indicates valid bytes for instruction 0 of the second 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC1VAL2(7:0)--Output to ICALIGN indicates valid bytes for instruction 1 of the second 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC2VAL2(7:0)--Output to ICALIGN indicates valid bytes for instruction 2 of the second 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

IC3VAL2(7:0)--Output to ICALIGN indicates valid bytes for instruction 3 of the second 8-byte. The valid bytes are used for muxing of the bytes to early decoding. The valid bytes can continue to next 8-byte blocks until the end bit is detected.

ICENDB1(3:0)--Output to ICALIGN indicates if end-bits for 4 instructions are detected in the first 8-byte block. If the end-bit is not set, the instruction continue to the next 8-byte blocks.

ICENDB2(3:0)--Output to ICALIGN indicates if end-bits for 4 instructions are detected in the second 8-byte block. If the end-bit is not set, the instruction continue to the next 8-byte blocks.

ICFUNC(15:0)--Output to ICALIGN and MENG indicates functional-bits, bits 7:0 are for the first 8-byte block and bits 15:8 are for the second 8-byte block.

INVPTR(3:0)--Output to ICFPC indicates the start pointer of the invalid instruction which needs to be pre-decoded.

INVINST--Output to ICFPC and ICCNTL indicates the invalid instruction which needs to be pre-decoded. No valid byte should be sent to the ICALIGN.

MROMPTR(3:0)--Output to ICFPC and MROM indicates the start pointer of the MROM instruction

ICMROM(1:0)--Output to MENG, bit 0 indicates the current instruction is MROM, bit 1 indicates the MROM instruction continue to the next line (end-bit is not detected in the current line).

MROMFUL--Input from MENG indicates MENG cannot accept any more instruction.

IC8BSEL(5:0)--Output to ICALIGN controls the muxes from IB(127:0) to IB1(191:0). Bit 5:3 is for the upper 8-byte IB(127:64) and bit 2:0 is for the lower 8-byte IB(63:0). 001 is for muxing to IB1(63:0), the first 8-byte, 010 is for muxing to the second 8-byte, and 100 is for muxing to the third 8-byte.

INVAL2--Output to ICALIGN to invalidate the second 8-byte block which has been muxed to IB1(191:0) because the first 8-byte has more than 4 instructions or the taken branch invalidates the second 8-byte block.

BSTRD--Input from TAP indicates to read the array and compare to set the result.

BSTWR--Input from TAP indicates to write the array from input registers.

BSTSTOUT--Input from ICSTORE connects the BIST chain.

FLUSHON--Input from TAP indicates flushing register mode, the result latch should use BSTDIN instead of the compare input for flushing the result registers.

BSTSHF1--Input from TAP indicates shifting of the master latch of registers.

BSTSHF2--Input from TAP indicates shifting of the slave latch of registers.

BSTFALSE--Input from TAP indicates to invert the test pattern.

BSTIDOUT--Output to TAP indicates the result of the data chain from the ICSTORE and ICPDAT arrays.

ICTAGV

Processor 500 executes the fast X86 instructions directly and the instructions are written into the Icache regardless of the pre-decode information. The linear valid bit is used for the whole line of instructions, assuming that the BIU always fetches 16-bytes of data. The CMASTER indicates which way to put in the pre-fetch data and tag. Writing of the tag is done at the same time as writing the data into the ICSTORE, and writing of the linear valid bit is done at the same time as writing the pre-decode bits into the ICPDAT. The start and end bits are sufficient to validate the instruction. If branching to the middle of the line or instructions wrapping to the next line, the start and end bytes must be detected for each instruction or else the instruction must be pre-decoded again. The possible cases for invalid instructions are (1) branching to the opcode and skipping the prefix, (2) part of the wrapping instruction are replaced in the Icache, (3) part of the line was not pre-decoded because of branch instruction and branch target. Whenever the MMU is re-mapped or the CMASTER execute a certain instruction, all the LV bits can be cleared. The next access to the Icache would results into LV miss, the CMASTER may send new mapping information to the Icache regarding the way associative, the SU, and the new tag. In this case the Icache needs to write the ICTAGV with new information (including setting the LV bit) and read the other arrays.

From the branch prediction, tag address must be read from the ICTAGV in the next cycle to merge with the successor index for the predicted target address. The predicted target address must be sent to the decode units and to the functional units for comparison.

ICTAGV ORGANIZATION

The ICTAGV includes 2048 lines of:

20-bit Tag address.

2 Status bits (SU, LV).

The status bits need to be dual-port to read and write in the same clock cycle. The ICTAGV is organized as two sets of 64 rows by 224 columns and two sets of 64 rows by 128 columns. Each of the first two sets consists of 7-bit tag address, and each of the last two sets consists of 3-bit tag address and the SU or LV bit. The two status bits are dual port RAM cells. The SU uses the delayed PC to write, and the LV bit has the snooping index from CMASTER. The ICTAGV uses 64 rows for dual-port RAM and quick reading of tag address. For optimal performance the layout of the column should be 32 RAM cells, pre-charge, 32 RAM cells, write buffer and senamp. The row decoder should be in the middle of the array to drive 112 or 96 columns each way. Basically, the pre-charge and the row decoder should be crossed in the middle of the array. The row decoder for the dual port RAM should be build at one end of the array. The self-time column is used to generate internal clock for each set of the array. Pre-charge is gated by ICLK. The status bits muxed by the TAGHIT should be gated by ICLK to be valid for the second ICLK. The above layout is to ensure the minimum routing for the TAGHIT, and is shown in FIG. 12.

The BIST for the ICTAGV array uses 22 TAEC cells for reading and writing the arrays, as explained further below.

Signal list

ITADD(11:4)--Input from ICFPC indicates the address of instruction to access the array. Bits 11:5 are for the row decoder, bit 4 is for column select. Writing into the SU array is a delay of the index to next ICLK.

IVADD(11:4)--Input from ICFPC indicates the address of instruction to write the LV bit. Bits 11:5 are for the row decoder, bit 4 is for column select.

ICTAG(31:12)--Input from ICFPC indicates the address of instruction to compare with the tag arrays.

ICTVRD--Input from ICCNTL to read tag array.

ICTWR--Input from ICCNTL to write new tag.

ICCLRA--Input from ICCNTL to clear all valid bits.

ICSUWR--Input from ICCNTL to write the SU bit.

ICLVWR--Input from ICCNTL to write the LV bit.

SRTVRD--Input from ICCNTL to read tag for special register.

SRTVWR--Input from ICCNTL to write tag for special register.

ICSRBB(31:10)--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB. Bits 31:12 are the address, bit 11 is the supervisor/user, and bit 10 is the valid bit.

SETSEL(7:0)--Input from ICFPC indicates which set to read, no tag compare is needed.

TAGCHK--Input from ICCNTL to indicates the valid set is from TAGHIT or SETSEL.

TAGHIT(7:0)--Output indicates which set is selected to read instructions.

VALBIT(7:0)--Output indicates the valid bits of 8 sets, uses for way-prediction.

TVSU--Output indicates the supervisor/user mode of current block.

IBTARGET(31:12)--Output to decode unit indicates the predicted taken branch target for the line on instruction in the previous cycle. The predicted taken branch from ICNXTBLK provides only the index, the upper bits are read from ICTAGV in the next cycle.

BSTRD--Input from TAP indicates to read the array and compare to set the result.

BSTWR--Input from TAP indicates to write the array from input registers.

BSTNBOUT--Input from ICNXTBLK connects the BIST chain.

FLUSHON--Input from TAP indicates flushing register mode, the result latch should use BSTDIN instead of the compare input for flushing the result registers.

BSTSHF1--Input from TAP indicates shifting of the master latch of registers.

BSTSHF2--Input from TAP indicates shifting of the slave latch of registers.

BSTFALSE--Input from TAP indicates to invert the test pattern.

PORTSEL--Input from TAP indicates to select the second dual port.

BSTITOUT--Output to TAP indicates the result of the data chain from the ICNXTBLK and ICTAGV arrays.

ICNXTBLK

This block contains the branch prediction information for the Icache. An important feature for performance of superscalar/superpipelined microprocessors is branch prediction. As the number of pipeline stages and the number of functional units increase the cost of mis-prediction is high. The tag comparison and selection of the 8-way associative in ICTAGV takes more than one clock cycle to resolve. Processor 500 implements another prediction technique to pick one out of the 8 ways and to use the predicted way for fetching of next line to remove the bubble in the pipeline. Three bits are needed for this way prediction. Another two bits are needed to select one of the two branch targets for fetching the next predicted line. Without the two bits to select the branch targets, comparison of the start-byte position with the positions of the branch targets will cause the way-prediction to be more than one clock cycle. This speculatively selected line of instructions can be corrected in the next cycle from the proper TAGHIT and the branch prediction. The following rules are used to set up the ICNXTBLK:

During pre-decode, if there is an unconditional branch instruction, the fetching is stalled until the new target PC can be calculated. If the branch is direct, the target PC can be calculated in the next cycle in the ICFPC.

The backward taken conditional branch which the new target PC can be calculated in the ICPFC should also predict taken.

If the branch is indirect, the target PC is from the functional unit. The speculative way-prediction is updated with the successor index in the cycle following the target address access. If there is no pre-decoded taken branch, the speculative way-prediction is updated after fetching of the next sequential block. The index after accessing the array should be kept for 3 clock cycles before the way-prediction is known for updating.

From mis-prediction, the new target PC will be fetched and the selected set and successor index will be kept in a branch holding registers which will be discussed in next section.

For better branch prediction hit ratio, the ICNXTBLK will increase to 2 branch targets for both taken and non-taken branches, and pre-decode for the unconditional branches and taken branches. The pre-decoding also calculate the branch target address for the branch instructions if available. If there is a hit in the ICNXTBLK, the new target will be used for the new fetch PC. The taken branch will have higher priority to occupy the two targets in ICNXTBLK.

Processor 500 will implement two different branch predictors to maximize the performance. The next few sections discuss the Bimodal and Global predictors and the implementation of the combined branch predictor on Processor 500.

Bimodal Branch Prediction

This branch prediction uses a saturated counter for prediction. A 2-bit counter is used for taken/non-taken prediction. The most significant bit is used for taken/non-taken prediction. Since branch instructions are more likely to be taken than non-taken, the counter should initialize to 10 if the branch target address can be calculated. As the branch is taken, the counter increases by 1 and is saturated at 11. As the branch is not taken, the counter decreases by 1 and is saturated at 00. The bimodal branch prediction is better than a single bit prediction as the branch correct prediction is 88.09% instead of 82.29% for two targets prediction. The bimodal branch prediction behaves well for mostly taken or non-taken branch instruction and is worst as the conditional branches flip-flop between taken and non-taken. The cost is one extra bit per branch target in the ICNXTBLK, and extra logic for the counter.

Global Branch Prediction

This branch prediction is an independent branch predictor, not a part of the Icache. There are many different types of global branch prediction; Processor 500 uses the global branch prediction which has the highest branch correct prediction ratio. The prediction entries are indexed by an exclusive OR of the PC and the branch shift register, which is referred to as global sharing branch prediction. This global branch prediction has the branch correct prediction at 89.24%; the prediction improves as more branch history bits are used in the prediction. A single shift register records the direction taken/non-taken by the most recent n conditional branches. Since the branch history is global to all branches, global branch prediction takes advantage of two types of patterns, the direction taken by the current branch may depend strongly on the other recent branches, and the duplicating the behavior of local branch prediction (patterns of branches in loops). For Processor 500, since the highest priority of the two branch targets is taken branch, the global shift register includes both the conditional and unconditional branches. In a few cases, the non-taken conditional branches may not include in the global shift register. To match the number of entries in the Icache, the global branch prediction needs to have 2048 entries with 2 targets per entry. It is organized with 256 rows of 8-way associative. Eight bits are used to index the branch prediction table. The PC uses bit 11:4 for indexing the branch prediction table.

Processor 500's Combined Branch Prediction

Combining the Bimodal and Global branch predictions should give a better correct prediction ratio. A predictor counter is used to select which branch predictor is better for each individual branch instruction. This technique should give a higher correct prediction ratio than the above two prediction techniques; the prediction ratio can be shown to be 89.93%. The same saturated counter is used for the predictor counter: if the bimodal predictor is correct and the global predictor is incorrect then increase the counter until saturated; if the global predictor is correct and the bimodal predictor is incorrect then decrease the counter until saturated; else no change in the predictor counter. The most significant bit of the predictor counter is used for selecting the branch predictor. ICNXTBLK is implemented with the bimodal counter and the predictor counter. ICNXTBLK has 2 targets per instruction line, where each target consists of the following:

12 bits--successor index, need 11:4 for global table index, 11:0 for icache.

3 bits--for 8-way associative.

4 bits--byte position of the branch instruction within the current line.

2 bits--bimodal counter

2 bits--predictor counter

1 bit--valid target

The table for global branch predictor also has 2 targets per entry, where each entry consists of a 2-bit global counter. The bimodal and predictor counters must be able to update the count on every cycle. The least significant bit of the counters is dual ported. If the count is 10, predicted taken, the new count is 11. If the count is 01, predicted non-taken, the new count is 00. Only on branch mis-prediction does the most significant bit of the counters change state.

The successor index, way, and byte position are shared between the bimodal and global counters. The predictor counter selects between the bimodal and global counters. The combination of the counters is to predict branch instructions as taken/non-taken. In most cases, the shared target is sufficient for the two branch predictors. The branch may have two different targets depended on two different patterns of branch instructions. In this case, the global predictor may desire to have its own target. It would be very expensive in layout area to have 4 targets per 16 bytes of instruction. A diagram of ICNXTBLK is shown as FIG. 13.

Implementation of Global Branch Tag for Recovery

As discussed above, the global branch predictor needs a table with 256 rows, 8-way associative, and 2 targets per line. A shift register of 8 bits is needed for indexing. The global branch predictor shift register must be able to back track to the previous conditional branch which is mis-predicted. As each conditional branch is predicted, the direction of the branch is shifted into the shift register from right to left, 1 for taken and 0 for non-taken. The shift register needs a total of 24 bits and each of the bit beyond the 8 indexing bits needs to have a tag. The tag has 4 bits to indicate the conditional branch position in the shift register. FIROB has 6 lines of 4 instructions and the pipeline from fetch to dispatch can hold another 3 lines of 4 instructions for a total of 36 instructions. The average length of X86 instruction is 3 bytes, thus (36 instruction.times.3 bytes) 108 bytes are equivalent to 6.75 lines from the Icache. Each Icache line of instructions can have up to 2 branch targets, which is 14 branch instructions in the pipeline. The extra 16 bits in the shift register is sufficient to handle all branches in the pipeline. The shift register needs to keep track of all branch instructions. All the branch tags and the taken/non-taken bits are shifted in the shift register. The shift register tag (branch tag) is routed with the branch instruction to the functional units and FIROB. As the branch instruction is mis-predicted the branch tag is used to retreat the old 8 bits in the shift register to restore the shift register with new direction for the mis-predicted branch instruction.

Even though it is unlikely that the number of branch instructions in the pipeline exceeds 16, a mechanism is needed to detect the overflow of the global shift register. An extra valid bit is set for each branch in the global shift register. As the branch instruction is retired, the branch tag is returned to the global shift register to clear all the tail valid bits from the branch tag. As the global shift register is shifted, if the valid bit at the tail of the shift register is set, then the pipeline must stall for the branch instruction to retire from the FIROB.

In the global shift register, beside the taken/non-taken bits, the branch predictor count, the bimodal count, the global count, the valid bit, and the branch target number should be kept in the same global shift register which will be restored for updating of the counters and the branch target number in case of branch mis-prediction. The counters are 6 bits, the valid is 1 bit, the branch target number is 1 bit, the taken/non-taken is 1 bit, and the branch tag is 4 bits; the total bits in the shift register is 13. The branch target number is to update one of the two branch targets in the ICNXTBLK. Since the ICNXTBLK can keep only two branch targets, some of the branch instructions may not be detected and may not get a branch tag from the global shift register. If the mis-prediction was not in the branch prediction, a new entry should be setup. The counters will be restored and incremented/decremented before sending to the holding register for updating the mis-predicted block. The return stack in the ICFPC should also restore from mis-prediction.

The global shift register is set and shifted in the second ICLK as the branch prediction is determined. In later pipeline stages, the unconditional jump, call, and return instructions can be detected and change the direction of the fetched instruction. In this case, the global shift register must be restored. A new branch tag is setup for the unconditional jump, call, and return instructions. The only branch instructions without branch tags are the conditional branch instruction which are not recorded in the ICNXTBLK. The ICFPC must keep track of the branch instructions in the first 4 pipeline stages for recovery of the global shift register.

All the branches must be detected in pre-decoding and kept in the ICNXTBLK unless there are more than two branches. If the branch is mis-predicted and not detected in the prediction then there are more than two branches in the same line with the mis-predicted branch. On Processor 500, there are two branch targets, if the branch mis-prediction matches one of the target, then the mis-prediction will update the same target. If the branch mis-prediction was not in the ICNXTBLK, then one of the two branch targets must be selected to be replaced. Information is needed with each of the line PC, the associated branch information from dispatching is:

Taken/non-taken (1/0) for the two branch targets of the current line PC.

Current way selection of the line PC.

Taken/non-taken prediction with each branch instruction.

Global shift register branch tag with each branch instruction.

Valid branch tag indication with each instruction.

Non-taken is assumed for the invalid branch targets in the ICNXTBLK. Branch target bits and way select are sent with the PC to the FIROB. The FIROB returns the two branch target bits upon mis-prediction for replacement algorithm of the branch targets in the ICNXTBLK. The first priority for replacing the branch targets is non-taken. If both bits are set for the line of the mis-predicted branch, then random replacement based on the least significant bit of the address is used. For branch mis-prediction, the following information are returned from the FIROB:

Current branch way select.

Valid branch tag indication.

Branch tag.

Current branch index.

Taken/non-taken branch target bits of the line PC.

New branch target address.

A diagram of the global branch predictor is shown as FIG. 14.

Branch-Holding Register for Updating Branch Targets

Some processors use the successor index instead of the full address to limit the size of the array, the selected way for the successor index is known after the branch target is fetched from the Icache. Updating the ICNXTBLK with successor index and selected way required dual-port RAM. With two targets per line of instructions, the current dual-port RAM cells implementation of the ICNXTBLK would make the ICNXTBLK array larger than the ICSTORE array. There are two cases of updating the branch targets: during pre-decoding of taken branch instruction and branch mis-prediction. On Processor 500, an extra branch holding register for branch mis-prediction and pre-decoding branch instruction will be implemented. The branch holding register should always be compared to the PC address and forward the data instead of reading from the ICNXTBLK. When the next branch mis-prediction occurs, the FIROB sends the logical address PC. The successor index, the way select, and branch predictor counts are latched inside the ICNXTBLK to write into the array at a later convenient time. Since the way prediction array is dual-ported, it should be updated immediately instead of keeping in the branch holding register. The branch holding register will update the last mis-predicted branch target to the ICNXTBLK as the ICFPC takes one cycle to calculate the new linear address from the logical address. Another condition to write the branch holding register into the ICNXTBLK array is when external fetch is started. With the branch holding register, the ICNXTBLK array can be single-ported which is less than half the size of the dual-ported array. The branch holding register includes the branch address which is used for comparison and forwarding of data, the successor index, the update branch predictor count after reading of the new target line. The branch address register resides in the ICFPC for comparison to the current fetch PC. If the mis-prediction is a RETURN instruction, only the target selection of the way prediction should be updated.

The branch predictor counters are kept in the global shift register. If the mis-prediction returns a valid branch tag, then the counters increase or decrease before latching in the branch holding register. If the mis-prediction does not have a valid branch tag, then the bimodal counter is used with 10. The global shift register should restore the proper branch pattern and the return stack should remove the cancelled CALL/RETURN instructions.

WAY PREDICTION

Since the evaluation of the branch prediction takes two cycles which would create a bubble in the pipeline, the way-prediction is implemented for faster prediction. The way prediction predicts one of the 8-way associative will be hit, and uses the ICNXTBLK for the next fetch PC. The way-prediction is validated in the next cycle with the TAGHIT and the actual branch prediction. If the way is mis-predicted, a correct way will be selected for the 8-way latches in the ICPDAT and a new line will be fetched creating a bubble in the pipeline. Since the tag compare is not completed until the next clock cycle, the scanning logic should be done in parallel with the tag compare for optimal timing of fetching instruction. The scanning logic is implemented on all 8 ways pre-decode data and the outputs are selected by TAGHIT. With the way prediction, a single pre-decode data can be selected for scanning logic thus reducing the logic to one-eighth. The ICPDAT must implement a set of latches to keep the output data; in case of way mis-prediction, the correct data will be used for scanning logic in the next cycle. The branch prediction in the ICNXTBLK should be resolved in parallel with TAGHIT for the correct next line fetch in the third cycle. The instructions from the ICSTORE are not needed for aligning until the next clock cycle which will be selected by TAGHIT. The way select from branch prediction should be used to select the way instead of the way prediction. From branch prediction, there is no tag comparator for the upper address bits.

The way-predicting has 3 bits to mux the successor index and branch prediction from ICNXTBLK for accessing the Icache in the next cycle. Depending the current fetch PC's position, the way prediction can use one of the two branch targets or none for sequential. In order to access the next PC within a cycle, a target selection of 2 bits is needed. The target selection can also include the return stack option. The program for the target selection is:

00--sequential,

01--first branch target,

10--second branch target,

11--return stack.

The way prediction should provide the byte position of the return instruction so that the ICPDAT can invalidate all followed instructions. For speed, another 4 bits are needed to indicate the byte position pointer for the instruction after the taken branch instruction for ICPDAT. The ICPDAT can decode and invalidate the pre-decode data directly from this 4-bit branch pointer. If the 4-bit branch pointer is all zeros, no invalidation of the pre-decode data is needed.

The way prediction includes dual ported RAM cells because the information must be updated while reading data, the initial value for the way prediction should be the same as the current PC's set. The way prediction is not known for updating until the next clock cycles or until the early decoding of the return instruction. For convenience, a holding way register is used for updating of the way prediction in the fifth ICLK.

The way mis-prediction can be at two levels, the first level is the wrong predicted way and the second level is the wrong selected target. Way mis-prediction is from comparing the predicted way to the tag compares, a mis-prediction would have re-fetched the correct instruction line and a new fetch address as shown in case 1 of FIG. 15. If the way prediction is correct, the next level is the target selection mis-prediction, the recovery mechanism is shown in case 2 of FIG. 15. The return stack prediction is not known until ICLK4 to correct the fetch done in ICLK2, other target predictions are compared to the branch prediction in ICLK2 and re-fetch the next address in ICLK3 as shown in case 3 of FIG. 15.

ICNXTBLK ORGANIZATION

The ICNXTBLK consists of 2048 lines of 2 branch targets, each target consist of 24 bits:

12 bits--successor index, need 11:4 for global table index, 11:0 for icache.

3 bits--for 8-way associative.

4 bits--byte position.

2 bits--bimodal counter.

2 bits--predictor counter.

1 bit--valid target.

The least significant bits of the bimodal and predictor counters are dual ported for writing back the increment count after reading. For speculative prediction, the most significant bit of the counter should not change. The new value of the bimodal and predictor counters are speculative; if there is a branch mis-prediction, the corrected counters will be written from the branch holding register.

The ICNXTBLK also includes 2048 lines for way prediction which are dual ported:

3 Way-prediction bits.

2 Target-selection bits.

4 Taken branch byte-position bits.

The global branch prediction includes 2048 lines of 2 global counters which is organized as 256 rows for 8-way associative. The least significant bit of the global counter is dual ported for reading and writing the speculative prediction in the next cycle.

The ICNXTBLK is organized as 4 sets of 64 rows by 256 columns, 2 sets of 64 rows by 196 columns including some dual-ported columns, 1 set of 64 rows by 128 dual-ported column, 1 set of 64 rows by 96 dual-ported columns, 1 set of 64 rows by 64 dual-ported columns, and 1 set of global counter array. Each of the first two sets consist of 2.times.4 bits of successor index. The next two sets consists of 2.times.4 bits of successor index and 2.times.4 bits of the byte position. The next two sets consists of 2.times.2 bits bimodal counter, 2.times.2 bits predictor counter, and 2.times.3 bits 8-way associative, the least significant bits of the counters are dual-port. The next set consists of 4 bits of way branch byte pointer. The last two sets consist of the 3 bits way-prediction and 2 bits target selection which are dual-ported RAM cells. The least significant bits of the counters are dual ported to be updated on every cycle. To minimize routing and implementation of the branch holding register, the same associated bits of the two branch targets should be laid out in two sets opposite each other. The branch successor index is selected by the way and target prediction to access the ICACHE in next clock cycle. Because of this speed-path in way prediction for reading the Icache in the next cycle, the array for ICNXTBLK is 64 rows instead of 128 rows as for the ICSTORE array. For optimal performance the layout of the column should be 32 RAM cells, pre-charge, 32 RAM cells, write buffer and senamp. The row decoder should be in the middle of the array to drive 96 or 112 column each way. Basically, the pre-charge and the row decoder should be crossed in the middle of the array. The self-time column is used to generate internal clock for each set of the array. Pre-charge is gated by ICLK. The ICNXTBLK has two different outputs; the first output in the first cycle is based on the way-prediction, and the second output in the second cycle is based on TAGHIT. If the two outputs do not select the same set or are not both non-taken, the reading of instruction in the second cycle will be invalidated, creating a bubble in the pipeline. The second output should be gated with TAGHIT and ICLK to be valid in the second cycle.

The branch holding register may be built into the ICNXTBLK array. This means that the bits of the two targets must be alternated in the array to access the branch holding register. The array may be skewed to accommodate the bits into a single array. The global branch counter is also implemented as the array in ICNXTBLK. The shift register and the branch tag for mis-prediction recovery are also implemented next to the array.

The BIST uses 55 TAEC cells for reading and writing the arrays. See the section on BIST and ATPG. A diagram of ICNXTBLK layout is shown as FIG. 16.

Signal List

INADD(11:3)--Input from ICFPC indicates the address of instruction to access the array. Bits 11:5 are for the row decoder, bit 4 is for column select, bit 3 is for special register read/write to each target. This index should be delayed by 3 cycles to write data for the way prediction bits. This index should be latched into the branch holding register.

ICNVRD--Input from ICCNTL to read branch prediction array.

ICNWR--Input from ICCNTL to write branch prediction. This signal is asserted during pre-decoding, the ENDLINE and not PDTAKEN cause the branch holding register to be written into the array.

ICBCWR--Input from ICCNTL to write bimodal counter bits. The index is 2 cycle delay from INADD.

ICPSWR--Input from ICCNTL to write predictor counter bits. The index is 2 cycle delay from INADD.

ICGCWR--Input from ICCNTL to write global counter bits. The index is 2 cycle delay from INADD.

ICWWR--Input from ICCNTL to write way prediction bits. The index is 3 cycle delay from INADD.

INVBHREG--Input from FIROB to invalidate the branch holding register. The branch mis-prediction is speculative, an early branch can be mis-predicted at a later time.

WRBHREG--Input from ICCNTL to write the branch holding register with information from the global shift register or from ICPRED.

WRBHREG1--Input from ICCNTL to write the branch holding register with the way and successor index from accessing the array with information from the global shift register or from ICPRED. This signal is 1 cycle later than WRBHREG.

SRNRD--Input from ICCNTL to read branch prediction for special register.

SRNWR--Input from ICCNTL to write branch prediction for special register.

ICSRBB(28:0)--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB. Bits 23:0 are the branch target, bit 28:26 is the way-selected prediction, and bit 26:24 is way-target prediction. The array requires bit 3 of the address to read the whole line.

SETSEL(7:0)--Input from ICFPC indicates which set to read, no tag compare is needed.

TAGCHK--Input from ICCNTL to indicates the valid set is from TAGHIT or SETSEL.

TAGHIT(7:0)--Input from ICTAGV indicates which set is selected to read branch array.

ENDLINE--Input from ICPRED indicates that pre-decoding has reached the end of the line or encountered a taken branch instruction, the pre-decode data should be written into the array.

PDJMP--Input from ICPRED indicates the current instruction is a branch instruction. The branch holding register should be setup until pre-decoding of the whole line is completed. If there is a taken branch instruction, the new branch holding register must wait for BWAY and not update the ICNXTBLK until the next opportunity. The ICNXTBLK should send BTAG1 to the decode unit.

PDTAKEN--Input from ICPRED indicates the current instruction is taken branch (the taken branch target can be calculated). The predictor counter in the branch holding register should be setup until pre-decoding of the whole line is completed. The successor index and way associative will be sent to the ICPRED by ICFPC. The ICNXTBLK should send BTAKEN1(0) to decode unit.

GSRSHIFT(3:0)--Input from ICFPC indicates restoring the global shift register from mis-prediction of the RETURN instruction in decode.

MINDEX(14:0)--Input from ICFPC indicates new successor index from branch mis-prediction or new pre-decode taken branch instruction to latch into branch holding register.

MBTAG(3:0)--Input from ICFPC indicates the branch tag from branch mis-prediction to restore the global shift register, counters, byte position, and target number for updating the ICNXTBLK. The target number indicates which branch target to update. The byte position should not change for branch mis-prediction.

BWAY(2:0)--Input from ICFPC indicates new way associative from taken branch mis-prediction or new pre-decode taken branch instruction to latch into branch holding register and for way prediction. This signal is one cycle later than PDINDEX, MINDEX, or MBTAG. BWAY is accessing the next line.

BTAR(1:0)--Output to ICNXTBLK indicates the target of the current line for way prediction. This signal is three cycle after the current line access.

WAYBPTR(3:0)--Output to ICPDAT indicates the byte position of the branch taken pointer of way prediction. For reading, this pointer is decoded into 16 bits to zero-out all bytes after the pointer for scanning logic.

All the branch prediction signals to the decode units need to mux in the pre-decode branch information and STARTPTR as the first branch target. The branch target address is from the ICFPC as ICPC1 or ICPC2.

BPMSB(1:0)--Internal, indicates taken branch from the msb of the bimodal count of the two targets.

GPMSB(1:0)--Internal, indicates branch taken from the msb of the global count of the two targets.

PSMSB(1:0)--Internal, from the msb of the predictor count of the two targets, 1 indicates using the bimodal predictor, 0 indicates using the global predictor.

PTAKEN(1:0)--Internal, indicates if the branch targets are predicted taken. This signal is the multiplex of the above three signals.

STARTPTR(3:0)--Input from ICFPC indicates the start byte position of the instruction, the position of the branch target must be greater than the start byte. This byte pointer is latched into the branch holding register for pre-decode taken branch instruction and written into the array for pre-decode non-taken branch instruction.

ICBCOL1(3:0)--Internal and output to decode units, indicates the column of the first branch target in the ICNXTBLK for the lines of instructions being fetched. This signal must be greater or equal to STARTPTR. This signal qualifies the BTAG1 in the decode units.

ICBCOL2(3:0)--Internal and output to decode units, indicates the column of the second branch target in the ICNXTBLK for the lines of instructions being fetched. This signal must be greater or equal to STARTPTR. This signal qualifies the BTAG2 in the decode units.

BVAL1--Internal and output to decode units to qualify BTAG1, indicates the first branch target is greater or equal to STARTPTR.

BVAL2--Internal and output to decode units to qualify BTAG2, indicates the second branch target is greater or equal to STARTPTR.

BTAKEN1(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVALl. Bit 0 is the last line and bit 1 is new line.

BTAKEN2(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVAL2. Bit 0 is the last line and bit 1 is new line.

SINDEX(14:0)--Output indicates the successor index from branch prediction, selected by PTAKEN, BVAL1, and BVAL2.

BTAG1(3:0)--Output indicates the position of the first target branch instruction with respect to the global shift register in case of branch mis-prediction.

BTAG2(3:0)--Output indicates the position of the second target branch instruction with respect to the global shift register in case of branch mis-prediction.

BTAG1N(3:0)--Output indicates the position of the first target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

BTAG2N(3:0)--Output indicates the position of the second target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

ICPWAY(2:0)--Internal to select the index from way prediction. The branch prediction and targets are used in the ICNXTBLK to access the next line. This signal selects one of the eight way of successor indexes to ICFPC. The ICFPC needs to compare this signal against TAGHIT to validate the way prediction.

ICPTAR(1:0)--Output to ICFPC indicates which branch target to use to access the cache in the next cycle. 00--sequential, 01--return stack, 10--first branch target, and 11--second branch target. Bit 0 selects one of the two successor indexes before the way prediction. The ICFPC needs to compare this signal against the actual taken/non-taken branch prediction. For return stack, the decode unit should detect the return instruction.

WINDEX(14:0)--Output to ICFPC indicates the successor index from way prediction.

DISPBRN1(1:0)--Input from ICALIGN indicates the first predicted branch instruction dispatched to a decode unit. This signal is the OR of ICxBRNB1. Bit 0 is for the first 8-byte and bit 1 is for the second 8-byte of the line if NEWLINE(1) is set for the second 8-byte.

DISPBRN2(1:0)--Input from ICALIGN indicates the second predicted branch instruction dispatched to decode unit. This signal is the OR of ICxBRNB2. Bit 0 is for the first 8-byte and bit 1 is for the second 8-byte of the line if NEWLINE(1) is set for the second 8-byte.