Improving virtual function call target prediction via dependence-based pre-computation
Amir Roth, Andreas Moshovos, Gurindar S. Sohi · 1999
We introduce dependence-based pre-computation as a complement to history-based target prediction schemes.We present pre-computation in the context of virtual finction calls (v-calls), a class of control transfers that is becoming increasingly important and has resisted conventional prediction.Our proposed technique dynamically identljies the sequence of operations that computes a v-call's target.When the first instruction in such a sequence is encountered, a small execution engine speculatively and aggressively pre-executes the rest.The pre-computed target is stored and subsequently used when a prediction needs to be made.We show that a common v-call instruction sequence can be exploited to implement pre-computation using a previously proposed prefetching mechanism and minimal additional hardware.In a suite of C++ programs, dependence-based pre-computation eliminates 46% of the mispredictions incurred by a simple BTB and 24% of those associated with a path-based two-levelpredictol: