Return target address prediction by moving entry pointer to return stack popped at completion to deeper one at return instruction fetch

An information processing device, comprising:

• an instruction fetch controller to control executing:
• maintaining a branch history in which an instruction address of a branch instruction and an address of a branched-to instruction for use when a branch is taken are registered as a set of data for the branch instruction;
• maintaining a return address stack having a top-of-stack and pushing a returned- to instruction address of a subroutine when a subroutine call instruction is completely executed and popping the return address stack when a subroutine return instruction is completely executed;
• reporting completion of instruction execution;
• predicting a return address of a subroutine during an instruction fetching by designating as a predicted return address a designate entry in the return address stack storing return addresses of subroutine calls;
• and
• fetching a predicted return address of a subroutine using the return address stored in a designate entry of the return address stack,
• wherein the designating of the designate entry in the return address stack includes computing a position of the designate entry in the return address stack relative to a leading entry of the return address stack by:
• when a subroutine call instruction is predicted during an instruction fetching, changing the designate entry independently of a push or pop operation of the return address stack to indicate a one-step shallower entry of the return address stack relative to the leading entry of the return address stack,
• when a subroutine return instruction is predicted during an instruction fetching, changing the designate entry independently of a push or pop operation of the return address stack to indicate a one-step deeper entry of the return address stack relative to the leading entry of the return address stack and, and
• changing the designate entry depending upon a push and pop operation of the return address stack when a subroutine call and a subroutine return instruction is completely executed according to the reporting of completion of instruction execution,
• thereby keeping a position of the designate entry relative to the leading entry of the return address stack, and
• wherein an entry in the return address stack as a predicted return address of a subroutine is designated under a condition that an instruction is fetched from a main storage device, the instruction is detected as a hit in the branch history, and the instruction is determined as a return instruction from the subroutine.

An instruction fetch control method, comprising:

• pushing onto a return address stack a returned-to instruction address of a subroutine when a subroutine call instruction is completely executed and popping the return address stack when a subroutine return instruction is completely executed;
• determining whether a fetched instruction resulting in a hit in a branch history, containing an address of a branch instruction and a branched-to-instruction, is a return instruction;
• signaling completion of instruction execution;
• predicting a return address of a subroutine during an instruction fetching by designating as a predicted return address a designate entry in the return address stack storing return addresses of subroutine calls;
• and
• fetching a predicted return address of a subroutine using the return address stored in a designate entry of the return address stack,
• wherein the designating of the designate entry in the return address stack includes computing a position of the designate entry in the return address stack relative to a leading entry of the return address stack by:
• when a subroutine call instruction is predicted during an instruction fetching, changing the designate entry independently of a push or pop operation of the return address stack to indicate a one-step shallower entry of the return address stack relative to the leading entry of the return address stack,
• when a subroutine return instruction is predicted during an instruction fetching, changing the designate entry independently of a push or pop operation of the return address stack to indicate a one-step deeper entry of the return address stack relative to the leading entry of the return address stack and, and
• changing the designate entry depending upon a push and pop operation of the return address stack when a subroutine call and a subroutine return instruction is completely executed according to the reporting of completion of instruction execution,
• thereby keeping a position of the designate entry relative to the leading entry of the return address stack,
• wherein an entry in the return address stack as a predicted return address of a subroutine is designated under a condition that an instruction is fetched from a main storage device, the instruction is detected as a hit in the branch history, and the instruction is determined as a return instruction from the subroutine.