Apparatus and method for instruction queue scanning

An apparatus for scanning primary instructions in an instruction queue of a superscalar processor having a plurality of dispatch positions, wherein each primary instruction includes an opcode and an opcode identifier to identifying the location of the opcode within the instruction queue, and wherein each primary instruction maps to a number of one or more secondary instructions, the apparatus having a plurality of stages corresponding to dispatch positions allocated to the primary instructions, each stage comprising:

• look-ahead signal generation logic having an input for receiving opcode identifiers, and a first output;
• a first group of opcode identifier masking circuits, each having:
• inputs for receiving opcode identifiers, the number of the ROP most recently allocated a dispatch position, and the number of ROPs to which the primary instruction maps;
• and
• outputs for furnishing masked/unmasked opcode identifiers, an incremented version of the number of the ROP most recently allocated a dispatch position, and the number of ROPs to which the primary instruction maps;
• and
• a second group of opcode identifier masking and blocking circuits;
• each having:
• inputs for receiving opcode identifiers, the number of the ROP most recently allocated a dispatch position, and the number of ROPs to which the primary instruction maps, and further having an input coupled to the first output of the look-ahead signal generation logic;
• and
• outputs for furnishing masked/unmasked opcode identifiers, an incremented version of the number of the ROP most recently allocated a dispatch position, and the number of ROPs to which the primary instruction maps.

An apparatus for scanning instructions in an instruction queue of a superscalar processor having a plurality of dispatch positions, wherein each instruction includes an opcode and an opcode identifier to identifying the location of the opcode within the instruction queue, and wherein each instruction maps to a number of one or more RISC-like operations ("ROPs"), the apparatus comprising:

• means for allocating the dispatch positions to the instructions depending on the number of ROPs to which each instructions maps and the number of dispatch positions available;
• and
• a plurality of stages respectively corresponding to the dispatch positions for identifying and reporting to the respective dispatch positions locations of opcodes in the instruction queue for instructions to which the dispatch positions are allocated in the allocating means;
• wherein each stage has an input array of opcode identifiers and an output array of opcode identifiers and comprises:
• means for identifying a location of the first opcode in the input array;
• and
• means for propagating opcode identifiers from the input array to the output array, the propagating array having the location identified in the identifying means masked when the corresponding dispatch position is a last-allocated dispatch positions to a particular instruction;
• the stages being serially coupled to one another with a leading one of the stages having the input array thereof coupled to the opcode identifiers in the instruction queue, and each of the other stages having the input array thereof coupled to the output array of an immediately preceding stage;
• and wherein each stage is partitioned into a plurality of groups of opcode identifier processing logic and includes look-ahead means providing inputs to higher order groups of the stage for reducing propagation delays within the stage.

An apparatus for scanning pre-decoded x86 instructions in an instruction queue of a superscalar processor having a plurality of dispatch positions, wherein each instruction includes an opcode and an opcode identifier bit to identifying the location of the opcode within the instruction queue, and wherein each instruction maps to a number of one or more RISC-like operations ("ROPs"), the apparatus comprising a first stage and a second stage, wherein the first stage comprises:

• first first opcode identification signal generation logic having an input coupled to the opcode bits and the opcode identifier bits of the instruction queue;
• partial dispatch signal generation logic having an input for receiving a partial dispatch signal;
• first look-ahead signal generation logic having an input coupled to the opcode bits and the opcode identifier bits of the instruction queue;
• a first group of bit masking logic having inputs coupled to a first field output of the first first opcode identification signal generation logic and to the partial dispatch signal generation logic, and having an output for identifying a location of an earliest-occurring opcode identifier bit in the first field of the instruction queue;
• a second group of bit masking logic having inputs coupled to a second field output of the first first opcode identification signal generation logic, to an output of the partial dispatch signal generation logic, and to an output of the first look-ahead signal generation logic, and having an output for identifying a location of an earliest-occurring opcode identifier bit in the second field of the instruction queue;
• and wherein the second stage comprises:
• second first opcode identification signal generation logic having an input coupled to an opcode bit output and an opcode identifier bit output of the first and second groups of bit masking logic;
• second look-ahead signal generation logic having an input coupled to the opcode bits and the opcode identifier bits of the instruction queue;
• a third group of bit masking logic having inputs coupled to a first field output of the second first opcode identification signal generation logic and to an opcode bit output and an opcode identifier bit output of the first group of bit masking logic;
• and
• a fourth group of bit masking logic having inputs coupled to a second field output of the second first opcode identification signal generation logic and to an opcode bit output and an opcode identifier bit output of the second group of bit masking logic.

A method for scanning a queue of primary instructions in a superscalar processor, the queue of primary instructions having one or more opcodes at respective locations in the queue identified by a first set of opcode location identifiers ("OLI"), wherein each primary instruction maps to a sequence of a number of one or more secondary instructions, the method comprising:

• identifying first and second subsets in the first set of OLIs;
• generating for a first dispatch position in the superscalar processor a second set of OLIs having first and second subsets in which any first asserted OLIs thereof are identified, the first and second subsets of the second set of OLIs corresponding to the first and second subsets of the first set of OLIs;
• generating for the first dispatch position a look-ahead signal if the first subset of the first set of OLIs does not include any asserted OLIs;
• applying the look-ahead signal for the first dispatch position to the second subset of the second set of OLIs to generate from the second set of OLIs a third set of OLIs for the first dispatch position indicating a first asserted OLI in the first set and not indicating any successively asserted OLIs in the first set;
• deriving a fourth set of OLIs from the first set;
• generating for a second dispatch position in the superscalar processor a fifth set of OLIs having first and second subsets in which any first asserted OLIs thereof are identified, the first and second subsets of the fifth set of OLIs corresponding to the first and second subsets of the fourth set of OLIs;
• generating for the second dispatch position a look-ahead signal if the first subset of the fourth set of OLIs does not include any asserted OLIs;
• applying the look-ahead signal for the second dispatch position to the second subset of the fifth set of OLIs to generate from the fifth set of OLIs a sixth set of OLIs for the second dispatch position indicating a first asserted OLI in the fourth set and not indicating any successively asserted OLIs in the fourth set.

A method for scanning a queue of primary instructions in a superscalar processor, the queue of primary instructions having one or more opcode bytes at respective locations in the queue respectively identified by asserted bits of a first array, wherein each primary instruction maps to a sequence of a number of one or more secondary instructions, the method comprising:

• identifying first and second subsets of bits in the first array;
• generating for a first dispatch position in the superscalar processor a second array having first and second subset of bits indicating first-asserted bits in respectively the first and second subsets of bits of the first array;
• generating for the first dispatch position a look-ahead signal if the first subset of bits in the first array does not include an asserted bit;
• applying the look-ahead signal for the first dispatch position to the second subset of bits of the second array to generate from the second array a third array of bits for the first dispatch position indicating a first asserted bit in the first array and not indicating any successively asserted bits in the first array;
• deriving a fourth array from the first array;
• identifying first and second subsets of bits in the fourth array;
• generating for a second dispatch position in the superscalar processor a fifth array having first and second subset of bits indicating first-asserted bits in respectively the first and second subsets of bits of the fourth array;
• generating for the second dispatch position a look-ahead signal if the first subset of bits in the fourth array does not include an asserted bit;
• applying the look-ahead signal for the second dispatch position to the second subset of bits of the fifth array to generate from the fifth array a sixth array of bits for the second dispatch position indicating a first asserted bit in the fourth array and not indicating any successively asserted bits in the fourth array.

A method for scanning instructions in an instruction queue of a superscalar processor having a plurality of dispatch positions and a plurality of respective scanning stages, wherein each instruction includes an opcode and an opcode identifier to identifying the location of the opcode within the instruction queue, and wherein each instruction maps to a number of one or more RISC-like operations ("ROPs"), the method comprising:

• allocating the dispatch positions to the instructions depending on the number of ROPs to which each instructions maps and the number of dispatch positions available;
• identifying locations of opcodes in the instruction queue for instructions to which the dispatch positions are allocated;
• reporting the opcode locations from the identifying step to the respective dispatch positions;
• on a stage-by-stage basis, wherein each stage has an input array of opcode identifiers and an output array of opcode identifiers:
• identifying a location of the first opcode in the input array;
• and
• propagating opcode identifiers from the input array to the output array, the propagating array having the location identified in the identifying means masked when the corresponding dispatch position is a last-allocated dispatch positions to a particular instruction;
• the stages being serially coupled to one another with a leading one of the stages having the input array thereof coupled to the opcode identifiers in the instruction queue, and each of the other stages having the input array thereof coupled to the output array of an immediately preceding stage;
• and
• wherein each stage is partitioned into a plurality of groups of opcode identifier processing logic:
• providing look-ahead signals to higher order groups of a stage for reducing propagation delays within the stage.