A Practical Stride Prefetching Implementation in Global Optimizer
Hucheng Zhou, Xing Zhou, Tianwei Sheng, Dehao Chen, Jianian Yan, Shinming Liu, Wenguang Chen, Weimin Zheng · 2008
Software data prefetching is a key technique for hiding memory latencies on modern high performance processors. Stride memory references are prime candidates for software prefetches on architectures with, and without, support for hardware prefetching. Compilers typically implement software prefetching in the context of loop nest optimizer (LNO), which focuses on affine references in well formed loops but miss out on opportunities in C++ STL style codes. In this paper, we describe a new inductive data prefetching algorithm implemented in the global optimizer. It bases the prefetching decisions on demand driven speculative recognition of inductive expressions, which equals to strongly connected component detection in data flow graph, thus eliminating the need to invoke the loop nest optimizer. This technique allows accurate computation of stride values and exploits phase ordering. We present an efficient implementation after SSAPRE optimization, which further includes sophisticated prefetch scheduling and loop transformations to reduce unnecessary prefetches, such as loop unrolling and splitting to further reduce unnecessary prefetches. Our experiments using SPEC2006 on IA-64 show that we have competitive performance to the LNO based algorithms.