Value Range Analysis of Conditionally Updated Variables and Pointers
Johnnie Birch, Robert van Engelen, Kyle A. Gallivan · 2004
Pointer-based array traversals are often used by C programmers to optimize sequential memory access. However, the use of pointer arithmetic prevents compilers from effectively applying dependence testing and loop analysis for optimization and parallelization. Because pointer variables can be viewed as reference-type induction variables, conventional induction variable recognition and substitution methods can be used to translate pointer-based code to array-based code, thereby enabling the application of traditional loop restructuring compiler optimizations for parallelization. However, conditionally updated induction variables and pointers are prohibiting the application of these optimizations, due to the inability to determine closed-form function equivalents. This paper presents a method for value range analysis on conditionally updated induction variables and pointers which have no closed-form functions.