US5826053A — Speculative instruction queue and method therefor…

Claim 1

Independent Claim 147 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a plurality of byte positions for storing a plurality of instruction bytes; first means for shifting said array by an amount corresponding to one or more instruction boundaries of instruction bytes stored therewithin; second means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes; third means for loading a plurality of instruction bytes into said array starting at said next available byte position, said plurality of instruction bytes being stored in speculative execution order; fourth means for simultaneously presenting said plurality of instruction bytes stored within said array to an instruction decoder; and means for indicating to said instruction decoder which of said byte positions hold valid instruction bytes appropriate for decoding.

Claim 2

Dependent Claim 147 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a plurality of byte positions for storing a plurality of instruction bytes; first means for shifting said array by an amount corresponding to one or more instruction boundaries of instruction bytes stored therewithin; second means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes; third means for loading a plurality of instruction bytes into said array starting at said next available byte position, said plurality of instruction bytes being stored in speculative execution order; fourth means for simultaneously presenting said plurality of instruction bytes stored within said array to an instruction decoder; and means for indicating to said instruction decoder which of said byte positions hold valid instruction bytes appropriate for decoding.

Claim 3

Dependent Claim 19 words

A speculative instruction queue as in claim 1 further comprising means for flushing said array of valid instruction bytes.

Claim 4

Dependent Claim 26 words

A speculative instruction queue as in claim 2 wherein said means for flushing said array comprises means for marking all of said byte positions as invalid.

Claim 5

Dependent Claim 154 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a plurality of byte positions for storing a plurality of instruction bytes; first means for shifting said array by an amount corresponding to one or more instruction boundaries of instruction bytes stored therewithin; second means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes; third means for loading a plurality of instruction bytes into said array starting at said next available byte position, said plurality of instruction bytes being stored in speculative execution order; and fourth means for simultaneously presenting said plurality of instruction bytes stored within said array to an instruction decoder; wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 6

Dependent Claim 154 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a plurality of byte positions for storing a plurality of instruction bytes; first means for shifting said array by an amount corresponding to one or more instruction boundaries of instruction bytes stored therewithin; second means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes; third means for loading a plurality of instruction bytes into said array starting at said next available byte position, said plurality of instruction bytes being stored in speculative execution order; and fourth means for simultaneously presenting said plurality of instruction bytes stored within said array to an instruction decoder; wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 7

Dependent Claim 51 words

A speculative instruction queue as in claim 4 wherein said first means comprises: fifth means for generating a plurality of instruction bytes representing a rotation of said instruction bytes stored within said array; and sixth means for selectively loading certain of said rotated plurality of stored instruction bytes into said array.

Claim 8

Dependent Claim 51 words

A speculative instruction queue as in claim 4 wherein said third means comprises: seventh means for generating a plurality of instruction bytes representing a rotation of instruction bytes retrieved from an instruction memory; and eighth means for selectively loading certain of said rotated plurality of retrieved instruction bytes into said array.

Claim 9

Dependent Claim 37 words

A speculative instruction queue as in claim 4 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents a starting byte of an instruction.

Claim 10

Dependent Claim 37 words

A speculative instruction queue as in claim 4 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents an ending byte of an instruction.

Claim 11

Dependent Claim 37 words

A speculative instruction queue as in claim 4 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents an opcode byte of an instruction.

Claim 12

Dependent Claim 59 words

A speculative instruction queue as in claim 4 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin was retrieved from an instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding or succeeding byte position of said array.

Claim 13

Dependent Claim 65 words

A speculative instruction queue as in claim 4 wherein each byte position of said array includes an indicator field for indicating, if asserted, whether a respective instruction byte stored therewithin represents an instruction byte valid for decode, dispatch, and speculative execution, and if deasserted, the respective byte position is available for loading an additional instruction byte, retrieved from an instruction memory, in speculative execution order.

Claim 14

Dependent Claim 194 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; and means for indicating to said instruction decoder which of said byte positions hold valid instruction bytes appropriate for decoding; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder.

Claim 15

Dependent Claim 194 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; and means for indicating to said instruction decoder which of said byte positions hold valid instruction bytes appropriate for decoding; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder.

Claim 16

Dependent Claim 19 words

A speculative instruction queue as in claim 12 further comprising means for flushing said array of valid instruction bytes.

Claim 17

Dependent Claim 26 words

A speculative instruction queue as in claim 13 wherein said means for flushing said array comprises means for marking all of said byte positions as invalid.

Claim 18

Dependent Claim 202 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 19

Dependent Claim 202 words

A speculative instruction queue for a processor of the type having a variable byte-length instruction format, comprising: an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 20

Dependent Claim 31 words

A speculative instruction queue as in claim 15 wherein said array comprises a first byte position representing said FIFO head, and further comprises a last byte position representing said FIFO tail.

Claim 21

Dependent Claim 36 words

A speculative instruction queue as in claim 15 wherein said array comprises a circular FIFO, wherein said FIFO head and said FIFO tail correspond to byte positions which dynamically change as shifting of said FIFO occurs.

Claim 22

Dependent Claim 31 words

A speculative instruction queue as in claim 15 wherein said plurality of byte positions is equal in number to the number of instruction bytes of the longest instruction of said processor.

Claim 23

Dependent Claim 31 words

A speculative instruction queue as in claim 15 wherein said plurality of byte positions is greater in number than the number of instruction bytes of the longest instruction of said processor.

Claim 24

Dependent Claim 30 words

A speculative instruction queue as in claim 15 wherein said plurality of byte positions is sufficient in number to store therewithin multiple complete instructions of average length of said processor.

Claim 25

Dependent Claim 43 words

A speculative instruction queue as in claim 15 wherein said load means comprises: fetch means for retrieving a plurality of instruction bytes from a cache memory; and pre-fetch means for retrieving a plurality of instruction bytes from a memory external to said processor.

Claim 26

Dependent Claim 56 words

A speculative instruction queue as in claim 15 wherein said load means comprises: alignment means for generating an aligned plurality of instruction bytes representing a rotation of said plurality of instruction bytes retrieved from said instruction memory; and first drive means for selectively loading certain bytes of said plurality of aligned instruction bytes into said array.

Claim 27

Dependent Claim 53 words

A speculative instruction queue as in claim 15 wherein said shift means comprises: first rotation means for generating a plurality of instruction bytes representing a rotation of the instruction bytes stored within said array; and second drive means for selectively loading certain of said rotated plurality of stored instruction bytes into said array.

Claim 28

Dependent Claim 31 words

A speculative instruction queue as in claim 15 further comprising means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes.

Claim 29

Dependent Claim 37 words

A speculative instruction queue as in claim 15 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents a starting byte of an instruction.

Claim 30

Dependent Claim 37 words

A speculative instruction queue as in claim 15 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents an ending byte of an instruction.

Claim 31

Dependent Claim 37 words

A speculative instruction queue as in claim 15 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin represents an opcode byte of an instruction.

Claim 32

Dependent Claim 57 words

A speculative instruction queue as in claim 15 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding byte position of said array.

Claim 33

Dependent Claim 57 words

A speculative instruction queue as in claim 15 wherein each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately succeeding byte position of said array.

Claim 34

Dependent Claim 65 words

A speculative instruction queue as in claim 15 wherein each byte position of said array includes an indicator field for indicating, if asserted, whether a respective instruction byte stored therewithin represents an instruction byte valid for decode, dispatch, and speculative execution, and if deasserted, the respective byte position is available for loading an additional instruction byte, retrieved from an instruction memory, in speculative execution order.

Claim 35

Dependent Claim 337 words

In a processor system of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, a method for providing to an instruction decoder an aligned instruction stream to facilitate instruction decoding, comprising: providing an array configured as a FIFO having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order; coupling an output of each of said byte positions to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes stored therewithin to said instruction decoder; maintaining control information for said array for communicating which of said byte positions contain valid instruction bytes stored therein, said valid instruction bytes suitable for decoding, and conversely for communicating which of said byte positions are invalid and therefore available for storing instruction bytes not yet present within said array; retrieving from said instruction memory a block of instruction bytes including a particular instruction byte corresponding to a particular address provided by said processor and predicted to execute subsequent to execution of valid instruction bytes already stored within said array, and further retrieving subsequent additional blocks containing subsequent predicted executed instruction bytes therefrom; storing those of said retrieved instruction bytes beginning with said particular instruction byte and continuing through each predicted executed instruction byte retrieved within said blocks of instruction bytes, said instruction bytes being stored into available invalid byte positions within said array and continuing as additional invalid byte positions become available; and shifting said instruction bytes stored within said array, in response to control signals received from said instruction decoder, by a number of byte positions corresponding to complete instructions stored therewithin and previously received by said instruction decoder, whereby the first of said byte positions, if valid, is maintained to correspond to a starting byte of a successive instruction to be next received by said instruction decoder to decode and dispatch for speculative execution, and if invalid, is reserved for subsequent storing of such an instruction byte.

Claim 36

Dependent Claim 337 words

In a processor system of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, a method for providing to an instruction decoder an aligned instruction stream to facilitate instruction decoding, comprising: providing an array configured as a FIFO having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order; coupling an output of each of said byte positions to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes stored therewithin to said instruction decoder; maintaining control information for said array for communicating which of said byte positions contain valid instruction bytes stored therein, said valid instruction bytes suitable for decoding, and conversely for communicating which of said byte positions are invalid and therefore available for storing instruction bytes not yet present within said array; retrieving from said instruction memory a block of instruction bytes including a particular instruction byte corresponding to a particular address provided by said processor and predicted to execute subsequent to execution of valid instruction bytes already stored within said array, and further retrieving subsequent additional blocks containing subsequent predicted executed instruction bytes therefrom; storing those of said retrieved instruction bytes beginning with said particular instruction byte and continuing through each predicted executed instruction byte retrieved within said blocks of instruction bytes, said instruction bytes being stored into available invalid byte positions within said array and continuing as additional invalid byte positions become available; and shifting said instruction bytes stored within said array, in response to control signals received from said instruction decoder, by a number of byte positions corresponding to complete instructions stored therewithin and previously received by said instruction decoder, whereby the first of said byte positions, if valid, is maintained to correspond to a starting byte of a successive instruction to be next received by said instruction decoder to decode and dispatch for speculative execution, and if invalid, is reserved for subsequent storing of such an instruction byte.

Claim 37

Dependent Claim 47 words

A method as in claim 31 wherein said plurality of byte positions is at least as great in number as the number of instruction bytes of the longest instruction of said processor, and is further sufficient in number to store therewithin multiple complete instructions of typical length.

Claim 38

Dependent Claim 14 words

A method as in claim 31 wherein said instruction memory comprises a cache memory.

Claim 39

Dependent Claim 19 words

A method as in claim 31 wherein said instruction memory comprises an external memory accessible via a processor bus.

Claim 40

Dependent Claim 15 words

A method as in claim 34 wherein said instruction memory further comprises a cache memory.

Claim 41

Dependent Claim 15 words

A method as in claim 31 wherein said instruction memory comprises a non-volatile semiconductor memory.

Claim 42

Dependent Claim 15 words

A method as in claim 31 wherein said instruction memory comprises a magnetic disk memory.

Claim 43

Dependent Claim 70 words

A method as in claim 31 wherein said storing step comprises: generating a plurality of instruction bytes representing a rotation of a given block of said instruction bytes retrieved from said instruction memory; masking certain of said byte positions of said retrieved and rotated instruction bytes to produce a second plurality of non-masked instruction bytes; loading said second plurality of non-masked instruction bytes into respective byte positions of said array.

Claim 44

Dependent Claim 29 words

A method as in claim 31 wherein said plurality of retrieved instruction bytes each include at least one indicator field for indicating information descriptive of a respective instruction byte.

Claim 45

Dependent Claim 88 words

A method as in claim 31 wherein the step of shifting said instruction bytes stored within said array comprises shifting by a number of byte positions corresponding to complete instructions stored therewithin and previously decoded and dispatched by said instruction decoder, whereby the first of said byte positions, if valid, is maintained to correspond to the first instruction byte of the successive instruction to be next decoded by said instruction decoder for dispatch and speculative execution, and if invalid, is reserved for subsequent storing of such instruction byte.

Claim 46

Dependent Claim 66 words

A method as in claim 40 wherein said shifting step further comprises: generating a plurality of instruction bytes representing a rotation of said instruction bytes stored within said array; masking certain of said byte positions of said stored and rotated instruction bytes to produce a first plurality of non-masked instruction bytes; loading said first plurality of non-masked instruction bytes into respective byte positions of said array.

Claim 47

Dependent Claim 74 words

A method as in claim 31 wherein the step of maintaining control information for communicating which of said byte positions contains valid instruction bytes stored therein, comprises providing an indicator field for each of said byte positions, asserting a first predetermined value of said indicator field for each byte position containing a valid instruction byte, and asserting a second predetermined value of said indicator field for each byte position containing an invalid instruction byte.

Claim 48

Dependent Claim 31 words

A method as in claim 42 further comprising the step of flushing the array of valid instruction bytes whenever said instruction bytes stored therewithin no longer represent predicted executed instruction bytes.

Claim 49

Dependent Claim 20 words

A method as in claim 43 wherein said step of flushing the array comprises marking all byte positions as invalid.

Claim 50

Dependent Claim 51 words

A method as in claim 31 wherein said retrieving step comprises: predecoding said instruction bytes retrieved from said instruction memory; and assigning a plurality of indicator fields corresponding to each of said predecoded instruction bytes, each of said plurality of indicator fields being descriptive of a respective instruction byte previously predecoded.

Claim 51

Dependent Claim 35 words

A method as in claim 45 wherein said storing step comprises storing into each of said byte positions within said array said plurality of indicator fields corresponding to each of said instruction bytes so stored.

Claim 52

Dependent Claim 40 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte represents a starting byte of an instruction.

Claim 53

Dependent Claim 40 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte represents an ending byte of an instruction.

Claim 54

Dependent Claim 40 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte represents an opcode byte of an instruction.

Claim 55

Dependent Claim 60 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding byte position of said array.

Claim 56

Dependent Claim 60 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately succeeding byte position of said array.

Claim 57

Dependent Claim 62 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating, if asserted, whether a respective instruction byte represents an instruction byte valid for decode, dispatch, and speculative execution, and if deasserted, whether a respective byte position is available for loading an additional instruction byte.

Claim 58

Dependent Claim 55 words

A method as in claim 46 wherein said plurality of indicator fields corresponding to each of said byte positions of said array includes an indicator field for indicating, for an instruction memory including an N-way set-associative cache memory, from which of N possible sets an instruction byte stored within a respective byte position was retrieved.

Claim 59

Dependent Claim 175 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means, seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; and means for indicating to said instruction decoder which of said instruction bytes provided thereto are valid instruction bytes appropriate for decoding.

Claim 60

Dependent Claim 175 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means, seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; and means for indicating to said instruction decoder which of said instruction bytes provided thereto are valid instruction bytes appropriate for decoding.

Claim 61

Dependent Claim 175 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means; and seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; wherein each of said instruction bytes includes a plurality of indicator fields for indicating information descriptive of a respective instruction byte.

Claim 62

Dependent Claim 175 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means; and seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; wherein each of said instruction bytes includes a plurality of indicator fields for indicating information descriptive of a respective instruction byte.

Claim 63

Dependent Claim 310 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means; and seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; wherein each of said instruction bytes includes an indicator field for indicating a particular property of a respective instruction byte, said property chosen from the group consisting of: whether a respective instruction byte represents a starting byte of an instruction; whether a respective instruction byte represents an ending byte of an instruction; whether a respective instruction byte represents an opcode byte of an instruction; whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an immediately preceding instruction byte; whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an immediately succeeding instruction byte; whether a respective instruction byte represents an instruction byte valid for decode, dispatch, and speculative execution; and for a respective instruction byte retrieved from an N-way set-associative cache memory, a value indicating from which of N possible sets said respective instruction byte was retrieved.

Claim 64

Dependent Claim 310 words

An instruction queue for a processor of the type having variable byte-length instructions stored with no particular byte alignment within an instruction memory, said instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: first means for storing a block of instruction bytes; second means for retrieving a block of unaligned instruction bytes from said instruction memory; third means for shifting said block of unaligned instruction bytes to produce a first shifted instruction byte block; fourth means for loading at least a portion of said first shifted instruction byte block into said storage means; fifth means for shifting said instruction bytes stored within said storage means to produce a second shifted instruction byte block; sixth means for loading at least a portion of said second shifted instruction byte block into said storage means; and seventh means for providing a plurality instruction bytes stored within said storage means to said instruction decoder; wherein each of said instruction bytes includes an indicator field for indicating a particular property of a respective instruction byte, said property chosen from the group consisting of: whether a respective instruction byte represents a starting byte of an instruction; whether a respective instruction byte represents an ending byte of an instruction; whether a respective instruction byte represents an opcode byte of an instruction; whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an immediately preceding instruction byte; whether a respective instruction byte was retrieved from said instruction memory using a non-sequential address compared to that of an immediately succeeding instruction byte; whether a respective instruction byte represents an instruction byte valid for decode, dispatch, and speculative execution; and for a respective instruction byte retrieved from an N-way set-associative cache memory, a value indicating from which of N possible sets said respective instruction byte was retrieved.

Claim 65

Dependent Claim 42 words

An instruction queue as in claim 56 wherein said second means comprises: fetch means for retrieving said block of instruction bytes from a cache memory; and pre-fetch means for retrieving said block of instruction bytes from a memory external to said processor.

Claim 66

Dependent Claim 56 words

An instruction queue as in claim 56 wherein said first means comprises an array having a plurality of byte positions, said array configured as a circular FIFO having a FIFO head and a FIFO tail, wherein said FIFO head and said FIFO tail correspond to byte positions which dynamically change as shifting of said FIFO occurs.

Claim 67

Dependent Claim 48 words

An instruction queue as in claim 58 wherein said plurality of byte positions is at least equal in number to the number of instruction bytes of the longest instruction of said processor, and sufficient in number to store therewithin multiple complete instructions of average length of said processor.

Claim 68

Dependent Claim 44 words

An instruction queue as in claim 58 wherein said third means for shifting comprises means for aligning any selected byte position of said block of unaligned instruction bytes to correspond to and be loaded subsequently into a particular byte position of said first means.

Claim 69

Dependent Claim 224 words

In a super-scalar CISC processor of the type having a variable byte-length instruction format wherein each CISC instruction is stored with no particular byte alignment within an instruction memory, and wherein each CISC instruction is mapped to a corresponding sequence of one or more internal RISC-like operations ("ROPs") for execution within a superscalar RISC-like core processor, a speculative instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: an array having a plurality of byte positions for storing a plurality of predecoded instruction bytes and for providing said plurality of predecoded instruction bytes to said instruction decoder; a retrieval block for retrieving a block of unaligned instruction bytes from said instruction memory; an array rotate block, responsive to said retrieved block of unaligned instruction bytes, for producing a first rotated instruction byte block; an array mask block for masking a portion of said first rotated instruction byte block and for driving a remaining non-masked portion thereof to respective inputs of said array for loading thereinto; an output rotate block, responsive to said plurality of instruction bytes stored within said array, for producing a second rotated instruction byte block; and an output mask block for masking a portion of said second rotated instruction byte block and for driving a remaining non-masked portion thereof to respective inputs of said array for loading thereinto.

Claim 70

Dependent Claim 224 words

In a super-scalar CISC processor of the type having a variable byte-length instruction format wherein each CISC instruction is stored with no particular byte alignment within an instruction memory, and wherein each CISC instruction is mapped to a corresponding sequence of one or more internal RISC-like operations ("ROPs") for execution within a superscalar RISC-like core processor, a speculative instruction queue for providing to an instruction decoder an aligned instruction stream, comprising: an array having a plurality of byte positions for storing a plurality of predecoded instruction bytes and for providing said plurality of predecoded instruction bytes to said instruction decoder; a retrieval block for retrieving a block of unaligned instruction bytes from said instruction memory; an array rotate block, responsive to said retrieved block of unaligned instruction bytes, for producing a first rotated instruction byte block; an array mask block for masking a portion of said first rotated instruction byte block and for driving a remaining non-masked portion thereof to respective inputs of said array for loading thereinto; an output rotate block, responsive to said plurality of instruction bytes stored within said array, for producing a second rotated instruction byte block; and an output mask block for masking a portion of said second rotated instruction byte block and for driving a remaining non-masked portion thereof to respective inputs of said array for loading thereinto.

Claim 71

Dependent Claim 18 words

A speculative instruction queue as in claim 61 wherein said super-scalar CISC processor executes the X86 instruction set.

Claim 72

Dependent Claim 31 words

A speculative instruction queue as in claim 61 wherein said plurality of byte positions is equal in number to the number of instruction bytes of the longest instruction of said processor.

Claim 73

Dependent Claim 31 words

A speculative instruction queue as in claim 61 wherein said plurality of byte positions is greater in number than the number of instruction bytes of the longest instruction of said processor.

Claim 74

Dependent Claim 31 words

A speculative instruction queue as in claim 61 further comprising means for indicating which of said plurality of byte positions within said array is next available for loading additional instruction bytes.

Claim 75

Dependent Claim 95 words

A speculative instruction queue as in claim 61 wherein said retrieval block, said array rotate block, said array mask block, said output rotate block, and said output mask block produce their respective outputs within a given processor cycle, thus providing to respective inputs of said array for loading thereinto a plurality of instruction bytes representing both instruction bytes previously stored within said array during a previous processor cycle, and newly retrieved instruction bytes within said given cycle, and thereby appearing upon said outputs of said array on a processor cycle subsequent to said given cycle.

Claim 76

Dependent Claim 32 words

A speculative instruction queue as in claim 61 wherein each of said predecoded instruction bytes includes an ROP field for indicating the number of ROPs into which each CISC instruction is mapped.

Claim 77

Dependent Claim 58 words

A speculative instruction queue as in claim 67 wherein said ROP field is set to a first value to indicate to said instruction decoder that a corresponding CISC instruction is mapped into one ROP, a second value to indicate two ROPs, a third value to indicate three ROPs, and a fourth value to indicate greater than three ROPs.

Claim 78

Dependent Claim 34 words

A speculative instruction queue as in claim 61 wherein said plurality of byte positions is sufficient in number to store therewithin and to provide to said instruction decoder multiple complete instructions of typical length.

Claim 79

Dependent Claim 18 words

A speculative instruction queue as in claim 69 wherein said plurality of byte positions equals 16 in number.

Claim 80

Dependent Claim 85 words

A speculative instruction queue as in claim 61 wherein each of said byte positions of said array includes an indicator field for indicating to said instruction decoder which of said byte positions hold valid instruction bytes, said indicator field having a first value to indicate a valid instruction byte corresponding thereto, and having a second value to indicate an invalid instruction byte corresponding thereto and represents a byte position available for loading an additional instruction byte, retrieved from an instruction memory, in speculative execution order.

Claim 81

Dependent Claim 19 words

A speculative instruction queue as in claim 71 further comprising means for flushing said array of valid instruction bytes.

Claim 82

Dependent Claim 26 words

A speculative instruction queue as in claim 72 wherein said means for flushing said array comprises means for marking all of said byte positions as invalid.

Claim 83

Dependent Claim 50 words

A speculative instruction queue as in claim 61 wherein said inputs to each of said byte positions of said array each comprise a wired-or bus for merging said non-masked portions of said first and second rotated instruction byte blocks into a single instruction byte block for loading into said array.

Claim 84

Dependent Claim 54 words

A speculative instruction queue as in claim 74 wherein each of said wired-or busses remains at an inactive value whenever said bus is driven by neither of said array mask block nor said output mask block, said inactive value corresponding to said second value of said indicator field for indicating an invalid instruction byte.

Claim 85

Dependent Claim 40 words

A speculative instruction queue as in claim 61 further comprising a queue control block, responsive to signals received from said instruction decoder, for controlling each of said array rotate block, array mask block, output rotate block, and output mask block.

Claim 86

Dependent Claim 94 words

A speculative instruction queue as in claim 76 wherein, for an instruction decoder capable of decoding up to M variable byte-length instructions stored within said instruction queue and dispatching up to N ROPs corresponding thereto, all within a given processor cycle, said queue control block comprises a plurality of generation blocks, each responsive to respective signals from said instruction decoder, for speculatively generating a plurality of control signals for shifting said array by a number of instruction bytes corresponding to the number of ROPs potentially dispatched by said instruction decoder within said given cycle.

Claim 87

Dependent Claim 63 words

A speculative instruction queue as in claim 77 wherein said queue control block comprises a plurality "N+1" of generation blocks, each responsive to respective signals from said instruction decoder, for speculatively generating control signals corresponding to the number of ROPs potentially dispatched within the given cycle, said "N+1" generation blocks corresponding, respectively, to the cases of zero ROPs dispatched through "N" ROPs dispatched.

Claim 88

Dependent Claim 58 words

A speculative instruction queue as in claim 78 wherein said queue control block further comprises a selection circuit, responsive to signals received from said instruction decoder indicating the number of ROPs actually dispatched in said given cycle, said selection circuit for selecting from said plurality of control signals those control signals corresponding to said number of ROPs dispatched.

Claim 89

Dependent Claim 200 words

A speculative instruction queue as in claim 61 wherein each of said byte positions of said array includes an indicator field for indicating a particular property of a respective instruction byte stored therewithin, said property chosen from the group consisting of: whether a respective instruction byte stored therewithin represents a starting byte of an instruction; whether a respective instruction byte stored therewithin represents an ending byte of an instruction; whether a respective instruction byte stored therewithin represents an opcode byte of an instruction; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding byte position of said array; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately subsequent byte position of said array; whether a respective instruction byte stored therewithin represents an instruction byte valid for decode, dispatch, and speculative execution; and for a respective instruction byte stored therewithin and retrieved from an N-way set-associative cache memory, a value indicating from which of N possible sets said respective instruction byte was retrieved.

Claim 90

Dependent Claim 58 words

A speculative instruction queue as in claim 80 further comprising scanning means for determining, for each starting byte of an instruction encountered within said array, whether a corresponding ending byte of an instruction is encountered before encountering a subsequent starting byte, and if an intervening ending byte is not so encountered, for indicating an instruction queue error condition.

Claim 91

Dependent Claim 47 words

A speculative instruction queue as in claim 81 further comprising means for flushing said array of valid instructions upon detecting said instruction queue error condition, requesting from said instruction decoder an address for an instruction to be next decoded, and retrieving said instruction from said instruction memory.

Claim 92

Dependent Claim 58 words

A speculative instruction queue as in claim 80 further comprising scanning means for determining, for each ending byte of an instruction encountered within said array, whether a corresponding starting byte of an instruction is encountered before encountering a subsequent ending byte, and if an intervening starting byte is not so encountered, for indicating an instruction queue error condition.

Claim 93

Dependent Claim 47 words

A speculative instruction queue as in claim 83 further comprising means for flushing said array of valid instructions upon detecting said instruction queue error condition, requesting from said instruction decoder an address for an instruction to be next decoded, and retrieving said instruction from said instruction memory.

Claim 94

Independent Claim 266 words

An apparatus for processing information comprising: an external memory for holding said 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; and a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder; wherein said instruction cache includes an instruction queue comprising an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 95

Independent Claim 266 words

An apparatus for processing information comprising: an external memory for holding said 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; and a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder; wherein said instruction cache includes an instruction queue comprising an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes at least one indicator field for storing information descriptive of a respective instruction byte stored therewithin.

Claim 96

Dependent Claim 35 words

An apparatus as in claim 85 wherein said external memory comprises a memory chosen from the group consisting of; secondary cache memory; a non-volatile semiconductor memory; a volatile semiconductor memory; and a magnetic disk memory.

Claim 97

Dependent Claim 14 words

An apparatus as in claim 85 wherein said processor executes the X86 instruction set.

Claim 98

Independent Claim 433 words

An apparatus for processing information comprising: an external memory for holding said 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; and a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder; wherein said instruction cache includes an instruction queue comprising an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes an indicator field for indicating a particular property of a respective instruction byte stored therewithin, said particular property chosen from the group consisting of: whether a respective instruction byte stored therewithin represents a starting byte of an instruction; whether a respective instruction byte stored therewithin represents an ending byte of an instruction; whether a respective instruction byte stored therewithin represents an opcode byte of an instruction; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding byte position of said array; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately subsequent byte position of said array; whether a respective instruction byte stored therewithin represents an instruction byte valid for decode, dispatch, and speculative execution; and for a respective instruction byte stored therewithin and retrieved from an N-way set-associative cache memory, a value indicating from which of N possible sets said respective instruction byte was retrieved.

Claim 99

Independent Claim 433 words

An apparatus for processing information comprising: an external memory for holding said 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; and a plurality of functional units, each coupled to the plurality of registers and coupled to the instruction decoder; wherein said instruction cache includes an instruction queue comprising an array configured as a FIFO having a FIFO head and a FIFO tail, said array having a plurality of byte positions for storing up to a corresponding plurality of instruction bytes in speculative execution order, each of said byte positions having an output coupled to an instruction decoder of said processor for simultaneously communicating each of said plurality of instruction bytes respectively stored therewithin to said instruction decoder; shift means coupled to said array and responsive to said instruction decoder for shifting instruction bytes stored within said array by a variable number of byte positions corresponding to complete instructions stored therewithin; and load means coupled to said array for loading a plurality of instruction bytes retrieved from an instruction memory into available byte positions of said array; wherein said array is loaded and shifted such that said FIFO head at all times contains a start byte of an instruction to be next decoded by said instruction decoder; and wherein each of said byte positions of said array includes an indicator field for indicating a particular property of a respective instruction byte stored therewithin, said particular property chosen from the group consisting of: whether a respective instruction byte stored therewithin represents a starting byte of an instruction; whether a respective instruction byte stored therewithin represents an ending byte of an instruction; whether a respective instruction byte stored therewithin represents an opcode byte of an instruction; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately preceding byte position of said array; whether a respective instruction byte stored therewithin was retrieved from said instruction memory using a non-sequential address compared to that of an instruction byte stored within an immediately subsequent byte position of said array; whether a respective instruction byte stored therewithin represents an instruction byte valid for decode, dispatch, and speculative execution; and for a respective instruction byte stored therewithin and retrieved from an N-way set-associative cache memory, a value indicating from which of N possible sets said respective instruction byte was retrieved.

Claim 100

Dependent Claim 36 words

An apparatus as in claim 88 wherein said external memory comprises a memory chosen from the group consisting of: a secondary cache memory; a non-volatile semiconductor memory; a volatile semiconductor memory; and a magnetic disk memory.

Claim 101

Dependent Claim 14 words

An apparatus as in claim 88 wherein said processor executes the X86 instruction set.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-10-19	2002-04-20	2002-10-20	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-10-19	2006-04-20	2006-10-20	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-10-19	2010-04-20	2010-10-20	$7700.00	Window Closed / Lapsed

Speculative instruction queue and method therefor particularly suitable for variable byte-length instructions

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag