Apparatus and method for performing subroutine call and return operations

Abstract

An apparatus and a method for performing subroutine call and return operations in a computer having a processor with an instruction prefetch mechanism which includes a branch history table for storing target addresses of a plurality of branch instructions found in an instruction stream. The branch history table 22 contains a potential call instruction tag 37 and a return instruction tag 39. For each potential subroutine call instruction found in a prefetch instruction stream an address pair containing the call target address and the next sequential instruction address of the instruction is stored in a return identification stack 24. Subsequently detected branch instructions initiate an associative search on the next sequential instruction part in the return identification stack where a matching entry identifies the branch instruction as a return instruction. The address pair contained in the matching entry is then transferred to a return cache 30 which is arranged in parallel to the branch history table. The branch history table and the return cache are simultaneously accessed in the same operation cycle with the address 28 of each prefetched instruction, and if by the access a return instruction tag is found, the next sequential instruction address from the return cache is used as return address. A return cache update 32 is performed in response to a branch instruction in the instruction stream by a lookup of the return cache for an entry having a corresponding target address and by replacing the next sequential instruction address in said entry by the next sequential address of said branch instruction.