We present an automatic approach for prefetching data for linked list data structures. The main idea is based on the observation
that linked list elements are frequently allocated at constant distance from one another in the heap. When linked lists are
traversed, a regular pattern of memory accesses with constant stride emerges. This regularity in the memory footprint of linked
lists enables the development of a prefetching framework where the address of the element accessed in one of the future iterations
of the loop is dynamically predicted based on its previous regular behavior.
We automatically identify pointer-chasing recurrences in loops that access linked lists. This identification uses a surprisingly
simple method that looks for induction pointers — pointers that are updated in each loop iteration by a load with a constant offset. We integrate induction pointer prefetching
with loop scheduling. A key intuition incorporated in our framework is to insert prefetches only if there are processor resources
and memory bandwidth available. In order to estimate available memory bandwidth we calculate the number of potential cache
misses in one loop iteration. Our estimation algorithm is based on an application of graph coloring on a memory access interference
graph derived from the control flow graph. We implemented the prefetching framework in an industry-strength production compiler,
and performed experiments on ten benchmark programs with linked lists. We observed performance improvements between 15% and
35% in three of them.