US 5,604,877 A · Method and apparatus for resolving return from subroutine instructions in a computer processor

Abstract

A method and apparatus for resolving Return From Subroutine instructions in a computer processor are disclosed. The method and apparatus resolve Return From Subroutine instructions in four stages. A first stage predicts Call Subroutine instructions and Return From Subroutine instructions within the instruction stream. The first stage stores a return address in a return register when a Call Subroutine instruction is predicted. The first stage predicts a return to the return address in the return register when a Return From Subroutine instruction is predicted. A second stage decodes each Call Subroutine and Return From Subroutine instruction in order to maintain a Return Stack Buffer that stores a stack of return addresses. Each time the second stage decodes a Call Subroutine instruction, a return address is pushed onto the Return Stack Buffer. Correspondingly, each time the second stage decodes a Return From Subroutine instruction, a return address is popped off of the Return Stack Buffer. The second stage verifies predictions made by the first stage and predicts return addresses for Return From Subroutine instructions that were not predicted by the first stage. A third stage executes Return From Subroutine instructions such that the predictions are verified. Finally, a fourth stage retires Return From Subroutine instructions and ensures that no instructions fetch after a mispredicted return address are committed into permanent state.

Claims28

Dependent claims

An apparatus for predicting return addresses for Return From Subroutine instructions, said apparatus comprising

a branch target buffer, said branch target buffer comprising a plurality of branch entries for storing information about a plurality of branch instructions;
a branch target buffer circuit, said branch target buffer circuit predicting said plurality of branch instructions in a stream of computer instructions using said information stored in said branch target buffer;
a return register, said branch target buffer circuit storing a return address into said return register after a Call Subroutine branch instruction is predicted by said branch target buffer circuit, said branch target buffer circuit predicting a branch to said return address in said return register when a Return From Subroutine branch instruction is predicted by said branch target buffer circuit;
and
a return register valid bit, said return register valid bit determining how said branch target buffer circuit predicts said return address for said Return From Subroutine instruction.

2 more elements

A method for handling Return From Subroutine instructions in a computer processor, said method comprising

predicting branch instructions using a branch target buffer circuit;
storing a return address in a return register when said branch target buffer circuit predicts a Call Subroutine instruction;
determining a return register valid bit status;
and
predicting said return address in said return register when said branch target buffer circuit predicts a Return From Subroutine instruction based on said return register valid bit status.

2 more elements

A branch instruction prediction mechanism in a computer processor, said branch instruction prediction mechanism predicting branch instructions within a stream of computer instructions, said branch instructions comprising Call Subroutine instructions and Return From Subroutine instructions, said branch instruction prediction mechanism comprising

a branch target buffer, said branch target buffer comprising a plurality of entries for storing information about said branch instructions;
a branch execution unit, said branch execution unit executing a plurality of branch instruction in said stream of computer instructions, said branch execution unit storing information about said executed branch instructions in said branch target buffer;
a branch target buffer circuit, said branch target buffer circuit predicting said executed branch instructions in said stream of computer instructions when said executed branch instructions are encountered again;
a return register, said branch target buffer circuit storing a return address into said return register after each said Call Subroutine instruction predicted by said branch target buffer circuit;
a return register valid bit, said return register valid bit associated with said return register determining source of said return address predicted by said branch target buffer circuit;
and
a return address prediction mechanism, said return address prediction mechanism predicting a branch to said return address stored in said return register when said each said Return From Subroutine instruction is predicted by said branch target buffer circuit based on a return register valid bit.

4 more elements

Dependencies are inferred from the claim text.

Method and apparatus for resolving return from subroutine instructions in a computer processor

Life of this patent

Method and apparatus for resolving return from subroutine instructions in a computer processor

Life of this patent

Abstract

Claims28