Computing the correct Increment of Induction Pointers with application to loop unrolling

Induction pointers (IPs) are the analogue of induction variables (IVs), namely, pointers that are advanced by a fixed amount every iteration of a loop (e.g., $p=p\to \mathit{next}\to \mathit{next}$). Although IPs have been considered in previous works, there is no algorithm to properly compute the correct amount of pointer jumping (AOPJ) by which IPs should be advanced if loop unrolling is to be applied to loops of the form $\mathit{while}(p)\{\dots p=p\to \mathit{next}\to \mathit{next}\text{;}\}$. The main difficulty in computing the correct AOPJ of IPs is that pointers can be used to modify the data structure that is traversed by the loop (e.g., adding/removing/by-passing elements). Consequently, a simple advancement $p=p\to \mathit{next}$ in a loop does not necessarily mean that $p$ is advanced by one element every iteration. This situation contrasts with the use of IVs, which cannot change the structure of arrays that are traversed by loops. Hence, if $i$ is an IV, $A[i+1]$ will always mean the next element of $A[]$, while if $p=p\to \mathit{next}\text{;}$ is preceded by $p\to \mathit{next}=q\text{;}$ it may be advanced by $k>1$ elements at every iteration. The proposed method for computing the correct AOPJ of IPs and an accompanying loop unrolling technique were implemented in the SUIF compiler for C programs. Our experiments with automatic unrolling of loops with pointers yielded an improvement of 3–5% for a set of SPEC2000 programs. Experiments with a VLIW IA-64 machine also verified the usefulness of this approach for embedded systems.