Subroutine return prediction mechanism using ring buffer and comparing predicated address with actual address to validate or flush the pipeline

A computer pipeline comprising:

• a) an instruction cache which stores coded instructions and has an input that receives a program count which indexes the coded instructions, and an output at which the indexed coded instructions are provided;
• b) an instruction fetching decoder having an input coupled to the instruction cache output and which decodes the coded instructions, and having as outputs:
• i) a subroutine call address when the coded instruction is a subroutine call instruction,
• ii) a multiplexer control signal which indicates whether the coded instruction is a return instruction, the call instruction or neither,
• iii) a ring pointer counter control signal which is a first value when the coded instruction is a return instruction and a second value when the coded instruction is the call instruction, and
• iv) a decoded instruction;
• b) an execution stage coupled to the instruction fetching decoder which executes the decoded instruction;
• c) a program counter coupled to the input of the instruction cache and having an output at which is provided the program count to the instruction cache input;
• d) a multiplexer having a plurality of inputs, a control input coupled to the multiplexer control signal output of the instruction fetching decoder, and an output coupled to the program counter input;
• e) an adder having a an input coupled to the output of the program counter and an output coupled to one of said multiplexer inputs at which is provided a value equal to the program count plus one;
• f) a ring pointer counter having an input coupled to the instruction fetching decoder to receive the ring pointer counter control signal, and containing a ring pointer which points to buffer locations in response to the ring pointer counter control signal, said ring pointer being incremented when the instruction fetching decoder decodes a subroutine call instruction and being decremented when the instruction fetching decoder decodes a subroutine return instruction;
• g) a ring buffer having an input coupled to the adder output, a plurality of buffer locations, and an output coupled to one of said multiplexer inputs, said ring buffer storing said value received from the adder output as a return value in the buffer location pointed to by said ring pointer when a subroutine call instruction is decoded and providing said return value from the buffer location pointed to by the ring pointer at the ring buffer output when a subroutine return instruction is decoded, said return value at said ring buffer output being the predicted subroutine return address;
• h) the multiplexer operating to output:
• i) the subroutine call address when the multiplexer control signal is indicative of the subroutine call instruction,
• ii) the predicted return address when the multiplexer is indicative of the subroutine return instruction, and
• iii) the output of the adder when the multiplexer control signal is indicative of neither the subroutine call instruction nor the subroutine return instruction;
• and
• i) a comparison unit coupled to said ring buffer and to said execution stage, the comparison unit comparing an actual return address produced by the execution stage in response to the processing of the return instruction with the predicted return address for that return instruction, and having an output at which is provided a mis-comparison signal when the actual return address is not the same as the predicted return address, the mis-comparison signal being coupled to the computer pipeline to cause the computer pipeline to flush the computer pipeline when the actual return address is not the same as the predicted return address.

A method of predicting subroutine return addresses in a pipelines computer comprising:

• (a) storing in one of a plurality of buffer locations in a ring buffer a value equal to one plus an address of a call instruction in response to that call instruction;
• (b) pointing to the buffer location containing the most recently stored value;
• (c) providing the pointed to most recently stored value as an output in response to a return instruction, said output being the predicted subroutine return address;
• (d) pointing to the buffer location containing the next most recently stored value;
• (e) comparing an actual return address produced by the computer pipeline in response to the processing of the return instruction with the predicted return address for that return instruction to determine whether the predicted return address is valid;
• and
• (f) when the determination indicates that the predicted return address is not valid, generating a mis-comparison signal to cause a flush of the computer pipeline.