Browse Prior Art Database

Subroutine Return Address Stack

IP.com Disclosure Number: IPCOM000048093D
Original Publication Date: 1981-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 3 page(s) / 66K

Publishing Venue

IBM

Related People

Losq, J: AUTHOR

Abstract

Branch History Tables (BHTs) are used to predict branches before they are decoded. The BHT keeps track of the last nitrogen taken branches executed by the machine (nitrogen being the BHT size) by keeping their target address in the table. It is an associative or set associative table that is accessed by instruction addresses. when an instruction is prefetched, its address is sent to the BHT. If there is a BHT hit (that is, there is an entry corresponding to that particular address), this means that the last time this instruction was executed, it was a taken branch. When there is a hit, the BHT provides the address of the target of the branch on the last execution of that branch (these addresses are kept in the BHT). This address is used to redirect the instruction prefetching.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 3

Subroutine Return Address Stack

Branch History Tables (BHTs) are used to predict branches before they are decoded. The BHT keeps track of the last nitrogen taken branches executed by the machine (nitrogen being the BHT size) by keeping their target address in the table. It is an associative or set associative table that is accessed by instruction addresses. when an instruction is prefetched, its address is sent to the BHT. If there is a BHT hit (that is, there is an entry corresponding to that particular address), this means that the last time this instruction was executed, it was a taken branch. When there is a hit, the BHT provides the address of the target of the branch on the last execution of that branch (these addresses are kept in the BHT). This address is used to redirect the instruction prefetching. The rationale behind this is that it is likely that if the last time the branch was executed it was taken, it is also going to be taken next time. Also, frequently the target address does not change between successive executions of the same branch, hence, the reason for using the old target address as the predicted new target address. However, this is not true for branches that implement subroutine returns. For them, the address of the target changes from one execution to the next. This would cause the prefetching of the instruction to be incorrect. This article deals with the problem of predicting the target address of subroutine returns.

The idea is to provide the BHT with a small stack (first-in- last-out stack). This stack is referred to as the Subroutine Return Address Stack.,When the BHT predicts that a given instruction is a taken BALR (Branch and Link Register) or BAL (Branch and Link), it will push down the stack the return address which is simply the byte address of the BALK instruction plus 2 (or BAL address plus 4). This address is available to the BHT sine it is the one used to access it for that particular instruction. However, the BHT will have to be able to know that it is a BAL or BALK. This can be simply done by adding a one bit field to the BHT entries indicating whether the branch is a BAL/BALR. Another way is to let the decoder make the entries in the stack at the time the BALs/BALRs get decoded. However, this may cause problems for short subroutines: the BHT is a few cycles ahead of the decoder and, hence, it may predict the return before the decoder has pushed the corresponding entry on the stack.

When the BHT predicts that an Instruction is a taken branch that implements a return form subroutine, the BHT pops the stack (gets the entry at the top of the stack) and uses it as the branch target address rather than the old target address (which is stored in the BHT). The rationale behind the use of such a stack is that subroutines are well nested: one exists first from the innermost subroutine and only then from the outer one. Fig. 1 shows an example of how the stack can be used to accurately keep track of...