Range finding circuit for selecting a consecutive sequence of reorder buffer entries using circular carry lookahead

A range-finding circuit comprising:

• a plurality of look-ahead cells arranged in an array according to a hierarchical significance, each look-ahead cell receiving the hierarchical portion of the bits of a first multiple-bit pointer, the hierarchical portion of the bits of a second multiple-bit pointer, and a carry of a plurality of carries arranged according to the hierarchical significance, each look-ahead cell including:
• a generate circuit input coupled to the hierarchical portion of the first and second pointers to furnish, as a function thereof, a generate of a plurality of generates arranged according to the hierarchical significance;
• a propagate circuit input coupled to the hierarchical portion of the first and second pointers to furnish, as a function thereof, a propagate of a plurality of propagates arranged according to the hierarchical significance;
• and
• an enable circuit input coupled to the hierarchical portion of the first and second pointers and input coupled to the carry to furnish the hierarchical portion of the bits of a multiple-bit range designated by the pointers in which range bits between the pointers are assigned a first logic level and range bits outside the pointers are assigned a second opposite logic level;
• and
• a circular propagate carry circuit coupled to the plurality of look-ahead cells to receive the generates and propagates and to furnish the carries as a function thereof.

A method for assigning bit values to a multiple-bit range, comprising the steps of:

• receiving a multiple-bit enabling pointer and a multiple-bit disabling pointer;
• distributing bits of the enabling and disabling pointers into a plurality of portions in an order of hierarchical significance:
• for each hierarchical portion of the enabling pointer and the disabling pointer, receiving the pointers and a carry and in response thereto, determining a generate, a propagate and a carry for an hierarchical portion of the range,
• the carry, generate and propagate being ones of a plurality of respective carries, generates and propagates arranged according to the hierarchical significance;
• and
• analyzing the plurality of generates and propagates determined for all portions of the pointers and determining carries for each portion therefrom;
• wherein the step of determining each hierarchical portion of the range comprises the steps of:
• enabling any range bits of the hierarchical portion having a hierarchical significance subsequent to the enabling pointer within the portion or a carry into the portion and having a hierarchical significance antecedent to the disabling pointer within the portion, if any;
• and
• disabling other range bits of the hierarchical portion.

A dependency logic circuit comprising:

• a compare/hit circuit coupled to an operand pointer and coupled to a plurality of destination pointers and destination signals, the compare/hit circuit for detecting an operand pointer that is equal to an asserted destination pointer signal;
• a range-finding circuit including:
• a plurality of cells arranged in a ordered array,
• each cell being input coupled to a carry, to an ordered portion of bits of a first multiple-bit pointer and to an ordered portion of bits of a second multiple-bit pointer and
• each cell being output coupled to a generate, to a propagate and to an ordered portion of bits of a multiple-bit range which corresponds to the ordered portions of first and second pointers,
• the carry, generate and propagate being respective elements of a plurality of ordered carries, generates and propagates, and
• the pointers designating a range in which range bits between the pointers are assigned a first logic level and range bits outside the pointers are assigned a second opposite logic level;
• and
• a propagating circuit coupled to the plurality of cells to receive the ordered generates and propagates and to furnish the ordered carries as a function thereof;
• and
• an AND circuit coupled to the compare/hit circuit and the range finding circuit, the AND circuit for detecting an operand pointer that is equal to an asserted destination pointer signal within the range designated by the range-finding circuit.

A dependency logic circuit comprising:

• a compare/hit circuit coupled to an operand pointer and coupled to a plurality of destination pointers and destination signals, the compare/hit circuit for detecting an operand pointer that is equal to an asserted destination pointer signal;
• a range-finding circuit including:
• a plurality of look-ahead cells arranged in an array according to a hierarchical significance, each look-ahead cell receiving the hierarchical portion of the bits of a first multiple-bit pointer, the hierarchical portion of the bits of a second multiple-bit pointer, and a carry of a plurality of carries arranged according to the hierarchical significance, each look-ahead cell including:
• a generate circuit input coupled to the hierarchical portion of the first and second pointers to furnish, as a function thereof, a generate of a plurality of generates arranged according to the hierarchical significance;
• a propagate circuit input coupled to the hierarchical portion of the first and second pointers to furnish, as a function thereof, a propagate of a plurality of propagates arranged according to the hierarchical significance;
• and
• an enable circuit input coupled to the hierarchical portion of the first and second pointers and input coupled to the carry to famish the hierarchical portion of the bits of a multiple-bit range designated by the pointers in which range bits between the pointers are assigned a first logic level and range bits outside the pointers are assigned a second opposite logic level;
• and
• a circular propagate carry circuit coupled to the plurality of look-ahead cells to receive the generates and propagates and to furnish the carries as a function thereof;
• and
• an AND circuit coupled to the compare/hit circuit and the range finding circuit, the AND circuit for detecting an operand pointer that is equal to an asserted destination pointer signal within the range designated by the range-finding circuit.