Value Profiling and Optimization

Brad Calder, Peter Feller, and Alan Eustace

Journal of Instruction Level Parallelism, March 1999.


Variables and instructions that have invariant or predictable values at run-time, but cannot be identified as such using compiler analysis, can benefit from value-based compiler optimizations. Value-based optimizations include all optimizations based on a predictable value or range of values for a variable or instruction at run-time. These include constant propagation, code specialization, optimizations assuming the value predictability of an instruction, continuous optimization, and partial evaluation.

This paper explores the value behavior found from profiling load instructions and memory locations. We compare the value predictability and invariant behavior of instructions (registers) and variables (memory locations) found from value profiling across different inputs. We use the value profiles to perform code-specialization, showing that value profiles can be used to reduce a program's execution time up to 21%. The ability to accurately and efficiently generate value profiles is also examined using convergent profiling and random sampling.