COMPILER TRANSFORMATIONS FOR HIGH-PERFORMANCE COMPUTING

In the last three decades a large number of compiler transformations f or optimizing programs have been implemented. Most optimizations for u niprocessors reduce the number of instructions executed by the program using transformations based on the analysis of scalar quantities and data-flow techniques. In contrast, optimizations for high-performance superscalar, vector, and parallel processors maximize parallelism and memory locality with transformations that rely on tracking the propert ies of arrays using loop dependence analysis. This survey is a compreh ensive overview of the important high-level program restructuring tech niques for imperative languages such as C and Fortran. Transformations for both sequential and various types of parallel architectures are c overed in depth. We describe the purpose of each transformation, expla in how to determine if it is legal, and give an example of its applica tion. Programmers wishing to enhance the performance of their code can use this survey to improve their understanding of the optimizations t hat compilers can perform, or as a reference for techniques to be appl ied manually. Students can obtain an overview of optimizing compiler t echnology. Compiler writers can use this survey as a reference for mos t of the important optimizations developed to date, and as a bibliogra phic reference for the details of each optimization. Readers are expec ted to be familiar with modern computer architecture and basic program compilation techniques.