System and method of maintaining and utilizing multiple return stack buffers

• US 6,151,671 A
• Filed: 02/20/1998
• Issued: 11/21/2000
• Est. Priority Date: 02/20/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: D'Sa, Reynold V., Kyker, Alan B., Kalafatis, Stavros, Hebda, Rebecca E., Chaput, Robert B.
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): PATEL, GAUTAM
• Application Number:
  US09/027,407
• Time in Patent Office: 1,005 Days
• Field of Search: 712/239, 712/238, 712/202
• US Class Current: 712/239
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer

Abstract

An instruction pipeline in a microprocessor is provided. The instruction pipeline includes a plurality of pipeline units, each of the plurality of pipeline units processing a plurality of instructions. At least two of the plurality of pipeline units are a source of at least some of the instructions for the pipeline. The pipeline further includes at least two speculative return address stacks, each of the speculative return address stacks coupled is coupled to at least one of the instruction source units. Each of the speculative return return address stacks are capable of storing at least two speculative return addresses.

Claims

1. An instruction pipeline in a microprocessor, comprising:

an instruction fetch unit for fetching a plurality of macro-code instructions from a memory device, each of the plurality of macro-code instructions corresponding to at least one micro-code instruction, the instruction fetch unit capable of recognizing a subroutine CALL macro-code instruction, the instruction fetch unit determining a respective first return address for each subroutine CALL macro-code instruction recognized by the instruction fetch unit, the instruction fetch unit further capable of recognizing a RETURN FROM SUBROUTINE macro-code instruction;

a first return address stack, coupled to the instruction fetch unit, the instruction fetch unit pushing each respective first return address onto the first return address stack, wherein the instruction fetch unit pops one respective first return address from the first return address stack for each RETURN FROM SUBROUTINE macro-code instruction the instruction fetch unit recognizes;

a decode unit for decoding the each of the plurality of macro-code instructions into the at least one corresponding micro-code instruction, the decode unit capable of recognizing a subroutine CALL macro-code instruction, the decode unit determining a respective second return address for each subroutine CALL macro-code instruction recognized by the decode unit, the decode unit further capable of recognizing a RETURN FROM SUBROUTINE macro-code instruction;

a second return address stack, coupled to the decode unit, the decode unit pushing each respective second return address onto the second return address stack, and wherein the decode unit pops one respective second return address from the second return address stack for each RETURN FROM SUBROUTINE macro-code instruction the decode unit recognizes;

a third unit for executing each of the plurality of micro-code instructions;

a fourth unit for retiring each macro-code instruction corresponding to the executed plurality of micro-code instructions, the fourth unit capable of recognizing a subroutine CALL macro-code instruction, the fourth unit determining a respective third return address for each CALL macro-code instruction recognized by the fourth unit, the fourth unit further capable of recognizing a RETURN FROM SUBROUTINE macro-code instruction; and

a third return address stack, coupled to the fourth unit, the fourth unit pushing each third respective third return address onto the third return address stack, and wherein the fourth unit pops one respective third return address from the third return address stack for each RETURN FROM SUBROUTINE macro-code instruction the fourth unit recognizes.

2. A method for maintaining return address information in an instruction pipeline of a micro-processor, comprising the steps of:

fetching, by a first pipeline unit, a plurality of instructions from a memory device, the plurality of instructions including a subroutine CALL instruction;

detecting, by the first pipeline unit, the subroutine CALL instruction;

determining, by the first pipeline unit, a respective first return address as a function of the detected subroutine CALL macro-code instruction;

pushing the respective first return address onto a first return address stack;

transmitting the plurality of instructions to a second pipeline unit;

detecting, by the second pipeline unit, the subroutine CALL macro-code instruction;

determining, by the second pipeline unit, a respective second return address as a function of the detected subroutine CALL instruction;

pushing the respective second return address onto a second return address stack;

transmitting the plurality of instructions to a third pipeline unit;

detecting, by the third pipeline unit, the subroutine CALL instruction;

determining, by the third pipeline unit, a respective third return address as a function of the detected subroutine CALL instruction; and

pushing the respective third return address onto a third return address stack.

3. The method of claim 2, wherein the plurality of instructions includes a RETURN FROM SUBROUTINE instruction, and further comprising the steps of:

detecting, by the first pipeline unit, by the first pipeline unit, the RETURN FROM SUBROUTINE instruction;

popping the respective first return address from the first return address stack;

detecting, by the second pipeline unit, the RETURN FROM SUBROUTINE instruction;

popping the respective second return address from the second return address stack;

detecting, by the third pipeline unit, the RETURN FROM SUBROUTINE instruction; and

popping the respective third return address from the third return address stack.

4. The method of claim 3, wherein the plurality of instructions includes a conditional branch instruction, further comprising the steps of:

detecting, by the first unit, the conditional branch instruction;

predicting a branch direction for the conditional branch instruction; and

fetching, by the first unit, a further instruction as a function of the predicted branch direction.

5. The method of claim 2, further comprising the steps of:

decoding each of the plurality of instructions into at least one micro-code instruction;

assigning a respective sequence number to each of the at least one micro-code instruction;

maintaining a pointer into at least one of the first return address stack, the second address stack, and the third address stack;

updating the pointer each time a subroutine CALL instruction is detected by at least one of the first pipeline unit, the second pipeline unit, and the third pipeline unit; and

storing the pointer in a table as a function of each respective sequence number for each of the at least one micro-code instruction.

6. The method of claim 5, wherein the plurality of instructions includes a conditional branch instruction, further comprising the steps of:

detecting the conditional branch instruction;

predicting a branch direction for the conditional branch instruction;

executing at least one of the at least one micro-code instructions;

determining, at a function of the execution step, if the predicted branch direction is correct; and

if the predicted branch direction is not correct, retrieving the pointer from the table as a function of the sequence number assigned to at least one of the at least one micro-code instructions.