US 5,689,672 A · Pre-decoded instruction cache and method therefor particularly suitable for variable byte-length instructions

Abstract

An instruction cache for a superscalar processor having a variable byte-length instruction format, such as the X86 format, is organized as a 16K byte 4-way set-associative cache. An instruction store array is organized as 1024 blocks of 16 predecoded instruction bytes. The instruction bytes are prefetched and predecoded to facilitate the subsequent parallel decoding and mapping of up to four instructions into a sequence of one or more internal RISC-like operations (ROPs), and the parallel dispatch of up to 4 ROPs by an instruction decoder. Predecode bits are assigned to each instruction byte and are stored with the corresponding instruction byte in the instruction store array. The predecode bits include bits for identifying the starting, ending, and opcode bytes, and for specifying the number of ROPs that an instruction maps into. An address tag array is dual-ported and contains 1024 entries, each composed of a 20-bit address tag, a single valid bit for the entire block, and 16 individual byte-valid bits, one for each of the 16 corresponding instruction bytes within the instruction store array. A successor array is dual-ported and contains 1024 entries, each composed of a 14-bit successor index, a successor valid bit which indicates that the successor index stored in the successor array should be used to access the instruction store array or that no branch is predicted taken within the instruction block, and a block branch index which indicates the byte location within the current instruction block of the last instruction byte predicted to be executed.

Claims38

Dependent claims

An instruction cache for a processor of the type having a variable byte-length instruction format, comprising:

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes;
first means for prefetching a plurality of instruction bytes from an instruction source;
second means for predecoding each of the prefetched instruction bytes to determine the at least one corresponding predecode bit for each prefetched instruction byte, the at least one predecode bit including a field for indicating instruction boundaries among the plurality of prefetched instruction bytes;
third means for storing the plurality of prefetched instruction bytes and corresponding at least one predecode bit for each prefetched instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of instruction bytes and corresponding at least one predecode bit from an instruction block within the array to an instruction decoder of the processor;
wherein the variable byte-length instruction format is the X86 instruction set format, and wherein the at least one predecode bit corresponding to each of the instruction bytes includes a group of predecode bits collectively set to:
a first value to indicate that the corresponding instruction byte, as prefetched and predecoded, is a prefix byte;
a second value to indicate that the corresponding instruction byte, as prefetched and predecoded, is an opcode byte;
a third value to indicate that the corresponding instruction byte, as prefetched and predecoded, is a MODR/M byte;
a fourth value to indicate that the corresponding instruction byte, as prefetched and predecoded, is an S-I-B byte;
and
a fifth value to indicate that the corresponding instruction byte, as prefetched and predecoded, is a DISP/IMM byte.

10 more elements

In a super-scalar CISC processor of the type having a variable byte-length instruction format wherein each CISC instruction is mapped to a corresponding sequence of one or more internal RISC-like instructions for execution within a superscalar RISC-like core processor, an instruction cache comprising:

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of CISC instruction bytes and at least one corresponding predecode bit for each of the CISC instruction bytes;
first means for prefetching a plurality of CISC instruction bytes from an instruction source;
second means for predecoding each of the prefetched CISC instruction bytes to determine the at least one corresponding predecode bit for each prefetched CISC instruction byte, the at least one predecode bit including a field for indicating CISC instruction boundaries among the plurality of prefetched CISC instruction bytes;
third means for storing the plurality of prefetched CISC instruction bytes and corresponding at least one predecode bit for each prefetched CISC instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of CISC instruction bytes and corresponding at least one predecode bit from an instruction block within the array to an instruction decoder of the processor;
wherein the at least one predecode bit corresponding to each of the CISC instruction bytes includes:
a first bit for indicating, when asserted, that the corresponding CISC instruction byte, as prefetched and predecoded, is a starting byte of a CISC instruction;
and
a second bit for indicating, when asserted, that the corresponding CISC instruction byte, as prefetched and predecoded, is an ending byte of a CISC instruction.

7 more elements

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of CISC instruction bytes and at least one corresponding predecode bit for each of the CISC instruction bytes;
first means for prefetching a plurality of CISC instruction bytes from an instruction source;
second means for predecoding each of the prefetched CISC instruction bytes to determine the at least one corresponding predecode bit for each prefetched CISC instruction byte, the at least one predecode bit including a field for indicating CISC instruction boundaries among the plurality of prefetched CISC instruction bytes;
third means for storing the plurality of prefetched CISC instruction bytes and corresponding at least one predecode bit for each prefetched CISC instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of CISC instruction bytes and corresponding at least one predecode bit from an instruction block within the array to an instruction decoder of the processor;
wherein the at least one predecode bit corresponding to each of the CISC instruction bytes includes a first group of bits for identifying a CISC instruction byte according to which instruction fields, as prefetched and predecoded, are provided by the CISC instruction byte.

4 more elements

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of CISC instruction bytes and at least one corresponding predecode bit for each of the CISC instruction bytes;
first means for prefetching a plurality of CISC instruction bytes from an instruction source;
second means for predecoding each of the prefetched CISC instruction bytes to determine the at least one corresponding predecode bit for each prefetched CISC instruction byte, the at least one predecode bit including a field for indicating CISC instruction boundaries among the plurality of prefetched CISC instruction bytes;
third means for storing the plurality of prefetched CISC instruction bytes and corresponding at least one predecode bit for each prefetched CISC instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of CISC instruction bytes and corresponding at least one predecode bit from an instruction block within the array to an instruction decoder of the processor;
wherein the at least one predecode bit corresponding to each of the CISC instruction bytes includes a second group of bits for indicating whether the corresponding CISC instruction byte, as prefetched and predecoded, is a CISC opcode byte, and for indicating the number of internal RISC-like instructions that the corresponding CISC instruction, as prefetched and predecoded, is mapped into.

4 more elements

An instruction cache for a processor of the type having a variable byte-length instruction format, comprising:

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes;
first means for prefetching a plurality of instruction bytes from an instruction source;
second means for predecoding each of the prefetched instruction bytes to determine the at least one corresponding predecode bit for each prefetched instruction byte, the at least one predecode bit including a field for indicating instruction boundaries among the plurality of prefetched instruction bytes;
third means for storing the plurality of prefetched instruction bytes and corresponding at least one predecode bit for each prefetched instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of instruction bytes and corresponding at least one predecode bit from an instruction block within the array to an instruction decoder of the processor;
wherein said second means comprises:
a group of registers for storing a plurality of instruction bytes prefetched from said instruction source, said group of registers providing sufficient storage for storing instruction bytes corresponding to at least two instruction blocks of said instruction cache;
an assign block coupled to the group of registers for determining, in response to a starting point within said group of registers, the location of various individual instruction bytes corresponding to various instruction fields;
and
a lookup table block, coupled to the assign block, for receiving therefrom a plurality of instruction fields for a given instruction, and for returning thereto a plurality of status indicators and descriptor fields.

8 more elements

An apparatus for processing information comprising:

an external memory for holding the information;
and
a processor coupled to said external memory via a processor bus, said processor including
an instruction cache coupled to said external memory;
an instruction decoder coupled to said instruction cache;
a plurality of registers coupled to said external memory;
a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder;
wherein said instruction cache includes
an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes;
first means for prefetching a plurality of instruction bytes from said external memory;
second means for predecoding each of the prefetched instruction bytes to determine the at least one corresponding predecode bit for each prefetched instruction byte, the at least one predecode bit including a field for indicating instruction boundaries among the plurality of prefetched instruction bytes;
third means for storing the plurality of prefetched instruction bytes and corresponding at least one predecode bit for each prefetched instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of instruction bytes and corresponding at least one predecode bit from an instruction block within the array to the instruction decoder of the processor;
wherein said fourth means comprises:
a queue for buffering a plurality of instruction bytes;
means for loading instruction bytes into available positions of said queue;
and
means for shifting the instruction bytes within said queue in response to information received from said instruction decoder corresponding to the number of instruction bytes processed by said decoder, and for aligning unprocessed instruction bytes at the head of said queue.

16 more elements

An apparatus for processing information comprising:

an external memory for holding the information;
and
a processor coupled to said external memory via a processor bus, said processor including
an instruction cache coupled to said external memory;
an instruction decoder coupled to said instruction cache;
a plurality of registers coupled to said external memory;
a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder;
wherein said instruction cache includes
an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes;
first means for prefetching a plurality of instruction bytes from said external memory;
second means for predecoding each of the prefetched instruction bytes to determine the at least one corresponding predecode bit for each prefetched instruction byte, the at least one predecode bit including a field for indicating instruction boundaries among the plurality of prefetched instruction bytes;
third means for storing the plurality of prefetched instruction bytes and corresponding at least one predecode bit for each prefetched instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of instruction bytes and corresponding at least one predecode bit from an instruction block within the array to the instruction decoder of the processor;
wherein said array comprises:
a store array for storing said plurality of instruction blocks;
a tag array for storing a plurality of cache tags, each of said cache tags corresponding to a respective instruction block stored within said store array;
and
a successor array for storing branch information corresponding to each instruction block stored within said store array, said branch information indicating whether a branch instruction in stored within a corresponding instruction block, and if so, the location of the branch instruction within said instruction block.

16 more elements

An apparatus for processing information comprising:

an external memory for holding the information;
and
a processor coupled to said external memory via a processor bus, said processor including
an instruction cache coupled to said external memory
an instruction decoder coupled to said instruction cache;
a plurality of registers coupled to said external memory;
a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder;
wherein said instruction cache includes
an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes;
first means for prefetching a plurality of instruction bytes from said external memory;
second means for predecoding each of the prefetched instruction bytes to determine the at least one corresponding predecode bit for each prefetched instruction byte, the at least one predecode bit including a field for indicating instruction boundaries among the plurality of prefetched instruction bytes;
third means for storing the plurality of prefetched instruction bytes and corresponding at least one predecode bit for each prefetched instruction byte into an instruction block within the array;
and
fourth means for delivering a requested stream of instruction bytes and corresponding at least one predecode bit from an instruction block within the array to the instruction decoder of the processor;
wherein said second means comprises:
a group of registers for storing a plurality of instruction bytes prefetched from said instruction source, said group of registers providing sufficient storage for storing instruction bytes corresponding to at least two instruction blocks of said instruction cache;
an assign block coupled to the group of registers for determining, in response to a starting point within said group of registers, the location of various individual instruction bytes corresponding to various instruction fields;
and
a lookup table block, coupled to the assign block, for receiving therefrom a plurality of instruction fields for a given instruction, and for returning thereto a plurality of status indicators and descriptor fields.

16 more elements

An instruction cache for a processor of the type having a variable byte-length instruction format, comprising:

an array for storing a plurality of instruction blocks, each of the instruction blocks comprising a plurality of instruction bytes and at least one corresponding predecode bit for each of the instruction bytes, the at least one predecode bit indicating instruction boundaries among the plurality of prefetched instruction bytes;
wherein the at least one predecode bit indicates a property of the corresponding instruction byte, the property chosen from the group consisting of:
whether a respective instruction byte, as prefetched and predecoded, represents a starting byte of an instruction;
whether a respective instruction byte, as prefetched and predecoded, represents an ending byte of an instruction;
whether a respective instruction byte, as prefetched and predecoded, represents an opcode byte of an instruction;
which instruction fields are provided by a respective instruction byte, as prefetched and predecoded;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction prefix byte;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction MODR/M byte;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction S-I-B byte;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction DISP/IMM byte;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction opcode byte for an X86 instruction which is mapped into 1 internal RISC-like instruction;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction opcode byte for an X86 instruction which is mapped into a sequence of 2 internal RISC-like instructions;
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction opcode byte for an X86 instruction which is mapped into a sequence of 3 internal RISC-like instructions;
and
whether a respective instruction byte, as prefetched and predecoded, is an X86 instruction opcode byte for an X86 instruction which is mapped into a sequence of 4 or more internal RISC-like instructions.

12 more elements

Dependencies are inferred from the claim text.

Pre-decoded instruction cache and method therefor particularly suitable for variable byte-length instructions

Life of this patent

Pre-decoded instruction cache and method therefor particularly suitable for variable byte-length instructions

Life of this patent

Abstract

Claims38