Browse Prior Art Database

Highly Accurate Subroutine Stack Prediction Mechanism

IP.com Disclosure Number: IPCOM000060383D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Emma, PG: AUTHOR [+4]

Abstract

A subroutine stack is a push-down stack that is used for guessing the return addresses of subroutine calls. Subroutine calls are usually implemented with the instructions BAL, BALR, BAS, and BASR. Returns are performed via a branch on condition register (BCR) instruction. The calling instruction specifies a register into which the next sequential address to the calling instruction is loaded (the link register), and it specifies an entry point into the subroutine by returning to the address specified in this register, i.e., the next sequential to the caller (or link). It has been determined that if a stack is kept onto which the link register is pushed at the time of a call, it is frequently the case that a subsequent BCR will branch to the address given by the top entry on the stack.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Highly Accurate Subroutine Stack Prediction Mechanism

A subroutine stack is a push-down stack that is used for guessing the return addresses of subroutine calls. Subroutine calls are usually implemented with the instructions BAL, BALR, BAS, and BASR. Returns are performed via a branch on condition register (BCR) instruction. The calling instruction specifies a register into which the next sequential address to the calling instruction is loaded (the link register), and it specifies an entry point into the subroutine by returning to the address specified in this register, i.e., the next sequential to the caller (or link). It has been determined that if a stack is kept onto which the link register is pushed at the time of a call, it is frequently the case that a subsequent BCR will branch to the address given by the top entry on the stack. Since the stack is a push-pop stack, this particular phenomena does not preclude subroutine nesting. BCR instructions are accurately predicted by a decode history table (DHT) (i.e., they are persistent in action), yet they have extremely low accuracy in a branch history table (BHT). Since the major difference between a BHT and a DHT is that the BHT attempts to predict the target address as well as the branch action, it would appear that BCRs change their target address.

Indeed, this is the case since a subroutine when called by procedure A will return to procedure A (via a BCR), and when it is called by procedure B, it will return to procedure B (via the same BCR). Since there was no apparent way of distinguishing which of the BAL and BALR instructions were, in fact, implementing a subroutine call, and no apparent way of distinguishing which of the BCR instructions were in fact subroutine returns, in view of the determination above, the broad assumption is that all BALs and BALRs were calls, and all BCRs were returns. Thus, in such a stack, all BALs and BALRs cause the link register to be pushed, and all taken BCRs cause the stack to be popped. This resulted in an improvement in accuracy over the BHT, yet the improvement was less dramatic than might have been expected. This is because not all BALs and BALRs are calls, and not all BCRs are returns. Thus, this type stack would attempt prediction in many cases that were inappropriate, and would subsequently make many erroneous predictions. The proposed mechanism is a stack that is able to recognize such cases. Thus, this stack will not predict as frequently as the just described stack, but when it does predict, it predicts correctly. This is accomplished by considering other aspects of subroutine call- return that would normally be apparent in the code, and eliminating those candidate subroutine returns that do not display such aspects. Specifically, these aspects are the STM (save context) which is typically done upon subroutine entry, and the LM (restore context) which is typi...