Code and data outlining
Peng Zhao · 2005
In this dissertation we investigate compiler techniques to address the performance problems caused by heterogeneous execution frequency of code in the same function and heterogeneous access pattern of fields in the same data structure. These heterogeneous characteristics are bad for performance. On one hand, it is frequent that instructions in the same function have very different execution frequencies. There is often infrequently referenced cold code, such as exception handlers, intertwined in frequently invoked hot functions. Cold code in hot functions not only degrades instruction cache efficiency but also makes host functions too large to be inlined. On the other hand, programmers organize their data layout in a semantically meaningful way that often does not match the runtime access pattern well. This data organization causes inefficient data cache utilization. We use compiler outlining techniques to address these performance problems that are difficult to handle by programmers. For programs with heterogeneous execution frequency, we use function outlining to split cold code out of the host function. Function outlining makes the host function smaller and more amenable for inlining optimization because the compiler is then able to do partial inlining, i.e., inline only the hot parts of a callee. To address the heterogeneous data pattern issue, we use data outlining or reshaping, which splits large data structures into smaller ones, to improve the efficiency of data cache. We describe in detail the necessary analysis and transformations needed to preserve correct program behavior in code and data outlining. In both function outlining and data outlining, we conduct a study of possible strategies. Our study shows that, although function outlining can be used to reduce function sizes (by up to 97%) and partial inlining improves performance by up to 5.75%, partial inlining has very limited effect on enabling more aggressive inlining for SPEC2000 benchmarks. The major benefits of partial inlining are actually the benefits of function outlining, which become more pronouncing when inlining is enabled. We also found that data reshaping could improve performance dramatically: one of the benchmarks studied achieves 2.1 times speedup with proper reshaping strategy. Detailed analysis explains these performance results.