A Next Return Target Address stack to maintain return addresses for call
and return operations. The invention accommodates both definite return
addresses and speculative return address in a single stack. Return
addresses are written into the stack and read out of the stack at an
entry/exit register interior to the stack. The stack has a lower portion
below the entry/exit register for maintaining both actual and speculative
return addresses, and an upper portion above the entry/exit register for
maintaining return addresses that have been speculatively popped out. A
branch history register keeps an ongoing record of the most recent calls
and returns. In the event of a pipeline flush, such as would be caused by
a branch mispredict, the contents of the branch history register are
examined to determine how to adjust the contents of the stack. One or
more depth counters keep track of which contents in the branch history
register are to be examined.