Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms

Abstract:

This paper evaluates several mechanisms for repairing the
return-address stack after branch mispredictions. The return-address
stack is a small but important structure for achieving better
control-flow prediction accuracy and therefore better performance. But
wrong-path execution after mispredictions frequently corrupts the
return-address stack, making repair mechanisms necessary. If the
processor implements multipath execution -- simultaneously executing
both sides of a branch -- the contention among different paths makes
the problem more severe.

For conventional, single-path processors, this paper proposes saving
both the top-of-stack pointer and the top-of-stack contents for
later restoration in case of a misprediction. This simple technique
achieves nearly 100% hit rates and improves performance by up to
8.7% compared to a stack with no repair mechanism. For multipath processors,
providing each path with its own return-address stack completely
eliminates contention, improving performance by over 25%.

This technical report has been published as

Improving Prediction for Procedure Returns with Return-Address-Stack
Repair Mechanisms. K. Skadron, P.S. Ahuja, M. Martonosi, and D.W. Clark.
In Proceedings of the 31st Annual
ACM/IEEE International Symposium on Microarchitecture,
pp. 259-71, December 1998.