Static transformation for heap layout using memory access patterns

Abstract

Unless the speed gap between CPU and memory disappears, efficient memory usage remains as a decisive factor for performance. As the hardware storage capacity and computing power grow, the amount of data used by programs also increase; we focus on the compiler optimizations - pool allocation and field layout reconstruction - that optimize data usage of programs according to the memory hierarchy. Most of the previous work relied on profiling, since it is difficult to foresee run-time behaviors of programs at compile-time. On the contrary, our goal is to develop a fully automatic stand-alone compiler that transforms input codes to use memory more efficiently. We notice that regular expressions, which present repetition explicitly, are suitable for memory access patterns. In this paper, we describe how to extract memory access patterns as regular expressions in detail. Based on static patterns, we apply pool allocation to repeatedly accessed structures, and then exploit field layout reconstruction according to field affinity relations of chosen structures. In order to make a scalable framework, we devise and apply new abstraction techniques while finding properties for entire programs. We implement our analyses and layout transformations with the CIL compiler. To verify the effect and scalability of our framework, we examine various benchmarks including SPECINT 2000. Our experiments demonstrate that the layout transformations for dynamic memory dramatically improve cache locality by 16% and performance by 14% on average.