The Predictability of Branches in Libraries

Brad Calder, Dirk Grunwald and Amitabh Srivastava

28th International Symposium on Microarchitecture, pages 24-34, November 1995, WRL Research Report 95/6 version.


Profile-based optimizations are being used with increasing frequency. Profile information can be used to improve instruction scheduling, code layout, and to increase instruction level parallelism. These optimizations have been shown to be effective when they are applied to the same program from which the profile was gathered. However, it is an open question how profile-based optimizations should be applied to library subroutines. If many programs use libraries in the same way, it may be possible to ``pre-optimize'' a library, or to use an optimized shared library.

This study examines the use of commonly used libraries among 43 C and FORTRAN programs to see if the libraries have common behavior across different programs. We examine the behavior of the most commonly used Unix libraries on Digital Unix. We found that libraries have very predictable behavior between applications. This implies that profile-based compiler optimizations may be effective for libraries across applications. Therefore, one can use profile optimizations on shared and non-shared libraries before they are shipped, allowing a program using those libraries to take advantage of profile-based optimization without having to gather any profiles. All results in this study are shown using branch misprediction rates. We feel this metric indicates the likelihood that programs have similar behavior, and allows comparison to earlier branch prediction studies.