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.
A pipeline process system, a super-scalar process system, or an out-of-order-execution process system is applied to an information processing device. A sequence of instructions containing a branch instruction, especially a subroutine, can be processed at a high speed using a branch history and a return address stack storing a return address corresponding to a subroutine call instruction. To successfully perform the process, when an instruction detected as a bit in the branch history is a subroutine return instruction, an address of a branched-to instruction registered in the branch history is compared with all return addresses stored in valid entries in the return address stack. A unit is provided to transmit a matching address as a return address of the return instruction to an instruction fetch unit for fetching an instruction.
A microprocessor capable of suppressing reduction in performance caused due to a cache miss when a specific command is issued. The processor according to the present invention comprises a command buffer/queue; an execution unit; a subroutine call decoder; a data cache control unit; an Addiu decoder for detecting an addiu command; a pre-fetch control section; an adder; a PAdr register; a selector; and an adder circuit. When a subroutine call occurs, a stack pointer is moved by an amount used in a subroutine, and data used in the subroutine is pre-fetched to be stored in an area used by the subroutine in a data cache. Therefore, it is possible to reduce cache miss penalties due to stack access which is apt to be generated at the time of a subroutine call.
An apparatus for storing predicted return addresses of instructions being executed by a pipelined processor, the apparatus includes a two part return address buffer that includes a speculative return address buffer and a committed return address buffer, both of which having multiple entries that may include predicted return addresses that have been pushed onto the return buffer.
A branch history information write control device in an instruction execution processing apparatus includes a memory unit storing an instruction string, and a branch prediction unit performing a branch prediction of a branch instruction. A control unit in the device controls the memory unit and the branch prediction unit in such a way that writing of branch history information in the branch prediction unit and control over fetching of the instruction string in the memory unit may not occur simultaneously so that no instruction fetch is held. A bypass unit in the device makes the branch history information of the branch instruction a research target of a branch prediction, where said control unit uses a counter to count several clock cycles (several states) to delay, for a period of several clock cycles (several states), the writing of the branch history information and control, beforehand, the fetching of the instruction string.
An apparatus for recognizing a subroutine call is disclosed. The apparatus includes a circuit comprising a first input for receiving contents of a register, a second input for receiving a non-sequential change in program flow, and a third input for receiving the next sequential address after the non-sequential change in program flow. The circuit is configured to compare the next sequential address and the contents of the register to determine whether the non-sequential change in program flow is a subroutine call.
