Effective compile -time analysis for data prefetching in Java

The memory hierarchy in modern architectures continues to be a major performance bottleneck. Many existing techniques for improving memory performance focus on Fortran and C programs, but memory latency is also a barrier to achieving high performance in object-oriented languages. Existing software techniques are inadequate for exposing optimization opportunities in object-oriented programs. One key problem is the use of high-level programming abstractions which make analysis difficult. Another challenge is that programmers use a variety of data structures, including arrays and linked structures, so optimizations must work on a broad range of programs. We develop a new unified data-flow analysis for identifying accesses to arrays and linked structures, called recurrence analysis. Prior approaches that identify these access patterns are ad hoc, or treat arrays and linked structures independently. The data-flow analysis is intra- and inter-procedural, which is important in Java programs that use encapsulation to hide implementation details. We show Java programs that traverse arrays and linked structure have poor memory performance. We use compiler-inserted data prefetching to improve memory performance in these types of programs. The goal of prefetching is to hide latency by bringing data into the cache prior to a program\u27s use of the data. We use our recurrence analysis to identify prefetching opportunities in Java programs. We develop a new algorithm for prefetching arrays, and we evaluate several methods for prefetching objects in linked structures. Since garbage collection is an integral part of Java, we evaluate the impact of a copying garbage collector on prefetching. We demonstrate how to improve the memory performance of the collector itself by using prefetching. This dissertation shows that a unified whole-program compiler analysis is effective in discovering prefetching opportunities in Java programs that traverse arrays and linked structures. Compiler-inserted data prefetching improves the memory performance even in the presence of object-oriented features that complicate analysis