Correlated Software Prediction for Indirect Branch in Dynamic Translation Systems

Dynamic translation system should perform an address translation for each execution of indirect branch instructions, so handling indirect branch becomes a major performance overhead of the system. The translation systems without hardware support always use software prediction to reduce the overhead of address translation, but the low prediction accuracy restricts the performance improvement. This paper analyzes the performance bottleneck of software prediction, and proposes a novel prediction mechanism called low-overhead correlated software prediction (LOCSP), which can significantly improve the prediction accuracy using branch correlation. LOCSP uses code replicas to distinguish the different branch occasions of an indirect branch instruction. By making different control flows execute different code replicas, and deploying individual software prediction chains for each replica, LOCSP realizes correlated prediction without any increase in dynamic instruction count. Meanwhile, LOCSP classifies the indirect branch instructions by dynamic profiling, and only applies correlated prediction on hot and hard-to-predict instructions, further minimizing prediction overhead. The experiment shows that, compared with software prediction, LOCSP can improve the average prediction accuracy from 58.9% to 82.2%, thus reduces the performance overhead by 19.3% on average, up to 41.9%, while only increases static code size by 2.4% on average. Furthermore, LOCSP can cooperate with other optimization techniques of handling indirect branch.